Принцип работы генетического алгоритма
Например: пусть скрещиваются две хромосомы 111111 и 000000. Определяем случайным образом точку разрыва хромосомы, пусть, это будет 3: 111|111 000|000. Теперь хромосомы обмениваются частями, стоящими после точки разрыва, и образуют двух новых потомков: 111000 и 000111.
Таблица 1
Исходная популяция
|
№ |
Особь | ||
|
Целое число |
Двоичное число |
Приспособленность | |
|
1 |
2 |
010 |
-0,33 |
|
2 |
3 |
011 |
7,25 |
|
3 |
5 |
101 |
7,92 |
|
4 |
4 |
100 |
10,33 |
Для нашей популяции процесс создания первого поколения потомков показан в таблице 2.
Таблица 2
Одноточечный кроссинговер
|
№ |
Особь популяции |
Выбранный номер |
Вторая особь-родитель |
Точка кроссинговера |
Особи-потомки |
|
1 |
010 |
4 |
100 |
1 |
000 |
|
110 | |||||
|
2 |
011 |
2 |
011 |
011 | |
|
011 | |||||
|
3 |
101 |
1 |
010 |
2 |
100 |
|
011 | |||||
|
4 |
100 |
4 |
100 |
100 | |
|
100 |
Следующим шагом в работе генетического алгоритма являются мутации, т.е. случайные изменения полученных в результате скрещивания хромосом. Пусть вероятность мутации равна 0,3. Для каждого потомка возьмем случайное число на отрезке [0;1], и если это число меньше 0,3, то инвертируем случайно выбранный ген (заменим 0 на 1 или наоборот) (см. табл. 3).