Генетические алгоритмы и их практическое применение

   группа  исследователей шла по пути  применения в генетических алгоритмах

   отличных  от двоичных алфавитов для  решения частных прикладных задач.  Одной

   из таких  задач является нахождение решений,  представленных в форме

   вещественных  чисел, что называется не иначе  как «поисковая оптимизация в

   непрерывных  пространствах». Возникла следующая  идея: решение в хромосоме

   представлять  напрямую в виде набора вещественных  чисел. Естественно, что

   потребовались  специальные реализации биологических операторов. Такой тип

   генетического  алгоритма получил название непрерывного  генетического

   алгоритма  (RGA, или real-coded genetic algorithm), или генетического

   алгоритма  с вещественным кодированием.

 

   Первоначально непрерывные гены стали использоваться в специфических

   приложениях  (например, хемометрика, оптимальный  подбор параметров

   операторов  стандартных генетических алгоритмов  и др.). Позднее они

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

   пространствах  (работы исследователей Wright, Davis, Michalewicz, Eshelman,

   Herrera в  1991-1995 гг). Поскольку до 1991 теоретических  обоснований

   работы  непрерывных генетических алгоритмов  не существовало, использование

   этого  нового подвида было спорным; ученые, знакомые с фундаментальной

   теорией  эволюционных вычислений, в которой  было доказано превосходство

   двоичного  алфавита перед другими, критически  воспринимали успехи

   алгоритмов  с вещественным кодированием. После  того, как спустя некоторое

   время  теоретическое обоснование появилось,  непрерывные генетические

   алгоритмы  полностью вытеснили двоичные  хромосомы при поиске в непрерывных

   пространствах.

 

   Преимущества  и недостатки двоичного кодирования

 

   Прежде  чем излагать особенности математического аппарата непрерывных

   генетических  алгоритмов, остановимся на анализе  достоинств и недостатков

   двоичной  схем кодирования.

 

   Как известно, высокая эффективность отыскания  глобального минимума или

   максимума  генетическим алгоритмом с двоичным кодированием теоретически

   обоснована  в фундаментальной теореме генетических  алгоритмов («теореме о

   шаблоне»), доказанной Холландом. Ее суть  в том, что двоичный алфавит

   позволяет  обрабатывать максимальное количество  информации по сравнению с

   другими  схемами кодирования.

 

   Однако  двоичное представление хромосом  влечет за собой определенные

   трудности  при поиске в непрерывных пространствах  большой размерности, и

   когда  требуется высокая точность найденного  решения. В генетических

   алгоритмах  с двоичным кодированием для  преобразования генотипа в фенотип

   используется  специальный прием, основанный  на том, что весь интервал

   допустимых  значений признака объекта 0x01 graphic

   разбивается  на участки с требуемой точностью. Заданная точность p

   определяется  выражением

 

                                  0x01 graphic

 

   где N - количество разрядов для кодирования  битовой строки.

 

   Эта формула  показывает, что p сильно зависит  от N, т.е. точность

   представления  определяется количеством разрядов, используемых для

   кодирования  одной хромосомы. Поэтому при  увеличении N пространство поиска

   расширяется  и становится огромным.

 

   Известный  книжный пример: пусть для 100 переменных, изменяющихся в

   интервале  0x01 graphic

   , требуется  найти экстремум с точностью  до шестого знака после запятой.  В

   этом  случае при использовании генетических  алгоритмов с двоичным

   кодированием  длина строки составит 3000 элементов,  а пространство поиска -

   около  0x01 graphic

   хромосом.

 

   Эффективность  генетических алгоритмов с двоичным  кодированием в этом

   случае  будет невысокой. На первых  итерациях алгоритм потратит  много усилий

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

   хромосомы.  Но оптимальное значение на первых итерациях будет зависеть от

   старших  разрядов числа. Следовательно,  пока в процессе эволюции алгоритм

   не выйдет  на значение старшего разряда  в окрестности оптимума, операции  с

   младшими  разрядами окажутся бесполезными. С другой стороны, когда это

   произойдет, станут не нужны операции со  старшими разрядами - необходимо

   улучшать  точность решения поиском в  младших разрядах. Такое «идеальное»

   поведение  не обеспечивает семейство генетических  алгоритмов с двоичным

   кодированием, т.к. эти алгоритмы оперируют битовой строкой целиком, и на

   первых  же эпохах младшие разряды  чисел "застывают", принимая  случайное

   значение. В классических генетических  алгоритмах разработаны специальные

   приемы  по выходу из этой ситуации. Например, последовательный запуск

   ансамбля  генетических алгоритмов с постепенным  сужением пространства

   поиска.

 

   Есть  и другая проблема: при увеличении  длины битовой строки необходимо

   увеличивать  и численность популяции.

 

   Математический  аппарат непрерывных генетических алгоритмов

 

   Как уже  отмечалось, при работе с оптимизационными  задачами в непрерывных

   пространствах  вполне естественно представлять  гены напрямую вещественными

   числами.  В этом случае хромосома есть  вектор вещественных чисел. Их

   точность  будет определяться исключительно  разрядной сеткой той ЭВМ, на

   которой  реализуется real-coded алгоритм. Длина  хромосомы будет совпадать с

   длиной  вектора-решения оптимизационной  задачи, иначе говоря, каждый ген

   будет  отвечать за одну переменную. Генотип объекта становится идентичным

   его фенотипу.

 

   Вышесказанное  определяет список основных преимуществ  алгоритмов с

   непрерывными  генами:

 

    1. Использование  непрерывных генов делает возможным  поиск в больших

       пространствах (даже в неизвестных), что трудно делать в случае

       двоичных генов, когда увеличение  пространства поиска сокращает

       точность решения при неизменной  длине хромосомы.

 

    2. Одной  из важных черт непрерывных  генетических алгоритмов является  их

       способность к локальной настройке решений.

 

    3. Использование  непрерывных генетических алгоритмов  для представления

       решений удобно, поскольку близко  к постановке большинства прикладных

       задач. Кроме того, отсутствие  операций кодирования/декодирования,

       которые необходимы в генетических  алгоритмах с двоичным кодированием,

       повышает скорость работы алгоритма.

 

   Как известно, появление новых особей в популяции  канонического

   генетического  алгоритма обеспечивают несколько  биологических операторов:

   отбор,  скрещивание и мутация. В качестве  операторов отбора особей в

   родительскую  пару здесь подходят любые  известные из двоичных генетических

   алгоритмов: рулетка, турнирный, случайный.  Однако операторы скрещивания  и

   мутации не годятся: в классических реализациях они работают с битовыми

   строками. Нужны собственные реализации, учитывающие  специфику real-coded

   алгоритмов.

 

   Оператор  скрещивания непрерывного генетического  алгоритма, или кроссовер,

   порождает  одного или нескольких потомков от двух хромосом. Собственно

   говоря, требуется из двух векторов  вещественных чисел получить  новые

   векторы  по каким-либо законам. Большинство  real-coded алгоритмов

   генерируют  новые векторы в окрестности  родительских пар. Для начала

   рассмотрим  простые и популярные кроссоверы.

 

   Пусть 0x01 graphic

   и 0x01 graphic

   - две хромосомы, выбранные оператором селекции для скрещивания. После

   формулы  для некоторых кроссоверов приводится  рисунок - геометрическая

   интерпретация его работы. Предполагается, что 0x01 graphic

   и 0x01 graphic

   .

 

     * Плоский кроссовер (flat crossover): создается  потомок 0x01 graphic

       - случайное число из интервала  0x01 graphic

       .

 

     * Простейший кроссовер (simple crossover): случайным образом выбирается

       число k из интервала 0x01 graphic

       и генерируются два потомка  0x01 graphic

       и 0x01 graphic

       .

 

     * Арифметический кроссовер (arithmetical crossover): создаются два

       потомка 0x01 graphic

       , 0x01 graphic

       , где 0x01 graphic

       , 0x01 graphic

       , 0x01 graphic

       , w либо константа (равномерный  арифметический кроссовер) из  интервала

       0x01 graphic

       , либо изменяется с увеличением  эпох (неравномерный арифметический

       кроссовер).

 

                                  0x01 graphic

 

     * Геометрический кроссовер (geometrical crossover): создаются два

       потомка 0x01 graphic

       , 0x01 graphic

       , где 0x01 graphic

       , 0x01 graphic

       , w - случайное число из интервала 0x01 graphic

       .

 

                                  0x01 graphic

 

     * Смешанный кроссовер (blend, BLX-alpha crossover): генерируется один

       потомок 0x01 graphic

       , где 0x01 graphic

       - случайное число из интервала 0x01 graphic

       , 0x01 graphic

       , 0x01 graphic

       , 0x01 graphic

       . BLX-0.0 кроссовер превращается в плоский.

 

                                  0x01 graphic

 

     * Линейный кроссовер (linear crossover): создаются  три потомка 0x01

       graphic

       , 0x01 graphic

       , где 0x01 graphic

       , 0x01 graphic

       , 0x01 graphic

       . На этапе селекции в этом  кроссовере отбираются два наиболее  сильных

       потомка.

 

                                  0x01 graphic

 

     * Дискретный кроссовер (discrete crossover): каждый ген 0x01 graphic

       выбирается случайно по равномерному  закону из конечного множества  0x01

       graphic

       .

 

                                  0x01 graphic

 

     * Расширенный линейчатый кроссовер (extended line crossover): ген 0x01

       graphic

       , w - случайное число из интервала  0x01 graphic

       .

 

                                  0x01 graphic

 

     * Эвристический кроссовер (Wright's heuristic crossover). Пусть 0x01

       graphic

       - один из двух родителей с  лучшей приспособленностью. Тогда  0x01

       graphic

       , w - случайное число из интервала  0x01 graphic

       .

 

                                  0x01 graphic

 

   Нечеткий  кроссовер (fuzzy recombination, FR-d crossover): создаются два

   потомка 0x01 graphic

   , 0x01 graphic

   . Вероятность того, что в i-том гене появится число 0x01 graphic

   , задается  распределением 0x01 graphic

   , где  0x01 graphic

   - распределения  вероятностей треугольной формы  (треугольные нечеткие

   функции  принадлежности) со следующими свойствами 0x01 graphic

   ( 0x01 graphic

   и 0x01 graphic

   ):

 

   +----------------------------------------------+

   |   Распределение   |Минимум | Центр  |Максимум|

   |   вероятностей    |        |        |        |

   |-------------------+--------+--------+--------|

   |0x01 graphic       |0x01    |0x01    |0x01    |

   |                   |graphic |graphic |graphic |

   |-------------------+--------+--------+--------|

   |0x01 graphic       |0x01    |0x01    |0x01    |

   |                   |graphic |graphic |graphic |

   +----------------------------------------------+

 

   Параметр d определяет степень перекрытия  треугольных функций

   принадлежности, по умолчанию 0x01 graphic

   .

 

                                  0x01 graphic

 

   В качестве  оператора мутации наибольшее  распространение получили:

   случайная  и неравномерная мутация (random and non-uniform mutation).

 

   При случайной  мутации ген, подлежащий изменению,  принимает случайное

   значение из интервала своего изменения. В неравномерной мутации значение

   гена  после оператора мутации рассчитывается  по формуле:

 

                                  0x01 graphic

 

   Сложно  сказать, что более эффективно  в каждом конкретном случае, но

   многочисленные исследования доказывают, что непрерывные генетические

   алгоритмы  не менее эффективно, а часто  гораздо эффективнее справляются  с

   задачами  оптимизации в многомерных пространствах,  при этом более просты в

   реализации  из-за отсутствия процедур кодирования и декодирования хромосом.

 

   Рассмотренные  кроссоверы исторически были  предложены первыми, однако во

   многих  задачах их эффективность оказывается  невысокой. Исключение

   составляет BLX-кроссовер с параметром 0x01 graphic

   - он превосходит по эффективности большинство простых кроссоверов. Позднее

   были  разработаны улучшенные операторы  скрещивания, аналитическая формула

   которых  и эффективность обоснованы теоретически. Рассмотрим подробнее один

   из таких  кроссоверов - SBX.