Esplora il fascino delle 50 città più visitate d’Europa utilizzando algoritmi genetici e l’API di Google Maps, sbloccando percorsi di viaggio efficienti
Ricorda quella sensazione dopo aver visto film come Euroviaggiodove i personaggi attraversano pittoresche città europee in un’avventura di una vita? È accattivante. Eppure, la realtà ce lo ricorda subito: organizzare un viaggio attraverso numerose destinazioni non è un compito semplice. Ma ecco la svolta entusiasmante: armato di esperienza di programmazione e di conoscenza degli algoritmi genetici, mi sono imbarcato nello sviluppo di una soluzione. Immagina di poter ottimizzare con precisione percorsi complessi che abbracciano decine di località. È qui che il mondo della scienza dei dati si interseca con l’arte della pianificazione delle avventure. In questo articolo, svelo uno script algoritmico che affronta con eleganza la complessità Problema del commesso viaggiatore (TSP), promettendo di aiutare la pianificazione dei viaggi e migliorare la nostra comprensione dell’ottimizzazione nella scienza dei dati.
La lettura di questo articolo ti fornirà una chiara comprensione di come la sinergia tra Python, API di Google Maps e algoritmi genetici sblocca soluzioni basate sui dati per attività non banali.
Partire per un viaggio spesso accende un senso di avventura, ma mentre contempliamo le complessità del viaggio, l’eccitazione può essere accompagnata da sfide logistiche. Una di queste sfide che da decenni cattura l’attenzione di matematici, informatici ed esperti di logistica è il problema del commesso viaggiatore (TSP). Fondamentalmente, il TSP pone una domanda apparentemente semplice: dato un elenco di città e le distanze tra loro, qual è il percorso più breve possibile che consente a un venditore di visitare ciascuna città esattamente una volta e tornare al punto di partenza? Sebbene l’enunciazione del problema sia concisa, le sue implicazioni si estendono ben oltre la sua semplicità superficiale.
Nel mondo dell’ottimizzazione e della logistica, il TSP è più di una curiosità teorica; ha un immenso significato pratico. Prendi in considerazione i servizi di consegna, dove ridurre al minimo le distanze di viaggio si traduce direttamente in una riduzione dei costi del carburante e in un servizio più rapido.
Al di sotto di questa affermazione del problema apparentemente semplice risiede un profondo livello di complessità. La natura combinatoria del TSP nasce dalla crescita esponenziale delle possibili soluzioni all’aumentare del numero delle città. La quantità di percorsi possibili sale rapidamente alle stelle oltre ogni fattibilità computazionale, rendendo i tradizionali metodi di forza bruta impraticabili per casi più grandi. Il numero di percorsi possibili è uguale a
dove n rappresenta il numero di città — a esplosione fattoriale che diventa rapidamente travolgente. Con sole 50 città, il numero di percorsi possibili è pari a 3*10⁶², che è quasi il numero di atomi nella Via Lattea.
Il TSP rappresenta un esempio per eccellenza dell’intrigante intersezione tra matematica, informatica e sfide logistiche del mondo reale. Man mano che il numero delle città aumenta, svelare il percorso più breve richiede strategie innovative che trascendono gli approcci computazionali convenzionali.
La ricerca di soluzioni efficienti per il TSP ha spinto i ricercatori a esplorare una varietà di metodologie. Tra questi ci sono gli algoritmi genetici, una classe di tecniche di ottimizzazione ispirate al processo di selezione naturale. Gli algoritmi genetici eccellono nell’esplorazione di spazi di soluzioni complessi, rendendoli una soluzione naturale per affrontare problemi come il TSP, dove i metodi di forza bruta diventano rapidamente irrealizzabili man mano che il numero di città cresce.
Lo scopo di questo articolo è quello di esplorare l’unione di questi due ambiti: il problema del commesso viaggiatore e gli algoritmi genetici. Nello specifico, ci immergiamo in un’applicazione pratica: uno script Python progettato per sfruttare la potenza degli algoritmi genetici per risolvere il TSP. La nostra esplorazione metterà in evidenza come questa fusione algoritmica abbia il potenziale per migliorare la pianificazione dei viaggi, la logistica e le sfide di ottimizzazione in tutti i settori. Man mano che comprenderemo il funzionamento interno della nostra soluzione basata su algoritmi genetici, il mondo della scienza dei dati e dell’innovazione algoritmica convergerà, promettendo nuove intuizioni e percorsi efficienti anche attraverso i percorsi più labirintici.
Fondamentalmente, un algoritmo genetico (GA) è una tecnica di ricerca euristica ispirata all’elegante processo di selezione naturale ed evoluzione.
L’ispirazione dietro gli algoritmi genetici risale alla teoria dell’evoluzione di Charles Darwin. I GA imitano il processo di selezione naturale evolvendo iterativamente una popolazione di potenziali soluzioni. In questo crogiolo digitale, le soluzioni che mostrano tratti favorevoli sopravvivono e si riproducono, trasmettendo i loro “geni” alla generazione successiva. Questa evoluzione generazionale continua fino al raggiungimento di una soluzione ottimale o quasi ottimale.
Gli algoritmi genetici sono caratterizzati da quattro componenti fondamentali:
- Selezione: Proprio come in natura, i meccanismi di selezione identificano e favoriscono soluzioni con maggiore fitness, rispecchiando il concetto di “sopravvivenza del più adatto”.
- Incrocio: Le soluzioni, o “cromosomi”, scambiano materiale genetico per creare una prole con una miscela dei tratti dei genitori.
- Mutazione: Per introdurre la diversità e prevenire una convergenza prematura verso soluzioni non ottimali, gli algoritmi genetici incorporano un operatore di mutazione. Questa operazione altera in modo casuale alcuni elementi di una soluzione, simile alle mutazioni genetiche in natura.
- Valutazione dell’idoneità: È la determinazione dell’idoneità di ciascuna soluzione, che quantifica quanto bene esegue il compito da svolgere. La funzione fitness guida il processo di selezione assegnando una maggiore probabilità di riproduzione alle soluzioni superiori.
Gli algoritmi genetici mostrano una notevole versatilità quando si tratta di affrontare problemi di ottimizzazione. La loro capacità di esplorare spazi di soluzione in modo non lineare e multidimensionale li rende adatti alle sfide complesse del mondo reale. Che si tratti di ottimizzare progetti ingegneristici complessi, mettere a punto parametri di reti neurali o, come vedremo presto, risolvere il TSP, gli algoritmi genetici eccellono in scenari in cui gli algoritmi tradizionali falliscono.
Ora, approfondiamo l’applicazione degli algoritmi genetici (GA) per risolvere il problema del commesso viaggiatore (TSP).
Fondamentalmente, i GA si avvicinano al TSP considerando ogni potenziale percorso come un individuo all’interno di una popolazione. Questa popolazione di percorsi si evolve nel corso delle generazioni, e ogni percorso rappresenta un itinerario unico per il venditore ambulante.
Per facilitare questa evoluzione genetica, rappresentiamo ogni percorso come un cromosoma, una sequenza di città che definiscono l’ordine di visita. Per esempio:
Il compito fondamentale è scoprire il cromosoma ottimale, la sequenza che minimizza la distanza totale da percorrere. L’idoneità di ciascun cromosoma viene quantificata valutando la distanza totale che copre visitando le città nell’ordine specificato. Una distanza inferiore equivale a una maggiore forma fisica, rispecchiando l’obiettivo di trovare il percorso più breve.
Ora seguiamo passo dopo passo l’implementazione di alto livello dello script Python progettato per affrontare il TSP. Il codice completo è disponibile nel mio Repositorio GitHub.
Ottenere i dati
Il primo passo consiste nella scelta delle destinazioni. Per questo esempio, ho scelto di selezionare le 50 città più visitate d’Europa. Una volta definite le destinazioni, avevo bisogno delle distanze e dei tempi di viaggio tra ogni coppia di città. Per questo tipo di query, le API di Google Maps rappresentano la soluzione all’avanguardia. Dopo aver configurato un account Quipuoi richiedere la tua chiave API personale, necessaria per autenticarti.
Le richieste alle API di Google Maps vengono inviate in questo modo:
Inizializzazione
Il processo inizia generando una popolazione iniziale di percorsi. Questi percorsi vengono generalmente creati in modo casuale o tramite un metodo euristico.
Valutazione e selezione dell’idoneità
In ogni passaggio, dopo aver generato prole e aver modificato alcuni percorsi, viene calcolata la distanza totale per ciascun percorso per valutarne l’idoneità. Questo passaggio garantisce che l’algoritmo continui a concentrarsi sulla selezione dei percorsi più brevi.
Nello spirito della selezione naturale, i percorsi di riproduzione vengono scelti in base alla loro forma fisica. È più probabile che vengano selezionati percorsi con distanze totali più brevi – quelli più vicini alla soluzione ottimale – consentendo agli individui con tratti vantaggiosi di avere maggiori probabilità di riprodursi.
Crossover e mutazione
Per le particolarità di questo problema non viene effettuata la classica operazione di crossover. Ho optato per due tipi di mutazione:
- Mutazioni puntuali: Per mantenere la diversità e introdurre nuove soluzioni, l’algoritmo introduce piccole modifiche casuali ai percorsi selezionati. Questo emula le mutazioni genetiche, introducendo lievi variazioni.
- “Mutazioni crossover”: Muta una soluzione tagliando un sottoinsieme casuale del suo genoma e aggiungendolo in un’altra posizione. Per riprendere termini biologici, si tratta di una sorta di riproduzione asessuata.
Iterazione
I passaggi precedenti vengono ripetuti per un determinato numero di generazioni, consentendo alla popolazione di evolversi nel tempo. Ogni iterazione avvicina l’algoritmo a una soluzione ottimale o quasi ottimale.
L’algoritmo continua l’iterazione finché non viene soddisfatto un criterio di terminazione. In questo caso il criterio di cessazione consiste nel raggiungimento di un numero predeterminato di generazioni.
In questa esplorazione, ho utilizzato un GA con una popolazione di 200 individui e l’ho gestito per 1000 generazioni per affrontare il TSP con 50 città. Il viaggio dalla generazione iniziale al risultato finale rivela la notevole efficienza dell’approccio basato su GA.
All’inizio, nella generazione zero, è emersa la prima soluzione con un’idoneità di 70.755 chilometri:
('Sofia, Bulgaria', 'Nice, France', ..., 'Naples, Italy', 'Luxembourg City, Luxembourg')
Questa soluzione iniziale, come previsto, rappresentava una disposizione casuale delle città, a significare il punto di partenza dell’algoritmo. Tuttavia, man mano che l’AG attraversava le generazioni successive, abbiamo osservato una notevole trasformazione nella qualità delle soluzioni.
Dopo 1000 generazioni l’AG ha trovato le sue rotte. L’endpoint era una soluzione con un’idoneità di 21.345 chilometri, una riduzione significativa della distanza da percorrere rispetto alla soluzione casuale iniziale. Questo notevole miglioramento di quasi 49.410 chilometri sottolinea l’efficacia dell’AG nell’ottimizzazione di percorsi complessi come il TSP.
Ho eseguito 4 prove modificando la dimensione della popolazione. I risultati complessivamente migliori si ottengono con una popolazione più numerosa, ma il tempo di calcolo è ovviamente più lungo. Possiamo vedere come, per ogni prova, il valore di fitness diminuisce rapidamente durante le prime iterazioni e si stabilizza successivamente su un valore di plateau. Questo è il comportamento tipico di un algoritmo convergente.
Mentre il TSP rimane un problema NP-difficile, il che significa che trovare la soluzione ottimale assoluta può essere impegnativo dal punto di vista computazionale per istanze più grandi, la capacità del GA di avvicinarsi a soluzioni quasi ottimali si rivela preziosa nelle applicazioni pratiche. Questo risultato apre le porte a una pianificazione dei viaggi più efficiente, a una logistica semplificata e a una maggiore ottimizzazione in diversi settori. Questo esperimento evidenzia la relazione simbiotica tra scienza dei dati e algoritmi innovativi. Sottolinea come il calcolo evolutivo, ispirato ai meccanismi di selezione della natura, possa affrontare con eleganza problemi complessi nel mondo reale.
(1): Posizionamento ottimale della PMU a tre obiettivi, compresa la stima accurata dello stato: il caso dei sistemi di distribuzione
(2): Analisi delle prestazioni degli operatori di mutazione per risolvere il problema del commesso viaggiatore
(3): Modello probabilistico con ottimizzazione evolutiva per la diagnosi cognitiva
(4): Crossover binario simulato per uno spazio di ricerca continuo
(5): Un nuovo operatore di mutazione per algoritmi genetici codificati reali
(6): Calcolo del viaggio stradale ottimale attraverso gli Stati Uniti
