Введение
1. Обзор и анализ алгоритмов решения задачи Штейнера для этапов трассировки соединений ЭВА 14
1.1 Постановка задачи глобальной трассировки СБИС 14
1.2 Постановка задачи построения дерева Штейнера для этапа глобальной трассировки СБИС 20
1.3 Обзор и анализ алгоритмов построения дерева Штейнера для этапа глобальной трассировки 26
Выводы 46
2. Разработка архитектуры, стратегии и выбор модели эволюционного поиска для этапа глобальной трассировки 47
2.1 Разработка модифицированной архитектуры стратегии генетического поиска 47
2.2 Разработка модифицированной схемы блока параллельного эволюционного поиска 54
2.3 Оценка эффективности генетических операторов для разработанных алгоритмов эволюционного моделирования 59
Выводы 62
3. Разработка комбинированных генетических алгоритмов построения дерева Штейнера 64
3.1 Описание комбинированного генетического алгоритма CombiGA 64
3.2 Выбор методики кодирования 75
3.3 Разработка алгоритма создания начальной популяции ...80
3.4 Описание алгоритма ускоренного поиска ортогональных деревьев Штейнера PTBGA 85
3.5 Теоретические оценки разработанных алгоритмов 96
Выводы 98
4. Экспериментальные исследования комбинированных генетических алгоритмов построения дерева Штейнера 100
4.1 Краткое описание программной и аппаратной среды 100
4.2 Цель экспериментального исследования 105
4.3 Этапы экспериментальных исследований 106
4.4 Результаты экспериментальных исследований разработанного алгоритма CombiGa 107
4.5 Результаты экспериментальных исследований разработанного алгоритма PTBGA 123
Выводы 140
Заключение 141
Список использованных источников 143
Приложение 155
Приложение А 156
Приложение Б 157
