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

3.9.
Модификации классического генетического 
алгоритма 
 
В классическом генетическом алгоритме используется двоичное пред-
ставление хромосом, селекция методом колеса рулетки и точечное 

---

А.Е. Кононюк Дискретно-непрерывная математика 
146 
скрещивание (с одной точкой скрещивания). Для повышения эффек-
тивности его работы создано множество модификаций основного ал-
горитма. Они связаны с применением других методов селекции, с мо-
дификацией генетических операторов (в первую очередь оператора 
скрещивания), с преобразованием функции приспособленности (путем 
ее масштабирования), а также с иными способами кодирования 
параметров задачи в форме хромосом. Существуют также версии ге-
нетических алгоритмов, позволяющие находить не только глобальный, 
но и локальные оптимумы. Это алгоритмы, использующие так 
называемые ниши, введенные в генетические алгоритмы по аналогии с 
природными экологическими нишами. Другие версии генетических 
алгоритмов служат для многокритериальной оптимизации, т.е. для 
одновременного поиска оптимального решения для нескольких функ-
ций. Встречаются также специальные версии генетического алгоритма, 
созданные для решения проблем малой размерности, не требующих ни 
больших популяций, ни длинных хромосом. Их называют 
ге-
нетическими микроалгоритмами. 
3.9.1. 
Методы селекции 
Основанный на принципе колеса рулетки метод селекции считается 
для генетических алгоритмов основным методом отбора особей для 
родительской популяции с целью последующего их преобразования 
генетическими операторами, такими как скрещивание и мутация. 
Несмотря на случайный характер процедуры селекции, родительские 
особи выбираются пропорционально значениям их функций 
приспособленности, т.е. согласно вероятности селекции, определяемой 
по формуле (3.3). Каждая особь получает в родительском пуле такое 
количество своих копий, какое устанавливается выражением
e(ch
i
) = p
s
(ch
i
)∙/V, (3.16)
где 
N 
- количество хромосом ch
i
, i=1,2.....N
в популяции, a p
s
(ch
i
)
- вероятность селекции хромосомы ch
i
, рассчитываемая по формуле 
(3.3). Строго говоря, количество копий данной особи в родительском 
пуле равно целой части от e(ch
i
). При использовании формул (3.3) и 
(3.16) необходимо обращать внимание на то, что e(ch
1
) = F(ch
i
)/
F
, 
где 
F
 
- среднее значение функции приспособленности в популяции. 
Очевидно, что метод рулетки можно применять тогда, когда значения 
функции приспособленности положительны. Этот метод может 

---

А.Е. Кононюк Дискретно-непрерывная математика 
147 
использоваться только в задачах максимизации функции (но не мини-
мизации). 
Очевидно, что проблему минимизации можно легко свести к задаче 
максимизации функции и обратно. В некоторых реализациях генетического 
алгоритма метод рулетки применяется для поиска минимума функции (а не 
максимума). 
Это 
результат 
соответствующего 
преобразования, 
выполняемого программным путем для удобства пользователей, поскольку 
в большинстве прикладных задач решается проблема минимизации 
(например, затрат, расстояния, погрешности и т.п.). В качестве примера 
такой реализации можно назвать программу