Содержание к диссертации
ВВЕДЕНИЕ 4
1. АНАЛИЗ АЛГОРИТМОВ ТИПИЗАЦИИ ЭЛЕМЕНТОВ СБИС 14
1.1 Постановка и анализ задачи типизации элементов СБИС 14
1.2 Анализ и выбор математических моделей схем для задачи типизации 17
1.3 Постановка и анализ задачи типизации элементов СБИС на основе распознавания изоморфного вложения графов 21
1.4 Обзор существующих алгоритмов распознавания изоморфного вложения графов 26
1.5 Генетические алгоритмы как метод повышения эффективности алгоритмов распознавания изоморфного вложения графов 36
1.5.1 Символьная модель 38
1.5.2 Стратегии селекции и рекомбинации 41
1.5.3 Основные генетические операторы 43
1.5.4 Модели генетических алгоритмов 48
1.5.5 Общая схема генетического алгоритма 49
Выводы и рекомендации 51
2. РАЗРАБОТКА ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ ТИПИЗАЦИИ ЭЛЕМЕНТОВ СБИС НА ОСНОВЕ ВЫДЕЛЕНИЯ ИЗОМОРФНЫХ ПОДГРАФОВ 53
2.1 Разработка генетического алгоритма распознавания изоморфного вложения графов 54
2.1.1 Кодирование хромосом 55
2.1.2 Формирование начальной популяции 57
2.1.3. Расчет целевой функции хромосомы 65
2.1.4. Схема скрещивания хромосом 70
2.1.5. Операторы, используемые для улучшения целевой функции хромосомы 72
2.1.6. Оценка генетического разнообразия популяции 77
2.1.7 Критерий остановки и анализ сходимости 81
2.2 Разработка генетического алгоритма типизации элементов СБИС... 84
2.3 Решение задачи типизации элементов СБИС с учетом дополнительных ограничений и критериев 90
2.4 Теоретическая оценка временной сложности алгоритма типизации элементов СБИС 92
2.5 Повышение эффективности генетических алгоритмов 93
Выводы и рекомендации 95
3. РАЗРАБОТКА МНОГОАГЕНТНОЙ СИСТЕМЫ УПРАВЛЕНИЯ ГЕНЕТИЧЕСКИМ ПОИСКОМ РЕШЕНИЙ ЗАДАЧИ ТИПИЗАЦИИ ЭЛЕМЕНТОВ СБИС 97
3.1 Структура многоагентной системы 100
3.2. Описание интеллектуального агента-координатора 101
3.2.1 Распределение точек поиска на основе кластерного анализа 106
3.2.2 Управление количеством поисковых агентов на основе иерархического группирования 110
3.2.3 Комплексная оценка качества решений задачи типизации элементов СБИС 112
3.3 Управление параметрами реактивных агентов в процессе поиска оптимального решения 114
* 3.4 Адаптационный агент 122
Выводы и рекомендации 125
4. РАЗРАБОТКА ПРОГРАММНОЙ РЕАЛИЗАЦИИ АЛГОРИТМОВ И АНАЛИЗ ЭКСПЕРИМЕНТАЛЬНЫХ ИССЛЕДОВАНИЙ 127
4.1 Описание инструмента исследования 127
4.2 Исследование зависимости качества решений типизации от параметров генетического алгоритма 129
4.3 Оценка эффективности многоуровневого генетического алгоритма типизации элементов СБИС 131
4.4 Сравнение качества решений разработанных алгоритмов 135
Выводы и рекомендации 141
ЗАКЛЮЧЕНИЕ 142
ЛИТЕРАТУРА 145
ПРИЛОЖЕНИЕ 1 157
ПРИЛОЖЕНИЕ 2 162
Введение к работе
При создании современной электронной аппаратуры большое значение приобретают эффективные методы автоматизированного проектирования, которые позволяют создавать высоконадёжные СБИС в короткие сроки и при сравнительно низких затратах. Тенденция к росту степени интеграции СБИС приводит к существенному увеличению трудоёмкости проектирования, что вызывается ростом размерности решаемых при проектировании задач [1-5].
Производство интегральных схем разбивается на три этапа: проектирование, изготовление, тестирование. В виду значительной сложности ни один из этих этапов не может быть выполнен без средств автоматизированного проектирования [2, 6].
Одним из этапов проектирования СБИС является этап конструкторского проектирования, который включает в себя следующие стадии: компоновка, размещение, трассировка, верификация. Повысить эффективность алгоритмов комплексных систем автоматизации конструкторского проектирования позволяет разбиение схемы на части по критерию минимальной номенклатуры частей разбиения (критерию максимальной однотипности), то есть типизация частей(узлов) схемы. Сокращение номенклатуры узлов схемы позволяет, также значительно уменьшить затраты на дальнейшее проектирование: разработку фотошаблонов, контролирующих тестов и т. д. Существуют различные определения однотипных узлов. Наибольшее преимущество, применительно к комплексным САПР, дает типизация, когда под однотипными понимаются узлы, имеющие одинаковый состав элементов и одинаковую схему соединений с точностью до инвариантного контакта. В этом случае задача типизации может быть сформулирована как задача выделения в графе изоморфных подграфов [7].
Использование математических методов служит гарантией создания качественных систем проектирования. Эти методы состоят, в основном, из математических моделей, адекватных объектам проектирования, и алгоритмов оптимальных преобразований этих моделей с целью получения желаемого качества.
В настоящее время при создании и анализе структурных математических моделей схем используется аппарат теории графов. Это дает возможность строить математически обоснованные алгоритмы проектирования, находить простые и высококачественные решения, рационально и эффективно использовать ЭВМ [8, 9]. В качестве математических моделей схем используют специальные графы и гиперграфы, позволяющие адекватно отражать набор отношений, характерных для элементов СБИС [10-14]. Использование гиперграфов позволяет более точно и компактно описывать проектируемую схему, а также строить эффективные локально-оптимальные и точные алгоритмы решения исследуемых задач. Выбор математической модели для задачи типизации, когда требуется выделение изоморфных подграфов в моделирующем графе, зависит от размерности задачи.
Выделение в графе изоморфных подграфов является частным случаем распознавания изоморфного вложения графов. Разработка методов и алгоритмов для решения задач распознавания изоморфного вложения графов осуществляется на протяжении ряда лет, являясь, по-прежнему, актуальной. Это связано, в первую очередь, с тем, что эта задача является NP-полной, и, как следствие, затруднительна разработка алгоритма, позволяющего находить точное оптимальное решение за приемлемое время[15]. Появление новых, более совершенных методов, средств и технологий производства электронной техники, и, как следствие, увеличение степени интеграции цифровых и аналоговых микросхем является побудительной причиной для разработки новых алгоритмов распознавания изоморфного вложения графов и типизации в частности.
Существуют два метода решения задачи распознавания изоморфного вложения и изоморфизма графов. Первый метод основывается на последовательном вычислении инвариантов графов, с постоянным увеличением полноты вычисляемого инварианта. Алгоритмы, использующие данный метод относятся к непереборным. Последовательное увеличение полноты инвариантов сопровождается ростом временной сложности алгоритма вычисления инвариантов, что становится особенно заметным с ростом размерности задачи. Второй метод решения задачи распознавания изоморфного вложения графов связан с реализацией того же принципа, что и первый, но обязательно включает процедуру перебора на одном из этапов поиска изоморфной подстановки. Алгоритмы, реализующие второй метод относятся к переборным. Переборные алгоритмы используют относительно простые (легко вычислимые) инварианты графов, а основная трудоемкость алгоритмов этого типа заключается в переборе. Постоянный рост размерности задач конструкторского проектирования обуславливает необходимость комбинирования приближенных методов способных находить квазиоптимальные решения за полиномиальное время с точными методами для получения оптимального решения задачи типизации в комплексных САПР.
К приближенным методам относятся методы случайно-направленного поиска. Одним из методов случайно-направленного поиска является метод генетического поиска. Сейчас это хорошо известная оптимизационная методология, основанная на аналогии процессов натуральной селекции в биологии. Биологическая основа для адаптационных процессов - есть эволюция от одной генерации к другой, выполняющаяся путем исключения "слабых" и оставления оптимальных или квазиоптимальных элементов. В работе [16] содержится теоретический анализ класса адаптивных систем, в которых структурные модификации представляются последовательностями (стрингами) символов, выбранных из некоторого (обычно двоичного) алфавита. Поиск в поле таких представлений осуществляют так называемые генетические алгоритмы (ГА).
Основная особенность ГА состоит в том, что анализируется не одно решение, а некоторое подмножество квазиоптимальных решений, называемых "хромосомами" или стрингами. Это подмножество носит название "популяция". Для каждой хромосомы должна быть вычислена целевая функция F(n), называемая эволюционной, где п - число элементов в хромосоме. Такие функции вычисляют относительный вес каждой хромосомы в популяции. В каждой популяции хромосомы могут подвергаться действиям различных операторов. При этом происходят процессы, аналогичные действиям, которые имеют место в естественной генетике. К основным операторам относят: кроссинговер (ОК), инверсию (ОИ), мутацию (ОМ), транслокацию (ОТ) и сегрегацию (ОС) [16-23].
Достоинства ГА, в сравнении с другими подходами к решению задач комбинаторной оптимизации, заключаются в том, что они начинают работать с несколькими начальными решениями, позволяют легко распараллеливать процесс поиска, а также позволяют избежать попадания в локальные оптимумы, при этом комбинируя и наследуя элементы наиболее качественных решений [24 - 26].
Ввиду вышеизложенного, разработка алгоритмов, позволяющих найти приемлемое по качеству и по трудоёмкости решение задач типизации частей схем в комплексных САПР, является АКТУАЛЬНОЙ ПРОБЛЕМОЙ, стоящей перед разработчиками САПР и представляет научный и практический интерес.
ЦЕЛЬЮ диссертационной работы является разработка и исследование генетических алгоритмов типизации схем СБИС на основе изоморфного вложения графов, позволяющих находить оптимальные и квазиоптимальные решения задачи.
Для достижения поставленной цели в диссертации решаются следующее основные задачи:
1) Анализ задачи типизации и определение ее места в общей задаче конструкторского проектирования СБИС с применением комплексных САПР, а также анализ и обоснование выбора математической модели схемы для разрабатываемого генетического алгоритма типизации на основе распознавания изоморфного вложения графов.
2) Анализ принципов и схемы работы ГА, а также основных генетических операторов и их модификаций с точки зрения их пригодности для решения задачи типизации.
3) Построение общей схемы алгоритма распознавания изоморфного вложения графов, выбор методики кодирования решений, инициализации базового решения, а также методики позволяющей повысить качество отдельных решений.
4) Разработка алгоритма типизации элементов СБИС на основе генетического алгоритма распознавания изоморфного вложения графов и схемы применения генетических операторов.
5) Разработка методики определения функции оценки качества получаемых решений по критерию минимальной номенклатуры частей разбиения (минимальное число групп изоморфных подграфов).
6) Разработка концепции генетического поиска оптимальных решений задачи типизации элементов СБИС, на основе агентно-ориентированного подхода.
7) Теоретическая оценка быстродействия и эффективности разработанных алгоритмов типизации элементов СБИС.
8) Проведение имитационного программного моделирования (экспериментов).
Для решения поставленных задач использовались следующие МЕТОДЫ ИССЛЕДОВАНИИ: элементы высшей математики, теории графов и гиперграфов, алгоритмов, статистических вычислений, генетического поиска, теории многоагентных систем.
ОСНОВНЫЕ НАУЧНЫЕ РЕЗУЛЬТАТЫ диссертационной работы:
1) На основе анализа алгоритмов распознавания изоморфного вложения графов, разработана модифицированная процедура инициализации популяции с применением эвристики для формирования базового решения, позволяющая повысить среднее значение целевой функции на начальном этапе работы генетического алгоритма.
2) На основе анализа жадных стратегий локального улучшения целевой функции, разработана модификация жадного алгоритма, позволяющая повысить качество отдельных решений, учитывающая специфику решаемой задачи.
3) На основе генетического алгоритма распознавания изоморфного вложения графов разработан многоуровневый генетический алгоритм типизации элементов СБИС.
4) Разработана структура многоагентной системы управления поиском оптимального решения задачи типизации элементов СБИС на основе многоуровневого генетического алгоритма типизации, состоящая из интеллектуального агента-координатора, множества поисковых агентов и адаптационного агента.
5) Разработан механизм адаптации многоагентной системы управления генетическим поиском оптимального решения задачи типизации элементов СБИС на основе обучающейся системы классификаторов.
6) Проведено экспериментальное исследование разработанных алгоритмов с помощью созданного пакета программ, показало преимущество в скорости многоуровневого генетического алгоритма типизации на 5-12% над известными приближенными эвристическими алгоритмами, а также наличие положительного эффекта в виде повышения значения комплексной оценки качества решения задачи типизации на 10-20 % в сравнении с качеством решения задачи многоуровневым генетическим алгоритмом.
ОСНОВНЫЕ ПОЛОЖЕНИЯ, ВЫНОСИМЫЕ НА ЗАЩИТУ:
1) Процедура инициализации популяции с применением эвристики для формирования базового решения.
2) Модификация жадного алгоритма локального улучшения ЦФ, учитывающая специфику решаемой задачи.
3) Концепция применения ГА и общей схемы функционирования многоуровневого генетического алгоритма типизации элементов СБИС на основе распознавания изоморфизма графов.
4) Структура многоагентнои системы управления генетическим поиском оптимального решения задачи типизации элементов СБИС с механизмом адаптации на основе обучающейся системы классификаторов.
5) Результаты исследования трудоемкости предлагаемого многоуровневого генетического алгоритма типизации по сравнению с приближенными эвристическими алгоритмами и качества получаемых решений по сравнению с многоагентнои системой управления генетическим поиском оптимального решения.
ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют:
- генетический алгоритм и программа распознавания изоморфизма и изоморфного вложения графов;
- многоуровневый генетический алгоритм и программа типизации элементов СБИС;
- структура многоагентнои системы управления генетическим поиском оптимального решения задачи типизации на основе многоуровневого генетического алгоритма;
- результаты исследований эффективности разработанных алгоритмов. РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Основные теоретические и практические результаты диссертационной работы использованы в научно-исследовательской работе «Новые стратегии обучения нейронных сетей на основе вероятностных алгоритмов эволюционного поиска» №12392 по гранту Министерства образования РФ (шифр Е02-2.0-44), а также научно-исследовательской работе, выполненной по гранту Российского фонда фундаментальных исследований № 03-01-00336, Кроме того, материалы диссертации использованы в учебном процессе на кафедре САПР ТРТУ при чтении лекций и в цикле лабораторных работ по курсам «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования». АПРОБАЦИЯ основных теоретических и практических результатов работы проводилась на IV,V Всероссийской научной конференция с международным
участием молодых ученых и аспирантов (г. Таганрог, 2001 - 2002 гг.), Международной конференции «Интеллектуальные САПР» (CAD-2002, CAD-2003) (г. Геленджик, 2002 - 2003 гг.), Всероссийской научно-технической конференции с участием зарубежных представителей «Интеллектуальные САПР» (г. Таганрог, 2003 - 2004 гг.).
ПУБЛИКАЦИИ. Результаты диссертации отражены в 8 печатных работах. СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИОННОЙ РАБОТЫ. Диссертационная работа состоит из введения, четырех глав, заключения, и списка использованных источников. Работа содержит 164 стр., включая 35 рис., 3 табл., список использованных источников из 131 наименований и двух приложений, включающих акты об использовании. СОДЕРЖАНИЕ РАБОТЫ.
ВО ВВЕДЕНИИ обоснована актуальность темы диссертационной работы, дано общее описание выполненной работы.
В ПЕРВОЙ ГЛАВЕ Приведена постановка задачи типизации элементов СБИС. Рассмотрены графовые и гиперграфовые модели схем. Отмечено, что при решении задачи типизации необходимо использовать модели, учитывающие предварительные знания о решаемых задачах. Описан метод решения задачи типизации путем выделения изоморфных подграфов. Приведена постановка задач распознавания изоморфизма и изоморфного вложения графов. Рассмотрена классификация методов решения задач распознавания изоморфизма и изоморфного вложения графов на графовых и гиперграфовых моделях Проведен краткий обзор существующих методов решения задач распознавания изоморфизма и изоморфного вложения графов. Отмечено, что перспективными исследованиями являются разработка генетических алгоритмов и их модификаций для решения большого класса графовых задач и распознавания изоморфного вложения в частности, позволяющих решать проблемы предварительной сходимости алгоритмов и получать квазиоптимальные и оптимальные решения. Приведена общая схема генетического алгоритма. Рассмотрены модели процесса генетического поиска, методы селекции и отбора, выявлены их особенности и даны рекомендации по использованию. ВО ВТОРОЙ ГЛАВЕ на основе анализа операторов мутации и кроссинговера определены операторы, не приводящие к получению «нелегальных» решений, что обеспечивает сокращение пространства поиска и ведет к улучшению получаемых решений. Для кодировки хромосом выбраны универсальные представления в виде числовых векторных гомологичных хромосом, что обусловлено ограничениями на кодирование информации задачей типизации. Определена методика кодирования, учитывающая специфику решаемой задачи и позволяющая улучшить качество получаемых решений. Проведен комплексный анализ и выбор генетических операторов для использования в ГА распознавания изоморфизма. Разработана соответствующая структура генетических операторов, учитывающая специфику решаемой задачи, что позволяет избегать образования «нелегальных» решений, и улучшает качество получаемых решений. Описана схема инициализации популяций с применением эвристик, позволяющая на начальном этапе получить качественные решения, равномерно расположенные в пространстве поиска. В ТРЕТЬЕЙ ГЛАВЕ Описана структура многоагентной системы управления поиском решения задачи типизации элементов СБИС, состоящая из интеллектуального агента-координатора, множества поисковых агентов и адаптационного агента. Интеллектуальный агент-координатор реализует островную модель ГА, основанную на методе конкурирующих точек. При этом точки, представляют собой начальные «эталонные» графы и являются исходными данными для поисковых агентов. Поисковые агенты предоставляют решения задачи типизации, которые оцениваются и из них выбирается оптимальное, что позволяет вести поиск глобального оптимума. Описан алгоритм конкурирующих точек, применяемый для реализации островной модели ГА. Описанные механизмы распределения точек поиска на основе кластерного анализа и управления количеством поисковых агентов на основе иерархического группирования позволяют уменьшить время поиска оптимальных решений за счет сужения пространства поиска и соответственно, уменьшения количества активных поисковых агентов. В ЧЕТВЕРТОЙ ГЛАВЕ сформулирована цель исследования полученных результатов и выполнена статистическая обработка полученных данных. Выполненные расчеты подтвердили, в целом, полученные ранее теоретические оценки временной и пространственной сложности алгоритма. Это позволило получить ответы на вопросы прикладного характера, а также оценить разработанный алгоритм. Выполнено сравнение разработанного алгоритма МГАї типизации с одним из существующих приближенных эвристических алгоритмов типизации элементов СБИС и экспериментально подтверждено, что применение разработанного алгоритма позволяет от 5% до 12% сократить время решения задачи типизации. Исследование качества решений полученных в ходе работы многоагентной системы управления генетическим поиском на основе МГАї выявило положительный эффект состоящий в повышение значения комплексной оценки качества решения задачи типизации на 10-20 % в сравнении с качеством решения МГА].
В ЗАКЛЮЧЕНИИ изложены основные выводы и результаты диссертационной работы.
В приложениях приведены алгоритм распознавания изоморфизма графов и копии актов внедрения.
