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

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

     Строительные  блоки

     Из  полученного в теореме шим выражения видно, что шимы с малым порядком и малой определяющей длиной менее подвержены разрушению в результате кроссовера или мутации, поэтому рост (или уменьшение) их доли в популяции происходит динамичнее. Шимы с высокой приспособленностью, малым порядком и малой определяющей длиной называются строительными блоками (building blocks) [9;285].

     Холланд (1992) показал, что в то время, как  ГА обрабатывает N строк на каждом поколении, в то же время неявно обрабатываются порядка N3 гиперплоскостей. Это доказывается с рассчетом на реально применимые размеры популяции и длины строки. Практически это означает, что большая популяция имеет возможность локализовать решение быстрее, чем маленькая. Для оценки рекомендуемого размера популяции в зависимости от длины строки можно вспомнить, что всего гиперплоскостей 3L.

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

     В гипотезе о строительных блоках считается, что в процессе приближения популяции к глобальному оптимуму порядок и приспособленность строительных блоков увеличиваются. Это легко видно на простом примере:

     График

     

     Все локальные максимумы приведенной  функции приходятся на блок **0*, а  минимумы — на **1*, поэтому очевидно, что после отбора основная часть  особей будут представителями первого  блока. Левая половина графика в  среднем ниже правой, поэтому доля блока 1*** будет преобладать над долей 0***. Получается, что основная масса особей окажутся представителями блока 1*** и в то же время **0*, значит, большое их количество будут представителями блока 1*0*. Теперь, выбирая между блоками 100* и 110*, получаем, что второй блок будет преобладать над первым. Таким образом, можно сказать, что хорошие строительные блоки малого порядка сложились в приспособленные блоки большего порядка, и в результате мы оказались в области глобального максимума, чем приблизились к решению задачи. 

 

      Раздел II. Модели генетических алгоритмов 

     2. 1. Настройка генетических алгоритмов 

     Генетический  алгоритм производит поиск решений  двумя методами одновременно: отбором  гиперплоскостей (hyperplane sampling) и методом hill-climbing. Кроссовер осуществляет первый из них, поскольку комбинирует и совмещает шаблоны родителей в их детях. Мутация обеспечивает второй метод: особь случайным образом изменяется, неудачные варианты вымирают, а если полученное изменение оказалось полезным, то, скорее всего, эта особь останется в популяции.

     Возникает вопрос: какой же из этих методов  лучше осуществляет поиск хороших  решений? Исследования показали, что  на простых задачах, таких, как максимизация унимодальной функции, ГА с мутацией (и без кроссовера) находят решение быстрее[3;211]. Также для такого метода требуется меньший размер популяции. На сложных многоэкстремальных функциях лучше использовать ГА с кроссовером, поскольку этот метод более надежен, хотя и требует большего размера популяции.

     С точки зрения теоремы шаблонов, мутация только вредит росту количества представителей хороших шаблонов, поскольку лишний раз их разрушает. Однако мутация просто необходима для ГА с малым размером популяции. Дело в том, что для малочисленных популяций свойственна преждевременная сходимость (premature convergence). Это ситуация, когда в некоторых позициях все особи имеют один и тот же бит, но такой набор битов не соответствует глобальному экстремуму[20]. При этом кроссовер практически не изменяет популяции, т. к. все особи почти одинаковы. В этом случае мутация способна инвертировать «застрявший» бит у одной из особей и вновь расширить пространство поиска.

     Введем  понятие давления отбора (selection pressure) — это мера того, насколько различаются  шансы лучшей и худшей особей популяции попасть в промежуточную популяцию. Для пропорционального отбора эта величина имеет свойство уменьшаться с увеличением средней приспособленности популяции. Действительно, при этом для каждой особи отношение f ⁄ <f> стремится 1, а значит шансы плохой и хорошей особей создать потомство уравниваются.

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

     Методология управления сходимостью классического  ГА до сих пор не выработана. 

     2. 2. Модели генетических алгоритмов 

     Классический  ГА хорош для понимания работы генетических алгоритмов, однако он не является наиболее эффективным из них. Сейчас мы рассмотрим различные варианты кодировки, генетические операторы и стратегии отбора, а также другие модели ГА[21].

     Кодирование

     Если  сравнивать кодирование бинарным алфавитом  и небинарным, то первый вариант  обеспечивает лучший поиск с помощью гиперплоскостей, т. к. предоставляет максимальное их количество. Действительно, если требуется закодировать 2L значений, то для бинарного алфавита количество гиперплоскостей будет 3L, тогда как при использовании, к примеру, четырехзначного алфавита длина слов будет в 2 раза меньше, и гиперплоскостей будет 5L ⁄ 2, т. е. меньше.

     Еще один аргумент в пользу бинарных алфавитов  — это то, что для встречаемости  каждого символа в каждой позиции  им требуется меньший размер популяции. Действительно, даже если имеется всего две строки, есть вероятность, что на каждой позиции в популяции есть и 0, и 1 (т. е. одна строка является результатом инвертирования другой) [3;215]. Если же алфавит большей мощности, то популяция из двух строк заведомо не будет содержать в каждой позиции несколько символов, и до применения мутации большая часть пространства поиска будет недоступна с точки зрения кроссовера. После применения мутации станет недоступна другая часть.

     С другой стороны, небинарные алфавиты зачастую обеспечивают более наглядное представление решений задачи.

     Исследования  показали, что для большинства  функций генетические алгоритмы  будут работать лучше, если закодировать параметры в строку кодом Грея, а не прямым бинарным кодом. Это связано  с т. н. Hamming cliffs, когда, к примеру, числа 7 и 8 различаются на 4 бита. Бинарное кодирование добавляет дополнительные разрывы, что осложняет поиск. Это можно показать на примере: пусть требуется минимизировать функцию f(x) = x2. Если в популяции изначально преобладали отрицательные хорошие решения, то с большой вероятностью она сойдется к −1 = 11…1. При этом достигнуть глобального минимума будет практически невозможно, поскольку любые изменения одного бита будут приводить к ухудшению решения. При кодировании кодом Грея такой проблемы не возникает[10;167].

     Кодирование с плавающей точкой тоже является более удачным, чем прямое бинарное. На вопрос, лучше ли оно, чем кодирование  кодом Грея, можно ответить, что  на каких-то задачах лучше работает первый вариант, на других — второй. Как определить, какой вариант использовать для конкретной задачи, пока неизвестно.

     Кроссовер

     Одноточечный  кроссовер мы рассмотрели выше.

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

     Скрещивающиеся  особи

     

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

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

     Однородный  кроссовер осуществляется следующим  образом: один из детей наследует  каждый бит с вероятностью p0 у  первого родителя, а иначе у второго. Второй ребенок получает все остальные не унаследованные биты. Обычно p0 = 0.5. Для однородного кроссовера не важна определяющая длина шаблона, и вообще в большинстве случаев шаблон разрушается. Такой агрессивный оператор плохо предназначен для отбора гиперплоскостей, однако его применение оправдано при малом размере популяции, т. к. он препятствует преждевременному схождению, свойственному таким популяциям[11].

     Стратегии отбора

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

     Ранковый  отбор (rank selection) отличается от пропорционального тем, что для каждой особи ее вероятность попасть в промежуточную популяцию пропорциональна ее порядковому номеру в отсортированной по возрастанию приспособленности популяции. Такой вид отбора не зависит от средней приспособленности популяции.

     Турнирный отбор (tournament selection) осуществляется следующим  образом: из популяции случайным  образом выбирается t особей, и лучшая из них помещается в промежуточную  популяцию. Этот процесс повторяется N раз, пока промежуточная популяция не будет заполнена. Наиболее распространен вариант при t = 2. Турнирный отбор является более агрессивным, чем пропорциональный.

     Отбор усечением (truncation selection): популяция сортируется  по приспособленности, затем берется  заданная доля лучших, и из них случайным образом N раз выбирается особь для дальнейшего развития[18;192].

     Стратегии формирования нового поколения

     Выделяют  два типа формирования нового поколения  после получения множества детей  в результате кроссовера и мутации:

1. дети замещают родителей;
2. новое поколение составляется из совокупности и детей, и их родителей, например, выбором N лучших.

     Также для формирования нового поколения  возможно использование принципа элитизма: в новое поколение обязательно  включается заданное количество лучших особей предыдущего поколения (часто одна лучшая особь) [19;169].

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

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

     Классический  ГА был рассмотрен выше. Напомним, что его создал Holland (1975).

     Genitor

     Этот  алгоритм был создан Уитли (D. Whitley). Genitor-подобные алгоритмы отличаются от классического  ГА следующими тремя свойствами:

         На каждом шаге только одна  пара случайных родителей создает  только одного ребенка.

         Этот ребенок заменяет не родителя, а одну из худших особей  популяции (в первоначальном Genitor — самую худшую).