Классический генетический алгоритм

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

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

Хромосома кодирует признаки особи, то есть хромосома – это кодированное решение задачи (рис. 1.5).

Рис. 1.5. Соотношение между генотипом и фенотипом

Для кодирования решения могут использоваться вещественные числа или двоичный алфавит: {0,1}.

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

Рассмотрим простой пример. Пусть необходимо найти максимум функции одной переменной F (x). Если кодировать x цепочкой из пяти битов, то пространство поиска разбивается на две части А и В гиперплоскостями вида (символ * обозначает произвольное значение):

0**** и 1****

Каждое из пространств А и В разбивается на два подпространства соответственно цепочками:

00***, 01*** (А 1, А 2) и 10***, 11***(В 1, В 2)

Геометрически это можно изобразить следующим образом (рис. 1.6):

Рис. 1.6. Разбиение пространства поиска

Шаблоны, разделяющие пространство поиска, называются схемами.

Схема - это строка длины m, состоящая из знаков алфавита {0; 1; *}, где {*} - неопределенный символ.

В соответствии с рис. 1.6 схемы с малым количеством закрепленных символов проверяют крупные подпространства в пространстве решений.

Например, в хромосоме всего три бита, то возможны следующие решения:

000 001 010 011 100 101 110 111

Количество решений равно 2³=8. Эти решения можно представить вершинами куба в трехмерном пространстве (рис. 1.7).

Можно описать отдельные области, в которых происходит поиск решения (т.е. схемы). Для этого используется символ *.

При использовании символа * получается общее количество решений, равное 3³=27.

Так как схема должна содержать хотя бы один символ *, то общее количество схем равно: 27 - 8=19.

Сами схемы имеют вид:

0** 1** 01* ***

*0* *1* 10* **0

**1 *01 00* 11*

*10 0*0 1*1 1*0

*00 *11 0*1

В приведенном примере схема *** описывает все пространство решений, т.е. всю поверхность куба. Схемы с одним закрепленным символом описывают грани куба. Схемы с двумя закрепленными символами описывают ребра куба.

Рис. 1.7. Геометрическое представление вариантов решения задачи

Таким образом, если конкретная хромосома – это вариант решения задачи, то схема – это целая область в пространстве решений.

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

Работа ГА управляется тремя генетическими операторами: селекция, скрещивание, мутация (рис. 1.8).

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

Селекция (другие названия – отбор, репродукция) – это первая генетическая операция, осуществляемая над популяцией. В результате селекции должны быть отобраны хромосомы, которые будут участвовать в процессе генерации новой популяции (популяции потомков). Селекция происходит на основании оценок пригодности хромосом. В результате селекции возникает промежуточная популяция (mating pool или родительский пул). Промежуточная популяция — это набор особей, которые получили право размножаться. Приспособленные особи могут быть записаны туда несколько раз. «Плохие» особи с большой вероятностью туда вообще не попадут.

Рис. 1.8. Общая структура ГА

В классическом ГА вероятность P_i каждой i -й особи попасть в промежуточную популяцию пропорциональна отношению ее ОП к сумме ОП всех хромосом:

Такой способ называется пропорциональный отбор (proportional selection). Его можно реализовать следующим образом: пусть особи располагаются на колесе рулетки, так что размер сектора S_i (в процентах) каждой особи соответствует P_i (рис. 1.9):

S_i = P_i *100%

Рис. 1.9. Колесо рулетки

Изначально промежуточная популяция пуста. Затем рулетка запускается N раз, так что каждый раз выбирается хромосома, сектор которой оказался под указателем.

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

После селекции выполняются операции скрещивания и мутации, которые обобщенно называют рекомбинацией.

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

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

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

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

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

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

Помимо операторов скрещивания и мутации в ГА может использоваться оператор инверсии.