Review: population methods of Pareto set approximation
in multi-objective optimization problem
77-30569/363023
# 04, April 2012
Karpenko A.,P., Semenikhin A., S., Mitina E.V.
Bauman Moscow State Technical University apkarpenko@mail.ru saspost@yandex.ru mitinakaterina@gmail.com
This authors present a review of numerical methods of approximate Pareto set generation in the multi-objective optimization problem. The following methods are discussed: "naive" methods, switching objective functions methods, methods of objective functions aggregation, methods based on ranking of population agents, and other methods. All cases referred to methods involving the use of genetic or swarm algorithms, such as particle swarm optimization algorithm.
Publications with keywords: multiobjective optimization
,
Pareto set
,
Pareto front
, population methods
Publications with words: multiobjective optimization
,
Pareto set
,
Pareto front
, population methods
References
1. Podinovskii V.V., Nogin V.D. Pareto-optimal'nye resheniia mnogokriterial'nykh zadach
[Pareto-optimal solutions of multicriterion problems]. Moscow, Fizmatlit, 2007. 256 p.
2. Nogin V.D. Priniatie reshenii v mnogokriterial'noi srede: kolichestvennyi podkhod
[Decision-making in multicriterion environment: a quantitative approach]. Moscow, Fizmatlit, 2005.
176 p.
3. Larichev O.I. Teoriia i metody priniatiia reshenii [Theory and methods of decision making]. Moscow, Universitetskaia kniga, Logos, 2006. 392 p.
4. Kureichik V.M. Geneticheskie algoritmy i ikh primenenie [Genetic algorithms and their applications]. Taganrog, TRSU Publ., 2002. 244 p.
5. Ashlock D. Evolutionary Computation for Modeling and Optimization. Springer, 2006.
571 p.
77-30569/363023
, №04 апрель 2012 г. http://technomag.edu.ru
34 6. Guliashki V., Toshev H., Korsemov Ch. Survey of Evolutionary Algorithms Used in
Multiobjective Optimization. Problems of Engineering Cybernetics and Robotics, 2009, vol. 60, pp.
42 – 54.
7. Zitzler E., Deb K., Thiele L. Comparison of Multiobjective Evolutionary Algorithms:
Empirical Results. Evolutionary Computation (journal), 2000, vol. 8, no. 2, pp. 173-195.
8. Karpenko A. P., Seliverstov E. Iu. Global'naia optimizatsiia metodom roia chastits.
Obzor [Global optimization of method of particle swarm. Overview]. Informatsionnye tekhnologii,
2010, no. 2, pp. 25-34.
9. Karpenko A. P., Seliverstov E. Iu. Obzor metodov roia chastits dlia zadachi global'noi optimizatsii [Review of the particle swarm optimization method (PSO) for a global optimization problem]. Nauka i obrazovanie: nauchnoe izdanie MGTU im. N.E. Baumana [Science and
Education: scientific periodical of the Bauman MSTU], 2009, no. 3. Available at: http://technomag.edu.ru/doc/116072.html, accessed 4.05.2012.
10. Fonseca C. M., Fleming P. J. Genetic Algorithms for Multiobjective Optimization:
Formulation, Discussion and Generalization. Proc. of the 5th International Conference on Genetic
Algorithms, San Mateo, California, 1993, pp. 416-423.
11. Zitzler E., Thiele L., Marco Laumanns M., Fonseca C. M., da Fonseca V. G. Performance
Assessment of Multiobjective Optimizers: An Analysis and Review. IEEE Transactions of
Evolutionary Computation, 2003, Vol. 7 (2), pp. 117-132.
12. Knowles J.D., Corne D.W. On Metrics for Comparing Non-Dominated Sets. Proc. of the
IEEE Congress on Evolutionary Computation (CEC '02), Vol. 1, New Jersey, Piscataway, May
2002, IEEE Service Center, 2002, pp. 711 – 716.
13. Gumennikova A. V. Adaptivnye poiskovye algoritmy dlia resheniia slozhnykh zadach
mnogokriterial'noi optimizatsii. Kand. diss. [Adaptive search algorithms for solving complex problems of multicriteria optimization. Cand. diss.]. Krasnoiarsk, 2006. 129 p.
14. Luke S. Essentials of Metaheuristics. A Set of Undergraduate Lecture Notes. Department of Computer Science George Mason University, Online Version 1.3 February, 2012. Available at: http://cs.gmu.edu/sean/book/metaheuristics/Essentials.pdf.
15. Sobol' I.M., Statnikov R.B. Vybor optimal'nykh parametrov v zadachakh so mnogimi
kriteriiami [The choice of optimal parameters in problems with many criteria]. Moscow, Drofa,
2006. 175 p.
16. Schaffer J.D. Multiple Objective Optimization with Vector Evaluated Genetic
Algorithms. Proc. of the First International Conference on Genetic Algorithms and Their
Applications, 1985, Lawrence Erlbaum, pp. 93-100.
17. Moor D.A., Mukhlisullina D. T. Analiz effektivnosti razlichnykh svertok kriteriev optimal'nosti v zadache mnogokriterial'noi optimizatsii [Analysis of the effectiveness of different scalar convolutions in multiobjective optimization problem]. Nauka i obrazovanie: nauchnoe
izdanie MGTU im. N.E. Baumana [Science and Education: scientific periodical of the Bauman
http://technomag.edu.ru/doc/363023.html
35
MSTU], 2010, no. 4. Available at: http://technomag.edu.ru/doc/141623.html, accessed 4.05.2012.
18. Ryu J.-H., Kim S., Wan H. Pareto front approximation with adaptive weighted sum method in multiobjective simulation optimization. Proc. of the 2009 Winter Simulation Conference
(WSC), 2009, Austin, pp. 623-633. Available at: http://www.informs-sim.org/wsc09papers/060.pdf
19. Srinivas N., Deb K. Multiobjective optimization using nondominated sorting in genetic algorithms. Evolutionary Computation (journal), 1994, vol. 2, p. 221–248.
20. Horn J., Nafpliotis N., Goldberg D.E. A Niched Pareto Genetic Algorithm for
Multiobjective Optimization. Proc. of the First IEEE Conference on Evolutionary Computation,
IEEE World Congress on Computational Intelligence, New Jersey, Piscataway, June 1994, IEEE
Service Center, Vol. 1, pp. 82-87.
21. Deb K., Pratap A., Agarwal S., Meyarivan T. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 2002, vol. 6, no. 2, pp. 182
– 197.
22. Zitzler E., Thiele L. Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach. IEEE Transactions on Evolutionary Computation, 1999, vol. 3, no. 4, pp. 257–271.
23. Zitzler E., Laumanns M., Thiele L. SPEA2: Improving the Strength Pareto Evolutionary
Algorithm for Multiobjective Optimization. Evolutionary Methods for Design, Optimization and
Control with Application to Industrial Problems (EUROGEN 2001), International Center for
Numerical Methods in Engineering (CIMNE), 2002, pp. 95‑ 100.
24. Knowles J., Corne D. The Pareto achieved evolution strategy: A new baseline algorithm for Pareto multiobjective optimization. Proc. of the Congress on Evolutionary Computation
(CEC99), Washington, 1999, Vol. 1, pp. 98–105.
25. Bentley P. J., Wakefield J. P. An Analysis of Multiobjective Optimization within Genetic
Algorithms. Technical Report ENGPJB96, University of Huddersfield, UK, 1996. 19 p.
26. Mostaghim S., Teich J. Strategies for Finding Good Local Guides in Multi-objective
Particle Swarm Optimization (MOPSO). Proc. of the Swarm Intelligence Symposium (SIS '03),
IEEE, 2003, pp. 26 – 33.
27. Fieldsend J.E., Singh S. A multi-objective algorithm based upon particle swarm
optimization, an efficient data structure and turbulence. 2002. Available at: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.6959.
28. Coello C.A., Lechuga M.S. MOPSO: A proposal for multiple objective particle swarm optimization. Proc. of the World Congress on Evolutionary Computation (CEC2002), IEEE Service
Center, 2002, pp. 1051-1056.
29. Hu X., Eberhart R. Multiobjective Optimization Using Dynamic Neighborhood Particle
Swarm Optimization. Proc. of the Congress on Evolutionary Computation (CEC '02), May 2002,
IEEE Service Center, pp. 1677 – 1681.
77-30569/363023
, №04 апрель 2012 г. http://technomag.edu.ru
36 30. Laumanns M., Rudolph G., Schwefel H.P. A spatial predator-prey approach to multi- objective optimization: A preliminary study. Fifth International Conference on Parallel Problem
Solving from Nature (PPSN-V), Berlin, Germany, pp. 241-249.
31. Deb K. Multi-objective optimization using evolutionary algorithms. Chichester, UK,
Wiley, 2001. 518 p.
32. Deb K., Rao U. B. Investigating Predator-Prey Algorithms for Multi-Objective
Optimization. KanGAL Report Number 2005010. Kanpur Genetic Algorithms Laboratory
(KanGAL), Department of Mechanical Engineering Indian Institute of Technology Kanpur, India.
Available at: http://www.iitk.ac.in/kangal/.
33. Deb K., Mohan M., Mishra S. Evaluating the -domination based multi-objective evolutionary algorithm for a quick computation of Pareto-optimal solutions. Evolutionary
Computation Journal, 2005, vol. 13, no. 4, pp. 501-525.
34. Antukh A.E., Karpenko A.P., Semenikhin A.S., Khasanova R.V. Postroenie mnozhestva
Pareto metodom roia chastits na graficheskikh protsessorakh arkhitektury CUDA [The construction of the Pareto set using method of a swarm of particles on the GPUs CUDA architecture]. Nauchnyi
servis v seti Internet: superkomp'iuternye tsentry i zadachi: Trudy Mezhdunarodnoi
superkomp'iuternoi konferentsii (20-25 sentiabria 2010 g., g. Novorossiisk) [Scientific services on the Internet: supercomputing centers and Objectives: Proc. of the International Supercomputer
Conference (20-25 September 2010, Novorossiysk)]. Moscow, Bauman MSTU Publ., 2010, pp.
274-280.
35. Karpenko A.P., Semenikhin A.S., Cherviatsova M.N. Metod priblizhennogo postroeniia granitsy oblasti dostizhimosti mnogosektsionnogo manipuliatora tipa «khobot» [Approximation of a set of attainability for trunk multisectional robot-manipulator ]. Nauka i obrazovanie: nauchnoe
izdanie MGTU im. N.E. Baumana [Science and Education: scientific periodical of the Bauman
MSTU], 2011, no. 1. Available at: http://technomag.edu.ru/doc/165078.html, accessed 4.05.2012.
|
Скачать 0.63 Mb.