Skip to content

Clase 9 — Exploración y Explotación en Algoritmos Genéticos: Problemas Multimodales y Algoritmo CHC

Resumen Ejecutivo

Última clase del bloque de algoritmos genéticos. Se formaliza el concepto de exploración vs. explotación —presente en todos los algoritmos bioinspirados— y se analiza su impacto en problemas multimodales (múltiples óptimos locales). Se presentan estrategias para gestionar ese equilibrio: secuenciales, paralelas e híbridas. El núcleo de la clase es el algoritmo CHC (Cross-generation Elitistic Selection, Heterogeneous Recombination and Cataclysm Mutation), una variante de AG con selección elitista, cruce uniforme, prevención de incesto mediante distancia de Hamming y reinicialización catastrófica. Actividad 2 con entrega el 21/05.

Conceptos Clave

  • Exploración: búsqueda global; saltos grandes por el espacio de búsqueda para descubrir regiones prometedoras. Aumenta la diversidad de la población. ⚠️ EXAMEN
  • Explotación: búsqueda local; refinamiento profundo en una región para encontrar el óptimo local. Mejora las soluciones actuales. ⚠️ EXAMEN
  • Problema multimodal: función con varios óptimos locales (varios picos o valles). El reto es no quedar atrapado en un óptimo local subóptimo. ⚠️ EXAMEN
  • Óptimo local vs. global: el óptimo local es el mejor dentro de una vecindad \(N(x^*)\); el global es el mejor en todo el espacio de búsqueda. ⚠️ EXAMEN
  • Convergencia prematura: el algoritmo se estanca en un óptimo local antes de explorar suficiente. Principal problema de los AG mal ajustados. ⚠️ EXAMEN
  • Distancia de Hamming: número de bits distintos entre dos cadenas binarias. Mide la similitud entre individuos en AG binarios. ⚠️ EXAMEN
  • Algoritmo CHC: variante de AG para problemas multimodales. Sin mutación clásica; en su lugar usa reinicialización catastrófica. ⚠️ EXAMEN
  • Sharing: técnica que distribuye el fitness de un individuo entre sus vecinos para fomentar la diversidad.
  • Clearing: variante del sharing que mantiene el fitness solo para los mejores individuos de cada vecindad y lo pone a cero en el resto.
  • Reinicialización catastrófica: cuando la población converge (umbral de Hamming ≈ 0), se descarta y se regenera conservando los mejores individuos (élite).

Desarrollo del Temario

1. Exploración vs. Explotación

El equilibrio exploración–explotación es transversal a todos los algoritmos bioinspirados (AG, PSO, colonias de abejas, etc.). En los AG, los parámetros que lo controlan son principalmente la tasa de mutación y la intensidad del cruce.

Exploración  →  saltos grandes  →  alta diversidad  →  evita óptimos locales
Explotación  →  cambios pequeños  →  convergencia local  →  refina la solución

Desequilibrio hacia la exploración: el algoritmo salta constantemente sin refinar — puede perderse el óptimo.

Desequilibrio hacia la explotación: el algoritmo converge pronto en un óptimo local — convergencia prematura.

Analogía con el gradiente descendente: una longitud de paso muy grande provoca oscilación; muy pequeña, convergencia lenta. ⚠️ EXAMEN

2. Óptimos local y global

Definición formal de óptimo local en minimización:

\[x^* \text{ es óptimo local} \iff f(x^*) \leq f(x) \quad \forall x \in N(x^*, \delta)\]

Donde \(N(x^*, \delta)\) es la vecindad de radio \(\delta\) alrededor de \(x^*\).

Óptimo global:

\[x^* \text{ es óptimo global} \iff f(x^*) \leq f(x) \quad \forall x \in \mathcal{D}\]

Con \(\mathcal{D}\) el dominio completo de búsqueda (siempre acotado en la práctica).

Los AG no garantizan el óptimo global — son heurísticas. El objetivo es encontrar una buena solución en tiempo razonable. ⚠️ EXAMEN

3. Problemas multimodales

Un problema multimodal tiene varios óptimos locales (varios picos en maximización, varios valles en minimización). Los AG tienen tendencia natural a converger prematuramente en uno de esos óptimos locales si la diversidad de la población cae.

Ejemplo típico en la asignatura: la función de Ackley o funciones similares con múltiples valles en varias dimensiones.

graph LR
    A[Población inicial\nalto diversidad] --> B[Exploración\nsaltos grandes]
    B --> C{¿Encontró región\nprometedora?}
    C -- sí --> D[Explotación\nconvergencia local]
    C -- no --> B
    D --> E{¿Convergencia\nprematura?}
    E -- sí --> F[Reinicialización\ncatastrófica]
    F --> A
    E -- no --> G[Óptimo encontrado]

4. Estrategias para gestionar el equilibrio

4.1 Estrategias secuenciales

Ejecutan un único AG modificando operadores o parámetros a lo largo de las generaciones:

Estrategia Descripción
Cambio de operadores Empezar con cruces/mutaciones de alta intensidad (exploración) y reducirlos progresivamente (explotación).
Ajuste de parámetros Variar la tasa de mutación, umbral de distancia u otros parámetros por generación.
Multietapa diferenciada Primera fase exploratoria, segunda fase intensiva.
Híbrido secuencial Combinar AG con búsqueda local (primero AG para buenas semillas, luego búsqueda local; o al revés).

El híbrido secuencial es el origen histórico del término metaheurística: combinar heurísticas a conveniencia. ⚠️ EXAMEN

4.2 Estrategias paralelas

Ejecutan múltiples poblaciones en paralelo, mayor coste computacional pero menor tiempo de reloj:

Modelo Descripción
Maestro-esclavo (master-slave) Una sola población; la evaluación del fitness se paraleliza entre varios procesadores.
Islas (island model) Varias poblaciones independientes evolucionan en paralelo con migración periódica entre ellas. ⚠️ EXAMEN
Celular Se superpone una rejilla al espacio de búsqueda; cada celda contiene subpoblaciones que interactúan localmente.
Híbrido paralelo Combina modelos anteriores; por ejemplo: empezar con maestro-esclavo y pasar a islas.

4.3 Técnicas de diversidad: Sharing y Clearing

Fitness Sharing: el fitness de un individuo se comparte (divide) entre los individuos de su vecindad, ponderado por su similitud. Penaliza las zonas sobrepobladas y atrae hacia regiones prometedoras desocupadas.

\[f'(x_i) = \frac{f(x_i)}{\sum_{j} sh(d(x_i, x_j))}\]

Donde \(sh(d)\) es la función de sharing (valor entre 0 y 1 según la distancia \(d\)). ⚠️ EXAMEN

Clearing: dentro de cada vecindad, solo los \(k\) mejores individuos conservan su fitness; el resto recibe fitness = 0. Reduce el coste computacional respecto al sharing.

5. Algoritmo CHC

CHC = Cross-generation Elitistic Selection, Heterogeneous Recombination and Cataclysm Mutation. Diseñado específicamente para problemas multimodales. Rasgo llamativo: no tiene mutación clásica; la diversidad se gestiona por la distancia de Hamming y la reinicialización catastrófica. ⚠️ EXAMEN

5.1 Selección elitista

Evalúa el fitness de toda la población, ordena de mejor a peor y selecciona los \(k\) mejores directamente. Sin ruleta ni torneo — determinista. ⚠️ EXAMEN

5.2 Cruce uniforme con prevención de incesto

  1. Calcular la distancia de Hamming entre los dos padres: contar cuántos bits difieren.
  2. Umbral de incesto (\(d_{min}\)): si la distancia es menor o igual al umbral, no se cruzan (se descarta la pareja — "prevención de incesto"). ⚠️ EXAMEN
  3. Si la distancia supera el umbral, se aplica el cruce uniforme: de los bits distintos entre los dos padres, se intercambia el 50 % (elegidos aleatoriamente).

Ejemplo con cadenas de 8 bits:

Padre A:  1 0 1 1 0 0 1 0
Padre B:  1 1 1 0 0 1 1 0
Distintos:  ^     ^   ^      → 3 bits distintos
50% de 3 → intercambiar 1 bit (redondeado)

Hijo A:  1 1 1 1 0 0 1 0   (se tomó bit 2 de Padre B)
Hijo B:  1 0 1 0 0 1 1 0   (se tomó bit 2 de Padre A)

El umbral \(d_{min}\) se inicializa típicamente a \(L/4\) (un cuarto de la longitud del cromosoma) y se va reduciendo a lo largo de las generaciones. ⚠️ EXAMEN

5.3 Reinicialización catastrófica (cataclysm)

Cuando el umbral \(d_{min}\) alcanza un valor muy bajo (la población ha convergido y ya no se generan hijos), el algoritmo:

  1. Conserva los mejores individuos (élite — "arca de Noé").
  2. Descarta el resto de la población.
  3. Genera una nueva población aleatoria (o perturbada a partir de la élite).
  4. Reinicia el umbral \(d_{min}\).

Esto sustituye a la mutación clásica: en lugar de perturbaciones pequeñas y continuas, aplica una perturbación masiva y puntual. ⚠️ EXAMEN

5.4 Pseudocódigo CHC

Inicializar población P de N individuos (longitud L)
d_min ← L / 4

Mientras no se cumpla criterio de parada:
    Para cada par de padres (A, B) seleccionados (elitista):
        d ← distancia_Hamming(A, B)
        Si d > d_min:
            (hijo_A, hijo_B) ← cruce_uniforme(A, B)  // intercambiar 50% bits distintos
            Añadir hijos al pool
        Si no:
            Descartar pareja  // prevención de incesto

    Selección elitista sobre (P ∪ pool) → nueva P
    d_min ← d_min - 1

    Si no se generaron hijos (d_min ≤ 0):
        Conservar k mejores (élite)
        Reinicializar resto de P aleatoriamente
        d_min ← L / 4  // reinicio catastrófico

6. Reinicialización como estrategia general

Independientemente del algoritmo, la reinicialización es una herramienta habitual ante convergencia prematura:

  • Manual: el investigador detecta el estancamiento y reinicia con nuevos parámetros o nueva semilla.
  • Automática: muchas librerías (R, Python) exponen un argumento n_restarts o similar.
  • Con élite conservada: los mejores individuos de la última ejecución sirven de semilla para la siguiente.

En entornos académicos donde se conoce el óptimo, la comparación directa permite detectar convergencia prematura con precisión. En problemas reales, se usa la ausencia de mejora durante \(N\) iteraciones como indicador. ⚠️ EXAMEN

7. Medida de diversidad: Distancia de Hamming

Para cadenas binarias de longitud \(L\):

\[d_H(A, B) = \sum_{i=1}^{L} \mathbf{1}[A_i \neq B_i]\]

Es decir, el número de posiciones en que las dos cadenas difieren. Rango: \([0, L]\).

  • \(d_H = 0\): individuos idénticos.
  • \(d_H = L\): individuos completamente opuestos.
  • \(d_H \leq d_{min}\): demasiado similares → no cruzar (CHC).

Para otros tipos de codificación (permutaciones, reales) existen métricas análogas. ⚠️ EXAMEN

Ejemplos y Ejercicios

Ejemplo 1: Cálculo de distancia de Hamming y decisión de cruce

Cromosoma A: 1 0 1 1 0 1 0 1   (L = 8)
Cromosoma B: 1 0 0 1 1 1 0 0
                   ^   ^     ^
d_H(A, B) = 3

d_min = L/4 = 8/4 = 2

Como d_H = 3 > d_min = 2  →  SE CRUZAN
Bits distintos: posiciones 3, 5, 8
50% de 3 = 1 bit a intercambiar
Se elige aleatoriamente: posición 3

Hijo A: 1 0 0 1 0 1 0 1
Hijo B: 1 0 1 1 1 1 0 0

Ejemplo 2: Disparador de reinicialización catastrófica

Generación 45: d_min = 1, solo 2 parejas generan hijos
Generación 46: d_min = 0, ninguna pareja supera el umbral → 0 hijos generados

→ Cataclismo:
  - Conservar 10 mejores individuos (élite)
  - Generar 90 nuevos individuos aleatorios
  - Reiniciar d_min = L/4 = 2

Preguntas de Autoevaluación

  1. Define exploración y explotación en el contexto de los algoritmos genéticos. ¿Qué ocurre si se favorece en exceso una de las dos?
  2. ¿Qué es un problema multimodal? Pon un ejemplo y explica por qué los AG estándar tienen dificultades con ellos.
  3. Diferencia óptimo local y óptimo global. ¿Cuál de los dos garantizan (o no) los algoritmos heurísticos?
  4. Explica la diferencia entre estrategias secuenciales y paralelas para gestionar la exploración–explotación. Da un ejemplo de cada una.
  5. ¿Qué es el modelo de islas (island model)? ¿Qué ventaja ofrece frente al AG estándar?
  6. Describe el mecanismo de fitness sharing. ¿Qué efecto tiene sobre la distribución de la población?
  7. ¿Qué es la distancia de Hamming? Calcula \(d_H\) entre 10110010 y 11010011.
  8. Explica la prevención de incesto en el CHC. ¿Por qué se inicializa el umbral \(d_{min}\) a \(L/4\)?
  9. ¿Por qué el algoritmo CHC no usa mutación clásica? ¿Qué mecanismo cumple esa función?
  10. Describe el proceso de reinicialización catastrófica. ¿Qué se conserva y qué se descarta? ¿En qué condición se activa?
  11. ¿Cuál es la diferencia entre sharing y clearing? ¿Qué ventaja computacional ofrece el clearing?
  12. En el cruce uniforme del CHC con dos padres que difieren en 5 bits y \(d_{min} = 2\), ¿cuántos bits se intercambian? Justifica.