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

Работу генетического алгоритма рассмотрим на следующем примере.

Пример. Найти максимум функции (4.3) для целочисленной переменной , принимающей значения от 0 до 31.

Решение:

1. Используя двоичную систему счисления, закодируем числа от 0 до 31. Тогда хромосомы приобретут вид двоичных последовательностей, состоящих из 5 битов (0 как 00000, 31 как 11111)

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

3. Выберем случайным образом исходную популяцию, состоящую из 6 кодовых последовательностей (N =6). Пусть выбраны хромосомы:

Соответствующие им фенотипы – это числа от 0 до 31:

=19

=3

=7

=21

=8

=29

По формуле (4.3) рассчитаем значения функции приспособленности для каждой хромосомы в популяции, получим:

723

19

99

883

129

1683

4. Селекция хромосом осуществляется методом рулетки.

Используя формулы (4.1) и (4.2) получим, что

Рис 4.2

Розыгрыш с помощью колеса рулетки сводится к случайному выбору числа из интервала [0, 100], указывающего на соответствующий сектор на колесе, т.е. на конкретную хромосому (рисунок 4.2).

Допустим, что выбраны числа: 97, 26, 54, 13, 31, 88. Это означает выбор хромосом , , , , , .

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

.

Декодировав полученные последовательности, вычислим функции принадлежности данных хромосом:

.

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