Algoritmo evolutivo

Parte de una serie sobre el
Algoritmo evolutivo
Desarrollo artificial Vida artificial Algoritmo evolutivo celular Algoritmo cultural Evolución diferencial Fitness efectivo Computación evolutiva Estrategia de evolución Adaptación gaussiana Optimización multimodal evolutiva Evolución gramatical Optimización de Enjambre de partículas Algoritmo memético Estrategia de evolución natural Neuroevolución Algoritmo genético basado en promotores Algoritmo de optimización en espiral Código auto modificable Código polimórfico
Algoritmo genético
Cromosoma Algoritmo de selección clonal Transversal Mutación Memoria genética Sistemas genéticos difusos Selección Algoritmo de vuelo
Programación genética
Programación genética cartesiana Programación genética lineal Programación de expresiones múltiples Esquema Eurisko Punto de referencia de paridad
v t mi

Parte de una serie sobre
Inteligencia artificial
Grandes metas Inteligencia artificial general Planificación Visión por computador Juego general Razonamiento del conocimiento Aprendizaje automático Procesamiento natural del lenguaje Robótica
Enfoques Simbólico Aprendizaje profundo Redes bayesianas Algoritmos evolutivos
Filosofía Ética Riesgo existencial prueba de Turing Cuarto chino Problema de control IA amigable
Historia Cronología Progreso AI invierno
Tecnología Aplicaciones Proyectos Lenguajes de programación
Glosario Glosario
v t mi

En inteligencia computacional (CI), un algoritmo evolutivo ( EA ) es un subconjunto del cálculo evolutivo , ^[1] 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 desempeñan el papel de los 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. ^[2] 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; ^{[ cita requerida]} 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:

1. Evaluar la aptitud de cada individuo de la población (límite de tiempo, aptitud suficiente alcanzada, etc.)
2. Seleccione los individuos más aptos para la reproducción . (Padres)
3. Críe nuevos individuos a través de operaciones de cruce y mutación para dar a luz a sus crías .
4. 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), ^[2] aplicando operadores como recombinación y mutación (a veces uno, a veces ambos). Este tipo de EA se utiliza a menudo en problemas de optimización .
• Programación genética : aquí las soluciones están en forma de programas de computadora, y su idoneidad está determinada por su capacidad para resolver un problema computacional.
• 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.
• Programación de expresión génica : al igual que la programación genética, GEP también desarrolla programas de computadora, pero explora un sistema genotipo-fenotipo, donde los programas de computadora de diferentes tamaños se codifican en cromosomas lineales de longitud fija.
• 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 los procesos biológicos

Una posible limitación ^{[¿ según quié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. ^{[3] [4]} Estas codificaciones indirectas (también conocidas como generativas o de desarrollo) también permiten que la evolución aproveche la regularidad del entorno. ^[5] Trabajos recientes en el campo deembriogenia artificial , o sistemas de desarrollo artificial, busca abordar estas preocupaciones. Y la programación de 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. ^{[6] [ síntesis incorrecta? ]}

Técnicas relacionadas

Los algoritmos de enjambre ^{[ aclaración necesaria ]} 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) se inspira en la función de los corredores y las raíces de las plantas en la naturaleza ^[7]
• 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 de Electimize se basa en el comportamiento del flujo de electrones a través de las ramas del circuito eléctrico con la menor resistencia eléctrica. ^[8]
• 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 ^[9] adaptado como método de optimización combinatoria. ^[10]
• 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 sencillo orientado al rendimiento, basado en la actualización del parámetro de relación de dimensionalidad de búsqueda (SDR) en cada iteración. ^[11]
• 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 : se basa 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

En 2020, Google declaró que su AutoML-Zero puede redescubrir con éxito algoritmos clásicos como el concepto de redes neuronales. ^[12]

Las simulaciones por computadora Tierra y Avida intentan modelar la dinámica macroevolutiva .

Galería

^{[13] [14] [15]}

• 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.

• Estimación del algoritmo de distribución sobre la función de Keane

• Una búsqueda de EA de dos poblaciones de un óptimo acotado de la función de Simionescu .

Referencias

1. Vikhar, PA (2016). "Algoritmos evolutivos: una revisión crítica y sus perspectivas de futuro". Actas de la Conferencia Internacional de 2016 sobre Tendencias Globales en Procesamiento de Señales, Computación de la Información y Comunicación (ICGTSPICC) . Jalgaon: 261-265. doi : 10.1109 / ICGTSPICC.2016.7955308 . ISBN 978-1-5090-0467-6. S2CID  22100336 .
2. Cohoon, J; et al. (26 de noviembre de 2002). Algoritmos evolutivos para el diseño físico de circuitos VLSI (PDF) . Avances en Computación Evolutiva: Teoría y Aplicaciones . Springer, págs. 683-712, 2003. ISBN  978-3-540-43330-9.
3. GS Hornby y JB Pollack. "Creación de componentes de alto nivel con representación generativa para la evolución cuerpo-cerebro". Vida artificial , 8 (3): 223–246, 2002.
4. Jeff Clune, Benjamin Beckmann, Charles Ofria y Robert Pennock. "Evolución de la marcha cuadrúpeda coordinada con la codificación generativa HyperNEAT" Archivado el 3 de junio de 2016 en la Wayback Machine . Actas del Congreso IEEE sobre Computación Evolutiva Sección Especial sobre Robótica Evolutiva , 2009. Trondheim, Noruega.
5. J. Clune, C. Ofria y RT Pennock, "How a generative encoding fares as problem-regularity disminuye" , en PPSN (G. Rudolph, T. Jansen, SM Lucas, C. Poloni y N. Beume, eds .), vol. 5199 de Lecture Notes in Computer Science , págs. 358–367, Springer, 2008.
6. Ferreira, C., 2001. "Programación de expresión genética: un nuevo algoritmo adaptativo para resolver problemas" . Sistemas complejos , vol. 13, número 2: 87-129.
7. F. Merrikh-Bayat, "El algoritmo de la raíz del corredor: una metaheurística para resolver problemas de optimización unimodal y multimodal inspirada en los corredores y las raíces de las plantas en la naturaleza", Applied Soft Computing , vol. 33, págs. 292–303, 2015
8. Khalafallah Ahmed; Abdel-Raheem Mohamed (1 de mayo de 2011). "Electimize: Nuevo Algoritmo Evolutivo de Optimización con Aplicación en Ingeniería de la Construcción". Revista de Informática en Ingeniería Civil . 25 (3): 192-201. doi : 10.1061 / (ASCE) CP.1943-5487.0000080 .
9. Oftadeh, R .; Mahjoob, MJ; Shariatpanahi, M. (octubre de 2010). "Un novedoso algoritmo de optimización meta-heurística inspirado en la caza grupal de animales: búsqueda de caza". Computadoras y Matemáticas con Aplicaciones . 60 (7): 2087–2098. doi : 10.1016 / j.camwa.2010.07.049 .
10. Amine Agharghor; Mohammed Essaid Riffi (2017). "Primera adaptación del algoritmo de búsqueda de caza para el problema de asignación cuadrática". Avances en la cooperación entre Europa y MENA en tecnologías de la información y la comunicación . Avances en Computación y Sistemas Inteligentes. 520 : 263-267. doi : 10.1007 / 978-3-319-46568-5_27 . ISBN 978-3-319-46567-8.
11. Hasançebi, O., Kazemzadeh Azad, S. (2015), "Búsqueda dimensional adaptable: un nuevo algoritmo metaheurístico para la optimización de tamaño de celosía discreta", Computadoras y estructuras , 154, 1-16.
12. Gent, Edd (13 de abril de 2020). "La inteligencia artificial está evolucionando por sí sola" . Ciencia | AAAS . Archivado desde el original el 16 de abril de 2020 . Consultado el 16 de abril de 2020 .
13. Simionescu, PA; Beale, DG; Dozier, GV (2004). "Resolución de problemas de optimización restringida mediante la estimación de algoritmos de distribución" (PDF) . Proc. del Congreso 2004 sobre Computación Evolutiva - CEC2004. Portland, OR: 1647–1653. doi : 10.1109 / CEC.2006.1688506 . S2CID 1717817 . Consultado el 7 de enero de 2017 .  
14. Simionescu, PA; Dozier, GV; Wainwright, RL (2006). "Un algoritmo evolutivo de dos poblaciones para problemas de optimización restringida" (PDF) . 2006 Conferencia Internacional IEEE sobre Computación Evolutiva . Proc 2006 IEEE International Conference on Evolutionary Computation. Vancouver, Canada. págs. 1647-1653. doi : 10.1109 / CEC.2006.1688506 . ISBN  0-7803-9487-9. S2CID  1717817 . Consultado el 7 de enero de 2017 .
15. Simionescu, PA (2014). Herramientas de simulación y gráficos asistidos por computadora para usuarios de AutoCAD (1ª ed.). Boca Raton, FL: CRC Press . ISBN 978-1-4822-5290-3.

Enlaces externos

• Una descripción general de la historia y los gustos de los algoritmos evolutivos

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. Prensa.
• Bäck, T., Fogel, D., Michalewicz, Z. (1997), Manual de Computación Evolutiva , Universidad de Oxford. Prensa.
• 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 .^{[ fuente autoeditada ]}
• 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 .