Иллюстрация работы генетического алгоритма
I. Условие. Даны два числа. Найти число, содержащее наибольшее число единиц.
Решение.
Сформируем восемь хромосом:
Случайным способом сформируем популяцию, состоящую из восьми хромосом.
111001100101 | H1 | 7 |
011011100100 | H2 | 6 |
101100111110 | H3 | 8 |
010011000000 | H4 | 3 |
011101000000 | H5 | 4 |
100011001001 | H6 | 5 |
101110111010 | H7 | 8 |
000010111100 | H8 | 5 |
Начальная популяция.
Случайным образом сформируем пары для скрещивания:
В результате применения одноточечного кроссинговера получаем следующие значения:
II. Условие. Необходимо раскрасить граф в три цвета: красный (к), синий (с), жёлтый (ж).
Решение.
Критерий отбора в новую популяцию: из всех возможных вариантов раскраски в новую популяцию попадают те варианты, которые имеют наибольшее число удовлетворительных рёбер (соединяющих вершины различных цветов).