Análisis de rendimiento de una propuesta algorí­tmica basada en la búsqueda local multiobjetivo MOLS | Revista Publicando
Análisis de rendimiento de una propuesta algorí­tmica basada en la búsqueda local multiobjetivo MOLS
Vol 2. No 5. 2015
Ver PDF

Palabras clave

Optimización multiobjetivo
Metaheurísticas
Metaheurísticas basadas en trayectoria Multiobjective optimization
Metaheuristics
Trajectory-based metaheuristics

Cómo citar

Cedeño Muñoz, J. A., Zambrano Vega, C., & Pico Saltos, R. (2015). Análisis de rendimiento de una propuesta algorí­tmica basada en la búsqueda local multiobjetivo MOLS. Revista Publicando, 2(5), 21-35. Recuperado a partir de https://revistapublicando.org/revista/index.php/crv/article/view/91

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.

Ver PDF

Citas

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.

Creative Commons License

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

Descargas

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