Содержание к диссертации
Введение
1. Анализ алгоритмов и методов решения задачи разбиения схем при проектировании СБИС 13
1.1. Анализ и выбор математической модели 13
1.2. Постановка задачи разбиения схем при проектировании СБИС 22
1.3. Учёт тепловых характеристик 36
1.4. Классификация методов и алгоритмов решения поставленной задачи 37
1.5. Выводы.. 44
2. Применение методов генетического поиска для решения задачи разбиения схем при проектировании СБИС 45
2.1. Отличия методов генетического поиска от других оптимизационных методов 45
2.2. Элементы генетических алгоритмов 48
2.3. Структура генетического алгоритма 51
2.4. Выбор методики кодирования информации 54
2.5. Селекция 64
2.6. Основные генетические операторы 68
2.6.1. Оператор кроссинговера 68
2.6.2. Оператор мутации 74
2.6.3. Оператор инверсии 78
2.7. Выводы 81
3. Разработка генетического алгоритма разбиения с элементами адаптации (ГАСЭА) 82
3.1. Структурная схема ГАСЭА для разбиения схем при проектировании СБИС 82
3.2. Элементы адаптации в ГАСЭА 89
3.3. Генератор хромосом содержащих группы вершин (ГХСЯ) 91
3.4. Модифицированные процедуры, применяемые для ГО 100
3.5. Блок локального улучшения решений 103
3.6. Блок анализа преждевременной сходимости и критерия остановки алгоритма 106
3.7. Блок адаптации алгоритма 109
3.8. Теоретические оценки алгоритма 112
3.9. Выводы 114
4. Разработка программной реализации и экспериментальное исследование алгоритма разбиты и схем при проектировании СБИС 1 16
4.1. Разработка основных пунктов меню программного обеспечения 116
4.2. Формат входного файла гиперграфа 118
4.3. Формат выходного файла (решения) 119
4.4. Цель экспериментального исследования 121
4.5. Этапы экспериментальных исследований 122
4.6. Результаты экспериментальных исследований 123
4.6.1. Результаты исследований для блока модифицированных генетических операторов 124
4.6.2. Результаты исследований для проблемно-ориентированного генератора стартовой популяции (ГХСЯ) 131
4.6.3. Результаты исследований для разработанного алгоритма (ГАСЭА) 134
4.7. Сравнение полученных экспериментальных данных ГАСЭА с результатами аналогов 137
4.8. Выводы... 140
Заключение 141
Литература 143
- Классификация методов и алгоритмов решения поставленной задачи
- Отличия методов генетического поиска от других оптимизационных методов
- Блок анализа преждевременной сходимости и критерия остановки алгоритма
- Результаты исследований для блока модифицированных генетических операторов
Введение к работе
Современный этап развития человеческой цивилизации,
характеризующийся высокими темпами роста развития науки и техники, нелегко представить без использования изделий микроэлектронной промышленности в повседневной жизни. Использование различных достижений микроэлектроники при производстве интегральных схем (ИС), больших ИС (БИС), сверхбольших ИС (СБИС), суперкристаллов, обуславливает повышение основных характеристик электронных вычислительных средств (ЭВС) проектируемых на их основе, например, снижаются массогабаритные показатели, уменьшаются потребляемая и
. рассеиваемая мощности, повышаются быстродействие и надёжность [1-3]. Современные ЭВС, такие как, персональные компьютеры, оборудование
* вычислительных и специальных пользовательских сетей, контроллеры и другие управляющие устройства и системы содержат в своём составе десятки, а иногда и сотни СБИС [3]. Однако к характеристикам ЭВС предъявляются неоднозначные требования в зависимости от класса и назначения аппаратуры, использующей СБИС и суперкристаллы. Какая-то из характеристик или их совокупность могут быть определяющими, тогда как требования к остальным снижаются. К примеру, в аппаратуре с автономным питанием потребляемая мощность микросхем должна быть как можно меньшей по сравнению с мощностью аналогичных изделий, используемых в стационарных радиоэлектронных средствах (РЭС). В бытовой же аппаратуре компоненты со сверхвысоким быстродействием (электронные цифровые часы, калькуляторы, игрушки) использовать ни к чему.
Развитие микроэлектроники происходило поэтапно: малые схемы, средние, большие, сверхбольшие. Первые ИС представляли собой объединение транзистора с набором сопротивлений и выполняли какую-либо логическую функцию. Степень интеграции постоянно возрастает с момента изобретения ИС. В 1965 году сопрезидент фирмы Intel Гордон Мур, предсказал, что число элементов на кристалле ИС должно удваиваться каждый год на протяжении последующих 10 лет. Это предсказание впоследствии было названо законом
Мура [76]. Последующие 25 лет позволили уточнить закон Мура: число элементов на кристалле удваивается в среднем каждые 1,5 года. Применение на этапе проектирования САПР разного уровня способствует повышению степени интеграции СБИС на уровне узлов, блоков и всей системы в целом [4- 10J. Сегодня СБИС способны выполнять сложнейшие наборы функции, а геометрические размеры транзисторов сократились до 0.18 микрона! В настоящее время промышленностью выпускается широкая номенклатура СБИС, суперкристаллов, содержащих миллионы элементов на кристалле 25x25мм. Неуклонное повышение степени интеграции СБИС привело к тому, что в них более 60% общей временной задержки сигнала приходится на задержки в межсоединениях. Рост размера области, отводимой для межсоединений, опережает рост размера области, предназначенной для активных элементов. В чипе, содержащем 10 миллионов транзисторов и использующем 4 слоя металлизации, около 40% площади отводится под межсоединения. Кроме того, рост числа транзисторов на кристалле, увеличивает также и средние размеры кристаллов. Посчитано, что площади кристаллов самых больших ИС возрастают примерно на 13% в год и эта тенденция, согласно прогнозу, сохранится, по крайней мере, на ближайших полтора - два десятилетия.
Быстрая эволюция в производстве ИС стала бы невозможной без использования автоматизации выполнения различных этапов проектирования [7-9]. Сейчас, на всех стадиях проектирования топологии СБИС интенсивно используют средства' автоматизации проектирования (САПР) и многие фазы могут быть полностью или частично автоматизированы. Важнейшим этапом в цикле проектирования СБИС, является этап конструкторского проектирования, на котором решаются задачи разбиения (компоновки), планирования, размещения, трассировки, упаковки, верификации [7].
Поскольку СБИС может содержать несколько миллионов транзисторов, то невозможно спроектировать топологию всей схемы целиком в связи с ограниченными возможностями вычислительных средств, поэтому схема разбивается группированием компонентов в блоки. В результате разбиения
формируется множество блоков и множество соединений между блоками [4, И, 12]. В очень больших схемах используется иерархическая структура разбиения.
Задача планирования заключается в определении взаимного расположения блоков относительно друг друга.
Задачей размещения является определение конкретного места для каждого блока на кристалле.
Трассировка заключается в конструктивной реализации связей между элементами.
Задачей компакции является простое сжатие топологии во всех направлениях для уменьшения общей площади кристалла. Компакция позволяет уменьшить длину связей и временные задержки между компонентами кристалла. Уменьшение площади одного кристалла с помощью компакции позволяет размещать большее число кристаллов на площади одной подложки.
На последнем этапе делается верификация топологии спроектированного кристалла либо схемы. Она заключается в проверке геометрических размеров, ограничений, временных задержек и других параметров, влияющих на работоспособность всей схемы.
Большой ,вклад в развитие моделей, методов, стратегий, алгоритмов автоматизированного проектирования СБИС внесли такие учёные, как: Бершадский A.M., Деньдобренко Б.П., Казеннов Г.Г., Курейчик В.М., Морозов К.К., Норенков И.П., Селютин В.А., Шервани Н. и др. В многочисленной своей массе разработанные алгоритмы, программы и пакеты в САПР предназначены для оптимальной компоновки, размещении разногабаритных объектов (формирования базового плана кристалла) и межблочной трассировки межсоединений по критерию минимизации занимаемой площади и длины связей [13 - 16]. В связи с большой сложностью и размерностью задач конструкторского проектирования, а также с возникновением новых тенденций в технологии изготовления СБИС, появляется . необходимость в разработке новых направлений, методик,
алгоритмов для решения данного класса задач. Поскольку даже в условиях современного развития информационных технологий, многие алгоритмы не справляются с решением или требуют много процессорного времени для поиска решений. С точки зрения повышения эффективности САПР, представляет интерес разработка новых алгоритмов и методов проектирования, для так называемых NP-полных задач, в которых нахождение оптимального решения возможно только полным перебором и которые являлись бы достаточно эффективными как с точки зрения точности и оптимальности получаемых решений, так и с позиции времени работы. К таким можно отнести методы эволюционного моделирования, которые были разработаны, как новое направление, в начале 1970 гг., но только сейчас приобрели приоритет в отношении других методов. Сравнительно недавно, их начали широко применять для решения задач в самых различных областях [17-23], в том числе для решения задач проектирования СБИС, поскольку эти методы способны обрабатывать множество решений при учёте множества критериев [24-36]. Данными свойствами обладают генетические алгоритмы (ГА) -поисковые алгоритмы, основанные на механизмах натуральной селекции и генетики, работающие с популяциями решений методом эволюционного поиска.
Значительный вклад в развитие стратегий эволюционного поиска внесли такие учёные, как: Батищев Д.И., Букатова И.Л, Гольдберг Д.Е., Курейчик В.М., Норенков И.П., Растригин Л.А., Холланд Д.Х. и др. Основная цель ГА -абстрактно и формально объяснить адаптацию процессов в естественных системах и спроектировать искусственные программные системы, которые содержат основные механизмы естественных систем. Основная тема поиска ГА - поиск баланса между эффективностью и качеством для "выживания" в различных условиях. Главные отличия ГА от других оптимизационных и поисковых процедур следующие: осуществляют поиск из множества точек, а не из единственной точки; используют целевую функцию, а не её различные приращения; для оценки получаемой информации используют не детерминированные, а вероятностные правила; дают не одно решение, а целый
спектр решений, из которых возможно выбрать наилучшее, с точки зрения поставленной задачи. Пожалуй, одним из главных свойств ГА является, то что, они достаточно легко преодолевают локальные оптимумы в силу своей
"природы". Гибкость структуры ГА, возможность её настройки и
перенастройки дают возможность создания структур, обеспечивающих
. получение наилучшего результата за приемлемое время. Это, в свою очередь, предоставляет исследователям широчайшие возможности, для поиска альтернативных решений в этом направлении.
В этой связи, тема работы, связанная с разработкой нового алгоритма разбиения схем, при проектировании СБИС, использующего методы генетического поиска в комбинации с другими итерационными методами, позволяющего сократить время поиска решений в задачах большой размерности, и в то же время повысить качество получаемых решений за счёт адаптивной архитектуры, является АКТУАЛЬНОЙ.
ЦЕЛЬЮ диссертационной работы является исследование и разработка методов разбиения схем при проектировании СБИС на основе модифицированных структур генетического поиска, с элементами адаптации, по критерию суммарного числа внутренних (внешних) связей, а также тепловой совместимости элементов, позволяющих повысить качество решений для задач большой размерности.
Для достижения поставленной цели были выполнены следующие этапы:
1. Проведен комплексный анализ известных методов оптимизации,
. существующих алгоритмов разбиения схем (последовательных, параллельных,
последовательно-параллельных, смешанных), а также анализ и обоснование
* выбора математической модели схем для разрабатываемого алгоритма
разбиения схем при проектировании СБИС.
2. Разработан новый проблемно-ориентированный генератор стартовой
популяции (ГХСЯ), использующий знания о решаемой задаче и позволяющий
генерировать хромосомы, содержащие группы генов (опорное подмножество
или ядро), что позволило повысить качество получаемых решений и сократить
время работы алгоритма.
Выполнен анализ основных генетических операторов с точки зрения их пригодности и эффективности для решения поставленной задачи.
Разработаны модифицированные процедуры для генетических операторов (кроссинговера, мутации, инверсии), зависящие от динамических параметров и позволяющие получать "хороших" потомков.
Разработан блок оценки предварительной сходимости алгоритма и блок адаптации по управлению динамически изменяемыми параметрами в ходе работы алгоритма.
Разработана структурная схема генетического алгоритма разбиения гиперграфов на подгиперграфы с элементами адаптации (ГАСЭА) для задачи разбиения схем при проектировании СБИС.
Выполнены экспериментальные исследования разработанного проблемно-ориентированного генератора стартовой популяции решений (ГХСЯ), блока модифицированных процедур генетических операторов, разработанного алгоритма (ГАСЭА), а также сравнение его с известными алгоритмами разбиения.
Для решения поставленных задач использовались следующие МЕТОДЫ * ИССЛЕДОВАНИИ: элементы теории множеств, элементы теории графов и
гиперграфов, элементы теории алгоритмов, элементы теории генетического
поиска.
НАУЧНАЯ НОВИЗНА диссертационной работы заключается в:
1. Разработке методики формирования стартовой популяции хромосом,
содержащих группы генов (опорное подмножество или ядро хромосомы),
позволяющей повысить сходимость алгоритма и сократить время поиска
решений. -
.2. Разработке модифицированных процедур для генетических операторов
*
(кроссинговера, мутации, инверсии), зависящих от динамических параметров, . позволяющих повысить качество получаемых решений, а также устойчивость генетического поиска.
3. Разработке новой адаптивной архитектуры генетического поиска с элементами адаптации, позволяющей оптимизировать процесс генетического
поиска, представленной в виде общей структурной схемы, которая применима
- не только для поставленной задачи.
ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют:
1. Методика поиска решений, использующая знания о решаемой задаче и позволяющая учитывать как математическую, так и статистическую закономерность при распределении элементов, что позволяет улучшить практические результаты по сходимости алгоритма.
2; Новая адаптивная архитектура генетического поиска с динамическими параметрами, оптимизирующая процесс генетического поиска, представленная в виде общей структурной схемы.
3. Генетический алгоритм с элементами адаптации и программа для
разбиения схем при проектировании СБИС, разработанная под наиболее
популярное семейство 32-разрядных операционных систем
Windows 9х/МЕ/2000/ХР фирмы Microsoft Corporation, созданная в среде объектно-ориентированного программирования Borland C++ Builder'" 5.0.
РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетной работе « Разработка интеллектуальных систем проектирования на основе эволюционной адаптации » (№ ГР 1.8.96), г/б « Разработка теории и принципов построения интеллектуальных систем автоматизированного
+
- проектирования на основе эволюционной адаптации, нейросетевых моделей и
методов принятия решений» (№ ГР 1.04.01), х/д между ТРТУ и Российским
научно-исследовательским институтом информационных технологий и систем
автоматизированного проектирования (Рос НИИ ИТ и АП) «Разработка
эволюционных алгоритмов на графах с динамическими параметрами»
"(№ 12301).
Результаты работы используются в НИИ ТКБ ТРТУ по договору
№71-0/98-16002-7 «Участие в разработке технических предложений по
созданию РИС и алгоритмов её функционирования». Кроме того, материалы .
. диссертации использованы в учебном процессе на кафедре САПР ТРТУ при
чтении лекций по курсу "Методы оптимизации", "Методы генетического
поиска", а также в - цикле лабораторных работ по курсу "Автоматизация конструкторского проектирования СБИС".
АПРОБАЦИЯ основных теоретических и практических результатов . работы проводилась на научных семинарах (с 2000 по 2003 гг., ТРТУ), V, VI Всероссийских научно-технических конференциях студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления" (г. Таганрог, 2000 г., 2002 г.), XVII Международной научно-технической конференции "Интеллектуальные САПР" (г. Геленджик, 2002 г.), Пятой Всероссийской научной конференции молодых учёных и аспирантов «Новые информационные технологии. Разработка и аспекты применения» (г. Таганрог, 2002 г.)."
ПУБЛИКАЦИИ. По теме диссертации опубликовано 8 печатных работ.
СТРУКТУРА И ОБЪЁМ ДИССЕРТАЦИОННОЙ РАБОТЫ.
*. Диссертационная работа состоит из введения, четырёх глав, заключения, и
списка использованных источников. Работа содержит 173 стр., включая 69 рис.,
18 табл., список использованных источников из 107 наименований, 23 стр.
приложений и актов об использовании.
СОДЕРЖАНИЕ РАБОТЫ.
ВО ВВЕДЕНИИ обоснована актуальность темы диссертационной работы, сформулированы цели, дано общее описание выполненной работы.
.В ПЕРВОЙ ГЛАВЕ приведена постановка задачи разбиения схем при проектировании СБИС на основе гиперграфовой математической модели, по критерию максимизации (минимизации) суммарного количества гиперрёбер в " каждом подгиперграфе (между подгиперграфами), с учётом тепловой совместимости элементов. Рассмотрены существующие алгоритмы и методы решения задачи разбиения схем при проектировании СБИС, выявлены их достоинства и недостатки.
ВО ВТОРОЙ ГЛАВЕ рассмотрены методы генетического поиска, применяемые для решения поставленной задачи. Показаны преимущества методов генетического поиска при решении задач разбиения схем при проектировании СБИС относительно других оптимизационных методов.
Выбрана универсальная по постановке задачи методика кодирования информации. Рассмотрены и выбраны основные генетические операторы, используемые для решения поставленной задачи.
В ТРЕТЬЕЙ ГЛАВЕ описано решение задачи разбиения схем при
проектировании СБИС при помощи генетического алгоритма с элементами
адаптации (ГАСЭА). Приведена структурная схема ГАСЭА. Разработаны
проблемно-ориентированный генератор хромосом стартовой популяции,
модифицированные процедуры для генетических операторов, а также
дополнительные блоки, используемые в ГАСЭА: локального улучшения
решений; адаптации по архитектуре поиска; анализа преждевременной
сходимости и остановки алгоритма. Определены теоретические оценки
временной и пространственной сложности разработанного алгоритма.
В ЧЕТВЕРТОЙ ГЛАВЕ приведено описание экспериментальных исследований ГАСЭА. Выполнена статистическая обработка полученных экспериментальных данных. Проделанные расчёты позволили подтвердить полученные ранее теоретические оценки временной и пространственной - сложности разработанного алгоритма. Определены диапазоны оптимальных значений параметров генетического поиска. Оценена эффективность применения разработанного проблемно-ориентированного генератора стартовой популяции решений. Выполнено сравнение результатов работы разработанного ГАСЭА с известными аналогами. Представлено описание программного обеспечения для генерации, решения и исследования, различных гиперграфовых моделей схем для задачи разбиения схем при проектировании СБИС.
В ЗАКЛЮЧЕНИИ изложены основные выводы и результаты
диссертационной работы.
В приложениях приведены копии актов об использовании, графический интерфейс программного обеспечения, примеры решения задачи разбиения схем для стандартных тестовых схем.
Классификация методов и алгоритмов решения поставленной задачи
В задачах разбиения при проектировании СБИС можно выделить два основных класса: задачи, в которых осуществляется разбиение схемы на блоки - с учётом конструктивных факторов (мощность блоков, число блоков и межсоединений между ними) и задачи, в которых помимо конструктивных факторов существенны и функциональные характеристики блоков [4, 6, 7]. Рассмотрим первый класс задач разбиения схем (с учётом конструктивных факторов), поскольку второй класс задач выходит за рамки диссертационной работы. Задачи первого класса состоят в отыскании такого разбиения к из множества возможных разбиений К некоторого гиперграфа Н (либо графа G), при котором минимизируется (либо максимизируется) некоторая величина F, являющаяся весовой функцией разбиения, и учитываются все поставленные в задаче ограничения [3, 4, 9]. Задача разбиения относится к задачам дискретной условной оптимизации из-за прерывности её целевой функции и наличия множества ограничений на переменные. Количество методов решения задач условной оптимизации достаточно велико, хотя эффективные алгоритмы известны лишь для специальных классов задач, таких, как задачи линейного, квадратичного или выпуклого программирования. Широко распространен симплекс метод и метод нелинейного программирования (метод штрафных и барьерных функций). Однако, применительно к задаче разбиения большинство из вышеприведенных методов не может быть использовано в связи с её дискретностью, которая приводит к существенному росту трудностей при поиске оптимума. Поэтому, данные задачи выделяют в особый класс комбинаторных задач [105]. В задачах такого класса, таких, как разбиение и размещение элементов, общее число вариантов решения равно числу перестановок из п "элементов, т.е. . формирование подмножеств (кусков графа в задаче разбиения) — числу сочетаний из п элементов по т, т. е. - где п — множество элементов, am- число кусков. По формуле (1.4.) видно, что решение задачи разбиения полным перебором даже с учётом ограничений недопустимо, из-за слишком большого объёма вычислительной работы. Это привело к появлению множества алгоритмов решения данных задач, основанных на различных методах [12 16]. К таким относится метод парных перестановок, методы последовательного приближения и направленного перебора, а в последнее время появились и методы генетического поиска. Все они в каком-то смысле основаны на переборе вариантов решения, однако различаются по принципам исполнения и вычислительной процедуре (последовательные, параллельно последовательные, итерационные) [21, 40, 41]. Методы динамического программирования и дискретной оптимизации [42] при поиске новых решений используют информацию, полученную на предыдущих шагах (итерациях) алгоритма. Знание о получаемых решениях способствует формированию определенного поискового пространства, в котором будет происходить поиск новых решений. Естественно, данные методы требуют больших ресурсов памяти для хранения промежуточных . результатов и мощный процессор для обработки массивов данных. ВСА данных методов составляют в среднем О(осп2). Комбинаторные методы [7, 10] предназначены для поиска оптимального решения в некотором конечном множестве. В большинстве случаев они используют различные варианты сокращённого перебора, поскольку полный перебор в реальных задачах неосуществим из-за слишком большой их размерности. Наиболее распространенный из этих методов — метод ветвей и границ (МВГ) [4, 10, 42]. Алгоритмы разбиения с применением МВГ основаны на идее последовательного разбиения множества на заданное число подмножеств и формировании оценок, позволяющих рассматривать только те подмножества, которые могут содержать решение задачи (т. е. отбрасываются заведомо не перспективные варианты). Основной недостаток этих методов заключается в необходимости корректного выбора оценок, в противном случае (при неверном выборе) данный метод будет осуществлять полный перебор. Вычислительная сложность алгоритмов данного типа лежит в . пределах от О (an2) до 0(j3n4). Эвристические методы [7, 42]. Для данного класса методов нет чёткого . математического обоснования, отсутствуют оценки точности решений и условия, гарантирующие получение корректных результатов. В их основе лежат логические соображения. Данные методы не гарантируют нахождение оптимального решения и сильно зависят от класса и описания решаемой задачи. Эвристические методы на практике позволяют получать неплохие результаты, однако предсказать их поведение невозможно. Эвристические методы могут использоваться как самостоятельно, так и в соединении с другими методами, используя найденное с помощью эвристики решение в качестве исходного и дальнейшего улучшения его каким-либо другим, например, комбинаторным методом. Это позволяет значительно сократить время решения задачи. Сложность эвристических алгоритмов может быть любой, но большинство известных алгоритмов имеют ВСА от O(an) до 0((3п3). Методы генетического поиска (МГП) [17, 18, 21, 41, 90]. Данные методы реализуют механизмы натуральной селекции и генетики, объединяя процедуру "выживания сильнейших", формируя и изменяя поисковый алгоритм на основе эволюционного поиска [43]. Основная тема поиска — нахождение баланса между эффективностью и качеством для выживания в различных условиях (т. е. поиск "компромиссного" по критериям, ограничениям и условиям решения). Генетические алгоритмы, как один из МГП, используют в процессе нахождения решения знания о решаемой задаче, включая информацию о множестве решений полученных на предыдущих шагах. Сложность ВСА алгоритмов, построенных на МГП, в большинстве случаев составляет О(шГ) либо 0(ап ), но в зависимости от применяемой эвристики может достигать 0(ст4) (в мощных ГА, Greedy-алгоритмах и т. п.). . Известно множество алгоритмов, построенных на рассмотренных выше методах решения [8, 12-16]. Сущность большинства из них заключается в выборе некоторого начального разбиения исходного графа и последующего его улучшения с помощью итерационного, парного или группового обмена вершин из различных кусков (блоков). При этом для каждой итерации осуществляется перестановка таких вершин, которая обеспечивает максимальное уменьшение числа связей между кусками графа (основной критерий задачи разбиения) или минимальное приращение числа внешних соединений. Среди наиболее популярных алгоритмов разбиения графа на куски известны следующие: . а) алгоритм Kernighan - Lin и его улучшенные эвристики [13], [44]; " б) алгоритм Simulated Annealing (моделирование отжига) [13]; в) алгоритм Fiduccia - Mattheyses и его модификации [45], [14], [15]; г) Stable - algorithm и многие другие [14]. д) генетические алгоритмы, в том числе использующие эвристическую базу алгоритмов а) - г) [46, 40, 79]. Сравнительная оценка нескольких из вышеприведенных алгоритмов показывает, что алгоритмы, использующие высокоэффективную эвристику, дают приблизительно тот же результат, затрачивая при этом на каждую генерацию значительно меньше (до 10 раз!) времени [13]. Это связано с тем, что многие эвристические алгоритмы используют для решения не полный перебор, а направленный на улучшение целевой функции поиск, отбрасывая при этом множество "ненужных" решений. Таким преимуществом обладают и . генетические алгоритмы, базирующиеся на методах эволюционного " моделирования.
Отличия методов генетического поиска от других оптимизационных методов
При построении алгоритмов всегда возникает проблема выбора метода решения, связанного с поставленной целью. Как уже отмечалось в главе 1, в связи с большой размерностью задач разбиения и размещения альтернативой для их решения всё чаще являются комбинаторные методы и методы генетического поиска (МГП), .которые, благодаря своей универсальности, можно применить в большинстве задач переборного типа [80-84]. Применение МГП для решения поставленной задачи позволяет избежать трудностей, связанных с дискретностью ЦФ, размерностью задачи, возникающих обычно при использовании других методов. Так в чём же заключается необычайная "сила" и всё возрастающая в последнее время популярность использования МГП в NP-полных задачах Ответ на этот вопрос станет очевидным, если сравнить МГП с некоторыми категориями существующих методов оптимизации.
К первой категории относятся методы, пытающиеся сузить границы перебора за счёт построения частичных решений, представленных деревом поиска, и применения методов построения оценок, позволяющих опознать бесперспективные частичные решения, в результате чего от дерева поиска " отсекаются бесперспективные ветви. К таким методам относятся широко известный метод ветвей и границ или метод неявного перебора.
Другую категорию составляют метод динамического программирования, метод отсечений и метод Лагранжа. Здесь снижение размерности перебора достигается через "снижение требований", которое заключается в отказе от поиска оптимального решения и нахождении квазиоптимального решения за приемлемое время. -Такие алгоритмы получили название эвристических, поскольку для поиска решения они используют различные правила (эвристики) не имеющие строгого научного обоснования и определяемые опытным (эмпирическим) путём. Поэтому такие методы сильно зависят от специфики решаемой задачи. Одним из наиболее распространенных методов оптимизации является метод "локального поиска", когда заранее выбранное множество локальных операций используется для последовательного улучшения начального решения „ до тех пор, пока такое улучшение возможно, в противном случае оказывается, " что достигнут локальный оптимум [74]. Однако все описанные методы имеют один серьезный недостаток - они неспособны находить выход из локальных оптимумов. Это вызвано применением жёстких правил поиска в алгоритме оптимизации. Существует ещё одна категория поисковых методов - случайные методы, которые, в свою очередь делятся на три класса: случайный поиск, моделирование отжига и МГП [21, 41, 78, 90]. Эти методы образуют третью , область, обладающую в силу непрерывности оптимизационного поиска наибольшими перспективами развития [88, 89]. Генетические алгоритмы (ГА), относящиеся к МГП, являются случайно-направленными поисковыми методами. ГА, позаимствованный у природных аналогов, является наиболее ярким представителем эволюционных методов и представляет собой мощнейшее поисковое средство, имеющее важное значение при решении различных проблем. Теоретической основой МГП является моделирование естественного эволюционного процесса, в котором сильнейшие особи (решения с более качественной целевой функцией) имеют больший шанс выживания, оставляя, тем не менее, некоторый шанс (процент) выживания и для слабых решений. Это одно из существенных отличий МГП от других методов. Основные же отличия ГА от других оптимизационных и поисковых процедур заключаются в следующем: а) ГА работают не с параметрами, а закодированным множеством параметров; б) поиск осуществляется не из одной, а из множества точек; в) для оценки информации используется целевая функция, а не её приращения; г) при работе ГА используют вероятностные, а не детерминированные правила. ГА работает до тех пор, пока не пройдет заданное число итераций, либо не будет получено решение, удовлетворяющее заданным критериям. В отличие от остальных оптимизационных методов, ГА более приспособлены для" нахождения новых решений за счёт объединения . квазиоптимальных решений из разный популяций и обладают возможностями для выхода из локальных оптимумов. ГА отлично себя зарекомендовали на NP трудных задачах (см. рис.2.1.) [17, 20, 22 - 36, 81]. . Таким образом, на основании проведённого анализа можно утверждать, что, взяв за основу ГА для решения задачи разбиения схем при проектировании СБИС, можно получить лучший результат, по сравнению с другими оптимизационными методами. 2.2. Элементы генетических алгоритмов В начале 70-х годов Джон Холланд предложил использовать механизм эволюции органического мира для оптимизации технических систем [49]. По его теории анализ эволюции как процесса совершенствования различных органических систем позволяет описать процесс развития животного и . растительного.мира Земли. С течением времени среда обитания претерпевает постоянные изменения. Для того, чтобы выжить в изменившихся условиях организмы вынуждены перестраивать свою структуру - адаптироваться. То есть происходит комплексная адаптация многочисленной группы организмов (популяции), к изменяющимся внешним условиям среды. Возможности адаптации популяции организмов к внешним условиям среды зависят от разнообразия особей популяции. Популяция тождественных особей обладает очень низкой адаптивностью. Популяция индивидуальных особей, напротив, способна адаптироваться к любым внешним условиям среды [41]. То есть эволюцию можно рассматривать как процесс оптимизации органических систем необходимый для их выживания во внешней среде. Метод оптимизации технических систем, основанный на этих идеях получил название "генетические алгоритмы" (ГА). В качестве исходных данных для работы генетического алгоритма необходима популяция индивидов. Каждый индивид содержит хромосому, описывающую свойства объекта, и механизм построения объекта по хромосоме. Хромосома, в свою очередь, состоит из набора генов, каждый из которых описывает какое-либо свойство индивида. Совокупность генов, составляющих хромосому индивида, называют генотипом. Выбор метода кодирования хромосомы чрезвычайно важен, поскольку неправильный код может привести к потере оптимальных решений, попаданию в локальный оптимум, получению "нелегальных" решений.
Блок анализа преждевременной сходимости и критерия остановки алгоритма
Блок анализа преждевременной сходимости и критерия останова алгоритма — на каждой итерации алгоритма вычисляет и сравнивает лучшую целевую функцию "текущей популяции с лучшей целевой функцией . предыдущей популяции. При этом если они отличаются друг от друга, то преждевременной сходимости нет, в противном случае, блок анализа преждевременной сходимости передаёт необходимую информацию блоку адаптации, который вносит изменения в ход генетического поиска. Блок критерия останова проверяет условие окончания работы алгоритма, после чего производится выдача результатов.
Блок адаптации — программное или аппаратное устройство, которое анализирует ход решения задачи и вносит коррективы в организацию процесса поиска. Например, БА может менять архитектуру самого поиска (включать/отключать какой-либо блок), менять размер подпопуляции, способ получения популяции в нужный момент времени, а также изменять динамические параметры ГА [94 - 97].
В начале работы алгоритма на этапе анализа задачи, происходит анализ всей входной информации: постановки задачи, входных переменных, критериев и динамических параметров. Далее приступает к работе блок генерации стартовой популяции, который использует в своей работе генератор хромосом с группами (ГХСЯ) и создаёт популяцию "хороших" хромосом, заданного размера. Для определения размера группы и конкретных в ней вершин, производится анализ матрицы инцидентности исходного гиперграфа, в результате которого определяются максимальные и средняя локальные степени вершин, после чего и определяется размер, а по максимальной локальной степени конкретные вершины входящие в искомую группу. Необходимо заметить, что ГХСЯ используется только на начальном этапе работы алгоритма и не входит в дальнейший цикл генетического поиска, иначе бы в каждой последующей популяции возникали " решения из двух источников - на основе репродукции (стандартные средства ГА), и на основе ГСХЯ. Получаемые решения могут совпадать между собой и даже быть "хуже" чем решения, получаемые в результате генетического поиска. В конце концов, алгоритм может сойтись на хорошем, но далеко не оптимальном решении, либо потребуется намного больше времени для нахождения этого самого оптимального решения. .
После того, как сформирована стартовая популяция, алгоритм переходит к генетическому поиску. В блоке генетического поиска сначала начинает свою работу блок генетических операторов (ГО), который отличается от такового используемого в ПГА, наличием модифицированных процедур для каждого ГО. Каждая такая процедура использует в своей работе помимо статических параметров (размер популяции, размер подпопуляции с "лучшими" решениями, вероятности ГО) ещё и динамические параметры (параметр п, отвечающий за число раз выполнения каждого оператора; размер подпопуляции из которого выбираются хромосомы для ГО), изменяемые блоком адаптации в процессе работы алгоритма.
Применение ГО к хромосомам стартовой популяции осуществляется последовательно, согласно начальному распределению вероятностей ОК, ОМ, ОИ, учитывая параметр п. Заданный в начале работы алгоритма параметр п, для каждого ГО, случайным образом присваивается количеству хромосом равному п из стартовой популяции, т. е. параметру п соответствует некоторое натуральное число из диапазона 3 п Рт, где Рт - мощность стартовой популяции. Эти хромосомы как раз и будут иметь возможность участвовать в генетических операторах. Таким образом, мощность множества хромосом из - которого они копируются, для каждого ГО, может быть разной и равняется п. После чего случайным образом копируются хромосомы для ГО из подпопуляции размера п. Описанная процедура присвоения хромосомам параметра п производится заново после выполнения очередного ГО, поскольку после выполнения ГО этот параметр изменяется. Необходимо заметить, что стартовая и последующие популяции поделены на две подпопуляции, причём в первой подпопуляции размер которой задаётся в начале работы алгоритма, располагаются "лучшие" хромосомы посредством элитной селекции, а во второй подпопуляции все остальные хромосомы, размер которой вычисляется . относительно первой.
Производится оценка целевых функций (ЦФ) для всех хромосом в стартовой популяции и фиксируется наилучшая ЦФ. После этого, происходит случайный выбор хромосом-родителей для оператора кроссинговер (ОК) на основе аутбридинга, т. е. первая хромосома выбирается случайным образом из первой подпопуляции с "лучшими" хромосомами, а вторая с большей вероятностью будет максимально далёкая от первой, в смысле ЦФ - из второй. Использование генетического аутбридинга оказалось эффективным для ГП, т. к. аутбридинг направлен на предупреждение сходимости, заставляя алгоритм просматривать новые, неисследованные области ландшафта. Следует заметить, что порядок применения ГО к выбранным хромосомам не важен, т. к. он не влияет на качество получаемых решений. Наконец, осуществляется реализация оператора кроссинговер. После получения потомков производится оценка их ЦФ. Если ЦФ хотя бы одного из потомков "лучше" ЦФ "лучшего" родителя, то все потомки заносятся в новую популяцию, а блок адаптации уменьшает параметр п в 2 раза. В противном случае ОК реализуется заново, причём количество реализаций связано с параметром п для этого оператора, т. е. чем больше п, тем больше потребуется общего времени для оператора, но тем более качественные получаются решения. Если по истечении п попыток для ГО так и не было получено потомка с ЦФ лучшей, чем у "лучшего" родителя, то по окончании последней реализации ГО, заносятся все потомки с "худшими" ЦФ. Таким образом, в основе предложенной методики поиска заложен принцип многодетной семьи, заключающийся в многократном применении ГО к выбранной паре родителей и стремящейся получить потомков, лучше своих родителей в смысле ЦФ, т. е. параметр п как бы даёт шанс на получение - алгоритмом "лучших" хромосом в результате реализации ГО [92 - 94]. " Локальное улучшение решений выполняется при помощи модифицированной процедуры для оператора мутации (ОМ), работающей по тому же принципу что и процедура для ОК. Отличие состоит в том, что для ОМ хромосомы-родители выбираются из подпопуляции только с "лучшими" решениями, т. е. ОМ работает над "лучшими" решениями пытаясь их улучшить [93, 94]. . Далее реализуется следующий ГО — оператор инверсии (ОИ). Аналогичным образом выполняется модифицированная процедура для ОИ, но в . отличие от ОМ, хромосомы-родители случайным образом выбираются из всей " популяции. Указанный механизм "производства" потомков может включаться / выключаться пользователем для ОК, ОМ, ОИ. По окончании работы ОК, ОМ и ОИ формируется новая популяция, в которую входит прежняя популяция и хромосомы, полученные в результате работы ГО. После чего выполняется редукция новой популяции на. основе элитной селекции, которая производится по значению ЦФ, предварительно рассчитанной через . декодирование решений и оценку критериев. В результате элитной селекции в новую популяцию попадает нужное количество хромосом с "лучшими" ЦФ для следующей итерации.
Результаты исследований для блока модифицированных генетических операторов
При этом для расчёта показателей работы алгоритмов ГАСЭА и ПГА использовались формулы (4.1.). Результаты работы алгоритмов ГАСЭА и ПГА для тестов 19ks, PrimGAl и PrimGA2 сведены в таблице П.2.4., табл. П.2.5. и табл. П.2.6. соответственно. Здесь же приведены характеристики работы других алгоритмов. В данных таблицах использованы следующие сокращения:
Разработан пакет прикладных программ - пользовательский интерфейс для генерации и исследования различных гиперграфовых задач разбиения схем при проектировании СБИС, основной отличительной особенностью которого является универсальность и возможность генерации гиперграфов с любыми свойствами, а также утилита для конвертирования форматов входных файлов гиперграфов для обеспечения совместимости с другими аналогами. Представлены форматы данных входного файла гиперграфа и выходного файла (решения).
Сформулированы цели выполнения экспериментальных исследований; составлен план проведения и выполнены серии экспериментов; произведена статистическая обработка экспериментальных данных, что позволило уточнить теоретические оценки ВС А и ПСА алгоритма разбиения, подтвердившие, в целом, ранее полученные теоретические оценки. Полученные экспериментальные данные и их статистическая обработка позволили определить характер зависимости времени и памяти от количества вершин гиперграфа (примерно квадратичная). Проведенные исследования позволили получить ответы на вопросы прикладного характера, а также адекватно оценить - разработанный алгоритм. ,
Выполнено сравнение разработанного алгоритма разбиения схем с ПГА, а также с существующими аналогами. Экспериментально подтверждено, что применение разработанного алгоритма позволяет на 2 - 5% повысить качество решения задачи разбиения схем при проектировании СБИС. В результате выполненных теоретических и практических исследований по теме диссертационной работы реализованы следующие научные и практические положения: 1. Приведена классификация методов и алгоритмов решения задачи разбиения схем при проектировании СБИС. Проведён анализ существующих методов, алгоритмов и подходов к решению задачи разбиения, выявлены их достоинства и недостатки. 2. Показаны преимущества ГА по сравнению с традиционными методами решения NP-полных задач (возможность выхода из локальных оптимумов, работа не с одним, а с несколькими вариантами решений, гибкость структуры ГА и т. д.). Рассмотрены основные положения теории генетического поиска, методы селекции и отбора, выявлены их особенности и даны рекомендации по их использованию. На основе анализа эволюционных методик составлена универсальная схема генетического поиска с адаптивной структурой на основе динамических параметров, используемого в качестве метода оптимизации. Универсальность разработанной схемы состоит в том, что она может быть применима практически для любой оптимизационной задачи. Разработаны модифицированные -процедуры для генетических операторов, приведена структурная схема ГАСЭА, дано её функциональное и алгоритмическое описание. 3. Для повышения качества решений, был разработан проблемно ориентированный генератор хромосом стартовой популяции (ГХСЯ), повышающий качество получаемых решений на начальном этапе работы алгоритма и функционирующий только в предложенной системе кодирования решений. Созданы модифицированные процедуры, для генетических операторов, зависящие от динамических параметров, позволяющие повысить устойчивость генетического поиска и качество получаемых решений. Теоретически определена оценка пространственной сложности алгоритма, вычислительной сложности применяемых генетических операторов и алгоритма в целом. Оценка ПСА составляет 0(ап2) (где а - коэффициент, зависящий от текущих динамических, а также дополнительных параметров. алгоритма), а ВСА модифицированных процедур для генетических операторов и разработанного алгоритма составляет не выше 0(Рп2) (где (3 - коэффициент, зависящий от текущих параметров алгоритма (размер популяции, вероятностей ГО, динамических параметров й т.п.)), что в целом ниже либо равно ВС А многих из существующих равнозначных методов. 4. Проведены серии тестов и экспериментов и выполнена обработка экспериментальных данных, что позволило уточнить теоретические оценки ПСА и ВСА алгоритма разбиения и его поведение при разбиении схем различной структуры. Приведены оценки качественных характеристик алгоритмов при работе на схемах промышленного изготовления, в том числе и СБИС. Использование динамических параметров в процессе генетического поиска позволило алгоритму эффективнее адаптироваться к изменяющимся условиям задачи и как следствие, повысить качество получаемых им решений, что подтверждается результатами экспериментальных исследований. . 5. Разработано программное обеспечение, приведено его описание для изучения характеристик алгоритма (экспериментального тестирования) разбиения схем при проектировании СБИС и утилита для конвертирования форматов данных входных файлов гиперграфов с целью совместимости с известными аналогами. При создании программ использовался пакет Borland C++ Builder 5.0 для 32-разрядных ОС семейства Windows 9х, а отладка, тестирование и эксперименты поводились на IBM совместимом компьютере с процессором Intel Pentium II \ 400 MHz и оперативной памятью 320 MB DIMM РС-133. Для адекватного сравнения программного обеспечения использовались стандартные оценки производительности различных систем (по бенчмаркам ІСОМР и др.), представленные фирмой Intel [75]. Проведённые комплексные исследования показали улучшение работы алгоритма по сравнению с ПГА от 3% до 7% в зависимости от вида задачи. В задачах с числом элементов более 100, разработанный алгоритм ГАСЭА по качеству получаемых решений выглядел на 5% - 7% лучше.
