Другие журналы

научное издание МГТУ им. Н.Э. Баумана

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

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

Исследование эффективности и настройка модифицированного алгоритма «хищник-жертва» в задаче многоцелевой оптимизации

# 12, декабрь 2016
DOI: 10.7463/1216.0852423
Файл статьи: SE-BMSTU...o181.pdf (1848.94Кб)
авторы: профессор, д.ф.-м.н. Карпенко А. П.1,*, Пугачев А. В.1

УДК 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: 5th 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: 2nd 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: 13th 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 с.
Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2017 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)