Algoritmos genéticos

Un algoritmo genético no sabe nada del problema que resuelve. No calcula derivadas, no conoce la forma del paisaje y no tiene un plan. Solo mantiene una población de candidatos, los evalúa, y deja que los mejores tengan más descendencia. La esperanza es que la selección acumule las piezas correctas antes de que la población se vuelva uniforme.

La idea

La inspiración es la evolución biológica, pero el algoritmo es una técnica de búsqueda estocástica, no una simulación de biología. Cada individuo representa una solución posible. Una función de fitness le asigna un número. En cada generación se seleccionan padres, se recombinan sus genomas y se introducen mutaciones. Los hijos reemplazan a la población y el proceso se repite.

La pieza central es la representación. Un genoma puede ser una cadena de bits, un vector de números reales, una permutación o un árbol. La elección no es neutral: determina qué soluciones son alcanzables y qué operadores tienen sentido.

Las piezas

pieza	función
representación	codifica una solución como un genoma
fitness	mide qué tan buena es una solución
selección	favorece a los individuos con mejor fitness
cruce	combina material genético de dos padres
mutación	introduce cambios pequeños y aleatorios
elitismo	preserva los mejores individuos sin cambios

La selección por torneo es una de las más simples: se eligen k individuos al azar y gana el de mayor fitness. Con k = 3 la presión selectiva es moderada. El cruce de un punto corta dos genomas en la misma posición y los intercambia. La mutación voltea bits con probabilidad baja. El elitismo evita perder la mejor solución encontrada.

Un ejemplo concreto

Queremos maximizar una función multimodal en el intervalo [0, 32]:

El genoma es una cadena de 16 bits. Se interpreta como un entero entre 0 y 65.535, que se escala linealmente a [0, 32]. La población tiene 30 individuos; se usan torneos de tamaño 3, cruce de un punto con probabilidad 0,9, mutación por bit de 0,01 y elitismo de dos individuos. Durante 100 generaciones se registran el mejor fitness y la media.

En esta ejecución el mejor individuo quedó en x ≈ 26.741, con f(x) ≈ 36.722. El máximo de la función está en x ≈ 26.741, así que el algoritmo encontró la región correcta. Lo importante no es el número exacto, sino la forma de la curva: el mejor fitness sube rápido y se estanca, mientras la media tarda más en acercarse.

La diferencia entre ambas curvas es información útil. Si la media se pega al mejor demasiado pronto, la población perdió diversidad y la búsqueda puede quedar atrapada en un óptimo local. Si la media nunca sube, la presión selectiva es demasiado débil o la representación no permite construir mejores soluciones.

Por qué funciona, y cuándo no

La explicación clásica es el teorema de los esquemas: la selección aumenta la representación de los bloques que están por encima de la media, y el cruce puede recombinar bloques buenos de padres distintos. Es una justificación útil, no una garantía. El teorema describe el efecto esperado de la selección sobre patrones, pero no promete que el algoritmo encuentre el óptimo global.

El paisaje importa. Si el fitness es ruidoso, si las variables interactúan de forma hostil o si el óptimo global está rodeado de valles profundos, la población puede converger a una solución mediocre. El fenómeno se llama convergencia prematura, y se combate con más diversidad, mutación adaptativa, reinicios o poblaciones estructuradas. No hay una receta universal.

Tampoco existe un algoritmo genético “mejor” para todos los problemas. El teorema de no free lunch dice que, promediado sobre todos los paisajes posibles, ningún algoritmo de búsqueda supera a otro. Un algoritmo genético incorpora supuestos: que el espacio se puede representar, que las buenas soluciones comparten bloques y que la selección puede explotarlos. Si esos supuestos no se cumplen, el método pierde su ventaja.

Por eso un GA no suele ser la primera opción cuando hay gradientes, restricciones suaves o un problema convexo. Es más razonable cuando el fitness es una caja negra, cuando el espacio es discreto o combinatorio, cuando hay múltiples óptimos o cuando evaluar una solución es caro pero se puede paralelizar.

Una implementación mínima

El siguiente código reproduce el experimento. No es un framework: es el esqueleto para entender dónde está cada decisión.

import math
import random

BITS, POP, GENS = 16, 30, 100
TOUR, PC, PM = 3, 0.9, 0.01
random.seed(20261024)


def fitness(bits):
    x = int("".join(map(str, bits)), 2) / (2**BITS - 1) * 32
    return x * math.sin(x) + 10


def tournament(population, fits):
    contenders = random.sample(range(len(population)), TOUR)
    return population[max(contenders, key=lambda i: fits[i])]


population = [[random.randint(0, 1) for _ in range(BITS)]
              for _ in range(POP)]

for gen in range(GENS):
    fits = [fitness(g) for g in population]
    elite = sorted(range(POP), key=lambda i: fits[i], reverse=True)[:2]
    next_pop = [population[i][:] for i in elite]

    while len(next_pop) < POP:
        a = tournament(population, fits)[:]
        b = tournament(population, fits)[:]

        if random.random() < PC:
            cut = random.randint(1, BITS - 1)
            a, b = a[:cut] + b[cut:], b[:cut] + a[cut:]

        for g in (a, b):
            for i in range(BITS):
                if random.random() < PM:
                    g[i] ^= 1

        next_pop.extend([a, b])

    population = next_pop[:POP]

best = max(population, key=fitness)
print("".join(map(str, best)), fitness(best))

Hay tres detalles que suelen pasarse por alto. Primero, los padres se copian antes de mutar; si no, la mutación modifica la población anterior. Segundo, el elitismo se aplica antes del cruce y la mutación, para que el mejor individuo no se pierda. Tercero, el torneo se hace con reemplazo: un mismo individuo puede ser seleccionado varias veces, lo que aumenta la presión selectiva.

Cierre

Un algoritmo genético no es una inteligencia y no “descubre” el problema. Es una forma de sesgar una búsqueda: mantener varias respuestas, castigar a las malas y dejar que la variación explore. Su virtud es la misma que la de la hormiga de Langton: reglas locales simples, comportamiento global que no se ve a simple vista.