НАУКА и ОБРАЗОВАНИЕ

Файл статьи: SE-BMSTU...o181.pdf (1848.94Кб)

УДК 519.6

1 МГТУ им. Н.Э. Баумана, Москва, Россия

Рассматриваем класс алгоритмов многоцелевой оптимизации – алгоритмы Парето-аппроксимации, которые предполагают предварительное построение конечномерной аппроксимации множества Парето, а тем самым и фронта Парето этой задачи. Выполнен обзор популяционных и непопуляционных алгоритмов Парето-аппроксимации, выявлены их достоинства и недостатки. Представлен канонический алгоритм «хищник-жертва», показаны его недостатки. Предлагаем ряд модификаций канонического алгоритма «хищник-жертва», имеющих целью преодоление недостатков этого алгоритма. Представляем результаты широкого исследования эффективности указанных модификаций алгоритма. Особенность исследования заключается в использовании индикаторов качества Парето-аппроксимации, не используемых в предшествующих публикациях. Кроме того, представляем результаты мета-оптимизации модифицированного алгоритма, то есть определения оптимальных значений некоторых свободных параметров этого алгоритма.
Исследование эффективности модифицированного алгоритма «хищник-жертва» показали, что предложенные модификации позволили улучшить следующие показатели базового алгоритма: мощность множества архивных решений; равномерность распределения архивных решений; время вычислений. В целом, результаты исследований показали, что модифицированный и мета-оптимизированный алгоритм позволяет достичь той же точности аппроксимации, что и базовый алгоритм, но с числом жертв меньшим на порядок. Пропорционально уменьшаются вычислительные затраты.

1. Kalyanmoy Deb. Multi-objective optimization using evolutionary algorithms. Chichester; N.Y.: Wiley, 2001. 497 p.
2. Карпенко А. П., Митина Е. В., Семенихин А. С. Популяционные методы аппроксимации множества Парето в задаче многокритериальной оптимизации. Обзор // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2012. № 4. С.25.DOI: 10.7463/0412.0363023
3. Laumanns M., Rudolph G., Schwefel H.P. A spatial predator-prey approach to multi-objective optimization: a preliminary study // Parallel problem solving from nature: 5^th Intern. conf. on parallel problem solving from nature (Amsterdam, Netherlands, Sept. 27– 30, 1998): proceedings. B.: Springer, 1998. Pp. 241–249. DOI: 10.1007/BFb0056867
4. Xiaodong Li. A real-coded predator-prey genetic algorithm for multiobjective optimization // Evolutionary multi-criterion optimization: 2^nd Intern. conf. on evolutionary multi-criterion optimization. EMO-2003 (Faro, Portugal, April 8-11, 2003): proceedings. B.: Springer, 2003. Pp. 207-221. DOI: 10.1007/3-540-36970-815
5. Kalyanmoy Deb, Udaya Bhaskara Rao N. Investigating predator-prey algorithms for multi-objective optimization // KanGAL Report. 2005. No. 2005010. 12 p.
6. Chowdhury S., Dulikravich G. S., Moral R.J. Modified predator-prey algorithm for constrained and unconstrained multi-objective optimisation // Int. J. of Mathematical Modelling and Numerical Optimisation. 2009. Vol. 1. No. 1/2. Pp. 1–38. DOI: 10.1504/IJMMNO.2009.030085
7. Surafel Luleseged Tilahun, Hong Choon Ong. Prey-predator algorithm: A new metaheuristic algorithm for optimization problem // Intern. J. of Information Technology & Decision Making. 2015. Vol. 14. № 6. Pp. 1331 -- 1352. DOI: 10.1142/S021962201450031X
8. Silva A., Neves A., Costa E. An empirical comparison of particle swarm and predator prey optimisation // Artificial intelligence and cognitive science: 13^th Irish Intern. conf. AICS 2002 (Limerick, Ireland, Sept. 12-13, 2002): proceedings. B.: Springer, 2002. Pp. 103-110. DOI: 10.1007/3-540-45750-X_13
9. Grimme C., Schmitt K. Inside a predator-prey model for multi-objective optimization: A second study // Genetic and evolutionary computation conf. GECCO’06 (Seattle, Washington, USA, July 8–12, 2006): proceedings. Vol. 1. Pp. 707 -- 714. DOI: 10.1145/1143997.1144121
10. Eiben A. E., Michalewicz Z., Schoenauer M., Smith J. E. Parameter control in evolutionary algorithms // Parameter setting in evolutionary algorithms. B.: N.Y.: Springer, 2007. Pp. 19 -- 46. DOI: 10.1007/978-3-540-69432-82
11. Eshelman L.J., Schaffer J.D. Real-coded genetic algorithms and interval- schemata // Foundations of genetic algorithms - 2: Workshop on foundations of genetic algorithms: FOGA-92 (Vail, Colo., 1992). San Mateo: Morgan Kaufmann, 1993. Pp. 187 -- 202. DOI: 10.1016/B978-0-08-094832-4.50018-0
12. Michalewicz Z. Genetic algorithms + data structures = evolutionary programs. B.; N.Y.: Springer, 1992. 250 p.
13. Соболь И. М., Статников Р. Б. Выбор оптимальных параметров в задачах со многими критериями. 2-е изд. М.: Дрофа, 2006. 175 с.
14. Kalyanmoy Deb, Thiele L., Laumanns M., Zitzler E. Scalable test problems for evolutionary multi-objective optimization // Evolutionary multiobjective optimization. L.: Springer, 2005. Pp. 105-145. DOI: 10.1007/1-84628-137-7_6
15. Zitzler E., Kalyanmoy Deb, Thiele L. Comparison of multiobjective evolutionary algorithms: Empirical results // Evolutionary Computation. 2000. Vol. 8. Iss. 2. Pp. 173-195. DOI: 10.1162/106365600568202
16. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой. М.: Изд-во МГТУ им. Н.Э. Баумана, 2014. 446 с.