Содержание к диссертации
Введение
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
- Обзор и анализ алгоритмов построения дерева Штейнера для этапа глобальной трассировки
- Разработка модифицированной схемы блока параллельного эволюционного поиска
- Описание алгоритма ускоренного поиска ортогональных деревьев Штейнера PTBGA
- Результаты экспериментальных исследований разработанного алгоритма CombiGa
Введение к работе
Достижение высокого научно-технического уровня производства невозможно без широкого внедрения автоматизации проектирования при создании различных устройств. Тенденции развития ЭВМ четвертого поколения связаны с развитием многопроцессорных систем, обладающих возможностью распараллеливания процесса решения, изменения структуры устройств в ходе решения задач, высоким быстродействием, технологичностью производства, живучестью и т. п. Наиболее эффективно использование параллельных вычислительных систем для решения задач управления подвижными объектами и моделирования сложных ситуаций и больших систем. В этом случае параллельные процессоры представляют собой не универсальные ЭВМ, а специализированные микропроцессоры, ориентированные для решения заданного круга задач. Такие параллельные системы известны в литературе как цифровые вычислительные структуры (ЦВС). Эти структуры являются типичным представителем ЭВМ четвертого поколения. Они ориентированы на решение специального класса задач, сводящихся к решению дифференциальных уравнений, уравнений в частных производных и воспроизведения сложных функциональных зависимостей.
Роль ЭВМ неизмеримо возросла благодаря достижениям последних лет в области микроэлектроники, что позволило решать такие задачи разработки и производства радиоэлектронной аппаратуры, которые по техническим и экономическим соображениям были совершенно нереальны прежде. Так, применение интегральных схем позволило на один—два порядка повысить плотность компоновки в единице объема, увеличить быстродействие радиоэлектронной аппаратуры, поднять надежность ее работы и приблизительно в десять раз уменьшить стоимость радиоэлектронных устройств. Указанные характеристики значительно улучшились с появлением больших интегральных схем (БИС). С точки зрения реализации
устройств на интегральных схемах оптимальным является выполнение их на одном типе ячеек с одинаковой конфигурацией соединений между ячейками, т. е. построения этих устройств в виде однородных ЦВС. ЦВС, реализованные на базе БИС, позволяют решить такие важные вопросы создания дискретных устройств, как высокая универсальность, технологичность изготовления, гибкость, надежность, эффективность функционирования.
Природа поражает своей сложностью и богатством всех своих проявлений. Среди примеров можно назвать сложные социальные системы, иммунные и нейронные системы, сложные взаимосвязи между видами. Они -всего лишь некоторые из чудес, которые стали более очевидны, когда мы стали глубже исследовать себя самих и мир вокруг нас. Наука - это одна из сменяющих друг друга систем веры, которыми мы пытается объяснять то, что наблюдаем, этим самым изменяя себя, чтобы приспособиться к новой информации, получаемой из внешнего мира. Многое из того, что мы видим и наблюдаем, можно объяснить единой теорией: теорией эволюции через наследственность, изменчивость и отбор.
Теория эволюции повлияла на изменение мировоззрения людей с самого своего появления. Теория, которую Чарльз Дарвин представил в работе, известной как "Происхождение Видов", в 1859 году, стала началом этого изменения. Многие области научного знания в настоящее время наслаждаются свободой мысли в атмосфере, которая многим обязана революции, вызванной теорией эволюции и развития. Но Дарвин, подобно многим своим современникам, кто предполагал, что в основе развития лежит естественный отбор, не мог не ошибаться. Например, он не смог показать механизм наследования, при котором поддерживается изменчивость. Его гипотеза о пангенезисе оказалась неправильной. Это было на пятьдесят лет до того, как теория наследственности начала распространяться по миру, и за тридцать лет до того, как "эволюционный синтез" укрепил связь между теорией эволюции и относительно молодой наукой генетикой. Однако
Дарвин выявил главный механизм развития: отбор в сочетании с изменчивостью или, как он его называл, "спуск с модификацией". Во многих случаях, специфические особенности развития через изменчивость и отбор все еще не бесспорны, однако, основные механизмы объясняют невероятно широкий спектр явлений, наблюдаемых в природе.
Поэтому неудивительно, что ученые, занимающиеся компьютерными исследованиями, обратились к теории эволюции в поисках вдохновения. Возможность того, что вычислительная система, наделенная простыми механизмами изменчивости и отбора, могла бы функционировать по аналогии с законами эволюции в природных системах, была очень привлекательна. Эта надежда стала причиной появления ряда вычислительных систем, построенных на принципах естественного отбора.
История эволюционных вычислений началась с разработки ряда различных независимых моделей. Основными из них были генетические алгоритмы и классификационные системы Голланда (Holland), опубликованные в начале 60-х годов и получившие всеобщее признание после выхода в свет книги, ставшей классикой в этой области, - "Адаптация в естественных и искусственных системах" ("Adaptation in Natural and Artifical Systems", 1975). В 70-х годах в рамках теории случайного поиска Растригиным Л.А. был предложен ряд алгоритмов, использующих идей бионического поведения особей. Развитие этих идей нашло отражение в цикле работ Букатовой И.Л. по эволюционному моделированию. Развивая идеи ЦетлинаМ.Л. о целесообразном и оптимальном поведении стохастических автоматов, НеймаркЮ.И. предложил осуществлять поиск глобального экстремума на основе коллектива независимых автоматов, моделирующих процессы развития и элиминации особей. Большой вклад в развитие эволюционного программирования внесли Фогел (Fogel) и Уолш (Walsh). Несмотря на разницу в подходах, каждая из этих "школ" взяла за основу ряд принципов, существующих в природе, и упростила их до такой степени, чтобы их можно было реализовать на компьютере.
Главная трудность с возможностью построения вычислительных систем, основанных на принципах естественного отбора и применением этих систем в прикладных задачах, состоит в том, что природные системы достаточно хаотичны, а все наши действия, фактически, носят четкую направленность. Мы используем компьютер как инструмент для решения определенных задач, которые мы сами и формулируем, и мы акцентируем внимание на максимально быстром выполнении при минимальных затратах. Природные системы не имеют никаких таких целей или ограничений, во всяком случае нам они не очевидны. Выживание в природе не направлено к некоторой фиксированной цели, вместо этого эволюция совершает шаг вперед в любом доступномее направлении.
Генетические алгоритмы в разных формах применяются к решению многих научных и технических проблем. Генетические алгоритмы используются при создании других вычислительных структур, например, автоматов или сетей сортировки. В машинном обучении они используются при проектировании нейронных сетей или управлении роботами. Они также применяются при моделировании развития в разных предметных областях, включая биологические (экология, иммунология и популярная генетика) и социальные (такие как экономика и политические системы) системы.
Тем не менее, возможно популярное применение генетических алгоритмов - оптимизация многопараметрических функций. Большинство реальных задач могут быть сформулированы как поиск оптимального значения, где значение - сложная функция, зависящая от определенных входных параметров. В некоторых случаях, нужно найти те значения параметров, при которых достигается точное значение функции. В других случаях, точный оптимум не нужен - решением может считаться любое значение, лучшее за определенную заданную величину. В этом случае, генетические алгоритмы - приемлемый метод для поиска "приемлемых" значений. Сила генетического алгоритма состоит в его способности манипулировать одновременно многими параметрами, которая используется
в сотнях прикладных программ, включая проектирование самолетов, настраивании параметров алгоритмов и поиске стойких состояний систем нелинейных дифференциальных уравнений.
Генетические алгоритмы являются эффективной процедурой поиска, которая конкурирует с другими процедурами. Эффективность генетических алгоритмов сильно зависит от таких деталей, как метод кодирования решений, операторов, настраивания параметров, отдельных критериев успеха.
Таким образом, проектирование и изготовление ЦВС на БИС невозможно без использования ЭВМ, являющихся незаменимым инструментом для расчета, изготовления, испытания, внедрения БИС и устройств, созданных на их основе. Однако использование ЭВМ для этих целей малоэффективно без наличия мощного специального математического обеспечения, под которым понимается создание автоматизированных систем проектирования (АСП). АСП, в общем случае, должны решать три категории задач: функциональное, техническое и технологическое проектирование.
Проблема автоматизированного проектирования эскиза топологии БИС— техническое проектирование — охватывает широкий спектр вопросов, включающих представление исходной электрической схемы в виде математических или матричных моделей, размещение типовых фрагментов топологии на рабочем поле кристалла, проектирование коммутационных связей между отдельными элементами, распределение фрагментов трасс в проводящих слоях кристалла, контроль топологии, компоновку узлов ЦВС и т. д. Очевидно, что решение этих задач традиционными "ручными" методами связано с большими затратами трудовых и временных ресурсов. Кроме того, значительно увеличивается вероятность внесения ошибок. Преодоление указанных трудностей возможно лишь с использованием ЭВМ, функции которой обусловлены режимом диалога с разработчиком в процессе вычислений.
Значительный интерес, проявляемый к проблеме машинного проектирования эскиза топологии соединений, во многом объясняется большой трудоемкостью этого этапа и невозможностью создания универсальных алгоритмов трассировки, одинаково эффективных для различных конструкций БИС. Известно большое число алгоритмов трассировки, основанных на различных методах построения, как отдельных трасс, так и цепей в целом. Важным вопросом при трассировке является построение кратчайших связывающих деревьев (КСД) цепей электрических схем.
Различают два принципа построения минимальных покрывающих деревьев. Первый состоит в том, что не допускается вводить дополнительные вершины. Такая задача называется построением минимального покрывающего дерева (МИД). Существуют эффективные алгоритмы Крускала, Прима и другие, предназначенные для построения МПД. Второй случай состоит в том, что разрешается вводить произвольное количество дополнительных вершин и соединяющих их ребер. Такая задача называется задачей Штейнера. Ее решение приводит к построению дерева Штейнера (ДШ), а дополнительные вершины называются точками Штейнера (ТШ).
В этой связи, тема работы, связанная с разработкой нового алгоритма трассировки схем, при проектировании СБИС, использующего методы генетического поиска в комбинации с другими итерационными методами, позволяющего сократить время поиска решений в задачах большой размерности, и в то же время повысить качество получаемых решений за счёт адаптивной архитектуры, является АКТУАЛЬНОЙ.
ЦЕЛЬЮ диссертационной работы является разработка методов глобальной трассировки цепей схем при проектировании СБИС на основе модифицированных структур генетического поиска, с элементами адаптации, по критерию суммарной длины связей, позволяющего получить решение с наименее возможной длиной цепей и повысить качество решений для задач большой размерности.
Для достижения поставленной цели были поставлены и решены следующие задачи:
,я
Проведен комплексный анализ известных методов оптимизации, существующих алгоритмов трассировки схем, а также анализ и обоснование выбора математической модели схем для разрабатываемого алгоритма трассировки схем при проектировании СБИС.
Разработка и анализ методов решения задачи Штейнера для этапа глобальной трассировки.
Создание модифицированных генетических операторов и процедур (кроссинговер, мутация, селекция).
Построение алгоритма формирования начальной популяции.
Создание структуры и принципов кодирования и декодирования хромосомы.
6. Разработка процедуры оценки и качества (целевой функции).
Для решения поставленных задач использовались следующие
МЕТОДЫ ИССЛЕДОВАНИИ: элементы теории множеств, элементы теории графов и гиперграфов, элементы теории алгоритмов, элементы теории генетического поиска.
НАУЧНАЯ НОВИЗНА диссертационной работы заключается в:
Разработке комбинированных генетических алгоритмов, построения дерева Штейнера, позволяющих повысить эффективность алгоритма и сократить время поиска решений.
Разработке модифицированных процедур для генетических операторов (кроссинговера, мутации), позволяющих повысить качество получаемых решений, а также устойчивость генетического поиска.
'*> 3. Разработке новой адаптивной архитектуры генетического поиска с
элементами адаптации, позволяющей оптимизировать процесс генетического поиска, представленной в виде общей структурной схемы, которая применима не только для поставленной задачи.
ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют:
Структура и принцип представления информации для генетических алгоритмов построения дерева Штеинера для задачи глобальной трассировки СБИС.
Алгоритмы и программное обеспечение для решения задачи построения дерева Штеинера для этапа глобальной трассировки СБИС, которые позволяют уменьшить длину соединительных проводников при проектировании СБИС.
Разработка новой адаптивной архитектуры генетического поиска с элементами адаптации, позволяющей оптимизировать процесс генетического поиска, представленной в виде общей структурной схемы,
^ которая применима не только для поставленной задачи.
РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ.
Основные теоретические и практические результаты диссертационной работы использованы в госбюджетной работе №12353 «Разработка теории и принципов построения интеллектуальных систем автоматизированного проектирования на основе эволюционной адаптации, нейросетевых моделей и методов принятия решений».
Материалы диссертации были использованы в учебном процессе на
№ кафедре САПР ТРТУ при чтении лекций по курсам «Методы оптимизации»,
«Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования».
Научные результаты, полученные в диссертационной работе
Калашникова Р.С., использовались в х/д НИР 12305 по теме «Исследование
алгоритмов решения Евклидовой задачи Штеинера для трассировки
электрических соединений».
4*f АПРОБАЦИЯ основных теоретических и практических результатов
работы проходила на Международной научно-технической конференции «Интеллектуальные САПР(САО-2002)» (г. Геленджик, 2002 г.), на Международной научно-технической конференции «Интеллектуальные САПР(САЕ>-2004)» (г. Геленджик, 2004 г.).
ПУБЛИКАЦИИ. По теме диссертации опубликовано 8 печатных работ.
СТРУКТУРА И ОБЪЁМ ДИССЕРТАЦИОННОЙ РАБОТЫ
Диссертационная работа состоит из введения, четырёх глав,
заключения, и списка использованных источников. Работа содержит стр.,
включая рис., табл., список использованных источников из
наименований, стр. приложений и актов об использовании.
СОДЕРЖАНИЕ РАБОТЫ.
Во ВВЕДЕНИИ обоснована актуальность темы диссертационной работы, сформулированы цели, дано общее описание выполненной работы.
В ПЕРВОЙ ГЛАВЕ приведена постановка задачи трассировки соединений как заключительного этапа конструкторского проектирования ЭВА. Рассмотрены основные алгоритмы и методы решения задач построения дерева Штейнера применяемых при трассировке СБИС. Выявлены их достоинства и недостатки. Описаны методы генетического поиска, основные генетические операторы, их отличие от других оптимизационных и поисковых методов.
Во ВТОРОЙ ГЛАВЕ проведена разработка архитектуры стратегии
генетического поиска для решения задачи трассировки. Проведена
v#/ разработка модифицированной схемы блока параллельного эволюционного
поиска. Проведен анализ и выбор модели генетического поиска для решения
задачи глобальной трассировки схем при проектировании СБИС.
В ТРЕТЬЕЙ ГЛАВЕ описано решение задачи построения дерева
Штейнера как части задачи глобальной трассировки схем при
проектировании СБИС при помощи генетического алгоритма с элементами
адаптации. Приведена структурная схема разработанного комбинированного
>, генетического алгоритма. Выбран оптимальный метод кодирования,
наиболее приемлемый, из всех существующих, для решения ортогональной задачи построения дерева Штейнера. Разработан комбинированный алгоритм создания начальной популяции. Определены теоретические оценки временной и пространственной сложности разработанного алгоритма.
В ЧЕТВЕРТОЙ ГЛАВЕ приведено описание экспериментальных исследований разработанного генетического алгоритма. Выполнена статистическая обработка полученных экспериментальных данных. Проделанные расчёты позволили подтвердить полученные ранее теоретические оценки временной и пространственной сложности разработанного алгоритма. Определены диапазоны оптимальных значений параметров генетического поиска. Выполнено сравнение результатов работы разработанного метода с известными аналогами. Представлено описание программного обеспечения для генерации, решения и исследования, различных графовых моделей схем для задачи трассировки схем при проектировании СБИС.
В ЗАКЛЮЧЕНИИ изложены основные выводы и результаты диссертационной работы.
В приложениях приведены копии свидетельства о регистрации программы и актов об использовании тексты программы для ЭВМ.
Обзор и анализ алгоритмов построения дерева Штейнера для этапа глобальной трассировки
Проблема построения кратчайших связывающих сетей одна из наиболее сложных при автоматизированном проектировании внутрисхемных соединений электронных устройств. Поскольку при машинной трассировке соединений используется ортогональная опорная сетка, интерес представляет построение связывающих деревьев Штейнера в ортогональной метрике. Существует множество различных алгоритмов построения деревьев Штейнера. Все алгоритмы решения данной оптимизационной задачи можно разделить на несколько видов. Существующие алгоритмы могут одновременно принадлежать к нескольким перечисленным ниже видам.
Динамическое программирование - это математический метод поиска оптимального управления, специально приспособленный к многошаговым процессам. Динамическое программирование [3] служит эффективным методом решения задач оптимизации дискретных многостадийных процессов, для которых критерий оптимальности задается как аддитивная функция критериев оптимальности отдельных стадий. Без особых затруднений указанный метод можно распространить и на случай, когда критерий оптимальности задан в другой форме, однако при этом обычно увеличивается размерность отдельных стадий. Результаты решения обычно не могут быть выражены в аналитической форме, а получаются в виде таблиц. Таким образом указанные методы при поиске новых решений используют информацию, полученную на предыдущих шагах (итерациях) алгоритма. Знание о получаемых решениях способствует формированию определенного поискового пространства, в котором будет происходить поиск новых решений. Естественно, данные методы требуют больших ресурсов памяти для хранения промежуточных результатов и мощный процессор для обработки массивов данных. ВСА этих методов составляют 0(ап ). Комбинаторные методы - предназначены для поиска оптимального решения в некотором конечном множестве. В большинстве случаев они используют различные варианты сокращенного перебора, поскольку полный перебор в реальных задачах неосуществим из-за слишком большой их размерности. Наиболее распространенный из этих методов — метод ветвей и границ. Алгоритмы с применением метода ветвей и границ основаны на идее последовательного разбиения множества на заданное число подмножеств и формировании оценок, позволяющих рассматривать только те подмножества, которые могут содержать решение задачи (т.е. отбрасываются заведомо не перспективные варианты). Основной недостаток этих методов заключается в необходимости корректного выбора оценок, в противном случае (при неверном выборе) данный метод будет осуществлять полный перебор. Временная сложность алгоритмов данного типа лежит в пределах от 0(ап ) до 0(ап4).
Одним из важнейших классов является - эвристические методы. Для этого класса алгоритмов нет четкого математического обоснования, отсутствуют оценки точности решений и условия, гарантирующие получение корректных результатов. В их основе лежат логические выводы. Данные методы не гарантируют нахождение оптимального решения и сильно зависят от класса и описания решаемой задачи. Эвристические методы на практике позволяют получать неплохие результаты, однако предсказать их поведение невозможно. Эвристические методы могут использоваться как самостоятельно, так и в соединении с другими методами, используя найденное с помощью эвристики решение в качестве исходного и дальнейшего улучшения его каким-либо другим, например, комбинаторным методом. Это позволяет значительно сократить время решения задачи. Сложность эвристических алгоритмов может быть любой, но большинство известных алгоритмов имеют ВСА от О(ап) до 0(ап ).
В [4] предлагается алгоритм построения дерева Штейнера основанный на методе горизонтальных (вертикальных) столбов Штейнера. Этот метод заключается в том, что из любой точки, которую требуется соединить деревом Штейнера, проводится горизонтальный столб Штейнера, а затем из остальных точек проводятся перпендикулярные отрезки на этот столб. Таким образом, строится дерево Штейнера. Далее перебираются все варианты точек, через которые проводится горизонтальный столб Штейнера, из которых выбирается наилучший, т.е. тот вариант дерева Штейнера при котором сумма всех соединений минимальна. Аналогичным образом строится вертикальный столб Штейнера и дерево Штейнера с использованием описанного выше метода.
При оценке временной сложности алгоритма принимаем во внимание тот факт, что основное время работы алгоритма тратится на соединение перпендикулярными отрезками точек с горизонтальным (вертикальным) столбом, которое равно T(V), а также на перебор всех вариантов точек через которые проводится горизонтальный (вертикальный) столб, которое также равно T(V). Таким образом получаем зависимость T(V ).
Таким образом, главным достоинством алгоритма построения дерева Штейнера методом горизонтальных (вертикальных) столбов является большая скорость исполнения. Существенным недостатком этого метода является тот факт, что в результате получается дерево, сумма ребер которого далека от минимально возможной.
Другим из известных алгоритмов построения дерева Штейнера является метод основанный на раздельности (ZRST). НО, Vijauan, и Wong [122] представили метод получения оптимальных ортогональных ДШ из МПД, если МПД удовлетворяет специальному свойству т.н. раздельность. Пара несмежных ребер называются раздельными, если их ступенчатые макеты не пересекаются и частично не накладываются. МПД называется раздельным (SMST) если все пары несмежных ребер удовлетворяют этому свойству. Если удалить ребро из такого SMST, ступенчатые макеты двух результирующих поддеревьев не пересекутся и не будут покрывать друг друга. Наложения могут произойти только между двумя ребрами имеющими общую вершину. Это свойство дает возможность использования динамического программирования для получения оптимального S-RST (раздельное ортогональное дерево Штейнера).
Алгоритм работает в два шага. На первом шаге разраздельное дерево SMST Т получается путем объединения множества Np точек модифицированным алгоритмом Прима за время 0(NP ). На втором шаге находится оптимальное Z-RST (при использовании SMST, полученного на первом шаге) за время 0(Np tmax6), где Uax - максимальное из всех t(e), где t(e) - число ребер в ортогональном макете ребра е SMST-дерева Т. В соответствии с теоремой Z-достаточности [121] оптимальное Z-RST является оптимальным S-RST деревом.
Разработка модифицированной схемы блока параллельного эволюционного поиска
В данной диссертации автором проведена разработка блока параллельного эволюционного поиска, как модификации схемы предложенной в [9]. На рисунке 2.3 представлена модифицированная схема разработанного блока параллельного эволюционного поиска. Суть работы блока параллельного эволюционного поиска заключается в разбиении исходной популяции хромосом на две подпопуляции. Далее параллельным способом применяется один из комбинированных генетических алгоритмов построения дерева Штейнера представленных в диссертации (подробное описание приведено в главе 3). Полученные результирующие подпопуляции передаются в блок миграции, где происходит миграция хромосом между полученными подпопуляциями. Миграция [9] - процедура установления порядка обмена хромосом между популяциями. Таким образом, подпопуляции на этом шаге обмениваются хромосомами с вероятностью 30%. Т.е. каждая третья хромосома из одной подпопуляции попадает в другую. Далее происходит модификация каждой из подпопуляции по разным схемам. Модификация первой подпопуляции происходит по эволюционной схеме Дарвина. Модель эволюции Ч. Дарвина - это условная структура, реализующая процесс, посредством которого особи некоторой популяции, имеющие более высокое функциональное значение, получают большую возможность для воспроизведения потомков, чем «слабые» особи. Такой механизм часто называют методом «выживания сильнейших». Движущими силами эволюции по Ч. Дарвину являются: неопределенная изменчивость, то есть наследственно обусловленное разнообразие организмов каждой популяции; борьба за существование, в ходе которой устраняются от размножения менее приспособленные организмы; естественный отбор - выживание более приспособленных особей, в результате которого накапливаются и суммируются полезные наследственные изменения и возникают новые адаптации. Существует спектр путей развития, по которым может пойти эволюция Ч. Дарвина. Возможный путь развития здесь определяет случайность. Эволюция по Ч. Дарвину состоит из следующих положений: в природе все подвержено неопределенной наследственной изменчивости, производится потомство, отличающееся по многим признакам. все организмы в природе размножаются в геометрической прогрессии, но численность всех организмов в среднем остается более или менее постоянной, она колеблется около средней величины. основой отбора является метод «выживания сильнейших». Моделирование эволюции может предоставить алгоритмические средства для решения оптимизационных задач. В общих чертах, эволюция может быть описана как многоступенчатый итерационный процесс, состоящий из случайных изменений и последующей затем селекции. Таким образом, существует взаимосвязь между определением эволюции и оптимизационными алгоритмами. На основе данной схемы можно составить примерный алгоритм модели эволюции по Ч.Дарвину. 1. Популяция. Пусть существует популяция особей (например, табун лошадей) на некоторой территории обитания (например, степь). Табун (популяция) насчитывает 50 взрослых лошадей (особей). 2. Наследственность. Каждый год в табуне (популяции) рождаются жеребята (новое поколение, потомство). 3. Изменчивость. Все родившиеся жеребята (потомки) отличаются друг от друга и от родителей цветом, размерами, ростом, физическими данными (скорость, выносливость и т.д.). 4. Отбор. Наибольшие шансы выжить и закрепиться в табуне (популяции) имеют физически более мощные жеребята (способность к самозащите, возможность победить соперников, способность к воспроизводству), обладающие большей скоростью (возможность спастись от хищников), выносливостью (способность преодолевать большие расстояния в поисках пищи). Тогда как слабые, больные жеребята (особи), а также жеребята, имеющие какие-либо отклонения (чересчур короткие или длинные ноги, слишком низкий или слишком высокий рост и т.д.), как правило, погибают. В то же время в ходе эволюции могут появляться особи с так называемыми «полезными» отклонениями от доминирующего в табуне (популяции) «стандарта» (генотипа), которые позволяют их носителям успешнее выживать в существующих условиях. 5. Эволюционная смена форм. Именно такие особи, как правило, , выживают в результате схемы эволюции Дарвина и они постепенно, поколение за поколением становятся преобладающим (доминирующим) видом в данной популяции. Модификация второй подпопуляции происходит по эволюционной схеме Де Фриза. В ее основе лежит моделирование социальных и географических катастроф, приводящих к резкому изменению видов и популяций. Эволюция, таким образом, представляет собой последовательность скачков в развитии популяции без предварительного накопления количественных изменений в эволюционных процессах. Такой механизм эволюции иногда называют эволюцией катастроф. Он проявляется один раз ориентировочно в несколько тысяч поколений. Основная идея его состоит во внесении глобальных изменений в генофонд на момент k i катастрофы. Тогда алгоритм эволюции по Г. де Фризу можно представить следующим образом. Пусть существует известная нам популяция хромосом, полученная на предыдущих этапах. В ходе эволюции данной популяции происходит смена поколений. Причем происходящие изменения генотипа популяции носят регулярный постепенный характер.
Описание алгоритма ускоренного поиска ортогональных деревьев Штейнера PTBGA
Основной сложностью применения генетических алгоритмов для построения прямолинейных деревьев Штейнера является оптимальное кодирование хромосом в популяции. Существует ряд методов и способов кодирования минимальных покрывающих деревьев и деревьев Штейнера. Опишем наиболее современные и распространенные методы.
В [12] предложен метод кодирования с помощью таблицы маршрутов (routing table). Метод основан на кодировании хромосом с помощью генов описывающих маршруты в графе. Доказано, что в графе G=(V,E), существует V х (V-1) возможных пар типа «источник-цель». Пара «источник-цель» может быть соединена с помощью набора связей (ребер графа), называемого «маршрутом» («route»). Обычно существует множество маршрутов между источником и целью в каждой паре. Например, в графе, представленном на рисунке 3.1, возможные маршруты между v0 и V4 следующие: Vo - v4, v0 - V5 -V4, ..., и так далее. Метод кодирования представлен таблицей маршрутов, включающей в себя R возможных маршрутов построенных для каждой пары «источник-цель». Например на рисунке 3.7 представлена таблица маршрутов для пары (vo,v4). Размер таблицы маршрутов - R - является параметром представленного метода. Возможные маршруты в таблице маршрутов могут быть отсортированы с по их длине (по числу связей). Это важно для решения
задач построения минимальных покрывающих деревьев. Таким образом для вершины-источника Vo и набора вершин-целей D={ ub ub..., uk}, хромосома может быть представлена строкой целых чисел (стрингом) длиной к. Ген gi (1 і к) хромосомы в массиве {0,1,..., R-1} представляет возможный маршрут между v0 и щ, где и{ є D. Связь между хромосомой, геном и таблицей маршрутов представлена на рисунке 3.8. Очевидно, что хромосома является представлением решения задачи построения минимальных покрывающих деревьев, так как она содержит информацию о маршруте между вершиной-источником и любой из вершин-целей. Однако хромосома не обязательно может представлять дерево, что не является серьезной проблемой, так как граф (хромосома) с циклами и неудовлетворительным значением целевой функции будет удален в последующих поколениях (популяциях). Возможно использовать метод кодирования, в котором хромосома будет представлять дерево. Важным достоинством этого метода является то, что по полученной хромосоме можно легко определить граф, т.е. достаточно легко декодировать.
В [19] разработчик компании Intel Corporation Марк Рабкин описал следующий вариант кодирования дерева Штейнера. Метод заключается в том, что через все точки (вершины) исходного множества проводятся горизонтальные и вертикальные линии, образующие решетку Ханаана. Точки пересечения решетки какой-либо области будут являться возможными вариантами точек Штейнера. Таким образом хромосома будет состоять из битов (bit-string) соответствующих вариантам возможных точек Штейнера. Разрядность каждого бита является двоичной: 1 - присутствие данной точки Штейнера,: 0 - отсутствие точки Штейнера.
Другая методика кодирования, представленная в [13,14] в различных модификациях, состоит в следующем. Битовые строки (стринги) включают в себя информацию о координатах точек Штейнера. При этом каждый стринг (ген) содержит информацию о некоторых флагах, используемых для генерации точек Штейнера, и координатах точек Штейнера в одной из областей (частей), на которые разбит граф (множество точек на координатной плоскости). Достоинство этого метода состоит в исключении получения циклов в графе (недостаток первого метода) и в отсутствии каких-либо проблем при декодировании хромосомы. Это связано с тем что хромосома не содержит информацию о ребрах, соединениях и вершинах графа, что исключает изменение положения точек графа при применении генетических операторов, таких как кроссинговер, мутация и т.д.
Еще один метод кодирования предложен китайскими учеными Zhou Xianwei, Chen Changjia и Zhu Gang [17]. Основная идея кодирования состоит в следующем: генотип представляет собой набор точек Штейнера. Декодер вычисляет соответствующее решение для избранных точек Штейнера и вершин (которые необходимо соединить) с помощью существующих эвристик (например построение дерева Прима-Крускала). Избранные точки Штейнера описываются бит-стрингах (bitstring), в которых каждый бит (ген) соответствует своей вершине. Например генотип описан следующим образом: {(7i(0),t Я(о)), ... , (7i(s-l),t тф-і))}, где s- количество возможных точек Штейнера, tk є {0,1},к = 0,1,...,5--1. Точки Штейнера 5 є V\ W определются генотипом следующим образом: S = {vk є Vtk =1}. Т.е. точки S являются точками Штейнера и входят в состав дерева, если tk = 1. Дерево Штейнера в графе G, соответствующее генотипу, вычисляется любым эвристическим методом используя набор SuWu{s} как набор вершин, которые необходимо соединить.
Предложенный в данной работе автором метод кодирования является развитием (модификацией) предпоследней методики. В процессе кодирования граф необходимо разбить на области, включающие три, четыре или пять вершин. Каждый стринг содержит информацию о координатах точек Штейнера (их количество колеблется от 0 до 2 в каждой области) своей области. Пример представлен на рисунках 3.9, 3.10. Алгоритм создания начальной популяции с помощью этого метода будет описан в следующей главе. На рисунке 3.9 представлен пример условного исходного коммутационного поля блоков ЭВА. Далее представлена графовая модель исходного коммутационного поля, и результат кодирования в виде хромосомы.
Результаты экспериментальных исследований разработанного алгоритма CombiGa
В этом эксперименте изменяемым параметром является вероятность инверсии. Интервал значений этого параметра: {0%;100%} с шагом 10%. Исследования проведены на множестве 50 и 100 точек.
Наблюдение за поведением целевой функции приводит к выводу, что сильное увеличение вероятности инверсии не приводит к резкому улучшению (минимизации) значения целевой функции, но тем не менее, в большинстве случаев помогает вывести поиск из локального оптимума. Поэтому рекомендуется остановиться значении вероятности инверсии: Pinv=50%.
Не менее важным объектом экспериментального исследования является критерий остановки поиска - число поколений. В качестве критерия эффективности будем также использовать значение целевой функции. Общие параметры для эксперимента: 1. Количество особей в первом поколении: М=100; 2. Вероятность оператора кроссинговера: Pcr0ss =90%; 3. Вероятность мутации: РтШ=40%; 4. Вероятность инверсии: Pim=50%; Результаты экспериментов отражены на таблице 4.13 и на рисунке 4.17. Из результатов эксперимента видно, что целевая функция как для случая с 50 точками так и с 70 точками перестает улучшаться после 10-11 поколения. Таким образом, можно сделать вывод о том, что оптимальным критерием остановки алгоритма для 50 точек является количество поколений N=15, а для 100 точек N=30. Результаты тестирования алгоритма на бенчмарках SteinLib [131] представлены в таблице 4.14. На рисунке 4.18 представлено решение теста Alue7080. Данные для тестов предоставлялись в виде тестовых файлов с координатами вершин, ребер графа, и контактов подлежащих соединению. Тесты относятся к группе VLSI Testsets, т.е. ориентированы на трассировку заказных СБИС. В ряде примеров разработанный алгоритм PTBGA показал результаты сходные с известными оптимальными решениями. В данной главе проведены экспериментальные исследования существующих алгоритмов, а также разработанных комбинированных генетических алгоритмов построения дерева Штейнера. Целью исследования разработанных алгоритма является определение оптимальных параметров, при которых алгоритмы находят наилучшие решения за минимальное время работы по сравнению с существующими алгоритмами, а также доказательство их эффективности (оптимальности), по сравнению с другими аналогичными алгоритмами. По результатам экспериментов, даны рекомендации генетических параметров (размер популяции, вероятность кроссинговера, вероятность мутации, количество генераций (поколений)), обеспечивающих возможность получения наиболее оптимальных решений. Результаты экспериментов показали эффективность разработанных алгоритмов по сравнению с существующими. Основными критериями эффективности являются качество получаемого решения (целевая функция) и временная сложность алгоритма. Алгоритм тестировался на бенчмарках каталога SteinLib. В ряде тестов разработанный алгоритм PTBGA показал результаты сходные с известными оптимальными решениями при значительном сокращении времени работы. В результате выполненных теоретических и практических 4,- исследований по теме диссертационной работы реализованы следующие положения: 1. Проведен анализ существующих методов и алгоритмов эволюционного моделирования для решения оптимизационной задачи построения дерева Штейнера для этапа глобальной трассировки СБИС. Приведено описание методов, использующих комбинаторные эвристические алгоритмы и алгоритмы эволюционного моделирования и их сравнительная характеристика. 2. Разработаны комбинированные алгоритмы основанные на методах эволюционного моделирования с применением генетических операторов: кроссинговер, мутация, селекция. Данные алгоритмы моделируют процессы, схожие с процессами живой природы, такими !\ как процессы скрещивания, мутации, динамического изменения размера популяции, процессы естественного отбора. Это позволило применить новые механизмы оптимизации, поиска новых свойств при нахождении оптимального решения. 3. Разработана новая адаптивная архитектура генетического поиска с элементами адаптации, позволяющая оптимизировать процесс vN генетического поиска, представленная в виде общей структурной схемы, которая применима не только для поставленной задачи. Проведена разработка модифицированной схемы блока параллельного эволюционного поиска. Проведен анализ и выбор модели генетического поиска для решения задачи глобальной трассировки схем при проектировании СБИС. 4. Разработана программная среда, позволяющая исследовать влияние динамических параметров при эволюционном моделировании. При создании программы использовалась среда разработки Borland С++ Builder Enterprise Suite Version 5.0, что позволило обеспечить удобный интерфейс пользователя и визуализацию работы алгоритмов.
