Skip to content

Clase 4 — Búsqueda Exhaustiva vs. Búsqueda Tabú: Problemas Combinatorios

Resumen Ejecutivo

En esta sesión se resolvieron dos problemas combinatorios clásicos (parques infantiles y problema de la mochila) comparando la búsqueda exhaustiva con la búsqueda tabú. Se formalizó cómo representar soluciones mediante vectores binarios (bits) y cómo diseñar vecindades para heurísticas de búsqueda local. Se introdujo la clasificación de metaheurísticas en búsqueda local vs. poblacional, y se discutieron estrategias para escapar de óptimos locales.

Conceptos Clave

  • Búsqueda exhaustiva: Algoritmo exacto que evalúa todas las soluciones posibles; garantiza el óptimo pero con coste computacional exponencial. ⚠️ EXAMEN
  • Búsqueda tabú: Heurística de búsqueda local que usa una memoria (lista tabú) para evitar ciclos, prohibiendo soluciones ya visitadas durante un número determinado de iteraciones. ⚠️ EXAMEN
  • Variable binaria de decisión: Representación donde \(x_i \in \{0, 1\}\) indica si se selecciona (1) o no (0) un elemento. ⚠️ EXAMEN
  • Espacio de soluciones factibles (\(S\)): Subconjunto de todas las combinaciones que cumple las restricciones del problema.
  • Vecindad (\(B\)): Conjunto de soluciones alcanzables desde la solución actual mediante una transformación local (cambio de k bits).
  • Lista tabú: Vector/memoria que almacena soluciones recientes y prohíbe su reutilización durante un número fijo de iteraciones.
  • Óptimo local: Solución mejor que todas sus vecinas pero no necesariamente la mejor global; problema principal de la búsqueda local. ⚠️ EXAMEN
  • Criterio de parada: Condición para detener el algoritmo (convergencia, número de iteraciones, tiempo de ejecución).

Desarrollo del Temario

1. Representación de soluciones con vectores binarios

El paso fundamental antes de programar cualquier algoritmo es diseñar cómo se representará la solución para que el ordenador la procese. ⚠️ EXAMEN

Para problemas de selección combinatoria se usa un vector de bits donde cada posición representa un elemento y el valor (0 o 1) indica si se selecciona o no.

Ejemplo (Parques infantiles): Se tienen 5 fincas y hay que construir 3 parques. El vector \([1, 0, 1, 1, 0]\) significa: construir en fincas 1, 3 y 4; no construir en fincas 2 y 5.

2. Problema de los Parques Infantiles

Enunciado: Un ayuntamiento quiere construir 3 parques infantiles eligiendo entre 5 fincas, minimizando el coste. Restricción adicional: las fincas 4 y 5 no pueden seleccionarse simultáneamente.

Formulación matemática: - Variables: \(x_i \in \{0, 1\}\), con \(i = 1, \ldots, 5\) - Función objetivo: Minimizar \(\sum_{i=1}^{5} c_i \cdot x_i\) (donde \(c_i\) es el coste de cada finca) - Restricción 1: \(\sum_{i=1}^{5} x_i = 3\) (exactamente 3 fincas) - Restricción 2: \(x_4 + x_5 \leq 1\) (no ambas simultáneamente) ⚠️ EXAMEN

Traducir restricciones del lenguaje natural a matemáticas es una habilidad clave para el examen. La frase "no construir simultáneamente en 4 y 5" se traduce como \(x_4 + x_5 \leq 1\), ya que si ambas fueran 1, la suma sería 2, violando la restricción. ⚠️ EXAMEN

Reducción del espacio de búsqueda (estilo cribado): - Total sin restricciones: \(2^5 = 32\) combinaciones - Aplicando restricción de 3 fincas: \(\binom{5}{3} = 10\) combinaciones - Aplicando restricción \(x_4 + x_5 \leq 1\): 7 soluciones factibles

Ejemplo: De las 32 combinaciones posibles, el cribado sucesivo reduce a 10 y luego a 7 soluciones. La diferencia de 32 a 7 parece pequeña, pero al escalar el problema, la reducción es crítica.

3. Problema de la Mochila (Knapsack Problem)

Enunciado: Seleccionar objetos para meter en una mochila maximizando el valor total, sin exceder una capacidad de peso.

Formulación: - Maximizar: \(\sum_{i=1}^{n} v_i \cdot x_i\) (valor total) - Restricción: \(\sum_{i=1}^{n} w_i \cdot x_i \leq W\) (peso máximo) - Con \(x_i \in \{0, 1\}\)

Con 4 objetos: \(2^4 = 16\) combinaciones posibles. Problema sencillo en pequeño, pero de complejidad NP-Hard al escalar. ⚠️ EXAMEN

Ejemplo: Con 4 objetos y capacidad máxima de peso 5 (o 7 según la variante), se generan las 16 combinaciones, se calcula valor y peso de cada una, se descartan las que exceden el peso, y de las factibles se elige la de mayor valor.

4. Búsqueda Exhaustiva (Algoritmo Exacto)

Procedimiento: 1. Generar todas las combinaciones posibles 2. Evaluar la función objetivo de cada una 3. Filtrar las que cumplen restricciones (soluciones factibles) 4. Seleccionar la de mejor valor (mínimo o máximo según el caso)

Ventaja: Garantiza encontrar el óptimo global. Desventaja: Coste exponencial; inviable para problemas grandes. ⚠️ EXAMEN

5. Búsqueda Tabú (Heurística de Búsqueda Local)

Parámetros de entrada: ⚠️ EXAMEN 1. Solución inicial (aleatoria, greedy, o dada por experto) 2. Tamaño de la lista tabú (típicamente entre 5 y 20 en problemas determinísticos) 3. Criterio de parada (convergencia, nº de iteraciones, tiempo) 4. Definición de vecindad (cómo generar vecinos y cuántos)

Pseudocódigo: 1. Generar solución inicial \(s_0\); fijar \(s^* = s_0\) (mejor global); lista tabú vacía 2. While (no se cumpla criterio de parada): - Generar vecinos de la solución actual - Evaluar todos los vecinos - Seleccionar el mejor vecino que no esté en la lista tabú - Si es mejor que \(s^*\), actualizar \(s^*\) - Añadir la solución a la lista tabú - Actualizar solución actual 3. Devolver \(s^*\)

Generación de vecinos en el problema de parques: Como se requieren exactamente 3 fincas, un vecino se genera haciendo dos cambios simultáneos: un 0 pasa a 1 y un 1 pasa a 0 (intercambio), manteniendo siempre la suma igual a 3. ⚠️ EXAMEN

Generación de vecinos en la mochila: Se puede ir agregando un producto (cambiar un 0 a 1) de uno en uno.

Ejemplo: Si la solución actual es \([1, 0, 1, 1, 0]\), un vecino por intercambio sería \([1, 1, 1, 0, 0]\) (se activa finca 2, se desactiva finca 4). Se evalúan todos los vecinos factibles y se elige el mejor.

Variantes de la lista tabú: - Determinística: tamaño fijo (ej. 3 iteraciones de prohibición) - Dinámica/adaptativa: el tamaño crece proporcionalmente al tamaño del problema - Aleatoria: tamaño variable según función estocástica

6. Clasificación de Metaheurísticas

Tipo Característica Ejemplos
Búsqueda local Un solo punto de inicio, explora vecindad Hill Climbing, Simulated Annealing, Búsqueda Tabú
Búsqueda poblacional Múltiples puntos simultáneos Algoritmos Genéticos, Optimización por Enjambre, Evolución Diferencial

Hill Climbing: Siempre se mueve al mejor vecino; muy susceptible a óptimos locales. ⚠️ EXAMEN

Simulated Annealing: Acepta soluciones peores con cierta probabilidad (simulando enfriamiento físico), lo que permite escapar de óptimos locales. ⚠️ EXAMEN

Búsqueda Tabú: Similar al Hill Climbing pero con memoria para evitar ciclos. ⚠️ EXAMEN

7. Estrategias para escapar de óptimos locales

  • Reinicio múltiple (multi-start): Ejecutar la búsqueda local desde diferentes puntos iniciales (aleatorios o determinados) y quedarse con la mejor solución global encontrada. ⚠️ EXAMEN
  • Listas tabú avanzadas (dinámicas, adaptativas)
  • Aceptación de soluciones peores (como en Simulated Annealing)

8. Punto inicial y diseño del algoritmo

Para las metaheurísticas, la solución inicial puede obtenerse mediante: - Aleatorio: un punto al azar - Conocimiento experto: solución razonable basada en experiencia - Algoritmo Greedy (voraz): construye rápidamente una primera solución, pero es "ciego" ante alternativas

Dos decisiones clave que debe tomar el programador: ⚠️ EXAMEN 1. Cómo representar la solución (diseño de la variable) 2. Cómo generar los vecinos (cantidad y método de generación)

Preguntas de Autoevaluación

  1. Dado un problema con 5 fincas donde hay que elegir 3 y las fincas 2 y 3 no pueden seleccionarse simultáneamente, ¿cómo formularías la restricción matemáticamente?

  2. ¿Cuál es la diferencia fundamental entre la búsqueda exhaustiva y la búsqueda tabú en cuanto a garantía de optimalidad?

  3. Si tienes un vector binario de 6 bits y debes seleccionar exactamente 4, ¿cuántas soluciones factibles existen (sin restricciones adicionales)?

  4. Explica qué es la lista tabú y por qué es necesaria en el algoritmo de búsqueda tabú.

  5. ¿Qué problema tienen las heurísticas de búsqueda local en su versión básica y qué estrategias existen para mitigarlo?

  6. En el problema de la mochila con \(n = 4\) objetos, ¿cuántas combinaciones totales genera la búsqueda exhaustiva? ¿Y si \(n = 20\)?

  7. Describe dos formas diferentes de generar la solución inicial en una metaheurística.

  8. ¿Cuál es la diferencia entre búsqueda local y búsqueda poblacional? Nombra un ejemplo de cada tipo.

Guía generada automáticamente a partir de transcripción con faster-whisper + Claude Opus.