Разработка и исследование генетических алгоритмов типизации элементов СБИС на основе изоморфного вложения графов

• Автор: Силютин, Денис Сергеевич
• Шифр специальности: 05.13.12, 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Таганрог
• Количество страниц: 165 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ.

1. АНАЛИЗ АЛГОРИТМОВ ТИПИЗАЦИИ ЭЛЕМЕНТОВ СБИС

1.1 Постановка и анализ задачи типизации элементов СБИС.

1.2 ААЛИЗ И ВЫБОР МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ СХЕМ ДЛЯ ЗАДАЧИ ТИПИЗАЦИИ

1.3 Постановка и анализ задачи типизации элементов СБИС на основе

РАСПОЗНАВАНИЯ ИЗОМОРФНОГО ВЛОЖЕНИЯ ГРАФОВ.

1.4 Обзор существующих алгоритмов распознавания изоморфного вложения ГРАФОВ.

1.5 Генетические алгоритмы как метод повышения эффективности алгоритмов распознавания изоморфного вложения графов

1.5.1 Символьная модель.

1.5.2 Стратегии селекции и рекомбинации.

1.5.3 Основные генетические операторы.
1.5.4 Модели генетических алгоритмов
1.5.5 Общая схема генетического алгоритма
Выводы и рекомендации.
2. РАЗРАБОТКА ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ ТИПИЗАЦИИ ЭЛЕМЕНТОВ СБИС НА ОСНОВЕ ВЫДЕЛЕНИЯ ИЗОМОРФНЫХ ПОДГРАФОВ.
2.1 Разработка генетического алгоритма распознавания изоморфного вложения графов.
2.1.1 Кодирование хромосом
2.1.2 Формирование начальной популяции
2.1.3. Расчет целевой функции хромосомы.
2.1.4. Схема скрещивания хромосом.
2.1.5. Операторы, используемые для улучшения целевой функции хромосомы
2.1.6. Оценка генетического разнообразия популяции
2.1.7 Критерий остановки и анализ сходимости
2.2 Разработка генетического алгоритма типизации элеме 1тов СБИС.
2.3 Решение задачи типизации элементов СБИС с учетом дополнительных ограничений и критериев
2.4 Теоретическая оценка временной сложности алгоритма типизации элементов СБИС
2.5 Повышение эффективности генетических алгоритмов.
Выводы и рекомендации.
т 3. РАЗРАБОТКА МНОГОАГЕНТНОЙ СИСТЕМЫ УПРАВЛЕНИЯ
ГЕНЕТИЧЕСКИМ ПОИСКОМ РЕШЕНИЙ ЗАДАЧИ ТИПИЗАЦИИ ЭЛЕМЕНТОВ СБИС
3.1 Структура многоагентной системы
3.2. Описание интеллектуального агентакоординатора
3.2.1 Распределение точек поиска на основе кластерного анализа
3.2.2 Управление количеством поисковых агентов на основе иерархического группирования
3.2.3 Комплексная оценка качества решений задачи типизации элементов СБИС
3.3 Управление параметрами реактивных агентов в процессе поиска
ОПТИМАЛЬНОГО РЕШЕНИЯ.
3.4 Адаптационный агент
Выводы и рекомендации
4. РАЗРАБОТКА ПРОГРАММНОЙ РЕАЛИЗАЦИИ АЛГОРИТМОВ И АНАЛИЗ ЭКСПЕРИМЕНТАЛЬНЫХ ИССЛЕДОВАНИЙ
4.1 Описание инструмента исследования
4.2 Исследование зависимости качества решений типизации от параметров генетического алгоритма.
4.3 Оценка эффективности многоуровневого генетического алгоритма типизации элементов СБИС.
4.4 Сравнение качества решений разработанных алгоритмов
Выводы и рекомендации
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


Отмечено, что перспективными исследованиями являются разработка генетических алгоритмов и их модификаций для решения большого класса графовых задач и распознавания изоморфного вложения в частности, позволяющих решать проблемы предварительной сходимости алгоритмов и получать квазиоптимальные и оптимальные решения. Приведена общая схема генетического алгоритма. ВО ВТОРОЙ ГЛАВЕ на основе анализа операторов мутации и кроссинговера определены операторы, не приводящие к получению «нелегальных» решений, что обеспечивает сокращение пространства поиска и ведет к улучшению получаемых решений. Для кодировки хромосом выбраны универсальные представления в виде числовых векторных гомологичных хромосом, что обусловлено ограничениями на кодирование информации задачей типизации. Определена методика кодирования, учитывающая специфику решаемой задачи и позволяющая улучшить качество получаемых решений. Проведен комплексный анализ и выбор генетических операторов для использования в ГА распознавания изоморфизма. Разработана соответствующая структура генетических операторов, учитывающая специфику решаемой задачи, что позволяет избегать образования «нелегальных» решений, и улучшает качество получаемых решений. Описана схема инициализации популяций с применением эвристик, позволяющая на начальном этапе получить качественные решения, равномерно расположенные в пространстве поиска. В ТРЕТЬЕЙ ГЛАВЕ Описана структура многоагентной системы управления поиском решения задачи типизации элементов СБИС, состоящая из интеллектуального агента-координатора, множества поисковых агентов и адаптационного агента. Интеллектуальный агент-координатор реализует островную модель ГА, основанную на методе конкурирующих точек. При этом точки, представляют собой начальные «эталонные» графы и являются исходными данными для поисковых агентов. Поисковые агенты предоставляют решения задачи типизации, которые оцениваются и из них выбирается оптимальное, что позволяет вести поиск глобального оптимума. Описан алгоритм конкурирующих точек, применяемый для реализации островной модели ГА. В ЧЕТВЕРТОЙ ГЛАВЕ сформулирована цель исследования полученных результатов и выполнена статистическая обработка полученных данных. Выполненные расчеты подтвердили, в целом, полученные ранее теоретические оценки временной и пространственной сложности алгоритма. Это позволило получить ответы на вопросы прикладного характера, а также оценить разработанный алгоритм. Выполнено сравнение разработанного алгоритма МГА1 типизации с одним из существующих приближенных эвристических алгоритмов типизации элементов СБИС и экспериментально подтверждено, что применение разработанного алгоритма позволяет от 5% до % сократить время решения задачи типизации. Исследование качества решений полученных в ходе работы многоагентной системы управления генетическим поиском на основе МГА| выявило положительный эффект состоящий в повышение значения комплексной оценки качества решения задачи типизации на - % в сравнении с качеством решения МГА1. В ЗАКЛЮЧЕНИИ изложены основные выводы и результаты диссертационной работы. В приложениях приведены алгоритм распознавания изоморфизма графов и копии актов внедрения. На этапе системотехнического (структурного) проектирования разрабатывается структурная схема устройства, определяются основные характеристики отдельных узлов. Целью схемотехнического проектирования является разработка логических схем устройства, разработка диагностических тестов, синтез схем отдельных узлов, моделирование и анализ полученных схем. Этап технического проектирования включает в себя конструкторское и технологическое проектирование. Основной задачей конструкторского проектирования является «материализация» функциональной схемы устройства, т. ФС) в набор конструктивно законченных изделий, реализующих эти схемы. Цель технологического проектирования - разработка технологии и получение технологической документации, необходимой для организации производства. Значимость задач конструкторского проектирования в общем цикле разработки ЭВА велика, и от эффективного решения конструкторских задач во многом зависит время проектирования и качество всего проекта в целом. Решаемые на этапе конструкторского проектирования задачи являются хорошо формализуемыми, и поэтому внедрение САПР именно в этой области является наиболее эффективным.