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

Algorismes Genètics

Següent ►
►

El branch and bound ens va portar a l'òptim del TSP de Rutalia expandint mil nodes en lloc d'un milió — però vam tancar la lliçó admetent que l'explosió combinatòria només estava retardada: amb les 60-120 parades d'una furgoneta real, cap mètode exacte no acaba a temps. Aquesta lliçó creua la frontera de manera deliberada: els algorismes genètics (AG) renuncien a la garantia d'optimalitat i, a canvi, produeixen solucions molt bones en temps controlat, per a gairebé qualsevol problema que sàpigues avaluar. Veurem l'esquema evolutiu complet — codificació, població, fitness, selecció, encreuament, mutació, elitisme — i l'implementarem sencer en Python sobre la mateixa instància de 10 punts de 02-02/02-03, per poder comparar contra l'òptim conegut de 35,22 km. Acabarem amb una guia d'hiperparàmetres i un cop d'ull breu a les metaheurístiques "cosines" (recuita simulada, cerca tabú).

Contingut

  1. Exactes vs heurístics: què sacrifiquem i què guanyem
  2. La metàfora evolutiva
  3. Representació: cromosomes binaris i permutacions
  4. Funció de fitness
  5. Selecció: torneig i ruleta
  6. Encreuament: un punt i order crossover (OX)
  7. Mutació, elitisme i criteris de parada
  8. Implementació completa: AG per al TSP de Rutalia
  9. Hiperparàmetres: què tocar i què esperar
  10. Les cosines de veïnatge: recuita simulada i cerca tabú

Exactes vs heurístics: què sacrifiquem i què guanyem

Exactes (02-03) Metaheurístiques (02-04, 02-05)
Resultat Òptim certificat Solució bona, sense certificat
Temps Impredictible (exponencial en el pitjor cas) Controlat: tu decideixes quantes iteracions
Escala TSP: desenes de nodes (centenars amb fites fines) Milers de nodes i problemes "bruts"
Requisits Estructura explotable (fites, relaxacions) Només saber avaluar una solució
Reproduïbilitat Determinista Estocàstica: cada execució pot diferir

La paraula clau és certificat. Un AG pot donar-te la ruta òptima — de fet, en la nostra instància petita ho farà — però no t'ho pot dir: no produeix fites que demostrin que no existeix res millor. Per a Rutalia el tracte sol compensar: entre "la ruta òptima d'aquí a tres setmanes" i "una ruta un 2 % pitjor d'aquí a un minut", operacions tria el segon cada dia. La disciplina professional consisteix a saber quan estàs fent aquest tracte i a mesurar la qualitat contra fites o instàncies amb òptim conegut — exactament el que farem aquí.

La metàfora evolutiva

Un AG manté una població de solucions candidates i la fa evolucionar imitant la selecció natural:

flowchart LR
    A["Població inicial<br/>(aleatòria)"] --> B["Avaluar el fitness<br/>de cada individu"]
    B --> C["Seleccionar pares<br/>(els millors tenen avantatge)"]
    C --> D["Encreuament:<br/>combinar dos pares"]
    D --> E["Mutació:<br/>alterar a l'atzar"]
    E --> F["Nova generació<br/>(+ elitisme)"]
    F --> B
    B -->|"criteri de parada"| G["Millor individu<br/>trobat"]

La intuïció de per què funciona: la selecció concentra la població en zones bones de l'espai de solucions (explotació), l'encreuament combina fragments bons de pares diferents — potser una mare resol bé el nord de la ciutat i un pare el sud —, i la mutació injecta varietat per no quedar-se encallat (exploració). Res d'això no garanteix l'òptim; el que produeix és una pressió estadística sostinguda cap a solucions millors.

Vocabulari que farem servir: individu/cromosoma (una solució codificada), gen (una posició del cromosoma), fitness (qualitat de l'individu), generació (una iteració del bucle).

Representació: cromosomes binaris i permutacions

La primera decisió de disseny — i la més important — és com codificar una solució:

  • Codificació binària: una llista de 0/1. Natural per a problemes de subconjunt, com la motxilla de 02-02: [0, 1, 0, 1, 0] significa "carregar E2 i E4". Els operadors clàssics (encreuament per punt, mutació bit a bit) funcionen directament.
  • Codificació de permutació: un ordre d'elements. Natural per a problemes de seqüència com el TSP: [3, 1, 5, ...] és l'ordre de visita de les parades. Compte: els operadors binaris clàssics aquí trenquen la solució — encreuar dues permutacions per un punt sol duplicar unes parades i ometre'n d'altres, és a dir, produeix fills que ni tan sols són rutes. Les permutacions exigeixen operadors especialitzats (OX, que veurem de seguida).
Problema de Rutalia Codificació Individu d'exemple Compte amb
Què carregar a la furgoneta (motxilla) Binària [1, 0, 0, 1, 1] Individus infactibles (sobrepès): penalitzar o reparar
Ordre de la ruta (TSP) Permutació [4, 1, 6, 9, 3, 7, 5, 2, 8] L'encreuament ha de preservar que sigui permutació

Funció de fitness

El fitness tradueix "qualitat" a un número que la selecció pugui comparar. Per al TSP, menor distància = millor individu. Dues opcions habituals: usar directament la longitud de la ruta (i seleccionar els menors), o convertir a "més gran és millor" amb fitness = 1 / longitud. Usarem la primera per claredat, amb una precaució d'enginyeria: l'avaluació de fitness és el 90 % del cost d'un AG típic (s'executa població × generacions vegades), així que ha de ser barata — i amb la nostra matriu D precalculada a 02-02, ho és.

Per a problemes amb restriccions (motxilla amb sobrepès), el fitness a més ha de decidir què fer amb els infactibles: penalitzar (restar molt valor per quilo d'excés) o reparar (descarregar objectes fins que hi càpiga). Les penalitzacions mal calibrades són una font clàssica d'AG que "funcionen" plens de solucions inservibles.

Selecció: torneig i ruleta

La selecció tria quins individus es reprodueixen. Ha d'afavorir els bons sense eliminar la diversitat (si només es reprodueix el millor, en tres generacions la població són clons i l'AG degenera en un voraç car).

  • Torneig (k participants): tria k individus a l'atzar i guanya el millor. Simple, robust i amb pressió regulable: k = 2 és suau, k = 7 és agressiu. És l'opció per defecte a la pràctica.
  • Ruleta: cada individu rep una probabilitat proporcional al seu fitness (una "ruleta" amb sectors de mida desigual). Elegant en teoria, delicada a la pràctica: exigeix fitness positiu i "més gran = millor", i si un individu domina molt, monopolitza la ruleta (convergència prematura); si tots són semblants, la selecció esdevé gairebé aleatòria.
import random

def seleccio_torneig(poblacio, k=3):
    """Retorna el millor de k individus triats a l'atzar (menor longitud guanya)."""
    candidats = random.sample(poblacio, k)
    return min(candidats, key=longitud_individu)

def seleccio_ruleta(poblacio):
    """Probabilitat proporcional al fitness 1/longitud."""
    pesos = [1.0 / longitud_individu(ind) for ind in poblacio]
    return random.choices(poblacio, weights=pesos, k=1)[0]

Encreuament: un punt i order crossover (OX)

Encreuament d'un punt (codificació binària): talla tots dos pares per la mateixa posició aleatòria i intercanvia les meitats. Per a la motxilla: [1,0|0,1,1] × [0,1|1,0,0] → fills [1,0,1,0,0] i [0,1,0,1,1]. Barat i efectiu quan gens contigus formen "blocs" amb sentit.

Order crossover (OX) (permutacions): l'operador estrella per a rutes. Copia un segment del pare 1 tal qual, i omple els forats amb les parades restants en l'ordre en què apareixen al pare 2. El fill hereta una subruta literal d'un pare i l'ordre relatiu de l'altre — i sempre és una permutació vàlida:

Pare 1:   4 1 | 6 9 3 | 7 5 2 8        segment triat: posicions 2-4
Pare 2:   9 3 5 2 6 8 1 4 7

Fill:     _ _ | 6 9 3 | _ _ _ _        1) copiar el segment del pare 1
Restants en l'ordre del pare 2 (saltant 6, 9, 3): 5 2 8 1 4 7
Fill:     5 2 | 6 9 3 | 8 1 4 7        2) omplir els forats en aquest ordre
def encreuament_ox(pare1, pare2):
    n = len(pare1)
    a, b = sorted(random.sample(range(n), 2))       # extrems del segment
    fill = [None] * n
    fill[a:b + 1] = pare1[a:b + 1]                  # 1) segment literal del pare 1
    usats = set(fill[a:b + 1])
    restants = [g for g in pare2 if g not in usats]      # 2) ordre del pare 2
    forats = [i for i in range(n) if fill[i] is None]
    for i, gen in zip(forats, restants):
        fill[i] = gen
    return fill

Mutació, elitisme i criteris de parada

  • Mutació: amb probabilitat petita, alterar l'individu. Binària: capgirar un bit. Permutacions: intercanviar dues posicions (swap) o invertir un tram. Sense mutació, la població només recombina material genètic inicial: si cap permutació inicial no posa H al final, l'encreuament mai no ho inventarà; la mutació sí.
  • Elitisme: copiar intactes els 1-2 millors individus a la generació següent. Garanteix que el millor resultat mai no empitjora entre generacions (monotonia que la selecció estocàstica per si sola no dona). Amb massa elit, la població s'uniformitza.
  • Criteris de parada: nombre fix de generacions (predictible, el nostre default), estancament (X generacions sense millora — el més usat en producció), pressupost de temps, o assolir una fita coneguda.

Implementació completa: AG per al TSP de Rutalia

Tot junt, sobre la instància de 02-02 (requereix NOMS, D i longitud_ruta d'aquella lliçó). El dipòsit (índex 0) queda fora del cromosoma: sempre és inici i final, així que l'individu és una permutació d'[1..9]:

import random

def longitud_individu(individu):
    """Individu = permutació d'1..9. La ruta completa anteposa el dipòsit."""
    return longitud_ruta(tuple([0] + individu))

def crear_individu():
    gens = list(range(1, len(NOMS)))
    random.shuffle(gens)
    return gens

def mutacio_swap(individu, prob=0.2):
    if random.random() < prob:
        i, j = random.sample(range(len(individu)), 2)
        individu[i], individu[j] = individu[j], individu[i]
    return individu

def algorisme_genetic(mida_poblacio=100, generacions=200,
                      k_torneig=3, prob_mutacio=0.2, elit=2, llavor=42):
    random.seed(llavor)                        # reproduïbilitat de l'execució
    poblacio = [crear_individu() for _ in range(mida_poblacio)]
    historial = []                             # millor longitud per generació

    for g in range(generacions):
        poblacio.sort(key=longitud_individu)            # millors primer
        historial.append(longitud_individu(poblacio[0]))

        nova = [ind[:] for ind in poblacio[:elit]]      # ELITISME: còpies, no referències
        while len(nova) < mida_poblacio:
            pare1 = seleccio_torneig(poblacio, k_torneig)
            pare2 = seleccio_torneig(poblacio, k_torneig)
            fill = encreuament_ox(pare1, pare2)
            nova.append(mutacio_swap(fill, prob_mutacio))
        poblacio = nova

    millor = min(poblacio, key=longitud_individu)
    return millor, longitud_individu(millor), historial

millor, km, hist = algorisme_genetic()
print([NOMS[i] for i in [0] + millor], round(km, 2))
# ['DEP', 'D', 'A', 'F', 'I', 'C', 'G', 'E', 'B', 'H'] 35.22
print("Generació en què s'ha assolit:", hist.index(min(hist)))

Punts que mereixen lupa:

  • Avaluacions totals: 100 individus × 200 generacions = 20.000 avaluacions de ruta — del mateix ordre de feina útil que els ~1.200 nodes de B&B multiplicats pel seu cost de fita, i molt per sota de les 362.880 rutes de la força bruta. En la nostra execució, l'AG assoleix l'òptim conegut de 35,22 km (la mateixa ruta que B&B), normalment en les primeres desenes de generacions. Que això passi gairebé sempre en una instància de 10 nodes és esperable: l'espai és petit per a la potència del mètode. La diferència apareix en escalar: amb 100 parades, B&B no acaba i l'AG continua lliurant bones rutes amb el mateix codi.
  • L'elit es copia (ind[:]), no es referencia: si la mutació toqués una referència compartida, corrompria el millor individu silenciosament. Errors així són el malson de depurar AG, perquè l'algorisme continua funcionant, només que pitjor.
  • L'historial és el teu instrument de diagnòstic: una corba que cau ràpid i s'aplana aviat suggereix convergència (prematura?); una que baixa a batzegades fins al final demana més generacions.
  • La llavor fixa la seqüència aleatòria. En producció s'executen diverses llavors i es reporta mitjana i millor cas — una sola execució d'un algorisme estocàstic és una anècdota, no una mesura.

Hiperparàmetres: què tocar i què esperar

Els AG no es programen una vegada: s'ajusten. Guia d'efectes:

Hiperparàmetre Valor típic Si és massa baix Si és massa alt
Mida de població 50–200 Poca diversitat: convergència prematura Cost per generació alt sense millora proporcional
Generacions 100–1000 S'atura abans de convergir Temps malbaratat després de l'estancament
k del torneig 2–5 Pressió feble: deriva gairebé aleatòria Pressió brutal: clons en poques generacions
Prob. de mutació 0,05–0,3 per individu La població s'uniformitza i s'encalla La cerca degenera en passeig aleatori
Elit 1–2 (≈ 1–2 %) El millor es pot perdre entre generacions L'elit domina i congela l'evolució

La tensió de fons és sempre la mateixa: explotació (refinar el que és bo: més pressió de selecció, més elit) contra exploració (buscar el que és nou: més mutació, més població). No existeix cap configuració universal; existeix l'hàbit de mesurar amb l'historial i ajustar un paràmetre cada vegada.

Les cosines de veïnatge: recuita simulada i cerca tabú

Els AG no són l'única manera de cercar sense garanties. Dues famílies que convé conèixer de nom — treballen amb un sol individu que es mou pel seu veïnatge (solucions a un petit canvi de distància), en lloc de fer-ho amb una població:

  • Recuita simulada (simulated annealing): accepta de vegades moviments que empitjoren, amb una probabilitat que decau amb el temps (la "temperatura" baixa). Al principi explora amb llibertat; al final només refina. Inspiració: el refredament lent dels metalls.
  • Cerca tabú: cerca local que manté una llista tabú de moviments recents prohibits, per no desfer el camí fet ni ciclar al voltant d'un òptim local.
Algorisme genètic Recuita simulada Cerca tabú
Estat Població Un individu Un individu + memòria
Motor de millora Encreuament + selecció Veí aleatori + acceptació probabilística Millor veí no tabú
Escapa d'òptims locals per… Diversitat poblacional i mutació Acceptar empitjoraments (temperatura) Prohibir tornar enrere
Hiperparàmetre crític Pressió de selecció / mutació Esquema de refredament Mida de la llista tabú

A la pràctica competeixen de tu a tu amb els AG (i sovint s'hibriden: un AG el millor individu del qual es refina amb cerca local). No les desenvoluparem més: en tenim prou de saber que existeixen i què les distingeix, perquè la propera lliçó presenta una metaheurística d'esperit molt diferent — basada en cooperació mitjançant rastres compartits — i tancarem comparant les tres aproximacions del mòdul sobre el mateix TSP.

Errors Comuns i Consells

  • Encreuament clàssic sobre permutacions. L'encreuament d'un punt aplicat a rutes produeix fills amb parades duplicades i omeses — ni tan sols són solucions. Amb permutacions, usa OX (o PMX/CX, els seus parents). És l'error número u en adaptar codi de motxilla a TSP.
  • Oblidar copiar l'elit. nova = poblacio[:2] guarda referències; una mutació posterior corromp els millors. Copia amb ind[:] o list(ind).
  • Fitness car. Si avaluar un individu costa 10 ms, 100 × 200 avaluacions són 3,3 minuts només de fitness. Precalcula (la nostra matriu D), fes memòria cau, vectoritza. L'anàlisi de costos de 01-02 s'aplica dins de la metaheurística.
  • Convergència prematura no diagnosticada. Si a la generació 20 tots els individus són gairebé idèntics, la resta del pressupost es llença. Vigila la diversitat (p. ex., longituds diferents a la població) a més del millor fitness.
  • Concloure a partir d'una execució. Estocàstic significa que la llavor 42 pot ser afortunada. Executa 10-30 llavors i mira la distribució, no l'anècdota.
  • Usar un AG on hi ha mètode exacte viable. Per a la motxilla de 5 enviaments o el TSP de 10 punts, PD i B&B donen l'òptim certificat en menys temps del que costa ajustar hiperparàmetres. Les metaheurístiques són l'eina de frontera, no la primera opció.
  • Consell: guarda sempre el millor individu global de l'execució (no només el de la darrera generació) i, si existeix, compara'l amb una fita o un òptim conegut. Sense referència, "l'AG ha millorat" no significa res.

Exercicis

  1. OX a mà. Amb pares P1 = [2, 5, 1, 4, 3, 6] i P2 = [4, 1, 6, 2, 5, 3] i segment a les posicions 1–3 (0-indexat, totes dues incloses), calcula el fill de l'encreuament_ox pas a pas. Verifica que és una permutació vàlida.

  2. AG per a la motxilla. Adapta l'esquema complet a la motxilla 0/1 de 02-02 (capacitat 15, pesos [12, 7, 11, 8, 9], valors [40, 24, 35, 26, 30]): codificació binària, encreuament d'un punt, mutació de capgirament de bit, i fitness amb penalització per sobrepès (valor − 10 × excés). Assoleix l'òptim de 50 €? Què passa si la penalització és 1 per unitat d'excés en lloc de 10?

  3. Estudi de mutació. Executa algorisme_genetic amb prob_mutacio a {0.0, 0.05, 0.2, 0.8} i 10 llavors cadascuna (deixa la resta de paràmetres per defecte). Per a cada valor anota quantes llavors assoleixen 35,22 km i la mitjana del millor resultat. Interpreta els extrems.

Solucions

Exercici 1. Segment de P1, posicions 1–3: 5, 1, 4 → fill parcial [_, 5, 1, 4, _, _]. Restants de P2 en el seu ordre, saltant 5, 1, 4: P2 = [4, 1, 6, 2, 5, 3] → queden 6, 2, 3. Forats: posicions 0, 4, 5 → fill = [6, 5, 1, 4, 2, 3]. Conté cada gen 1..6 exactament una vegada: permutació vàlida. Observa l'herència: el bloc 5-1-4 ve literal de P1; l'ordre relatiu 6 → 2 → 3 ve de P2.

Exercici 2. Esquelet dels canvis:

def crear_individu():
    return [random.randint(0, 1) for _ in range(5)]

def fitness(ind, penal=10):
    pes   = sum(p * x for p, x in zip([12, 7, 11, 8, 9], ind))
    valor = sum(v * x for v, x in zip([40, 24, 35, 26, 30], ind))
    exces = max(0, pes - 15)
    return valor - penal * exces

def encreuament_un_punt(p1, p2):
    c = random.randint(1, len(p1) - 1)
    return p1[:c] + p2[c:]

def mutacio_bit(ind, prob=0.2):
    if random.random() < prob:
        i = random.randrange(len(ind))
        ind[i] = 1 - ind[i]
    return ind

Amb penalització 10, el sobrepès surt caríssim i la població convergeix a individus factibles; l'òptim [0,1,0,1,0] (50 €) apareix en poques generacions — l'espai només té 2⁵ = 32 punts, així que més que un repte és un banc de proves. Amb penalització 1 l'AG descobreix un "truc" indesitjat: [1,1,1,1,1] pesa 47 (excés 32) i puntua 155 − 32 = 123 > 50 — el millor individu és infactible i l'AG optimitza amb entusiasme el problema equivocat. És la lliçó important de l'exercici: la penalització ha de fer que cap infactible no superi un factible, o el fitness menteix.

Exercici 3. Resultats típics (els teus variaran, d'això tracta l'exercici): amb 0.0, diverses llavors es queden clavades per sobre de l'òptim — sense mutació, la població esgota el seu material genètic inicial i no pot fabricar ordenacions noves; amb 0.05 i 0.2, la gran majoria de llavors assoleixen 35,22 km, amb 0.2 una mica més robust en aquesta instància; amb 0.8, els fills es destrueixen gairebé sempre tot just néixer i la mitjana empitjora — la cerca s'acosta a un mostreig aleatori amb elit. La corba qualitat-vs-mutació té forma d'U invertida: el punt dolç és on hi ha varietat suficient sense destruir l'herència.

Conclusió

Hem fet el tracte heurístic amb els ulls oberts: a canvi del certificat d'optimalitat que donaven PD i B&B, els algorismes genètics ens donen escala i generalitat — només demanen una codificació sensata (binària per a subconjunts, permutacions amb OX per a rutes), un fitness barat i honest amb les restriccions, i l'equilibri etern entre pressió de selecció i mutació. Sobre el TSP de Rutalia, el nostre AG de 100 individus i 200 generacions va assolir els mateixos 35,22 km que B&B va certificar a 02-03 — sense poder certificar-los, però amb un codi que continuaria funcionant igual amb 100 parades, on B&B ja no juga. A la propera lliçó coneixerem una metaheurística amb una altra inspiració biològica: en lloc d'herència i selecció, cooperació indirecta — formigues que es deixen senyals químics sobre les bones rutes. Implementarem l'optimització per colònia de formigues sobre aquesta mateixa instància i tancarem el mòdul amb la comparació experimental de les tres aproximacions: exacta, evolutiva i estigmèrgica.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2026. Tots els drets reservats