martes, 17 de diciembre de 2013

Algoritmo evolutivo multiobjetivo


Segun Miettinen, en el libro escrito el año 1998 mencionado anteriormente, a finales del siglo veinte, existían más de treinta técnicas de programación matemática para resolver problemas de optimización multiobjetivo. Con todo, la complejidad de muchos problemas de optimización multiobjetivo del mundo real vuelve a estas técnicas inadecuadas o incluso inaplicables para resolverlos. La complejidad de estos problemas se debe, entre otras cosas: A la multimodalidad, a la alta dimensionalidad del espacio de búsqueda, a la discontinuidad de sus funciones objetivo, a desconexiones tanto en el espacio de las variables de decisión como en el de las funciones objetivo, o a que son NP-completos. Algunos investigadores, entre los que destacan Fogel, con el libro escrito el año 1999 titulado “Inteligencia artificial a través de la evolución simulada: Cuarenta años de programación evolutiva”, además de Michalewicz y Fogel, con el libro escrito el año 2000 titulado “Como resolverlo: Heurísticas modernas”, han identificado algunas dificultades que tienen las técnicas clásicas para resolver problemas de optimización multiobjetivo. A continuación se listan algunas de ellas: (1) Los algoritmos necesitan ejecutar varias veces para encontrar varias soluciones del conjunto de óptimos de Pareto. (2) La mayoría de los algoritmos requieren información sobre el dominio del problema que se trata. (3) Algunos algoritmos son sensibles a la forma o continuidad del frente de Pareto. (4) En los problemas que involucran incertidumbre o eventos estocásticos, los métodos clásicos son inadecuados. (5) La dispersión de las soluciones del frente de Pareto depende de la eficiencia del optimizador monoobjetivo.

La complejidad de los problemas de optimización multiobjetivo del mundo real ha conducido a la búsqueda de enfoques alternativos para resolver este tipo de problemas. Uno de esos enfoques lo encabezan los algoritmos evolutivos. A finales de los años 1960, Rosenberg, en la tesis doctoral escrita el año 1967 titulada “Simulación de poblaciones genéticas con propiedades bioquímicas”, plantea utilizar un método genético de búsqueda para resolver problemas de optimización multiobjetivo. No obstante, no fue hasta el año 1984 cuando David Schaffer, en la tesis doctoral titulada “Optimización de objetivos múltiples con algoritmos genéticos de vectores evaluados”, propone la primera implementación de lo que actualmente se conoce como algoritmo evolutivo multiobjetivo. A partir de ese momento, varios investigadores, entre los que destacan Coello y Toscano, con el artículo escrito el año 2001 titulado “Optimización multiobjetivo utilizando un algoritmo micro genético”, además de Zitzler y Thiele, con el artículo escrito el año 1999 titulado “Algoritmos evolucionarios multiobjetivo: Un caso de estudio comparativo y el enfoque del frente de Pareto”, han desarrollado su propio algoritmo evolutivo multiobjetivo. La publicación de los resultados de estos algoritmos mostró la superioridad de los algoritmos evolutivos multiobjetivo sobre las técnicas clásicas de programación matemática. Los algoritmos evolutivos son naturalmente adecuados para resolver problemas de optimización multiobjetivo gracias a que trabajan de manera simultánea con un conjunto de soluciones potenciales, es decir, la población. Esta característica permite encontrar varias soluciones del conjunto óptimo de Pareto en una sola ejecución. Asimismo, son menos sensibles a la forma o continuidad del frente de Pareto. Zitzler y Thiele mencionan que las características fundamentales, de un algoritmo evolutivo multiobjetivo, son las siguientes: Mantener un conjunto de soluciones potenciales, el cual es sometido a un proceso de selección y es manejado por operadores genéticos, generalmente la recombinación y la mutación. Los algoritmos evolutivos y los algoritmos evolutivos multiobjetivo son estructuralmente similares. La diferencia fundamental es que un algoritmo evolutivo multiobjetivo calcula muchas funciones de aptitud.

No hay comentarios:

Publicar un comentario en la entrada