Разработка теории и принципов поисковой адаптации для решения оптимизационных задач топологического синтеза

• Автор: Лебедев, Борис Константинович
• Шифр специальности: 05.13.18, 05.13.12
• Научная степень: Докторская
• Год защиты: 2001
• Место защиты: Таганрог
• Количество страниц: 384 с. : ил

СОДЕРЖАНИЕ
Введение
1. Проблемы, методы, состояние и практика решения задач автоматизированного проектирования СБИС

1.1. Основные задачи, решаемые при конструкторском проектировании СБИС

1.2. Методы оптимизации при решении задач конструкторского проектирования СБИС

1.2.1. Традиционные методы оптимизации

1.2.2. Основные понятия и определения адаптации

1.2.3. Моделирование отжига

1.2.4. Альтернативная поисковая адаптации на основе вероятностных обучающихся автоматов

1.2.5. Генетические алгоритмы

1.3. Задачи, методы и алгоритмы поисковой адаптации

1.3.1.Структура поискового алгоритма оптимизации.
1.3.2. Проблема представления в адаптивных алгоритмах оптимизации
1.3.3. Поисковая адаптация на основе сочетания самообучения,
самоорганизации и генетического поиска.
Выводы.
2. Разработка алгоритмов и моделей поисковой адаптации для решения задачи покрытия .
2.1. Проблемная формулировка, термины и определения
2.2. Формирование пространства решений.
2.3. Организация поисковой процедуры на основе коллективной адаптации для решения задачи покрытия
2.4. Структура, принципы кодирования и декодирования хромосомы .
2.5. Генетические операторы при покрытии
2.6. Организация процедуры генетического поиска для решения задачи покрытия.
2.7. Экспериментальные исследования
Выводы .
3. Построение оптимизационных процедур разбиения на основе
моделирования поисковой адаптации.
3.1. Введение.
3.2. Постановка задачи разбиения
3.3. Механизмы адаптации при разбиении
ЗАСтрукзура, принципы кодирования и декодирования хромосом
при разбиении
3.5. Генетические операторы при разбиении
3.6. Организация процедуры генетического поиска при разбиении
3.7. Экспериментальные исследования
Выводы
4. Формирование поисковых оптимизационных процедур на основе эволюционного моделирования для решения задачи размещения .
4.1. Проблемная формулировка, термины и обозначения
4.2. Формирование моделей среды и объекта адаптации
4.3. Организация процесса переразмещеиия
4.4. Общая структура адаптивного поиска при размещении .
4.5. Структура, принципы кодирования и декодирования хромосом при размещении.
4.6. Генетические операторы
4.7. Организация процедуры генетического поиска при размещении .
4.8 Экспериментальные исследования .
Вывод ы
5. Разработка интеллектуальных адаптивных поисковых алгоритмов
глобальной трассировки
5.1. Проблемная формулировка, термины и обозначения .
5.2. Распределение ресурсов коммутационного поля
5.3. Организация процесса коллективной адаптации при глобальной трассировке .
5.4. Структура, принципы кодирования и декодирования хромосом .
5.5. Генетические операторы .
5.6. Организация процедуры генетического поиска .
5.7. Интеллектуальная система построения дерева Штейнера на основе процедур отсечки и сужения пространства решений .
5.7.1. Постановка задачи построения дерева Штейнера .
5.7.2. Подход к построению дерева Штейнера.
5.7.3. Организация процесса построения дерева Штейнера на основе
отсечек
5.7.4. Метод сужения пространства решений .
5.8. Экспериментальные исследования
Выводы
6. Построение поисковых оптимизационных процедур распределения соединений между выводами на основе моделирования адаптивных процессов .
6.1. Проблемная формулировка, термины и обозначения .
6.2. Переключение соединений в канале .
6.3. Организация процесса коллективной адаптации при перераспределении соединений между выводами в канале
6.4. Механизмы генетического поиска при перекоммутации соединений
6.5. Динамическое распределение инвариантных контактов .
6.6. Экспериментальные исследования
Выводы .
7. Синтез интеллектуальных, адаптивных и динамических поисковых процедур детальной трассировки
7.1. Формулировка проблемы канальной трассировки .
7.2. Расчет нижних оценок .
7.3. Процедуры сужения и отсечения .
7.4. Динамический канальный трассировщик .
7.5. Трассировка в канале методом ветвей и границ
7.6. Трассировка в коммутационном блоке на основе генетических процедур .
7.6.1. Формулировка задачи, основные термины и обозначения .
7.6.2. Генетический алгоритм трассировки в коммутационном блоке
7.6.2.1. Структура хромосом, их кодирование и декодирование
7.6 Генетические операторы .
7.7. Канальная трассировка на основе генетических процедур .
7.7.1. Формулировка задачи, основные термины и обозначения .
7.7.2. Алгоритм генетической канальной трассировки .
7.7.2.1. Кодирование и декодирование хромосом
. Исходная популяция .
. Генетические операторы .
7.8. Однослойная трассировка в приканальной надъячеечной области .
7.8.1. Проблемная формулировка, термины и обозначения
7.8.2. Алгоритм надъячеечной трассировки .
7.8. Экспериментальные исследования
Выводы .
8. Разработка, на основе моделирования поисковой адаптации,
оптимизационных процедур разнесения соединений по слоям
8.1 Проблемная формулировка, термины, определения
8.2. Разбиение цепей на фрагменты
8.3. Формирование пространства решений .
8.4. Организация процесса коллективной адаптации при разнесении соединений по слоям.
8.5. Организация процесса генетического поиска при разнесении соединений по слоям .
8.6. Экспериментальные исследования . .
Выводы .
Заключение .
Литература


Поэтому очень большой класс алгоритмов основан на различного рода эвристиках, обеспечивающих получение приемлемого результата в полиномиальное время ,,,. Обычно такие алгоритмы разделяют на последовательные и итерационные. В основе работы этих алгоритмов поиск в пространстве состояний решений . Суть последовательных алгоритмов в последовательном сужении исходного пространства решений, пока в нем не останется одно решение. На каждом шаге выбранное на предыдущем шаге подпространство разбивается частичными решениями на подпространства. Например, при размещении подпространство разбивается на подпространства в соответствии с выбором элемента, размещаемого в рассматриваемую на данном шаге позицию. Затем в соответствии с эвристикой осуществляется выбор подпространства для разбиения на следующем шаге. Последовательные алгоритмы отличаются наименьшей трудоемкостью, но, с другой стороны, дают наименьшее качество. Так, для задачи трассировки это проблема очередности трассируемых соединении. Для задачи размещения это проблема очередности рассмотрения позиций или проблема очередности рассмотрения элементов. Дчя последовательных алгоритмов полное решение задачи получается после выполнения последнего шага. Напротив, итерационные алгоритмы предусматривают наличие какогото начального решения. Суть итерационных алгоритмов заключается в последовательном улучшении решения на каждой итерации. Поиск в пространстве состояний удобно представить в виде ориентированного графа СХ,и где Хх, ,2 . Стандартные итерационные алгоритмы не гарантируют получения глобального результата. Работа таких алгоритмов завершается либо после попадания в локальный оптимум, либо после выполнения очередного количества шагов. В последнее время дальнейшим совершенствованием итерационных алгоритмов была разработка поисковых методов, основанных на моделировании естественных адаптационных процессов. К таким методам относятся метод моделирования отжига , методы генетического поиска эволюционная адаптация ,,методы альтернативной поисковой адаптации на основе вероятностных обучающихся автоматов ,,. Являясь по своей сути итерационными, алгоритмы на основе моделирования отличаются от обычных итерационных процедур слепого поиска. Адаптация это способность живого организма или технической системы изменять свое состояние и поведение параметры, структуру, алгоритм и функционирование в зависимости от изменения условий внешней среды путем накопления и использования и формации о ней. Как правило, под адаптивной системой понимают систему, которая работает при наличии априорной неопределенности и изменяющихся внешних условий, а получаемую в процессе работы информацию об этих условиях используют для повышения эффективности работы системы. Адаптация является частным случаем управления со стабильными целями. Основные цели адаптации связаны с экстремальными требованиями, предъявляемыми к объекту адаптации в виде максимизации эффективности его функционирования. Основной задачей управления является организованное воздействие на объект управления ОУ, в качестве которого может выступать та или иная техническая система, которая переводит объект в требуемое состояние. Аналогичным образом строится система адаптации в САПР . Объектом управления является САПР, а адаптивным устройством управления специальная подсистема адаптации рис. Рис. На вход САПР поступает поток задач X. У получаемые решения. Каждое получаемое решение при этом динамически оценивается в блоке оценок БО. РХ получаемых решений критерии адаптации. Рис. Рассмотрим классификацию видов адаптации, представленную на рис. В зависимости от наличия или отсутствия модели объекта адаптации все виды адаптации делятся на два класса адаптация с моделью и поисковую адаптацию без модели. При наличии адекватной модели объекта адаптации связаны параметры входной задачи X, решения У, состояния объекта Б, адаптирующего воздействия . При изменении параметров X алгоритом на модели вычисляется необходимое адаптирующее воздействие и, которое должно перевести объект адаптации в требуемое состояние максимум эффективности и выполнение заданных ограничений.