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

Можно выбирать некоторое количество точек  в хромосоме для инверсии, причем их число также может быть случайным. Также можно инвертировать сразу  некоторую группу подряд идущих точек. Среди рекомендаций по выбору вероятности  мутации нередко можно встретить  варианты 1/L или 1/N.

3.7 Критерии останова

 

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

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

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

4. Теория

Рассмотрим  несколько теоретических фактов, которые помогут более чётко  понять природу генетических алгоритмов и примерно объяснить, почему же они  работают.

4.1 Шаблоны

Шаблоном (schema) называется строка длины L из символов 0, 1 и *(«don't care» символ). Строка является представителем данного шаблона, если все символы кроме * совпадают. Например, у шаблона 1*0*0 есть 4 представителя:

• 10000
• 10010
• 11100
• 11110

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

 

Поэтому термины «шаблон» и «гиперплоскость» взаимозаменяемы.

Порядком шаблона называется количество фиксированных в нём битов.

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

Например, для шаблона H = *0**10*: порядок o(H) = 3, определяющая длина Δ(H) = 4.

Очевидно, что количество представителей шаблона H равно , а количество шаблонов равно .

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

4.2 Неявный параллелизм

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

4.3 Теорема шаблонов

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

M(H, t) — число представителей шаблона H в поколении t.

Количество  представителей шаблона H в промежуточном поколении:

где f(H, t) — приспособленность шаблона H в поколении t, а <f(t)> — средняя приспособленность поколения t.

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

 

где P(H, t) — доля представителей шаблона H в поколении t. Первый множитель произведения равен вероятности попадания точки раздела между фиксированными битами шаблона, а второй — вероятности выбрать в пару представителя другого шаблона.

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

1.1011  ->  1.1011

1.0100      1.0100

 

Как видно, в этой ситуации шаблон не разрушается.

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

 

Учтём влияние мутации. В шаблоне o(H) фиксированных битов, и каждый не будет инвертирован с вероятностью (1 − p_m). Откуда получаем итоговую формулу теоремы шаблонов:

 

 

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

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

5. Настройка ГА

Генетический  алгоритм производит поиск решений  с помощью:

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

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

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

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

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

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

Необходимость сбалансированной сходимости ГА:

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

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

6. Различные модификации ГА

6.1 Кодирование

Аргументы в пользу кодирования бинарным алфавитом:

• обеспечивает лучший поиск с помощью гиперплоскостей, т. к. предоставляет максимальное их количество.

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

• для встречаемости каждого символа в каждой позиции требуется меньший размер популяции

Даже  для двух строк, есть вероятность, что  на каждой позиции в популяции  есть и 0, и 1. Если же алфавит большей  мощности, то до применения мутации  большая часть пространства поиска будет недоступна с точки зрения кроссовера, после применения мутации станет недоступна другая часть.

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

Для большинства функций ГА будут работать лучше при кодировании параметров кодом Грея, а не прямым бинарным кодом. Это связано с тем, что расстояние Хэмминга между битовыми представлениями данных может и не отражать близость в привычном смысле – например, числа 7 и 8 различаются на 4 бита. Бинарное кодирование добавляет дополнительные разрывы, что осложняет поиск.

Пример: пусть требуется минимизировать функцию 

Если  в начальной популяции преобладали  хорошие отрицательные решения, то скорее всего мы придём к решению −1 = 11…1. Но достигнуть глобального минимума 00…0 будет практически невозможно, поскольку изменение любого бита будет приводить к ухудшению решения. При кодировании кодом Грея такой проблемы не возникает.

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

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

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

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

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

6.3 Кроссовер

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

010.1001.1011  ->  010.1011.1011

110.1011.0100      110.1001.0100

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

Однородный кроссовер: один из детей наследует каждый бит с вероятностью p₀ у первого родителя и с (1 - p₀) у второго, второй ребенок получает не унаследованные первым биты. Обычно p₀ = 0.5.

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

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

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

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

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

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

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

7. Некоторые модели ГА

7.1 Genitor (Whitley)

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

Таким образом, на каждом шаге в популяции  обновляется только одна особь.