Содержание к диссертации
Введение
ГЛАВА 1. Состояние проблемы структурного синтеза в проектировании и логистике 12
1.1. Задачи структурного синтеза проектных решений 12
1.1.1. Задачи пространственного синтеза 13
1.1.2. Задачи пространственно-временного синтеза 23
1.2. Подходы к решению задач структурного синтеза проектных решений
26
1.2.1. Интеллектуальные системы и методы структурного синтеза 26
1.2.2. Методы дискретного математического программирования 31
1.3. Эволюционные методы 37
1.3.1. Базовый генетический алгоритм 37
1.3.2. Метод «поведения толпы» 43
1.3.3. Метод «колонии муравьев» 45
1.4. Тестовые задачи 47
Выводы 52
ГЛАВА 2. Генетические алгоритмы 53
2.1. Разновидности генетических операторов 53
2.2. Многоточечный и однородный кроссовер 60
2.3. Параллельные и гибридные генетические методы 61
2.4. Метод комбинирования эвристик 63
Выводы 65
ГЛАВА 3. Новые генетические методы 66
3.1. Смешанный эволюционный метод 66
3.1.1. Обоснование предпочтительности многоточечного кроссовера 66
3.1.2. Варианты смешанного эволюционного метода 67
3.2. Метагенетический метод 69
3.3. Циклический генетический метод 77
Выводы 79
ГЛАВА 4. Экспериментальная оценка эффективности новых генетических методов 80
Программное обеспечение генетического поиска 80
4.2. Многоточечность и полигамность 81
4.2.1. Оценка эффективности смешанного эволюционного метода 81
4.2.2. Оценка эффективности метода комбинирования эвристик 87
4.3. Адаптивность 90
4.4. Предотвращение преждевременной стагнации 108
Выводы 109
Выводы и заключение 111
Список литературы
- Задачи пространственного синтеза
- Многоточечный и однородный кроссовер
- Варианты смешанного эволюционного метода
- Многоточечность и полигамность
Введение к работе
В настоящее время весьма актуальными являются проблемы создания и
разработки новых высокоточных и быстрых методов для синтеза проектных
решений[18,23]. Маршруты проектирования сложных изделий в САПР
машиностроения и радиоэлектроники состоят из чередующихся процедур
синтеза и анализа проектных решений. В современных САПР
преимущественно развиты математическое и программное обеспечения
процедур анализа. Принятие проектных решений охватывает широкий круг
задач, однако эти задачи трудно формализуемы. Но и в случае формализации
их практическая реализация не всегда очевидна. Для многих формализуемых
задач структурного синтеза применение известных математических
методов не представляется возможным вследствие проблем NP-полноты и большого размера задач. Именно по этой причине структурный синтез обычно выполняется в интерактивном режиме при определяющей роли человека. В первую очередь, это относится к структурному синтезу, при котором выбираются принципиальные конструктивные и схемные решения. Однако по мере усложнения проектируемых изделий возможности человека в решении задач сужаются, растут затраты времени на проектирование, зачастую принимаются решения, далекие от оптимальных. Поэтому поиск новых эффективных методов структурного синтеза проектных решений относится к актуальным проблемам развития математического обеспечения САПР.
Методы локальной оптимизации (Hill Climbing), моделирование отжига (Simulated Annealing) [55,56], генетические алгоритмы (Genetic Algorithms), [35,51,54], нейронные сети (Neural Network) [57,63,66] и поиск с запретами (Tabu Search)[47,48,49,50] - только часть стохастических алгоритмов, которые применяются при решении задач проектирования. Все
5 эти методы, за исключением генетических алгоритмов (ГА), в каждый
момент поиска рассматривают только одно решение, и оно неоднократно
улучшается во время работы алгоритма.
Генетические алгоритмы отличаются тем, что в процессе поиска рассматривается несколько решений параллельно. При оптимизации ГА также допускаются значительные и недетерминированные изменения (оператор мутации), что уменьшает вероятность «застревания» текущей точки в локальных экстремумах или на дне узких «оврагов». В ГА с помощью комбинирования двух проектных решений (оператор кроссовера), создается третье решение, что делает возможным попадание в новую область в пространстве поиска. Параллельно рассматривая подмножество альтернатив с мощностью N, генетические алгоритмы начинают поиск в нескольких точках одновременно, благодаря чему уменьшается вероятность попадания ГА в локальные оптимумы.
Генетические алгоритмы были предложены в 1975 г. профессором Джоном Холландом [54] в Мичиганском университете. Они получили широкое распространение благодаря профессору университета штата Иллинойс Дэйвиду Гольдбергу [51] и его студентам [35]. В дальнейшем генетические алгоритмы получили развитие в трудах: Э.Гудмана, Л.Дэйвиса, Д.Фогелья и многих других. Значительный вклад в развитие теории эволюционного моделирования и стохастической оптимизации внесли Курейчик В.В.[9,10,59], Курейчик В.М.[5,10,11,12], Батищев Д.И.[2], Мухачева А.С. [16], Де Янг[35,36], Букатова И.Л.[3], Растригин Л.А.[27], НоренковИЛ. [17,18,19,20,23].
Генетические алгоритмы являются моделями естественных процессов эволюции в виде вычислительных процедур. ГА использует два основных принципа теории эволюции - наследственность, то есть передача информации от одной генерации к другой, и конкуренция (выживает сильнейший), в результате чего слабые индивидуумы выбывают из популяции.
Основные преимущества ГА следующие
адаптируются и «обучаются» в течение своего исполнения; имеют параллельность внутренних процессов; применимы к задачам как с числовыми, так и предметными переменными, т.е. позволяют осуществлять поиск в неметризуемых пространствах параметров.
ГА применяются для решения сложных задач параметрической оптимизации и структурного синтеза, где математические модели имеют сложную структуру и использование стандартных методов нецелесообразно. В частности, они перспективны для решения задач синтеза расписаний, планирования работ и распределения ресурсов, синтеза топологии сетей различного назначения, маршрутизации транспортных средств, компоновки и размещения оборудования и др.
Эффективность применения ГА, оцениваемая, прежде всего, степенью приближения результатов решения к оптимальным значениям, не всегда оказывается удовлетворительной. Кроме того, ГА довольно трудоемки, что ограничивает сложность моделей, используемых для расчета целевых функций. Поэтому исследования, направленные на устранение указанных недостатков ГА, сохраняют свою актуальность.
Для повышения эффективности ГА разрабатываются новые алгоритмы выполнения генетических операторов. Разработан ряд алгоритмов кроссовера, селекции и мутации [21,32,36,40,64,65,68].
Другой подход к повышению эффективности ГА основан на применении метода комбинирования эвристик (НСМ) [17], в котором гены представляют не сами искомые проектные параметры, а некоторые эвристические алгоритмы их выбора. Эффективность НСМ зависит от правильности выбора совокупности используемых при поиске эвристических правил.
К сожалению, априорный выбор наиболее эффективных алгоритмов выполнения генетических операторов и эвристических правил, как правило,
7 невозможен. Поэтому на практике перед собственно решением задачи
выполняют пробные решения с варьированием конкурирующих алгоритмов
и совокупностей эвристик. Однако такие предварительные решения
существенно увеличивают и без того большие затраты машинного времени
на получение искомых результатов и потому возможны лишь в отдельных
случаях.
Таким образом, целью диссертационной работы является разработка эволюционных методов решения задач структурного синтеза в проектировании и логистике.
В работе показано, что достижение поставленной цели требует решения следующих основных задач:
Анализ существующих подходов к решению задач структурного синтеза в проектировании и логистике.
Определение параметров, управление которыми позволяет повысить эффективность ГА.
Разработка новых генетических методов структурного синтеза проектных решений.
Экспериментальная оценка эффективности разработанных методов.
Научная значимость заключается в разработке и обосновании эффективности новых генетических методов структурного синтеза и дискретной оптимизации для систем автоматизированного проектирования и логистической поддержки промышленных изделий.
В процессе решения поставленных задач используются методы оптимизации, методы эволюционных вычислений и генетические алгоритмы.
Диссертация включает введение, четыре главы с выводами, заключение, список литературы и приложения.
В первой главе исследованы проблемы структурного синтеза в проектировании и логистике. В САПР используют две группы методов для решения задач структурного синтеза - экспертные методы и методы
8 дискретной оптимизации. Использование экспертных систем не получило
широкого распространения в силу трудностей создания баз знаний для
представительных классов проектируемых объектов. В большинстве случаев
задачи структурного синтеза стараются свести к задачам дискретного
математического программирования.
Рассмотрены задачи структурного синтеза проектных решений - задачи пространственного синтеза и задачи пространственно-временного синтеза и подходы к их решению. Критериями эффективности методов структурного синтеза являются точность получаемых решений, понимаемая как степень приближения найденного решения к экстремальному, и затраты вычислительных ресурсов, основное значение в которых имеют затраты машинного времени.
Тщательному анализу подвергнуты эволюционные методы: базовый генетический алгоритм, метод «поведения толпы» и метод «колонии муравьев». Среди методов дискретного математического программирования для решения сложных задач автоматизированного проектирования и логистической поддержки наиболее перспективны генетические методы эволюционных вычислений в силу применимости к задачам, как с числовыми, так и предметными переменными. Однако базовый генетический алгоритм при решении ряда задач проектирования и логистики часто оказывается неэффективным.
Показана актуальность проблемы поиска путей и разработки новых генетических методов, обеспечивающих получение проектных решений с приемлемыми значениями критериев эффективности. Предложены тестовые задачи, используемые для проверки эффективности разрабатываемых методов.
Во второй главе рассмотрены разновидности генетических операторов. В практических алгоритмах существует и используется большое число вариантов реализации генетических операторов. Эффективность применения того или иного варианта зависит от характера задачи и часто от ситуации,
9 складывающейся во время решения задачи. Следовательно, априорный выбор вариантов случайным образом влияет на эффективность поиска и одним из направлений повышения эффективности ГА является разработка адаптивных генетических методов.
Рассмотрены многоточечный и однородный кроссовер. Кроссовер -генетический оператор, в значительной мере влияющий на эффективность поиска. Исследования ряда авторов показали, что многоточечный кроссовер более эффективен по сравнению с одноточечным кроссовером. Причины большей эффективности многоточечного кроссовера и определение оптимальных значений числа разрывов хромосом при многоточечном кроссовере требуют дальнейших исследований.
Рассмотрены параллельные и гибридные генетические методы, а также метод комбинирования эвристик. Применение единственной конкретной эвристики на всех шагах поиска малоэффективно. Перспективно использование различных эвристик на разных шагах синтеза решений. Метод комбинирования эвристик позволяет генерировать проектные решения со значительно лучшими оценками целевой функции.
В третьей главе рассмотрены предлагаемые в диссертации новые генетические методы - смешанный эволюционный метод, метагенетический метод и циклический генетический метод. Смешанный эволюционный метод основан на использовании многоточечного кроссовера и селекции с участием нескольких родительских хромосом. Предпочтительность многоточечного кроссовера доказана благодаря учету при выводе теоремы схем фактов не только разрушения схем из-за кроссовера и мутаций, но и генерации новых полезных схем при многоточечном кроссовере.
Автоматический выбор значений параметров и типов генетических операторов в процессе генетического поиска реализован в метагенетическом алгоритме. Как и для определения значений управляемых параметров исходной оптимизационной задачи, для выбора значений параметров и типов операторов использованы генетические алгоритмы.
Предотвращение преждевременной стагнации при генетическом поиске возможно, если при макромутациях обеспечить, во-первых, сохранение накопленного генного материала, во-вторых, соизмеримость начальной полезности всех хромосом популяции. Эти условия соблюдены в разработанном циклическом генетическом методе.
В четвертой главе проведена экспериментальная оценка
эффективности новых генетических методов. Полученные результаты позволили сделать ряд выводов.
Во-первых, параметры многоточечного кроссовера влияют на эффективность поиска. Однородный и одноточечный кроссоверы не относятся к лучшим вариантам ГА. Смешанный генетический метод с многими родителями превосходит по эффективности классический ГА, в котором при кроссовере происходит скрещивание генов только двух родителей.
Во-вторых, подтверждено, что метод комбинирования эвристик превосходит по эффективности генетический метод с обычным кодированием хромосом.
В-третьих, показано, что эффективность разработанного метагенетического алгоритма, в котором автоматически настраиваются параметры алгоритма и выбираются вероятности применения эвристик, превосходит эффективность неадаптивных методов.
В-четвертых, подтверждено, что дополнительное повышение точности результатов решения задачи можно достигнуть с помощью предложенного циклического генетического метода (ЦГМ).
Практическая ценность работы состоит в том, что разработанная автором программа, реализующая предложенные генетические методы, была использована не только для решения не только тестовых задач, но и для практических задач проектирования. Решена задача размещения макроблоков для СБИС. Разработаны и решены задачи размещения и трассировки соединений СБИС, основанные на одновременном генетическом
поиске оптимальных значений как параметров исходной задачи, так и параметров самого алгоритма.
Результаты диссертационной работы внедрены в ЗАО «СИНОПСИС АРМЕНИЯ», в КБ ИГАС «Волна» (г. Москва) и в учебный процесс МГТУ им. Н.Э. Баумана.
Основные результаты диссертационной работы были доложены на IX Молодежной научно-технической конференции «Наукоемкие технологии и интеллектуальные системы - 2007» (ИУ-4,МГТУ им. Н.Э.Баумана, М.2007), IV Международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (Россия, Коломна, 2007) и на других научно-технических и научно-практических конференциях.
Задачи пространственного синтеза
Компоновка оборудования [24,29]. Компоновка заключается в распределении п заданных элементов (конструктивов) в т блоках.
Элементами могут быть микросхемы, распределяемые между типовыми элементами замены (ТЭЗами), приборы, размещаемые в отсеках корабля, работы, назначаемые на выполнение конкретным исполнителям и др. Типичными ограничениями при компоновке является ограничение на вместимость блоков, число межблочных связей, несовместимость компонентов отдельных типов друг с другом и потому необходимость их распределения в разные блоки и др.
Например, при проектировании электронных устройств основной задачей компоновки является разрезание большой схемы (структурной, функциональной, логической, принципиальной) на части (микросборки, ТЭЗы, узлы и т. п.), Разрезание выполняется с минимизацией числа связей между частями.
Разновидностями компоновки в радиоэлектронике являются также задачи: - типизации - разбиения схемы на конструктивные элементы (или топологические компоненты в микросхеме) различных типов и определение минимальной номенклатуры их; - покрытия - преобразования исходной схемы в схему соединений элементов (модулей), номенклатура которых задана.
Разрезание, типизация, покрытие могут решаться автономно или комплексно. Кроме минимизации числа межмодульных связей, используются и другие критерии, например, общее число модулей, суммарная площадь, занимаемая элементами и соединениями, электромагнитная совместимость элементов в модуле, параметры теплообмена между элементами в узле.
К типу задач компоновки относится также ряд других задач. По своей постановке к ним близка актуальная задача распределения частот между сотами в системах мобильной связи [26,70]. Здесь компонентами являются соты, а блоками - диапазоны частот. Задано расположение сот и требуется обеспечить максимальное удаление сот с одинаковыми частотными диапазонами друг от друга. Другим примером этого типа задач является известная задача о назначениях. Размещение компонентов [29,31]. После компоновки обычно решается задачи размещения компонентов в блоках. Результаты размещения определяют степени удаленности компонентов друг от друга и, следовательно, влияют на время передачи продукции или информации между компонентами. Например, в микроэлектронике от результатов размещения существенно зависят возможности трассировки и, следовательно, быстродействие СБИС, так как основные задержки сигналов приходятся именно на соединения.
В САПР находят применение следующие критерии размещения: - суммарная длина всех соединений; - расстояние между элементами, соединенными наибольшим числом связей; - длина наиболее длинных связей; - число межслойных переходов; - параметры паразитных связей между элементами и проводниками и Др.
Синтез топологии сети соединений. Различают задачи с заданной схемой соединений и с заданным трафиком между компонентами сети.
Первый тип характерен для проектирования в радиоэлектронике [29], где после размещения или одновременно с размещением решается задача трассировки соединений. При этом заданное множество соединений надо проложить в коммутационном пространстве СБИС или печатной платы.
Второй тип задач топологического синтеза характерен для проектирования транспортных или информационных сетей [39]. В этих приложениях задается интенсивность потока некоторой субстанции между узлами сети и необходимо выбрать систему трасс для передачи субстанции, минимизируя затраты на создание или эксплуатацию транспортной системы при обеспечении трафика заданного объема.
Многоточечный и однородный кроссовер
Генетические алгоритмы могут быть распараллелены, по меньшей мере, двумя способами. Первый способ относится к параллельному выполнению операций внутреннего цикла базового ГА. Очевидно, что в этом случае имитируется эволюция одной и той же популяции хромосом. Реализация алгоритма целесообразна на компьютере с числом процессоров, не меньшем размера ПОПУЛЯЦИИ Npop.
Второй способ заключается [52] в имитации эволюции нескольких популяций, периодически обменивающихся между собой частью своих генотипов. Разновидности этого способа определяются расписанием межпопуляционных обменов. В расписании должны быть указаны следующие сведения: а) период автономной эволюции, измеряемый числом смен поколений в популяциях между обменами; б) матрица В обменов, элемент by которой равен 1, если генный материал передается от популяции / к популяции у, иначе Ьу=0 ; в) содержание обменов, т.е. список хромосом, передаваемых при обмене от популяции / к популяции/ Например, возможен круговой обмен (bjf=l, только если у=/+1, за исключением популяции с максимальным номером /, для которой Ь\/=\). Генетический алгоритм с межпопуляционными обменами по второму способу находит применение и на однопроцессорных компьютерах.
Если популяции обмениваются своими лучшими представителями, то обычно после нескольких обменов во всех популяциях начинают доминировать генотипы лучшего из поколений, т.е. происходит выравнивание качества генофонда во всех популяциях на уровне лучшей из популяций. Другими словами, результаты применения параллельного ГА приблизительно совпадают с результатами выполнения нескольких попыток решения задачи обычным (непараллельным) способом.
Гибридным называют алгоритм, в котором для поиска экстремума используются идеи двух или более методов оптимизации. Типичным примером гибридного алгоритма является генетический алгоритм с улучшением каждого генерируемого потомка с помощью метода локального поиска. Локальный поиск выполняется посредством макромутаций. Размер макромутаций, т.е. число мутируемых генов, определяет окрестность текущей точки поиска, в которой ищется лучшая точка. Число безуспешных попыток найти такую точку ограничено величиной к. Если найдена точка с лучшим значением функции полезности, то происходит переход в эту точку и вновь допускается поиск с числом попыток, равным к.
Как показали результаты экспериментов, гибридный алгоритмы не имеют заметных преимуществ по точности получаемых решений перед негибридными ГА, в то же время затраты времени на решение могут существенно возрасти.
При постановке задач структурного синтеза с помощью эволюционных методов необходимо прежде всего выбрать способ кодирования проектных решений, т.е. способ отображения в хромосоме оптимизируемых параметров.
Непосредственное представление структурных параметров (например, в случае задачи JSSP порядковых номеров работ и номеров используемых машин), во-первых, порождает проблему появления недопустимых хромосом и вытекающую из этого необходимость использования операторов корректировки, во-вторых, излишне удлиняет хромосому, что отрицательно сказывается на эффективности поиска экстремума. Поэтому целесообразно использовать идею отображения в хромосоме информации о синтезируемом объекте в неявной форме, что выполнено в эволюционном методе комбинирования эвристик (НСМ - Heuristics Combination Method) [17]. Гены в этом методе представляют не сами структурные параметры, а указывают на способ (метод) определения этих параметров, что дает основание называть НСМ также мультиметодным ГА. Так, в случае синтеза расписаний гены должны представлять не номера работ или обслуживающих аппаратов, а правила генерации очередного пункта расписания.
В НСМ исходная задача трансформируется в задачу поиска и использования оптимальной последовательности правил (другими словами, оптимальной последовательности эвристик), используемых в процессе поиска экстремума. Последовательность применения этих правил можно рассматривать как программу структурного синтеза и, с этой точки зрения, НСМ можно интерпретировать как разновидность генетического программирования.
Варианты смешанного эволюционного метода
Специфика ММЕМ отражена главным образом в блоке формирования хромосом для следующего поколения. Параметрами, характеризующими особенности применяемого метода, являются длина фрагментов, на которые разделяются родительские хромосомы, параметр у, указывающий наличие или отсутствие кроссовера внутри фрагментов (у {да, нет}), число хромосом-родителей у каждой формируемой хромосомы. В зависимости от значений этих параметров возможны следующие варианты процедуры формирования хромосом-потомков:
1. Две родительские хромосомы А и В разделяются на фрагменты одинаковой длины L, потомки образуются из чередующихся фрагментов родителей, как показано на рис.3.1, где L=5; наверху рисунка отмечено, из какой хромосомы (А или В) взят фрагмент. Предполагается, что для каждого потомка значения L выбираются случайно из некоторого множества. А А В Фрагменты" Структура хромосомы в первом варианте формирования потомка
2. Как и в предыдущем варианте, используются два родителя, но дополнительно вводится операция кроссовера внутри каждого фрагмента, причем случайно выбираемые точки разрыва отделяют участки хромосом, взятые от разных родителей (рис.3.2). Точки разрыва хромосом
3. Вариант, аналогичный варианту 1, но в формировании потомка может участвовать более двух родителей, т.е. потомок формируется из фрагментов хромосом, случайно выбираемых в соответствии с их вероятностями qj, рассчитанными в процедуре «Определение перспективности членов популяции».
4. Вариант, аналогичный вариантам 2 и 3, т.е. характеризуемый наличием кроссовера внутри фрагментов и полигамностью - использованием нескольких родительских хромосом. Число вариантов процедуры формирования хромосом можно увеличить, применяя разные множества, из которых выбираются значения параметра L. Частными случаями предложенной процедуры формирования потомков являются реализации эволюционных методов ГА, АСО и PSO.
Вариант 2 с длиной L, равной длине всей хромосомы, соответствует одноточечному генетическому алгоритму. Тот же вариант, но при 1=1, близок к GA с однородным кроссовером. Методу АСО соответствует вариант 3 при L=\. Метод PSO имеет место, если 1=1, а в качестве родителей при формировании у-го потомка преимущественно используются две хромосомы: глобально рекордная (с лучшим значением целевой функции среди всех хромосом популяции) и локально рекордная (с лучшим значением целевой функции средиу-х членов всех предыдущих поколений).
Эффективность применения ГА, оцениваемая прежде всего степенью приближения результатов решения к оптимальным значениям, не всегда оказывается удовлетворительной. Кроме того, ГА довольно трудоемки, что ограничивает сложность моделей, используемых для расчета целевых функций. Поэтому исследования, направленные на устранение указанных недостатков ГА, сохраняют свою актуальность.
Обычно повышение эффективности стремятся достичь на основе применения новых алгоритмов выполнения генетических операторов. Разработан ряд алгоритмов кроссовера, селекции и мутации. Их подробное рассмотрение выполнено выше.
Первые исследования по определению оптимальной конфигурации ГА были проведены Де Янгом[35]. Для этого он определил тестовые функции и эмпирически определил оптимальные параметры для ГА (п. 1.4).
Данная конфигурация считается "стандартом" и применяется в различных исследованиях. Еще один подход для определения параметров был предложен в работе [37], но данный алгоритм требует большой размер популяции. В других работах [60,64,71] была предложена идея использования многопопуляционных генетических алгоритмов, где каждая отдельная популяция использует свой набор параметров.
Другой подход к повышению эффективности ГА основан на применении метода комбинирования эвристик (НСМ) [17], в котором гены представляют не сами искомые проектные параметры, а некоторые эвристические алгоритмы их выбора. Эффективность НСМ зависит от правильности выбора совокупности используемых при поиске эвристических правил.
К сожалению, априорный выбор наиболее эффективных алгоритмов выполнения генетических операторов и эвристических правил, как правило, невозможен. Поэтому на практике перед собственно решением задачи выполняют пробные решения с варьированием конкурирующих алгоритмов и совокупностей эвристик. Однако такие предварительные решения существенно увеличивают и без того большие затраты машинного времени на получение искомых результатов и потому возможны лишь в отдельных случаях.
Многоточечность и полигамность
В этом параграфе приведены результаты экспериментов по оценке эффективности многоточечности и полигамности, составляющими основу предложенного смешанного эволюционного метода, в сравнении с известными генетическими методами. В качестве тестовых использовались задачи, рассмотренные в главе 1. Было принято следующее лаконичное обозначение методов: имя метода - число точек разрыва хромосом при кроссовере (число родителей). Если именем одноточечного базового ГА является CGA (Classic Genetic Algorithm), то его обозначение будет CGA-1(2). В смешанном эволюционном методе фигурируют т точек разрыва (multipoint crossover) и т родителей (multi parents), поэтому ММЕМ будет обозначаться CGA-w(w), если гены непосредственно являются искомыми параметрами задачи, или HCM-m(m), если гены обозначают номера эвристик для расчета искомых параметров.
Выполненное исследование потенциала рекомбинации позволяет сделать вывод о наличии оптимальных значений длин фрагментов L, на которые разделяются хромосомы при кроссовере. Для подтверждения этого вывода было проведено экспериментальное исследование зависимости функций полезности от L на примерах нескольких задач.
Одной из наиболее сложных для решения NP-трудных задач является многостадийная задача синтеза расписаний (JSSP). В этой задаче при применении НСМ используются эвристики, состоящие из правил двух групп. Правило первой группы служит для выбора очередной работы, назначаемой на исполнение. Правило второй группы содержит алгоритм выбора машины для этой работы. Два основных использованных правила первой группы: выбирается работа с наименьшим предельным временем выполнения Т(; правило «первым пришел - первым обслужен» (FIFO). Правила второй группы: выбирается наиболее производительная машина; выбирается машина с наименьшей ценой обслуживания.
Сочетание правил двух групп дает четыре эвристики. Ранее отмечено, что снижение эффективности генетического поиска происходит из-за явления преждевременной стагнации. Это явление исследовалось на применении методов НСМ -1(2) и НСМ -20(/я) к задаче синтеза расписаний со следующими исходными данными число стадий обслуживания работ q-4 стадии, число работ л=105, число машин т-15. Результаты двух вариантов решения задачи при применении каждого из сравниваемых методов приведены в табл.4.1, где JV - число разрывов хромосом при кроссовере (отметим, что длина хромосомы в данной задаче равна q n=420), Evals - число оценок целевой функции. Результаты показывают, что при многоточечном кроссовере вероятность преждевременной стагнации уменьшается, соответственно удается заметно ближе подойти к точке экстремума.
Назовем коэффициентом разнообразия долю генов, имеющих неодинаковые значения в хромосомах родителей в очередном акте кроссовера. На рис. 4.1 представлена зависимость коэффициента разнообразия г от номера поколения. На рисунке светлыми точками обозначены значения г, полученные в некоторых случайно выбранных актах кроссовера при применении смешанного метода НСМ-20(от), а темными точками - аналогичные значения, полученные при применении одноточечного кроссовера НСМ-1 (2). Рисунок иллюстрирует заметно меньшую предрасположенность ММЕМ к ранней стагнации
В предыдущей главе были приведены теоретические обоснования наличия оптимальных значений длин фрагментов L в смешанном эволюционном методе. Для подтверждения теоретических результатов были проведены эксперименты по определению оптимальных значений L.
На рис.4.2 представлены результаты решения задачи синтеза многостадийных расписаний с 4 стадиями, 200 работами и 15 машинами с помощью метода НСМ-/и(т). Точки соответствуют отдельным вариантам решения, кривая отображает усредненную зависимость целевой функции от размера фрагмента L.
Полученные результаты позволяют сделать вывод: длина фрагментов L влияет на эффективность поиска. Для HCM-m(m) в задаче JSSP оптимальные значения L находятся в диапазоне {5, 40} при общей длине хромосомы,
