Optimización multimodal evolutiva
En matemáticas aplicadas, la optimización multimodal evolutiva se ocupa de las tareas de optimización que implican encontrar todas o la mayoría de las soluciones múltiples (al menos localmente óptimas) de un problema, en lugar de una única y mejor solución. La optimización multimodal evolutiva es una rama de la computación evolutiva , que está estrechamente relacionada con el aprendizaje automático. Wong proporciona una breve encuesta, en la que el capítulo de Shir y el libro de Preuss cubren el tema con más detalle.[1][2][3]
Motivación
editarEl conocimiento de múltiples soluciones para una tarea de optimización es especialmente útil en ingeniería, cuando debido a limitaciones físicas (y/o de costo), los mejores resultados pueden no siempre ser realizables. En tal escenario, si se conocen soluciones múltiples (local y/o globalmente óptimas), la implementación puede cambiarse rápidamente a otra solución y obtener el mejor rendimiento posible del sistema. También se podrían analizar múltiples soluciones para descubrir propiedades (o relaciones) ocultas del problema de optimización subyacente, lo que las hace importantes para obtener conocimiento de dominio. Además, los algoritmos para optimización multimodal no solo localizan óptimos múltiples en una sola ejecución, sino que también preservan la diversidad de su población, lo que da como resultado su capacidad de optimización global en funciones multimodales. Además, las técnicas para la optimización multimodal suelen tomarse prestadas como técnicas de mantenimiento de diversidad para otros problemas.[4]
Antecedentes
editarLas técnicas clásicas de optimización necesitarían múltiples puntos de reinicio y múltiples ejecuciones con la esperanza de que se pueda descubrir una solución diferente en cada ejecución, sin ninguna garantía. Los algoritmos evolutivos (EA) debido a su enfoque basado en la población, proporcionan una ventaja natural sobre las técnicas de optimización clásicas. Mantienen una población de soluciones posibles, que se procesan cada generación, y si las soluciones múltiples se pueden preservar a lo largo de todas estas generaciones, a la terminación del algoritmo tendremos varias soluciones buenas, en lugar de solo la mejor solución. Tenga en cuenta que esto va en contra de la tendencia natural de las técnicas de optimización clásicas, que siempre convergerán a la mejor solución, o una solución subóptima (en una función robusta de "mal comportamiento"). La búsqueda y el mantenimiento de soluciones múltiples es donde radica el desafío de usar EA para la optimización multimodal. Niching[5] es un término genérico referido como la técnica de encontrar y preservar múltiples nichos estables, o partes favorables del espacio de soluciones posiblemente en torno a múltiples soluciones, para evitar la convergencia a una única solución.
El campo de los algoritmos evolutivos abarca algoritmos genéticos (GA), estrategia de evolución (ES), evolución diferencial (DE), optimización de enjambre de partículas (PSO) y otros métodos. Se han realizado intentos para resolver la optimización multimodal en todos estos ámbitos y la mayoría, si no todos los distintos métodos implementan niching de alguna forma u otra.
Optimización multimodal utilizando algoritmos genéticos / estrategias de evolución
editarEl método de hacinamiento de De Jong, el enfoque de la función de intercambio de Goldberg, el método de compensación de Petrowski, el apareamiento restringido y el mantenimiento de múltiples subpoblaciones son algunos de los enfoques populares que la comunidad ha propuesto. Los primeros dos métodos están especialmente bien estudiados, sin embargo, no realizan una separación explícita en soluciones que pertenecen a diferentes cuencas de atracción.
La aplicación de la optimización multimodal dentro de ES no fue explícita durante muchos años, y se ha explorado solo recientemente. Shir introdujo un framework de niching que utiliza ES no aleatorio,[6] proponiendo el CMA-ES como optimizador de niching por primera vez . El fundamento de ese framework fue la selección de un pico individual por subpoblación en cada generación, seguido de su muestreo para producir la dispersión consecutiva de los puntos de búsqueda. La analogía biológica de esta maquinaria es que un macho alfa gana todas las competiciones impuestas y domina a partir de entonces su nicho ecológico , que luego obtiene todos los recursos sexuales para generar su descendencia.
Recientemente, se propuso un enfoque evolutivo de optimización multiobjetivo (EMO),[7] en el cual se agrega un segundo objetivo adecuado al problema de optimización multimodal objetivado originalmente, de modo que las soluciones múltiples forman un frente pareto-óptimo débil . Por lo tanto, el problema de optimización multimodal se puede resolver para sus múltiples soluciones usando un algoritmo EMO. Mejorando su trabajo, los mismos autores han hecho su algoritmo autoadaptativo, eliminando así la necesidad de preespecificar los parámetros.[8]
En cambio, se propone un enfoque que no utiliza ningún radio para separar la población en subpoblaciones (o especies) sino que emplea la topología espacial.[9]
Optimización multimodal utilizando DE
editarLos métodos de niching utilizados en GA también se han explorado con éxito en la comunidad DE. La selección local basada en DE y los enfoques de selección global también se han intentado para resolver problemas multimodales. Los DE combinados con los algoritmos de búsqueda locales (Memetic DE) se han explorado como un enfoque para resolver problemas multimodales.
Para un tratamiento integral de los métodos de optimización multimodal en DE, consulte la tesis doctoral Ronkkonen, J. (2009). Optimización global multimodal continua con métodos basados en la evolución diferencial.[10]
Optimización multimodal utilizando algoritmo GSO basado en inteligencia de enjambre
editarGlowworm swarm optimization (GSO) es un algoritmo basado en inteligencia de enjambre, introducido por KN Krishnanand y D. Ghose en 2005, para el cálculo simultáneo de múltiples funciones óptimas multimodales.[11][12][13][14] El algoritmo comparte algunas características con algunos algoritmos más conocidos, como la optimización de colonia de hormigas y la optimización de enjambre de partículas , pero con varias diferencias significativas. Los agentes en la OSG son considerados como luciérnagas que llevan una cantidad de luminiscencia llamada luciferina junto con ellos. Los luciérnagas codifican la aptitud de sus ubicaciones actuales, evaluadas mediante la función objetivo, en un valor de luciferina que transmiten a sus vecinos. La luciérnaga identifica a sus vecinos y calcula sus movimientos mediante la explotación de un vecindario adaptable, que está limitado por su rango de sensores. Cada luciérnaga selecciona, usando un mecanismo probabilístico, un vecino que tiene un valor de luciferina más alto que el suyo y se mueve hacia él. Estos movimientos, basados únicamente en la información local y las interacciones vecinas selectivas, permiten que el enjambre de luciérnagas se divida en subgrupos disjuntos que convergen en óptimos múltiples de una función multimodal determinada. A diferencia de la mayoría de los otros algoritmos de optimización multimodales evolutivos, la propiedad de dividirse en subgrupos permite que el algoritmo converja simultáneamente a valores óptimos locales de diferentes valores, lo que lo hace adecuado para resolver problemas de búsqueda de fuentes de señales múltiples utilizando robots.[15]
Véase también
editar- Optimización de enjambre de luciérnagas
- Algoritmo de Firefly
Referencias
editar- ↑ Wong, K. C. (2015), Evolutionary Multimodal Optimization: A Short Survey arXiv preprint arXiv:1508.00457
- ↑ Shir, O.M. (2012), Niching in Evolutionary Algorithms Archivado el 4 de marzo de 2016 en Wayback Machine.
- ↑ Preuss, Mike (2015), Multimodal Optimization by Means of Evolutionary Algorithms
- ↑ Wong, K. C. et al. (2012), Evolutionary multimodal optimization using the principle of locality Information Sciences
- ↑ Mahfoud, S. W. (1995), "Niching methods for genetic algorithms"
- ↑ Shir, O.M. (2008), "Niching in Derandomized Evolution Strategies and its Applications in Quantum Control"
- ↑ Deb, K., Saha, A. (2010) "Finding Multiple Solutions for Multimodal Optimization Problems Using a Multi-Objective Evolutionary Approach" (GECCO 2010, In press)
- ↑ Saha, A., Deb, K. (2010) "A Bi-criterion Approach to Multimodal Optimization: Self-adaptive Approach " (Lecture Notes in Computer Science, 2010, Volume 6457/2010, 95–104)
- ↑ C. Stoean, M. Preuss, R. Stoean, D. Dumitrescu (2010) Multimodal Optimization by means of a Topological Species Conservation Algorithm. In IEEE Transactions on Evolutionary Computation, Vol. 14, Issue 6, pages 842–864, 2010.
- ↑ Ronkkonen,J., (2009). Continuous Multimodal Global Optimization with Differential Evolution Based Methods Archivado el 25 de diciembre de 2014 en Wayback Machine.
- ↑ K. N. Krishnanand and D. Ghose (2005). Detection of multiple source locations using a glowworm metaphor with applications to collective robotics. IEEE Swarm Intelligence Symposium, Pasadena, California, USA, pp. 84–91,
- ↑ K. N. Krishnanand and D. Ghose. Glowworm swarm optimization for simultaneous capture of multiple local optima of multimodal functions. Swarm Intelligence, Vol. 3, No. 2, pp. 87–124, June 2009.
- ↑ K. N. Krishnanand and D. Ghose. (2008). Theoretical foundations for rendezvous of glowworm-inspired agent swarms at multiple locations. Robotics and Autonomous Systems, 56(7): 549–569.
- ↑ K. N. Krishnanand and D. Ghose. (2006). Glowworm swarm based optimization algorithm for multimodal functions with collective robotics applications. Multi-agent and Grid Systems, 2(3): 209–222.
- ↑ K. McGill and S. Taylor, Robot algorithms for localization of multiple emission sources, ACM Computing Surveys, Vol. 43, Issue 3, April 2011, pp. 15:1 – 15:25
Datos: Q5418713
