Skip to content

Clase 8 — Algoritmos Genéticos: Representación y Problemas Clásicos (Mochila y TSP)

Resumen Ejecutivo

Continuación del bloque de algoritmos genéticos. Repaso de la estructura canónica del AG y profundización en la representación/codificación de fenotipos mediante variables binarias. Se trabajan los dos problemas de referencia de la optimización combinatoria: el problema de la mochila (Knapsack) y el problema del agente viajero (TSP), mostrando cómo codificar sus soluciones en cromosomas binarios/de orden y cómo manejar las restricciones mediante penalización en la función de aptitud. La actividad 1 se entregó el 30 de abril. ⚠️ EXAMEN: codificación binaria de soluciones, técnica de penalización de restricciones, estructura de la función de aptitud con restricción.

Conceptos Clave

  • Fenotipo / codificación: Representación de la solución del problema como un cromosoma. En este bloque se usa codificación binaria: cada gen es 0 o 1 (presencia/ausencia del atributo). ⚠️ EXAMEN
  • Función de aptitud (fitness): Función objetivo que el AG maximiza. Mide la calidad del individuo. ⚠️ EXAMEN
  • Criterio de parada: Puede ser número de iteraciones, alcanzar el óptimo conocido (solo en problemas pequeños/académicos), o número de iteraciones sin mejora. ⚠️ EXAMEN
  • Problema de la mochila (Knapsack): Maximizar el valor total de objetos cargados respetando una restricción de capacidad (peso, volumen, etc.). NP-completo. ⚠️ EXAMEN
  • Problema del agente viajero (TSP): Encontrar el recorrido más corto que visita todas las ciudades exactamente una vez y regresa al origen. NP-completo. ⚠️ EXAMEN
  • Penalización de restricciones: Técnica para manejar restricciones en algoritmos heurísticos. La restricción incumplida se incorpora a la función objetivo como un término negativo (penalización). ⚠️ EXAMEN
  • Función Lagrangiana relajada: Inspiración formal de la penalización — la restricción se sube a la función objetivo igualada a cero.

Desarrollo del Temario

1. Repaso de la estructura canónica del AG

1. Generar población inicial
2. Evaluar (función de aptitud)
3. Seleccionar individuos
4. Cruzar (crossover)
5. Mutar
6. Evaluar nueva generación
7. Repetir desde 3 hasta criterio de parada

Vistos en la clase 7: operadores de selección (torneo, ranking, etc.), cruce (one-point, uniforme, de orden) y mutación. Hoy el foco es en cómo representar la solución y cómo construir la función de aptitud cuando hay restricciones.

2. Codificación de fenotipos: variables binarias

La codificación más natural para problemas combinatorios es la binaria: cada gen vale 0 o 1.

  • 1 → el elemento está presente/seleccionado en la solución.
  • 0 → el elemento está ausente/no seleccionado.

Esta representación es directa para el problema de la mochila y adaptable al TSP.

3. Problema de la mochila (Knapsack)

3.1 Definición

Dados \(n\) objetos, cada uno con un valor \(v_i\) y un peso \(w_i\), y una mochila con capacidad máxima \(W\):

\[\text{maximizar} \quad \sum_{i=1}^{n} v_i \cdot x_i \quad \text{sujeto a} \quad \sum_{i=1}^{n} w_i \cdot x_i \leq W\]

Donde \(x_i \in \{0, 1\}\): 1 si se lleva el objeto \(i\), 0 si no.

3.2 Codificación del cromosoma

Un cromosoma de \(n\) genes, donde el gen \(i\) indica si el objeto \(i\) va en la mochila:

Objetos:   [Obj1, Obj2, Obj3, Obj4, Obj5]
Cromosoma: [  1,    0,    1,    0,    1 ]
           → llevar Obj1, Obj3 y Obj5

3.3 Problema con los algoritmos heurísticos: la restricción

Los algoritmos heurísticos (AG, PSO, etc.) no tienen mecanismo nativo para respetar restricciones — iteran libremente. Pueden generar soluciones que sobrepasen la capacidad de la mochila. La solución estándar es la penalización. ⚠️ EXAMEN

3.4 Función de aptitud con penalización

\[f(x) = \sum_{i} v_i x_i - M \cdot \max\left(0,\ \sum_{i} w_i x_i - W\right)\]
  • Si la solución cumple la restricción: \(\sum w_i x_i \leq W\) → el término de penalización es 0 → se evalúa solo el valor.
  • Si la solución viola la restricción: se resta una penalización proporcional al exceso × \(M\) (constante grande).

\(M\) debe ser suficientemente grande para que ninguna solución infactible pueda competir con una factible de bajo valor. ⚠️ EXAMEN

Analogía con la Lagrangiana: en optimización clásica, subir la restricción a la función objetivo igualando a cero da lugar a la función de Lagrange. La penalización es la versión heurística de esa idea.

4. Problema del agente viajero (TSP)

4.1 Definición

Dadas \(n\) ciudades y las distancias entre ellas, encontrar el ciclo hamiltoniano de coste mínimo: visitar cada ciudad exactamente una vez y regresar al punto de partida.

\[\text{minimizar} \quad \sum_{i} d(c_i, c_{i+1})\]

NP-completo: no hay algoritmo exacto eficiente para instancias grandes. ⚠️ EXAMEN

4.2 Representación del cromosoma

No se usa codificación binaria directa sino codificación de orden (permutación):

Ciudades:  [A, B, C, D, E]
Cromosoma: [3, 1, 4, 2, 5]  → recorrido C → A → D → B → E → C

Cada gen contiene el índice de la ciudad a visitar en esa posición del recorrido. No puede haber repetidos — los operadores de cruce deben ser cruce de orden (OX, PMX) para preservar la permutación válida.

4.3 Conversión a maximización

El AG suele maximizar la aptitud. Como el TSP minimiza distancia, la función de aptitud se invierte:

\[f(x) = \frac{1}{\text{distancia\_total}(x)} \quad \text{o} \quad f(x) = D_{max} - \text{distancia\_total}(x)\]

Así, el recorrido más corto tiene la mayor aptitud. ⚠️ EXAMEN

5. Flujo completo del AG aplicado

Inicialización: población de cromosomas aleatorios (permutaciones válidas para TSP,
                binarios para mochila)
        ↓
Evaluación: calcular f(x) para cada individuo (con penalización si hay restricciones)
        ↓
Selección: torneo, ruleta, etc.
        ↓
Cruce: one-point / uniforme (mochila) | OX / PMX (TSP)
        ↓
Mutación: bit-flip (mochila) | swap de ciudades (TSP)
        ↓
Nueva generación → repetir hasta criterio de parada

6. Criterios de parada

Criterio Cuándo usarlo
Número fijo de iteraciones Problemas pequeños, pruebas rápidas
Alcanzar el óptimo conocido Solo en contextos académicos donde se conoce el óptimo
N iteraciones sin mejora Más práctico en problemas reales — evita parar antes de tiempo y evita iterar inútilmente ⚠️ EXAMEN

Preguntas de Autoevaluación

  1. ¿Qué es el fenotipo en un AG? ¿Cómo se codifica en el problema de la mochila?
  2. Explica la estructura del cromosoma para el problema de la mochila con 5 objetos. ¿Qué significa un gen con valor 1?
  3. ¿Por qué los algoritmos heurísticos no pueden imponer restricciones directamente? ¿Cómo se soluciona?
  4. Escribe la función de aptitud del problema de la mochila con penalización. ¿Qué pasa cuando se viola la restricción?
  5. ¿Cómo se elige el valor de \(M\) en la penalización? ¿Qué ocurre si es demasiado pequeño?
  6. ¿Qué tipo de codificación se usa en el TSP? ¿Por qué no sirve la codificación binaria directa?
  7. ¿Por qué hay que usar operadores de cruce especiales (OX, PMX) en el TSP y no un cruce de un punto estándar?
  8. El TSP es un problema de minimización. ¿Cómo se transforma la función objetivo para que el AG pueda maximizar la aptitud?
  9. Nombra tres criterios de parada para un AG. ¿Cuál es el más usado en problemas reales y por qué?
  10. ¿Qué relación tiene la penalización con la función de Lagrange de la optimización clásica?