ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Journal influence

Higher Attestation Commission (VAK) - К1 quartile
Russian Science Citation Index (RSCI)

Bookmark

Next issue

4
Publication date:
09 September 2024

Study of differential adaptive genetic algorithm for conditional optimization problems solving

The article was published in issue no. № 1, 2014 [ pp. 82-86 ]
Abstract:The article discusses standard methods for solving constrained optimization problems based on artificial dete-rioration of the objective function value when violating given constraints. The methods of assigning dynamic and adaptive penalties are described. The paper considers selection modifications in a differential adaptive genetic algorithm based on the behavioral memory method for adapting it to this class of problems. The paper presents the results of study a combination of standard methods and observable differential algorithm on a test functions set that show the most efficient combination of dynamic penalty and algorithm modification. The algorithm modification is presented in the possibility of a transition to S k subset only solutions that satisfy all the constraints. Allocation of two subsets determines low efficiency of adaptive penalties due to inability to obtain complete information on the entire set of decisions and frequent changes in S o subset. Based on a comparison of the data and test results of other genetic algorithms, it is concluded that the differential algorithm is better av-eraged performance of the classical algorithm, but can yield better at non-optimal settings, as well as comparable to the co-evolutionary algorithm. This allows using differentiated adaptive genetic algorithm to solve practical optimization problems.
Аннотация:Рассмотрены стандартные методы решения задач условной оптимизации на основе искусственного ухудшения значения целевой функции при нарушении заданных ограничений, а именно методов назначения динамических и адаптивных штрафов. Дано описание модификации селекции в дифференцированном адаптивном генетическом алгоритме на базе метода поведенческой памяти для его адаптации к данному классу задач. Приводятся результаты ис-следования эффективности решения задач условной оптимизации дифференцированным адаптивным генетическим алгоритмом в сочетании со стандартными методами учета ограничений на тестовом множестве функций. По результатам исследования делается вывод о том, что наибольшую эффективность показывает комбинация динамического штрафа и модификации алгоритма, выраженной в переходе в подмножество S k только тех решений, которые удовлетворяют заданным критериям. Это также обусловливает низкую эффективность применения метода адаптивных штрафов в сочетании с дифференцированным адаптивным генетическим алгоритмом. По результатам сравнительно-го анализа эффективности делается вывод о том, что дифференцированный адаптивный генетический алгоритм лучше усредненного по эффективности классического генетического алгоритма, но может уступать лучшему при неоптимальных настройках, а также сравним с коэволюционным алгоритмом, что позволяет применять его при решении практических задач оптимизации.
Authors: Zhukov V.G. (vadimzhukov@mail.ru) - Academician M.F. Reshetnev Siberian State Aerospace University, Krasnoyarsk, Russia, Ph.D, Parotkin N.Yu. (U-571_sos@mail.ru) - Academician M.F. Reshetnev Siberian State Aerospace University, Krasnoyarsk, Russia,
Keywords: behavioral memory, penalty functions, differentiated adaptive genetic algorithm, constrained optimization
Page views: 8588
Print version
Full issue in PDF (7.83Mb)
Download the cover in PDF (1.01Мб)

Font size:       Font:

При решении практических задач нахождения оптимальных параметров какого-либо процесса или настроек системы требуется соблюдение ряда ограничений, накладываемых на диапазоны их изменения, обусловленные физической природой объекта или экономическими требованиями. Кроме того, зачастую нельзя с достаточной точностью описать реальную систему без использования алгоритмических выражений, что приводит к невозможности ее оптимизации только математическими методами. Одним из способов решения таких задач, относящихся к задачам условной оптимизации, является аппарат эволюционных алгоритмов, в частности генетические алгоритмы (ГА). Для этого к ним применяется ряд методов, воздействующих как на итоговое значение целевой функции, отражающей качество найденного решения, так и на состав множества решений, которыми оперирует ГА. Следовательно, разработка новых, более эффективных методов учета ограничений в эволюционных алгоритмах и решения задач условной оптимизации является актуальной для научных и технических исследований.

Методы решения задач условной оптимизации

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

                                         (1)

где f(x) – целевая функция; gj(x)£0, hj(x)=0 – ограничения задачи; m – общее количество ограничений. Тогда итоговая пригодность индивида x может быть вычислена по формуле

,               (2)

где t – номер текущего поколения; d=1, если решается задача минимизации; d= –1, если решается задача максимизации; fj(x) – штраф за нарушение j-го ограничения; β – вещественное число.

В методе динамических штрафов [1] вычисление значения fj(x) происходит динамически, в зависимости от степени нарушения ограничений, по формуле для t-й итерации, а значение l(t)=(C×t)a:

Подпись:  
Обобщенная схема ДАГА
                        (3)

Рекомендуемые значения параметров C=0,5, a=b=2 могут изменяться в зависимости от зада- чи и влияют на эффективность нахождения решения [2].

Развитием данного метода является метод адаптивных штрафов [1, 2], в котором λ(t) зависит не только от номера итерации, но и от количества попаданий лучшего представителя популяции на каждом шаге в допустимую или недопустимую область:

         (4)

где  – лучший индивид i-й популяции; b1, b2>1 и b1¹b2.

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

Описанные методы универсальны и подходят для применения в любом ГА без его существенной модификации. Кроме данного вида методов, воздействующих непосредственно на итоговое значение целевой функции, существует ряд механизмов, влияющих на структуру и порядок работы самого алгоритма для повышения его эффективности при решении задач условной оптимизации [2–4]. Одним из них является метод поведенческой памяти [5]. Суть его в последовательном увеличении количества критериев, которым будет удовлетворять заданная часть популяции, при итеративной работе генетических операторов поиска.

Модификации дифференцированного адаптивного ГА для решения задач условной оптимизации

Поскольку решение задач условной однокритериальной оптимизации является более трудоемким, чем однокритериальных безусловных задач, целесообразно использовать эволюционные алгоритмы, обладающие большей эффективностью, чем классический ГА. В работе [6] предлагается новый метод взаимодействия с пространством поиска и способом накопления информации о решении задачи. На его основе разработан дифференцированный адаптивный ГА (ДАГА), обобщенная схема которого представлена на рисунке.

Перед описанием предлагаемых модификаций ДАГА для решения задач условной оптимизации приведем его алгоритм, используемый при решении однокритериальных безусловных задач оптимизации. На первом этапе общая популяция решений делится на две субпопуляции в отношении Sk/So, определяемом пользователем. Задачей Sk-субпопуляции является накопление хороших, апробированных в процессе работы алгоритма решений, а So – активное исследование поискового пространства и тестирование качества найденных решений. Вводится параметр Tlife, определяющий количество раундов алгоритма, в которых индивид содержался в популяции в неизменном состоянии. В изначальной случайно сгенерированной популяции выделяются N/Sk лучших индивидов, формирующих Sk-субпопуляцию, остальные переходят в So. В каждом раунде алгоритма  раз формируется потомок в So. Для этого случайно выбирается -индивид из Sk. Второй -индивид выбирается по турнирной схеме из So, то есть формируется выборка из n индивидов, среди которых выбирается один индивид с наилучшим значением целевой функции. При ее равных значениях – с наибольшим значением Tlife. После определения пары  формируется потомок путем скрещивания хромосом и применения оператора мутации. Далее происходит сравнение по значению по целевой функции потомка и . Если потомок лучше, то он замещает , а его параметр Tlife обнуляется. Если лучше , то потомок отбрасывается, а Tlife  увеличивается на 1.

По завершении процедуры формирования потомков изменяется соотношение количества индивидов Sk/So по периодическому закону. Далее осуществляется поиск индивидов для сохранения их генетической информации в Sk нового поколения. Для этого просматриваем всех индивидов  и отбираем тех, у которых время жизни больше значения параметра Tlife, установленного пользователем, и наихудшее значение целевой функции. После этого сравниваем значение пригодности найденного -индивида со значением -индивида. Если у -индивида лучшее значение, заменяем им -индивида, при этом обнуляем у него Tlife. После проверки всех -индивидов увеличиваем время жизни у всех -индивидов на 1. При недостатке индивидов в Sk они добавляются из So только по критерию пригодности.

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

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

Второй способ предполагает внесение изменений в сам алгоритм оптимизации. Поскольку в ДАГА применяется разделение на две субпопуляции, переход между которыми возможен при доказанной в течение нескольких поколений успешности найденного решения, к нему может быть применена идея, заложенная в методе поведенческой памяти [5]. А именно, в субпопуляцию Sk индивиды будут отбираться по следующим параметрам: удовлетворение наибольшему количеству критериев, наибольшее значение параметра Tlife.

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

Исследование эффективности ГА решения задач условной оптимизации

Подпись: Таблица 1
Множество тестовых функций
№	Функция	Ограничения	Экстремум	Решение
1	 
 
min	  
 
2	 
 
max	  
 
3	 
 
max	 
 
4	 
 
max	  
 
5	 
 
min	  
 
6	 
 
min	  
 

Внесенные модификации были проверены на тестовых функциях (табл. 1), для которых ин- тервал изменения значений переменных равен [–10, 10], а шаг дискретизации – 0,001.

При проведении исследований были определены следующие начальные условия и параметры алгоритма: для метода динамических и адаптивных штрафов коэффициенты С=0,5, α=β=2, коэффициенты для адаптивных штрафов: β1=1,4, β2=1,2, k=3. Использовалась генерация начальных популяций множеством допустимых решений. Общее количество индивидов в субпопуляциях Sk и So составляло 100, количество поколений также равнялось 100, использовалось одноточечное и двухточечное скрещивание. Проводилось исследование штраф­ных функций отдельно и в сочетании их с модификацией алгоритма.

Подпись: Таблица 2
Результаты исследования эффективности ДАГА
Номер 
функции	Штраф	Доля С в популяции 5	Доля С в популяции 10
		Одноточечная	Двухточечная	Одноточечная	Двухточечная
		n (%)	S	n (%)	S	n (%)	S	n (%)	S
1	Адаптивный	100	59,40	100	55,60	100	54,00	100	43,40
	Динамический	100	42,60	100	57,20	100	45,60	100	54,20
	Адаптивный МА	99	57,62	100	52,82	100	51,84	99	40,80
	Динамический МА	100	40,47	100	56,06	100	43,78	100	50,95
2	Адаптивный	100	53,00	100	60,20	100	70,20	100	57,00
	Динамический	100	52,60	100	62,80	100	54,40	100	59,40
	Адаптивный МА	100	54,82	99	59,60	100	66,69	100	56,43
	Динамический МА	99	56,92	100	62,17	100	53,31	100	49,62
3	Адаптивный	19	79,40	17	67,20	21	64,60	20	63,40
	Динамический	31	63,40	32	73,20	27	59,40	38	72,40
	Адаптивный МА	20	77,81	18	62,50	22	61,37	21	60,86
	Динамический МА	36	61,50	40	69,54	29	57,02	39	67,33
4	Адаптивный	97	71,60	99	67,60	98	69,20	100	52,00
	Динамический	100	67,60	100	63,00	100	62,80	100	60,00
	Адаптивный МА	100	68,74	100	65,57	100	68,51	99	50,96
	Динамический МА	99	66,25	100	58,74	100	59,66	100	59,40
5	Адаптивный	55	62,20	66	66,20	45	59,60	57	62,00
	Динамический	69	74,20	72	66,00	52	60,20	61	69,00
	Адаптивный МА	61	60,96	71	64,88	48	56,02	60	60,76
	Динамический МА	70	69,75	78	65,34	55	59,60	67	64,86
6	Адаптивный	31	59,60	31	56,80	30	68,60	33	54,40
	Динамический	40	61,40	42	71,40	37	71,60	39	60,80
	Адаптивный МА	32	56,02	33	53,39	32	66,54	34	51,68
	Динамический МА	45	60,79	42	70,69	42	69,45	43	57,76
Таблица 3
Результаты сравнительного анализа эффективности алгоритмов
Номер 
функции	Наихудший ГА	Средний ГА	Наилучший ГА	Коэволюция	ДАГА
	n	S	n	S	n	S	n	S	n	S
1	0,016	69,8	0,249	64,1	0,736	70,8	0,990	57,8	1,00	56,06
2	0,190	56,0	0,735	59,6	1,000	62,6	1,000	27,0	1,00	62,17
3	0,000	-	0,066	73,2	0,292	73,4	0,990	48,0	0,40	69,54
4	0,014	57,2	0,550	61,5	1,000	68,0	0,982	39,4	1,00	58,74
5	0,000	-	0,080	70,5	0,320	71,0	0,996	50,2	0,78	65,34
6	0,028	16,5	0,172	50,8	0,372	75,4	0,340	59,0	0,42	70,69
Оценка эффективности алгоритма производилась по параметрам надежности и скорости поиска решений. Под надежностью понимается доля запусков из 100, при которых был найден глобальный оптимум функции на интервале, удовлетворяющий заданным ограничениям. Скорость определяется как усредненный номер поколения, на котором был найден глобальный оптимум. Результаты исследования эффективности ДАГА при решении однокритериальных задач условной оптимизации на множестве тестовых функций (табл. 1) приведены в таблице 2.

Проведем сравнение эффективности ДАГА с результатами исследований из [7] (табл. 3), которые были получены при тех же параметрах тестирования алгоритмов и для тех же функций.

По полученным результатам и их сравнительному анализу с [7] можно сделать следующие выводы:

–      для ДАГА наибольшую эффективность показывает сочетание метода динамического штрафа и модификации алгоритма; сниженная эффективность адаптивных штрафов связана с наличием двух субпопуляций и частого изменения состава подмножества So;

–      при сравнении с классическим ГА можно заключить, что ДАГА лучше усредненного по эффективности классического алгоритма, но может уступать лучшему при неоптимальных настройках;

–      при сравнении с коэволюционным алгоритмом, являющимся также развитием классического ГА, можно сказать, что данные алгоритмы сравнимы по эффективности.

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

Литература

1.     Michalewicz Z., Schoenauer M. Evolutionary algorithms for constrained parameter optimization problems. Evolutionary Computation, no. 4 (1), 1996, pp. 1–32.

2.      Mezura-Montes E., Coello Coello C.A. Constraint-handling in nature-inspired numerical optimization: Past, present and future. Swarm and Evolutionary Computation. 2011, vol. 1, no. 4, pp. 173–194.

3.     Yeniay Ö. Penalty function methods for constrained  optimization with genetic algorithms. Mathematical and Computational Applications. 2005, vol. 10, no. 1, pp. 45–56.

4.     Can M., Kusakci O.A. Constrained optimization with evolutionary algorithms: a comprehensive review. Southeast Europe journal of soft computing. 2012, vol. 1, no. 2, pp. 16–24.

5.     Schoenauer M., Xanthakis S. Proc. 5th Int. Conf. on Gene­tic Algorithms, Urbana-Champaign, IL, USA, 1993, pp. 473–580.

6.     Жуков В.Г., Паротькин Н.Ю. Дифференцированный адаптивный генетический алгоритм // Вестн. НГУ: сер. Информационные технологии. Новосибирск, 2011. Т. 9. Вып. 1. С. 5–11.

7.     Сергиенко Р.Б. Автоматизированное формирование нечетких классификаторов самонастраивающимися коэволюционными алгоритмами: автореф. дис. … канд. техн. наук. Красноярск: СФУ, 2010. 20 с.

References

1.     Michalewicz Z., Schoenauer M. Evolutionary algorithms for constrained parameter optimization problems. Evolutionary Computation, 1996, no. 4 (1), pp. 1–32.

2.      Mezura-Montes E., Coello Coello C.A. Constraint-hand­ling in nature-inspired numerical optimization: Past, present and future. Swarm and Evolutionary Computation. 2011, vol. 1, no. 4, pp. 173–194.

3.     Yeniay Ö. Penalty function methods for constrained  optimization with genetic algorithms. Mathematical and Computational Applications. 2005, vol. 10, no. 1, pp. 45–56.

4.     Can M., Kusakci O.A. Constrained optimization with evolutionary algorithms: a comprehensive review. Southeast Europe journal of soft computing. 2012, vol. 1, no. 2, pp. 16–24.

5.     Schoenauer M., Xanthakis S. Constrained GA optimization. Proc. of the 5th Int. Conf. on Genetic Algorithms. Urbana-Champaign, IL, USA, 1993, pp. 473–580.

6.     Zhukov V.G., Parotkin N.Yu. A differential adaptive genetic algorithm. Vestnik NGU [Bulletin of the Novosibirsk State Univ.]. Novosibirsk, 2011, vol. 9, iss. 1, pp. 5–11 (in Russ.).

7.     Sergienko R.B. Avtomatizirovannoe formirovanie nechet­kikh klassifikatorov samonastraivayushchimisya koevolyutsionnymi algoritmami [Automated forming of fuzzy classificators by self-adjusting coevolution algorithms]. Extended abstract of PhD diss. (Engineering), Siberian Fed. Univ. Publ., Krasnoyarsk, 2010, 20 p. (in Russ.).


Permanent link:
http://swsys.ru/index.php?page=article&id=3763&lang=en
Print version
Full issue in PDF (7.83Mb)
Download the cover in PDF (1.01Мб)
The article was published in issue no. № 1, 2014 [ pp. 82-86 ]

Perhaps, you might be interested in the following articles of similar topics: