Основной принцип работы генетических алгоритмов (2006, 176с., MET0008-05)

В генетических алгоритмах (ГА) за основу берутся биологические процессы эволюции (рис. 27).

Рис. 27. Основной принцип работы генетических алгоритмов

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

Рассмотрим основные фазы ГА решения задач оперативно-календарного планирования.

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

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

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

Популяция. При создании популяции учитываются четыре аспекта: величина, структура, схема замещения и начальная популяция.

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

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

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

Оценка (фитнес-функция). Расчет фитнес-функции заключается в трансформации генотипа в фенотип с последующим расчетом значения целевой функции из фенотипа. При декодировании генотипа происходит «чтение» хромосомы в соответствии с принципом кодирования. Работы переносятся на диаграмму Ганта к наиболее раннему сроку. После того как все работы перенесены на диаграмму Ганта, рассчитываются целевые критерии и фитнес-функция. В данном разделе рассмотрены лишь общие положения ГА. Более подробная информация содержится в других работах [58, 82, 86, 89, 148].

Источник: Иванов Д. А. Логистика. Стратегическая кооперация / Дмитрий Иванов. — М.: Вершина, 2006. – C. 119-122 (176 с.)