Computación evolutiva
Algoritmos genéticos, neuroevolución, CMA-ES
Sin gradientes y sin entender el problema: variar, seleccionar, repetir. La evolución es un algoritmo de búsqueda que produjo ojos, alas y cerebros.
Intuición
Un algoritmo genético mantiene una población de soluciones candidatas codificadas como «genomas». Las mejores (según una función de aptitud) se reproducen con cruce —mezclando genomas— y mutación —cambios aleatorios—. Generación tras generación, la población trepa el paisaje de aptitud.
La neuroevolución evoluciona redes neuronales: sus pesos o incluso su estructura. NEAT (Stanley y Miikkulainen, 2002) empieza con redes mínimas y añade neuronas y conexiones, protegiendo las innovaciones con especiación.
Las estrategias evolutivas tratan el problema como optimización continua. CMA-ES (Hansen y Ostermeier, 2001) muestrea de una gaussiana y adapta su media y su matriz de covarianza hacia las direcciones exitosas: la elipse aprende la forma del valle.
Mecanismo
Ciclo: evaluar aptitud → seleccionar (torneo, ruleta, elitismo) → cruzar → mutar. El teorema de los esquemas de Holland (1975) sugiere que los bloques cortos y con buena aptitud se propagan exponencialmente.
CMA-ES: en cada generación muestrea puntos , ordena por aptitud, mueve la media hacia el promedio ponderado de los mejores y actualiza con la información de rango 1 (camino evolutivo) y rango . Es invariante a transformaciones lineales del espacio: el problema mal condicionado se vuelve fácil.
Ventajas: no requiere derivadas, tolera ruido y funciones discontinuas, se paraleliza de forma trivial. Salimans et al. (2017) mostraron que las estrategias evolutivas compiten con RL en control continuo usando miles de CPU.
Laboratorio
Algoritmo genético: cohetes que aprenden a llegar
Cada cohete tiene un genoma de impulsos. Mueve la meta y los obstáculos; la población evoluciona con selección, cruce y mutación.
CMA-ES sobre un paisaje de aptitud
La elipse de la distribución se estira hacia el valle. Compara Rosenbrock, Rastrigin y un paisaje multimodal; haz clic para reiniciar desde otro punto.
NEAT: topología que evoluciona
Una población de redes crece neuronas y conexiones mientras resuelve un XOR visual. Especiación protege las innovaciones; el genoma se dibuja en vivo.
Historia
- 1966
L. J. Fogel, Owens y Walsh proponen la programación evolutiva.
Fogel, Owens & Walsh (1966), Artificial Intelligence through Simulated Evolution
- 1973
Rechenberg publica las estrategias evolutivas (Berlín).
Rechenberg (1973), Evolutionsstrategie
- 1975
Holland publica Adaptation in Natural and Artificial Systems.
Holland (1975), University of Michigan Press
- 1992
Koza sistematiza la programación genética: evolucionar programas.
Koza (1992), Genetic Programming, MIT Press
- 1994
Karl Sims evoluciona criaturas virtuales con cuerpo y cerebro.
Sims (1994), SIGGRAPH
- 2001
Hansen y Ostermeier publican la forma completa de CMA-ES.
Hansen & Ostermeier (2001), Evolutionary Computation 9(2)
- 2002
NEAT evoluciona topologías de redes neuronales.
Stanley & Miikkulainen (2002), Evolutionary Computation 10(2)
- 2019
La evolución regularizada encuentra arquitecturas de visión competitivas (AmoebaNet).
Real et al. (2019), AAAI
Límites
Costosa en evaluaciones: cada individuo requiere medir su aptitud.
En espacios de muy alta dimensión, el gradiente suele ganar por mucho.
Sensible a la codificación del genoma y al diseño de la aptitud.
¿Puede haber diseño sin diseñador?
Darwin disolvió el argumento del diseño de Paley: la selección acumulativa produce la apariencia de propósito. Dennett llamó a la evolución «un algoritmo»: un proceso mecánico, sin mente, que sin embargo encuentra soluciones ingeniosas.
Si la inteligencia humana surgió de un proceso ciego, ¿es la evolución artificial el camino más honesto hacia la IA, o solo el más lento?