Algoritmi genetici

 Esempio

Il problema preso in considerazione è quello comunemente noto come problema del commesso viaggiatore (travel salesman problem -TSP- in inglese): ci sono n città e partendo da una bisogna raggiungerle tutte e tornare a quella di partenza senza passare più volte per la stessa cercando di minimizzare la distanza totale percorsa. 
Per semplicità si assume che tutte le città siano connesse (cioè che esista una strada che colleghi direttamente ogni città a tutte le altre e che sia percorribile in entrambi i sensi). Il problema è pertanto schematizzabile come un grafo con n nodi da ognuno dei quali possono partire n-1 archi, uno verso ciascuna delle altre città. Come distanza si considera quella euclidea perché il risultato sia immediatamente evidente anche ad occhio nudo, ma ovviamente in termini algoritmici ciò non è necessario, basta assegnare ad ogni coppia di città un valore che ne rappresenti la distanza (o una misura analoga, come il tempo di percorrenza, il costo di viaggio ecc. ) perché il problema sia ben definito.
Se ad ogni città viene associato un numero da 1 a n le soluzioni sono pertanto stringhe di n cifre, che rappresentano quindi l'ordine con cui si visitano le città.
Ad esempio se vi sono 6 città una possibile soluzione è rappresentata da 136524, e da luogo ad un grafo come quello in figura. 

                            

Con n città tutte le possibili stringhe sono quindi n! sotto l'ipotesi che il grafo sia completamente connesso.
In questo tipo di problema è più conveniente codificare le soluzioni direttamente come stringhe di cifre decimali piuttosto che con un alfabeto binario. Concettualmente però non cambia nulla rispetto a quanto spiegato nelle sezioni precedenti.
Data una soluzione la fitness ad essa associata è ovviamente la distanza totale, data dalla somma delle singole distanze fra le città definite in precedenza e in questo esempio corrispondenti a quella euclidea. Si noti che con n città si percorrono n archi e non n-1 perché il problema prevede che si torni alla città di partenza. Si può pensare di prendere la città numero uno come quella di partenza, oppure supporre che si possa iniziare il percorso da una qualsiasi dal momento che la fitness, cioè la distanza totale percorsa non dipende ovviamente da quale città si parte. Inoltre come detto il tragitto può essere percorso nei due sensi, per cui in questo caso le soluzioni "indipendenti" sono in realtà n!/2n cioè (n-1)!/2.
Ciò riduce il numero di soluzioni che andrebbero esplorate per trovare la distanza minima, ma come si può facilmente immaginare queste crescono ugualmente molto velocemente col numero di città:
con n=6 le soluzioni sono 60 , ma con n=9 sono già 20160, e per n=14 addirittura più di 3*10⁹.
Come si vede questo è un tipico caso in cui non si può pensare di affrontare il problema esplorando indiscriminatamente tutto lo spazio delle soluzioni quando n è grande.
Quando la codifica delle soluzioni non è binaria ma permutazionale il crossover deve funzionare in modo che la ricombinazione di due sequenze (i genitori) dia luogo ad una stringa consistente, che sia cioè a sua volta una sequenza che soddisfi le condizioni poste dal problema ( che si passi cioè per tutte le città e mai più di una volta per la stessa). Operativamente ciò si realizza nella seguente maniera: data una coppia di stringhe e selezionato un punto di cross over (ci si sta riferendo quindi alla tecnica del one point) il figlio sarà la copia del primo genitore fino al punto di CO, dopodiché le cifre mancanti sono prese nell'ordine con cui compaiono nel secondo genitore.
                                    

La mutazione avviene invece permutando due cifre a caso della sequenza:

Una semplice applicazione degli AG per la risoluzione del problema TSP descritto in precedenza è fornita da un'applet in java sviluppato dal prof. Marek Obitko, autore di un sito sugli AG: http://cs.felk.cvut.cz/~xobitko/ga/ (Per visualizzare e far girare l'applet è necessario essere connessi a internet)

Come si vede è usata una popolazione di 16 individui, ma con il pulsante change view è possibile visualizzare un solo grafo alla volta, quello della soluzione migliore.

 L'utente può aggiungere un numero a piacere di città semplicemente cliccando col tasto sinistro del mouse all'interno di un qualsiasi grafo, dopodiché è necessario iniziare da capo la simulazione. Alle città possono essere associati dei numeri come in figura o no, a seconda che sia attivo il campo numbers.

 Una volta premuto start l'algoritmo inizia a girare, vengono cioè generate nuove soluzioni e aumentano le generazioni, il cui numero progressivo è segnalato dal campo generation. 

In ogni momento è possibile terminare l'algoritmo col tasto stop. 

Poiché la popolazione evolve in modo molto veloce è possibile visualizzarne l'evoluzione un passo alla volta col tasto step; prima di far ciò è necessario premere stop. Una volta terminata la simulazione, col tasto reset ci si riporta alla situazione di partenza ed è possibile iniziarne un'altra. 

E' possibile inoltre selezionare il tipo di crossover e di mutazione aprendo le rispettive finestre. Per il primo si può scegliere fra: 

 One point crossover 

 Two points crossover

 None 

None significa che non c'è crossover e pertanto i figli saranno la copia esatta dei genitori. La tecnica del one point nei casi in cui la codifica degli individui sia di tipo permutazionale è stata descritta in precedenza; la tecnica del two points è analoga: due parti di stringa sono prese dal primo genitore e copiate nel figlio, le rimanenti cifre in mezzo sono prese nello stesso ordine in cui compaiono nel secondo genitore . 

 Per la mutazione si può scegliere fra: 

Normal random mutation: alcune città scelte a caso vengono permutate

Random, only improving: alcune città scelte a caso vengono permutate solo se la nuova configurazione ha una fitness più alta 

Systematic, only improving: le città sono sistematicamente scelte e permutate solo se la nuova configurazione ha una fitness migliore

Random improving: come " random, only improving", ma prima viene eseguita una "normal random"  

Systematic improving: come "systematic, only improving", ma prima viene eseguita una "normal random" 

L'utente può quindi provare diverse combinazioni e vedere come cambiano le performance dell'algoritmo nei diversi casi. Come detto la complessità del problema, e quindi il numero di generazioni prima che vi sia convergenza cresce come n! se n è il numero delle città. Mentre in generale il crossover viene ritenuto il principale fattore dell'evoluzione della fitness di una popolazione, come accade in natura, in questo problema e in generale in tutti quelli combinatori sembra che la mutazione giochi un ruolo determinante. Le performance dell'algoritmo infatti migliorano sensibilmente in proporzione al grado di complessità del tipo di mutazione adottato, come è lecito attendersi dal momento che ( a parte nel primo caso, normal random) gli individui vengono effettivamente mutati solo se questo porta dei vantaggi, quindi in pratica ciò vuol dire che vi è convergenza dopo poche generazioni (circa una decina se le città sono 7-8, qualche centinaio man mano che si aumenta, contro le migliaia nel caso normal random). Inoltre la convergenza è ulteriormente accelerata a seconda che la mutazione avvenga sempre (sistematicamente) o con una certa probabilità.