🚚 Ottimizzatore di Percorsi per la Supply Chain — Un Algoritmo Genetico all'Opera

Si tratta di una piccola variante di instradamento veicoli del Problema del Commesso Viaggiatore (TSP): trovare il tour chiuso più breve che parte e termina in un deposito visitando ogni cliente esattamente una volta. Il TSP è NP-hard — il numero di percorsi possibili per N clienti è (N−1)!/2, che per soli 16 clienti supera i 650 miliardi. Gli algoritmi esatti (branch-and-bound, programmazione dinamica) possono risolvere istanze modeste ma scalano male. Gli algoritmi genetici, insieme ad altre metaeuristiche come il simulated annealing e l'ottimizzazione a colonie di formiche, rinunciano alla garanzia di ottimalità in cambio di un percorso solitamente molto buono trovato in una frazione del tempo — esattamente il compromesso che il software logistico reale adotta per flotte con decine o centinaia di tappe.

Se l'intera popolazione converge verso percorsi che condividono la stessa struttura di base, il crossover tra due genitori simili riproduce per lo più quella stessa struttura, e le piccole mutazioni per scambio raramente bastano a sfuggire da un ciclo localmente buono ma globalmente subottimale — per esempio un percorso con un incrocio evitabile. Questo fenomeno si chiama convergenza prematura: la diversità della popolazione crolla prima che venga trovato il miglior tour possibile. Aumentare il tasso di mutazione, ampliare la dimensione della popolazione o usare una nuova mappa per confrontare le esecuzioni sono modi per osservare questo compromesso tra esplorazione (diversità) e sfruttamento (perfezionare ciò che già funziona).

La selezione a torneo sceglie un piccolo sottoinsieme casuale della popolazione (un torneo, qui di dimensione 3) e seleziona come genitore il membro più adatto di quel sottoinsieme. È semplice, veloce, e la sua pressione selettiva è facile da regolare tramite la dimensione del torneo: un torneo più grande rende più probabile che il singolo individuo migliore domini la riproduzione (convergenza più rapida, rischio maggiore di convergenza prematura), mentre un torneo più piccolo mantiene più diversità. Questo evita alcune insidie della selezione proporzionale alla fitness (a ruota della fortuna), in cui un percorso con una distanza insolitamente breve può dominare immediatamente l'intera popolazione.

Una popolazione più grande esplora una porzione maggiore dello spazio delle permutazioni dei percorsi per generazione ed è meno soggetta a perdere diversità utile per deriva casuale, ma ogni generazione costa più valutazioni della distanza. Un tasso di mutazione più alto introduce più casualità, aiutando a sfuggire dagli ottimi locali ma disturbando anche più spesso i buoni percorsi, il che può rallentare la convergenza o persino peggiorare temporaneamente la media della popolazione (l'elitismo protegge comunque il singolo percorso migliore). In pratica esiste un punto ottimale — dimensioni della popolazione grosso modo tra le decine e le poche centinaia e tassi di mutazione di pochi punti percentuali per gene tendono a convergere più rapidamente per problemi di questa dimensione.