Поиск максимума одномерной функции
Пусть имеется набор натуральных чисел от 0 до 31 и функция f (x)= х, определенная на этом наборе чисел. Требуется найти максимум функции. Данная задача является тривиальной и не требует применения столь изощренных методов поиска, однако она позволяет эффективно проиллюстрировать функционирование генетического алгоритма. В качестве кода будем использовать двоичное представление аргументов функции. Это положение представляет собой фенотип алгоритма. Сам код будет представлять собой двоичную строку из 5 бит. Это генотип алгоритма. Целевой функцией будет непосредственно сама рассматриваемая функция, аргументом которой является число, чье двоичное представление использует алгоритм. Определим некоторые характеристики алгоритма. Пусть размер популяции будет 4, вероятность мутации 0,01, сам процесс мутации заключается в инверсии одного из битов строки, выбираемого случайно по равномерному закону. Операторы скрещивания и отбора аналогичны, описанным выше. Пусть на основе равномерного распределения создана исходная популяция из четырех особей, представленная в таблице 7.2. Табл. 7.2. Параметры исходной популяции особей
Предположим, что оператор отбора выбрал для производства потомков две пары строк (1, 2) и (2, 4). Работа оператора скрещивания проиллюстрирована в таблице 7.3. При этом в каждой паре разбиение на подстроки происходит независимо. Табл. 7.3. Иллюстрация работы оператора скрещивания
Пусть оператор мутации, несмотря на низкую вероятность, сработал для младшего бита потомка в строке 3 и данный код изменил свое значение с 10000 на 10001. Таким образом, популяция за счет порожденных потомков расширилась до восьми особей, представленных в таблице 7.4. Табл. 7.4. Исходная популяция и порожденные потомки
Оператор редукции далее сократит популяцию до исходного числа особей, исключив из нее те, чье значение целевой функции минимально. То есть будут исключены строки 1, 3, 4 и 5, и популяция первого поколения примет вид, представленный в таблице 7.5. Табл. 7.5. Новая популяция особей
На этом шаг работы генетического алгоритма закончится. Очевидно, что даже за эту одну итерацию качество популяции значительно улучшилось. Если в исходной популяции среднее значение целевой функции было 10,75, а ее минимальное значение составляло 2, то в популяции первого поколения среднее значение возросло до 19, а минимальное значение составило 14. Лучшее же решение увеличилось с 18 до 27 при оптимальном решении 31. Таким образом, данный пример наглядно иллюстрирует процесс улучшения как популяции в целом, так и наилучшего решения в частности в результате работы генетического алгоритма.
|
