Metodi e tecniche di ottimizzazione innovative per...

Metodi e tecniche diottimizzazione innovative per

applicazioni elettromagneticheAlgoritmi stocasticiParte 1 Tecniche evoluzionistiche

M. Repetto

Politecnico di Torino, Dip. Ingegneria Elettrica Industriale

Metodi e tecniche di ottimizzazione innovative per applicazioni elettromagnetiche – p. 1/26

Contents

tecniche evoluzionisticheevolution strategygenetic algorithm

metodi collettiviant colonyparticle swarm

artificial immune systems


Algoritmi stocastici (1/2)

Diversi algoritmi di ottimizzazione stocastica sono statisviluppati implementando analogie con fenomeninaturali

lo studio dell’artificial life ha fornito diversi spunti per ilproblem solving, tutti basati su popolazioni di individuiinteragenti la cui dinamica e’ regolata da leggi semplici:

evoluzione di una specie biologica che modifica neltempo le sue caratteristiche per affrontare al megliole interazioni con l’ambiente in cui vivecomportamento cooperativo di un gruppo checonsente di affrontare l’interazione con l’ambientemeglio di quanto non possa fare il singolosistema di difesa di un organismo che devedifendersi da attacchi biologici in forma semprediversa


Algoritmi stocastici (2/2)

Vengono presentati tre diverse classi di algoritmitecniche evoluzionistiche: basate sulla competizionetra gli individui della popolazione Evolution StrategyES, Genetic Algorithm GAtecniche collettive: basate sulla collaborazione esullo scambio di informazioni tra individui ParticleSwarm Optimization PSO, Ant Colony ACOtecniche immuni: basate sulla massimadiversificazione degli individui Artificial ImmuneSystems AIS


Tecniche Evoluzionistiche

All’interno delle tecniche evoluzionistiche si evidenzianodue metodi diversi per origine e struttura

Evolutionary Strategy: sviluppate in ambiente dilingua tedesca1965 Rechenberg: Cybernetic solution path of an experimental problem

Genetic Algorithm: sviluppati in ambito americano1966 Fogel Owens Walsh Artificial intelligence through simulated evolution

1975 Holland, Adaptation in natural and artificial systems

nonostante facciano riferimento alla evoluzioneDarwiniana basata sulla sopravvivenza del piu’ adattola loro implementazione e’ piuttosto diversa

quasi 30 anni dopo il loro comparire sulla scena, le duetecniche vengono spesso denominate evolutionarycomputation


Evoluzionistici: tratti comuni (1/3)

Popolazione: gruppo di individui che rappresenta unagenerazione della specie, un campionamentotemporale durante la sua dinamica

un individuo e’ un punto nello spazio dei parametri X

eventualmente all’individuo possono essereassociate altre caratteristiche

Fitness: misura della capacita’ dell’individuo disopravvivere nell’ambiente (per un coniglio la velocita’,per un falco la vista etc.), la fitness e’ la funzioneobiettivo

Corredo genetico o genetic outfit: caratteristichedel’individuo che vengono trasmesse alla suadiscendenza



Operatori genetici: meccanismi attraverso i quali vieneprodotta la successiva generazione a partire dallaattuale, devono garantire un grado di casualita’ allanuova generazione

condivisione del corredo genetico: meccanismo allabase di tutta la riproduzione sessuata (operatorebinario o superiore)mutazione del corredo genetico: evento casualedovuto ad errori (entropizzazione) nella copia delmateriale genetico (operatore unario)



Riproduzione : meccanismo attraverso cui un individuosi riproduce identico nella generazione successiva

Selezione : operazione decisionale attraverso cui sideterminano gli individui della generazione successiva,puo’ essere:

deterministica: solo i migliori sopravvivonoprobabilistica: i migliori hanno piu’ elevateprobabilita’ di sopravivenza


Evolutionary Strategy (1/3)

Rappresentazione degli individui: gli individui vengonorappresentati come vettori floating point all’interno deldominio dl problema

ogni individuo ha associato altre informazioni comeampiezza di mutazione etc.

Popolazione: µ genitori si combinano tra di loro dandoluogo a λ discendenti

Operatori genetici: i genitori si riproducono attraversoX-over:xA = (1 − α) ∗ x1 + α ∗ x2 xB = α ∗ x1 + (1 − α) ∗ x2

mutazionexnew = xold + r ∗ δold

gli operatori vengono applicati in sequenza



Ampiezza di mutazione: ogni individuo porta associataun’ampiezza di mutazione δold

l’ampiezza di mutazione viene ereditata dalleconfigurazioni discendentiviene modificata dal tasso di successo delleconfigurazioni

tasso di successo alto ⇒ aumento di δold

tasso di successo basso ⇒ diminuzione di δold

alcune implementazioni associano all’individuo ancheuna direzione di ricerca che si e’ rivelata fruttuosa inpassato



Selezione: la selezione e’ effettuata in modostrettamente deterministico facendo sopravvivere tra inuovi individui solo i µ con fitness piu’ elevata

esistono diverse tecniche per determinare lagenerazione successiva

tecnica (λ, µ): la selezione viene effettuata solo tra iλ discendenti, ogni individuo vive solo unagenerazionetecnica (λ + µ): la selezione viene effettuataconsiderando contemporaneamente genitori e figli,(fattore longevita’)

Deterioramento della fitness: con la tecnica (λ, µ) siaccetta un peggioramento della fitness, mentre nella(λ + µ) il miglior valore ottenuto sopravvive sempre


Genetic Algorithm (1/6)

Rappresentazione individui: gli individui vengonorappresentati mediante stringhe di numeri binari,eventualmente ottenute per conversione da valori reali

x1L = 0, x1U = 0.1, Number of digit = 8(28 = 128)

base1 = (0.1 − 0) /127 = 7.87 ∗ 10−4,

x1 = 0.05 ⇒ b1 = int (0.05−0)7.87∗10−4 = 64 ⇒ 01000000

x2L = 0.25, x2U = 1, Number of digit = 10(210 = 512)

base2 = (1 − 0.25) /512 = 1.46 ∗ 10−3,

x2 = 0.3 ⇒ b2 = int (0.3−0.25)1.46∗10−3 = 34 ⇒ 0000001010

rappresentazione vettore x = {x1, x2}individuo stringa 18 bit→ 010000000000001010



Popolazione: la popolazione e’ formata da un numeroprefissato di individui

Mating pool: popolazione intermedia di genitori cheviene selezionata probabilisticamente in base al valoredella fitness

il procedimento di selezione della mating pool consentedi prendere piu’ volte lo stesso individuo



Roulette wheel: ad ogni configurazione e’ assegnatauna probabilita’ di sopravvivenza data da:

pi = fi∑

kfk

10 individui totali 5 individui selezionati

Deterioramento della fitness: in maniera casuale laconfigurazione migliore potrebbe non essere scelta



Operatori genetici: una volta selezionata la popolazionedi genitori vengono applicati gli operatori cheproducono i nuovi individui:

cross-over: due genitori mescolano il loro corredogenetico dando luogo a due individui figligenitore 1→ 01010101 l 100100100genitore 2→ 01010000 l 111100100

offspring 1→ 01010000 l 111100100offspring 2→ 01010000 l 100100100

mutazione: un bit della configurazione vienecambiato in modo casuale:genitore 1→ 01010101100100100offspring 1→ 01010100100100100

gli operatori vengono applicati in percentuale fissata apriori Metodi e tecniche di ottimizzazione innovative per applicazioni elettromagnetiche – p. 15/26


Selezione: la selezione avviene nella scelta dellamating pool quindi in maniera diversa da quanto fattonella ES

Schema theorem: la convergenza del metodo vienedimostrata attraverso il teorema che analizzal’evoluzione e la crescita nella popolazione delleconfigurazioni migliori

building block: supponendo che le caratteristiche delleconfigurazioni migliori si concentrino in alcune regionidella stringa, la probabilita’ che queste passino allegenerazioni successive e’ crescente durante ilprocedimento (selective pressure)

configurazione 1→ 01111100100100configurazione 2→ 11111111000110



l’operatore x-over e’ quello che meglio garantisce di nondistruggere questi blocchi di informazione ed e’ quindi ilpiu’ utilizzato

l’operatore mutazione serve a mantenere l’esplorazionedello spazio dei parametri generando nuoveconfigurazioni

coding: la codifica binaria da un’importanza gerarchicaalla posizione dei bit cosi’ che un flip in una posizionepuo’ portare ad una grande modifica dellaconfigurazione

dato che in natura si vede che le mutazioni piu’ utilisono quelle che creano piccole modifiche si preferisceuna codifica in cui il flip di un bit porta ad unaconfigurazione adiacente (Gray coding)


Confronto ES/GA (1/2)

ES GAfloating point representation binarydeterministic selection probabilistic

changing genetic operators fixed

selection

µ

λ

µ

genetic

operators

parents

offsprings

new individuals

selection

genetic

operators

N old individuals

mating pool

N new individuals


Selective pressure (1/3)

le tecniche evoluzionistiche sono ottimizzatori globali edevono quindi ricercare la regione in cui questo si trovaall’interno del dominio (exploration )

la pressione selettiva imposta dall’algoritmo fasolitamente predominare pero’ l’exploitation rispettoall’exploration

la sopravvivenza dei migliori fa si che durante ilprocesso si possa arrivare ad un inbreeding dellapopolazione, cioe’ una riduzione del contenuto geneticodella mating pool

questo difetto dell’evoluzione in natura viene sorpassatoda altri fenomeni interagenti con la specie biologica



funzione multiJamba

f(x) = −1 −Ndim∑

j=1

(

x2j + cos (2π · xj)

)

0 20 40 60 80 100

1

2

3

4

5

6

exploitation

exploration

3D MultiJamba function 8 maximadata averaged on 100 runs

# of

max

ima

generation



per contenere l’addensamento della popolazione sidevono valutare gli individui non solo in base alla lorofitness bensi’ anche in base al loro corredo genetico(posizione nello spazio dei DoF )

tra le modifiche proposte per ridurre la convergenzaprematura dell’algoritmo si possono citare:

fitness sharingclustering


Fitness sharing (1/2)

l’applicazione delle tecniche evoluzionistiche comportaun addensamento della popolazione intorno a regionicaratterizzate da buoni valori di fitness

in natura questo si verifica quando alcune circostanzenaturali consentono ad una popolazione di espandersigrazie ad esempio ad un’abbondanza di risorse.

In natura si ottiene un bilanciamento grazie all’equilibriodi due fenomeni:

abbondanza di risorse ⇒ aumento densita’popolazione (azione positiva)aumento densita’ popolazione ⇒ diminuzionerisorse pro-capite (azione negativa)


Fitness sharing (2/2)

la tecnica del fitness sharing implementa il meccanismodi azione negativa all’affollamento attraverso unamodifica della OF

individui molto vicini tra loro vedono ridotta la lorofitnessregioni molto affollate diventano cosi’ menopromettenti e l’algoritmo puo’ fare emergere altrezone

la modifica rende quindi meno conveniente l’exploitationa favore di una maggiore exploration delo spazio


Clustering (1/3)

la tecnica del clustering si propone di mettere inevidenza l’addensamento degli individui in alcuneregioni dello spazio


Clustering (2/3)

il numero di individui per cluster puo’ essere ridottofavorendo cosi’ una parita’ di trattamento a diverseregioni

scegliendo ad esempio un solo individuo per ognicluster la procedura di selezione della mating pool puo’prendere in considerazione individui la cui fitness e’ nonelevata ma che rappresentano potenzialmente unanuova specie emergente

in entrambe le tecniche il prodotto del metodo non e’ unsingolo individuo, bensi’ una distribuzione di individui supiu’ regioni


Clustering (3/3)

funzione multiJamba

f(x) = −1 −Ndim∑

j=1

(

x2j + cos (2π · xj)

)

0 20 40 60 80 100

1

2

3

4

5

6

without clustering with clustering

3D MultiJamba function 8 maximadata averaged on 100 runs#

of m

axim

a

generation


Metodi e tecniche di ottimizzazione innovative per...

Documents

Transcript of Metodi e tecniche di ottimizzazione innovative per...