Принцип работы генетического алгоритма
Таблица 3
Мутация потомков
|
№ |
Особи-потомки |
Случайное число |
Выбранный ген для мутации |
Потомок после мутации |
Приспособленность потомка до мутации |
Приспособленность потомка после мутации |
|
1 |
000 |
0,1 |
3 |
001 |
5 |
-5,42 |
|
2 |
110 |
0,6 |
- |
110 |
5 |
5 |
|
3 |
100 |
0,5 |
- |
100 |
10,33 |
10,33 |
|
4 |
011 |
0,2 |
1 |
111 |
7,25 |
12,58 |
Как видно на примере, мутации способны улучшить (первый потомок) или ухудшить (четвертый потомок) приспособленность особи-потомка. В результате скрещивания хромосомы обмениваются «хвостами», т.е. младшими разрядами в двоичном представлении числа. В результате мутаций изменению может подвергнуться любой разряд, в том числе, старший. Таким образом, если скрещивание приводит к относительно небольшим изменениям пробных решений, то мутации могут привести к существенным изменениям значений пробных решений (см. рис. 2).
Рис. 2. Изменение популяции в процессе естественного отбора
Теперь из четырех особей-родителей и четырех полученных особей потомков необходимо сформировать новую популяцию. В новую популяцию отберем четыре наиболее приспособленных особей из числа «старых» особей и особей-потомков (см. табл. 4).
Таблица 4
Формирование новой популяции из особей-родителей и особей-потомков
|
№ |
Особи |
Приспособленность |
Новая популяция |
Приспособленность особей в новой популяции |
|
1 |
010 |
-0,33 |
001 |
-5,42 |
|
2 |
011 |
7,25 |
010 |
-0,33 |
|
3 |
101 |
7,92 |
110 |
5 |
|
4 |
100 |
10,33 |
011 |
7,25 |
|
5 |
001 |
-5,42 | ||
|
6 |
110 |
5 | ||
|
7 |
100 |
10,33 | ||
|
8 |
111 |
12,58 |