Algoritmo evolutivo

En inteligencia computacional (CI), un algoritmo evolutivo (EA) es un subconjunto de la computación evolutiva, 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 después de la aplicación repetida de los operadores anteriores.

Los algoritmos evolutivos a menudo funcionan bien aproximando soluciones a todo tipo de problemas porque idealmente no hacen ninguna suposición sobre el panorama de fitness subyacente. Las técnicas de algoritmos evolutivos aplicadas al modelado de la evolución biológica generalmente se limitan a exploraciones de procesos microevolutivos y modelos de planificación basados en procesos celulares. En la mayoría de las aplicaciones reales de los 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 de 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 haya 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 un solo objetivo.

Paso uno: Genere la población inicial de individuos al azar. (Primera generación)

Paso dos: repita los siguientes pasos regenerativos hasta la finalización:

1. Evaluar la aptitud de cada individuo en la población (límite de tiempo, aptitud suficiente alcanzada, etc.)
2. Seleccione los individuos más adecuados para la reproducción. (Padres)
3. Abrió a nuevos individuos a través de operaciones de cruce y mutación para dar a luz a la descendencia.
4. Reemplazar a los individuos menos aptos de la población con nuevos individuos.

Tipos

Técnicas similares difieren en la representación genética y otros detalles de implementación, y la naturaleza del problema particular aplicado.

• algoritmo genético – Este es el tipo más popular de EA. Uno busca la solución de un problema en forma de cadenas de números (tradicionalmente binario, aunque las mejores representaciones son generalmente las que reflejan algo sobre el problema que se está resolviendo), 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 informáticos, y su aptitud se determina por su capacidad de resolver un problema computacional. Hay muchas variantes de Programación Genética, incluyendo programación genética cartesiana, programación de expresión genética, evolución gramática, programación genética lineal, programación multiexpresiva, etc.
• Programación evolutiva – Similar a la programación genética, pero la estructura del programa se fija y sus parámetros numéricos se permiten evolucionar.
• Estrategia de Evolución – Trabaja con vectores de números reales como representaciones de soluciones, y normalmente utiliza tasas de mutación auto-adaptivas. El método se utiliza principalmente para la optimización numérica, aunque también hay variantes para tareas combinatorias.
• Evolución diferencial – Basada en diferencias vectoriales y, por lo tanto, se adapta principalmente a problemas numéricos de optimización.
• Neuroevolución – Similar a la programación genética pero los genomas representan redes neuronales artificiales describiendo la estructura y los pesos de conexión. La codificación del genoma puede ser directa o indirecta.
• Sistema de clasificación de aprendizaje – Aquí la solución es un conjunto de clasificadores (reglas o condiciones). Un Michigan-LCS evoluciona a nivel de clasificadores individuales mientras que un Pittsburgh-LCS utiliza poblaciones de conjuntos clasificatorios. Inicialmente, los clasificadores sólo eran binarios, pero ahora incluyen los tipos reales de redes neuronales o S-expresión. La aptitud se determina normalmente con un aprendizaje basado en fuerza o precisión o un enfoque de aprendizaje supervisado.

Antecedentes teóricos

Los siguientes principios teóricos se aplican a todos o casi todos los EA.

No hay teorema de almuerzo gratis

El teorema de optimización sin almuerzo gratis establece que todas las estrategias de optimización son igualmente efectivas cuando se considera el conjunto de todos los problemas de optimización. Bajo la misma condición, ningún algoritmo evolutivo es fundamentalmente mejor que otro. Esto sólo puede ser el caso si se restringe el conjunto de todos los problemas. Esto es exactamente lo que inevitablemente se hace en la práctica. Por lo tanto, para mejorar un EA, debe explotar el conocimiento del problema de alguna forma (por ejemplo, eligiendo una cierta fuerza de mutación o una codificación adaptada al problema). Por lo tanto, si se comparan dos EA, esta restricción está implícita. Además, un EA puede utilizar el conocimiento específico del problema, por ejemplo, no generando aleatoriamente la población inicial completa, sino creando algunos individuos a través de heurísticas u otros procedimientos. Otra posibilidad de adaptar un AE a un dominio de problema dado es involucrar heurísticas adecuadas, procedimientos de búsqueda local u otros procedimientos relacionados con el problema en el proceso de generación de la descendencia. Esta forma de extensión de un EA también se conoce como algoritmo memético. Ambas extensiones juegan un papel importante en las aplicaciones prácticas, ya que pueden acelerar el proceso de búsqueda y hacerlo más sólido.

Convergencia

Para las AE en las que, además de la descendencia, al menos el mejor individuo de la generación principal se utiliza para formar la generación siguiente (las denominadas AE elitistas), existe una prueba general de convergencia bajo la condición de que una óptimo existe. Sin pérdida de generalidad, se supone una búsqueda máxima para la prueba:

De la propiedad de la aceptación de la descendencia elitista y la existencia del óptimo sigue que por generación k{displaystyle k} una mejora de la aptitud F{displaystyle F} de la mejor persona x.{displaystyle x'} ocurrirá con una probabilidad 0}" xmlns="http://www.w3.org/1998/Math/MathML">P■0{displaystyle P título0}0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bd713165b8911d1e29aabe51e8ed093fa4b349ae" style="vertical-align: -0.338ex; width:6.006ex; height:2.176ex;"/>. Así:

F()x1.)≤ ≤ F()x2.)≤ ≤ F()x3.)≤ ≤ ⋯ ⋯ ≤ ≤ F()xk.)≤ ≤ ⋯ ⋯ {displaystyle F(x'_{1})leq F(x'_{2})leq F(x'_{3})leq cdots leq F(x'_{k})leq cdots }

Es decir, los valores de aptitud representan una secuencia monótonamente no decreciente, que está limitada debido a la existencia del óptimo. De aquí se sigue la convergencia de la sucesión contra el óptimo.

Dado que la prueba no hace ninguna afirmación sobre la velocidad de convergencia, es de poca ayuda en las aplicaciones prácticas de los EA. Pero sí justifica la recomendación de utilizar EA elitistas. Sin embargo, cuando se utiliza el modelo de población panmíctica habitual, las AE elitistas tienden a converger prematuramente más que las no elitistas. En un modelo de población panmíctica, la selección de pareja (paso 2 de la sección sobre implementación) es tal que cada individuo en toda la población es elegible como pareja. En poblaciones no panmícticas, la selección está convenientemente restringida, por lo que la velocidad de dispersión de mejores individuos se reduce en comparación con los panmícticos. Por lo tanto, el riesgo general de convergencia prematura de EA elitistas puede reducirse significativamente mediante modelos de población adecuados que restrinjan la selección de pareja.

Alfabetos virtuales

Con la teoría de los alfabetos virtuales, David E. Goldberg demostró en 1990 que al usar una representación con números reales, un EA que usa operadores de recombinación clásica (por ejemplo, uniforme o cruce de n puntos) no puede llegar a ciertas áreas del espacio de búsqueda., en contraste con una codificación con números binarios. Esto da como resultado la recomendación de que los EA con representación real utilicen operadores aritméticos para la recombinación (por ejemplo, media aritmética o recombinación intermedia). Con operadores adecuados, las representaciones de valores reales son más efectivas que las binarias, contrariamente a la opinión anterior.

Comparación con procesos biológicos

Una posible limitación de muchos algoritmos evolutivos es la falta de una distinción clara entre genotipo y fenotipo. En la naturaleza, el óvulo fertilizado pasa por 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. Tales codificaciones indirectas (también conocidas como generativas o de desarrollo) también permiten que la evolución explote la regularidad en el entorno. El trabajo reciente en el campo de la embriogenia artificial, o sistemas de desarrollo artificial, busca abordar estas preocupaciones. Y la programación de la expresión génica explora con éxito un sistema genotipo-fenotipo, donde el genotipo consta de cromosomas multigénicos lineales de longitud fija y el fenotipo consta de múltiples árboles de expresión o programas informáticos de diferentes tamaños y formas.

Aplicaciones

Las áreas en las que se utilizan prácticamente los algoritmos evolutivos son casi ilimitadas y van desde la industria, la ingeniería, la programación compleja, la agricultura, la planificación del movimiento de robots y las finanzas hasta la investigación y el arte. La aplicación de un algoritmo evolutivo requiere un replanteamiento por parte del usuario inexperto, ya que el enfoque de una tarea que utiliza un EA es diferente de los métodos exactos convencionales y, por lo general, esto no forma parte del plan de estudios de los ingenieros u otras disciplinas. Por ejemplo, el cálculo de la aptitud no solo debe formular el objetivo, sino también apoyar el proceso de búsqueda evolutiva hacia él, p. premiando las mejoras que aún no conducen a una mejor evaluación de los criterios de calidad originales. Por ejemplo, si en una tarea de programación se debe evitar la utilización máxima de recursos, como el despliegue de personal o el consumo de energía, no basta con evaluar la utilización máxima. Más bien, el número y la duración de las superaciones de un nivel aún aceptable también deben registrarse para recompensar las reducciones por debajo del valor pico máximo real. Por lo tanto, existen algunas publicaciones que están dirigidas al principiante y quieren ayudar a evitar los errores del principiante, así como a llevar un proyecto de aplicación al éxito. Esto incluye aclarar la cuestión fundamental de cuándo se debe usar un EA para resolver un problema y cuándo es mejor no hacerlo.

Técnicas relacionadas

Los algoritmos de enjambre incluyen:

• La optimización de la colonia de hormigas se basa en las ideas de forraje de hormiga por comunicación de feromonas para formar caminos. Principalmente adecuado para la optimización combinatoria y problemas gráficos.
• El algoritmo raíz de corredor (RRA) se inspira en la función de corredores y raíces de plantas en la naturaleza.
• El algoritmo de colonia de abejas artificiales se basa en el comportamiento de forraje de abeja. Propuesta principalmente para la optimización numérica y extendida para resolver problemas de optimización combinatoria, limitada y multiobjetiva.
• El algoritmo de abejas se basa en el comportamiento del forraje de las abejas. Se ha aplicado en muchas aplicaciones, como el enrutamiento y la programación.
• La búsqueda de cuco está inspirada en el parasitismo de la especie de cuco. También utiliza vuelos Lévy, por lo que se adapta a problemas de optimización global.
• La optimización enjambre de partículas se basa en las ideas de comportamiento animal. 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 – Un método inspirado por la caza de algunos animales como lobos que organizan su posición para rodear la presa, cada uno de ellos en relación con la posición de los otros y especialmente la de su líder. Es un método de optimización continua adaptado como un método de optimización combinatorial.
• Búsqueda dimensional adaptativa – A diferencia de las técnicas metaheurísticas inspiradas por la naturaleza, un algoritmo de búsqueda dimensional adaptativo no implementa ninguna metáfora como principio subyacente. Más bien utiliza un método simple orientado al rendimiento, basado en la actualización del parámetro de relación de dimensión de búsqueda (SDR) en cada iteración.
• El algoritmo de la luciérnaga se inspira en el comportamiento de las luciérnagas, atrayendo el uno al otro por la luz que parpadea. Esto es especialmente útil para la optimización multimodal.
• Búsqueda de armonía – Basado 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 combinatorial y la optimización de parámetros.
• Adaptación gausiana – Basada en la teoría de la información. Utilizado para maximizar el rendimiento de fabricación, significa fitness o información media. Vea por ejemplo Entropy en termodinámica y teoría de la información.
• algoritmo memético – Un método híbrido, inspirado en la noción de Richard Dawkins de un meme, toma comúnmente la forma de un algoritmo basado en la población junto con procedimientos de aprendizaje individuales capaces de realizar refinaciones locales. Pone de relieve la explotación de conocimientos específicos para problemas y trata de orquestar la búsqueda local y mundial de manera sinérgica.

Ejemplos

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

Las simulaciones por ordenador Tierra y Avida intentan modelar dinámicas macroevolutivas.

Galería

• 

  Una búsqueda de dos populación EA sobre una función de Rosenbrock limitada con un óptimo global consolidado

• 

  Una búsqueda de dos populación EA sobre una función de Rosenbrock limitada. El óptimo global no está ligado.

• 

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

• 

  Una búsqueda de dos populaciones de una optima atada de la función de Simionescu