Вероятностный генетический алгоритм для задач многокритериальной оптимизации

Таким образом, при решении многокритериальной задачи необходимо найти оптимум по К критериям, а сама задача формально записывается следующим образом:

У = f ( x ) = ( f 1 ( x ), f 2 ( x ),-, f K ( x )) ^ opt , g ^{( x} ) = ⁽ g 1^{( x} )> g 2^{( x} ). - . g r ^{( x} )) ^ ⁰ , h ( x ) = ( h r + 1 ( x ),K , h M ( x )) = 0 , где x = ( x i , x 2 ,..., x n ) e X - вектор решений, удовлетворяющий М ограничениям, y = ( y i , у 2 ,..., У к ) e Y - вектор целевых функций. При этом X означает пространство решений, а У- пространство целей или критериальное пространство.

Последние десятилетия получили развитие и продемонстрировали свою универсальность и применимость в сложных практических задачах так называемые эволюционные алгоритмы, в частности - генетический алгоритм (ГА) [1], которые представляют собой стохастичес кую оптимизационную процедуру, основанную на имитации процессов естественной эволюции. Е. С. Семенки-ным и Е. А. Соповым был предложен вероятностный генетический алгоритм (ВГА) безусловной оптимизации [2].

Работу ВГА в общем виде можно представить следующим образом.

• 1.    Инициализировать случайным образом популяцию решений.

• 2.    С помощью оператора селекции выбрать r наиболее пригодных индивидов текущей популяции (родителей). Вычислить распределение

P = { Р1^ . P n } ,

• 1    r ___

P j = ^P { x j = 1 } =; ^ x j , ^j = 1, n ^, . ri = 1

где n - длина хромосомы; x j -j-й бит i-го индивида.

• 1.    В соответствии с полученным распределением P = { p 1 ,K , p n } сформировать популяцию потомков с помощью датчика псевдослучайных чисел.

• 2.    Новые решения (потомки) подвергнуть мутации.

• 3.    Из популяции родителей и потомков сформировать новую рабочую популяцию.

• 4.    Повторять шаги 2-5 пока не выполнится условие остановки.

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

В данной работе для учета ограничений использовался метод динамического штрафа [3], выбранный после проведения сравнительного анализа эффективности различных методов учета ограничений в генетических алгоритмах.

Рассмотрим следующую задачу условной оптимизации для z-го критерия:

ft ( x ) ^ opt, i = 1, к ,

<

g j ^{( x} ) <  ⁰ , ^j = 1, r , h j ( x ) = 0, j = r + 1, M .

В методе динамического штрафа пригодность индивида х вычисляется по формуле

M R fitnessi (x) = fi (x) + 8Цt) E f/ (x)

j = 1

где t - номер текущего поколения; 8 = 1, если решается задача минимизации; 8 = - 1, если решается задача максимизации; f j ^{( x} ) - штраф за нарушениеу'-го ограничения; в - вещественное число; л( t ) = ( C ■ t )^а .

Штрафы f j ^{( x} ) вычисляются динамически, в зависимости от степени нарушения ограничений, по формуле [3]

f j ^{( x} ) = <

max { 0, g j ( x ) } , j = 1, r \ h j ^{( x} ^ j = r ⁺ 1, ^M

.

Параметры C , а, в подбираются на практике для каждой задачи индивидуально. Рекомендованные значения C = 0,5 , а = в = 2 [3].

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

Для анализа эффективности многокритериальной оптимизации вероятностными генетическим алгоритмом были выбраны четыре наиболее распространенные известные схемы: VEGA (Vector Evaluated Genetic Algorithm) [4], FFGA (Fonseca and Fleming’s Multiobjective Genetic Algorithm) [5], NPGA (Niched Pareto Genetic Algorithm) [6], SPEA (Strength Pareto Evolutionary Algorithm) [7].

Для задач условной оптимизации принцип Парето-доминирования следует применять в оштрафованном критериальном пространстве У.

Сравнение эффективности стандартного ГА и ВГА. Сравнение эффективности алгоритмов проводилось на следующих тестовых задачах условной оптимизации

Задача 1.

<

f 1 ( x , У ) = ( x — 6)² + ( y — 4)² ^ min f 2 ( x , У ) = ( x + 2)² + ( У — 5)² ^ min g 1 ( x , y ) = ( x - 1)² + ( y - 4)² <  4 _ g 2 ( x , y ) = ( x - 3)² + ( y - 4)² <  6,25.

Задача 2.

f 1 ( x , y ) = ( x - 6)² + ( y - 4)² ^ min f 2 ( x , y ) = ( x + 2)² + ( y - 5)² ^ min f з ( x , y ) = ( x - 4)² + ( y + 4)² ^ min

g1( x, y) = (x - 2)2 + (y - 2)2 < 10,24 g2(x, y) = (x - 5)2 + (y -1)2 < 16 g3(x,y) = (x - 3)2 + (y - 4)2 < 9 f1(x, y) = (x -1)2 + (y +1)2 ^ min f2(x,y) = (x + 2)2 +(y-2)2 ^min f$(x, y) = (x - 3)2 + (y - 4)2 ^ min f Дx,y) = (x - 4)2 + (y - 2)2 ^ min g1(x,y) = (x +1.8)2 + (y - 2)2 > 4 g2(x,y) = (x -1)2 + (y - 4.5)2 > 4

• g з ( x , y ) = ( x - 5.2)² + ( y - 2)² >  9 . g 4 ( x , y ) = ( x - 1)² + ( y + 2)² >  9 g 5 ( x , y ) = ( x - 1)² + ( y - 2)² <  6,25

Задача 3.

Задача 4.

f1(x, y) = (x -1)2 + (y +1)2 ^ min f 2(x,y) = (x + 2)2 + (y - 2)2 ^ min ft(x, y) = (x - 3)2 + (y - 4)2 ^ min f4(x, y) = (x - 4)2 + (y - 2)2 ^ min g1(x, y) = x2 + (y - 6)2 < 4

.g 2^{( x} , y ) = ^{( x + 2) 2 + (} y ^{- 5) 2}

< 4.

Особенность последней задачи состоит в том, что допустимая область лежит вне множества Парето.

В качестве исследуемых характеристик были выбраны: разброс точек в пространствахАи У, процент Паре-товских точек (%), процент допустимых точек (% доп.). В задачах 1и 4 множество Парето представляет собой отрезок и части окружностей соответственно, поэтому для этих задач дополнительно исследовалось среднее расстояние (Ср.р) до отрезка и окружностей. Поскольку алгоритмы являются стохастическими, то для каждой настройки алгоритмов эксперименты проводились по 50 раз и исследуемые характеристики усреднялись. Для проверки того, являются ли различия между алгоритмами случайными, применялся тест Колмогорова-Смирнова (Kstest) с5% уровнем значимости. Kstest = 0, если различия случайны, иначе Kstest = 1.

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

Метод SPEA представлен в табл. 1-4.

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

Метод NPGA представлен в табл. 5-8.

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

Таблица 1

Численные характеристики наилучших настроек

№	Стандартный ГА					Вероятностный ГА
	X	Г	%	% доп.	СР.Р	X	Г	%	% доп.	СР.Р
1	0,025 3	0,020 5	0	95,933 3	0,107 8	0,025 4	0,020 5	0	96,328 7	0,107 4
2	0,055 3	0,034 8	94,933 3	98,533 3		0,055 4	0,035 0	93,400 0	98,600 0
3	0,036 8	0,022 0	86,560 9	86,496 6		0,036 4	0,021 7	83,240 9	84,664 4
4	0,008 2	0,006 5	0	73,835 2	0,003 1	0,007 7	0,006 1	0	74,591 6	0,004 2

Таблица 2

№	Kstest
	X	Г	% Парето	% доп.	СР.Р
1	0	0		0	0
2	0	0	0	0
3	0	0	1	0
4	0	0		0	1

Таблица 3

№	СтандаРтный ГА					ВеРоятностный ГА
	X	Г	%	% доп.	СР.Р	X	Г	%	% доп.	СР.Р
1	0,024 2	0,020 2	0	94,933 3	0,136 2	0,024 0	0,020 2	0	94,666 7	0,130 6
2	0,054 2	0,034 7	93,8000	97,533 3		0,054 4	0,035 0	93,8667	97,933 3
3	0,035 2	0,021 0	84,7264	83,031 2		0,034 9	0,020 8	82,213 8	82,793 1
4	0,005 5	0,004 5	0	60,943 4	0,005 0	0,006 3	0,005 1	0	65,531 1	0,0049

Таблица 4

№	Kstest
	X	Г	% ПаРето	% доп.	СР.Р
1	0	0		0	0
2	0	0	0	0
3	0	0	0	0
4	0	0		0	0

Численные характеристики наилучших настроек

Таблица 5

№	СтандаРтный ГА					ВеРоятностный ГА
	X	Г	%	% доп.	СР.Р	X	Г	%	% доп.	СР.Р
1	0,032 5	0,017 0	0	93,790 9	0,183 8	0,030 7	0,016 6	0	95,732 1	0,2864
2	0,048 9	0,030 8	47,862 1	92,8940		0,047 6	0,030 1	61,698 0	92,847 7
3	0,031 6	0,018 1	92,713 8	92,713 8		0,023 1	0,013 2	23,072 0	93,590 5
4	0,003 3	0,003 3	0	61,908 2	0,026 7	0,001 5	0,001 5	0	63,961 8	0,051 1

Таблица 6

№	Kstest
	X	Г	% ПаРето	% доп.	СР.Р
1	1	1		1	1
2	0	0	1	1
3	1	1	1	1
4	0	0		0	0

Таблица 7

Численные характеристики наихудших настроек

№	СтандаРтный ГА					ВеРоятностный ГА
	X	Г	%	% доп.	СР.Р	X	Г	%	% доп.	СР.Р
1	0,019 3	0,015 8	0	38,418 6	0,523 0	0,015 1	0,013 1	0	48,683 7	0,453 7
2	0,042 3	0,026 8	91,3919	48,436 9		0,041 6	0,026 5	92,685 5	62,506 5
3	0,022 4	0,012 3	80,422 6	17,824 8		0,020 6	0,0113	85,478 0	23,072 0
4	0,000 0	0,0000	0	0,343 1	0,2240	0,000 0	0,0000	0	0,445 3	0,1212

Статистические характеристики наилучших настроек

Численные характеристики наихудших настроек

Статистические характеристики наихудших настроек

Статистические характеристики наилучших настроек

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

Метод FFGA представлен в табл. 9-12.

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

Метод PEGA представлен в табл. 13-16.

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

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

Таким образом, показано, что ВГА справляется с решением тестовых задач не хуже стандартного ГА, а в некоторых случаях превосходит его. Кроме того, ВГА содержит меньше настраиваемых параметров (отсутствует

Таблица 8

Статистические характеристики наихудших настроек

№	Kstest
	X	У	% Парето	% доп.	Ср.р
1	0	0		1	1
2	0	0	1	0
3	1	1	1	1
4	1	1		0	1

Таблица 9

Численные характеристики наилучших настроек

№	Стандартный ГА					Вероятностный ГА
	X	У	%	% доп.	СР.Р	X	У	%	% доп.	Ср.р
1	0,028 7	0,016 1	0	96,649 8	0,075 0	0,025 3	0,015 9	0	97,279 4	0,150 5
2	0,051 2	0,032 7	50,188 8	95,267 4		0,049 7	0,031 4	56,878 9	95,781 2
3	0,029 9	0,017 3	28,852 3	94,275 2		0,022 7	0,012 6	44,398 4	93,823 7
4	0,003 2	0,0027	0	74,899 6	0,018 9	0,001 4	0,001 4	0	72,016 0	0,045 8

Таблица 10

Статистические характеристики наилучших настроек

№	Kstest
	X	У	% Парето	% доп.	Ср.р
1	1	0		0	1
2	1	1	1	0
3	1	1	1	0
4	1	1		0	0

Таблица 11

Численные характеристики наихудших настроек

№	Стандартный ГА					Вероятностный ГА
	X	У	%	% доп.	Ср.р	X	У	%	% доп.	Ср.р
1	0,014 4	0,012 4	0	52,834 1	0,385 9	0,012 1	0,010 7	0	65,999 3	0,303 2
2	0,038 2	0,023 9	94,255 7	48,656 6		0,033 7	0,021 0	95,679 6	57,555 4
3	0,018 0	0,009 7	92,991 7	23,082 7		0,015 4	0,008 3	92,135 5	37,728 5
4	0	0	0	1,044 2	0,212 2	0,000 5	0,000 3	0	2,949 1	0,160 2

Таблица 12

Статистические характеристики наихудших настроек

№ Kstest X У % Парето % доп. Ср.р 1 1 0 1 1 2 1 1 1 1 3 0 0 0 1 4 0 0 0 0 оператор скрещивания), за счет чего уменьшается время работы алгоритма.

Все это делает ВГА перспективным для решения реальных практических задач [8].