Разработка и исследование гибридных методов решения задач проектирования систем и устройств информатики, моделируемых графовыми моделями

• Автор: Старостин, Николай Владимирович
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2001
• Место защиты: Нижний Новгород
• Количество страниц: 147 с. : ил

Введение.
Глава I. Экстремальные задачи проектирования систем и устройств информатики, моделируемых с помощью графовых моделей .

1.1. Постановка и математическая формулировка задач оптимального проектирования

1.2. Численные методы решения экстремальных задач на графе.

1.3. Способы хранения и эффективной обработки графовых моделей.

1.4. Построение тестовых задач с учетом специфики графовых моделей

1.5. Цели и задачи исследования

Глава 2. Эволюциопиогенетическнй подход к решению экстремальных задач на графах.

2.1. Эволюционногенетический подход как подкласс направленных методов случайного поиска глобальных олтимзьных решений.

2.2. Представления решений задач на графах в виде списковых структур и перестановок.

2.3. Базовая структура генетического алгоритма.

2.4. Формирование начальной популяции и генерация новых решений на основе генетических операторов кроссовера и мутации.
2.5. Механизмы селекционного отбора наиболее предпочтительных решений
2.6. Гибридный метод и особенности его практической реализации.
Глава 3, Гибридный алгоритм оптимального разбиения графовых моделей и основные вопросы его программной реализации.
3.1. Постановка задач оптимального проектирования и представление решений в виде бинарных и Личных строк.
3.2. Операторы построения и контроля допустимости решений
3.3. Эвристические алгоритмы локального улучшения получаемых текущих решений
3.4. Вычислительный эксперимент на классе тестовых задач.
Глава 4. Решение задач оптимальной правильной раскраски графа
4.1. Постановка экстремальных задач и представление решений в виде перестановок.
4.2. Использование понятия жадности в операторах оценивания решений.
4.3. Вычислительный эксперимент на классе тестовых задач
Глава 5. Модификация гибридного алгоритма дли решения многокритериальных задач разбиения графа.
5.1. Постановка задачи построения совокупности оптимальнокомпромиссных решений
5.2. Модификация алгоритма для решения бикритериальной задачи разбиения графа
5.3. Использование алгоритмов локального улучшения решения по отдельным частным критериям.
5.4. Вычислительный эксперимент на классе тестовых задач
Глава 6. Построение оптимальных н оптимальнокомпромиссных модульных схем с помощью гибридных методов оптимального проектирования
6.1. Оптимальная компоновка типовых модулей принципиальной схемы регистра сдвига с переменной задержкой по блокам с минимальным числом связей.
6.2. Распределение непересекаюшихся цепей схемы регистра сдвига цифрового интегратора по минимальному числу слоев многослойной печатной платы
6.3. Компоновка типовых модулей принципиальной схемы регистра сдвига по блокам с минимизацией внешних связей и минимизацией тепловыделения отдельных блоков.
Заключение
Литература


В главе рассмотрены различные однокритериальные задачи оптимальной раскраски графа и описан единый подход к их решению, основанный на генетическом алгоритме. В 4. Параграф 4. Приводятся два алгоритма декодеров. Обсуждается целесообразность их применения в зависимости от используемого критерия качества вершинных правильных раскрасок. В 4. На примере известных задач приводится сравнительный анализ методов решения и делаются выводы об эффективности гибридного алгоритма. В главе 5 обсуждаются вопросы модификации алгоритма для решения многокритериальных задач на примере задачи разбиения графа. Рассматривается объединение нескольких критериев в единую скалярную функцию как один из методов решения задачи. Предлагается альтернативный подход, который предполагает модификацию генетического алгоритма для работы с вектором критериев, включив идею ларетгодоминирования в операторы естественного отбора и используя специальные методики для равномерного распределения решений вдоль паретограницы. В 5. Ставится задача построения области компромиссов и паретограниц для бикритериальной модели. Вводится модификация символьной модели алгоритма для векторной функции приспособленности. В 5. Вводится специальное множество, в котором до последнего поколения поиска накапливаются отбрасываемые недоминируемые решения. Рассматривается случай, когда недоминируемых решений больше или меньше текущего размера популяции. Для этих случаев предлагаются специальные процедуры первая позволяет из всего множества недоминируемых решений выбирать только те, которые равномерно распределены вдоль паретограницы, вторая процедура описывает методику, по которой добирается популяция до следующего поколения. Параграф 5. Предлагается модификация оператора локальной адаптации для многокритериальной оптимизации. В 5. В главе 6 рассматриваются реальные задачи оптимального проектирования, возникающие на этапе разработки печатных плат. В 6. Описывается методика сведения задачи оптимальной компоновки к задачи кразбиения графа. На примере схемы регистра цифрового интегратора демонстрируется возможности предложенного подхода. В 6. Приводятся принципы сведения задачи расслоения к задачам оптимальной правильной раскраски. На примере схемы регистра цифрового интегратора показаны основные этапы решения задачи и приводятся результаты расслоения принципиальной схемы регистра. В 6. Рассматриваемая задача оптимального проектирования сводится к бикритериальной задаче разбиения графа. Для схемы регистра цифрового интегратора рассчитываются компромиссные варианты разбиения схемы устройства. Разработан метод сведения экстремальных задач проектирования печатных плат задача компоновки типовых модулей принципиальной схемы устройства по отдельным блокам и задача расслоения цепей принципиальной схемы устройства по слоям, исключающих топологические пересечения проводников к задачам декомпозиции 1рафов задачи разбиения графа, задачи оптимальной правильной вершинной раскраски графа. Сформулированы правила представления допустимых решений задач декомпозиции графа в виде гичных списковых структур и перестановок фиксированной длины, что позволяет свести экстремальную задачу на графе к задаче поиска в пространстве Аичных структур. Для поиска оптимальной структуры в пространстве Личных структур предложен гибридный метод, в основе которого лежит совместное использование эволюционногенетического алгоритма глобального поиска и специальных эвристических процедур, основанных на использовании дополнительной информации о структуре допустимых решений и специфике экстремальной задачи на графе. Реализованы гибридные алгоритмы нахождения оптимальных для задач разбиения неориентированного взвешенного графа и задач оптимальной правильной раскраски графа. Разработаны новые операторы воспроизводства новых допустимых решений, основанных на эвристических конструктивных алгоритмах построения структуры нового допустимого разбиения из фрагментов других решений экстремальной задачи на графе, в том числе операторы кроссовера с компонентной коррекцией и структурный кроссовер.