РАЗРАБОТКА ГИБРИДНОГО АЛГОРИТМА РЕШЕНИЯ ОПТИМИЗАЦИОННОЙ ЗАДАЧИ С НЕЛИНЕЙНОЙ ЦЕЛЕВОЙ ФУНКЦИЕЙ

Евич Л.Н.¹, Остроух Е.Н.², Панасенко П.А.³

¹ORCID: 0000-0002-7886-0954, кандидат физико-математических наук, доцент,

²кандидат технических наук, доцент,

Донской государственный технический университет, Россия, Ростов-на-Дону;

³кандидат технических наук,

Краснодарское высшее военное училище имени генерала армии С.М. Штеменко, Россия, Краснодар;

Статья написана при поддержке гранта РФННННиФИ №16-01-00391 «Разработка комбинированных алгоритмов для решения распределительных и транспортных задач с использованием идеологии искусственных иммунных систем и биоинспирированных алгоритмов»

РАЗРАБОТКА ГИБРИДНОГО АЛГОРИТМА РЕШЕНИЯ ОПТИМИЗАЦИОННОЙ ЗАДАЧИ С НЕЛИНЕЙНОЙ ЦЕЛЕВОЙ ФУНКЦИЕЙ

Аннотация

Рассматриваются популяционные алгоритмы задачи глобальной оптимизации с нелинейной целевой функцией. Представлен сравнительный анализ алгоритма искусственной пчелиной колонии и гибридного алгоритма искусственной пчелиной колонии с гравитационным алгоритмом. Произведен анализ производительности работы алгоритмов на основе сферической функции, функций Розенброка, Гривонка, Растригина, Швефеля. Подтверждена эффективность рассмотренного гибридного алгоритма по сравнению с алгоритмом  искусственной пчелиной колонии.

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

Evich L.N.¹, Ostroukh E.N.², Panasenko P.A.³

¹ORCID: 0000-0002-7886-0954, PhD in Physics and Mathematics, Associate professor,

²PhD in Engineering, Associate professor,

Don State Technical University, Russia, Rostov-on-Don;

³PhD in Engineering,

Krasnodar Higher Military School named after S.M. Shtemenko, Russia, Krasnodar;

The work was supported by the grant of RFNNNN and FI No. 16-01-00391 "Development of combined algorithms for the solution of distribution and transport problems with the use of the idea of artificial immune systems and bioinspired algorithms"

DEVELOPMENT OF HYBRID ALGORITHM FOR SOLUTION OF OPTIMIZATION PROBLEM WITH NONLINEAR TARGET FUNCTION

Abstract

The paper considers population algorithms of a global optimization problem with a nonlinear objective function. A comparative analysis of the algorithm of an artificial bee colony and the hybrid algorithm of an artificial bee colony with a gravitational algorithm is presented. The authors analyzed the performance of the algorithms based on the spherical function, Rosenbrock, Grivonck, Rastrigin, and Schwefel functions. The efficiency of the considered hybrid algorithm is confirmed in comparison with the algorithm of the artificial bee colony.

Keywords: optimization algorithms, hybrid algorithms, artificial bee colony algorithm, gravitational algorithm.

Введение

Одним из направлений развития решения задач поисковой оптимизации с нелинейной целевой функцией является гибридизация различных поисковых алгоритмов. На сегодняшний день известно большое количество различных гибридных алгоритмов с различными реализациями стратегий гибридизации. В работах Рендерса (J. Renders) предложены гибридные методы с использованием генетических алгоритмов глобальной оптимизации [1], [2]. Свое дальнейшее развитие гибридные алгоритмы получили при изучении сочетания разнообразных моделей с различными методами в работах [3], [4], [5], [6].

Целью гибридизации алгоритмов является использование сильных сторон каждого из участвующих в нем алгоритмов.  В настоящей работе рассматривается интегративная стратегия последовательной гибридизации типа процессор/постпроцессор. В качестве препроцессора выступает алгоритм искусственной пчелиной колонии (Artificial bee colony, ABC), обеспечивающий широту (диверсификацию) поиска. Алгоритм гравитационного поиска (Gravitational Search Algorithm, GSA) по сравнению со многими генетическими алгоритмами имеет большую скорость сходимости (интенсификацию поиска). В то же время, при оптимизации мультимодальных функций метод быстро сходится к локальному оптимуму. В связи с этим гибридизация  алгоритма пчелиной колонии с гравитационным алгоритмом позволит, с одной стороны за счет широты поиска на первых итерациях определить зоны локальных минимумов, и на втором этапе  осуществить быстрый поиск  глобального оптимума. Переход от пчелиного к гравитационному алгоритму осуществляется после выполнения t итераций алгоритма роя пчел. Гравитационный алгоритм позволяет оптимизировать локальные экстремумы, найденные в результате выполнения алгоритма роя пчел. На основе анализа проводится сравнительная характеристика ABC алгоритма с гибридным алгоритмом (ABCGSA).Одним из направлений развития решения задач поисковой оптимизации с нелинейной целевой функцией является гибридизация различных поисковых алгоритмов. На сегодняшний день известно большое количество различных гибридных алгоритмов с различными реализациями стратегий гибридизации. В работах Рендерса (J. Renders) предложены гибридные методы с использованием генетических алгоритмов глобальной оптимизации [1], [2]. Свое дальнейшее развитие гибридные алгоритмы получили при изучении сочетания разнообразных моделей с различными методами в работах [3], [4], [5], [6].

Постановка задачи и её решение на основе гибритных алгоритмов.

Рассмотрим детерминированную задачу оптимизации

где вектор  варьируемых параметров размерности |X|;   — |X|-мерное арифметическое пространство;   — целевая функция; — искомое оптимальное решение; — искомое экстремальное значение целевой функции.

Основные понятия пчелиного алгоритма. Самые ранние упоминания о пчелином алгоритме датируются 2005 г. в работах   Карабога (D. Karaboga) [7] и Фама (D. Pham) [8]. Позже алгоритм неоднократно модифицировался и применялся для  решения различных задач оптимизации и синтеза [9], [10], [11], [12, C. 179], [13].  В основе алгоритма лежат принципы поведении роя пчел в поисках местности с наибольшим количеством источников нектара. Некоторое количество пчел-разведчиков начинают поиск со случайных направлений и с некоторыми случайными векторами скоростей. Каждая пчела-разведчик запоминает места с наибольшей концентрацией источников нектара и по возвращении в улей сообщает о них другим пчелам колонии. На найденные участки отправляются рабочие пчелы. Количество рабочих пчел, вылетающих в каждом направлении,  может зависеть от перспективности участка. Пчелы, облетая разные участки, сравнивают новые места с местами найденными ими ранее. При этом скорость полета пчел увеличивается в направлении участков с наибольшим количеством источников нектара.  В итоге, весь рой сосредотачивается на участке с наибольшим количеством источников нектара. Отбор перспективных (с максимальным и близкими к ним значениями источников нектара) участков осуществляется на основе фитнесс-функции, которая учитывает свойства каждой пчелы.

Основные понятия гравитационного алгоритма. Гравитационный алгоритм был впервые предложен Рашеди (E. Rashedi)  в 2009 г. [14]. На сегодняшний день гравитационный алгоритм исследован в меньшей мере. Как правило, в работах различных авторов используется только его  основная концепция [15], [16], [17]. Данный алгоритм базируется на законах гравитации и взаимодействия масс. Закон гравитации используется в некоторой модификации. В частности, полагается, что сила F гравитационного притяжения между двумя частицами массами  и  прямо пропорциональна произведению их масс и обратно пропорциональна расстоянию R между ними:  .

В алгоритме с ростом числа итераций гравитационную постоянную G(t) уменьшают согласно закону: , где  — значение гравитационной постоянной в начальный момент времени,   β— свободный параметр алгоритма (β⊂(0,1)) , используется для контроля точности.

Ускорение a, приобретаемое частицей, прямо пропорционально силе гравитационного притяжения, и обратно пропорционально  массе частицы:

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

Схема алгоритма состоит из следующих шагов:

1.1. Задаем начальные значения свободным параметрам пчелиного алгоритма. Обозначим через N — количество особей в колонии,  m — количество пчел-разведчиков, s — количество рабочих пчел (m+s=N).

1.2. Случайным образом задаем m начальных точек, соответствующих начальным положениям пчел в начальный момент времени  заданных в пространстве  .

1.3. Вычисляем в этих точках значение фитнес-функции

Сортируем полученные значения по убыванию.

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

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

1.4.  В случайные точки каждого из  элитных участков и  перспективных участков посылаем соответственно по   рабочих пчел. При этом .  В новые случайные участки отправляем m пчел-разведчиков.

Скорость перемещения каждой пчелы в соответствующем направлении вычисляем согласно уравнению ,

 где  ;   — текущая координата пчелы,  p — случайное число в диапазоне [-1,1] для управления перехода в соседние решения, расположенные около .   Вычисляем в этих точках значения фитнес-функции.

1.4.  Если выполнено t1 итераций, переходим к шагу 2, в противном случае, переходим к шагу 1.3.

2. Задаем начальные параметры гравитационного алгоритма: максимальное количество итераций t2=t1; количество частиц N — соответствует количеству пчел колонии. Определяем значения коэффициентов, необходимых для вычисления сил гравитационного взаимодействия:  .

2.1. Генерируем систему частиц гравитационного алгоритма. В качестве начальной популяции частиц гравитационного алгоритма, выбираем N векторов, соответствующих точкам, отобранным после выполнения t1 итераций алгоритма ABC.

  — позиция частицы.

2.2. Значение гравитационной постоянной уменьшаем с ростом числа итераций по формуле:

где β — свободный параметр алгоритма, t — текущая итерация, T — максимальное число итераций.

Для простоты полагаем, что пассивная , активная  и инерциальная  массы совпадают: .

2.3. Определяем значения скоростей и ускорений частиц:

где  *— операция покомпонентного умножения векторов,  — случайная величина, равномерно распределенная на промежутке (0, 1).

2.4. Осуществляем пересчет частиц по формуле

2.5. Пересчитываем значения масс: ,

где  .

2.6. Повторяем итерации 2.1-2.5, пока не выполнится критерий останова.

Результаты экспериментальных исследований.

Вычислительные эксперименты проводились на основе пяти тестовых функций:

F1. Сферическая функция (Sphere function):   .

Функция имеет один глобальный минимум, равный 0, при . Границы поиска (-100;100) ^D.

F2. Функция Розенброка (Rosenbrock function):

  .

Функция имеет глобальный минимум, равный 0, при  . Границы поиска (-100;100)^D.

F3. Функция Растригина (Rastrigin function):

  .

Функция имеет глобальный минимум, равный 0, при .  Границы поиска (-5,12;5,12) ^D.

F4. Функция Гривонка (Griewank function):

  .

Функция имеет глобальный минимум, равный 0, при .  Границы поиска (-600;600) ^D.

F5. Функция Швефеля (Schwefel function):

  .

Функция имеет глобальный минимум, равный 0, при .  Границы поиска (-500;500) ^D.

Эффективность гибридного алгоритма ABCGSA рассматривалась на основе сравнения с алгоритмом ABC. При тестировании алгоритмов использовались одни и те же параметры. Для ABC:  количество особей в колонии N =100,  пчел-разведчиков m = N/2, limit =100. Максимальное количество циклов для ABC алгоритма t=2000. Для GSA: значение гравитационной постоянной G(0) =100, β=20. Максимальное количество циклов для ABCGSA алгоритма t=2000. Переход от АВС к GSA осуществлялся после t/2 итераций. Тестирование проводилось для размерностей D =50, 100.

В каждом случае значения усреднялись по результатам 30 прогонов. В таблице 1 представлены результаты работы алгоритмов для пяти тестовых функций. Здесь «SrMin» — среднее минимальное значение функции, «StdDev» —  стандартное отклонение функции.

Таблица 1 – Результаты вычислительных экспериментов для тестовых функций

Функция	Алгоритм	Размерность, D
		50		100
		SrMin	StdDev	SrMin	StdDev
F1	ABC	3,065E-14	8.513E-13	1,065E-10	1.533E-08
	ABCGSA	8,244E-16	4,336E-17	3,514E-13	1,732E-12
F2	ABC	4,372E+01	2.653E+01	4,384E+01	3.212E+01
	ABCGSA	8,163E-01	6,125E-01	1,018E+00	1,704E+00
F3	ABC	1,603E-04	2.643E-05	5,986E-00	9.261E+00
	ABCGSA	0,0E+00	0,0E+00	2,557E-10	6,710E-08
F4	ABC	3,408E-11	5.584E-06	1,509E-07	4.326E-04
	ABCGSA	7,216E-16	5,344E-16	2,114E-14	1,562E-14
F5	ABC	7,269E-01	5.573E-01	1,734E+02	1.943E+02
	ABCGSA	4,364E-08	5,374E-05	2,784E-02	8,322E-01

Выводы

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

Список литературы / References

1. Renders J. M. Hybridizing genetic algorithms with hill-climbing methods for global optimization: two possible ways / Renders J. M., Bersini H. // Evolutionary Computation, 1994. IEEE World Congress on Computational Intelligence, Proceedings of the First IEEE Conference on. 1, –1994. – P. 312-317.
2. Renders J. M. Hybrid methods using genetic algorithms for global optimization / Renders J. M., Flasse S. P. // IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics). – 1996. – V. 26. – №. 2. – P. 243-258.
3. Chiou J. P. Hybrid method of evolutionary algorithms for static and dynamic optimization problems with application to a fed-batch fermentation process / Chiou J. P., Wang F. S. //Computers & Chemical Engineering. – 1999. – V. 23. – №. 9. – P. 1277-1291.
4. Juang C. F. A hybrid of genetic algorithm and particle swarm optimization for recurrent network design / Juang C. F. // IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics). – 2004. – V. 34. – №. 2. – P. 997-1006.
5. Xia W. An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems / Xia W., Wu Z. //Computers & Industrial Engineering. – 2005. – V. 48. – №. 2. – P. 409-425.
6. Argáez M. A Hybrid Algorithm for Global Optimization Problems / Argáez M., Velázque L., Quinte C. //Reliable Computing. – 2011. – V. 15. – №. 3. – P. 230-241.
7. Karaboga D. An idea based on honey bee swarm for numerical optimization / Karaboga D. // Technical Report-TR06, Erciyes University, engineering faculty, computer engineering department. – 2005. – V. 200. – P. 1-10.
8. Pham D. T. The bees algorithm. Technical note / Pham D. T., Ghanbarzadeh A., Koc E. et al // Manufacturing Engineering Centre, Cardiff University, UK. – 2005. – P. 1-57.
9. Pham D. T. The bees algorithm: modelling foraging behaviour to solve continuous optimization problems / Pham D. T., Castellani M. // Proceedings of the Institution of Mechanical Engineers, Part C: Journal of Mechanical Engineering Science. – 2009. – V. 223. – №. 12. – P. 2919-2938.
10. Pham D. T. et al. Application of the bees algorithm to the training of radial basis function networks for control chart pattern recognition / Pham D. T., Ghanbarzadeh A., Koc E. et al // Proceedings of 5th CIRP international seminar on intelligent computation in manufacturing engineering (CIRP ICME’06), Ischia, Italy. – 2006. – P. 711-716.
11. Курейчик В. М. Использование роевого интеллекта в решении NP-трудных задач / Курейчик В. М., Кажаров А. А. // Известия Южного федерального университета. Технические науки. – 2011. – Т. 120. – №. 7. – C. 30-36.
12. Гладков Л. А. Биоинспирированные методы в оптимизации / Гладков Л.А., Курейчик В. В., Курейчик В. М. и др. // М.: Физмалит. – 2009. – 384 с.
13. Davidović T. Bee colony optimization Part I: The algorithm overview / Davidović T. // Yugoslav Journal of Operations Research. – 2016. – Т. 25. – №. 1. – P. 33-56.
14. Rashedi E. GSA: a gravitational search algorithm / Rashedi E., Nezamabadi-Pour H., Saryazdi S. // Information sciences. – 2009. – V. 179. – №. 13. – P. 2232-2248.
15. Карпенко А. П. Популяционные алгоритмы глобальной поисковой оптимизации. Обзор новых и малоизвестных алгоритмов / Карпенко А. П. // Информационные технологии. – 2012. – №. – P. 1-32.
16. Mirjalili S. A. Training feedforward neural networks using hybrid particle swarm optimization and gravitational search algorithm / Mirjalili S. A., Hashim S. Z. M., Sardroudi H. M. // Applied Mathematics and Computation. – 2012. – V. 218. – №. 22. – P. 11125-11137.
17. Смирнова О. С. Описание роевых алгоритмов, инспирированных неживой природой и бактериями, для использования в онтологической модели / Смирнова О. С., Богорадникова А. В., Блинов М. Ю. // International Journal of Open Information Technologies. – 2015. – Т. 3. – №. – C. 28-35.

Список литературы на английском языке / References in English

1. Renders J. M. Hybridizing genetic algorithms with hill-climbing methods for global optimization: two possible ways / Renders J. M., Bersini H. // Evolutionary Computation, 1994. IEEE World Congress on Computational Intelligence, Proceedings of the First IEEE Conference on. 1, –1994. – P. 312-317.
2. Renders J. M. Hybrid methods using genetic algorithms for global optimization / Renders J. M., Flasse S. P. // IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics). – 1996. – V. 26. – №. 2. – P. 243-258.
3. Chiou J. P. Hybrid method of evolutionary algorithms for static and dynamic optimization problems with application to a fed-batch fermentation process / Chiou J. P., Wang F. S. //Computers & Chemical Engineering. – 1999. – V. 23. – №. 9. – P. 1277-1291.
4. Juang C. F. A hybrid of genetic algorithm and particle swarm optimization for recurrent network design / Juang C. F. // IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics). – 2004. – V. 34. – №. 2. – P. 997-1006.
5. Xia W. An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems / Xia W., Wu Z. //Computers & Industrial Engineering. – 2005. – V. 48. – №. 2. – P. 409-425.
6. Argáez M. A Hybrid Algorithm for Global Optimization Problems / Argáez M., Velázque L., Quinte C. //Reliable Computing. – 2011. – V. 15. – №. 3. – P. 230-241.
7. Karaboga D. An idea based on honey bee swarm for numerical optimization / Karaboga D. // Technical Report-TR06, Erciyes University, engineering faculty, computer engineering department. – 2005. – V. 200. – P. 1-10.
8. Pham D. T. The bees algorithm. Technical note / Pham D. T., Ghanbarzadeh A., Koc E. et al // Manufacturing Engineering Centre, Cardiff University, UK. – 2005. – P. 1-57.
9. Pham D. T. The bees algorithm: modelling foraging behaviour to solve continuous optimization problems / Pham D. T., Castellani M. // Proceedings of the Institution of Mechanical Engineers, Part C: Journal of Mechanical Engineering Science. – 2009. – V. 223. – №. 12. – P. 2919-2938.
10. Pham D. T. et al. Application of the bees algorithm to the training of radial basis function networks for control chart pattern recognition / Pham D. T., Ghanbarzadeh A., Koc E. et al // Proceedings of 5th CIRP international seminar on intelligent computation in manufacturing engineering (CIRP ICME’06), Ischia, Italy. – 2006. – P. 711-716.
11. Kureichik V. M. Ispol'zovaniye royevogo intellekta v reshenii NP-trudnykh zadach [Use of swarm intelligence in solving NP-difficult problems] / Kureichik V.M., Kazharov A.A. // Izvestiya Yuzhnogo federal'nogo universiteta. Tekhnicheskiye nauki [Izvestiya Southern Federal University. Technical science]. – 2011. – V. 120. – №. 7. – P. 30-36. [in Russian]
12. Gladkov L. A. Bioinspirirovannyye metody v optimizatsii [Bioinspirated methods in optimization] / Gladkov L.A., Kureichik V.V., Kureichik V.M., Sorokoletov P.V. // М.: Fizmalit. – 2009. – 384 P. [in Russian]
13. Davidović T. Bee colony optimization Part I: The algorithm overview //Yugoslav Journal of Operations Research. – 2016. – Т. 25. – №. 1.
14. Rashedi E., Nezamabadi-Pour H., Saryazdi S. GSA: a gravitational search algorithm //Information sciences. – 2009. – Т. 179. – №. 13. – С. 2232-2248.
15. Karpenko A. P. Populyatsionnyye algoritmy global'noy poiskovoy optimizatsii. Obzor novykh i maloizvestnykh algoritmov [Population algorithms of global search engine optimization. Review of new and little-known algorithms] / Karpenko A. P. // Informatsionnyye tekhnologii [Information technology]. – 2012. – №. S7. – P. 1-32.
16. Mirjalili S. A., Hashim S. Z. M., Sardroudi H. M. Training feedforward neural networks using hybrid particle swarm optimization and gravitational search algorithm //Applied Mathematics and Computation. – 2012. – Т. 218. – №. 22. – С. 11125-11137.
17. Smirnova O.S. Opisaniye royevykh algoritmov, inspirirovannykh nezhivoy prirodoy i bakteriyami, dlya ispol'zovaniya v ontologicheskoy modeli [Description of swarm algorithms inspired by inanimate nature and bacteria for use in the ontological model] / Smirnova O.S., Bogoradnikova A.V., Blinov M. Yu. // International Journal of Open Information Technologies. – 2015. – Т. 3. – №. 12.