5.3.3. Пример решения задачи с использованием генетического алгоритма

Рассмотрим применение ГА для решения задачи поиска максимума одномерной функции [2].

Пусть имеется набор натуральных чисел в интервале [0, 31] и определенная на этом наборе чисел функция f(x) = x. Требуется найти максимальное значение функции.

В качестве кода используется двоичный формат аргументов функции (фенотип). Сам код представляет собой двоичную строку из 5 бит (генотип). Целевой функцией непосредственно является рассматриваемая функция f(x), аргументом которой является число, двоичное представление которого в качестве генотипа использует алгоритм.

Установим базовые характеристики ГА: размер популяции – 4, вероятность мутации – 0,01. Процедуру мутации определим как инверсию одного из битов строки, случайно выбранного по равномерному закону. Оператор скрещивания и отбора аналогичны описанным выше, стратегия элитизма не используется.

На первом этапе на основе равномерного распределения создается исходная популяция из четырех особей, представленная в табл. 5.2.

Таблица 5.2

Предположим, что оператор отбора выбрал для производства потомков две пары строк (1, 2) и (2, 4). Работа оператора скрещивания проиллюстрирована в табл. 5.3, причем разбиение каждой пары на подстроки происходит независимо.

Таблица 5.3

Кроме этого примем, что для младшего бита потомка в строке 3 сработал оператор мутации, вследствие чего данный код изменил свое значение с 10000 на 10001.

Таким образом, популяция за счет порожденных потомков расширилась до восьми особей, представленных в табл. 5.4.

Таблица 5.4

Оператор редукции сокращает популяцию до исходного числа особей, исключив из нее строки с наименьшими значениями целевой функции (1, 3, 4 и 5), после чего популяция первого поколения примет вид, представленный в таблице 5.5.

Таблица 5.5.

На этом шаг работы генетического алгоритма заканчивается. Очевидно, что даже за одну итерацию качество популяции значительно возросло. Если в исходной популяции среднее значение целевой функции было 10,75, а ее минимальное значение составляло 2, то в популяции первого поколения среднее значение возросло до 19, а минимальное значение составило 14. Лучшее же решение увеличилось с 18 до 27 при оптимальном решении 31.

Таким образом, данный пример наглядно иллюстрирует процесс улучшения как популяции в целом, так и наилучшего решения в частности в результате работы генетического алгоритма.