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

Файл статьи: Karpenko_A.pdf (960.36Кб)

УДК 519.6

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

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

Список литературы
1.    Лотов А.В., Поспелова И.И. Многокритериальные задачи принятия решений: учеб. пособие. М.: МАКС Пресс, 2008. 197 c.
2.    Карпенко А.П., Семенихин А.С., Митина Е.В. Популяционные методы аппроксимации множества Парето в задаче многокритериальной оптимизации // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2012. № 4. Режим доступа: http://www.technomag.edu.ru/doc/363023.html  (дата обращения 01.03.2014).
3.    Белоус В.В., Грабик А.В., Грошев С.В., Шибитов И.А. Качество Парето-аппроксимации в задаче многокритериальной оптимизации // XVIII Байкальская Всероссийская конференция «Информационные и математические технологии в науке и управлении»: материалы. Ч. 1. Иркутск: ИСЭМ СО РАН, 2013. С. 6-12.
4.    Zitzler E., Deb K., Thiele L. Comparison of Multiobjective Evolutionary Algorithms: Empirical Results // Evolutionary Computation. 2000. Vol. 8, no. 2. P. 173-195.
5.    Lukasiewycz M., Glass M., Reimann F., Teic J. Opt4J - A Modular Framework for Meta-heuristic Optimization // Proceedings of the Genetic and Evolutionary Computing Conference, 2011. P. 1723-1730.
6.    Google Guice. Available at: https://code.google.com/p/google-guice/, accessed 01.03.2014.
7.    SAT4j. Available at: http://www.sat4j.org/, accessed 01.03.2014.
8.    Ptplot. Available at: http://ptolemy.eecs.berkeley.edu/java/ptplot/ , accessed 01.03.2014.
9.    Zitzler E., Laumanns M., Thiele L. SPEA2: Improving the Strength Pareto Evolutionary Algorithm for Multiobjective Optimization // In: Evolutionary Methods for Design, Optimisation and Control with Application to Industrial Problems (EUROGEN 2001) / K. Giannakoglou, et al., editors. International Center for Numerical Methods in Engineering (CIMNE), 2002. P. 95-100.
10.    Agrawal S., Pratap A., Meyarivan T., Deb K. A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II // In: Parallel Problem Solving from Nature PPSN VI. Springer Berlin Heidelberg, 2000. P. 849-858. DOI: 10.1007/3-540-45356-3_83
11.    Reyes Sierra M., Coello Coello C.A. Improving PSO-based Multi-Objective Optimization using Crowding, Mutation and e-Dominance // In: Evolutionary Multi-Criterion Optimization. Springer Berlin Heidelberg, 2005. P. 505-519. DOI: 10.1007/978-3-540-31880-4_35
12.    Emmerich M., Beume N., Naujoks B. An EMO Algorithm Using the Hypervolume Measure as Selection Criterion // In: Evolutionary Multi-Criterion Optimization. Springer Berlin Heidelberg, 2005. P. 62-76. DOI: 10.1007/978-3-540-31880-4_5
13.    Deb K., Thiele L., Laumanns M., Zitzler E. Scalable Test Problems for Evolutionary Multi-Objective Optimization. Tech. Rep. 112. Zurich, Switzerland, 2001. 27 p.
14.    Barone L., While L., Huband L., Hingston S. Use of the WFG Toolkit and PISA for Comparison of MOEAs // Proceedings of IEEE Symposium on Computational Intelligence in Multi-Criteria Decision-Making, 2007. P. 382-389. DOI: 10.1109/MCDM.2007.369117
15.    Laumanns M., Thiele L., Zitzler E. Running Time Analysis of Multiobjective Evolutionary Algorithms on Pseudo-Boolean Functions // IEEE Transactions on Evolutionary Computation. 2004. Vol. 8, no. 2. P. 170–182. DOI: 10.1109/TEVC.2004.823470
16.    Zitzler E., Thiele L., Laumanns M., Fonseca C.V., Fonseca V.G. Performance Assessment of Multiobjective Optimizers: An Analysis and Review // IEEE Transactions of Evolutionary Computation. 2003. Vol. 7, no. 2. P. 117-132. DOI: 10.1109/TEVC.2003.810758
17.    Durillo J.J., Nebro A.J. jMetal: A Java Framework for Multi-Objective Optimization // Advances in Engineering Software. 2011. Vol. 42. P. 760-771.
18.    Kukkonen S., Lampinen J. GDE3: The Third Evolution Step of Generalized Differential Evolution. KanGAL Report No. 2005013, 2005. P. 443-450.
19.    Knowles J., Corne D. The Pareto Archived Evolution Strategy: A New Baseline Algorithm for Multiobjective Optimization // Proceedings of the 1999 Congress on Evolutionary Computation, Piscataway, NJ, 1999. P. 98-105.
20.    Beume N. SMS-EMOA: Multiobjective selection based on dominated hypervolume // European Journal of Operational Research. 2007. Vol. 181, no. 3. P. 1653-1669.
21.    Li H., Zhang Q. Multiobjective Optimization problems with Complicated Pareto Sets, MOEA/D and NSGA-II // IEEE Transactions on Evolutionary Computation. 2009. Vol. 13, no. 2. P. 284-302. DOI: 10.1109/TEVC.2008.925798
22.    Nebro О. Optimal Antenna Placement using a New Multiobjective CHC Algorithm // Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, London, England, 2007. P. 876-883.
23.    Zitzler E., Kunzli S. Indicator-based selection in multi objective search // In: Parallel Problem Solving from Nature - PPSN VIII. Springer Berlin Heidelberg, 2004. P. 832-842. DOI: 10.1007/978-3-540-30217-9_84      (Ser. Lecture Notes in Computer Science; vol. 3242).
24.    Eskandari H., Geiger C.D., Lamont G.B. FastPGA: A Dynamic Population Sizing Approach for Solving Expensive Multiobjective Optimization Problems // In: Evolutionary Multi-Criterion Optimization. Springer Berlin Heidelberg, 2007. P. 141-155. DOI: 10.1007/978-3-540-70928-2_14
25.    Greiner D., Emperador J.M., Winter G. Enhancing the multiobjective optimum design of structural trusses with evolutionary algorithms using DENSEA // In: 44th AIAA (American Institute of Aeronautics and Astronautics) Aerospace Sciences Meeting and Exhibit, 2006. Paper AIAA-2006-1474 (11 p).
26.    Durillo J.J., Nebro A.J., Luna F., Alba E. Solving Three-Objective Optimization Problems. Using a new Hybrid Cellular Genetic Algorithm // In: Parallel Problem Solving from Nature - PPSN X. Springer Berlin Heidelberg, 2008. P. 661-670. DOI: 10.1007/978-3-540-87700-4_66
27.    Vavak F., Fogarty T.C. Comparison of Steady State and Generational Genetic Algorithms for Use in Nonstationary Environments // Proc. of the IEEE International Conference on Evolutionary Computation, 1996. P. 192-195. DOI: 10.1109/ICEC.1996.542359 
28.    Hansen N.R., Ros N., Mauny M., Auger S.A. Impacts of Invariance in Search: When CMA-ES and PSO Face Ill-Conditioned and Non-Separable Problems // Applied Soft Computing. 2011. Vol. 11. P. 5755-5769.
29.    Nebro J., Durillo J.J., Coello Coello C.A. Analysis of Leader Selection Strategies in a Multi-Objective Particle Swarm Optimizer // 2013 IEEE Congress on Evolutionary Computation, 2013. P. 3153 - 3160. DOI: 10.1109/CEC.2013.6557955
30.    Nebro A.J., Luna F., Alba E., Dorronsoro B., Durillo J.J., Beham A. AbYSS. Adapting Scatter Search to Multiobjective Optimization // IEEE Transactions on Evolutionary Computation. 2006. Vol. 12, no. 4. P. 439-457. DOI: 10.1109/TEVC.2007.913109
31.    Nebro J., Durillo J.J., Luna F., Dorronsoro B., Alba E. MOCell. A Cellular Genetic Algorithm for Multiobjective Optimization // International Journal of Intelligent Systems. 2009. Vol. 24, no. 7. P. 726-746.
32.    Bleuler S., Laumanns M., Thiele L., Zitzler E. PISA—A Platform and Programming Language Independent Interface for Search Algorithms // In: Evolutionary Multi-Criterion Optimization. Springer Berlin Heidelberg, 2003. P. 494–508. DOI: 10.1007/3-540-36970-8_35
33.    MOEA Framework. Available at: http://moeaframework.org/documentation.html , accessed 01.03.2014.
34.    Knowles J.D., Thiele L., Zitzler E. A tutorial on the performance assessment of the stochastic multiobjective optimizers. TIK-Report No. 214. Computer Engineering and Network Laboratory, ETH Zurich, 2006. 35 p.
35.    Hadka D., Reed P. Diagnostic assessment of search controls and failure modes in many-objective evolutionary optimization // Evolutionary Computation. 2012. Vol. 20, no. 3. P. 423-452.
36.    Karpenko A.P., Svianadze Z.O. Meta-optimization based on self-organizing map and genetic algorithm // Optical Memory and Neural Networks (Information Optics). 2011. Vol. 20, no.4. P. 279-283.
37.    ParadisEO. Available at:  http://paradiseo.gforge.inria.fr , accessed 01.03.2014.
38.    Liefooghe L., Jourdan T., Legrand J., Talbi G. ParadisEO-MOEO: A Software Framework for Evolutionary Multi-objective Optimization // In: Advances in Multi-objective Nature Inspired Computing. Springer Berlin Heidelberg, 2010. P. 87-117. DOI: 10.1007/978-3-642-11218-8_5    (Ser. Studies in Computational Intelligence; vol. 272).
39.    Basseur M., Burke E.K. Indicator-based multi-objective local search // IEEE Congress on Evolutionary Computation (CEC'2007), 2007. P. 3100-3107. DOI: 10.1109/CEC.2007.4424867 
40.    Liefooghe J., Humeau S., Mesmoudi S., Jourdan L. On dominance-based multiobjective local search: design, implementation and experimental analysis on scheduling and traveling salesman problems // Journal of Heuristics. 2011. Vol. 18, iss. 2. P. 317-352. DOI: 10.1007/s10732-011-9181-3
41.    Huang J., Zhao F., Chen J., Pei J., Yin J. Towards Progressive and Load Balancing Distributed Computation: A Case Study on Skyline Analysis // Journal of Computer Science and Technology. 2010. Vol. 25, no. 3. P. 431-443.
42.    Christophe D., Raphael C., Fabienne J. Load balancing of the direct linear multisplitting method in a grid computing environment. Tech. rep. LIFC, 2008. 29 p.
43.    Watchmaker Framework for Evolutionary Computation. Evolving the Mona Liza. Available at: http://watchmaker.uncommons.org/examples/monalisa.php , accessed 01.03.2014.
44.    Watchmaker Framework for Evolutionary Computation. An Evolutionary Sudoku Solver. Available at: http://watchmaker.uncommons.org/examples/sudoku.php , accessed 01.03.2014.
45.    Watchmaker Framework for Evolutionary Computation. Watchmaker. Biomorphs. Available at: http://watchmaker.uncommons.org/examples/biomorphs.php , accessed 01.03.2014.
46.    A Java-based Evolutionary Computation Research System. Available at: http://cs.gmu.edu/~eclab/projects/ecj/, accessed 01.03.2014.
47.    Java  Genetic Algorithm Package. Available at: http://jgap.sourceforge.net/, accessed 01.03.2014.
48.    JCLEC - Java Class Library for Evolutionary Computation. Available at: http://jclec.sourceforge.net/, accessed 01.03.2014.
49.    A Java-based framework for Evolutionary Algorithms (Java/EvA). Available at: http://www.ra.cs.uni-tuebingen.de/software/JavaEvA/, accessed 01.03.2014.
50.    Genetic Algorithm Playground. Available at: www.aridolan.com/ga/gaa/gaa.html, accessed 01.03.2014.
51.    Jenes. Genetic Algorithms in Java. Available at: http://jenes.intelligentia.it/, accessed 01.03.2014.
52.    Evolving Objects (EO): An Evolutionary Computation Framework. Available at: http://eodev.sourceforge.net/, accessed 01.03.2014.
53.    Parizeau G.M. Genericity in Evolutionary Computation Software Tools: Principles and Case Study // International Journal on Artificial Intelligence Tools. 2006. Vol. 15, no. 2. P. 173-194.
54.    HeuristicLab: Paradigm-independent and Extensible Environment for Heuristic Optimization. Available at: http://dev.heuristiclab.com/trac/hl/core, accessed 01.03.2014.
55.    Wagner S., Kronberger G., Beham A., Kommenda M., Scheibenpflug A., Pitzer E., Vonolfen S., Kofler M., Winkler S., Dorfer V., Affenzeller M. Architecture and Design of the HeuristicLab Optimization Environment // In: Advanced Methods and Applications in Computational Intelligence. Springer International Publishing, 2014. P. 197-261. DOI: 10.1007/978-3-319-01436-4_10  (Ser. Topics in Intelligent Engineering and Informatics; vol. 6).