Gli algoritmi genetici (GA)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)
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.
L’annealing è un processo termico per mezzo del quale un materiale allo stato liquido riesce a solidificarsi nello stato di minima energia.
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.
Gli algoritmi genetici (GA) * Passi salienti del processo fisico
dove T è la temperatura e kB è la costante di Boltzmann
Modello matematico
* riproduzione crossover, mutation individuo migliore ottimo globale competizione selection adattamento all’ambiente f(x), fitness individuo x Gli algoritmi genetici (GA)
Probabilità di accettazione dello stato j alla temperatura T
* NO Reproductive cycle Initial population Fitness evaluation Start Stop criterion satisfied? SELECTION #1,#2 CROSSOVER pcross MUTATION pmut Fully populated? NO YES Genetic algorithm Stop YES Gli algoritmi genetici (GA)
Teoria matematica
* Gli algoritmi genetici (GA) Parallelismo implicito
Teorema degli schemi
Bilanciamento tra exploration ed exploitation
Ovviamente questa affermazione è di scarsa utilità ai fini dell’implementazione del Simulated Annealing come algoritmo di ottimizzazione
* Gli algoritmi genetici (GA)
* Gli algoritmi genetici (GA)
Codifica delle soluzioni
Popolazione iniziale
Calcolo della fitness
Selezione
Applicazione degli operatori
Iterazione e criterio di stop
* Gli algoritmi genetici (GA) Realizzazione dell’algoritmo
Codifica delle soluzioni
* Gli algoritmi genetici (GA) 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
Popolazione iniziale
* Gli algoritmi genetici (GA) 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
Fitness e funzione obiettivo
* Gli algoritmi genetici (GA) 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.
Selection
* Gli algoritmi genetici (GA) 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).
* 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)
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 0 2 punti genitori figli Crossover
Gli algoritmi genetici (GA)
* 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
* Selection Crossover Mutation Gli algoritmi genetici (GA)
Criterio di arresto
* Gli algoritmi genetici (GA) 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
Comments