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

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

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

1. Обзор и анализ генетических алгоритмов для решения задач проектирования БИС

1.1. Генетические операторы.

1.2. Генетические алгоритмы компоновки элементов СБИС.

1.3. Алгориты трассировки СБИС

1.4. Выводы.

2. Разработка архитектуры и стратегии генетического поиска генетических алгоритмов компоновки, группирования элементов и трассировки СБИС

2.1. Архитектура и стратегии.

2.2. Генетический алгоритм компоновки

2.3. Генетический алгоритм группирования элементов.
2.4. Генетический алгоритм трассировки СБИС построением дерева Штейнера.
2.5. Выводы
3. Разработка модифицированных генетических операторов
3.1. Представление хромосом по Нейману
3.2. Разработка модифицированных операторов кроссинговера
3.3. Разработка модифицированных операторов мутации.
3.4. Анализ разработанных генетических операторов
3.5. Выводы
4. Экспериментальные исследования разработанных генетических алгоритмов.
4.1. Программная среда для решения задач компоновки и группирования элементов СБИС.
4.2. Программная среда для решения задачи трассировки СБИС
4.3. Результаты экспериментальных исследований.
4.3.1. Порядок выполнения экспериментальных
исследований.
4.3.2. Результаты экспериментальных исследований генетических алгоритмов компоновки элементов СБИС
4.3.3. Результаты экспериментальных исследований генетических алгоритмов трассировки СБИС
4.4. Выводы
Заключение
Список литературы


Кроме того, материалы диссертации используются в учебном процессе на кафедре “ПМ и ВТ’ РГАСХМ при чтении лекций по дисциплинам “Дискретная математика” и “Программные средства САПР”. Модифицированные генетические алгоритмы компоновки и группирования элементов СБИС, позволяющие получать оптимальные решения за однократное срабатывание операторов. Генетический алгоритм трассировки СБИС, позволяющий получать оптимальные решения за полиномиальное время. Модифицированные операторы кроссинговера и мутации, основанные на представлении хромосом по Нейману. Апробация работы. Основные научные и практические результаты работы докладывались, обсуждались и были одобрены на Международых научно-технических конференциях “Интеллектуальные системы ’’(AIS-) и “Интеллектуальные CAFlP”(CAD-) (г. Геленджик г. VII Всероссийской научной конференции студентов и аспирантов “Техническая кибернетика, радиоэлектроника и системы управления” (КРЭС') (г. Таганрог г. Проблемы современного машиностроения”^. Ростов-на-Дону, РГАСХМ, , г. По материалам диссертационной работы опубликовано 6 работ, материалы вошли в два отчета по НИР. Публикации. Основные результаты диссертационной работы отражены в 6 печатных работах. Структура н объём диссертационной работы. Данная работа содержит четыре основных раздела. В первом разделе обзор и анализ известных генетических операторов и алгоритмов решения задач конструкторского проектирования. СБИС. Приводится описание алгоритмов построения дерева Штейнера и решения данных задач на графах. Показана трудоёмкость работы каждого из рассмотренных алгоритмов. Во втором разделе разработаны модифицированные архитектура и стратегии генетического поиска, ориентированные на решение задач компоновки элементов и трассировки СБИС. На основе предложенных архитектуры и стратегий генетического поиска предложены алгоритмы компоновки и группирования элементов СБИС, а также алгоритм трассировки соединений СБИС при построении дерева Штейнера. Описана работа каждого из предложенных алгоритмов, на основе модифицированных генетических операторах кроссинговера и мутации. В третьем разделе представлены предложенные модифицированные генетические операторы кроссинговера и мутации. Описана работа каждого из предложенных операторов. Дана сравнительная характеристика предложенных операторов кроссинговера и мутации с известными двухточечными операторами кроссинговера и мутации. В четвёром разделе приведены результаты экспериментального исследования разработанных алгоритмов с существующими и программное обеспечение для решения рассматриваемых задач проектирования СБИС. СБИС. Генетические операторы. Решение задач оптимизации на основе механизмов генетики являются эффективным средством решения оптимизационных задач [4,5, , ,,0-0], преимущество которых в параллельной обработке множества альтернативных решений, что является мощным средством выхода из локальных оптимумов. Генетические алгоритмы (ГА) - алгоритмы случайного поиска, однако заложенная в них стратегия эволюционного развития на основе естественного отбора приводит к синтезу решений, близких к оптимальным []. Объяснение принципа работы генетических алгоритмов представлено Д. Гольдбергом [3] как гипотеза о строительных блоках, в которой предполагается, что генетические алгоритмы выполняют одновременно две задачи. Первая заключается в выращивании строительных блоков, а вторая состоит в смешивании этих блоков с целью получения оптимального решения. Чтобы получить достаточно уверенную сходимость к глобальному оптимуму, необходимо, чтобы оба этих процесса были сбалансированы. Математические оценки эффективности генетических алгоритмов сформулированы в виде фундаментальной теоремы генетических алгоритмов [5]. Генетический алгоритм включает основные понятия и операции [ 2-7, , ,]: хромосома - закодированный вариант решения; ген - элемент решения; популяция - исходное множество вариантов решений; функция соответствия - критерий отбора вариантов; скрещивание -операция получения вариантов-отпрысков из вариантов-родителей; мутация -случайное изменение элементов хромосом.