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



т

/ / Ч Ь

X

РОСТОВСКАЯ-НА-ДОНУ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ СЕЛЬХОЗМАШИНОСТРОЕНИЯ

На правах рукописи

Ведерникова Ольга Геннадьевна

РАЗРАБОТКА И ИССЛЕДОВАНИЕ КОМБИНИРОВАННОГО АЛГОРИТМА ГЕНЕТИЧЕСКОГО ПОИСКА И

ИМИТАЦИИ ОТЖИГА ДЛЯ ЗАДАЧИ РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ СБИС

Специальность: 05.13.12 - системы автоматизации проектирования

Диссертация на соискание ученой степени кандидата технических наук

Научные руководители: заслуженный деятель науки РФ, академик Нью-Йоркской

академии наук и АПК РФ,д.т.н.,профессор Ю.О.Чернышев, заслуженный деятель науки РФ, академик АЕН РФ и МАИ, д.т.н., профессор В.М. Курейчик.

Ростов-на-Дону 1999

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ......................................................................................4

1. АНАЛИЗ И ИССЛЕДОВАНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ И МЕТОДОВ ЗАДАЧИ РАЗМЕЩЕНИЯ ПРИ ПРОЕКТИРОВАНИИ

СБИС............................................................................................10

1.1. Конструктивные особенности матричных СБИС...........................10

1.2. Иерархический подход к проектированию СБИС.........................11

1.3. Этапы проектирования СБИС....................................................12

1.4. Анализ математических моделей схем для задачи размещения..........13

1.5. Классификация критериев задачи размещения..............................18

1.6. Анализ методов решения задачи размещения................................21

1.6.1. Классификация традиционных методов размещения....................21

1.6.2. Метод имитации отжига........................................................27

1.6.3. Метод имитации эволюции....................................................30

1.6.4. Анализ достоинств и недостатков методов размещения ................30

1.7. Выводы и рекомендации.........................................................32

2. ТЕОРЕТИЧЕСКИЕ ИССЛЕДОВАНИЯ ФАКТОРОВ;.ВЛИЯЮЩИХ

НА КАЧЕСТВО И СХОДИМОСТЬ АЛГОРИТМСШ ГЕНЕТИЧЕСКОГО ПОИСКА И ИМИТАЦИИ ОТЖИГА........................................................33

2.1. Основные понятия и термины...................................................33

2.2. Символьная модель задачи оптимизации.....................................34

2.2.1 Функция степени приспособленности....................................... .36

2.3. Цель эволюции популяции в процессе естественного отбора............36

2.4. Оценка генетического разнообразия популяции..............................37

2.5. Способы создания стартовой популяции.......................................38

2.6. Классификация способов образования новых особей.......................41

2.7. Системы скрещивания особей...................................................44

2.7.1. Панмиксия (случайное скрещивание)........................................44

2.7.2. Инбридинг и аутбридинг.........................................................45

2.7.3. Ассортативное скрещивание...................................................46

2.8. Классификация стратегий отбора................................................49

2.9. Оценка эффективности генетических операторов...........................53

2.10. Анализ макроэволюции..........................................................57

2.11. Исследование метода имитации отжига......................................59

2.11.1 Марковская модель алгоритма моделирования отжига..................59

2.11.2. Универсальное расписание отжига..........................................61

2.11.3. Начальная температура.........................................................62

2.11.4. Правило изменения температуры............................................63

2.11.5. Ограничивающее окно.........................................................65

2.11.6. Инкрементный способ вычисления значений целевой функции......66

2.12. Выводы и рекомендации.........................................................66

3. РАЗРАБОТКА КОМБИНИРОВАННОГО АЛГОРИТМА ГЕНЕТИЧЕСКОГО

ПОИСКА И ИМИТАЦИИ ОТЖИГА........................................................70

3.1. Математическая модель и целевая функция..................................70

3.2. Формирование кластеров.........................................................74

3.3. Создание начальной популяции, основанное на методе последовательного размещения по связности.........................................................78

3.4. Модифицированные операторы направленной мутации..................81

3.4.1. Операторы мутации, основанные на методе релаксации.................82

3.4.2. Операторы мутации, основанные на методе Кернигана-Лина, уменьшающие степень загруженности каналов....................................85

3.4.3. Динамические нормы случайной и направленной мутаций.............88

3.5. Оператор кроссинговера......................................................... 90

3.5.1. Динамическая стратегия скрещивания или подбор особей

для оператора кроссинговера..........................................................91

3.6. Динамический оператор отбора, основанный на методе имитации отжига..............................................................................94

3.7. Механизм управления процессом генетического поиска...................97

3.8. Стратегия макроэволюции.......................................................97

3.9. Улучшение решения после разрушения кластеров методом имитации отжига.........................................................................99

3.10. Выводы и рекомендации......................................................104

4. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ РАЗРАБОТАННОГО АЛГОРИТМА..........................................................................................105

4.1. Цель экспериментального исследования.....................................105

4.2. Теоретическая оценка временной сложности алгоритма..................105

4.3. Определение пространственной и временной сложности алгоритма... 107

4.4. Определение управляющих параметров разработанного генетического алгоритма.................................................................................115

4.4.1. Генетические параметры......................................................116

4.4.2. Параметры кластеризации.....................................................128

4.4.3. Параметры имитации отжига.................................................133

4.5. Сравнение качества решений, получаемых разработанным алгоритмом задачи размещения элементов на плоскости......................................134

4.6. Выводы и рекомендации.........................................................139

ЗАКЛЮЧЕНИЕ..............................................................................140

ЛИТЕРАТУРА................................................................................142

ВВЕДЕНИЕ

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

Производство интегральных схем разбивается на три этапа: проектирование, изготовление, тестирование. В виду значительной сложности ни один из этих этапов не может быть выполнен без средств автоматизированного проектирования. Одним из этапов проектирования СБИС является этап конструкторского проектирования, который включает в себя следующие стадии [4]: компоновка, размещение, трассировка и т.д.

Разработка методов и алгоритмов для решения задачи размещения осуществляется на протяжении многих лет, но по-прежнему является актуальной. Это связано, в первую очередь, с тем, что эта задача является №-полной, и разработать универсальный алгоритм, позволяющий находить точное оптимальное решение за приемлемое время затруднительно. Появление новых более совершенных средств вычислительной техники, дающих мощные вычислительные ресурсы, а также повышенные требования к проектируемым устройствам, все это является побудительной причиной разработки новых алгоритмов решения задачи размещения. Большое значение при разработке новых алгоритмов является использование метода оптимизации. Существует несколько подходов к решению ИР - полных задач [4,5].

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

Ко второму классу относятся, так называемые, эвристические алгоритмы, позволяющие получать неплохие решения за приемлемое время.

К третьему классу относятся алгоритмы случайно-направленного поиска, основанные на принципах моделирования.

Недостатки методов первого класса очевидны. Недостатки эвристических алгоритмов решения задачи размещения сводятся, в общем, к низкому качеству решения, либо затрачивают на его поиск избыточное количество времени [4-6]. Алгоритмы случайно-направленного поиска обладают способностью находить более высококачественные решения и за приемлемое время.

Одним из методов случайно-направленного поиска является метод генетического поиска. В 1975 году американский исследователь Дж. Холланд описал методологию изучения адаптивных систем и их применения для искусственных систем, а также разработал подходы к решению комбинаторно-оптимизационных задач. Сейчас генетические алгоритмы (ГА) хорошо известная и эффективная технология оптимизации, применяемая для различных задач техники, моделирующая естественный процесс эволюции в качестве средства достижения оптимума и основанная на имитации процессов натуральной селекции и генетических преобразований [26].

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

Другой метод случайно-направленного поиска - метод имитации отжига. В 1953 году Метрополис сделал попытку применить идею процесса отжига, заимствованную из физики, к проблемам численных методов на основе имитационного моделирования. В 1983 году Кирпатрик использовал эту концепцию для решения комбинаторно-оптимизационных задач. С тех пор этот метод широко используется при решении технических задач, проводятся исследования и разработки его модификаций. Алгоритм имитации отжига обладает высокой способностью выходить из локальных ям и сходиться к глобальному минимуму, но при этом имеет один недостаток: большая временная сложность. Алгоритм генетического поиска обладает иными качествами: быстрой сходимостью, простотой реализации и иногда может сходиться к локальному минимуму. Скомбинировав должным образом эти алгоритмы можно устранить присущие им недостатки, сохранив при этом их достоинства и преимущества [91-95].

Недостатки генетических алгоритмов и алгоритмов имитации отжига, существующих и применяемых для решения задачи размещения, заключаются в том, что они не в достаточной степени учитывают особенности задачи, что приводит к излишним требованиям к объему памяти и времени работы алгоритма размещения.

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

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

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

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

2) разработан механизм управления процессом поиска ГА, основанный на методе имитации отжига, позволяющий осуществлять выход из локальных опти-мумов.

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

4) построены и исследованы: а) комбинированный алгоритм решения задачи размещения элементов СБИС без предварительного формирования кластеров; б) комбинированный алгоритм решения задачи размещения элементов СБИС с предварительным формированием кластеров и заключительным этапом имитации отжига после разрушения кластеров;

МЕТОДЫ ИССЛЕДОВАНИЯ в диссертации основаны на использовании элементов теории множеств, теории графов, теории алгоритмов, теории комбинаторной оптимизации, элементов теории статистических вычислений.

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

а) разработан алгоритм формирования начальной популяции решений для задачи размещения, основанный на методе последовательного размещения по

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

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

в) разработан механизм управления процессом поиска ГА, заключающийся в динамическом изменении вероятностей случайных и направленных операций с использованием имитации отжига, позволяющий преодолевать локальные опти-мумы.

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

- комбинированный алгоритм и программа генетического поиска и имитации отжига для решения задачи размещения ячеек СБИС без предварительного формирования кластеров;

- комбинированный алгоритм и программа генетического поиска и имитации отжига с предварительным формированием кластеров и заключительным этапом имитации отжига после разрушения кластеров;

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетной работе, проводимой кафедрой «ПМ и ВТ» Ростовской государственной академии сельскохозяйственного машиностроения (РГАСХМ) по темам: «Разработка мультипликативных и генетических алгоритмов решения оптимизационных задач САПР» 1993-1994гг, «Разработка генетических алгоритмов для решения оптимизационных задач технического обслуживания в условиях эксплуатации» (19951996гг.) В Ростовском-на-Дону филиале Ниижелдоравтоматизация использованы при выполнении НИОКР в 1998 г. комбинированный алгоритм решения задачи размещения элементов СБИС без предварительного формирования кластеров и программы размещения элементов СБИС на плоскости, основанные на разработанном алгоритме, и внедрены в 1999 г. в качестве программного обеспечения решения задач САПР. Комбинированный алгоритм генетического поиска с предварительным формированием кластеров внедрен в Майкопском государственном технологическом институте (МГТИ) в 1999 г. и используется в научно-исследовательском секторе (НИС) МГТИ для выработки управляющих решений в условиях высокой размерности и многовариантности решений. Кроме того, мате-

риалы диссертации использованы в учебном процессе на кафедре «ПМ и ВТ» РГАСХМа в цикле лабораторных работ и практических занятий по курсу «Математическое моделирование» в 1992-1995г.

АПРОБАЦИЯ основных теоретических и практических результатов работы проводилась на НТК РГАСХМа (г. Ростов-на-Дону,1994-1998гг.), Всероссийских научно-технических конференциях студентов и аспирантов «Новые информационные технологии. Информационное, программное и аппаратное обеспечение» (г. Таганрог, 1995, 1998гг.), Всероссийских научно-технических конференциях с участием зарубежных представителей "Интеллектуальные САПР" (г. Геленджик, 1995-1998гг.).

ПУБЛИКАЦИИ. Результаты диссертации отражены в 6-ти печатных работах.

СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИОННОЙ РАБОТЫ. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Работа содержит 142 стр., а также 46 рис., список литературы из 111 наименований, 12 стр. приложений и актов об использовании.

Во ВВЕДЕНИИ обоснована актуальность темы диссертационной работы, поставлена цель работы, дано общее описание выполненной работы.

В ПЕРВОЙ ГЛАВЕ приведены основные этапы в проектировании СБИС, проведена классификация критериев задачи размещения. Приведены классификация и анализ существующих алгоритмов решения задачи размещения. Определена перспективная область исследования. Рассмотрены существующие алгоритмы, которые относятся к перспективным: алгоритм генетического поиска и алгоритм имитации отжига. Приведена постановка задачи размещения ячеек СБИС.

Во ВТОРОЙ ГЛАВЕ Приведен анализ способов создания стартовой популяции и способ оценки генетического разнообразия популяции. Сделаны выводы о перспективности создания стартовых популяций, на основе детерминированных методов. Приведены классификация и анализ способов образования новых особей и систем скрещивания особей. Приведена классификация стратегий отбора и сделаны выводы о перспективности комбинирования детерминированных и вероятностных стратегий отбора. Разработан способ оценки эффективности генетических операторов. Проанализирован метод имитации отжига. Обоснован оптимальный режим отжига и оптимальный выбор начальной температуры. Сделан

вывод о перспективности комбинирования метода гене�