Примеры оптимизации функции с помощью программы Evolver

Приложения эволюционных алгоритмов

Большинство приложений эволюционных алгоритмов, и осо­бенно генетических алгоритмов, касается оптимизационных задач. Простейшими из них можно назвать задачи, представленные в приме­рах 4.1 - 4.3, в примерах 4.5 и 4.6, а также просчитанные на компью­тере примеры из п. 4.9. В каждом из них оптимизируется целевая функция, заданная конкретной формулой, и используется характер­ное для основного генетического алгоритма двоичное кодирование хромосом.

Как уже упоминалось в п. 4.8.4, последующая модификация классического генетического алгоритма заключалась в представле­нии хромосом действительными числами. О таком способе кодирова­ния говорилось и в разд. 4.10. Одной из наиболее известных компью-

Глава 4. Генетические алгоритмы

4.11. Приложения эволюционных алгоритмов

терных программ, предназначенных для решения задач при помощи генетического алгоритма с кодированием действительными числами (real coding), считается программа Evolver [49] В этой программе применяется алгоритм с частичной заменой популяции (steady-state), при которой в каждый момент времени заменяется только одна особь. Селекция основана на ранговом методе (rank-based). Если го­ворить о так называемых генетических операторах, то в программе Evolver применяются два различных оператора скрещивания и два различных оператора мутации - отдельно для оптимизационных и для комбинаторных задач.

Программа Evolver взаимодействует с табличным процессо­ром Excel, в котором решаемая задача описывается в соответствую­щих ячейках таблицы путем задания ее параметров (переменных) и формулы функции приспособленности

Прежде чем перейти к примерам, дадим характеристику гене­тическим операторам, используемым программой Evolver в задачах оптимизации функции.

Скрещивание. Это равномерное скрещивание (uniform crossover), определенное аналогично примененному в п. 4.8.3, но для хромосом, состоящих из генов с действительными аллелями.

Скрещивание производится в соответствии с так называемым показателем скрещивания (crossover rate), определяющим, какой процент генов потомок унаследует от каждого родителя. В программе Evolver показатель скрещивания вводится пользователем и пред­ставляет собой число из интервала от 0,01 до 1,0. Например, значе­ние показателя скрещивания 0,8 означает, что потомок получит около 80 % генов со значениями (аллелями) такими же, как у первого роди­теля, а оставшееся количество (порядка 20 %) - унаследует от второ­го родителя. Если показатель скрещивания равен 1, то никакого скре­щивания практически не происходит, а образуются только так называ­емые клоны, т.е. хромосомы, идентичные родителям. По умолчанию в программе Evolver применяется значение показателя скрещивания, равное 0,5, что означает наследование примерно одинакового коли­чества генов от каждого родителя.

Мутация. Каждый ген в хромосоме представляет один пара­метр задачи. Следовательно, аллели соответствуют фенотипам, т.е. значениям конкретных переменных. Для каждого гена случайным об­разом выбирается число из интервала от 0 до 1, которое сравнивает­ся с так называемым показателем мутации (mutation rate). Если ра­зыгранное число меньше введенного значения показателя или равно ему, то выполняется мутация данного гена. Эта операция заключает­ся в замене значения гена другим, случайно выбранным числом из области допустимых значений параметра, соответствующего мутиру­ющему гену.

Вводимое пользователем значение показателя мутации пред­ставляет собой число из интервала от 0,0 до 1,0. Чем больше это зна­чение, тем большее количество генов подвергается мутации. Если по­казатель мутации равен 1, то мутации подвергаются 100 % генов, вы­бираемых случайным образом. С учетом того, что в программе Evolver мутация всегда производится после скрещивания, задание показателя мутации равным 1 означает, что в этом случае эффект скрещивания не имеет никакого значения. Очевидно, что если пока­затель мутации равен 0, то мутация вообще не производится. Как правило, значение показателя мутации задается в пределах от 0,06 до 0,2. Отметим, что определяемый таким образом показатель мута­ции представляет собой аналог вероятности мутации р_т, описанной в разд. 4.4. В то же время используемый в программе Evolver пока­затель скрещивания имеет смысл, отличающийся от введенной в разд. 4.4 вероятности скрещивания р_с. Значения как показателя му­тации, так и показателя скрещивания можно изменять в процессе вы­полнения программы Evolver.

В классическом генетическом алгоритме на каждой итерации обновляется вся популяция, что соответствует формированию оче­редного поколения. Применительно к программе Evolver можно гово­рить о последовательных «тактах» (trials) ее выполнения, причем на каждом такте изменяется только одна особь. Если популяция насчи­тывает N хромосом (особей, которые в описании программы называ­ются организмами), то N таких «тактов» составляют одну итерацию классического генетического алгоритма. Поэтому для того, чтобы при заданном количестве «тактов» выполнения программы Evolver найти соответствующее ему количество поколений (в терминологии класси­ческого генетического алгоритма), необходимо значение N разделить на количество особей в популяции. В представляемых далее приме­рах «такты» будут обозначаться символом f. Пример 4.21 демонстри­рует применение программы Evolver для оптимизации функции трех переменных.

Пример 4.21

С помощью программы Evolver найти минимум функции

f(x₁,x₂,x₃) = x₁² + x₂² + x₃² для целочисленных х-|, х₂, х₃ в интервале [-5, 5].

Вычисления производились для популяции размерностью N = 6. Использовалось значение показателя скрещивания равное 0,9 Это означает, что в результате скрещивания потомок наследует при­близительно (с округлением до целого) 90 % генов от первого родите­ля и остальные гены (около 10 %) - от второго родителя. Заметим, что для показателя скрещивания равного 1 будет наблюдаться такой же эффект, что и при отсутствии скрещивания, поскольку потомок будет наследовать все гены только от первого родителя. По этой причине

Глава 4 Генетические алгоритмы

при выбранном значении данного показателя, равном 0,9, скрещива­ние либо не будет проводиться вообще (точнее говоря, потомок ока­жется абсолютно идентичным своему первому родителю), либо скре­щивание будет выполнено, и потомок унаследует большую часть ге­нов от первого родителя. Для мутации выбрана величина показателя мутации равная 0,1, которая указывает, что значения 10 % генов (с ок­руглением до целого) должны подвергнуться случайным изменениям. С помощью программы Evolver сформирована следующая ис­ходная популяция:

И II [ 2 [ 5

3 -5 3 -4

5]

После шести «тактов», т.е. для f = 6, что соответствует одной итерации классического генетического алгоритма, получена популя­ция особей, упорядоченных по убыванию функции приспособленнос­ти так, как это показано на рис. 4.68.

Отметим, что в популяцию не входит особь [4 -3 5] со значени­ем функции приспособленности, равным 50. Она была исключена как «наихудшая» особь (с наибольшим значением функции приспособ­ленности), и на ее место введена копия особи [5 3 -4]. Эта особь так­же оказывается «наихудшей», поэтому она будет исключена на сле­дующем «такте» (f = 7). Популяции для f = 7 и f = 8 представлены на рис. 4.69 и 4.70.

На последнем месте (№ п/п = 6) размещается «наилучшая к данному моменту» особь, имеющая наименьшее значение функции приспособленности. На первом месте (№ п/п = 1) показана вновь вве­денная в популяцию особь. На рис. 4.69 это копия особи [5 4 2] из пре­дыдущей популяции (f = 6), а на рис. 4.70 - новая особь [0 -4 2], по­лученная в результате скрещивания с последующей мутацией от па­ры особей из популяции для f = 7. Выделенное прямоугольником зна­чение функции приспособленности в первой строке таблицы относит­ся к особи, исключаемой из популяции.

На рис. 4.71 и 4.72 представлены популяции для t = 17 и t = 18. Заметим, что f = 18 соответствует трем итерациям классического ге­нетического алгоритма. Новая особь в популяции на рис. 4.71 получе­на скрещиванием пары особей из предыдущей популяции (для f = 16), а новая особь в популяции на рис. 4.72 сформирована в результате мутации среднего гена особи [2 -4 0] из предыдущей популяции (для

На рис. 4.73 показана популяция для f = 41. Обратим внимание, что f = 42 соответствует семи итерациям (поколениям) классического генетического алгоритма. «Наилучшее к данному моменту» решение - это [-1 2 0] со значением функции приспособленности, равным 5.

Получение «наилучшего» решения, равного [0 0 0], с нулевым значением функции приспособленности возможно в случае, если при

4.77. Приложения эволюционных алгоритмов
№п/п	f(xi, х2, х3)	*1	х2	х3
	Ш\			-А
				-А
				2
		-1	-5
			-А
		-1		-3
Рис. 4.68. Популяция особей для t = 6 (пример 4.21).
№п/П	f(Xv Х2, Х3)	Х1	х2	х3
	ш
				-А
				2
		-1	-5
			-А
		-1		-3
Рис. 4.69. Популяция особей для t = 7 (пример 4.21)
№п/п	1{хь х2, х3)	Х-|	х2	^хз
	ш		-4
		-1	-5
			-А
		_■!		-3

Рис. 4.70. Популяция особей для t = 8 (пример 4.21).

		Глава 4. Генетические алгоритмы
№п/п	f(xi,x2>x3)	х,	х2	х3
	т		-4
			-4
			-4
			-4
			-4
		-1		-3
Рис. 4.71.Популяция особей для t = 17 (пример 4.21).
№п/п	f(x1, х2, х3)	^Х1	х2	х3
	[20l		-3
			-4
			-4
			-4
		-1		-3
			-4
Рис. 4.72.Популяция особей для г = 18	(пример 4.21).
№п/п	f(Xi, х2, хз)	XI	х2	х3
	Во]		-3
		-1
		-1
		-1
			-3
		-1

Рис. 4.73. Популяция особей для t = 41 (пример 4.21).

4.11. Приложения эволюционных алгоритмов

дальнейшем выполнении алгоритма произойдет мутация второго ге­на (замена -3, 3 или 2 на 0).

Следующий пример представляет собой обобщение предыду­щего примера за счет увеличения количества переменных и расшире­ния пространства поиска.

Дата добавления: 2015-06-04