Cerramos el módulo con el problema que lo abrió. En 03-01 calculamos que el orden de las entregas de una furgoneta tiene n! posibilidades y que la fuerza bruta muere a partir de una docena de paradas; en 03-02 aprendimos a encontrar el mejor camino entre dos puntos, y en 03-03 a decidir frente a un rival. Pero ninguna de esas técnicas resuelve el problema completo de Diego: dado el mapa y las entregas del día, ¿en qué orden debe visitarlas la furgoneta para recorrer los menos kilómetros posibles? Es el célebre problema del viajante, y es el ejemplo perfecto de un problema de optimización: no buscamos un camino en un grafo, sino la mejor de entre un número astronómico de soluciones completas. En esta lección aprenderemos a formularlo (variables, función objetivo, restricciones), distinguiremos métodos exactos y aproximados, y construiremos tres algoritmos de búsqueda local y metaheurísticas que resuelven el viajante de NovaMarket en segundos: ascenso de colina, recocido simulado y algoritmos genéticos, validándolos contra la fuerza bruta en tamaño pequeño. Después aplicaremos la misma idea a la asignación de pedidos a los almacenes de Zaragoza y Getafe con una restricción de capacidad, y veremos cómo una restricción se convierte en una penalización. Terminaremos con la conexión que abre el módulo 4: entrenar un modelo de aprendizaje automático es, por dentro, también un problema de optimización.

1. Qué es un problema de optimización: variables, función objetivo, restricciones
2. Optimización exacta frente a aproximada; búsqueda local
3. Preparar el problema del viajante de NovaMarket: la matriz de distancias con Dijkstra
4. Fuerza bruta como referencia (7 entregas)
5. Ascenso de colina por intercambio de paradas: óptimos locales y reinicios aleatorios
6. Un problema mayor: 15 direcciones de entrega
7. Recocido simulado: la intuición de la temperatura
8. Algoritmos genéticos: población, torneo, cruce, mutación y elitismo
9. Segundo ejemplo: asignación de pedidos a dos almacenes con capacidad (restricciones como penalización)
10. Tabla comparativa de métodos y cuándo usar cada uno
11. Enlace con el módulo 4: aprender es optimizar

Un problema de optimización tiene tres componentes:

Cada asignación concreta de valores a las variables es una solución candidata; las que cumplen las restricciones son factibles; la factible con mejor objetivo es la óptima. La diferencia con la búsqueda de 03-02 es de perspectiva: allí el objeto era un camino que se construía paso a paso desde el estado inicial, y el coste se acumulaba tramo a tramo; aquí trabajamos con soluciones completas que evaluamos de golpe con la función objetivo, y el "camino" que nos importa no está en el mapa, sino en el espacio de soluciones. En 02-01 dijimos que un agente basado en utilidad elige la acción que maximiza una función; los algoritmos de esta lección son la maquinaria para hacer esa elección cuando las opciones son demasiadas para listarlas.

La búsqueda local parte de una solución completa (buena o mala) y la mejora paso a paso aplicando pequeños cambios, llamados movimientos; el conjunto de soluciones alcanzables con un movimiento desde la actual es su vecindario. La metáfora habitual es un paisaje: cada solución es un punto, su objetivo es la altura, y el algoritmo es un excursionista que quiere llegar al punto más alto (o más bajo, si minimizamos) moviéndose solo a puntos vecinos. Con esa imagen se entienden de inmediato los tres algoritmos de la lección: el ascenso de colina sube siempre y se queda atascado en la primera cima; el recocido simulado se permite bajar a veces para escapar; el algoritmo genético manda a muchos excursionistas a la vez y cruza sus rutas.

Un apunte de vocabulario: aunque en el viajante minimizamos kilómetros, la literatura habla de "ascenso" de colina por costumbre; minimizar f es maximizar −f, así que la idea es la misma.

En 03-01, la fuerza bruta solo aceptaba tramos entre barrios conectados por una carretera directa. Ahora podemos hacerlo bien: la distancia entre dos paradas cualesquiera es la del camino más corto entre ellas, que calculamos con la búsqueda de coste uniforme (Dijkstra) de 03-02, ejecutada desde cada nodo. El resultado es una matriz de distancias con la que el viajante ya no depende de la topología del grafo. Esta separación en dos capas (Dijkstra/A* para "cómo ir de A a B", optimización para "en qué orden visitar A, B, C…") es exactamente como funcionan los planificadores de reparto reales.

MATRIZ[a][b] es la distancia mínima por carretera de a a b; por ejemplo, MATRIZ["Almacen_Getafe"]["Retiro"] vale 17,0 (el resultado de A* en 03-02) y MATRIZ["Leganes"]["Vallecas"] vale 14,0 aunque no exista carretera directa. La matriz completa, en km:

La función longitud_ruta es nuestra función objetivo: recibe una permutación de las entregas (la variable de decisión) y devuelve los kilómetros de la ruta cerrada. La restricción "cada entrega exactamente una vez" queda garantizada por construcción, porque solo manejaremos permutaciones.

Con 7 entregas hay 7! = 5.040 permutaciones: la fuerza bruta de 03-01, ahora sobre la matriz, nos da el óptimo exacto que servirá de vara de medir para los métodos aproximados.

El óptimo son 39,0 km (curiosamente coincide con el que encontró la versión restringida de 03-01: en este mapa la mejor ruta ya usaba solo carreteras directas). Recuerda que este número es inalcanzable por fuerza bruta a partir de unas 12-13 entregas.

Movimiento: intercambiar dos paradas de la ruta. Con 7 paradas hay 21 intercambios posibles: ese es el vecindario. Algoritmo: mirar todos los vecinos, moverse al mejor si mejora la ruta actual, y parar cuando ningún vecino mejora (versión de "mejor mejora"; la alternativa de "primera mejora" se mueve al primer vecino que mejore).

En dos pasos ha pasado de 68,5 a 47,5 km, y ahí se ha parado: ninguno de los 21 intercambios mejora esa ruta, pero el óptimo es 39,0. Hemos llegado a un óptimo local: una cima desde la que todo lo que se ve alrededor es cuesta abajo, aunque haya montañas más altas más allá. Es el defecto estructural del ascenso de colina, y tiene tres remedios clásicos:

• Vecindarios más ricos (más movimientos posibles: por ejemplo, invertir un segmento de la ruta, el famoso 2-opt, que usaremos en la sección 7).
• Reinicios aleatorios: repetir el ascenso desde muchas soluciones iniciales distintas y quedarse con la mejor. Es simple, se paraleliza sin esfuerzo y funciona sorprendentemente bien.
• Aceptar a veces movimientos que empeoran, que es la idea del recocido simulado.

Con 10 reinicios alcanza el óptimo de la fuerza bruta. Si repites el experimento con 20 inicios distintos verás que unos 8 de cada 20 terminan en 39,0, otros tantos en 39,5 y el resto en óptimos locales peores (46-47,5 km): la probabilidad de acertar con un solo intento es de un 40 %, pero con 10 intentos independientes es de más del 99 %. Y el coste total ha sido 10 × (unos pocos pasos × 21 evaluaciones): unas 500 evaluaciones frente a las 5.040 de la fuerza bruta. Con 7 paradas la diferencia es anecdótica; con 30 es la diferencia entre segundos y siglos.

Para que las metaheurísticas tengan algo que morder, generamos una instancia mayor: 15 direcciones concretas de clientes repartidas alrededor de los barrios de COORDENADAS (03-02), con la distancia en línea recta como aproximación de la distancia real (en producción usaríamos la matriz Dijkstra sobre el callejero, exactamente como en la sección 3; el algoritmo de optimización no nota la diferencia porque solo consulta dist[a][b]).

Los nombres de las direcciones llevan el prefijo del barrio (E04_Vall es la cuarta entrega, cerca de Vallecas). Con 15 paradas la fuerza bruta necesitaría 15! ≈ 1,3 billones de evaluaciones; el ascenso de colina simple se atasca en 51,8 km, y con reinicios llega a 36,45 km, que es (como confirmarán los otros dos métodos) el mejor valor conocido para esta instancia. Guarda esa cifra como referencia.

El recocido simulado (simulated annealing) toma su nombre de la metalurgia: un metal calentado y enfriado lentamente cristaliza en una estructura de mínima energía, mientras que enfriado de golpe queda lleno de defectos. Traducido a búsqueda local:

• En cada iteración se genera un vecino al azar (no todos).
• Si mejora, se acepta siempre.
• Si empeora en una cantidad Δ, se acepta con probabilidad e^(−Δ/T), donde T es la temperatura. Con T alta casi todo se acepta (exploración libre, se salta entre valles); con T baja casi nada que empeore se acepta (el algoritmo se comporta como ascenso de colina y afina la solución).
• T empieza alta y se reduce poco a poco (enfriamiento), por ejemplo multiplicándola por 0,995 en cada iteración.

Unos números para fijar la intuición (probabilidad de aceptar un empeoramiento de Δ km a temperatura T):

Al principio acepta casi cualquier cosa; al final, prácticamente solo mejoras. Como movimiento usaremos el 2-opt: elegir dos posiciones e invertir el segmento entre ellas, que en rutas es más eficaz que el intercambio simple porque deshace cruces.

Desde la misma ruta inicial de 97,6 km en la que el ascenso de colina se quedó en 51,8, el recocido llega a 36,45 km (o a 36,84, un 1 % peor) en unas 1.400 evaluaciones, aceptando por el camino un centenar de movimientos que empeoraban: esos "pasos atrás" son los que le permiten salir de los valles. Tres detalles del código merecen atención: se guarda aparte la mejor solución vista (la actual puede empeorar al final de la fase caliente); la temperatura se multiplica en cada iteración (enfriamiento geométrico, el más habitual); y el número de iteraciones lo fija el ritmo de enfriamiento (de 10 a 0,01 a razón de 0,995 son unas 1.380 iteraciones). Enfriar más despacio (0,999) mejora la calidad a cambio de más tiempo; es el mando que Marta ajustará según los segundos disponibles antes de las 8 de la mañana.

Los algoritmos genéticos se inspiran en la evolución: en lugar de una solución que se mueve, mantienen una población de soluciones que se reproduce; las mejores tienen más descendencia, los hijos combinan trozos de sus padres y de vez en cuando sufren mutaciones. Vocabulario y ciclo:

• Individuo / cromosoma: una solución (una ruta); sus genes son las paradas.
• Aptitud (fitness): el objetivo (menos km, más apto).
• Selección por torneo: se toman k individuos al azar y gana el mejor; los buenos se reproducen más, pero los malos también tienen alguna opción, lo que preserva diversidad.
• Cruce: combinar dos padres. En permutaciones no vale copiar mitades (se repetirían paradas); el cruce de orden (OX) copia un segmento del padre 1 y rellena las posiciones restantes con las paradas que faltan en el orden en que aparecen en el padre 2.
• Mutación: cambio aleatorio pequeño (intercambiar dos paradas), que introduce novedad e impide que la población se vuelva idéntica.
• Elitismo: los mejores individuos pasan sin cambios a la siguiente generación, para no perder nunca la mejor solución encontrada.

La población empieza con una media de casi 100 km y en 18 generaciones (unas 1.000 evaluaciones) su mejor individuo ya está en 36,45 km. La ruta final tiene todo el sentido geográfico: sale hacia Villaverde, recorre Vallecas, sube a Retiro y Arganzuela, baja por Carabanchel y vuelve por Leganés. Un ejemplo del cruce OX para que veas la mecánica: con padres A B C D E F G y G F E D C B A, si el segmento elegido es las posiciones 1-2, el hijo hereda _ B C _ _ _ _ del primero y rellena con G F E D A (el orden del segundo, saltando B y C): G B C F E D A. Ninguna parada se repite ni se pierde.

Dos advertencias honestas: los algoritmos genéticos son sensibles a sus parámetros y estocásticos. Con otras semillas, la misma configuración termina en 41,3, 43,4, 43,8 o 46,1 km: la población converge prematuramente (todos los individuos se parecen y el cruce ya no aporta nada). Subir la probabilidad de mutación a 0,5 y la población a 150 hace que 4 de cada 5 ejecuciones alcancen 36,45. Comparado con el recocido, aquí el genético necesita más evaluaciones para el mismo resultado; su ventaja aparece en problemas donde no hay un movimiento local natural, donde la evaluación es paralelizable, o donde interesa obtener varias soluciones buenas y distintas.

Cambiemos de problema pero no de método. Cada mañana Diego debe decidir qué pedidos se preparan en Getafe y cuáles en Zaragoza (caso 6). Cada pedido tiene un coste de envío distinto según el almacén (por la zona de destino) y un volumen en cajas; cada almacén tiene una capacidad diaria de preparación en cajas. Formulación:

• Variables: para cada pedido, "Getafe" o "Zaragoza" (una lista de 20 etiquetas; 2²⁰ ≈ 1 millón de soluciones).
• Objetivo: minimizar el coste total de envío.
• Restricción: la suma de cajas asignadas a cada almacén no puede superar su capacidad.

La forma más habitual de tratar una restricción en búsqueda local es convertirla en penalización: sumar al objetivo un coste artificial proporcional a la violación (aquí, 20 € por cada caja de exceso). Así todas las soluciones son "evaluables", las infactibles simplemente salen muy caras, y el algoritmo aprende a evitarlas.

La asignación ingenua es la más barata sobre el papel (239 €), pero carga 38 cajas en Getafe, 6 por encima de su capacidad: penalizada, cuesta 359. El ascenso de colina mueve a Zaragoza dos pedidos de la zona centro (los que menos pierden al cambiar de almacén: 15 € y 3 € más) y llega a una asignación factible de 257 €. Como aquí el espacio tiene "solo" 2²⁰ soluciones, podemos comprobar por enumeración completa que 257 € es el óptimo exacto; con 200 pedidos (2²⁰⁰) esa comprobación sería imposible y la búsqueda local sería la única opción.

Dos lecciones de este ejemplo: la penalización debe ser lo bastante alta para que ninguna solución infactible salga a cuenta (con 20 €/caja funciona; con 2 €/caja el algoritmo preferiría pagar la multa), pero no tan alta que aplaste las diferencias de coste real y convierta el paisaje en una meseta; y el mismo esqueleto de búsqueda local sirve para problemas de naturaleza distinta cambiando solo la representación, el vecindario y la función objetivo.

La regla de decisión de Marta: si el problema es pequeño o tiene estructura conocida, exacto (y hay solvers de programación lineal excelentes, aunque quedan fuera de este curso); si no, ascenso de colina con reinicios como base, recocido simulado cuando se atasca, y genético cuando la representación lo pide. Y siempre validar en pequeño contra la fuerza bruta, como hemos hecho.

Cerramos con la conexión más importante de la lección. Recuerda aprender_umbral de 01-02: buscaba el umbral que mejor separaba dos clases probando valores. Eso ya era optimización: variable (el umbral), objetivo (aciertos), método (fuerza bruta sobre una rejilla). Todo entrenamiento de un modelo de aprendizaje automático es un problema de optimización: las variables son los parámetros del modelo (unos pocos en una regresión, miles de millones en un gran modelo de lenguaje), la función objetivo es una medida de error sobre los datos de entrenamiento (la "función de pérdida"), y las restricciones o penalizaciones son las técnicas de regularización de 04-06. La diferencia con esta lección es que, cuando los parámetros son números continuos y la función de pérdida es suave, no hace falta probar vecinos al azar: se puede calcular en qué dirección desciende la pérdida (su gradiente) y dar un paso en ella, una y otra vez. Ese método, el descenso del gradiente, es el "ascenso de colina con brújula" que hace funcionar las redes neuronales, y lo estudiaremos en 05-03. Todo lo que has aprendido hoy sobre óptimos locales, tamaño de paso (aquí, temperatura y vecindario) y validación te servirá tal cual allí.

• Confundir el óptimo local con el global: un ascenso de colina que "no mejora más" no ha terminado, se ha atascado. Reinicia, cambia el vecindario o usa recocido antes de dar la solución por buena.
• No validar en pequeño: antes de confiar en una metaheurística para 40 paradas, comprueba que en 7 u 8 encuentra el mismo óptimo que la fuerza bruta. Un error en la función objetivo (por ejemplo, olvidar el tramo de vuelta al almacén) pasa desapercibido sin esa comprobación.
• Semillas y reproducibilidad: los métodos de esta lección son estocásticos. Fija la semilla (random.Random(semilla)) para poder reproducir resultados y depurar, y evalúa siempre varias semillas antes de sacar conclusiones sobre un parámetro.
• Enfriar demasiado rápido en el recocido convierte el algoritmo en un ascenso de colina caro; enfriar demasiado lento desperdicia tiempo. Empieza con T₀ del orden de un empeoramiento "grande" típico y ajusta mirando cuántos movimientos a peor se aceptan.
• Cruce que rompe la representación: en permutaciones, un cruce ingenuo produce rutas con paradas repetidas o ausentes. Usa OX u otro operador que preserve permutaciones y comprueba tras cada cruce que sorted(hijo) == sorted(padre1).
• Penalización mal calibrada: demasiado baja y la solución "óptima" viola la restricción; demasiado alta y el algoritmo no distingue entre soluciones factibles. Comprueba siempre exceso == 0 en la solución final.
• Olvidar guardar la mejor solución vista en el recocido: la solución actual puede empeorar al aceptar movimientos a peor; devuelve siempre mejor, no actual.
• Optimizar el objetivo equivocado: como avisó 02-01, si el coste solo mide kilómetros, la ruta óptima puede incumplir todas las franjas horarias. Añade al objetivo (o como penalización) todo lo que importe.

Implementa la heurística constructiva del vecino más próximo: partiendo del almacén, ir siempre a la entrega pendiente más cercana. Aplícala a ENTREGAS con MATRIZ y a ENTREGAS15 con DIST15, compara con los óptimos conocidos (39,0 y 36,45 km) y úsala como ruta inicial del ascenso de colina. ¿Mejora el resultado respecto a un inicio aleatorio?

Escribe vecinos_2opt(ruta) que genere todas las rutas obtenidas al invertir un segmento ruta[i:j+1] y úsalo en lugar de vecinos_intercambio dentro de ascenso_colina (parametriza la función de vecindario). Compara, para 20 inicios aleatorios sobre ENTREGAS15, cuántas veces alcanza 36,45 km cada vecindario.

Cambia CAPACIDAD a {"Getafe": 30, "Zaragoza": 32} y vuelve a ejecutar ascenso_asignacion desde la solución ingenua. ¿Qué pedidos se mueven ahora, cuál es el coste final y es factible? Después baja PENALIZACION a 2 y observa qué ocurre con el exceso de la solución final. Explica el resultado.

Solución 1.

Con los 7 barrios el vecino más próximo da 39,5 km (Leganés, Carabanchel, Usera, Arganzuela, Retiro, Vallecas, Villaverde: recorre el mapa en sentido horario y vuelve por Villaverde), a solo 0,5 km del óptimo, y el ascenso por intercambio no consigue mejorarlo (0 pasos): es un óptimo local muy cercano al global. Con las 15 direcciones da 37,82 km y un solo paso de ascenso lo lleva a 36,45. Una buena solución inicial ahorra mucho trabajo (compara con los 51,8 km del inicio aleatorio), pero por sí sola no garantiza el óptimo: sigue haciendo falta la búsqueda local, y en general los reinicios o el recocido.

Solución 2.

Salida: intercambio: 1 de 20 inicios alcanzan 36.45 km frente a 2-opt: 15 de 20 inicios alcanzan 36.45 km. Invertir segmentos deshace cruces de la ruta, que es la fuente típica de óptimos locales malos en el viajante, y por eso 2-opt es el vecindario estándar en este problema.

Solución 3. Con {"Getafe": 30, "Zaragoza": 32} la ingenua tiene 8 cajas de exceso (399 penalizado). El ascenso mueve P008 (centro, 5 cajas) y después P015 (centro, 3 cajas) a Zaragoza, dejando 30 y 30 cajas: 263 €, factible, y de nuevo es el óptimo exacto (compruébalo con itertools.product). Con PENALIZACION = 2, mover P008 a Zaragoza cuesta 15 € más de envío pero solo ahorra 10 € de multa (5 cajas × 2 €), así que el algoritmo no mueve nada y devuelve la asignación ingenua (255 € penalizados, 239 € reales) con 8 cajas de exceso: la penalización es demasiado barata para representar una restricción que en la realidad es dura (el almacén simplemente no puede preparar más). Moraleja: la penalización debe superar el mayor ahorro que se pueda obtener violando la restricción.

Con esta lección hemos completado la caja de herramientas algorítmica del módulo. Hemos formulado los problemas de optimización con sus tres componentes (variables, objetivo, restricciones), hemos distinguido los métodos exactos de los aproximados, y hemos construido tres algoritmos de búsqueda local y metaheurísticas: el ascenso de colina, que sube hasta el primer óptimo local y se rescata con reinicios aleatorios; el recocido simulado, que acepta empeoramientos con una probabilidad que decrece con la temperatura para escapar de los valles; y el algoritmo genético, que hace evolucionar una población mediante torneo, cruce OX, mutación y elitismo. Los tres han resuelto el problema del viajante de la furgoneta de NovaMarket (39,0 km en 7 barrios, validado contra la fuerza bruta; 36,45 km en 15 direcciones, donde la fuerza bruta es imposible) sobre la matriz de distancias que Dijkstra nos dio en 03-02, y el mismo esqueleto ha resuelto la asignación de pedidos a Getafe y Zaragoza convirtiendo la capacidad en una penalización. Por último hemos visto que entrenar un modelo es optimizar, la idea que enlaza este módulo con los dos siguientes.

Con esto cerramos el módulo 3. Has recorrido el camino que va de la definición de algoritmo y la explosión combinatoria (03-01) a la búsqueda de caminos con BFS, DFS, coste uniforme y A* sobre GRAFO_CIUDAD (03-02), la decisión frente a un adversario con minimax y poda alfa-beta (03-03) y la optimización de soluciones completas con búsqueda local y metaheurísticas (03-04). El planificador de rutas y la asignación de pedidos de NovaMarket, que en 02-01 eran solo una formulación, ahora tienen código que funciona; en 09-01 volverás a ellos con más ejercicios. En el módulo 4, Aprendizaje Automático, cambiaremos de paradigma: en lugar de programar nosotros el algoritmo que resuelve el problema, daremos al sistema datos históricos (pedidos.csv, resenas.csv, incidencias.csv) para que aprenda por sí mismo la regla, y veremos que, por dentro, ese aprendizaje es una búsqueda del mejor modelo en un espacio enorme, con las mismas ideas de objetivo, óptimo local y validación que acabas de dominar. Marta y Diego pasarán de optimizar rutas a predecir la demanda y detectar el fraude.