Los algoritmos genéticos en la optimización multiobjetivo

Yaimi Barcenas Mompeller, Alexander Sánchez Díaz

Resumen

Hoy día las computadoras tienen un gran impacto en todas las esferas de la vida. Resulta casi imprescindible el uso de las mismas en las tareas que se acometen a diario los investigadores de las universidades y centros de investigación del mundo. En empresas, industrias y hasta para el entretenimiento resulta difícil, sino imposible encontrar un proceso en el que estas no estén presentes.

Con el empleo de las computadoras en diferentes esferas, se ha ido incrementando la complejidad de los problemas a resolver y se han hecho más demandantes las soluciones que estas deben brindar. Poco a poco, han ido surgiendo problemas cuya solución no se puede resolver por una secuencia de pasos o cuyo procedimiento computacional requiere un costo elevado. De manera que se ha abierto el camino a nuevas técnicas que permiten solucionar estos grandes y complejos problemas que van surgiendo.

Los problemas con múltiples objetivos se encuentran presentes en la mayoría de las disciplinas y su solución siempre ha representado un reto para los investigadores. La disciplina de la Inteligencia Artificial permite resolver problemas para los cuales no existe una solución algorítmica y en caso de existir, la complejidad computacional asociada a esta es muy elevada. Los procedimientos meta-heurísticos han demostrado una gran efectividad en la solución de problemas complejos de optimización.

La optimización es el proceso de buscar la mejor solución posible para determinado problema. Puede verse como la búsqueda de los valores de las variables de decisión para los que cierta Función Objetivo (FO) logra su valor extremo (Chong & Zak, 2013). Los métodos tradicionales de optimización están caracterizados por una elevada complejidad computacional. Las técnicas heurísticas constituyen una opción ante tal limitación  aunque no garantizan la solución óptima, son capaces de encontrar fácilmente una buena solución en un tiempo prudencial.

 

Los problemas de optimización (PO) involucran una única función objetivo que, salvo en el caso multimodal, usualmente poseen una única solución óptima. Por otro lado, los problemas de optimización multiobjetivo (POM) consideran simultáneamente varias funciones objetivo usualmente en conflicto. En este caso, se obtiene un conjunto de alternativas llamadas soluciones óptimas de Pareto o soluciones no-dominadas (Chong & Zak, 2013).

Múltiples son las meta-heurísticas que han sido aplicadas exitosamente en la solución de PO complejos, dentro de ellas en particular las basadas en poblaciones. La aplicación de estos métodos se ha extendido igualmente a entornos multiobjetivo, debido a su probada capacidad de explorar el espacio de búsqueda de una manera inherentemente concurrente y con ello aproximar el conjunto óptimo de Pareto de un problema de optimización multiobjetivo en una sola ejecución (Osman & Kelly, 2008).

Muchas instituciones a nivel internacional han mostrado su interés por el estudio y desarrollo de estas meta-heurísticas, encaminadas fundamentalmente a la mejora de los métodos ya existentes mediante el perfeccionamiento de alguna característica fundamenta la incorporación de nuevas ideas de otras meta-heurísticas a manera de métodos híbridos. Dentro de estas entidades se pueden nombrar los laboratorios de Soft Computing and Intelligent Information Systems (SCI2S),el Institut de Recherches Interdiciplinaires et de Développements en Intelligence Artificielle (IRIDIA) de la Universidad de Granada, en España, y la Universidad Libre de Bruselas, en Bélgica. Nuestro país también cuenta con centros especializados en el desarrollo de estas áreas de la ciencia como son el grupo de Optimización en el Instituto de Cibernética, Matemática y Física (ICIMAF), el Centro de Estudios de Ingeniería de Sistemas del ISPJAE, el grupo de Optimización de la UH y el Laboratorio de Inteligencia Artificial de la UCLV.

La Dirección de Informatización de la Universidad Agraria de La Habana (UNAH) junto con el grupo de investigación Procesos de Negocios (PRONEG), tiene dentro de sus líneas de investigación el trabajo relacionado con la minería de procesos. Dentro de esto, se encuentra trabajando en la implementación de algoritmos para el descubrimiento y optimización de modelos de procesos a partir de los modelos de los procesos y de los registros de eventos que se obtienen de la ejecución de los sistemas informáticos. El objetivo del presente trabajo radica en el estudio de las meta-heurísticas basadas en población dentro de los cuales se hace alusión a los Algoritmos Genéticos como son el Non dominated Sort Genetic Algorithm II (NSGAII) por (Deb, et al., 2002), el Strength Pareto Evolutionary Algorithm 2 (SPEA2) por (Zitzler et al., 2000) y Optimización basada en mallas variables (Puris et al., 2011).

Texto completo:

Sin título

Referencias

Back, T.(1996). Evolutionary Algorithms in Theory and Practice: Evolution Strategies Evolutionary Programming Genetic Algorithms. New york: Oxtford University Press.

Blum, C. & Roli, A.(2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys, Issue 35, pp. 268-308 pp.

Cáceres, A. 2009. Desarrollo de metaheuristicas poblacionales para la solucion de problemas complejos.. Departamento de Ciencia de la Computación. Uiversidad Central Marta Abreu de las Villas, Santa Clara.

Chong, E. & Zak, S.(2013). An introduction to optimization. En: An introduction to optimization 4th ed. Segunda ed. s.l.:John Wiley & Sons, p. 15.

Deb, K.(1999). Multi-objective Genetic Algorithms: Problem Difficulties and Construction of Test Problems. Evolutionary Computation, Issue 3. 205-230 pp.

Deb, K., Patrap, A., Agarwal, S. & Meyarivan, T., 2002. A Fast and Elitist Multi-Objective Genetic Algorithm: NSGAII. IEEE Transactions on Evolutionary Computation, 6(2). 182-197 pp.

Díaz, E., Martinez, A. & Gálvez, D.(2016). Una implementación de la meta-heuristica “Optimización en Mallas Variables” en la arquitectura CUDA. Revista Cubana de Ciencias Informáticas, 10(3).

Edgeworth, F. Y., 1881. Mathematical Physics. P. Keagan.

Ehrgott, M. & Wiecek, M., 2005. Multiobjetive programming: Multiple criteria decision analysis state of the art surveys. Springer, Issue 667-722.

Goldberg, D., 1998. Genetic Algorithms in Search. University of Alabama: Addison-Wesley Publishing Company.

Hooker, J., 1995. Testing Heuristics: We Have It All Wrong. Journal of Heuristics, Volumen 1. 33-42 pp.

Miettinen, K., 2008. Intorduction to Multiobjetive Optimization: Noninteractive Approaches. Springer berlin Heidelberg, Volumen 5252, pp. 1-26.

Osman, I. & Kelly, J., 2008. Meta-heuristics: theory and applications. s.l.:Kluwer Academic.

Pareto, V., 1896. Cours D'Economie Politique. F. Rouge.

Puris, A. & Bello, R.(2009). Optimización basada en Mallas Dinámicas. Su aplicacion en la solución de problemas de optimizacion continuos. Proc. of Memorias del VI Congreso Español sobre Metaheurísticas, Algoritmos Evolutivos y Bioisnpirados, pp. 441-448 pp.

Puris, A., Bello, R., Molina, D. & Herrera, F.(2011). Variable mesh optimization for continuos optimization problems. Soft Computing, 16(3), pp. 511-525.

Zitzler, E., Laumanns, M. & Thiele, L.(2000). SPEA2: Improving the Strengh Pareto Evolutionar Algorithm. Computer Engineering and Networks Laboratory (TIK).

Zitzler, E., Knowles, J. & Thiele, L., (2008). Quality Assessment of Pareto Set Approximations. Springer Berlin Heidelberg, Volumen 5252. 373-404 pp.

Enlaces refback

  • No hay ningún enlace refback.