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

В работе предлагается модификация численного метода фейерверков однокритериальной оптимизации для решения задач многокритериальной оптимизации. Метод относится к метаэвристическим алгоритмам, он не гарантирует нахождения точного решения, но может найти достаточно хорошее приближенное решение. Рассматриваются многокритериальные задачи оптимизации с числовыми критериями, имеющими одинаковую важность. Допустимое решение задачи представляется вектором из действительных чисел, значение каждой компоненты которого принадлежит определенному отрезку. Под оптимальным решением понимается решение, оптимальное по Парето. Так как точных решений, оптимальных по Парето, может быть бесконечно много, рассматривается способ нахождения приближения, состоящего из конечного числа решений, оптимальных по Парето. Модификация основана на процедуре недоминируемой сортировки, которая является основной процедурой для управления процессом поиска приближенного решения. Недоминируемая сортировка – это ранжирование решений на основе значений компонент числового вектора, полученных с помощью вычисления критериев. Каждая компонента соответствует определенному критерию, а множество решений разбивается на непересекающиеся подмножества. Первое подмножество – это решения, оптимальные по Парето, второе подмножество – это решения, оптимальные по Парето, если не учитывать первое подмножество, последнее подмножество – это решения, оптимальные по Парето, если не учитывать все предыдущие подмножества. После такого разбиения принимается решение о генерировании новых допустимых решений. Работа метода протестирована на общеизвестных задачах многокритериальной оптимизации с двумя критериями: ZDT2, LZ01. Задачи отличаются структурой расположения решений, оптимальных по Парето. Так LZ01 имеет достаточно сложную структуру решений, оптимальных по Парето. В заключении обсуждаются вопросы о дальнейшем направлении исследований и о возможности модификации метода для задач многокритериальной оптимизации с произвольными, а не параллелепипедными ограничениями.

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

1. Arias-Montano A., Coello Coello A.C., Mezura-Montes E. Multiobjective evolutionary algorithms in aeronautical and aerospace engineering // IEEE Transactions on Evolutionary Computation. 2012. Vol. 16, Iss. 5. Pp. 662–694. DOI: 10.1109/TEVC.2011.2169968

2. Multi-objective optimization. Techniques and applications in chemical engineering / Ed. G.P. Rangaiah. 2nd еd. World Scientific, 2017. 588 p. DOI: 10.1142/10240

3. Березкин В.Е., Лотов А.В., Лотова Е.А. Изучение гибридных методов аппроксимации оболочки Эджворта – Парето в нелинейных задачах многокритериальной оптимизации // Журнал вычислительной математики и математической физики. 2014. Т. 54, № 6. C. 905–918. DOI: 10.7868/S0044466914060039

4. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1982. 256 c.

5. Tan Y., Zhu Y. Fireworks Algorithm for Optimization // Advances in Swarm Intelligence. First International Conference. ICSI 2010, Beijing, China, June 12–15, 2010. Proceedings, Part I / Ed. Y. Tan, Y. Shi, K.C. Tan. Springer, Berlin, Heidelberg, 2010. Pp. 355–364. Lecture Notes in Computer Science, vol. 6145. DOI: 10.1007/978-3-642-13495-1_44

6. Handbook of Metaheuristics / Ed. F. Glover, G.A. Kochenberger. New-York; Boston; Moscow: Kluwer Academic Publishers, 2003. 557 p.

7. Пантелеев А.В., Крючков А.Ю. Метаэвристические методы оптимизации в задачах оценки параметров динамических систем // Научный Вестник МГТУ ГА. 2017. Т. 20, № 2. С. 37–45. DOI: 10.26467/2079-0619-2017-20-2-37-45

8. Fortin F.-A., Grenier S., Parizeau M. Generalizing the improved run-time complexity algorithm for non-dominated sorting // GECCO '13. Proceedings of the 15th annual conference on Genetic and evolutionary computation. Amsterdam, The Netherlands – July 06–10, 2013. 2013. Pp. 615– 622. DOI: 10.1145/2463372.2463454

9. Buzdalov M., Shalyto A. A Provably Asymptotically Fast Version of the Generalized Jensen Algorithm for Non-dominated Sorting // Parallel Problem Solving from Nature – PPSN XIII: 13th International Conference, Ljubljana, Slovenia, September 13–17, 2014: proceedings. Cham: Springer International Publishing, 2014. Pp. 528–537. DOI: 10.1007/978-3-319-10762-2_52

10. Zitzler E., Thiele L. Multiobjective optimization using evolutionary algorithms – a comparative case study // Parallel Problem Solving from Nature – PPSN V. 5th International Conference Amsterdam, The Netherlands September 27–30, 1998. 1998. Pp. 292–301. DOI: 10.1007/BFb0056872

11. Zitzler E., Deb K., Thiele L. Comparison of multiobjective evolutionary algorithms: empirical results // Evolutionary Computation. 2000. Vol. 8, № 2. Pp. 173–195. DOI: 10.1162/106365600568202

12. Li H., Zhang Q. Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II // IEEE Transactions on Evolutionary Computation. 2009. Vol. 13, Iss. 2, April. Pp. 284–302. DOI: 10.1109/TEVC.2008.925798

13. Amuso V.J., Enslin J. The Strength Pareto Evolutionary Algorithm 2 (SPEA2) applied to simultaneous multi-mission waveform design // 2007 International waveform diversity and design conference. Pisa, 2007. Pp. 407–417. DOI: 10.1109/WDDC.2007.4339452

14. Jain H., Deb K. An evolutionary many-objective optimization algorithm using referencepoint based nondominated sorting approach. Part II: Handling constraints and extending to an adaptive approach // IEEE Transactions on evolutionary computation. 2014. Vol. 18, Iss. 4, Aug. Pp. 602–622. DOI: 10.1109/TEVC.2013.2281534