Содержание к диссертации
Введение
1. Анализ алгоритмов решения задачи разбиения 4 Схемэва 15
1.1. Постановка задачи разбиения схем 15
1.2. Классификация методов и алгоритмов решения задачи разбиения 25
1.3. Выводы и рекомендации 29
2. Анализ и выбор моделей и алгоритмов решения задачи 30
2.1. Анализ и выбор математической модели 30
2.1.1. Виды математических моделей 30
2.1.2. Графовые модели 34
2.1.3. Модели на основе специальных графов 38
2.1.4. Гиперграфовые и ультраграфовые модели 38
2.2. Внутренняя и внешняя устойчивость 44
2.3. Анализ алгоритмов определения независимых и і» доминирующих подмножеств 48
2.3.1. Алгоритм полного перебора 48
2.3.2. Алгоритм систематического перебора 50
2.3.3 Последовательный алгоритм 52
2.3.4. Методы, основанные на логических произведениях 54
2.3.5. Векторный способ нахождения вершинного и реберного покрытий 55
2.4. Выводы и рекомендации 58
3. Разработка генетических алгоритмов выделения Ядер графа 59
3.1.Анализ существующих алгоритмов решения оптимизационных задач 59
3.1.1. Методы решения оптимизационных задач 59
3.1.2. Основные парадигмы генетических алгоритмов 60
3.1.3. Структура генетического алгоритма 70
3.2. Разработка итерационного алгоритма выделения экстремальных подмножеств 74
3.2.1. Алгоритм «Поиск в глубину» 74
3.2.2. Алгоритм «Поиск в глубину с отсечением» 75
3.3. Разработка простого генетического алгоритма выделения экстремальных подмножеств 78
3.3.1. Разработка методики кодирования 78
3.3.2. Подбор генетических операторов 81
3.3.3. Разработка структуры простого генетического алгоритма построения экстремальных подмножеств 87
3.4. Разработка модифицированного генетического алгоритма выделения независимых подмножеств в графе 91
3.4.1. Разработка структуры хромосом 91
3.4.2. Стратегия формирования начальной популяции 92
3.4.3. Разработка генетических операторов 92
3.4.4. Разработка схемы генетического поиска 95
3.5. Разработка эволюционного алгоритма выделения экстремальных подмножеств в графе 97
3.5.1. Алгоритм выделения доминирующих подмножеств 97
3.5.2. Алгоритм выделения независимых подмножеств 105
3.6. Теоретические оценки алгоритмов 110
3.7. Выводы и рекомендации 113
4. Экспериментальные исследования 115
4.1. Итерационный алгоритм нахождения экстремальных подмножеств 115
4.1.1. Анализ временной сложности алгоритма 115
4.1.2. Описание программы 116
4.1.3. Экспериментальные исследования 118
4.2. Простой генетический алгоритм нахождения экстремальных подмножеств 118
4.2.1. Описание интерфейса 118
4.2.2. Результаты экспериментальных исследований 121
4.2.3. Анализ временной сложности 123
4.3. Модифицированный генетический алгоритм выделения экстремальных подмножеств 125
4.3.1. Описание интерфейса 125
4.3.2. Экспериментальные исследования 128
4.4. Эволюционный алгоритм нахождения экстремальных подмножеств в графе 130
4.4.1. Описание интерфейса программы 130
4.4.2. Результаты экспериментальных исследований 138
4.5. Выводы и рекомендации 143
Заключение 145
Литература 146
Приложения 155
Приложение № 1 156
- Анализ алгоритмов определения независимых и і» доминирующих подмножеств
- Разработка простого генетического алгоритма выделения экстремальных подмножеств
- Разработка структуры простого генетического алгоритма построения экстремальных подмножеств
- Простой генетический алгоритм нахождения экстремальных подмножеств
Введение к работе
В настоящее время во многих отраслях таких, например, как электронная промышленность, приборо- и машиностроение широко применяются интегральные микросхемы (ИС) большой (БИС) и сверхбольшой (СБИС) степени интеграции. Это повышает надежность электронно-вычислительной аппаратуры (ЭВА), снижает ее габариты, потребляемую мощность, улучшая, таким образом, технико-экономические характеристики выпускаемых изделий.
Под «интегральной микросхемой (ИС)» понимается микроэлектронное изделие окончательной или промежуточной формы, предназначенное для выполнения функций электронной схемы, элементы и связи которого нераздельно сформированы в объеме и(или) на поверхности материала, на основе которого изготовлено изделие [1]. Согласно [2, 3] большой интегральной микросхемой (БИС) называется интегральная- микросхема содержащая 500 и более элементов, изготовленных по биполярной технологии, либо 1000 и более элементов, изготовленных по МДП-технологии, причем под элементом интегральной микросхемы понимается часть ИС, не выдел енная! в самостоятельное изделие, но реализующая функцию какого-либо элемента схемы, например, транзистора.
Степень интеграции постоянно возрастает с момента изобретения ИС. В 1965 году сопрезидент фирмы Intel Гордон Мур, предсказал, что число элементов на кристалле ИС должно удваиваться каждый год на протяжении последующих 10 лет. Это предсказание впоследствии было названо законом Мура [76]. Последующие 25 лет позволили уточнить закон Мура: число элементов на кристалле удваивается в среднем каждые 1,5 года. Применение на этапе проектирования САПР разного уровня способствует повышению степени интеграции СБИС на уровне узлов, блоков и всей системы в целом [4 — 10].
Неуклонное повышение степени интеграции СБИС привело к тому, что в них более 60% общей временной задержки сигнала приходится на задержки в межсоединениях. Рост размера области, отводимой для межсоединений, опережает рост размера области, предназначенной для активных элементов. В чипе, содержащем 10 миллионов транзисторов и использующем 4 слоя металлизации, около 40% площади отводится под межсоединения. Кроме того, рост числа транзисторов на кристалле, увеличивает также и средние размеры кристаллов. Подсчитано, что площади кристаллов самых больших ИС возрастают примерно на 13% в год и эта тенденция, согласно прогнозу, сохранится, по крайней мере, на ближайших полтора — два десятилетия.
Быстрая эволюция в производстве ИС стала бы невозможной без использования автоматизации выполнения различных этапов проектирования [7-9]. Сейчас, на всех стадиях проектирования топологии СБИС интенсивно используют средства автоматизации проектирования (САПР) и многие фазы могут быть полностью или частично автоматизированы.
Для того, чтобы получить решение задачи за приемлемое время, при условиях, когда размещение полной информации об объекте в памяти компьютера невозможно из-за ее большого объема, в современных системах проектирования применяется иерархический подход.
Иерархический подход подразумевает разбиение задачи проектирования СБИС на несколько последовательных этапов [4, 7]. Одним из важнейших этапов проектирования СБИС является этап конструкторского проектирования. Этап конструкторского проектирования, в свою очередь, также состоит из нескольких задач, к числу которых относится и задача разбиения.
Поскольку СБИС может содержать несколько миллионов транзисторов, то невозможно спроектировать топологию всей схемы целиком в связи с ограниченными возможностями вычислительных средств, поэтому схема разбивается группированием компонентов в блоки. ЕГ результате разбиения формируется множество блоков и множество соединений между блоками [4,11,12]. В очень больших схемах используется иерархическая структура разбиения.
Совершенно очевидно, что эффективность решения переборных задач непосредственно зависит от выбора формальной математической модели схемы. В настоящее время при создании структурных математических моделей схем используется аппарат теории графов. Это дает возможность строить
математически обоснованные алгоритмы проектирования, находить простые и высококачественные решения, рационально и эффективно использовать ЭВМ
[9, 10].
.Использование математических методов служит гарантией создания качественных систем. Эти методы состоят, в основном, из математических моделей, адекватных объектам проектирования, и алгоритмов оптимальных преобразований этих моделей с целью получения желаемого качества.
В качестве математических моделей схем используют специальные графы и гиперграфы, позволяющие адекватно отражать набор многоарных отношений, характерных для элементов БИС [11 -15].
Использование гиперграфов позволяет обходить «проблему узлов» и компактно описывать проектируемую схему, а также строить эффективные локально-оптимальные и точные алгоритмы решения исследуемых задач.
Вообще, проблема выделения независимых и доминирующих подмножеств, в графовых и гиперграфовых моделях относится к числу наиболее известных и популярных задач теории графов.
Большой вклад в развитие моделей, методов, стратегий, алгоритмов автоматизированного проектирования СБИС внесли российские и зарубежные учёные такие, как: Бершадский A.M., Казенное Г.Г., Курейчик В.М., Норенков И.П., Селютин В.А., Шервани Н. и др. В основном известные алгоритмы, программы и пакеты в САПР предназначены для оптимальной компоновки, размещения разногабаритных объектов (формирования базового плана кристалла) и межблочной трассировки межсоединений по критерию минимизации занимаемой площади и длины связей [13-16]. В связи с увеличением сложности и размерности задач конструкторского проектирования, а также с возникновением новых тенденций в технологии изготовления СБИС, появляется необходимость в разработке новых направлений, методик, алгоритмов для решения данного класса задач.
С точки зрения повышения эффективности САПР, представляет интерес разработка новых алгоритмов и методов проектирования, для так решения называемых NP-полных задач, т.е. задач, в которых нахождение оптимального
решения возможно только полным переборо.м. К числу таких методов можно отнести методы эволюционного моделирования, которые появились в начале 70-х годов двадцатого века. В настоящее время они получили широкое распространение при решении задач в самых различных областях [17 — 23], поскольку такие алгоритмы позволяют обрабатывать множество решений при учёте множества критериев [24-36]. Данными свойствами обладают генетические алгоритмы (ГА) - поисковые алгоритмы, основанные на механизмах натуральной селекции и генетики, работающие с популяциями решений методом эволюционного поиска. Уже Ихмеются примеры успешного применения ГА для решения самых различных задач [40 - 52], в том числе и задач автоматизированного проектирования СБИС [53 - 78].
Значительный вклад в развитие методов эволюционного поиска внесли такие учёные, как: Холланд Д., Гольдберг Д., Растригин Л.А., Букатова И.Л, Батищев Д.И., Курейчик В.М. и др. Сущность генетических алгоритмов заключается в моделировании естественных эволюционных процессов как средства достижения оптимума. Основная проблема при этом - поиск баланса между эффективностью и качеством для "выживания" в различных условиях. Пожалуй, одним из главных свойств ГА является, то что, они в силу своей "природы" достаточно легко преодолевают локальные оптимумы. Гибкость структуры ГА, возможность её настройки и перенастройки дают возможность создания структур, обеспечивающих получение наилучшего результата за приемлемое время. Это, в свою очередь, предоставляет исследователям широкие возможности для поиска в этом направлении [44, 50, 55 - 60, 63 - 66].
Из всего вышеизложенного следует, что задача разработки нового алгоритма разбиения схем при проектировании СБИС на основе методов эволюционного моделирования и генетического поиска в комбинации с итерационными методами, позволяющего сократить время поиска решений в задачах большой размерности, и в то же время повысить качество получаемых решений за счёт адаптивной архитектуры является АКТУАЛЬНОЙ.
ЦЕЛЬЮ диссертационной работы является исследование и разработка методов разбиения схем ЭВА на основе модифицированных схем и операторов
генетического поиска и эволюционного моделирования, по критерию суммарного числа внутренних (внешних) связей, позволяющих повысить качество решений для задач большой размерности.
Для достижения поставленной цели были решены следующие задачи:
1) Проведен анализ поставленной задачи и определено ее место в общей задаче проектирования ЭВА, а также комплексный анализ существующих алгоритмов разбиения схем (последовательных, параллельных, последовательно-параллельных, смешанных).
2) Проведен анализ и обоснование выбора математической модели схем для решения поставленной задачи. Предложен ряд графовых и гиперграфовых математических моделей для решения задачи разбиения схем ЭВА. Проведен анализ существующих алгоритмов решения задачи выделения независимых и доминирующих подмножеств в специальных графовых и гиперграфовых моделях схем ЭВА.
3) Выполнен анализ основных генетических операторов и их модификаций с точки зрения их пригодности для решения поставленной задачи, сформулированы основные принципы и схема работы ГА;
4) Предложена модифицированная схема алгоритма простого генетического алгоритма, а также методика кодирования решений, позволяющая повысить скорость получения решений;
5) Разработана новаяі схема генетического алгоритма выделения независимых и доминирующих подмножеств, а также генетические операторы, адаптированные к требованиям решаемой задачи (операторы кроссинговера, селекции, отбора, мутации). Предложена методика оценки качества получаемых решений (целевая функция);
6) Разработан новый эволюционный алгоритм выделения ядер в нечетких графах и гиперграфах. Разработана новая двухуровневая схема поиска ядер в нечетких графах и гиперграфах. Разработаны новые генетические и эволюционные операторы (кроссинговер на основе логических операций, мутация на основе целевой функции и др.).
7) Выполнены экспериментальные исследования разработанных
методов и алгоритмов, а также их сравнение с известными алгоритмами разбиения.
Для решения поставленных задач использовались следующие МЕТОДЫ ИССЛЕДОВАНИИ: элементы высшей математики, теории множеств, элементы теории графов и гиперграфов, элементы теории алгоритмов, элементы теории генетического поиска, статистических вычислений.
НАУЧНАЯ НОВИЗНА диссертационной работы заключается в:
1) Разработке новой схемы функционирования генетического алгоритма выделения независимых и доминирующих подмножеств;
2) Формировании структуры и принципов кодирования (декодирования) решений для» решения задачи выделения независимых и доминирующих подмножеств;
3) Построении новых эволюционных и генетических операторов и их модификаций, адаптированных к требованиям решаемой задачи;
4) Разработке новой двухуровневой архитектуры эволюционного поиска для выделения ядер в нечетких графах и гиперграфах, позволяющих повысить эффективность и быстродействие работы эволюционного алгоритма.
ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют: Пакет прикладных программ.
1) Новая методика поиска решений на основе межпопуляционного обмена, использующая знания о решаемой задаче, которая может эффективно применяться для решения задач различных экстремальных подмножеств в графах и гиперграфах.
2) Новая двухуровневая архитектура эволюционного поиска, существенно расширяющая пространство поиска и позволяющая добиться существенного улучшения качества получаемых решений без увеличения времени работы алгоритма.
3) Пакет прикладных программ для решения задачи выделения различных экстремальных подмножеств в графовых и гиперграфовых математических моделях схем ЭВА для операционных систем Windows® 9х/МЕ/2000/ХР фирмы Microsoft Corporation, созданная в среде
объектно-ориентированного программирования Borland C++ Builder.
РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетных работах «Разработка интеллектуальных систем проектирования на основе эволюционной адаптации» (№ ГР 01.9.60004346) и «Разработка теории и принципов построения интеллектуальных систем автоматизированного проектированного проектирования на основе эволюционной адаптации, неиросетевых моделей и методов принятия решений» (№ ГР 01.2.00118499), а также научно-исследовательских работах, выполняемых по грантам Российского фонда фундаментальных исследований «Разработка теории и принципов эволюционного проектирования на основе многоагентных подходов» (№ 02-01-01275), «Эволюционное проектирование с адаптацией» (№ 01-01-00044), «Генетические алгоритмы в интеллектуальных САПР» (№ 99-01-00050), х/д между ТРТУ и Российским научно-исследовательским институтом информационных технологий и систем автоматизированного проектирования (ГУ Рос НИИ ИТ и АП) № 12301 «Разработка эволюционных алгоритмов на графах с динамическими параметрами» и научно-исследовательской работе «Разработка интеллектуальных систем проектирования и технологической подготовки производства на основе эволюционной адаптации» (№ ГР 01200111207), выполняемой в рамках научно-технической программы Министерства образования РФ «Научные исследования высшей школы по приоритетным направлениям науки и техники». Кроме того, материалы диссертации использованы в учебном процессе на кафедре САПР ТРТУ при чтении лекций, а также лабораторных и практических занятиях по курсам «Эволюционное моделирование и генетические алгоритмы», «Методы оптимизации и генетические алгоритмы» и «Математические основы дискретной техники».
АПРОБАЦИЯ основных теоретических и практических результатов работы проводилась на научных семинарах кафедры САПР "Генетические алгоритмы" (с 2000 по 2004 гг., ТРТУ), Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и
системы управления» (г. Таганрог, 2000, 2002 гг.), Всероссийской научной конференции молодых ученых и аспирантов (г. Таганрог, 2000, 2001, 2003 г.), Всероссийской научной конференции молодых учёных и аспирантов «Новые информационные технологии. Разработка и аспекты применения» (г. Таганрог, 2002, 2003 гг.), Международной научно-технической конференции «Интеллектуальные САПР» (г. Геленджик, 2000 - 2004 гг.), Международной научной конференции «Искусственные интеллекиуальные системы» (г. Геленджик, 2002 - 2004 гг.).
ПУБЛИКАЦИИ. Результаты диссертации отражены в 10 печатных работах.
СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИОННОЙ РАБОТЫ. Диссертационная работа состоит из введения, четырех глав, заключения, и списка использованных источников. Работа содержит 157 стр., включая 67 рис., 4 табл., список использованных источников из 110 наименований, 3 стр. приложений и актов об использовании.
СОДЕРЖАНИЕ РАБОТЫ.
ВО ВВЕДЕНИИ обоснована актуальность темы диссертационной работы, дано общее описание выполненной работы.
В ПЕРВОЙ ГЛАВЕ приведена постановка задачи разбиения схем при проектировании СБИС по критерию максимизации (минимизации) суммарного количества межблочных связей. Рассмотрены существующие алгоритмы и методы решения задачи разбиения схем при проектировании СБИС, выявлены их достоинства и недостатки.
ВО ВТОРОЙ ГЛАВЕ проведен сравнительный анализ существующих математических моделей схем ЭВА и выбрана математическая модель, позволяющая интерпретировать задачу разбиения как задачу построения независимых и доминирующих подмножеств. Сформулирована постановка задачи определения независимых и доминирующих подмножеств для логических схем, представленных графовыми и гиперграфовыми математическими моделями и приведены основные теоретические положения и критерии, позволяющие оценить сложность рассматриваемой проблемы.
Проведен анализ существующих методов и алгоритмов выделения независимых и доминирующих подмножеств в графовых и гиперграфовых математических моделях и определено место рассматриваемой задачи в процессе автоматизированного проектирования ЭВА. Выделены основные группы алгоритмов, а также их достоинства, недостатки и перспективы развития. Приведены оценки пространственной и временной сложности алгоритмов.
В ТРЕТЬЕЙ ГЛАВЕ приведена краткая классификация методов оптимизации, показаны преимущества методов эволюционного моделирования и генетического поиска по сравнению с традиционными методами решения NP - полных задач. Кратко проанализированы основные положения теории генетического поиска. На основе анализа механизма эволюции предложен ряд подходов к использованию методов эволюционного моделирования и генетических алгоритмов для решения задачи построения независимых и доминирующих подмножеств в специальных графовых и гиперграфовых математических моделях. Предложена модифицированная форма представления исходных данных, позволяющая сократить объем требуемой памяти и ряд процедур построения начальной популяции и определения длины хромосом. Определена методика кодирования, учитывающая специфику решаемой задачи и позволяющая улучшить качество получаемых решений. Разработаны модификации генетических операторов, позволяющие учитывать особенности решаемой задачи. Предложены архитектура и принципы работы генетических алгоритмов выделения. независимых и доминирующих подмножеств, а также правила формирования популяции и отбора индивидов, сводящие к минимуму вероятность преждевременной сходимости. Определены теоретические оценки пространственной и временной сложности разработанных алгоритмов. На основе выполненного анализа ранее разработанных ГА даны рекомендации по настройке ГА и основных генетических операторов.
В ЧЕТВЕРТОЙ ГЛАВЕ приведено описание экспериментальных исследований разработанных алгоритмов и программ. Выполнена статистическая обработка полученных экспериментальных данных. Выполненные расчеты подтвердили, в целом, полученные ранее теоретические оценки временной и пространственной сложности комплекса алгоритмов. Это 0 позволило получить ответы на вопросы прикладного характера, а также оценить разработанные алгоритмы. Определены диапазоны оптимальных значений параметров генетического алгоритма. Выполнено сравнение разработанных алгоритмов выделения независимых и доминирующих подмножеств с существующими аналогами и приведены результаты работы разработанного комплекса алгоритмов. Представлено описание разработанного пакета прикладных программ для генерации, решения и исследования, ф различных графовых и гиперграфовых моделей схем для задачи разбиения схем при проектировании СБИС.
В ЗАКЛЮЧЕНИИ изложены основные выводы и результаты диссертационной работы.
В приложениях приведены копии актов внедрения.
Анализ алгоритмов определения независимых и і» доминирующих подмножеств
На первый взгляд кажется, что нахождение всех независимых подмножеств графа — очень простая задача, которую можно решить путем последовательного перебора всех возможных вариантов.
При этом достаточно перебрать все внутренне устойчивые подмножества в графе с одновременной проверкой каждого множества на независимость (это осуществляется путем добавления к исследуемому множеству дополнительной, не принадлежащей ему, вершины и выяснения того, сохраняется ли внутренняя устойчивость) и запоминанием независимых множеств.
Однако такое представление действительно справедливо, только для небольших графов, например с числом вершин, не превосходящим 20. Однако с увеличением числа вершин этот метод поиска становится с вычислительной точки зрения громоздким. Число независимых множеств увеличивается, и в процессе выполнения процедуры большое число внутренне устойчивых множеств формируется, а затем вычеркивается, так как обнаруживается, что они содержатся в других, ранее полученных множествах, и поэтому не являются независимыми.
Как и все алгоритмы полного перебора, данный алгоритм имеет экспоненциальную временную сложность и не может быть использован для решения практических задач. Для того чтобы избежать этих трудностей были разработаны различные методы улучшения перебора.
Достаточно эффективным является систематический метод перебора Брона и Кэрбоша [19]. Данный алгоритм является существенно упрощенным перебором, использующим дерево поиска. В этом методе не нужно запоминать генерируемые внутренне устойчивые множества для проверки их на независимость путем сравнения с ранее сформированными множествами. В процессе поиска - на некотором этапе k - внутренне устойчивое множество вершин Sk расширяется путем добавления к нему подходящим образом выбранной вершины (чтобы получилось новое внутренне устойчивое множество Sk+i) на этапе к + 7, и так поступают до тех пор, пока добавление вершин станет невозможным, а порождаемое множество не станет независимым множеством. Пусть Qk будет на этапе к наибольшим множеством вершин, для которого Sk п Qk = 0, т. е. после добавления любой вершины из Qk к Sk получается внутренне устойчивое множество Sk+i. В некоторый произвольный момент работы алгоритма множество Qk состоит вообще говоря, из вершин двух типов: подмножества Qk тех вершин, которые уже использовались в процессе поиска для расширения множеств Sk, и подмножества Qk таких вершин, которые еще не использовались. Тогда дальнейшее ветвление в дереве поиска включает процедуру выбора вершины х,ь є Qk, добавление ее к Sk для построения множества
Шаг возвращения алгоритма состоит в удалении вершины x,k из Sk+i, чтобы вернуться к Sk, изъятии xlk из старого множества QC И добавлении JC, к старому множеству Q для формирования новых множеств Qk и Qk.
Легко заметить, что множество Sk является независимым множеством только тогда, когда невозможно его дальнейшее расширение, т. е. когда Qk = 0. Если Qk 0, то немедленно заключаем, что текущее множество Sk было расширено на некотором предшествующем этапе работы алгоритма путем добавления вершины из Qk, и поэтому оно не является независимым множеством. Таким образом, необходимым и достаточным условием того, что Sk - независимое множество, является выполнение равенств
Теперь совершенно очевидно, что если очередной этап работы алгоритма наступает тогда, когда существует некоторая вершина х є Qk", для которой Г(х) Qk = 0 то безразлично, какая из вершин, принадлежащих Qk , используется для расширения Sk и это справедливо при любом числе дальнейших ветвлений; вершина х не может быть удалена из QH на любом следующем шаге р к. Таким образом, условие
Разработка простого генетического алгоритма выделения экстремальных подмножеств
Для решения задачи выделения экстремальных подмножеств в графе разработано два варианта простого генетического алгоритма (ПГА1 и ПГА2) отличающиеся друг от друга методикой кодирования и нахождения значений целевой функции, а также применяемыми генетическими операторами. Общим у этих алгоритмов является то, что оба имеют аналогичную структуру, которая соответствует определению простого генетического алгоритма.
Для ПГА1 разработана методика кодирования, когда каждое решение представляет собой бинарную хромосому длину N, где N - число вершин исследуемого графа G. Каждому гену соответствует определенная вершина графа. Вершины упорядочиваются, например, в порядке возрастания их номеров. То есть первому гену соответствует первая вершина графа, второму гену вторая вершина и т.д. Если значение гена равно 1, то данная вершина включается в экстремальное подмножество, если ноль - то вершина не включается в экстремальное подмножество. подмножество X = {хі, хз, Х5, хе}, так как гены 1, 3, 5, 6 рассматриваемой хромосомы - являются ненулевыми. Длина хромосомы свидетельствует о том, что исследуемый граф G имеет 7 вершин (N = 7).
Для ПГА2 предлагается следующая методика кодирования альтернативных решений. Длина хромосомы равна числу вершин исследуемого графа. Числовые значения разрядов хромосомы соответствуют номерам ф вершин графа. Начальная популяция формируется случайным образом, причем различные хромосомы отличаются друг от друга порядком следования вершин.
Для оценки качества полученных решений применяется следующая процедура. В хромосоме (строке) выбирается первая позиция, и затем данная числовая последовательность просматривается слева направо. На каждом шаге проверяется выполнение заданного условия. Так при построении независимых подмножеств таким условием является отсутствие общих ребер между рассматриваемыми вершинами. В результате выполнения данной процедуры будет сформировано одно экстремальное подмножество некоторой длины.
Следовательно, качество полученных решений определяется длиной соответствующих им подмножеств. При формировании на некотором шаге подмножества, аналогичного уже существующему, оно исключается из популяции.
Методика кодирования решений предложенная для алгоритма ПГА1, обеспечивает гомологичность хромосом. Следовательно, к ним можно применять стандартные генетические операторы кроссинговера и мутации. Другое дело, что не все полученные решения будут являться доминирующими подмножествами, но для этого предусмотрена специальная процедура проверки условия доминирования.
В данном алгоритме использованы следующие генетические операторы. Стандартный одноточечный оператор кроссинговера. При
скрещивании случайно выбирается точка разрыва внутри хромосомы. Затем происходит обмен участками родительских хромосом расположенных слева и справа от точки разрыва, хромосом часть первого родителя, расположенная левее точки скрещивания, и часть второго родителя, расположенная правее точки скрещивания, копируются в первого потомка. Второй потомок формируется из правой части первого родителя и левой части второго родителя. Пример работы стандартного одноточечного ОК показан на рис. 3.8.
Универсальный оператор кроссинговера. Случайно или целенаправленно генерируется маска, по которой производится скрещивание. В маске для каждого гена задается число 0 или 1. Ноль подразумевает, что первому потомку достанется ген 1-го родителя, а второму - ген 2-го родителя. Для значения 1 в маске применяется обратный порядок обмена
Разработка структуры простого генетического алгоритма построения экстремальных подмножеств
Структура хромосом и принципы их кодирования и декодирования оказывают наибольшее влияние на эффективность генетического поиска. Разработка этой части генетического алгоритма связана в первую очередь с учетом специфики рассматриваемой проблемы. Подходы к кодированию хромосом определяют тип и трудоемкость применяемых к ним генетических операторов и также трудоемкость операций кодирования и декодирования.
Рассмотрим структуру хромосомы, используемую в рассматриваемом здесь алгоритме. Пусть задан граф G = (X, U). Необходимо найти максимальное независимое подмножество цгтах, число внутренней устойчивости г((7) = у/тах и наибольшее семейство независимых подмножеств У . Воспользуемся формулами (1.2.1) и (1.3.1) для теоретической оценки нижней 1тт и верхней 1тах границы числа внутренней устойчивости. Тогда хромосома будет иметь вид: Число генов в хромосоме N равно верхней оценке числа внутренней устойчивости 1тах. Значением гена является номер вершины в графе G. Заполненная часть хромосомы / представляет собой внутренне устойчивое или независимое подмножество, / є [lmim lmax]. Т.к. / может быть меньше N, то оставшаяся часть хромосомы заполняется нулями. Так как параметр / определяет длину внутренне устойчивого или независимого подмножества, то его целесообразно использовать для, оценки качества хромосомы. Тогда целевой функцией (фитнессом) хромосомы, а также критерием оптимизации будет являться /, а целью оптимизации -максимизация функции, т.е. Начальная популяция хромосом представляет собой множество внутренне устойчивых подмножеств, некоторые из которых могут быть и независимыми. Создание популяции можно описать следующим образом.
Сначала случайным образом формируется множество вершин, мощность которого выбирается случайно в пределах [1тт, 1тах]. Проверяется, является ли это множество внутренне устойчивым, если да, то хромосома записывается в начальную популяцию, если нет, то формируется новое множество вершин. Процесс продолжается до тех пор, пока не будет сформировано заданное число хромосом.
Начальная популяция может быть представлена следующим набором хромосом (1тт = 3,1тах = Важную роль при разработке генетического алгоритма играет правильный выбор генетических операторов. Они, с одной стороны, должны обеспечивать разнообразие популяции и препятствовать преждевременной сходимости, а с другой, не должны давать нелегальных решении. В работе использовались следующие генетические операторы: модифицированный упорядочивающий одноточечный оператор кроссинговера модифицированный оператор мутации элитный и равновероятный операторы отбора Рассмотрим их подробнее.
Так как в данной работе используются негомологичные хромосомы, то использование стандартных (одноточечный, двухточечный и т.д.) операторов кроссинговера невозможно, в силу того, что они дают большое число нелегальных решений. Поэтому была использована модификация упорядочивающего одноточечного кроссинговера, разработанного Д. Дэвисом в 1985 году для негомологичных числовых хромосом. Приведём схему работы оператора кроссинговера.
Из двух родительских хромосом выбирается та, длина заполненной части ( /; ) которой меньше. Случайным образом выбирается точка скрещивания в пределах [1, //]. Далее в хромосому первого потомка копируется хромосома первого родителя до точки кроссинговера, а гены потомка, расположенные правее точки скрещивания записываются в последовательности соответствующей второму родителю. При этом второй родитель просматривается от начала до конца, слева направо, и элементы, которых не хватает в потомке, добавляются, начиная от точки кроссинговера, по порядку. Для создания второго потомка применяется обратный порядок действий.
Очень важным в генетических алгоритмах является оператор мутации, так как он порождает новый генетический материал, который может быть как плохим, так и хорошим, что способствует преодолению барьеров локальных оптимумов.
Рассмотрим схему работы модифицированного оператора мутации, используемого в данной работе.
Пусть заполненная часть хромосомы-родителя равна /;, а нулевая 10. Случайным образом сформируем множество вершин А, не принадлежащих родительской хромосоме, Л є [1, /о]. Допишем эти вершины в хромосому. Зададим случайное число п, п є [0, //], и удалим п генов от начала хромосомы. Полученное множество вершин записывается в хромосому потомка
Простой генетический алгоритм нахождения экстремальных подмножеств
Это означает, что данной хромосоме соответствует доминирующее подмножество X = {хі, хз, Х5, хе}, так как гены 1, 3, 5, 6 рассматриваемой хромосомы - являются ненулевыми. Длина хромосомы свидетельствует о том, что исследуемый граф G имеет 7 вершин (N = 7).
Для ПГА2 предлагается следующая методика кодирования альтернативных решений. Длина хромосомы равна числу вершин исследуемого графа. Числовые значения разрядов хромосомы соответствуют номерам ф вершин графа. Начальная популяция формируется случайным образом, причем различные хромосомы отличаются друг от друга порядком следования вершин.
Для оценки качества полученных решений применяется следующая процедура. В хромосоме (строке) выбирается первая позиция, и затем данная числовая последовательность просматривается слева направо. На каждом шаге проверяется выполнение заданного условия. Так при построении независимых подмножеств таким условием является отсутствие общих ребер между рассматриваемыми вершинами. В результате выполнения данной процедуры будет сформировано одно экстремальное подмножество некоторой длины. Следовательно, качество полученных решений определяется длиной соответствующих им подмножеств. При формировании на некотором шаге подмножества, аналогичного уже существующему, оно исключается из популяции.
Методика кодирования решений предложенная для алгоритма ПГА1, обеспечивает гомологичность хромосом. Следовательно, к ним можно применять стандартные генетические операторы кроссинговера и мутации. Другое дело, что не все полученные решения будут являться доминирующими подмножествами, но для этого предусмотрена специальная процедура проверки условия доминирования.
В данном алгоритме использованы следующие генетические операторы. Стандартный одноточечный оператор кроссинговера. При скрещивании случайно выбирается точка разрыва внутри хромосомы. Затем происходит обмен участками родительских хромосом расположенных слева и справа от точки разрыва, хромосом часть первого родителя, расположенная левее точки скрещивания, и часть второго родителя, расположенная правее точки скрещивания, копируются в первого потомка. Второй потомок формируется из правой части первого родителя и левой части второго родителя. Пример работы стандартного одноточечного ОК показан на рис. 3.8.
Универсальный оператор кроссинговера. Случайно или целенаправленно генерируется маска, по которой производится скрещивание. В маске для каждого гена задается число 0 или 1. Ноль подразумевает, что первому потомку достанется ген 1-го родителя, а второму - ген 2-го родителя. Для значения 1 в маске применяется обратный порядок обмена (Рис. 3.9).Инверсия. Случайным образом в хромосоме выбираются две точки разрыва, после чего гены, расположенные между выбранными точками инвертируются.
В алгоритме ПГА2 использовался упорядочивающий оператор кроссинговера. Пример выполнения упорядочивающего оператора кроссинговера показан на рис. ЗЛО. В процессе выполнения данного оператора кроссинговера случайным образом выбирается точка разрыва. Левые от точки разрыва части копируются в новые хромосомы без изменений, а правые переупорядочиваются таким образом, чтобы новые хромосомы не содержали повторяющихся вершин.
В алгоритме также использован оператор мутации на основе мутации обмена. При этом из популяции случайным методом выбирается хромосома, к которой будет применен оператор мутации. После этого в хромосоме случайным образом выбираются две позиции, и производится их перестановка между собой. Пример выполнения оператора мутации показан на рис. 3.11.
Очевидно, что в данном алгоритме для выбора хромосом используется случайная селекция. Может также применяться модификация данного алгоритма. В этом случае после создания начальной популяции решений и выделения в них экстремальных подмножеств производится переупорядочение всех строковых последовательностей (хромосом) следующим образом. В начале записывается последовательность чисел, соответствующая сформированному на базе данной хромосомы подмножеству, а затем оставшиеся вершины.
Тогда точка кроссинговера выбирается случайно среди первых Lp позиций, причем величина Lp соответствует мощности сформированного экстремального подмножества. Например для случайного графа Gi = (X, U) (рис. 3.12) можно сгенерировать некоторое решение
