Optimización multimodal evolutiva

En matemáticas aplicadas , la optimización multimodal se ocupa de tareas de optimización que implican encontrar todas o la mayoría de las múltiples (al menos localmente óptimas) soluciones de un problema, en contraposición a la mejor solución única. 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, [1] en la que el capítulo de Shir [2] y el libro de Preuss [3] cubren el tema con más detalle.

El 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), es posible que no siempre se puedan obtener los mejores resultados. En tal escenario, si se conocen múltiples soluciones (local y / o globalmente óptimas), la implementación puede cambiarse rápidamente a otra solución y aún así obtener el mejor rendimiento posible del sistema. También se podrían analizar múltiples soluciones para descubrir propiedades ocultas (o relaciones) del problema de optimización subyacente, lo que las hace importantes para obtener conocimiento del dominio . Además, los algoritmos para la optimización multimodal generalmente no solo localizan múltiples óptimos en una sola ejecución, sino que también preservan su diversidad de 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 la diversidad para otros problemas. [4]

Las 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 embargo, sin 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 posibles soluciones, que se procesan en cada generación, y si las múltiples soluciones pueden conservarse durante todas estas generaciones, entonces, al finalizar el algoritmo, tendremos múltiples buenas soluciones, 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 hacia la mejor solución, o una solución subóptima (en una función resistente y de "mal comportamiento"). Encontrar y mantener múltiples soluciones 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 la solución posiblemente alrededor de 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 hecho intentos para resolver la optimización multimodal en todos estos ámbitos y la mayoría, si no todos los métodos, implementan niching de una forma u otra.

El método de agrupamiento de De Jong, el enfoque de función de compartir de Goldberg, el método de limpieza de Petrowski, el apareamiento restringido, el mantenimiento de múltiples subpoblaciones son algunos de los enfoques populares que han sido propuestos por la comunidad. Los dos primeros métodos están especialmente bien estudiados, sin embargo, no realizan una separación explícita en soluciones pertenecientes 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 marco niching que utiliza ES desaleatorizado, [6] proponiendo el CMA-ES como un optimizador niching por primera vez . El sustento de ese marco fue la selección de un individuo pico 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 un macho alfa ganando todas las competencias impuestas y dominando a partir de entonces su nicho ecológico , que luego obtiene todos los recursos sexuales en él para generar su descendencia.

Recientemente, se propuso un enfoque de optimización evolutiva multiobjetivo (EMO), [7] en el que se agrega un segundo objetivo adecuado al problema de optimización multimodal de objetivo único originalmente, de modo que las soluciones múltiples forman un frente pareto-óptimo débil . Por lo tanto, el problema de optimización multimodal puede resolverse por sus múltiples soluciones utilizando un algoritmo EMO. Mejorando su trabajo, [8] los mismos autores han hecho que su algoritmo sea autoadaptable, eliminando así la necesidad de pre-especificar los parámetros.

En [9] 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]

"> File:GA-Multi-modal.ogvReproducir medios
Encontrar múltiples óptimos utilizando algoritmos genéticos en una tarea de optimización multimodal. (El algoritmo demostrado en esta demostración es el propuesto por Deb, Saha en el enfoque multiobjetivo para la optimización multimodal).

  1. ^ Wong, KC (2015), Optimización multimodal evolutiva: una breve encuesta preprint arXiv arXiv: 1508.00457
  2. ^ Shir, OM (2012), Niching en algoritmos evolutivos Archivado el 4 de marzo de 2016 en la Wayback Machine.
  3. ^ Preuss, Mike (2015), Optimización multimodal por medio de algoritmos evolutivos
  4. ^ Wong, KC y col. (2012), Optimización multimodal evolutiva utilizando el principio de las Ciencias de la Información de la localidad.
  5. ^ Mahfoud, SW (1995), " Métodos de Niching para algoritmos genéticos "
  6. ^ Shir, OM (2008), " Niching en estrategias de evolución desaleatorizadas y sus aplicaciones en el control cuántico "
  7. ^ Deb, K., Saha, A. (2010) " Encontrar múltiples soluciones para problemas de optimización multimodal utilizando un enfoque evolutivo multiobjetivo " (GECCO 2010, en prensa)
  8. ^ Saha, A., Deb, K. (2010) "Un enfoque de dos criterios para la optimización multimodal: enfoque autoadaptativo" (Lecture Notes in Computer Science, 2010, Volumen 6457/2010, 95-104)
  9. ^ C. Stoean, M. Preuss, R. Stoean, D. Dumitrescu (2010) Optimización multimodal mediante un algoritmo de conservación de especies topológicas . En IEEE Transactions on Evolutionary Computation, vol. 14, Número 6, páginas 842–864, 2010.

  • D. Goldberg y J. Richardson. (1987) " Algoritmos genéticos con compartición para la optimización de funciones multimodales ". En Actas de la Segunda Conferencia Internacional sobre Algoritmos Genéticos sobre Algoritmos Genéticos y su índice de aplicación, páginas 41–49. L. Erlbaum Associates Inc. Hillsdale, Nueva Jersey, EE. UU., 1987.
  • A. Petrowski. (1996) " Un procedimiento de compensación como método de niching para algoritmos genéticos ". En Actas de la Conferencia Internacional IEEE de 1996 sobre Computación Evolutiva, páginas 798–803. Citeseer, 1996.
  • Deb, K., (2001) "Optimización multiobjetivo mediante algoritmos evolutivos", Wiley ( Google Books)
  • F. Streichert, G. Stein, H. Ulmer y A. Zell. (2004) " Un EA niching basado en clústeres para espacios de búsqueda multimodal ". Lecture Notes in Computer Science, páginas 293–304, 2004.
  • Singh, G., Deb, K., (2006) " Comparación de algoritmos de optimización multimodales basados ​​en algoritmos evolutivos ". En Actas de la octava conferencia anual sobre computación genética y evolutiva, páginas 8-12. ACM, 2006.
  • Ronkkonen, J., (2009). Optimización global multimodal continua con métodos basados ​​en la evolución diferencial
  • Wong, KC, (2009). Un algoritmo evolutivo con explosión específica de especies para optimización multimodal. GECCO 2009: 923–930
  • J. Barrera y CAC Coello. " Una revisión de los métodos de optimización de enjambres de partículas utilizados para la optimización multimodal ", páginas 9–37. Springer, Berlín, noviembre de 2009.
  • Wong, KC, (2010). Efecto de la localidad espacial en un algoritmo evolutivo para la optimización multimodal. EvoApplications (1) 2010: 481–490
  • Deb, K., Saha, A. (2010) Encontrar múltiples soluciones para problemas de optimización multimodal utilizando un enfoque evolutivo multiobjetivo. GECCO 2010: 447–454
  • Wong, KC, (2010). Predicción de la estructura de proteínas en un modelo de celosía mediante técnicas de optimización multimodal. GECCO 2010: 155–162
  • Saha, A., Deb, K. (2010), A Bi-Criter Approach to Multimodal Optimization: Self-Adaptive Approach. SELLO 2010: 95–104
  • Shir, OM, Emmerich, M., Bäck, T. (2010), Enfoques adaptativos de radios de nicho y formas de nicho para Niching con el CMA-ES. Computación evolutiva Vol. 18, núm. 1, págs. 97-126.
  • C. Stoean, M. Preuss, R. Stoean, D. Dumitrescu (2010) Optimización multimodal mediante un algoritmo de conservación de especies topológicas . En IEEE Transactions on Evolutionary Computation, vol. 14, Número 6, páginas 842–864, 2010.
  • S. Das, S. Maity, BY Qu, PN Suganthan, " Optimización multimodal evolutiva de parámetros reales: un estudio del estado de la técnica ", vol. 1, núm. 2, págs. 71–88, Swarm and Evolutionary Computation, junio de 2011.

  • Optimización multimodal mediante la optimización del enjambre de partículas (PSO)
  • Niching en estrategias de evolución (ES)
  • Página de optimización multimodal en la Cátedra 11, Ciencias de la Computación, Universidad TU Dortmund
  • Grupo de trabajo IEEE CIS sobre optimización multimodal