Algoritmo evolutivo - Evolutionary algorithm
Parte de una serie sobre |
Inteligencia artificial |
---|
En inteligencia computacional (CI), un algoritmo evolutivo ( EA ) es un subconjunto del cálculo evolutivo , un algoritmo genérico de optimización metaheurística basado en la población . Un EA utiliza mecanismos inspirados en la evolución biológica , como la reproducción , la mutación , la recombinación y la selección . Las soluciones candidatas al problema de optimización juegan el papel de individuos en una población, y la función de aptitud determina la calidad de las soluciones (ver también función de pérdida ). La evolución de la población tiene lugar luego de la aplicación repetida de los operadores anteriores.
Los algoritmos evolutivos a menudo funcionan bien al aproximar soluciones a todo tipo de problemas porque, idealmente, no hacen ninguna suposición sobre el panorama de aptitud subyacente . Las técnicas de algoritmos evolutivos aplicados al modelado de la evolución biológica se limitan generalmente a la exploración de procesos microevolutivos y modelos de planificación basados en procesos celulares. En la mayoría de las aplicaciones reales de EA, la complejidad computacional es un factor prohibitivo. De hecho, esta complejidad computacional se debe a la evaluación de la función de aptitud. La aproximación al fitness es una de las soluciones para superar esta dificultad. Sin embargo, EA aparentemente simple puede resolver problemas a menudo complejos; por lo tanto, puede que no exista un vínculo directo entre la complejidad del algoritmo y la complejidad del problema.
Implementación
El siguiente es un ejemplo de un algoritmo genético genérico de objetivo único .
Paso uno: Genere la población inicial de individuos al azar. (Primera generación)
Paso dos: repita los siguientes pasos de regeneración hasta la terminación:
- Evaluar la aptitud de cada individuo de la población (límite de tiempo, aptitud suficiente alcanzada, etc.)
- Seleccione los individuos más aptos para la reproducción . (Padres)
- Críe nuevos individuos a través de operaciones de cruce y mutación para dar a luz a sus crías .
- Reemplazar a los individuos menos aptos de la población por nuevos individuos.
Tipos
Las técnicas similares difieren en la representación genética y otros detalles de implementación, y la naturaleza del problema aplicado particular.
- Algoritmo genético : este es el tipo de EA más popular. Se busca la solución de un problema en forma de cadenas de números (tradicionalmente binarios, aunque las mejores representaciones suelen ser las que reflejan algo sobre el problema que se está resolviendo), aplicando operadores como recombinación y mutación (a veces una, a veces ambas) . Este tipo de EA se utiliza a menudo en problemas de optimización .
- Programación genética : aquí las soluciones se encuentran en forma de programas de computadora, y su idoneidad está determinada por su capacidad para resolver un problema computacional. Hay muchas variantes de la programación genética, incluyendo la programación genética cartesiana , la programación de la expresión génica , la Gramática Evolución , la programación genética lineal , la expresión de múltiples programación , etc.
- Programación evolutiva : similar a la programación genética, pero la estructura del programa es fija y sus parámetros numéricos pueden evolucionar.
- Estrategia de evolución : funciona con vectores de números reales como representaciones de soluciones y, por lo general, utiliza tasas de mutación autoadaptativas.
- Evolución diferencial : se basa en diferencias vectoriales y, por lo tanto, se adapta principalmente a problemas de optimización numérica .
- Neuroevolución : similar a la programación genética, pero los genomas representan redes neuronales artificiales al describir la estructura y los pesos de conexión. La codificación del genoma puede ser directa o indirecta.
- Aprendizaje del sistema de clasificación : aquí la solución es un conjunto de clasificadores (reglas o condiciones). Un LCS de Michigan evoluciona a nivel de clasificadores individuales, mientras que un LCS de Pittsburgh usa poblaciones de conjuntos de clasificadores. Inicialmente, los clasificadores eran solo binarios, pero ahora incluyen tipos reales, de redes neuronales o de expresión S. La condición física se determina típicamente con un enfoque de aprendizaje reforzado o supervisado basado en la fuerza o la precisión .
Comparación con procesos biológicos
Una posible limitación de muchos algoritmos evolutivos es su falta de una clara distinción genotipo-fenotipo . En la naturaleza, el óvulo fertilizado se somete a un proceso complejo conocido como embriogénesis para convertirse en un fenotipo maduro . Se cree que esta codificación indirecta hace que la búsqueda genética sea más robusta (es decir, reduce la probabilidad de mutaciones fatales) y también puede mejorar la capacidad de evolución del organismo. Dichas codificaciones indirectas (también conocidas como generativas o de desarrollo) también permiten que la evolución aproveche la regularidad del entorno. El trabajo reciente en el campo de la embriogenia artificial , o sistemas de desarrollo artificiales, busca abordar estas preocupaciones. Y la programación de la expresión génica explora con éxito un sistema genotipo-fenotipo, donde el genotipo consiste en cromosomas multigénicos lineales de longitud fija y el fenotipo consiste en múltiples árboles de expresión o programas de computadora de diferentes tamaños y formas.
Técnicas relacionadas
Los algoritmos de enjambre incluyen
- La optimización de las colonias de hormigas se basa en las ideas de que las hormigas se alimentan mediante la comunicación de feromonas para formar caminos. Principalmente adecuado para optimización combinatoria y problemas de gráficos .
- El algoritmo de la raíz del corredor (RRA) está inspirado en la función de los corredores y las raíces de las plantas en la naturaleza.
- El algoritmo de colonias de abejas artificiales se basa en el comportamiento de búsqueda de alimento de las abejas melíferas. Principalmente propuesto para optimización numérica y extendido para resolver problemas de optimización combinatoria, restringida y multiobjetivo.
- El algoritmo de las abejas se basa en el comportamiento de búsqueda de alimento de las abejas melíferas. Se ha aplicado en muchas aplicaciones, como enrutamiento y programación.
- La búsqueda del cuco se inspira en el parasitismo inquietante de la especie de cuco . También utiliza vuelos Lévy , por lo que se adapta a los problemas de optimización global .
- La optimización del enjambre de partículas se basa en las ideas del comportamiento de las manadas de animales. También se adapta principalmente a problemas de optimización numérica .
Otros métodos metaheurísticos basados en la población
- Búsqueda de caza - Método inspirado en la caza grupal de algunos animales como los lobos que organizan su posición para rodear a la presa, cada una de ellas en relación con la posición de los demás y especialmente la de su líder. Es un método de optimización continua adaptado como método de optimización combinatoria.
- Búsqueda dimensional adaptativa : a diferencia de las técnicas metaheurísticas inspiradas en la naturaleza, un algoritmo de búsqueda dimensional adaptativa no implementa ninguna metáfora como principio subyacente. Por el contrario, utiliza un método simple orientado al rendimiento, basado en la actualización del parámetro de relación de dimensionalidad de búsqueda (SDR) en cada iteración.
- El algoritmo de luciérnagas se inspira en el comportamiento de las luciérnagas, que se atraen entre sí con la luz intermitente. Esto es especialmente útil para la optimización multimodal.
- Búsqueda de armonía : basada en las ideas del comportamiento de los músicos en la búsqueda de mejores armonías. Este algoritmo es adecuado para la optimización combinatoria y la optimización de parámetros.
- Adaptación gaussiana : basada en la teoría de la información. Se utiliza para maximizar el rendimiento de fabricación, la aptitud media o la información media . Véase, por ejemplo, Entropía en termodinámica y teoría de la información .
- Algoritmo memético : un método híbrido, inspirado en la noción de meme de Richard Dawkins , comúnmente toma la forma de un algoritmo basado en la población junto con procedimientos de aprendizaje individuales capaces de realizar refinamientos locales. Enfatiza la explotación del conocimiento específico del problema y trata de orquestar la búsqueda local y global de manera sinérgica.
Ejemplos de
En 2020, Google declaró que su AutoML-Zero puede redescubrir con éxito algoritmos clásicos como el concepto de redes neuronales.
Las simulaciones por computadora Tierra y Avida intentan modelar la dinámica macroevolutiva .
Galería
Una búsqueda de EA de dos poblaciones sobre una función de Rosenbrock restringida con un óptimo global acotado.
Una búsqueda de EA de dos poblaciones sobre una función de Rosenbrock restringida . El óptimo global no está limitado.
Una búsqueda de EA de dos poblaciones de un óptimo acotado de la función de Simionescu .
Referencias
enlaces externos
Bibliografía
- Ashlock, D. (2006), Computación evolutiva para modelado y optimización , Springer, ISBN 0-387-22196-4 .
- Bäck, T. (1996), Algoritmos evolutivos en teoría y práctica: Estrategias evolutivas, Programación evolutiva, Algoritmos genéticos , Universidad de Oxford. Presionar.
- Bäck, T., Fogel, D., Michalewicz, Z. (1997), Manual de Computación Evolutiva , Universidad de Oxford. Presionar.
- Banzhaf, W., Nordin, P., Keller, R., Francone, F. (1998), Programación genética - Introducción , Morgan Kaufmann, San Francisco
- Eiben, AE, Smith, JE (2003), Introducción a la Computación Evolutiva , Springer.
- Holland, JH (1992), Adaptación en sistemas naturales y artificiales , The University of Michigan Press, Ann Arbor
- Michalewicz Z., Fogel DB (2004). Cómo resolverlo: heurística moderna, Springer.
- Benko, Atila; Dosa, Gyorgy; Tuza, Zsolt (2010). "Bin Packing / Covering with Delivery, resuelto con la evolución de algoritmos". 2010 IEEE Quinta Conferencia Internacional sobre Computación Bioinspirada: Teorías y Aplicaciones (BIC-TA) . págs. 298-302. doi : 10.1109 / BICTA.2010.5645312 . ISBN 978-1-4244-6437-1. S2CID 16875144 .
- Poli, R .; Langdon, WB; McPhee, NF (2008). Una guía de campo para la programación genética . Lulu.com, disponible gratuitamente en Internet. ISBN 978-1-4092-0073-4. Archivado desde el original el 27 de mayo de 2016 . Consultado el 5 de marzo de 2011 .
- Price, K., Storn, RM, Lampinen, JA, (2005). "Evolución diferencial: un enfoque práctico para la optimización global" , Springer.
- Ingo Rechenberg (1971): Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (tesis doctoral). Reimpreso por Fromman-Holzboog (1973).
- Hans-Paul Schwefel (1974): Numerische Optimierung von Computer-Modellen (tesis doctoral). Reimpreso por Birkhäuser (1977).
- Simon, D. (2013): Algoritmos de optimización evolutiva , Wiley.
- Inteligencia computacional: una introducción metodológica de Kruse, Borgelt, Klawonn, Moewes, Steinbrecher, Held, 2013, Springer, ISBN 978-1-4471-5012-1
- Rahman, Rosshairy Abd .; Kendall, Graham; Ramli, Razamin; Jamari, Zainoddin; Ku-Mahamud, Ku Ruhana (2017). "Formulación de alimento para camarones mediante algoritmo evolutivo con heurística de potencia para el manejo de restricciones" . Complejidad . 2017 : 1–12. doi : 10.1155 / 2017/7053710 .