TSPEnryGA
by Enrico Mambrucchi
Download TSPEnryGA
Problema del Commesso Viaggiatore
Introduzione
Dati un numero di città, trovare il percorso più breve che passi attraverso tutte le città e torni a quella di partenza.
Nel caso in cui fossero poche le città, sarebbe possibile
risolvere questo problema anche con un normale algoritmo. Quando però le città
sono molte serve un algoritmo non lineare per ottenere la soluzione in tempi
accettabili. Ed è proprio qui che intervengono gli algoritmi genetici.
Algoritmo Genetico
Un algoritmo genetico è uno strumento in grado di risolvere
problemi di ricerca ed ottimizzazione.
Sono basati sui processi evolutivi biologici. Una
popolazione di individui si evolve, generazione dopo generazione, secondo i
principi della selezione naturale e della sopravivenza del migliore, come
teorizzato da Charles Darwin nel suo famoso libro "L'evoluzione delle specie".
Proprio imitando questo comportamento gli algoritmi genetici
riescono ad evolvere soluzioni a problemi reali.
In natura gli individui di una popolazione concorrono fra di
loro per il cibo, per l'acqua, per i territorio, per la riproduzione, ...
Quelli che hanno più successo nella riproduzione e nella
sopravvivenza avranno un numero maggiore di discendenti e quindi le proprie
caratteristiche verranno ereditate da molti individui; mentre i meno adatti
tenderanno ad avere sempre meno prole e quindi ad estinguersi.
Proprio così le specie riescono ad evolversi eliminando le
caratteristiche inutili o negative ed accumulando e migliorando quelle
positive.
Gli algoritmi genetici funzionano con gli stessi principi.
Anch'essi rappresentano una popolazione di individui, dove ogni individuo
rappresenta una possibile soluzione al problema.
Ad ogni individuo è assegnato un punteggio (fitness) a seconda di quanto sia buona la soluzione che propone.
Come anche in natura, gli individui migliori di un algoritmo genetico hanno maggiori probabilità di riprodursi e quindi di trasmettere le proprie caratteristiche (geni) alle generazioni future.
Soluzione Adottata
Per risolvere il problema del commesso viaggiatore rappresentiamo ogni città con un gene.
Un individuo, quindi il suo cromosoma, è formato
dall'insieme di tutti i geni e la loro sequenza indica la soluzione del
problema proposta dall'individuo.
Più il percorso è breve e maggiore sarà il suo fitness e quindi la sua probabilità di riprodursi.
Parent Selection
Gli individui con maggiore fitness hanno maggiore probabilità di essere selezionati per l'accoppiamento.
L'estrazione è quindi casuale ma viene pilotata verso gli individui con maggior fitness.
Fitness
Utilizziamo come tecnica per calcolare il fitness il cosiddetto fitness ranking.
Nel nostro caso calcoliamo quindi la lunghezza del percorso di ogni individuo (fitness).
Partendo poi dall'individuo con maggiore lunghezza cominciamo ad ordinarli assegnandogli come valore di
fitness ranking numeri consecutivi a partire da 1 fino a n (numero di individui).
Il migliore individuo avrà come fitness il valore n, mentre il peggiore 1.
Elitism
Utilizziamo questa tecnica per salvare e non mandare perdute
le caratteristiche del miglior individuo (nel nostro caso ne salviamo due)
della popolazione. In pratica il migliore cromosoma (quello con fitness
maggiore) viene duplicato nella nuova generazione (noi ne duplichiamo due)
Utilizzando il fitness ranking è probabile che sia il
migliore che il peggiore individuo non vengano scelti come genitori per le
nuove generazioni, visto che gli estremi tendono ad essere svantaggiati.
Proprio con l'elitismo riusciamo comunque a conservare le migliori soluzioni
raggiunte finora.
Mutation
Per garantire un aspetto ancora più casuale nella popolazione introduciamo la possibilità di una mutazione (probabilità nell'ordine di 0,001) nei figli appena generati.
Mutazione a scambio estesa
In questo caso, se avviene una mutazione, scambiamo due geni
di posizione: uno appartenente alla prima metà e uno alla seconda metà del
cromosoma.
Figlio F1
Figlio F1'
Mutazione a doppio scambio estesa
Con questa tecnica scambiamo, invece di un solo gene, una
coppia consecutiva di geni, sempre una appartenente alla prima metà e uno alla
seconda metà del cromosoma.
Figlio F1
Figlio F1'
Crossover
Questa è la tecnica da applicare per incrociare due cromosomi ed ottenere quindi due figli.
Ci sono ovviamente vari metodi per fare il crossover.
Nel nostro esempio ne proveremo alcuni per vedere quali effetti producono nella popolazione.
Crossover Uniforme Sequenziale
Questa tecnica è l'insieme di due tecniche diverse e permette di non mescolare le posizioni dei geni, visto che nel nostro caso è determinante per la soluzione del problema.
Dividiamo il cromosoma in quattro parti (3-point crossover) casuali.
Due di queste parti vengono copiate nel figlio A e le altre
due nel figlio B, rispettando le posizioni in cui erano nel genitore. Dal
secondo genitore, infine, prendiamo i geni non utilizzati nel primo genitore e
li mettiamo nei due figli riempiendo così i buchi (rispettiamo sempre la sequenza,
ma ovviamente le posizioni andranno perdute).
Genitore G1
Genitore G2
...Crossover Uniforme Sequenziale...
Figlio F1
Figlio F2
Single Point Crossover
Questa tecnica più semplice consiste nel dividere i genitori
in due parti ciascuno e scambiarle per formare due figli. E' più elementare
della precedente indicata ma garantisce comunque un buon risultato visto che
mantiene vicini i geni dei genitori. Anche se ne viene invertito l'ordine non
ci sono grossi problemi nel nostro caso, visto che la città di partenza non è
importante (il commesso viaggiatore parte da una città e ritorna nella stessa,
quindi può partire da una qualunque città, il percorso non cambia).
Mating
Utilizzando le tecniche appena descritte selezioniamo i
genitori dalla popolazione e ne creiamo una completamente nuova con lo stesso
numero di individui (i genitori possono anche essere scelti più volte, visto
che non vengono subito tolti dalla popolazione).
Quando la nuova generazione è completa si elimina completamente
la vecchia (gli individui non selezionati per l'accoppiamento muoiono e non
propagano i loro geni).
Software
Nel programma sarà possibile selezionare i vari metodi di crossover e mutazione per poter vedere come influenzano l'evoluzione della popolazione ed inoltre verrà visualizzata a video la migliore soluzione trovata.
Download TSPEnryGA