Разработка и исследование комбинированных алгоритмов построения деревьев Штейнера на основе эволюционного подхода

Достижение высокого научно-технического уровня производства невозможно без широкого внедрения автоматизации проектирования при создании различных устройств. Тенденции развития ЭВМ четвертого поколения связаны с развитием многопроцессорных систем, обладающих возможностью распараллеливания процесса решения, изменения структуры устройств в ходе решения задач, высоким быстродействием, технологичностью производства, живучестью и т. п. Наиболее эффективно использование параллельных вычислительных систем для решения задач управления подвижными объектами и моделирования сложных ситуаций и больших систем. В этом случае параллельные процессоры представляют собой не универсальные ЭВМ, а специализированные микропроцессоры, ориентированные для решения заданного круга задач. Такие параллельные системы известны в литературе как цифровые вычислительные структуры (ЦВС). Эти структуры являются типичным представителем ЭВМ четвертого поколения. Они ориентированы на решение специального класса задач, сводящихся к решению дифференциальных уравнений, уравнений в частных производных и воспроизведения сложных функциональных зависимостей.

Роль ЭВМ неизмеримо возросла благодаря достижениям последних лет в области микроэлектроники, что позволило решать такие задачи разработки и производства радиоэлектронной аппаратуры, которые по техническим и экономическим соображениям были совершенно нереальны прежде. Так, применение интегральных схем позволило на один—два порядка повысить плотность компоновки в единице объема, увеличить быстродействие радиоэлектронной аппаратуры, поднять надежность ее работы и приблизительно в десять раз уменьшить стоимость радиоэлектронных устройств. Указанные характеристики значительно улучшились с появлением больших интегральных схем (БИС). С точки зрения реализации устройств на интегральных схемах оптимальным является выполнение их на одном типе ячеек с одинаковой конфигурацией соединений между ячейками, т. е. построения этих устройств в виде однородных ЦВС. ЦВС, реализованные на базе БИС, позволяют решить такие важные вопросы создания дискретных устройств, как высокая универсальность, технологичность изготовления, гибкость, надежность, эффективность функционирования.

Природа поражает своей сложностью и богатством всех своих проявлений. Среди примеров можно назвать сложные социальные системы, иммунные и нейронные системы, сложные взаимосвязи между видами. Онивсего лишь некоторые из чудес, которые стали более очевидны, когда мы стали глубже исследовать себя самих и мир вокруг нас. Наука — это одна из сменяющих друг друга систем веры, которыми мы пытается объяснять то, что наблюдаем, этим самым изменяя себя, чтобы приспособиться к новой информации, получаемой из внешнего мира. Многое из того, что мы видим и наблюдаем, можно объяснить единой теорией: теорией эволюции через наследственность, изменчивость и отбор.

Теория эволюции повлияла на изменение мировоззрения людей с самого своего появления. Теория, которую Чарльз Дарвин представил в работе, известной как «Происхождение Видов», в 1859 году, стала началом этого изменения. Многие области научного знания в настоящее время наслаждаются свободой мысли в атмосфере, которая многим обязана революции, вызванной теорией эволюции и развития. Но Дарвин, подобно многим своим современникам, кто предполагал, что в основе развития лежит естественный отбор, не мог не ошибаться. Например, он не смог показать механизм наследования, при котором поддерживается изменчивость. Его гипотеза о пангенезисе оказалась неправильной. Это было на пятьдесят лет до того, как теория наследственности начала распространяться по миру, и за тридцать лет до того, как «эволюционный синтез» укрепил связь между теорией эволюции и относительно молодой наукой генетикой. Однако.

Дарвин выявил главный механизм развития: отбор в сочетании с изменчивостью или, как он его называл, «спуск с модификацией». Во многих случаях, специфические особенности развития через изменчивость и отбор все еще не бесспорны, однако, основные механизмы объясняют невероятно широкий спектр явлений, наблюдаемых в природе.

Поэтому неудивительно, что ученые, занимающиеся компьютерными исследованиями, обратились к теории эволюции в поисках вдохновения. Возможность того, что вычислительная система, наделенная простыми механизмами изменчивости и отбора, могла бы функционировать по аналогии с законами эволюции в природных системах, была очень привлекательна. Эта надежда стала причиной появления ряда вычислительных систем, построенных на принципах естественного отбора.

История эволюционных вычислений началась с разработки ряда различных независимых моделей. Основными из них были генетические алгоритмы и классификационные системы Голланда (Holland), опубликованные в начале 60-х годов и получившие всеобщее признание после выхода в свет книги, ставшей классикой в этой области, — «Адаптация в естественных и искусственных системах» («Adaptation in Natural and Artifical Systems», 1975). В 70-х годах в рамках теории случайного поиска Растригиным JI.A. был предложен ряд алгоритмов, использующих идей бионического поведения особей. Развитие этих идей нашло отражение в цикле работ Букатовой И. Л. по эволюционному моделированию. Развивая идеи Цетлина M.JI. о целесообразном и оптимальном поведении стохастических автоматов, НеймаркЮ.И. предложил осуществлять поиск глобального экстремума на основе коллектива независимых автоматов, моделирующих процессы развития и элиминации особей. Большой вклад в развитие эволюционного программирования внесли Фогел (Fogel) и Уолш (Walsh). Несмотря на разницу в подходах, каждая из этих «школ» взяла за основу ряд принципов, существующих в природе, и упростила их до такой степени, чтобы их можно было реализовать на компьютере.

Главная трудность с возможностью построения вычислительных систем, основанных на принципах естественного отбора и применением этих систем в прикладных задачах, состоит в том, что природные системы достаточно хаотичны, а все наши действия, фактически, носят четкую направленность. Мы используем компьютер как инструмент для решения определенных задач, которые мы сами и формулируем, и мы акцентируем внимание на максимально быстром выполнении при минимальных затратах. Природные системы не имеют никаких таких целей или ограничений, во всяком случае нам они не очевидны. Выживание в природе не направлено к некоторой фиксированной цели, вместо этого эволюция совершает шаг вперед в любом доступномее направлении.

Генетические алгоритмы в разных формах применяются к решению многих научных и технических проблем. Генетические алгоритмы используются при создании других вычислительных структур, например, автоматов или сетей сортировки. В машинном обучении они используются при проектировании нейронных сетей или управлении роботами. Они также применяются при моделировании развития в разных предметных областях, включая биологические (экология, иммунология и популярная генетика) и социальные (такие как экономика и политические системы) системы.

Тем не менее, возможно популярное применение генетических алгоритмов — оптимизация многопараметрических функций. Большинство реальных задач могут быть сформулированы как поиск оптимального значения, где значение — сложная функция, зависящая от определенных входных параметров. В некоторых случаях, нужно найти те значения параметров, при которых достигается точное значение функции. В других случаях, точный оптимум не нужен — решением может считаться любое значение, лучшее за определенную заданную величину. В этом случае, генетические алгоритмы — приемлемый метод для поиска «приемлемых» значений. Сила генетического алгоритма состоит в его способности манипулировать одновременно многими параметрами, которая используется в сотнях прикладных программ, включая проектирование самолетов, настраивании параметров алгоритмов и поиске стойких состояний систем нелинейных дифференциальных уравнений.

Генетические алгоритмы являются эффективной процедурой поиска, которая конкурирует с другими процедурами. Эффективность генетических алгоритмов сильно зависит от таких деталей, как метод кодирования решений, операторов, настраивания параметров, отдельных критериев успеха.

Таким образом, проектирование и изготовление ЦВС на БИС невозможно без использования ЭВМ, являющихся незаменимым инструментом для расчета, изготовления, испытания, внедрения БИС и устройств, созданных на их основе. Однако использование ЭВМ для этих целей малоэффективно без наличия мощного специального математического обеспечения, под которым понимается создание автоматизированных систем проектирования (АСП). АСП, в общем случае, должны решать три категории задач: функциональное, техническое и технологическое проектирование.

Проблема автоматизированного проектирования эскиза топологии БИС— техническое проектирование — охватывает широкий спектр вопросов, включающих представление исходной электрической схемы в виде математических или матричных моделей, размещение типовых фрагментов топологии на рабочем поле кристалла, проектирование коммутационных связей между отдельными элементами, распределение фрагментов трасс в проводящих слоях кристалла, контроль топологии, компоновку узлов ЦВС и т. д. Очевидно, что решение этих задач традиционными «ручными» методами связано с большими затратами трудовых и временных ресурсов. Кроме того, значительно увеличивается вероятность внесения ошибок. Преодоление указанных трудностей возможно лишь с использованием ЭВМ, функции которой обусловлены режимом диалога с разработчиком в процессе вычислений.

Значительный интерес, проявляемый к проблеме машинного проектирования эскиза топологии соединений, во многом объясняется большой трудоемкостью этого этапа и невозможностью создания универсальных алгоритмов трассировки, одинаково эффективных для различных конструкций БИС. Известно большое число алгоритмов трассировки, основанных на различных методах построения, как отдельных трасс, так и цепей в целом. Важным вопросом при трассировке является построение кратчайших связывающих деревьев (КСД) цепей электрических схем.

Различают два принципа построения минимальных покрывающих деревьев. Первый состоит в том, что не допускается вводить дополнительные вершины. Такая задача называется построением минимального покрывающего дерева (МПД). Существуют эффективные алгоритмы Крускала, Прима и другие, предназначенные для построения МПД. Второй случай состоит в том, что разрешается вводить произвольное количество дополнительных вершин и соединяющих их ребер. Такая задача называется задачей Штейнера. Ее решение приводит к построению дерева Штейнера (ДШ), а дополнительные вершины называются точками Штейнера (ТШ).

В этой связи, тема работы, связанная с разработкой нового алгоритма трассировки схем, при проектировании СБИС, использующего методы генетического поиска в комбинации с другими итерационными методами, позволяющего сократить время поиска решений в задачах большой размерности, и в то же время повысить качество получаемых решений за счёт адаптивной архитектуры, является АКТУАЛЬНОЙ.

ЦЕЛЬЮ диссертационной работы является разработка методов глобальной трассировки цепей схем при проектировании СБИС на основе модифицированных структур генетического поиска, с элементами адаптации, по критерию суммарной длины связей, позволяющего получить решение с наименее возможной длиной цепей и повысить качество решений для задач большой размерности.

Для достижения поставленной цели были поставлены и решены следующие задачи:

1. Провёден комплексный анализ известных методов оптимизации, существующих алгоритмов трассировки схем, а также анализ и обоснование выбора математической модели схем для разрабатываемого алгоритма трассировки схем при проектировании СБИС.

2. Разработка и анализ методов решения задачи Штейнера для этапа глобальной трассировки.

3. Создание модифицированных генетических операторов и процедур (кроссинговер, мутация, селекция).

4. Построение алгоритма формирования начальной популяции.

5. Создание структуры и принципов кодирования и декодирования хромосомы.

6. Разработка процедуры оценки и качества (целевой функции).

Для решения поставленных задач использовались следующие ——.

МЕТОДЫ ИССЛЕДОВАНИИ: элементы теории множеств, элементы теории графов и гиперграфов, элементы теории алгоритмов, элементы теории генетического поиска.

НАУЧНАЯ НОВИЗНА диссертационной работы заключается в:

1. Разработке комбинированных генетических алгоритмов, построения дерева Штейнера, позволяющих повысить эффективность алгоритма и сократить время поиска решений.

2. Разработке модифицированных процедур для генетических операторов (кроссинговера, мутации), позволяющих повысить качество получаемых решений, а также устойчивость генетического поиска.

3. Разработке новой адаптивной архитектуры генетического поиска с элементами адаптации, позволяющей оптимизировать процесс генетического поиска, представленной в виде общей структурной схемы, которая применима не только для поставленной задачи.

ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют:

1. Структура и принцип представления информации для генетических алгоритмов построения дерева Штейнера для задачи глобальной трассировки СБИС.

2. Алгоритмы и программное обеспечение для решения задачи построения дерева Штейнера для этапа глобальной трассировки СБИС, которые позволяют уменьшить длину соединительных проводников при проектировании СБИС.

3. Разработка новой адаптивной архитектуры генетического поиска с элементами адаптации, позволяющей оптимизировать процесс генетического поиска, представленной в виде общей структурной схемы, которая применима не только для поставленной задачи.

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ.

Основные теоретические и практические результаты диссертационной работы использованы в госбюджетной работе № 12 353 «Разработка теории и принципов построения интеллектуальных систем автоматизированного проектирования на основе эволюционной адаптации, нейросетевых моделей и методов принятия решений».

Материалы диссертации были использованы в учебном процессе на кафедре САПР ТРТУ при чтении лекций по курсам «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования».

Научные результаты, полученные в диссертационной работе Калашникова P.C., использовались в х/д НИР 12 305 по теме «Исследование алгоритмов решения Евклидовой задачи Штейнера для трассировки электрических соединений».

АПРОБАЦИЯ основных теоретических и практических результатов работы проходила на Международной научно-технической конференции «Интеллектуальные САПР (САО-2002)» (г. Геленджик, 2002 г.), на Международной научно-технической конференции «Интеллектуальные CAQP (CAD-2004)» (г. Геленджик, 2004 г.).

ПУБЛИКАЦИИ. По теме диссертации опубликовано 8 печатных работ.

СТРУКТУРА И ОБЪЁМ ДИССЕРТАЦИОННОЙ РАБОТЫ.

Диссертационная работа состоит из введения, четырёх глав,.

Выводы.

В данной главе проведены экспериментальные исследования существующих алгоритмов, а также разработанных комбинированных генетических алгоритмов построения дерева Штейнера. Целью исследования разработанных алгоритма является определение оптимальных параметров, при которых алгоритмы находят наилучшие решения за минимальное время работы по сравнению с существующими алгоритмами, а также доказательство их эффективности (оптимальности), по сравнению с другими аналогичными алгоритмами. По результатам экспериментов, даны рекомендации генетических параметров (размер популяции, вероятность кроссинговера, вероятность мутации, количество генераций (поколений)), обеспечивающих возможность получения наиболее оптимальных решений.

Результаты экспериментов показали эффективность разработанных алгоритмов по сравнению с существующими. Основными критериями эффективности являются качество получаемого решения (целевая функция) и временная сложность алгоритма.

Алгоритм тестировался на бенчмарках каталога 81ет1лЬ. В ряде тестов разработанный алгоритм РТВвА показал результаты сходные с известными оптимальными решениями при значительном сокращении времени работы.

Заключение

.

В результате выполненных теоретических и практических.

4, — исследований по теме диссертационной работы реализованы следующие положения:

1. Проведен анализ существующих методов и алгоритмов эволюционного моделирования для решения оптимизационной задачи построения дерева Штейнера для этапа глобальной трассировки СБИС. Приведено описание методов, использующих комбинаторные эвристические алгоритмы и алгоритмы эволюционного моделирования и их сравнительная характеристика.

2. Разработаны комбинированные алгоритмы основанные на методах эволюционного моделирования с применением генетических операторов: кроссинговер, мутация, селекция. Данные алгоритмы моделируют процессы, схожие с процессами живой природы, такими д как процессы скрещивания, мутации, динамического изменения п' размера популяции, процессы естественного отбора. Это позволило применить новые механизмы оптимизации, поиска новых свойств при нахождении оптимального решения.

3. Разработана новая адаптивная архитектура генетического поиска с элементами адаптации, позволяющая оптимизировать процесс ф генетического поиска, представленная в виде общей структурной схемы, которая применима не только для поставленной задачи. Проведена разработка модифицированной схемы блока параллельного эволюционного поиска. Проведен анализ и выбор модели генетического поиска для решения задачи глобальной трассировки схем при проектировании СБИС.

4. Разработана программная среда, позволяющая исследовать влияние динамических параметров при эволюционном моделировании. При создании программы использовалась среда разработки Borland С++ Builder™ Enterprise Suite Version 5.0, что позволило обеспечить удобный интерфейс пользователя и визуализацию работы алгоритмов.