Gli algoritmi genetici (GA)
15
Gli algoritmi genetici (GA) 1 Gli algoritmi genetici (GA) • Si ispirano al meccanismo dell’evoluzione • Viene creata una popolazione di individui che si riproduce ed evolve, di generazione in generazione, selezionando gli individui migliori cioè quelli che meglio si adattano ad un determinato ambiente.
description
Gli algoritmi genetici (GA). Si ispirano al meccanismo dell’evoluzione Viene creata una popolazione di individui che si riproduce ed evolve, di generazione in generazione, selezionando gli individui migliori cioè quelli che meglio si adattano ad un determinato ambiente . - PowerPoint PPT Presentation
Transcript of Gli algoritmi genetici (GA)
Gli algoritmi genetici (GA) 1
Gli algoritmi genetici (GA)
• Si ispirano al meccanismo dell’evoluzione
• Viene creata una popolazione di individui che si riproduce ed evolve, di generazione in generazione, selezionando gli individui migliori cioè quelli che meglio si adattano ad un determinato ambiente.
Gli algoritmi genetici (GA) 2
• viene generata una popolazione iniziale di individui
• mediante un meccanismo di riproduzione vengono generati nuovi individui, manipolando il materiale genetico della popolazione iniziale
• gli individui competono tra loro e quelli che meglio si adattano all’ambiente hanno maggiori probabilità di sopravvivenza e di trasmettere il patrimonio genetico alle generazioni future
• la popolazione evolve, di generazione in generazione, incrementando il numero degli individui migliori in essa presenti.
Passi salienti del processo fisico
3
Modello matematico
riproduzionecrossover, mutation individuo miglioreottimo globale
competizioneselectionadattamento all’ambientef(x), fitnessindividuox
Gli algoritmi genetici (GA)
4
NO
Reproductive cycle
Initial population
Fitness evaluation
Start
Stop criterion
satisfied?
SELECTION#1,#2
CROSSOVERpcross
MUTATIONpmut
Fully populated?
NO
YES
Genetic algorithm
Stop
YES
Gli algoritmi genetici (GA)
5
Teoria matematica
• Parallelismo implicito
• Teorema degli schemi
• Bilanciamento tra exploration ed exploitation
Gli algoritmi genetici (GA)
8
1. Codifica delle soluzioni2. Popolazione iniziale3. Calcolo della fitness4. Selezione5. Applicazione degli operatori6. Iterazione e criterio di stop
Realizzazione dell’algoritmo
Gli algoritmi genetici (GA)
9
Codifica delle soluzioni• Codifica binaria o con numeri reali.• Codifica binaria standard, codifica di Gray.• Ns: numero di bit; risoluzione discretizzazione
variabile continua• Cromosoma: unione delle stringhe binarie che
rappresentano le variabili. Ogni bit è detto gene. Il valore che può assumere il bit (0,1) è detto allele.
• La lunghezza Lc del cromosoma: Lc=Ns1+ Ns2+… +NsN
• Dimensione dello spazio di ricerca: 2Lc
Gli algoritmi genetici (GA)
10
Popolazione iniziale• La popolazione iniziale viene creata generando gli
individui in maniera casuale.• Il numero Np di cromosomi generati è la
dimensione della popolazione• Np è scelto in maniera euristica ed è dipendente
dalla natura della funzione obiettivo e dalle dimensioni dello spazio di ricerca
• Negli AG standard Np rimane fisso durante l’evoluzione
Gli algoritmi genetici (GA)
11
Fitness e funzione obiettivo• La funzione obiettivo gioca il ruolo dell’ambiente
nel corso dell’evoluzione.• funzione obiettivo = fitness dell’individuo?
Sì, in genere, a meno di scaling, ranking o normalizzazioni.
• Eventuali vincoli di eguaglianza possono essere trattati inserendo termini penalizzanti nella funzione obiettivo.
• Nell’ottimizzazione di dispositivi elettromagnetici, il calcolo della funzione obiettivo può comportare un’analisi FEM.
Gli algoritmi genetici (GA)
12
Selection• roulette wheel:
la popolazione è rappresentata mediante una ruota di roulette con i settori proporzionali alla fitness degli elementi; la pallina viene lanciata Np volte e gli elementi che hanno fitness migliore hanno probabilità maggiore di essere scelti.
• tournament selection: vengono scelti 2 individui a caso e quello tra i due
che ha la fitness migliore viene copiato nella nuova popolazione; l’operazione viene ripetuta Np volte; prima della selezione gli individui vengono mescolati (shuffle).
Gli algoritmi genetici (GA)
13
• Si può riportare nella nuova generazione l’elemento migliore della precedente popolazione: elitismo.
• Alla fine della selezione gli individui della popolazione intermedia vengono mischiati casualmente
Gli algoritmi genetici (GA)
14
Operatori genetici
• Per ogni coppia, il crossover viene applicato con probabilità Pc.
01001 110
11100 001
01001 001
11100 110 1 punto
1001 110 0
1100 001 1
1001 001 1
1100 110 02 punti
genitori figli• Crossover
Gli algoritmi genetici (GA)
15
• Mutation
• Per ogni individuo, la mutation viene applicata con probabilità Pm.
• L’operatore di crossover ricombina il materiale genetico esistente (favorendo l’exploitation). L’operatore di mutation introduce nuovo materiale genetico (favorendo l’exploration).
• Pc e Pm si scelgono in maniera euristica e in genere Pm<Pc (possono variare durante l’evoluzione).
010 0 1110 010 1 1110
Gli algoritmi genetici (GA)
16
Selection CrossoverMutation
Gli algoritmi genetici (GA)
17
Criterio di arresto• Il meccanismo di selezione, ricombinazione e
calcolo della fitness viene iterato.• L’evoluzione termina quando viene raggiunto
l’ottimo, se questo è noto.• Altrimenti l’evoluzione termina quando:
viene raggiunto il numero massimo Ng di generazioni; il numero totale Nt di valutazioni della funzione obiettivo Nt = Np * Ng
un indicatore di convergenza (uniformità della popolazione, mancanza di progressi nell’evoluzione) raggiunge un determinato valore
Gli algoritmi genetici (GA)
