Дискретно-непрерывная математика. Кн. 0 : Алгоритмы. Ч. Генетические алгоритмы

3.3. Другие модели ГА 
Классический ГА хорош для понимания работы генетических 
алгоритмов, однако он не является наиболее эффективным из них. 
Сейчас мы рассмотрим различные варианты кодировки, генетические 
операторы и стратегии отбора, а также другие модели ГА.
Кодирование 
Если сравнивать кодирование бинарным алфавитом и небинарным, то 
первый вариант обеспечивает лучший поиск с помощью 
гиперплоскостей, т. к. предоставляет максимальное их количество. 
Действительно, если требуется закодировать 2
L
значений, то для 
бинарного алфавита количество гиперплоскостей будет 3
L
, тогда как 
при использовании, к примеру, четырехзначного алфавита длина слов 
будет в 2 раза меньше, и гиперплоскостей будет 5
L
⁄ 2
, т. е. меньше.
Еще один аргумент в пользу бинарных алфавитов — это то, что для 
встречаемости каждого символа в каждой позиции им требуется 
меньший размер популяции. Действительно, даже если имеется всего 
две строки, есть вероятность, что на каждой позиции в популяции есть и 
0, и 1 (т. е. одна строка является результатом инвертирования другой). 
Если же алфавит большей мощности, то популяция из двух строк 
заведомо не будет содержать в каждой позиции несколько символов, и 
до применения мутации большая часть пространства поиска будет 
недоступна с точки зрения кроссовера. После применения мутации 
станет недоступна другая часть.

---

А.Е. Кононюк Дискретно-непрерывная математика 
113 
С другой стороны, небинарные алфавиты зачастую обеспечивают более 
наглядное представление решений задачи.
Исследования показали, что для большинства функций генетические 
алгоритмы будут работать лучше, если закодировать параметры в 
строку 
кодом Грея
, а не прямым бинарным кодом. Это связано с т. н. 
Hamming cliffs
, когда, к примеру, числа 7 и 8 различаются на 4 бита. 
Бинарное кодирование добавляет дополнительные разрывы, что 
осложняет поиск. Это можно показать на примере: пусть требуется 
минимизировать функцию 
f
(
x
) = 
x
2
. Если в популяции изначально 
преобладали отрицательные хорошие решения, то с большой 
вероятностью она сойдется к −1 = 11…1. При этом достигнуть 
глобального минимума будет практически невозможно, поскольку 
любые изменения одного бита будут приводить к ухудшению решения. 
При кодировании кодом Грея такой проблемы не возникает.
Кодирование с плавающей точкой тоже является более удачным, чем 
прямое бинарное. На вопрос, лучше ли оно, чем кодирование кодом 
Грея, можно ответить, что на каких-то задачах лучше работает первый 
вариант, на других — второй. Как определить, какой вариант 
использовать для конкретной задачи, пока неизвестно.