REVISIÓN SOBRE ALGORITMOS DE OPTIMIZACIÓN MULTI-OBJETIVO GENÉTICOS Y BASADOS EN ENJAMBRES DE PARTÍCULAS

  • Joaquín Javier Meza Álvarez Universidad Distrital FJC
  • Juan Manuel Cueva Lovelle Universidad de Oviedo
  • Helbert Eduardo Espitia Universidad Distrital FJC
Palabras clave: computación evolutiva, optimización multi-objetivo evolutiva (es_ES)

Resumen (es_ES)

El enfoque evolutivo como también el comportamiento social han mostrado ser una muy buena alternativa en los problemas de optimización donde se presentan varios objetivos a optimizar. De la misma forma, existen todavía diferentes vias para el desarrollo de este tipo de algoritmos. Con el fin de tener un buen panorama sobre las posibles mejoras que se pueden lograr en los algoritmos de optimización bio-inspirados multi-objetivo es necesario establecer un buen referente de los diferentes enfoques y desarrollos que se han realizado hasta el momento.

En este documento se revisan los algoritmos de optimización multi-objetivo más recientes tanto genéticos como basados en enjambres de partículas. Se realiza una revisión critica con el fin de establecer las características más relevantes de cada enfoque y de esta forma identificar las diferentes alternativas que se tienen para el desarrollo de un algoritmo de optimización multi-objetivo bio-inspirado.

Review about genetic multi-objective optimization algorithms and based in particle swarm

ABSTRACT

The evolutionary approach as social behavior have proven to be a very good alternative in optimization problems where several targets have to be optimized. Likewise, there are still different ways to develop such algorithms. In order to have a good view on possible improvements that can be achieved in the optimization algorithms bio-inspired multi-objective it is necessary to establish a good reference of different approaches and developments that have taken place so far. In this paper the algorithms of multi-objective optimization newest based on both genetic and swarms of particles are reviewed. Critical review in order to establish the most relevant characteristics of each approach and thus identify the different alternatives have to develop an optimization algorithm multi-purpose bio-inspired design is performed.

Keywords: evolutionary computation, evolutionary multi-objective optimization.

Descargas

La descarga de datos todavía no está disponible.

Biografía del autor/a

Juan Manuel Cueva Lovelle, Universidad de Oviedo
Catedrático de Escuela Universitaria de Lenguajes y Sistemas Informáticos de la Universidad de Oviedo (España). Director de la Escuela Universitaria de Ingenieria Técnica en Informática de Oviedo (Universidad de Oviedo) desde Julio-1996 a Julio-2004. Director del Departamento de Informática de la Universidad de Oviedo desde 2008 a la actualidad. Socio de ATI y miembro con voto de ACM. Sus áreas de investigación son Tecnologías Orientadas a Objetos, Procesadores de Lenguaje, Interacción Persona-Ordenador, Internet de las cosas, Ingeniería dirigida por modelos e Ingeniería Web. Ha dirigido mas de 25 proyectos de Investigación, más de 100 contratos con empresas y 30 tesis doctorales en Ingeniería Informática. Es autor de libros, artículos y comunicaciones a congresos.
Helbert Eduardo Espitia, Universidad Distrital FJC

Ingeniero Electrónico, Universidad Distrital Francisco José de Caldas, Colombia. Ingeniero Mecatrónico, Universidad Nacional de Colombia, Colombia.  Especialista en Telecomunicaciones Móviles,  Universidad Distrital Francisco José de  Caldas.  Magister en Ingeniería Industrial, Universidad Distrital Francisco José de Caldas. Magister en Ingeniería Mecánica, Universidad Nacional de Colombia. Doctor en Ingeniería de Sistemas y Computación, Universidad Nacional de Colombia.

Referencias

C. Coello, D. Van Veldhuizen, G. Lamont, Evolutionary Algorithms for Solving Multi-Objective Problems, Springer, Second Edition, 2007.

C. Coello., M. Salazar, MOPSO: A proposal for multiple objective particle swarm optimization, In Proceedings of the IEEE Congress of Evolutionary Compututation, 2002.

D. Van Veldhuizen, G. Lamont, “Multiobjective Evolutionary Algorithms: Analyzing the State-of-the-Art”, Evolutionary Computation, vol. 8, no. 2, pp. 125-147, 2000.

J. Schaffer, Multiple Objective Optimization with Vector Evaluated Genetic Algorithms, Proceedings of the First International Conference on Genetic Algorithms and Their Applications, pp. 93-100, 1985.

D. Van Veldhuizen, Multiobjective Evolutionary Algorithms: Classifications, Analyses, and New Innovations, Ph.D. thesis, Air Force Institute of Technology, Wright - Patterson AFB, Ohio, 1999.

E. Zitzler, L. Thiele, An evolutionary algorithm for multiobjective optimization: The strength Pareto approach, Technical report 43, Computer engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH) Zurich, 1999.

E. Zitzler, L. Thiele, “Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach”, IEEE Transaction on Evolutionary Computation, vol 3, no. 4, pp. 257-271, 1999.

J. Knowles, D. Corne, The Pareto archived evolution strategy: A new baseline algorithm for Pareto multiobjective optimization, IEEE Congress on Evolutionary Computation (CEC), 1999.

D. Corne, J. Knowles, M. Oates, “The Pareto envelope - based selection algorithm for multiobjective optimization”, Parallel Problem Solving from Nature - PPSN VI, pp. 839-848, 2000.

K. Deb, S. Agrawal, A. Pratap, T. Meyarivan, “A fast elitist non - dominated sorting genetic algorithm for multi-objective optimization: NSGA II”, Parallel Problem Solving From Nature - PPSN VI, pp. 849-858, 2000.

E. Zitzler, M. Laumanns, L. Thiele, SPEA 2: Improving the Strength Pareto Evolutionary algorithm, Technical report 103, Computer engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH) Zurich, 2001.

D. Dumitrescu, C. Grosan, M. Oltean, Simple Multiobjective, Evolutionary Algorithm, Seminars on Computer Science, Faculty of Mathematics and Computer Science, Babe-Bolyai University of Cluj-Napoca, pp. 3-12, 2001.

D. Dumitrescu, C. Grosan, M. Oltean, “A new evolutionary adaptive representation paradigm”, Studia Universitas Babes-Bolyai, Seria Informatica, vol. XLVI, no. 1, pp. 15-30, 2001.

D. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Publishing Co., Reading, Massachusetts, 1989.

N. Srinivas, K. Deb, “Multiobjective optimization using nondominated sorting in genetic algorithms”, Journal of Evolutionary Computation, vol. 2, no. 3, pp. 221-248, 1994.

J. Horn, N. Nafpliotis, D. Goldberg, A niched Pareto genetic algorithm for multiobjective optimization, IEEE World Congress on Computational Intelligence, IEEE Conference on Evolutionary Computation, 1994.

M. Erickson, A. Mayer, J. Horn, “The niched Pareto genetic algorithm 2 applied to the design of groundwater remediation systems”, Evolutionary Multi-Criterion Optimization, Lecture Notes in Computer Science, vol. 1993, pp. 681-695, 2001.

E. Zitzler, M. Laumanns, L. Thiele, “SPEA 2: Improving the Strength Pareto Evolutionary Algorithm”, CIMNE, Evolutionary Methods for Design, Optimisation, and Control, pp. 95-100, 2002.

D. Cvetkovic, I. Parmee, “Preferences and their application in evolutionary multiobjective optimization”, IEEE Transactions on Evolutionary Computation, vol. 6, no. 1, pp. 42-57, 2002.

A. Lara, G. Sanchez, C. Coello, O. Schutze, “HCS: A New Local Search Strategy for Memetic Multiobjective Evolutionary Algorithms”, IEEE Transactions on Evolutionary Computation, vol. 14, no. 1, 2010.

Y. Junchi, L. Guoqiang, Double space based multiobjective evolutionary algorithm, International Conference on Machine Learning and Cybernetics (ICMLC), 2012.

P. Bosman, “On Gradients and Hybrid Evolutionary Algorithms for Real-Valued Multiobjective Optimization”, IEEE Transactions on Evolutionary Computation, vol. 16, no. 1, 2012.

D. Brockhoff, E. Zitzler, Improving hypervolume-based multiobjective evolutionary algorithms by using objective reduction methods, IEEE Congress on Evolutionary Computation (CEC), 2007.

I. Karahan, M. Köksalan, “A Territory Defining Multiobjective Evolutionary Algorithms and Preference Incorporation”, IEEE Transactions on Evolutionary Computation, vol. 14, no. 4, 2010.

Z. Qingfu, L. Hui, “MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition”, IEEE Transactions on Evolutionary Computation, vol. 11, no. 6, 2007.

L. Chi-Ho, K. Ye-Hoon, K. Jong-Hwan, Multiobjective evolutionary algorithm reinforcing specific objective, IEEE Congress on Evolutionary Computation (CEC), 2008.

L. Hai-lin, L. Xueqiang, The multiobjective evolutionary algorithm based on determined weight and sub-regional search, IEEE Congress on Evolutionary Computation (CEC), 2009.

G. Montemayor-Garcia, G. Toscano-Pulido, A study of surrogate models for their use in multiobjective evolutionary algorithms, 8th International Conference on Electrical Engineering Computing Science and Automatic Control (CCE), 2011.

Z. Aimin, Z. Qingfu, Z. Guixu, A multiobjective evolutionary algorithm based on decomposition and probability model, IEEE Congress on Evolutionary Computation (CEC), 2012.

L. Hai-Lin, W. Dan, A constrained multiobjective evolutionary algorithm based decomposition and temporary register, IEEE Congress on Evolutionary Computation (CEC), 2013.

W. Chen, Y. Gong, Z. Zhan, J. Zhang, Y. Li, Y. Tan, “An Evolutionary Algorithm with Double-Level Archives for Multiobjective Optimization”, IEEE Transactions on Cybernetics, vol. PP, no. 99, 2014.

W. Rui, R. Purshouse, P. Fleming, “Preference-Inspired Coevolutionary Algorithms for Many-Objective Optimization”, IEEE Transactions on Evolutionary Computation, vol. 17, no. 4, pp. 474-494, 2013.

Q. Rongbin, D. Wenli, W. Zhenlei, Q. Feng, Multiobjective evolutionary algorithm based on the Pareto Archive and individual migration, 7th World Congress on Intelligent Control and Automation (WCICA), 2008.

J. Fieldsend, R. Everson, S. Singh, “Using unconstrained elite archives for multiobjective optimization”, IEEE Transactions on Evolutionary Computation, vol. 7, no. 3, pp. 305-323, 2003.

H. Shinn-Ying, S. Li-Sun, C. Jian-Hung, “Intelligent evolutionary algorithms for large parameter optimization problems”, IEEE Transactions on Evolutionary Computation, vol. 8, no. 6, pp. 522-541, 2004.

H. Sato, H. Aguirre, K. Tanaka, Local dominance using polar coordinates to enhance multiobjective evolutionary algorithms, Congress on Evolutionary Computation, 2004.

H. Sato, H. Aguirre, K. Tanaka, On the locality of dominance and recombination in multiobjective evolutionary algorithms, IEEE Congress on Evolutionary Computation, 2005.

W. Yong, C. Zixing, A constrained optimization evolutionary algorithm based on multiobjective optimization techniques, IEEE Congress on Evolutionary Computation, 2005.

M. Sato, H. Aguirre, K. Tanaka, Effects of d-Similar Elimination and Controlled Elitism in the NSGA-II Multiobjective Evolutionary Algorithm, IEEE Congress on Evolutionary Computation (CEC), 2006.

C. Zixing, W. Yong, “A Multiobjective Optimization-Based Evolutionary Algorithm for Constrained Optimization”, IEEE Transactions on Evolutionary Computation, vol. 10, no. 6, 2006.

L. Rachmawati, D. Srinivasan, “Multiobjective Evolutionary Algorithm With Controllable Focus on the Knees of the Pareto Front”, IEEE Transactions on Evolutionary Computation, vol. 13, no. 4, 2009.

Y. Song, J. Ji, Y. Wang, C. Liu, A New Evolutionary Algorithm for Solving Multiobjective Optimization, Fifth International Conference on Natural Computation (ICNC), 2009.

D. Phan, J. Suzuki, Boosting Indicator-Based Selection Operators for Evolutionary Multiobjective Optimization Algorithms, 23rd IEEE International Conference on Tools with Artificial Intelligence (ICTAI), 2011.

C. Chi, Y. Shiu, “A Multiobjective Evolutionary Algorithm That Diversifies Population by Its Density”, IEEE Transactions on Evolutionary Computation, vol. 16, no. 2, 2012.

L. Ke, A. Fialho, S. Kwong, Z. Qingfu, “Adaptive Operator Selection With Bandits for a Multiobjective Evolutionary Algorithm Based on Decomposition”, IEEE Transactions on Evolutionary Computation, vol. 18, no. 1, 2014.

K. Parsopoulos, M. Vrahatis, Multi-Objective Particles Swarm Optimization Approaches, IGI Global, 2008.

K. Parsopoulos, M. Vrahatis, Particle swarm optimization method in multiobjective problems, In Proceedings of the ACM Symposium on Applied Computing, 2002.

U. Baumgartner, C. Magele, W. Renhart, “Pareto optimality and particle swarm optimization”, IEEE Transactions on Magnetics, vol. 40, no. 2, pp. 1172-1175, 2004.

M. Mahfouf, M. Chen, D. Linkens, “Adaptive weighted particle swarm optimisation for multi-objective optimal design of alloy steels”, Lecture notes in computer science, vol. 3242, pp. 762-771, 2004.

X. Li, “A non-dominated sorting particle swarm optimizer for multi-objective optimization”, Lecture notes in computer science, vol. 2723, pp. 37-48 2003.

X. Hu, R. Eberhart, Multi-objective optimization using dynamic neighborhood particle swarm optimization, IEEE Congress Evolutionary Compututation, 2002.

X. Hu, R. Eberhart, Y. Shi, Particle swarm with extended memory for multi-objective optimization, IEEE Swarm Intelligence Symposium, 2003.

K. Parsopoulos, M. Vrahatis, On the computation of all global minimizers through particle swarm optimization, IEEE Transactions on Evolutionary Computation, 2004.

C. Chow, H. Tsui, Autonomous agent response learning by a multi-species particle swarm optimization, IEEE Congress on Evolutionary Computation, 2004.

J. Fieldsend, S. Singh, A multiobjective algorithm based upon particle swarm optimisation, An efficient data structure and turbulence, In Proceedings of the UK Workshop on Computational Intelligence, 2002.

T. Ray, K. Liew, “A swarm metaphor for multi-objective design optimization”, Engineering Optimization, vol. 34. no. 2, pp. 141-153, 2002.

T. Bartz-Beielstein, P. Limbourg, J. Mehnen, K. Schmitt, K. Parsopoulos, M. Vrahatis, Particle swarm optimizers for Pareto optimization with enhanced archiving techniques, IEEE Congress on Evolutionary Computation, 2003.

D. Srinivasan, T. Seow, Particle swarm inspired evolutionary algorithm (PSEA) for multi-objective optimization problem, IEEE Congress on Evolutionary Computation, 2003.

S. Mostaghim, J. Teich, Strategies for finding good local guides in multi-objective particle swarm optimization (MOPSO), IEEE Swarm Intelligence Symposium, 2003.

X. Li, “Better spread and convergence: Particle swarm multi-objective optimization using the maximin fitness function”, Lecture notes in computer science, vol. 3102, pp. 117-128, 2004.

G. Toscano, C. Coello, “Using clustering techniques to improve the performance of a particle swarm optimizer”, Lecture notes in computer science, vol. 3102, pp. 225-237, 2004.

M. Reyes-Sierra, C. Coello, Online adaptation in multi-objective particle swarm optimization, IEEE Swarm Intelligence Symposium, 2006.

S. Ho, S. Yang, G. Ni, E. Lo, H. Wong, “A particle swarm optimization-based method for multi-objective design optimizations”, IEEE Transactions on Magnetics, vol. 41, no. 5, pp. 1756-1759, 2005.

C. Raquel, P. Naval, An effecive use of crowding distance in multi-objective particle swarm optimization, In Proceedings of the GECCO, 2005.

J. Alvarez-Benitez, R. Everson, J. Fieldsend, “A MOPSO algorithm based exclusively on Pareto dominance concepts”, Lecture notes in computer science, vol. 3410, pp. 459-473, 2005.

M. Salazar, J. Rowe, Particle swarm optimization and fitness sharing to solve multi-objective optimization problems, IEEE Congress on Evolutionary Computation, 2005.

S. Mostaghim, J. Teich, “About selecting the personal best in multi-objective particle swarm optimization”, Lecture notes in computer science, vol. 4193, pp. 523-532, 2006.

X. Huo, L. Shen, H. Zhu, “A smart particle swarm optimization algorithm for multiobjective problems”, Lecture notes in computer science, vol. 4115, pp. 72-80, 2006.

M. Reyes-Sierra M., C. Coello, Online adaptation in multi-objective particle swarm optimization, IEEE Swarm Intelligence Symposium, 2006.

P. Tripathi, S. Bandyopadhyay, S. Pal, Adaptive mufti-objective particle swarm optimization algorithm, IEEE Congress on Evolutionary Computation (CEC), 2007.

S. Agrawal, Y. Dashora, M. Tiwari, S. Young-Jun, “Interactive Particle Swarm: A Pareto-Adaptive Metaheuristic to Multiobjective Optimization”, IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans, vol. 38, no. 2, pp. 258-277, 2008.

W. Hui, Q. Feng, Improved PSO-based Multi-Objective Optimization using inertia weight and acceleration coefficients dynamic changing, crowding and mutation, 7th World Congress on Intelligent Control and Automation (WCICA), 2008.

L. Wen-Fung, G. Yen, Dynamic swarms in PSO-based multiobjective optimization, IEEE Congress on Evolutionary Computation (CEC), 2007.

L. Wen-Fung, G. Yen, “PSO-Based Multiobjective Optimization With Dynamic Population Size and Adaptive Local Archives”, IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 38, no. 5, pp. 1270-1293, 2008.

C. Jinyin, Y. Dongyong, Constrained handling in multi-objective optimization based on Quantum-behaved particle swarm optimization, Sixth International Conference on Natural Computation (ICNC), vol. 8, 2010.

M. Hossain, M. Hossain, M. Hashem, M. Ali, Quantum Evolutionary Algorithm based on Particle Swarm theory in multiobjective problems, 13th International Conference on Computer and Information Technology (ICCIT), 2010.

W. Jingxuan, W. Yuping, A New Model Based Hybrid Particle Swarm Algorithm for Multi-objective Optimization, Third International Conference on Natural Computation (ICNC), vol. 3, 2007.

W. Leong, G. Yen, Impact of tuning parameters on dynamic swarms in PSO-based multiobjective optimization, IEEE Congress on Evolutionary Computation (CEC) (IEEE World Congress on Computational Intelligence), 2008.

G. Haichang, Z. Weizhou, Multiobjective Optimization Using Clustering Based Two Phase PSO, Fourth International Conference on Natural Computation (ICNC), vol. 6, 2008.

G. Yen, L. Wen, “Dynamic Multiple Swarms in Multiobjective Particle Swarm Optimization”, IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans, vol. 39, no. 4, pp. 890-911, 2009.

W. Elloumi, A. Alimi, A more efficient MOPSO for optimization, IEEE/ACS International Conference on Computer Systems and Applications (AICCSA), 2010.

Z. Zhi-Hui, L. Jingjing, C. Jiannong, Z. Jun, “Multiple Populations for Multiple Objectives: A Coevolutionary Technique for Solving Multiobjective Optimization Problems”, IEEE Transactions on Cybernetics, vol. 43, no. 2, pp. 445-463, 2013.

M. Helbig, A. Engelbrecht, Heterogeneous dynamic vector evaluated particle swarm optimisation for dynamic multi-objective optimisation, IEEE Congress on Evolutionary Computation (CEC), 2014.

P. Wei, Z. Qingfu, A decomposition-based multi-objective Particle Swarm Optimization algorithm for continuous optimization problems, IEEE International Conference on Granular Computing (GrC), 2008.

A. De Carvalho, A. Pozo, Analyzing the control of dominance area of solutions in particle swarm optimization for many-objective, 10th International Conference on Hybrid Intelligent Systems (HIS), 2010.

L. Chi-Nien, H. Chih-Li, L. Shu-Yan, Yu. Yu-Hsiang, Taguchi-based disturbance with tournament selection to improve on MOPSO, IEEE Congress on Evolutionary Computation (CEC), 2011.

Y. Jintao, Y. Bo, Z. Mingwu, K. Yuyan, Multiobjective Particle Swarm Optimization with Predatory Escaping Behavior, 3rd International Workshop on Intelligent Systems and Applications (ISA), 2011.

O. Soliman, S. Mohamed, E. Ramadan, A Bio-Inspired Memetic Particle Swarm Optimization Algorithm for Multi-objective Optimization Problems, Third International Conference on Innovations in Bio-Inspired Computing and Applications (IBICA), 2012.

H. Hirano, T. Yoshikawa, A study on two-step search using global-best in PSO for Multi-Objective Optimization Problems, 6th International Conference on Soft Computing and Intelligent Systems (SCIS) and 13th International Symposium on Advanced Intelligent Systems (ISIS), 2012.

H. Hirano, T. Yoshikawa, A study on two-step search based on PSO to improve convergence and diversity for Many-Objective Optimization Problems, IEEE Congress on Evolutionary Computation (CEC), 2013.

Z. Guangrui, M. Mahfouf, G. Panoutsos, W. Shen, A multi-objective particle swarm optimization algorithm with a dynamic hypercube archive, mutation and population competition, IEEE Congress on Evolutionary Computation (CEC), 2012.

T. Uchitane, T. Hatanaka, Experimental study for multi-objective PSO with single objective guide selection, IEEE Congress on Evolutionary Computation (CEC), 2012.

A. Nebro, J. Durillo, C. Coello, Analysis of leader selection strategies in a multi-objective Particle Swarm Optimizer, IEEE Congress on Evolutionary Computation (CEC), 2013.

Y. Zhenlun, A. Wu, M. Huaqing, A Multi-objective PSO algorithm with transposon and elitist seeding approaches, Sixth International Conference on Advanced Computational Intelligence (ICACI), 2013.

G. Ying, P. Lingxi, L. Fufang, L. Miao, Multi-objective cloud estimation of distribution particle swarm optimizer using maximum ranking, 10th International Conference on Natural Computation (ICNC), 2014.

S. Xiaoyan, X. Ruidong, Z. Yong, G. Dunwei, Sets evolution-based particle swarm optimization for many-objective problems, IEEE International Conference on Information and Automation (ICIA), 2014.

L. Man-Fai, N. Sin-Chun, C. Chi-Chung, A. Lui, A new strategy for finding good local guides in MOPSO, IEEE Congress on Evolutionary Computation (CEC), 2014.

H. Wang, G. Yen, “Adaptive Multiobjective Particle Swarm Optimization Based on Parallel Cell Coordinate System”, IEEE Transactions on Evolutionary Computation, vol. 19, no. 1, pp. 1-18, 2015.

Cómo citar
Meza Álvarez, J. J., Cueva Lovelle, J. M., & Espitia, H. E. (2016). REVISIÓN SOBRE ALGORITMOS DE OPTIMIZACIÓN MULTI-OBJETIVO GENÉTICOS Y BASADOS EN ENJAMBRES DE PARTÍCULAS. Redes De Ingeniería, 6(2), 54-76. https://doi.org/10.14483/udistrital.jour.redes.2015.2.a06
Publicado: 2016-03-09
Sección
Revisión