TSPEnryGA

   by Enrico Mambrucchi    English  Italiano    SourceForge.net Logo Support This Project
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
A B C D E F G H I J

Figlio F1'
A B I D E F G H C J


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
A B C D E F G H I J

Figlio F1'
A B I J E F G H C D


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
A B I J E F G H I J

Genitore G2
E H D B A G C J F I


...Crossover Uniforme Sequenziale...

Figlio F1
E B I J A F G H I J


Figlio F2
A B H D E F G C J I


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