Процесс работы генетического алгоритма

Общая схема работы генетического алгоритма представлена на рис. 5.12.

Формирование исходной популяции происходит, как правило, с использованием какого-либо случайного закона, на основе которого выбирается нужное количество точек поискового пространства. Исходная популяция может также быть результатом работы другого алгоритма оптимизации.

Рис. 5.12. Процесс работы генетического алгоритма

Основой порядка применения операторов отбора родительских пар и уничтожения особей является принцип «выживания сильнейшего». При случайном выборе особи для размножения вероятность ее участия в этом процессе вычисляется по формуле:

, (5.11)

где i – номер особи,

N – размер популяции,

f_i – значение целевой функции для i -й особи.

Целью поиска является нахождение особи с максимумом целевой функции. Очевидно, что одна особь может быть задействована в нескольких родительских парах.

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

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

Природный процесс наследования, т.е. передача свойств родителей потомкам, моделируется оператором скрещивания.

Простейший оператор скрещивания выполняется в два этапа. Пусть особь представляет собой строку из т элементов. На первом этапе равновероятно выбирается натуральное число k в диапазоне [1, т -1]. В соответствии с этим числом, называемым также точкой разбиения, обе исходные строки делятся на две подстроки. На втором этапе строки обмениваются своими подстроками, лежащими после точки разбиения, то есть элементами с k +1 по т. В результате получаются две новые строки, унаследовавшие частично свойства обоих родителей (рис. 5.13).

Рис. 5.13. Иллюстрация процесса скрещивания

Для того чтобы обеспечить постоянное появление новых особей в интересах расширения пространства поиска, вероятность применения оператора скрещивания обычно выбирается в пределах от 0,9 до 1.

Количество элитных особей определяется обычно по формуле:

К = N × (1 - Р), (5.12)

где К – количество элитных особей,

Р – вероятность применения оператора скрещивания,

N – размер популяции.

В случае использования стратегии элитизма скрещиванию подвергаются все выбранные родительские пары, несмотря на то, что вероятность применения оператора скрещивания меньше 1.

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

Вероятность мутации, в отличие от вероятности скрещивания выбирается, как правило, достаточно малой. Сам процесс мутации заключается в замене одного из элементов строки на другое значение. Это может быть перестановка двух элементов в строке, замена элемента строки значением элемента из другой строки, в случае битовой строки – инверсия одного из битов и др.

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

После завершения работы генетического алгоритма из конечной популяции выбирается особь, которая дает экстремальное (максимальное или минимальное) значение целевой функции и является, таким образом, результатом работы генетического алгоритма. За счет того, что конечная популяция лучше исходной, полученный результат представляет собой улучшенное решение.

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

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

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

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

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

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

Таблица 5.2

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

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

Таблица 5.3

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

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

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

Таблица 5.4

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

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

Таблица 5.5.

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

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

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

Дата добавления: 2014-12-29