Introduzione agli algoritmi genetici - areeweb.polito.it · Algoritmi genetici 2 Introduzione Gli...

Introduzione agli algoritmi genetici

Diego Nova

Algoritmi genetici 2

IntroduzioneIntroduzione

Gli Algoritmi Genetici (GA) sono procedure complesse, adattative, finalizzate alla risoluzione di problemi di ricerca e ottimizzazione e basate concettualmente sui principi che regolano l'evoluzione naturale delle specie.

L'idea che sta alla base degli AG è quindi quella di selezionarele soluzioni migliori e di ricombinarle in qualche modo fra loroin maniera tale che esse evolvano verso un punto di ottimo.


Nomenclatura

Nel linguaggio degli AG la funzione da massimizzare prende il nome di fitness (F).

Si supponga che la funzione di fitness dipenda da n variabili: F = f (x1, x2,…, xn). Un set di n valori x1, x2,…, xn appartenenti ad un certo intervallo viene detta individuo (o soluzione).

Un insieme di individui forma una popolazione

Una soluzione può essere codificata biunivocamente in codice binario (l’idea fu introdotta originariamente da J.Holland, il padre degli AG). La specifica sequenza (stringa) di 0 e 1 che costituiscono un individuo (soluzione) è detta cromosoma.


Nomenclatura (continua)

Considerando che si è in presenza di una evoluzione temporale della popolazione, si parla generazione per indicare la popolazione in un dato istante di tempo.


Principio di funzionamento

In natura gli individui si riproducono mescolando in questo modoi propri patrimoni genetici, cioè i loro cromosomi: i nuovi individui generati avranno pertanto un patrimonio genetico derivato in parte dal padre e in parte dalla madre. La selezionenaturale (cioè il riutilizzo di soluzioni buone) fa sì che riescano a sopravvivere e quindi a riprodursi solo gli individui più forti, "più adatti", cioè quelli con la fitness più elevata (più vicini all’ottimo); la fitness media della popolazione tenderà quindi ad aumentare con le generazioni, portando così la specie ad evolversi nel tempo.


Struttura di un GA

1. Definizione della generazione iniziale.Definire (anche a caso) un primo insieme di possibili soluzioni al problema in esame.

2. Valutazione di ogni soluzione e selezione selle migliori.Valutare ogni soluzione, associando a ciascuna un indicatore di qualità (o fitness) in modo da poterle ordinare.

3. Definizione di una nuova generazione.Definire un nuovo gruppo di soluzioni modificando opportunamente le soluzioni con qualità elevata, in modo da favorire lo sviluppo a scapito di quelle peggiori.


Struttura di un GA (continua)

4. Conclusione dell’elaborazione.Se il numero di iterazioni stabilite è stato raggiunto o la qualità della migliore soluzione disponibile è accettabile si può terminare l’elaborazione, altrimenti si ritorna al passo 2 per definire un nuovo gruppo di soluzioni.


Selezione

La selezione di un individuo dipende dal suo valore di fitness (cioè quanto l’individuo è “buono” a risolvere il problema): un valore più alto di fitness corrisponde ad una maggiore possibilità di essere scelto come genitore (parent) per creare la nuova generazione. Uno dei criteri più utilizzati è quello di Holland che attribuisce una probabilità di scelta proporzionale al fitness. Grazie al meccanismo della selezione, solo gli individui migliori hanno la possibilità di riprodursi e quindi di trasmettere il loro genoma alle generazioni successive.


Crossover e Mutazione

Per la creazione di nuovi individui ad ogni generazione si utilizzano due operazioni ispirate dall’evoluzionismo biologico: il crossover e la mutazione. Una volta individuati una coppia di genitori con il meccanismo della selezione, i loro genomi possono andare incontro a ciascuna delle due operazioni con probabilità rispettivamente Pcross (probabilità di crossover per coppia di individui, detta crossover rate) e Pmut (probabilità di mutazione per gene, detta mutation rate).


1010 001110 0011 010010

1010 010010 0011 001110

One Point Crossover

È la tecnica più semplice, date due stringhe viene individuato un punto che separa ciascuna di esse in due parti, in seguito si ricombinano come mostrato in figura.La probabilità che si verifichi il cross over è in genere abbastanza alta (in caso contrario è possibile avere figli che sono uguali ai genitori).

Genitori

Figli

Punto di crossover


Standard Corssover

Simile al precedente ma si selezionano due punti di taglio suddividendo la stringa in tre sottostringhe.

01 1001 00 10 0101 10

01 0101 00 10 1001 10


Order Corssover

Come lo standard crossover lavora su coppie di cromosomi. I due punti di taglio sono scelti a caso. Ciascum figlio è costruito prendendo la crossing section (la parte centrale del taglio) di un genitore e riempiendo gli spazi rimanendi con i simboli mancantipresi nell’ordine in cui compaiono nell’altro genitore.

CA BDHF EG DH CABE GF

HF CABE GD AE BDHF GC


Order Corssover (continua)

Questa interpretazione del cromosoma ben si adatta a problemi diordinamento quali il TSP dove, è possibile leggere il cromosoma cominciando da un punto qualsiasi, ma soprattutto, questo tipo di crossover mantenendo l’ordinamento garantisce l’ammissibilità delle nuove soluzioni.


Mutazione

Data la probabilità di mutazione, per ciascuna cifra di ogni individuo si estrae un numero casuale q: se q ≤ Pmut, la cifra binaria viene scambiata (1 diventa 0 e 0 diventa 1);


Il problema del commesso viaggiatore (TSP)

Vediamo ora l’applicazione di un algoritmo genetico al noto problema di ottimizzazione combinatoria.

Siano date n città (nodi del grafo) collegate da strade (archi del grafo). Il valore di un arco è la lunghezza della strada (o costo di viaggio) che quell’arco rappresenta. Un commesso viaggiatore si propone di visitare una ed una sola volta ciascuna città (partendo da una qualsiasi e ritornandovi), in modo da avere un percorso totale di lunghezza minima (o costo minimo).


∞31686F3∞5728E15∞494D674∞37C8293∞5B68475∞AFEDCBA

Il problema del commesso viaggiatore (TSP) (continua)

La matrice dei costi è la seguente:

La scelta della rappresentazione degliindividui costituisce un problemanon banale.Per questo problema si può pensaredi rappresentare un individuo conuna permutazione delle sei città.Es. p4=(F,E,A,B,D,C)

Mentre la funzione di fitness è ovvia:Dato un individuo il valore della fitness è inversamente proporzionale alla lunghezza del cammino descritto dall’individuo.



La popolazione iniziale (o prima generazione) P(t=0) è costituita dai seguenti individui (soluzioni ammissibili):

p1=(A, B, C, D, E, F) p2=(B, C, A, F, D, E) p3=(C, B, F, A, D, E)p4=(F, E, A, B, D, C) p5=(B, F, E, A, C, D) p6=(A, C, F, B, D, E)p7=(A, B, C, D, F, E)

Cioè P(0)=(p1, p2, p3, p4, p5, p6, p7)a cui sono associati i rispettivi costi di percorso:c1=26 c2=24 c3=29 c4=31 c5=35 c6=43 c7=20

Si può osservare che p1 e p7 sono gli individui con la fitness maggiore.



Definiamo l’algoritmo che risolve il problema:

1. individuo GA(individuo popolazione[], float Pmut) {2. individuo figlio[2], padre, madre;3. while(condizione_di_terminazione==FALSE) {4. SelezionaGenitori(popolazione, padre, madre);5. OrderCrossover(padre, madre, figlio);6. if( random()<=Pmut ) {7. Muta(figlio);8. }9. Aggiorna(popolazione, figlio);10. // modifica (se necessario la condizione di

terminazione11. }12. return Best(popolazione);13.}



1. individuo GA(individuo popolazione[], float Pmut) {2. individuo figlio[2], padre, madre;3. while(condizione_di_terminazione==FALSE) {… …11. }12. return Best(popolazione);13.}

La funzione riceve come parametri la popolazione iniziale e la probabilità di mutazione e ritorna il miglior individuo della popolazione finale (Best(popolazione)) nel momento in cui la condizione di terminazione è stata raggiunta (come già è stato detto questa può dipendere dal numero di iterazioni, del tempo trascorso…).



SelezionaGenitori(popolazione, padre, madre);

È una funzione che con qualche regola (anche casuale o euristica) seleziona due individui (padre e madre) adatti alla riproduzione dalla popolazione.Nel nostro la regola sarà la scelta dei due individui con la fitness più alta.

OrderCrossover(padre, madre, figlio);

Esegue l’operatore genetico di Order Crossover per creare i due figli (figlio[0] e figlio[1]).



if( random()<=Pmut ) {Muta(figlio);

}

In una percentuale proporzionale alla probabilità di mutazione di un figlio applica l’operatore genetico di mutazione agli individui appena generati.Anche in questo caso la mutazione può essere definita in svariati modi, per esempio:1. Togliere un elemento a caso e reinserirlo in un’altra

posizione (C, A, F, B, E, D) (C, F, B, E, A, D)2. Togliere a caso una sottostringa e reinserirla in un’altra

posizione (C, A, F, B, E, D) (C, E, D, A, F, B)



3. Togliere a caso una sottostringa, invertirla e reinserirla nellastessa posizione (C, A, F, B, E, D) (C, B, F, A, E, D)

4. …

Aggiorna(popolazione, figlio);Questa funzione aggiorna la popolazione attuale “trasformandola”nella generazione successiva P(t) P(t+1).L’aggiornamento può seguire le più svariate regole, nel nostro esempio specifico si sceglierà di eliminare ad ogni passo i due individui meno “adatti” (cioè quelli con la fitness più bassa).In realtà questa è una semplificazione in quanto, generalmente, l’intera popolazione si riproduce (secondo la probabilità Pcross), aggiornandosi interamente ad ogni generazione.



Ora che si ha la completa conoscenza del problema si può provare a far girare l’algoritmo per vederne il comportamento “genetico”.



Iterazione (generazione) 1:

Si entra nel ciclo

1. individuo GA(individuo popolazione[], float Pmut) {2. individuo figlio[2], padre, madre;3. while(condizione_di_terminazione==FALSE) {4. …

c4=31p4=(F, E, A, B, D, C)c7=20p7=(A, B, C, D, F, E)c3=29p3=(C, B, F, A, D, E)c6=43p6=(A, C, F, B, D, E)c2=24p2=(B, C, A, F, D, E)c5=35p5=(B, F, E, A, C, D)c1=26p1=(A, B, C, D, E, F)




Si selezionano i genitori

2. …3. while(condizione_di_terminazione==FALSE) {4. SelezionaGenitori(popolazione, padre, madre);5. …





Si generano i figli

3. …4. SelezionaGenitori(popolazione, padre, madre);5. OrderCrossover(padre, madre, figlio);6. …




OrderCrossover(…) {padre = (B C A F | D | E) , madre =(A B C D | F | E)

figlio[0] = (A B C F | D | E) , figlio[1]=(B C A D | F | E)}





Supponiamo per semplicità che non ci siano mutazioni (non entriamo nell’if)

5. …6. if( random()<=Pmut ) {7. Muta(figlio);8. …





Si aggiorna la popolazione

8. …9. Aggiorna(popolazione, figlio);10. …




Aggiorna(…) {Si calcola la funzione di costo per i figlifiglio[0]: (A B C F D E) 5+3+6+1+5+4=24figlio[1]: (B C A D F E) 3+7+4+1+3+2=20…

}




Aggiorna(…) {…Questo è un caso fortunato in cui entrambi i figli entrano a far parte della popolazione. Gli individui da eliminare pertanto risultano essere p6 avendo un costo di 43 e p5 avendo un costo di 35.…

}




Aggiorna(…) {…A cui sostituiamo figlio[0] e figlio[1]

}

c4=31p4=(F, E, A, B, D, C)c7=20p7=(A, B, C, D, F, E)c3=29p3=(C, B, F, A, D, E)c6=20p6=(B, C, A, D, F, E)c2=24p2=(B, C, A, F, D, E)c5=24p5=(A, B, C, F, D, E)c1=26p1=(A, B, C, D, E, F)




Siamo alla seconda generazione e già si può notare che gli individui si sono “adattati” ed iniziano ad avvicinarsi alla soluzione ottima del problema.

2. …3. while(condizione_di_terminazione==FALSE) {4. SelezionaGenitori(popolazione, padre, madre);5. …

c4=31p4=(F, E, A, B, D, C)c7=20p7=(A, B, C, D, F, E)c3=29p3=(C, B, F, A, D, E)c6=20p6=(B, C, A, D, F, E)c2=24p2=(B, C, A, F, D, E)c5=24p5=(A, B, C, F, D, E)c1=26p1=(A, B, C, D, E, F)



Si reitera il procedimento finchè la condizione di terminazione non è verificata nel qual caso si ritorna l’individuo “migliore”della generazione a cui si è giunti, il quale è anche la migliorsoluzione trovata fin’ora.


Conclusioni

Gli agloritmi genetici possiedono i seguenti pregi:• Forniscono sempre una soluzione• Sono facili da realizzare• Possono essere applicati a diverse problematiche• Permettono di scegliere un trade-off tra tempo di calcolo e

precisione

Ma presentano anche degli svantaggi come per esempio:• Non garantiscono che la soluzione offerta dopo un certo

numero di iterazioni sia quella ottima• La numerosità della generazione, la frequenza di applicazione

degli operatori genetici, e tutti gli altri paramenti possono essere determinati solo attraverso prove, valutando le performance e la qualità dei risultati offerti.


Per saperne di più

LIBRI• J.H.Holland. Algoritmi genetici. Le Scienze, n.289, 1992• L.Davis. Handbook of Genetic Algorithms. Van Nostrand Reinhold, 1991• J. H. Holland. Adaptation in Natural and Artificial Systems. The University

of Michigan Press, 1975• M. Mitchell. An Introduction to Genetic Algorithms. MIT Press, 1996.


Per saperne di più

SITI INTERNET• http://www.forumteorema.com/ Contieni riferimenti matematici e

filosofici sugli AG e l'Intelligenza Artificiale in genere• http://web.tiscali.it/vitaartificiale/algoritm.htm Contiene una spiegazione

teorica sugli AG in generale, e una loro applicazione al campo dell'analisi finanziaria

• http://www.dia.uniroma3.it/~patrigna/seminari/learning/ Una raccolta di lucidi sull'apprendimento delle macchine tramite AG

• http://cs.felk.cvut.cz/~xobitko/ga/ Contiene diverse applet in java con esempi di funzioni in 2D e 3D e TSP risolte con gli AG

• www.geocities.com/CapeCanaveral/Lab/5337/ Sito di un ricercatore italiano che contiene numerosi link

• http://www.aic.nrl.navy/mil/galist Contiene una ricca raccolta di codici sorgenti in C, C++, fortran ,VB ecc. di programmi che implementano AG, nonchè una lista di link

• http://www.aridolan.com/oltre che sugli AG,contiene interessanti riferimenti sulla vita artificiale in genere

Introduzione agli algoritmi genetici - areeweb.polito.it · Algoritmi genetici 2 Introduzione Gli...

Documents

Transcript of Introduzione agli algoritmi genetici - areeweb.polito.it · Algoritmi genetici 2 Introduzione Gli...