Palabras clave
Metaheurísticas
Metaheurísticas basadas en trayectoria
Categorías
Cómo citar
Resumen
En este artículo se presenta una propuesta algorítmica basada en la búsqueda local multiobjetivo (Multiobjective Local Search MOLS) y se lleva a cabo un estudio comparativo de su rendimiento frente a dos algoritmos clásicos en el área: NonDominated Sorting Genetic Algorithm-II (NSGA-II) y Pareto Archived Evolution Strategy (PAES), seleccionados como punto de comparación, el primero, por ser la principal referencia en el campo de la optimización multiobjetivo y el segundo por emplear una búsqueda local similar a la propuesta.
El objetivo es conocer cuán competitivas pueden ser las metaheurísticas basadas en métodos de trayectorias para resolver problemas de optimización multiobjetivo (MOPs) de complejidad NP-completo.
Los experimentos se realizaron sobre el conjunto de problemas del benchmark ZDT Test Suite. En el análisis de los resultados se emplearon tres indicadores de calidad multiobjetivo: Epsilon, Spread e Hipervolumen.
Los resultados generados por el algoritmo MOLS muestran tener una mayor diversidad de soluciones y una mejor convergencia hacia el verdadero frente de Pareto-í“ptimo en relación a los resultados generados por los algoritmos NSGA-II y PAES.
Referencias
Beume, N., Naujoks, B. y Emmerich, M. 2007. Sms-emoa: Multiobjective selection based on dominated hypervolume.
European Journal of Operational Research, 181, 1653-1669.
Bradstreet, L. 2011. The hypervolume indicator for multi-objective optimization: calculation and use. University of Western Australia, Ph.D. thesis.
Coello, C.A., Lamont, G.B. y Van Veldhuizen, D.A. 2007. Evolutionary Algorithms for Solving Multi-Objective Problems. New York, NY: Springer, pp. 1–40.
Coello, C.A. 1999. A Comprehensive Survey of Evolutionary-Based Multiobjective Optimization Techniques. Knowledge and Information Systems. An International Journal 1(3): 269-308.
Deb, K., Pratap, A., Agarwal, S. y Meyarivan, T. 2002. A fast and elitist multiobjective genetic algorithm: Nsga-ii. Evolutionary Computation, IEEE Transactions on 6: 182-197.
Durillo, J. y Nebro, A. 2011. jMetal: A Java framework for multi-objective optimization, Advances in Engineering Software, 42(10): 760-771.
Fonseca, C.M. y Flemming, P.J. 1995. An Overview of Evolutionary Algorithms in Multiobjective Optimization, Evolutionary Computation, 3(1): 1-16.
Horn, J., Nafpliotis, N., y Goldberg, D.E. 1994. A niched Pareto genetic algorithm for multiobjective optimization in Proc. 1st Int. Conf. Evol. Comput, pp. 82–87.
Ishibuchi, H., Murata, T. 1998. A multi-objective genetic local search algorithm and its application to flowshop scheduling. Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on 28(3): 392,403.
Knowles, J., Corne, D. 1999. The Pareto archived evolution strategy: a new baseline algorithm for Pareto multiobjective optimization. Evolutionary Computation, CEC 99. Proceedings of the 1999 Congress on 1: 105
Nebro, A.J., Durillo, J.J. y Vergne, M. 2015. Redesigning the jMetal Multi-Objective Optimization Framework. Proceedings of the Companion Publication of the 2015 on Genetic and Evolutionary Computation Conference (GECCO Companion '15) Pages 1093-1100.
Osyczka, A. 1985. Multicriteria Optimization for Engineering Design, Academic Press.
Schaus, P., Hartert, R. 2013. Multi-Objective Large Neighborhood Search. 19th International Conference, CP 2013, Uppsala, Sweden. Proceedings, pp 611-627.
Van Veldhuizen, D.A. y Lamont, G.B. 2000. Multiobjective Evolutionary Algorithms: Analyzing the State-of-the-Art, Evolutionary Computation 8(2): 125-147.
Wei, X., Zhang, W., Weng, W., Fujimura, S. 2012. Multi-objective Local Search Combined with NSGA-II for Bi-criteria Permutation Flow Shop Scheduling Problem .IEEJ Transactions on Electronics, Information and Systems, 132(1): 32-41.
Zhang, Q. y Li, H. 200. Moea/d: A multiobjective evolutionary algorithm based on decomposition. Evolutionary Computation, IEEE Transactions on 11: 712-731.
Zitzler, E., Deb y K., Thieler, L. 2000. Comparison of multiobjective evolutionary algorithms: Empirical results. IEEE Trans. on Evol. Computation 8: 173-195.
Zitzler, E., Laumanns, M. y Thiele, L. 2001. SPEA2: Improving the strength Pareto evolutionary algorithm. Swiss Federal Inst. Technol., Lausanne, Switzerland, Tech. Rep. TIK-Report 103.
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-CompartirIgual 4.0.
Derechos de autor 2019 Cristian Zambrano Vega, Joel A. Cedeño Muñoz, Roberto Pico Saltos