El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Algorismes d'Optimització

Següent ►
►

Tanquem el mòdul amb el problema que el va obrir. A 03-01 vam calcular que l'ordre dels lliuraments d'una furgoneta té n! possibilitats i que la força bruta mor a partir d'una dotzena de parades; a 03-02 vam aprendre a trobar el millor camí entre dos punts, i a 03-03 a decidir davant d'un rival. Però cap d'aquestes tècniques no resol el problema complet d'en Diego: donats el mapa i els lliuraments del dia, en quin ordre els ha de visitar la furgoneta per recórrer els mínims quilòmetres possibles? És el cèlebre problema del viatjant, i és l'exemple perfecte d'un problema d'optimització: no cerquem un camí en un graf, sinó la millor d'entre un nombre astronòmic de solucions completes. En aquesta lliçó aprendrem a formular-lo (variables, funció objectiu, restriccions), distingirem mètodes exactes i aproximats, i construirem tres algorismes de cerca local i metaheurístiques que resolen el viatjant de NovaMarket en segons: ascens de turó, recuit simulat i algorismes genètics, validant-los contra la força bruta en mida petita. Després aplicarem la mateixa idea a l'assignació de comandes als magatzems de Zaragoza i Getafe amb una restricció de capacitat, i veurem com una restricció es converteix en una penalització. Acabarem amb la connexió que obre el mòdul 4: entrenar un model d'aprenentatge automàtic és, per dins, també un problema d'optimització.

Contingut

  1. Què és un problema d'optimització: variables, funció objectiu, restriccions
  2. Optimització exacta davant d'aproximada; cerca local
  3. Preparar el problema del viatjant de NovaMarket: la matriu de distàncies amb Dijkstra
  4. Força bruta com a referència (7 lliuraments)
  5. Ascens de turó per intercanvi de parades: òptims locals i reinicis aleatoris
  6. Un problema més gran: 15 adreces de lliurament
  7. Recuit simulat: la intuïció de la temperatura
  8. Algorismes genètics: població, torneig, encreuament, mutació i elitisme
  9. Segon exemple: assignació de comandes a dos magatzems amb capacitat (restriccions com a penalització)
  10. Taula comparativa de mètodes i quan fer servir cadascun
  11. Enllaç amb el mòdul 4: aprendre és optimitzar

  1. Què és un problema d'optimització

Un problema d'optimització té tres components:

Component Què és En el viatjant de la furgoneta En l'assignació a magatzems
Variables de decisió El que podem triar L'ordre de les parades (una permutació dels lliuraments) Per a cada comanda, si surt de Getafe o de Zaragoza
Funció objectiu El nombre que volem minimitzar (o maximitzar) Quilòmetres totals de la ruta tancada des del magatzem Cost total d'enviament
Restriccions Condicions que tota solució ha de complir Visitar cada lliurament exactament una vegada, sortir i tornar al magatzem No superar la capacitat de preparació de cada magatzem

Cada assignació concreta de valors a les variables és una solució candidata; les que compleixen les restriccions són factibles; la factible amb millor objectiu és l'òptima. La diferència amb la cerca de 03-02 és de perspectiva: allà l'objecte era un camí que es construïa pas a pas des de l'estat inicial, i el cost s'acumulava tram a tram; aquí treballem amb solucions completes que avaluem de cop amb la funció objectiu, i el "camí" que ens importa no és al mapa, sinó a l'espai de solucions. A 02-01 vam dir que un agent basat en utilitat tria l'acció que maximitza una funció; els algorismes d'aquesta lliçó són la maquinària per fer aquesta elecció quan les opcions són massa nombroses per llistar-les.

  1. Optimització exacta davant d'aproximada; cerca local

Enfocament Què garanteix Exemples Cost Quan
Exacte Troba l'òptim demostrable Força bruta, ramificació i poda, programació dinàmica, programació lineal (per a problemes amb estructura lineal) Exponencial en el pitjor cas per al viatjant i els seus parents Mida petita, o problemes amb estructura especial
Heurístic constructiu Una solució raonable, ràpida "Anar sempre a la parada més propera" (veí més proper) Molt baix Punt de partida; quan el temps és crític
Cerca local / metaheurístic Una solució bona, sense garantia d'òptim, amb possibilitat de millorar-la donant més temps Ascens de turó, recuit simulat, algorismes genètics, cerca tabú Ajustable L'opció per defecte en problemes grans del món real

La cerca local parteix d'una solució completa (bona o dolenta) i la millora pas a pas aplicant petits canvis, anomenats moviments; el conjunt de solucions assolibles amb un moviment des de l'actual és el seu veïnat. La metàfora habitual és un paisatge: cada solució és un punt, el seu objectiu és l'altura, i l'algorisme és un excursionista que vol arribar al punt més alt (o més baix, si minimitzem) movent-se només a punts veïns. Amb aquesta imatge s'entenen de seguida els tres algorismes de la lliçó: l'ascens de turó puja sempre i es queda encallat al primer cim; el recuit simulat es permet baixar de vegades per escapar; l'algorisme genètic envia molts excursionistes alhora i encreua les seves rutes.

Un apunt de vocabulari: encara que en el viatjant minimitzem quilòmetres, la literatura parla d'"ascens" de turó per costum; minimitzar f és maximitzar −f, així que la idea és la mateixa.

  1. Preparar el problema: la matriu de distàncies amb Dijkstra

A 03-01, la força bruta només acceptava trams entre barris connectats per una carretera directa. Ara ho podem fer bé: la distància entre dues parades qualssevol és la del camí més curt entre elles, que calculem amb la cerca de cost uniforme (Dijkstra) de 03-02, executada des de cada node. El resultat és una matriu de distàncies amb què el viatjant ja no depèn de la topologia del graf. Aquesta separació en dues capes (Dijkstra/A* per a "com anar d'A a B", optimització per a "en quin ordre visitar A, B, C…") és exactament com funcionen els planificadors de repartiment reals.

import heapq
import math
import random
import itertools

GRAF_CIUTAT = {
    "Almacen_Getafe": [("Leganes", 4.5), ("Villaverde", 5.0)],
    "Leganes":        [("Almacen_Getafe", 4.5), ("Carabanchel", 4.5), ("Villaverde", 6.5)],
    "Villaverde":     [("Almacen_Getafe", 5.0), ("Leganes", 6.5), ("Usera", 4.5), ("Vallecas", 7.5)],
    "Carabanchel":    [("Leganes", 4.5), ("Usera", 4.5), ("Arganzuela", 5.0)],
    "Usera":          [("Villaverde", 4.5), ("Carabanchel", 4.5), ("Arganzuela", 3.5), ("Vallecas", 5.5)],
    "Vallecas":       [("Villaverde", 7.5), ("Usera", 5.5), ("Retiro", 6.0)],
    "Arganzuela":     [("Carabanchel", 5.0), ("Usera", 3.5), ("Retiro", 4.0)],
    "Retiro":         [("Arganzuela", 4.0), ("Vallecas", 6.0)],
}

def distancies_des_de(graf, origen):
    """Dijkstra compacte: distancia minima des d'origen a TOTS els nodes (03-02)."""
    dist = {origen: 0.0}
    frontera = [(0.0, origen)]
    while frontera:
        g, node = heapq.heappop(frontera)
        if g > dist[node]:                 # entrada obsoleta del monticle
            continue
        for vei, d in graf[node]:
            nou = g + d
            if vei not in dist or nou < dist[vei]:
                dist[vei] = nou
                heapq.heappush(frontera, (nou, vei))
    return dist

MATRIU = {n: distancies_des_de(GRAF_CIUTAT, n) for n in GRAF_CIUTAT}
NODES = list(GRAF_CIUTAT)
LLIURAMENTS = [n for n in NODES if n != "Almacen_Getafe"]    # els 7 lliuraments d'avui

def longitud_ruta(ruta, dist, origen="Almacen_Getafe"):
    """Km de la ruta tancada: origen -> ruta[0] -> ... -> ruta[-1] -> origen."""
    total = dist[origen][ruta[0]] + dist[ruta[-1]][origen]
    for a, b in zip(ruta, ruta[1:]):
        total += dist[a][b]
    return total

MATRIU[a][b] és la distància mínima per carretera d'a a b; per exemple, MATRIU["Almacen_Getafe"]["Retiro"] val 17,0 (el resultat d'A* a 03-02) i MATRIU["Leganes"]["Vallecas"] val 14,0 encara que no hi hagi carretera directa. La matriu completa, en km:

Getafe Leganes Villaverde Carabanchel Usera Vallecas Arganzuela Retiro
Almacen_Getafe 0 4,5 5,0 9,0 9,5 12,5 13,0 17,0
Leganes 4,5 0 6,5 4,5 9,0 14,0 9,5 13,5
Villaverde 5,0 6,5 0 9,0 4,5 7,5 8,0 12,0
Carabanchel 9,0 4,5 9,0 0 4,5 10,0 5,0 9,0
Usera 9,5 9,0 4,5 4,5 0 5,5 3,5 7,5
Vallecas 12,5 14,0 7,5 10,0 5,5 0 9,0 6,0
Arganzuela 13,0 9,5 8,0 5,0 3,5 9,0 0 4,0
Retiro 17,0 13,5 12,0 9,0 7,5 6,0 4,0 0

La funció longitud_ruta és la nostra funció objectiu: rep una permutació dels lliuraments (la variable de decisió) i retorna els quilòmetres de la ruta tancada. La restricció "cada lliurament exactament una vegada" queda garantida per construcció, perquè només manejarem permutacions.

  1. Força bruta com a referència (7 lliuraments)

Amb 7 lliuraments hi ha 7! = 5.040 permutacions: la força bruta de 03-01, ara sobre la matriu, ens dona l'òptim exacte que servirà de vara de mesurar per als mètodes aproximats.

def forca_bruta(lliuraments, dist):
    millor, millor_km = None, math.inf
    for ordre in itertools.permutations(lliuraments):
        km = longitud_ruta(ordre, dist)
        if km < millor_km:
            millor, millor_km = list(ordre), km
    return millor, millor_km

optim, optim_km = forca_bruta(LLIURAMENTS, MATRIU)
print(optim_km, " -> ".join(optim))
39.0 Leganes -> Carabanchel -> Arganzuela -> Retiro -> Vallecas -> Usera -> Villaverde

L'òptim són 39,0 km (curiosament coincideix amb el que va trobar la versió restringida de 03-01: en aquest mapa la millor ruta ja feia servir només carreteres directes). Recorda que aquest nombre és inassolible per força bruta a partir d'uns 12-13 lliuraments.

  1. Ascens de turó per intercanvi de parades

Moviment: intercanviar dues parades de la ruta. Amb 7 parades hi ha 21 intercanvis possibles: aquest és el veïnat. Algorisme: mirar tots els veïns, moure's al millor si millora la ruta actual, i parar quan cap veí no millora (versió de "millor millora"; l'alternativa de "primera millora" es mou al primer veí que millori).

def veins_intercanvi(ruta):
    """Genera totes les rutes que resulten d'intercanviar dues parades."""
    for i in range(len(ruta)):
        for j in range(i + 1, len(ruta)):
            v = ruta[:]
            v[i], v[j] = v[j], v[i]
            yield v

def ascens_turo(ruta_inicial, dist, verbose=False):
    actual = ruta_inicial[:]
    km_actual = longitud_ruta(actual, dist)
    passos = 0
    while True:
        millor_vei, millor_km = None, km_actual
        for v in veins_intercanvi(actual):
            km = longitud_ruta(v, dist)
            if km < millor_km:
                millor_vei, millor_km = v, km
        if millor_vei is None:                 # cap vei no millora: optim local
            return actual, km_actual, passos
        actual, km_actual = millor_vei, millor_km
        passos += 1
        if verbose:
            print(f"  pas {passos}: {km_actual:.1f} km  {' -> '.join(actual)}")

random.seed(7)
inicial = LLIURAMENTS[:]
random.shuffle(inicial)
print("Inicial:", longitud_ruta(inicial, MATRIU), "km", " -> ".join(inicial))
ruta, km, passos = ascens_turo(inicial, MATRIU, verbose=True)
print("Final:", km, "km en", passos, "passos")
Inicial: 68.5 km Arganzuela -> Retiro -> Vallecas -> Leganes -> Usera -> Villaverde -> Carabanchel
  pas 1: 53.0 km  Arganzuela -> Retiro -> Vallecas -> Carabanchel -> Usera -> Villaverde -> Leganes
  pas 2: 47.5 km  Vallecas -> Retiro -> Arganzuela -> Carabanchel -> Usera -> Villaverde -> Leganes
Final: 47.5 km en 2 passos

En dos passos ha passat de 68,5 a 47,5 km, i allà s'ha aturat: cap dels 21 intercanvis no millora aquesta ruta, però l'òptim és 39,0. Hem arribat a un òptim local: un cim des del qual tot el que es veu al voltant és costa avall, encara que hi hagi muntanyes més altes més enllà. És el defecte estructural de l'ascens de turó, i té tres remeis clàssics:

  • Veïnats més rics (més moviments possibles: per exemple, invertir un segment de la ruta, el famós 2-opt, que farem servir a la secció 7).
  • Reinicis aleatoris: repetir l'ascens des de moltes solucions inicials diferents i quedar-se amb la millor. És simple, es paral·lelitza sense esforç i funciona sorprenentment bé.
  • Acceptar de vegades moviments que empitjoren, que és la idea del recuit simulat.
def ascens_amb_reinicis(lliuraments, dist, n_reinicis, llavor=0):
    rng = random.Random(llavor)
    millor, millor_km = None, math.inf
    for _ in range(n_reinicis):
        inicial = lliuraments[:]
        rng.shuffle(inicial)
        ruta, km, _ = ascens_turo(inicial, dist)
        if km < millor_km:
            millor, millor_km = ruta, km
    return millor, millor_km

ruta, km = ascens_amb_reinicis(LLIURAMENTS, MATRIU, n_reinicis=10)
print(km, " -> ".join(ruta))
39.0 Leganes -> Carabanchel -> Arganzuela -> Retiro -> Vallecas -> Usera -> Villaverde

Amb 10 reinicis assoleix l'òptim de la força bruta. Si repeteixes l'experiment amb 20 inicis diferents veuràs que uns 8 de cada 20 acaben en 39,0, uns altres tants en 39,5 i la resta en òptims locals pitjors (46-47,5 km): la probabilitat d'encertar amb un sol intent és d'un 40 %, però amb 10 intents independents és de més del 99 %. I el cost total ha estat 10 × (uns pocs passos × 21 avaluacions): unes 500 avaluacions davant de les 5.040 de la força bruta. Amb 7 parades la diferència és anecdòtica; amb 30 és la diferència entre segons i segles.

  1. Un problema més gran: 15 adreces de lliurament

Perquè les metaheurístiques tinguin alguna cosa on mossegar, generem una instància més gran: 15 adreces concretes de clients repartides al voltant dels barris de COORDENADES (03-02), amb la distància en línia recta com a aproximació de la distància real (en producció faríem servir la matriu Dijkstra sobre el nomenclàtor, exactament com a la secció 3; l'algorisme d'optimització no nota la diferència perquè només consulta dist[a][b]).

COORDENADES = {
    "Almacen_Getafe": (0, 0), "Leganes": (-3, 3), "Villaverde": (3, 3), "Carabanchel": (-2, 7),
    "Usera": (2, 7), "Vallecas": (7, 8), "Arganzuela": (1, 10), "Retiro": (4, 12),
}

def generar_adreces(n, llavor=42):
    """n adreces ficticies de lliurament: cadascuna a prop d'un barri triat a l'atzar."""
    rng = random.Random(llavor)
    barris = [b for b in COORDENADES if b != "Almacen_Getafe"]
    adreces = {}
    for i in range(1, n + 1):
        barri = rng.choice(barris)
        x, y = COORDENADES[barri]
        adreces[f"E{i:02d}_{barri[:4]}"] = (x + rng.uniform(-1.5, 1.5), y + rng.uniform(-1.5, 1.5))
    return adreces

ADRECES = generar_adreces(15)
PUNTS = {"Almacen_Getafe": (0, 0), **ADRECES}

def euclidiana(a, b):
    (x1, y1), (x2, y2) = PUNTS[a], PUNTS[b]
    return math.hypot(x2 - x1, y2 - y1)

DIST15 = {a: {b: euclidiana(a, b) for b in PUNTS} for a in PUNTS}
LLIURAMENTS15 = list(ADRECES)

rng = random.Random(1)
inicial15 = LLIURAMENTS15[:]
rng.shuffle(inicial15)
print("Inicial:", round(longitud_ruta(inicial15, DIST15), 1), "km")
ruta, km, passos = ascens_turo(inicial15, DIST15)
print("Ascens de turo:", round(km, 1), "km en", passos, "passos")
for n in [1, 10, 50]:
    ruta, km = ascens_amb_reinicis(LLIURAMENTS15, DIST15, n_reinicis=n)
    print(f"Amb {n:2d} reinicis: {km:.2f} km")
Inicial: 97.6 km
Ascens de turo: 51.8 km en 7 passos
Amb  1 reinicis: 43.79 km
Amb 10 reinicis: 36.45 km
Amb 50 reinicis: 36.45 km

Els noms de les adreces porten el prefix del barri (E04_Vall és el quart lliurament, a prop de Vallecas). Amb 15 parades la força bruta necessitaria 15! ≈ 1,3 bilions d'avaluacions; l'ascens de turó simple s'encalla en 51,8 km, i amb reinicis arriba a 36,45 km, que és (com confirmaran els altres dos mètodes) el millor valor conegut per a aquesta instància. Guarda aquesta xifra com a referència.

  1. Recuit simulat: la intuïció de la temperatura

El recuit simulat (simulated annealing) pren el nom de la metal·lúrgia: un metall escalfat i refredat lentament cristal·litza en una estructura de mínima energia, mentre que refredat de cop queda ple de defectes. Traduït a cerca local:

  • A cada iteració es genera un veí a l'atzar (no tots).
  • Si millora, s'accepta sempre.
  • Si empitjora en una quantitat Δ, s'accepta amb probabilitat e^(−Δ/T), on T és la temperatura. Amb T alta gairebé tot s'accepta (exploració lliure, se salta entre valls); amb T baixa gairebé res que empitjori no s'accepta (l'algorisme es comporta com un ascens de turó i afina la solució).
  • T comença alta i es redueix a poc a poc (refredament), per exemple multiplicant-la per 0,995 a cada iteració.

Uns nombres per fixar la intuïció (probabilitat d'acceptar un empitjorament de Δ km a temperatura T):

Δ (km pitjor) T = 10 T = 1 T = 0,1
0,5 0,95 0,61 0,007
2 0,82 0,14 ≈ 0
5 0,61 0,007 ≈ 0

Al principi accepta gairebé qualsevol cosa; al final, pràcticament només millores. Com a moviment farem servir el 2-opt: triar dues posicions i invertir el segment entre elles, que en rutes és més eficaç que l'intercanvi simple perquè desfà encreuaments.

def recuit_simulat(ruta_inicial, dist, T0=10.0, refredament=0.995, T_min=0.01, llavor=0):
    rng = random.Random(llavor)
    actual = ruta_inicial[:]
    km_actual = longitud_ruta(actual, dist)
    millor, millor_km = actual[:], km_actual
    T = T0
    iteracions = acceptats_pitjors = 0
    while T > T_min:
        i, j = sorted(rng.sample(range(len(actual)), 2))
        vei = actual[:]
        vei[i:j + 1] = reversed(vei[i:j + 1])               # moviment 2-opt: invertir un segment
        km_vei = longitud_ruta(vei, dist)
        delta = km_vei - km_actual
        if delta < 0 or rng.random() < math.exp(-delta / T): # millora: sempre; empitjora: de vegades
            if delta > 0:
                acceptats_pitjors += 1
            actual, km_actual = vei, km_vei
            if km_actual < millor_km:                         # recordem la millor vista
                millor, millor_km = actual[:], km_actual
        T *= refredament
        iteracions += 1
    return millor, millor_km, iteracions, acceptats_pitjors

ruta, km, iteracions, pitjors = recuit_simulat(inicial15, DIST15)
print(f"Recuit: {km:.2f} km en {iteracions} iteracions ({pitjors} moviments a pitjor acceptats)")
for llavor in range(5):
    ruta, km, _, pitjors = recuit_simulat(inicial15, DIST15, llavor=llavor)
    print(f"  llavor {llavor}: {km:.2f} km, {pitjors} empitjoraments acceptats")
Recuit: 36.45 km en 1379 iteracions (117 moviments a pitjor acceptats)
  llavor 0: 36.45 km, 117 empitjoraments acceptats
  llavor 1: 36.84 km, 101 empitjoraments acceptats
  llavor 2: 36.45 km, 101 empitjoraments acceptats
  llavor 3: 36.84 km, 105 empitjoraments acceptats
  llavor 4: 36.45 km, 88 empitjoraments acceptats

Des de la mateixa ruta inicial de 97,6 km en què l'ascens de turó es va quedar en 51,8, el recuit arriba a 36,45 km (o a 36,84, un 1 % pitjor) en unes 1.400 avaluacions, acceptant pel camí un centenar de moviments que empitjoraven: aquests "passos enrere" són els que li permeten sortir de les valls. Tres detalls del codi mereixen atenció: es desa a part la millor solució vista (l'actual pot empitjorar al final de la fase calenta); la temperatura es multiplica a cada iteració (refredament geomètric, el més habitual); i el nombre d'iteracions el fixa el ritme de refredament (de 10 a 0,01 a raó de 0,995 són unes 1.380 iteracions). Refredar més a poc a poc (0,999) millora la qualitat a canvi de més temps; és el comandament que la Marta ajustarà segons els segons disponibles abans de les 8 del matí.

  1. Algorismes genètics

Els algorismes genètics s'inspiren en l'evolució: en lloc d'una solució que es mou, mantenen una població de solucions que es reprodueix; les millors tenen més descendència, els fills combinen trossos dels seus pares i de tant en tant pateixen mutacions. Vocabulari i cicle:

flowchart TD
    A[Població inicial aleatòria<br/>N rutes] --> B[Avaluació: km de cada ruta<br/>aptitud = -km]
    B --> C{Fi?<br/>generacions esgotades}
    C -- No --> D[Selecció per torneig:<br/>triar k a l'atzar, guanya el millor]
    D --> E[Encreuament OX:<br/>copiar un segment del pare 1<br/>i omplir en l'ordre del pare 2]
    E --> F[Mutació:<br/>amb prob. p, intercanviar dues parades]
    F --> G[Elitisme:<br/>els e millors passen intactes]
    G --> B
    C -- Sí --> H[Retornar la millor ruta]
  • Individu / cromosoma: una solució (una ruta); els seus gens són les parades.
  • Aptitud (fitness): l'objectiu (menys km, més apte).
  • Selecció per torneig: es prenen k individus a l'atzar i guanya el millor; els bons es reprodueixen més, però els dolents també tenen alguna opció, cosa que preserva diversitat.
  • Encreuament: combinar dos pares. En permutacions no val copiar meitats (es repetirien parades); l'encreuament d'ordre (OX) copia un segment del pare 1 i omple les posicions restants amb les parades que falten en l'ordre en què apareixen al pare 2.
  • Mutació: canvi aleatori petit (intercanviar dues parades), que introdueix novetat i impedeix que la població es torni idèntica.
  • Elitisme: els millors individus passen sense canvis a la generació següent, per no perdre mai la millor solució trobada.
def torneig(poblacio, dist, rng, k=3):
    candidats = rng.sample(poblacio, k)
    return min(candidats, key=lambda r: longitud_ruta(r, dist))

def encreuament_ox(pare1, pare2, rng):
    n = len(pare1)
    i, j = sorted(rng.sample(range(n), 2))
    fill = [None] * n
    fill[i:j + 1] = pare1[i:j + 1]                         # segment heretat del pare 1
    restants = [g for g in pare2 if g not in fill]         # el que falta, en l'ordre del pare 2
    forats = [k for k in range(n) if fill[k] is None]
    for k, g in zip(forats, restants):
        fill[k] = g
    return fill

def mutacio_intercanvi(ruta, rng, prob):
    if rng.random() < prob:
        i, j = rng.sample(range(len(ruta)), 2)
        ruta[i], ruta[j] = ruta[j], ruta[i]
    return ruta

def algorisme_genetic(lliuraments, dist, mida_poblacio=60, generacions=200,
                      elitisme=2, prob_mutacio=0.2, llavor=0, verbose=False):
    rng = random.Random(llavor)
    poblacio = []
    for _ in range(mida_poblacio):
        r = lliuraments[:]
        rng.shuffle(r)
        poblacio.append(r)
    historial = []
    for gen in range(generacions):
        poblacio.sort(key=lambda r: longitud_ruta(r, dist))      # millor primer
        millor_km = longitud_ruta(poblacio[0], dist)
        historial.append(millor_km)
        if verbose and gen % 25 == 0:
            mitjana = sum(longitud_ruta(r, dist) for r in poblacio) / len(poblacio)
            print(f"  gen {gen:3d}: millor {millor_km:.2f} km, mitjana {mitjana:.2f} km")
        nova = [r[:] for r in poblacio[:elitisme]]                # elitisme
        while len(nova) < mida_poblacio:
            p1, p2 = torneig(poblacio, dist, rng), torneig(poblacio, dist, rng)
            fill = encreuament_ox(p1, p2, rng)
            fill = mutacio_intercanvi(fill, rng, prob_mutacio)
            nova.append(fill)
        poblacio = nova
    poblacio.sort(key=lambda r: longitud_ruta(r, dist))
    return poblacio[0], longitud_ruta(poblacio[0], dist), historial

ruta, km, historial = algorisme_genetic(LLIURAMENTS15, DIST15, verbose=True)
print(f"Genetic: {km:.2f} km (millor assolit a la generacio {historial.index(min(historial))})")
print(" -> ".join(ruta))
  gen   0: millor 79.70 km, mitjana 99.49 km
  gen  25: millor 36.45 km, mitjana 39.24 km
  gen  50: millor 36.45 km, mitjana 39.69 km
  gen  75: millor 36.45 km, mitjana 40.86 km
  gen 100: millor 36.45 km, mitjana 39.18 km
  gen 125: millor 36.45 km, mitjana 41.31 km
  gen 150: millor 36.45 km, mitjana 39.64 km
  gen 175: millor 36.45 km, mitjana 37.70 km
Genetic: 36.45 km (millor assolit a la generacio 18)
E05_Vill -> E02_Vill -> E04_Vall -> E07_Vall -> E15_Vall -> E06_Vall -> E09_Reti -> E13_Reti -> E03_Arga -> E01_Arga -> E10_Cara -> E11_Cara -> E12_Cara -> E08_Cara -> E14_Lega

La població comença amb una mitjana de gairebé 100 km i en 18 generacions (unes 1.000 avaluacions) el seu millor individu ja és a 36,45 km. La ruta final té tot el sentit geogràfic: surt cap a Villaverde, recorre Vallecas, puja a Retiro i Arganzuela, baixa per Carabanchel i torna per Leganés. Un exemple de l'encreuament OX perquè en vegis la mecànica: amb pares A B C D E F G i G F E D C B A, si el segment triat són les posicions 1-2, el fill hereta _ B C _ _ _ _ del primer i omple amb G F E D A (l'ordre del segon, saltant B i C): G B C F E D A. Cap parada no es repeteix ni es perd.

Dues advertències honestes: els algorismes genètics són sensibles als seus paràmetres i estocàstics. Amb altres llavors, la mateixa configuració acaba en 41,3, 43,4, 43,8 o 46,1 km: la població convergeix prematurament (tots els individus s'assemblen i l'encreuament ja no aporta res). Pujar la probabilitat de mutació a 0,5 i la població a 150 fa que 4 de cada 5 execucions assoleixin 36,45. Comparat amb el recuit, aquí el genètic necessita més avaluacions per al mateix resultat; el seu avantatge apareix en problemes on no hi ha un moviment local natural, on l'avaluació és paral·lelitzable, o on interessa obtenir diverses solucions bones i diferents.

  1. Segon exemple: assignació de comandes a dos magatzems amb capacitat

Canviem de problema però no de mètode. Cada matí en Diego ha de decidir quines comandes es preparen a Getafe i quines a Zaragoza (cas 6). Cada comanda té un cost d'enviament diferent segons el magatzem (per la zona de destinació) i un volum en caixes; cada magatzem té una capacitat diària de preparació en caixes. Formulació:

  • Variables: per a cada comanda, "Getafe" o "Zaragoza" (una llista de 20 etiquetes; 2²⁰ ≈ 1 milió de solucions).
  • Objectiu: minimitzar el cost total d'enviament.
  • Restricció: la suma de caixes assignades a cada magatzem no pot superar la seva capacitat.

La manera més habitual de tractar una restricció en cerca local és convertir-la en penalització: sumar a l'objectiu un cost artificial proporcional a la violació (aquí, 20 € per cada caixa d'excés). Així totes les solucions són "avaluables", les infactibles simplement surten molt cares, i l'algorisme aprèn a evitar-les.

def generar_comandes(n, llavor=11):
    rng = random.Random(llavor)
    comandes = []
    tarifa = {"centre": (4, 7), "sud": (3, 9), "nord-est": (9, 4), "llevant": (8, 5)}   # €/caixa (Getafe, Zaragoza)
    for i in range(1, n + 1):
        zona = rng.choice(list(tarifa))
        caixes = rng.choice([1, 1, 2, 3, 5])
        comandes.append({"id": f"P{i:03d}", "zona": zona, "caixes": caixes,
                         "cost_getafe": tarifa[zona][0] * caixes,
                         "cost_zaragoza": tarifa[zona][1] * caixes})
    return comandes

COMANDES = generar_comandes(20)                     # 60 caixes en total
CAPACITAT = {"Getafe": 32, "Zaragoza": 30}
PENALITZACIO = 20                                   # € per caixa d'exces

def cost_assignacio(assignacio, comandes, capacitat, penalitzacio=PENALITZACIO):
    """Retorna (cost penalitzat, cost real, carrega per magatzem, caixes d'exces)."""
    cost = 0
    carrega = {"Getafe": 0, "Zaragoza": 0}
    for c, magatzem in zip(comandes, assignacio):
        cost += c["cost_getafe"] if magatzem == "Getafe" else c["cost_zaragoza"]
        carrega[magatzem] += c["caixes"]
    exces = sum(max(0, carrega[a] - capacitat[a]) for a in carrega)
    return cost + penalitzacio * exces, cost, carrega, exces

# Solucio ingenua: cada comanda al magatzem mes barat, sense mirar la capacitat
ingenua = ["Getafe" if c["cost_getafe"] <= c["cost_zaragoza"] else "Zaragoza" for c in COMANDES]
print("Ingenua:", cost_assignacio(ingenua, COMANDES, CAPACITAT))

def veins_assignacio(assignacio):
    """Veins: canviar UNA comanda de magatzem."""
    for i in range(len(assignacio)):
        v = assignacio[:]
        v[i] = "Zaragoza" if v[i] == "Getafe" else "Getafe"
        yield v

def ascens_assignacio(assignacio, comandes, capacitat):
    actual = assignacio[:]
    f_actual = cost_assignacio(actual, comandes, capacitat)[0]
    while True:
        millor, f_millor = None, f_actual
        for v in veins_assignacio(actual):
            f = cost_assignacio(v, comandes, capacitat)[0]
            if f < f_millor:
                millor, f_millor = v, f
        if millor is None:
            return actual, f_actual
        canviat = [i for i in range(len(actual)) if actual[i] != millor[i]][0]
        actual, f_actual = millor, f_millor
        print(f"  moc {comandes[canviat]['id']} ({comandes[canviat]['zona']}, "
              f"{comandes[canviat]['caixes']} caixes) a {actual[canviat]} -> "
              f"{cost_assignacio(actual, comandes, capacitat)}")

final, f = ascens_assignacio(ingenua, COMANDES, CAPACITAT)
print("Final:", cost_assignacio(final, COMANDES, CAPACITAT))
Ingenua: (359, 239, {'Getafe': 38, 'Zaragoza': 22}, 6)
  moc P008 (centre, 5 caixes) a Zaragoza -> (274, 254, {'Getafe': 33, 'Zaragoza': 27}, 1)
  moc P012 (centre, 1 caixes) a Zaragoza -> (257, 257, {'Getafe': 32, 'Zaragoza': 28}, 0)
Final: (257, 257, {'Getafe': 32, 'Zaragoza': 28}, 0)

L'assignació ingènua és la més barata sobre el paper (239 €), però carrega 38 caixes a Getafe, 6 per sobre de la seva capacitat: penalitzada, costa 359. L'ascens de turó mou a Zaragoza dues comandes de la zona centre (les que menys perden en canviar de magatzem: 15 € i 3 € més) i arriba a una assignació factible de 257 €. Com que aquí l'espai té "només" 2²⁰ solucions, podem comprovar per enumeració completa que 257 € és l'òptim exacte; amb 200 comandes (2²⁰⁰) aquesta comprovació seria impossible i la cerca local seria l'única opció.

Dues lliçons d'aquest exemple: la penalització ha de ser prou alta perquè cap solució infactible no surti a compte (amb 20 €/caixa funciona; amb 2 €/caixa l'algorisme preferiria pagar la multa), però no tan alta que aixafi les diferències de cost real i converteixi el paisatge en un altiplà; i el mateix esquelet de cerca local serveix per a problemes de naturalesa diferent canviant només la representació, el veïnat i la funció objectiu.

  1. Taula comparativa de mètodes

Mètode Tipus Garantia d'òptim Cost computacional Paràmetres Quan fer-lo servir
Força bruta Exacte Sí n! o 2ⁿ: només mides minúscules Cap Validar altres mètodes; problemes de joguina
Ramificació i poda, programació dinàmica, programació lineal Exacte Sí (si el problema té l'estructura adequada) Exponencial en el pitjor cas; molt eficaç en molts casos reals Pocs Quan existeix un solver adequat (assignació, flux, planificació lineal)
Veí més proper i altres constructius Heurístic No; típicament un 20-25 % pitjor que l'òptim en el viatjant Molt baix (n²) Cap Solució d'arrencada; resposta instantània
Ascens de turó (+ reinicis) Cerca local No; òptim local Baix per reinici, escalable Veïnat, nre. de reinicis Primera opció: simple i sovint suficient
Recuit simulat Metaheurístic No, però convergeix a l'òptim amb refredament infinitament lent Mitjà, controlable T₀, ritme de refredament Espais amb molts òptims locals; una sola solució bona
Algorisme genètic Metaheurístic No Mitjà-alt (població × generacions), paral·lelitzable Població, torneig, encreuament, mutació, elitisme Sense moviment local natural; diverses solucions diverses; avaluació paral·lela

La regla de decisió de la Marta: si el problema és petit o té estructura coneguda, exacte (i hi ha solvers de programació lineal excel·lents, encara que queden fora d'aquest curs); si no, ascens de turó amb reinicis com a base, recuit simulat quan s'encalla, i genètic quan la representació ho demana. I sempre validar en petit contra la força bruta, com hem fet.

  1. Enllaç amb el mòdul 4: aprendre és optimitzar

Tanquem amb la connexió més important de la lliçó. Recorda aprendre_llindar de 01-02: cercava el llindar que millor separava dues classes provant valors. Això ja era optimització: variable (el llindar), objectiu (encerts), mètode (força bruta sobre una graella). Tot entrenament d'un model d'aprenentatge automàtic és un problema d'optimització: les variables són els paràmetres del model (uns pocs en una regressió, milers de milions en un gran model de llenguatge), la funció objectiu és una mesura d'error sobre les dades d'entrenament (la "funció de pèrdua"), i les restriccions o penalitzacions són les tècniques de regularització de 04-06. La diferència amb aquesta lliçó és que, quan els paràmetres són nombres continus i la funció de pèrdua és suau, no cal provar veïns a l'atzar: es pot calcular en quina direcció descendeix la pèrdua (el seu gradient) i fer un pas en aquesta direcció, una vegada i una altra. Aquest mètode, el descens del gradient, és l'"ascens de turó amb brúixola" que fa funcionar les xarxes neuronals, i l'estudiarem a 05-03. Tot el que has après avui sobre òptims locals, mida de pas (aquí, temperatura i veïnat) i validació et servirà tal qual allà.

Errors Comuns i Consells

  • Confondre l'òptim local amb el global: un ascens de turó que "no millora més" no ha acabat, s'ha encallat. Reinicia, canvia el veïnat o fes servir recuit abans de donar la solució per bona.
  • No validar en petit: abans de confiar en una metaheurística per a 40 parades, comprova que en 7 o 8 troba el mateix òptim que la força bruta. Un error a la funció objectiu (per exemple, oblidar el tram de tornada al magatzem) passa desapercebut sense aquesta comprovació.
  • Llavors i reproduïbilitat: els mètodes d'aquesta lliçó són estocàstics. Fixa la llavor (random.Random(llavor)) per poder reproduir resultats i depurar, i avalua sempre diverses llavors abans de treure conclusions sobre un paràmetre.
  • Refredar massa ràpid en el recuit converteix l'algorisme en un ascens de turó car; refredar massa lent malbarata temps. Comença amb T₀ de l'ordre d'un empitjorament "gran" típic i ajusta mirant quants moviments a pitjor s'accepten.
  • Encreuament que trenca la representació: en permutacions, un encreuament ingenu produeix rutes amb parades repetides o absents. Fes servir OX o un altre operador que preservi permutacions i comprova després de cada encreuament que sorted(fill) == sorted(pare1).
  • Penalització mal calibrada: massa baixa i la solució "òptima" viola la restricció; massa alta i l'algorisme no distingeix entre solucions factibles. Comprova sempre exces == 0 a la solució final.
  • Oblidar desar la millor solució vista en el recuit: la solució actual pot empitjorar en acceptar moviments a pitjor; retorna sempre millor, no actual.
  • Optimitzar l'objectiu equivocat: com va avisar 02-01, si el cost només mesura quilòmetres, la ruta òptima pot incomplir totes les franges horàries. Afegeix a l'objectiu (o com a penalització) tot el que importi.

Exercicis

Exercici 1: veí més proper com a punt de partida

Implementa l'heurística constructiva del veí més proper: partint del magatzem, anar sempre al lliurament pendent més proper. Aplica-la a LLIURAMENTS amb MATRIU i a LLIURAMENTS15 amb DIST15, compara amb els òptims coneguts (39,0 i 36,45 km) i fes-la servir com a ruta inicial de l'ascens de turó. Millora el resultat respecte d'un inici aleatori?

Exercici 2: 2-opt a l'ascens de turó

Escriu veins_2opt(ruta) que generi totes les rutes obtingudes en invertir un segment ruta[i:j+1] i fes-lo servir en lloc de veins_intercanvi dins d'ascens_turo (parametritza la funció de veïnat). Compara, per a 20 inicis aleatoris sobre LLIURAMENTS15, quantes vegades assoleix 36,45 km cada veïnat.

Exercici 3: capacitat més ajustada a l'assignació

Canvia CAPACITAT a {"Getafe": 30, "Zaragoza": 32} i torna a executar ascens_assignacio des de la solució ingènua. Quines comandes es mouen ara, quin és el cost final i és factible? Després baixa PENALITZACIO a 2 i observa què passa amb l'excés de la solució final. Explica el resultat.

Solucions

Solució 1.

def vei_mes_proper(lliuraments, dist, origen="Almacen_Getafe"):
    pendents = set(lliuraments)
    ruta, actual = [], origen
    while pendents:
        seguent = min(pendents, key=lambda e: dist[actual][e])
        ruta.append(seguent)
        pendents.remove(seguent)
        actual = seguent
    return ruta

for lliuraments, dist, nom in [(LLIURAMENTS, MATRIU, "7 barris"), (LLIURAMENTS15, DIST15, "15 adreces")]:
    r = vei_mes_proper(lliuraments, dist)
    km = longitud_ruta(r, dist)
    r2, km2, passos = ascens_turo(r, dist)
    print(f"{nom}: vei mes proper {km:.2f} km -> despres de l'ascens {km2:.2f} km ({passos} passos)")

Amb els 7 barris el veí més proper dona 39,5 km (Leganés, Carabanchel, Usera, Arganzuela, Retiro, Vallecas, Villaverde: recorre el mapa en sentit horari i torna per Villaverde), a només 0,5 km de l'òptim, i l'ascens per intercanvi no aconsegueix millorar-lo (0 passos): és un òptim local molt proper al global. Amb les 15 adreces dona 37,82 km i un sol pas d'ascens el porta a 36,45. Una bona solució inicial estalvia molta feina (compara amb els 51,8 km de l'inici aleatori), però per si sola no garanteix l'òptim: continua fent falta la cerca local, i en general els reinicis o el recuit.

Solució 2.

def veins_2opt(ruta):
    for i in range(len(ruta)):
        for j in range(i + 1, len(ruta)):
            v = ruta[:]
            v[i:j + 1] = reversed(v[i:j + 1])
            yield v

def ascens_turo_generic(ruta_inicial, dist, veinat):
    actual, km_actual = ruta_inicial[:], longitud_ruta(ruta_inicial, dist)
    while True:
        millor, millor_km = None, km_actual
        for v in veinat(actual):
            km = longitud_ruta(v, dist)
            if km < millor_km:
                millor, millor_km = v, km
        if millor is None:
            return actual, km_actual
        actual, km_actual = millor, millor_km

for nom, veinat in [("intercanvi", veins_intercanvi), ("2-opt", veins_2opt)]:
    rng = random.Random(0)
    encerts = 0
    for _ in range(20):
        ini = LLIURAMENTS15[:]
        rng.shuffle(ini)
        _, km = ascens_turo_generic(ini, DIST15, veinat)
        encerts += round(km, 2) == 36.45
    print(f"{nom}: {encerts} de 20 inicis assoleixen 36.45 km")

Sortida: intercanvi: 1 de 20 inicis assoleixen 36.45 km davant de 2-opt: 15 de 20 inicis assoleixen 36.45 km. Invertir segments desfà encreuaments de la ruta, que és la font típica d'òptims locals dolents en el viatjant, i per això 2-opt és el veïnat estàndard en aquest problema.

Solució 3. Amb {"Getafe": 30, "Zaragoza": 32} la ingènua té 8 caixes d'excés (399 penalitzat). L'ascens mou P008 (centre, 5 caixes) i després P015 (centre, 3 caixes) a Zaragoza, deixant 30 i 30 caixes: 263 €, factible, i de nou és l'òptim exacte (comprova-ho amb itertools.product). Amb PENALITZACIO = 2, moure P008 a Zaragoza costa 15 € més d'enviament però només estalvia 10 € de multa (5 caixes × 2 €), així que l'algorisme no mou res i retorna l'assignació ingènua (255 € penalitzats, 239 € reals) amb 8 caixes d'excés: la penalització és massa barata per representar una restricció que en la realitat és dura (el magatzem simplement no pot preparar més). Moralitat: la penalització ha de superar el màxim estalvi que es pugui obtenir violant la restricció.

Conclusió

Amb aquesta lliçó hem completat la caixa d'eines algorísmica del mòdul. Hem formulat els problemes d'optimització amb els seus tres components (variables, objectiu, restriccions), hem distingit els mètodes exactes dels aproximats, i hem construït tres algorismes de cerca local i metaheurístiques: l'ascens de turó, que puja fins al primer òptim local i es rescata amb reinicis aleatoris; el recuit simulat, que accepta empitjoraments amb una probabilitat que decreix amb la temperatura per escapar de les valls; i l'algorisme genètic, que fa evolucionar una població mitjançant torneig, encreuament OX, mutació i elitisme. Els tres han resolt el problema del viatjant de la furgoneta de NovaMarket (39,0 km en 7 barris, validat contra la força bruta; 36,45 km en 15 adreces, on la força bruta és impossible) sobre la matriu de distàncies que Dijkstra ens va donar a 03-02, i el mateix esquelet ha resolt l'assignació de comandes a Getafe i Zaragoza convertint la capacitat en una penalització. Finalment hem vist que entrenar un model és optimitzar, la idea que enllaça aquest mòdul amb els dos següents.

Amb això tanquem el mòdul 3. Has recorregut el camí que va de la definició d'algorisme i l'explosió combinatòria (03-01) a la cerca de camins amb BFS, DFS, cost uniforme i A* sobre GRAF_CIUTAT (03-02), la decisió davant d'un adversari amb minimax i poda alfa-beta (03-03) i l'optimització de solucions completes amb cerca local i metaheurístiques (03-04). El planificador de rutes i l'assignació de comandes de NovaMarket, que a 02-01 eren només una formulació, ara tenen codi que funciona; a 09-01 hi tornaràs amb més exercicis. Al mòdul 4, Aprenentatge Automàtic, canviarem de paradigma: en lloc de programar nosaltres l'algorisme que resol el problema, donarem al sistema dades històriques (comandes.csv, ressenyes.csv, incidencies.csv) perquè aprengui pel seu compte la regla, i veurem que, per dins, aquest aprenentatge és una cerca del millor model en un espai enorme, amb les mateixes idees d'objectiu, òptim local i validació que acabes de dominar. La Marta i en Diego passaran d'optimitzar rutes a predir la demanda i detectar el frau.

◄ Anterior
◄
Següent ►
►

Fonaments d'Intel·ligència Artificial (IA)

Mòdul 1: Introducció a la Intel·ligència Artificial

Mòdul 2: Principis Bàsics de la IA

Mòdul 3: Algorismes en IA

Mòdul 4: Aprenentatge Automàtic (Machine Learning)

Mòdul 5: Xarxes Neuronals i Deep Learning

Mòdul 6: Lògica i Sistemes Experts

Mòdul 7: Eines i Llenguatges de Programació en IA

Mòdul 8: Projectes i Casos d'Estudi

Mòdul 9: Exercicis i Pràctiques

Mòdul 10: Recursos Addicionals

El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2026. Tots els drets reservats