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)