Исходная популяция

№ строки	Экз. кода	y1	y2	x1	x2	f	pi
1	011001010	12	10	17	12	702	0,1199
2	100001101	16	13	21	15	579	0,0989
3	110011100	25	12	30	14	319	0,0545
4	001011010	5	10	10	12	751	0,1283
5	010001011	8	11	13	13	727	0,1242
6	011101000	14	8	19	10	694	0,1186
7	101010111	21	7	26	9	528	0,0902
8	111010001	29	1	34	3	220	0,0376
9	001101110	6	14	11	16	678	0,1158
10	100010010	17	2	22	4	655	0,1119

Действия оператора отбора, использующего распределение p_i, привели к выбору родительских пар (2,7), (5,10), (6,9), (1,4), (4,9). В каждой паре точки разбиения выбираются независимо с помощью датчика целых случайных чисел от 1 до 8 с равными вероятностями. Результаты работы оператора скрещивания приведены в табл. 4.2. Точки разбиения показаны косой чертой. Значения аргументов и функции даны для потомков.

Таблица 4.2

Результаты работы оператора скрещивания

№ строки	Экз. кода родителей	Экз. кода потомков	y1	y2	x1	x2	f
2 7	100/001101 101/010111	100010111 101001101	17 20	7 13	22 25	9 15	640 475
5 10	0100010/11 1000100/10	010001010 100010011	8 17	10 3	13 22	12 5	742 656
6 9	01110/1000 00110/1110	011101110 001101000	14 6	14 8	19 11	16 10	598 774
1 4	01/1001010 00/1011010	011011010 001001010	13 4	10 10	18 9	12 12	687 750
4 9	00101/1010 00110/1110	001011110 001101010	5 6	14 10	10 11	16 12	679 750

Теперь предположим, что оператор мутации сработал для 7 потомка, поменяв местами биты 1 и 2. Код этого потомка сменился с 011101110 на 101011010, значение функции стало 495. Расширенная популяция включает 10 исходных особей и 10 потомков. Сокращаем популяцию до принятого размера, отбрасывая особи с меньшими значениями функции. Полученная после этого популяция первого поколения представлена в табл. 4.3. В ней только первые 4 особи из исходной популяции.

Таблица 4.3

Популяция первого поколения

№ строки	Экз. кода	x1	x2	f
1	011001010	17	12	702
2	001011010	10	12	751
3	010001011	13	13	727
4	011101000	19	10	694
5	010001010	13	12	742
6	001101000	11	10	774
7	011011010	18	12	687
8	001001010	9	12	750
9	001011110	10	16	679
10	001101010	11	12	750

Из сравнения данных в табл. 4.1 и 4.3 видно, что новая популяция лучше исходной. Если среднее значение целевой функции на начальной популяции было равно 585,3, то на новом поколении оно возросло до 725,6.

Следующий шаг заключается в проверке условия окончания поиска. Оно может быть представлено в разных вариантах: min f_i > f_min или max f_i – min f_i < _f, или n  n_задан. В первом варианте все особи должны быть лучше заданного уровня качества, во втором критерием выступает близость особей, в третьем – число поколений (итераций). Если предположить, что выбранное условие выполняется на первом поколении, то поиск на этом заканчивается. За решение принимаем лучший результат: x₁ = 11, x₂ = 10, f = 774. Оптимальному решению соответствуют значения: x₁ = 10, x₂ = 5, f = 800. Сравнение показывает, что по значению критерия получено неплохое приближение к оптимуму. Понятно, что продолжение итераций приведет к дальнейшему улучшению популяции и получению более близкого к оптимальному решения.

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