Разработка и исследование генетических алгоритмов компоновки блоков ЭВА

• Автор: Смирнова, Ольга Валентиновна
• Шифр специальности: 05.13.12
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Ростов-на-Дону
• Количество страниц: 159 с. : ил

Содержание
Введение.

1. Анализ и состояние проблемы компоновки блоков ЭВА.

1.1 Графовые и гиперграфовые модели блоков ЭВА

1.2 Постановка задачи компоновки.

1.3 Обзор существующих алгоритмов разбиения

1.4 Выводы.

2. Разработка поисковых методов компоновки графовых

моделей блоков ЭВА

2.1 Классификация оптимизационных задач разбиения графов.

2.2 Использование эвристических поисковых методов при разбиении графов.

2.3. Построение архитектур генетического поиска при
разбиении графа на части.
2.4. Выводы
3. Разработка комбинированных генетических алгоритмов компоновки блоков ЭВА
3.1. Построение модифицированных генетических операторов
для разбиения графовых моделей на части
3.2. Разработка эвристического алгоритма разбиения графов
на основе агрегации фракталов
3.3. Разработка алгоритмов разбиения графов с использованием
клик, независимых множеств графов.
3.4. Выводы.
4. Экспериментальные исследования алгоритмов разбиения
графовых моделей схем ЭВА
4.1. Основные принципы построения программного обеспечения
для решения оптимизационных задач разбиения графов
4.2. Результаты экспериментальных исследований
4.3. Выводы.
Заключение.
Список использованной литературы


Наиболее приемлемой моделью, как известно [4-8], являются графы различного вида. Важно, чтобы абстрактная модель (граф) наиболее полно отражала конструктивные свойства схемы и обладала определеннными знаниями о решаемых задачах, что связано с правильностью получаемых результатов и качеством проектирования. Существует ряд методов перехода от блоков ЭВА к графам. Наиболее известный метод [6] заключается в том, что элементам схемы ставятся в соответствие ребра графа, а электрическим цепям - вершины. Этот метод успешно используется для анализа и синтеза электрических схем. Однако для решения задач, связанных с проектированием блоков ЭВА данный метод неприемлем. Для решения задач компоновки, как правило, используется метод перехода к графу 0=(Х. ХієХ, а электрические цепи представляются ребрами Н|€ Н, Х={хьх2,. Х|=п, и={иьи2,. Заметим, что каждый узел в схеме соединений блоков ЭВА в общем случае должен представляться в графе Сі полными подграфами. При переходе от схемы соединений к графу за счет развязки узлов (узел соответствует соединению всех элементов между собой), в графе появляются «лишние» ребра, т. ЭВА. Это с одной стороны вносит избыточную информацию, а с другой стороны может позволить перестраивать структуру графа после каждого этапа алгоритма. Например, для условной схемы соединений (рис. О', имеет вид показанный на рис. Устраняем в О’, в соответствии с цикломатичесмим числом у(0')=6, такие шесть ребер, чтобы в полученном графе не осталось ни одного цикла и он остался связанным. Таким образом, построим два из возможных покрывающих деревьев, показанных на рис Л Л,в,г. Очевидно, что в соответствии с формулой Кэли (^п”'2 []) можно получить = 5 изоморфных деревьев. Пусть условная схема (рис. Л ,а) должна быть разбита на две части по два и три блока в каждой. Тогда в первом разбиении (рис. Следовательно, простая перестройка дерева подграфа позволяет минимизировать количество внешних связей. В тех случаях, когда имеется возможность хранить большое количество вариантов изоморфных деревьев, и требуется получать оптимальное или квазиоптимальное решение, автор предлагает использовать указанный метод с перестройкой структуры графа. Часто используемся метод перехода от схемы соединений к графу, когда контактные площадки под элементы СБИС представляются вершинами графа 0=(Х,и), а соединения между ними - ребрами. При этом полученный граф С представляет собой объединение полных подграфов схемы. Если в каждом полном подграфе выделить покрывающее дерево, г. При таком способе резко возрастает число вершин исследуемого графа, но появляется возможность получения оптимального разбиения. Автор предлагает здесь также использовать перестроение деревьев после каждого этапа. Рис. Рис. Первое дерево Рис. Говорят, что задан гиперграф Н=(Х,Е), если задано множество вершин Х={Х|,х2,. Х|=п, Е={Є|,е2,. Х, ісі, 1={1,2,. Для моделирования схемы соединений гиперграфом предлагается следующее. Каждому элементу і=={ 1,2,. Х гиперграфа. Если электрическая цепь І соединяет элементы схемы 8Д,. Естественно, что в общем случае пересечение двух различных ребер не пусто, так как один элемент схемы может принадлежать различным электрическим цепям. Например, на рис. Гииерграфовая модель П=(Х,Е) представляющая эту схему показана на рис. Х|=5, |Е[=4, причем Є|={Х|,Х2,х3}, е:={хьх2,х4}, е4-{х3,х4,х5}. Отметим, что однозначной моделью гиперграфа Н=(Х, Е) является граф Кэнига [-] Сц=(ХиЕ,У). Граф Кэнига для гиперграфа Н (рис. Здесь V множество ребер графа Оц, указывающее на связь между множествами вершин X и Е. Для решения задач разбиения полученные графы и гиперграфы могут представляться различными способами. Наиболее удобными являются матрицы и списки соединений различного вида. Список ребер данного графа имеет ВИД и={(Х|,Х2), (х2,х3), (х3,х4), (х4,Х5)}. Матрицы смежности удобны при большой насыщенности схем связями. Практически матрицы смежности графов схем заполнены на % нулевыми элементами. Поэтому в некоторых случаях более целесообразно применять кодовую реализацию Як матрицы смежности Я. Для графа, показанного на рис.