Примеры решения задач. Пример поиска максимума одномерной функции

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

В качестве кода будем использовать двоичное представление аргументов функции. Это положение представляет собой фенотип нашего алгоритма. Сам код будет представлять собой двоичную строку из 5 бит. Это генотип алгоритма. Целевой функцией будет непосредственно сама рассматриваемая функция, аргументом которой является число, чье двоичное представление использует алгоритм.

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

Пусть на основе равномерного распределения создана исходная популяция из четырех особей, представленная в таблице 1

Таблица 1

Номер строки	Код генотипа	Значение целевой функции	Вероятность участия в размножении
			11/43
			18/43
			2/43
			12/43
		Сумма 43

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

Пропорциональный простейший отбор (рулетка) выбирает n особей после n запусков. Колесо рулетки содержит по одному сектору для каждого гена популяции. Размер сектора пропорционален вероятности участия.

Таблица 2

№ строки	Родители	Потомки	Значение целевой функции для потомков
	0*1011
	1*0010
	100*10
	011*00

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

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

Таблица 3

№ строки	код	Значение целевой функции
Исходная популяция
Порожденные потомки

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

Таблица 4

№ строки	Код	Значение целевой функции	Вероятность участия в процессе размножения
			18/ 76
			27/ 76
			17/ 76
			14/ 76

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

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