Algoritmos genéticos

La idea

Un algoritmo genético optimiza imitando la evolución biológica. En vez de un único punto que se mueve, mantiene una población de soluciones candidatas (los individuos, codificados como vectores de números o cadenas de bits) y la hace evolucionar generación tras generación. La calidad de cada individuo la mide una función de aptitud, que es simplemente la función objetivo del problema.

Cada generación aplica tres operadores. La selección elige a los progenitores favoreciendo a los mejores, por torneo (se sortean k individuos y gana el más apto) o por ruleta (probabilidad proporcional a la aptitud). El cruce combina dos progenitores para crear descendencia: en codificación binaria se parte la cadena en un punto y se intercambian los trozos; en codificación real se toma una combinación convexa de los padres. La mutación altera al azar una pequeña parte de cada hijo, lo que mantiene la diversidad y evita que la población se estanque. Muchas implementaciones añaden elitismo: copiar sin cambios a los mejores individuos para no perder nunca la mejor solución encontrada.

El equilibrio entre exploración (mutación alta, población grande y diversa) y explotación (presión selectiva fuerte) es delicado: demasiada presión provoca convergencia prematura, con toda la población clonada alrededor de un mínimo local; demasiada mutación convierte el método en una búsqueda aleatoria. No hay garantías teóricas de encontrar el óptimo, y el teorema de «no hay comida gratis» recuerda que ninguna metaheurística es mejor que otra en todos los problemas. Su valor está en la flexibilidad: solo hacen falta una codificación y una función de aptitud, sin derivadas ni continuidad, y las evaluaciones se paralelizan sin esfuerzo.

Fórmulas clave

• Aptitudaptitud(individuo) = f(x) (a maximizar)
• Selección por ruletaP(i) = aptitud(i) / Σⱼ aptitud(j)
• Cruce de un punto (binario)padres 1101|011 y 0010|110 → 1101110 y 0010011
• Cruce aritmético (real)hijo = λ padre₁ + (1 − λ) padre₂, λ ∈ [0, 1]
• Mutación gaussianax' = x + σ · N(0, 1)
• Elitismolos e mejores pasan intactos a la generación siguiente

Dónde se aplica

La NASA diseñó con algoritmos evolutivos la antena de la misión ST5, con una forma retorcida que ningún ingeniero habría dibujado y un rendimiento mejor que la versión convencional. En ingeniería mecánica se optimizan perfiles de álabes de turbina y estructuras aligeradas; en finanzas se calibran reglas de inversión; y en aprendizaje automático se usan para buscar hiperparámetros y arquitecturas de redes neuronales (neuroevolución). También aparecen en planificación de horarios escolares y de producción, donde la codificación como permutación es natural y las restricciones son difíciles de derivar.

Con programación (Python)

import math, random

# Maximizar f(x) = x * sen(x) en [0, 10]
def f(x):
    return x * math.sin(x)

random.seed(3)
N, generaciones, sigma = 30, 40, 0.6
pob = [random.uniform(0, 10) for _ in range(N)]
for g in range(generaciones):
    pob.sort(key=f, reverse=True)
    elite = pob[: N // 3]
    hijos = []
    while len(hijos) < N - len(elite):
        p1, p2 = random.choice(elite), random.choice(elite)
        lam = random.random()
        h = lam * p1 + (1 - lam) * p2 + random.gauss(0, sigma)
        hijos.append(max(0.0, min(10.0, h)))
    pob = elite + hijos
    if (g + 1) % 10 == 0:
        vals = [f(x) for x in pob]
        print("gen %2d   mejor x = %.5f   f = %.6f   promedio = %.6f" %
              (g + 1, elite[0], f(elite[0]), sum(vals) / len(vals)))

pob.sort(key=f, reverse=True)
print("Mejor solucion: x = %.5f   f = %.6f" % (pob[0], f(pob[0])))
print("Maximo real aproximado: x = 7.97867, f = 7.91673")

La versión en JavaScript, editable y ejecutable en el navegador, está en la página interactiva del tema.

Temas relacionados

Recocido simulado · Probabilidad clásica · Descenso del gradiente