Применение генетических алгоритмов

      НАЧАЛО /* генетический алгоритм */

      Создать начальную популяцию

      Оценить приспособленность каждой особи

      останов := FALSE

      ПОКА  НЕ останов ВЫПОЛНЯТЬ

      НАЧАЛО /* создать популяцию нового поколения */

      ПОВТОРИТЬ (размер_популяции/2) РАЗ

      НАЧАЛО /* цикл воспроизводства */

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

      Скрестить выбранные особи и получить двух потомков

      Оценить приспособленности потомков

      Поместить потомков в новое поколение

      КОНЕЦ

      ЕСЛИ  популяция сошлась ТО останов := TRUE

      КОНЕЦ

      КОНЕЦ 

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

     Хотя  модель эволюционного развития, применяемая  в ГА, сильно упрощена по сравнению  со своим природным аналогом, тем  не менее ГА является достаточно мощным средством и может с успехом  применяться для широкого класса прикладных задач, включая те, которые трудно, а иногда и вовсе невозможно, решить другими методам[8;239]. Однако, ГА, как и другие методы эволюционных вычислений, не гарантирует обнаружения глобального решения за полиномиальное время. ГА-мы не гарантируют и того, что глобальное решение будет найдено, но они хороши для поиска "достаточно хорошего" решения задачи "достаточно быстро". Там, где задача может быть решена специальными методам, почти всегда такие методы будут эффективнее ГА и в быстродействии и в точность найденных решений. Главным же преимуществом ГА-мов является то, что они могут применяться даже на сложных задачах, там, где не существует никаких специальных методов. Даже там, где хорошо работаю существующие методики, можно достигнуть улучшения сочетанием их с ГА[10;247]. 

      1. 2. Алгоритм работы

     На  рисунке изображена схема работы любого генетического алгоритма:

     В классическом ГА начальная популяция формируется случайным образом. Фиксируется размер популяции (количество особей в ней будем обозначать символом N), который не изменяется в течение работы всего алгоритма. Каждая особь генерируется как случайная L-битная строка, где L — длина кодировки особи, она тоже фиксирована и для всех особей одинакова.

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

     Шаг алгоритма состоит из трех стадий: генерация промежуточной популяции (intermediate generation) путем отбора (selection) текущего поколения (current generation), скрещивание (recombination) особей промежуточной популяции путем кроссовера (crossover), что приводит к формированию нового поколения (next generation), и мутация нового поколения. На рисунке изображены первые две стадии:

 

     Промежуточная популяция — это набор особей, которые получили право размножаться. Приспособленные особи могут  быть записаны туда несколько раз. «Плохие» особи с большой вероятностью туда вообще не попадут[12;275].

     В классическом ГА вероятность каждой особи попасть в промежуточную  популяцию пропорциональна ее приспособленности, т. е. работает пропорциональный отбор (proportional selection). Можно его реализовать следующим образом: пусть особи располагаются на колесе рулетки, так что размер сектора каждой особи пропорционален ее приспособленности. Изначально промежуточная популяция пуста. N раз запуская рулетку, выберем требуемое количество особей для записи в промежуточную популяцию. Ни одна выбранная особь не удаляется с рулетки. Такой отбор называется stochastic sampling.

     Другой  способ отбора, который также является пропорциональным, это remainder stochastic sampling. Для каждой особи вычисляется отношение ее приспособленности к средней приспособленности популяции. Целая часть этого отношения указывает, сколько раз нужно записать особь в промежуточную популяцию, а дробная — это ее вероятность попасть туда еще раз. Пусть, к примеру, для некоторой особи i f_i ⁄ <f> = 1.36 (<f> — средняя приспособленность текущей популяции). Тогда она будет выбрана один раз, а затем с вероятностью 0.36 еще раз. Реализовать такой способ отбора удобно следующим образом: расположим особи на рулетке так же, как было описано[3;177]. Теперь пусть у рулетки не одна стрелка, а N, причем они отсекают одинаковые сектора. Тогда один запуск рулетки выберет сразу все N особей, которые нужно записать в промежуточную популяцию. Такой способ иллюстрируется следующим рисунком:

     После отбора особи промежуточной популяции  случайным образом разбиваются  на пары. Каждая из них с вероятностью p_c скрещивается, т. е. к ней применяется оператор кроссовера, в результате чего получаются два потомка. Они записываются в новое поколение. Если же паре не выпало скрещиваться, в новое поколение записываются сами особи этой пары[4;258].

В классическом генетическом алгоритме применяется  одноточечный оператор кроссовера (1-point crossover): для родительских хромосом (т. е. строк) случайным образом выбирается точка раздела, и они обмениваются отсеченными частями. Полученные две строки являются потомками:

11010 01100101101 ⇒ 10110 01100101101

10110 10011101001 ⇒ 11010 10011101001

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

1011001100101101 ⇒ 1011001101101101

     Таким образом, процесс отбора, скрещивания и мутации приводит к формированию нового поколения. Шаг алгоритма завершается объявлением нового поколения текущим. Далее все действия повторяются.

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

     Схождением  называется такое состояние популяции, когда все строки популяции почти  одинаковы и находятся в области  некоторого экстремума. В такой ситуации кроссовер практически никак не изменяет популяции. А вышедшие из этой области за счет мутации особи склонны вымирать, так как чаще имеют меньшую приспособленность, особенно если данный экстремум является глобальным максимумом. Таким образом, схождение популяции обычно означает, что найдено лучшее или близкое к нему решение[18;213].

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

     1.3.  Шимы, теорема шим 

     Шимой (schema) называется строка длины L (т. е. той же длины, что и любая строка популяции), состоящая из символов {0, 1, *} (где * — «don't care» символ). Будем говорить, что строка является представителем данной шимы, если в позициях, где знак шимы равен 0 или 1, она имеет тот же символ. Например, у шимы 01*0*110 следующие представители:

         01000110

         01001110

         01110110

         01111110

     Порядком (order) шимы называется количество фиксированных битов в ней. Определяющей длиной (defining length) шимы называется расстояние между ее крайними фиксированными битами. Например, для шимы *1***01* порядок o = 3, а определяющая длина Δ = 5.

     Очевидно, что количество представителей шимы H равно 2L−o(H), а количество шим равно 3L (действительно, шимы — это строки, у которых на каждой позиции может находиться один из трех символов) [3;180].

     Если  представить пространство поиска в  виде гиперкуба, то строки это его  вершины, а шима определяет в нем гиперплоскость. К примеру, шима **1 определяет правую грань этого трехмерного куба:

     Куб

     

     Поэтому термины «гиперплоскость» и «шима» взаимозаменяемы. Следующий рисунок изображает другое представление шим:

     Сечение пространства поиска

     

     На  нем видно, что некоторые шимы имеют с среднем по всему пространству поиска большую приспособленность, чем другие.

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

     Внешне  кажется, что генетический алгоритм при отборе выбирает строку, однако при этом неявным образом происходит выборка шим, представителем которых она является[7;334]. Это означает, что на каждом поколении количество представителей шимы изменяется в соответствии с текущей приспособленностью этой шимы. У «хороших» шим представители в среднем более приспособленные, а значит, они чаще будут выбираться в промежуточную популяцию. «Плохие» шимы имеют много шансов вымереть. Одна строка является представителем сразу многих шим (а именно 2L: на каждой позиции мы либо оставляем бит строки, либо заменяем его на «*»). Поэтому при отборе одной строки отбирается сразу целое множество шим. Это явление получило название неявный параллелизм (implicit parallelism).

     Теорема шим

     Теорема шим (The Schema Theorem) была приведена в упомянутой выше работе Холланда и является первой попыткой объяснить, почему генетические алгоритмы работают. Она показывает, как изменяется доля представителей шимы в популяции.

     Пусть M(H, t) — число представителей шимы H в t-ом поколении. В силу того, что при построении промежуточной популяции используется пропорциональный отбор, в ней количество представителей данной шимы будет M(H, t + intermediate) = M(H, t) f(H, t) ⁄ <f(t)>,где f(H, t) — приспособленность шимы H в t-ом поколении, а <f(t)> — средняя приспособленность t-го поколения.

     Особи промежуточной популяции с вероятностью pc подвергаются кроссоверу. Одноточечный кроссовер может разрушить шиму, что означает, что один из родителей был представителем рассматриваемой шимы, но ни один из детей уже таковым являться не будет. Вероятность разрушения меньше, чем Δ(H) (1 − P(H, t) f(H, t) ⁄ <f(t)>) ⁄ (L−1), где P(H, t) — доля представителей шимы H в t-ом поколении. Первый множитель произведения равен вероятности точки раздела попасть между фиксированными битами шимы, а второй — вероятности выбрать в пару представителя другой шимы[7;335].

     Действительно, кроссовер разрушает шиму не чаще, чем когда второй родитель (а он выбирается в промежуточной популяции) не является представителем этой шимы, и при этом точка раздела попадает между фиксированными битами шимы. Даже в этих ситуациях она не обязательно разрушается, например, если мы рассматриваем шиму 11****, а кроссоверу подвергаются строки 110101 и 100000, и точка раздела попадает между первыми двумя битами, то, хотя вторая строка не является представителем нужной шимы, все равно один из потомков окажется подходящим и шима не разрушится.

     Таким образом, после кроссовера, переходя от количества представителей к их доле, получаем следующее неравенство:

     P(H, t + 1) ≥ P(H, t) f(H, t) [1 − pc Δ(H) (1 − P(H, t) f(H, t) ⁄ <f(t)>) ⁄ (L−1)] ⁄ <f(t)>

     Теперь  учтем влияние мутации. Для каждого  фиксированного бита вероятность того, что он не будет инвертирован, равна (1 − pm). Поскольку всего в шиме фиксированных битов o(H), то верна следующая итоговая формула теоремы шим:

     P(H, t + 1) ≥ P(H, t) f(H, t) [1 − pc Δ(H) (1 − P(H, t) f(H, t) ⁄ <f(t)>) ⁄ (L−1)] (1 − pm)o(H) ⁄ <f(t)>

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