Algoritmi euristici ed evolutivi per l'ottimizzazione · Si basano sulla teoria darwiniana...

IntroduzioneAlgoritmi genetici

Ant Colony OptimizationParticle Swarm Optimization

Considerazioni finali

Algoritmi euristici ed evolutivi perl’ottimizzazione

Marco Baioletti

Dipartimento di Matematica e InformaticaUniversità degli Studi di Perugia

Via Vanvitelli, Perugia

17 febbraio 2009 / GALN 2009

Marco Baioletti Alg. Eurist. ed Evolut. per l’Ottimizzazione




Sommario

1 Introduzione

2 Algoritmi genetici

3 Ant Colony Optimization

4 Particle Swarm Optimization

5 Considerazioni finali





Algoritmi ispirati da fenomeni naturali

La Natura offre una vastissima gamma di esempi dicapacità di ottimizzazioneDa un lato i meccanismi evolutivi naturali portano allacreazione di individui particolarmente adatti al loro habitatDall’altro esseri viventi estremamente semplici sono ingrado insieme di svolgere compiti complessi (intelligenza“collettiva”)Molti modelli sono stocastici e danno luogo ad algoritmirandomizzatiOvviamente solo alcuni aspetti naturali sono realmenteinteressanti dal punto di vista algoritmico





Sommario

1 Introduzione









Cenni Storici

Studiati in maniera approfondita per la prima volta daHolland (1975)Delineati a grandi linee già nell’articolo di TuringComputing Machinery and Intelligence (1950)Molto utilizzati e studiati sia dal punto di vista teorico cheapplicativoUsando una rappresentazione binaria si potrebberoapplicare a qualsiasi problema di ottimizzazioneSi basano sulla teoria darwiniana dell’evoluzione





Selezione naturale

Principio darwiniano della selezione naturale:sopravvivenza del più adattoRiproduzione: formazione di nuovi individui che ereditano ilpatrimonio genetico dai genitoriMutazioni genetiche casuali: indispensabili per l’evoluzionedella specie”Scopo”: ottenere popolazioni di individui adattiall’ambiente





Ingredienti per gli algoritmi geneticiRappresentazione

Individui rappresentati mediante il loro patrimonio genetico(genotipo)Cromosoma: stringa di lunghezza fissa LOgni simbolo (gene) è preso da un alfabeto finito dielementi (alleli)Possibile presenza di vincoli: non tutte le stringherappresentano cromosomi validi





Ingredienti per gli algoritmi geneticiFitness

Definizione di una funzione fitness fIndividui con alta fitness sono i più adatti all’ambiente:hanno maggiori probabilità di sopravvivere e di riprodursiScopo dell’AG: trovare l’individuo (o gli individui) con lafitness maggioreLa fitness potrebbe essere diversa dalla funzione damassimizzare (essere una trasformata monotonacrescente)





Ingredienti per gli algoritmi geneticiPopolazione

La popolazione viene inizializzata in qualche modo (adesempio con N individui generati a caso)Il numero di individui è mantenuto fissoLa popolazione è manipolata per un certo numero digenerazioni mediante

SelezioneRiproduzioneMutazione





Ingredienti per gli algoritmi geneticiSelezione

La selezione avviene in modo probabilistico in base allafitnessSi estraggono N elementi secondo la distribuzione diprobabilità

πi =f (i)∑j f (j)

Si creano N2 coppie

Tanti altri possibili schemi di selezione





Ingredienti per gli algoritmi geneticiRiproduzione/Crossover

Ogni coppia di elementi produce due nuovi “figli”Ogni figlio eredita parte del patrimonio da ognuno dei duegenitoriLo schema più usato e più semplice è il crossover ad unpuntoSi sceglie un punto I a caso tra 1 e LUn figlio prende i geni da 1 a I-1 da un genitore e il restodall’altroL’altro figlio al contrario





Esempio di crossover ad un punto

Genitore 1=ABBBCDAC Genitore 2=BAAAADDAScelgo il punto 4Genitore 1 ABBBCDAC Genitore 2 BAAAADDAFiglio 1 ABBAADDA Figlio 2 BAABCDAC





Ingredienti per gli algoritmi geneticiCrossover

Sono possibili molti altri operatori di crossover (a due punti,ecc.)Particolare attenzione nel caso di presenza di vincoliAltro schema diffuso: selezione a caso tra i due genitoriGenitore 1 ABBBCDAC Genitore 2 BAAAADDAFiglio 1 AABAADAA Figlio 2 BBABCDDC





Ingredienti per gli algoritmi geneticiMutazione

Si sceglie a caso una o più posizioni dei cromosomi “figli” esi alterano casualmenteFiglio 1 AABAADAA Figlio 2 BBABCDDCFiglio 1 ABBCADDA Figlio 2 DAABCDAC

Particolare attenzione nel caso di presenza di vincoli





Uno schema di algoritmo genetico

init_population()for i:=1 to max_gen

evaluation()selection()crossover()mutation()replacement()

endreturn best element





Parametri

pc probabilità con cui applicare il crossoverpm probabilità con cui applicare la mutazioneN dimensione popolazionemax_gen numero di generazioni. . .





Applicazioni

Esistono un numero impressionante di applicazioni deglialgoritmi geneticiSi possono usare sia per l’ottimizzazione di funzioni avariabile reale sia per ottimizzazione combinatoricaGli algoritmi genetici sono anche stati implementati perproblemi decisionali (ad esempio SAT)





AG e TSP

Un cromosoma è un elenco di L = n città (senza duplicati)La fitness è una qualsiasi funzione monotona decrescentedella lunghezza del percorsoIl problema è come scegliere gli operatori di crossover (emutazione)Dai due genitori (123456) e (532146) si potrebberogenerare i due figli (123146) e (532456) che non sonopermutazioni





AG e TSPPossibili soluzioni

“Riparare” cromosomi non validi“Eliminare” cromosomi non validiAccettare (ma penalizzare) cromosomi non validiUsare operatori di crossover “ad hoc”Cambiare rappresentazione





AG per ottimizzazioni numeriche

Per massimizzare una funzione di una o più variabili reali(soggetta a vincoli) non conviene usare unarappresentazione binaria con crossover e mutazione“classici”I cromosomi sono invece numeri in virgola mobileUn operatore di crossover aritmetico è la media pesata deigenitoriUn operatore di mutazione è la mutazione non–uniforme

x ′k = xk + ∆(t , xk )

ove ∆ è un numero casuale chegarantisce che x ′

k cada nell’intervallo di definizioneha maggiore probabilità di assumere valori vicini allo 0





Giustificazioni teoriche

Esistono giustificazioni teoriche per spiegare il buoncomportamento degli AGLa più semplice giustificazione usa il cosiddetto Teoremadello schemaUno schema per cromosomi binari è una stringa di 0,1, ?(? rappresenta 0 o 1)Il teorema dice che buoni schemi tendono ad esseresempre più presenti nella popolazione





Sommario

1 Introduzione









Cenni storici

Ideata da Dorigo nei primi anni ’90 a partire da studi sulcomportamento di colonie di formiche “reali”Utilizzato in molti problemi di ottimizzazione combinatoricaSi basa sul concetto di stigmergia





Stigmergia

Le formiche quando si muovono rilasciano sul terreno ilferomoneNella ricerca del cibo tendono a seguire percorsi conmaggior quantità di feromoneAvendo trovato il cibo, quando rientrano al nido rilascianouna quantità maggiore di feromoneIl feromone evapora





Feromone assente





All’inizio le formiche si muovono a caso





Quelle che scelgono il percorso più breve arrivano(ovviamente) prima al cibo





Tornando indietro rinforzano la traccia che sarà seguita da altreformiche





Formiche artificialiGrafo

Scopo “ideale”: trovare il massimo della funzionef : S → RGli elementi di S sono assimilabili a percorsi in un grafo(N,A)

N è l’insieme degli statiA è l’insieme delle transizioni ammissibili(opzionale) crs è il costo della transizione r → sΩ è l’insieme dei vincoli del problema (restrizioni suipossibili percorsi)





Formiche artificialiFormiche e terreno

Ogni “formica”parte da uno stato inizialeha una condizione di terminazione del percorsocrea un elemento di S un componente alla voltaha una memoria in cui tiene traccia del proprio percorso

Colonia di m formicheIl “terreno” consiste in una funzione τ : A→ Rτrs è la quantità di feromone depositata sulla transizioner → s





Formiche artificialiMovimento delle formiche

La formica si muove sul grafo in maniera probabilistica

ps|r =τα

rsηβrs∑

z ταrzη

βrz

ηrs è una funzione euristica: indica quanto è “promettente”passare da r a sα e β sono parametri di importanza





Formiche artificialiAggiornamento del feromone

Il feromone può essere aggiornato“step–by–step”: durante la costruzione della soluzionein maniera “differita”: una volta costruita la soluzioneτrs ← τrs + ∆τrs (la quantità è proporzionale alla bontàdella soluzione)dal “demone”: si aggiornano solo i feromoni dellecomponenti che partecipano alle migliori soluzioni

Il feromone evapora: τrs ← (1− ρ)τrs





Descrizione di un semplice algoritmo ACO

init_phero()while not criterion

for i = 1 to minit_ant(i)while not terminate(i)

choose_component(i)update_state(i)update_phero_step(i)

endupdate_phero_delayed(i)

endupdate_phero_daemon()

end





Applicazioni

TSPQAPJob–shop schedulingAntNetVehicle routingColorazione di grafi. . .





ACO e TSP

Componenti: archi tra cittàVincolo: ogni formica deve visitare tutte le città una solavoltaηij = 1

dij(dij distanza euclidea)

Aggiornamento del feromone ∆kij = 1

L+





Varianti

Ant System: prime versioni di ACO, aggiornamento solodifferitoAnt Colony System:

scelta del componente: con probabilità q quello chemassimizza τα

rsηβrs, altrimenti a caso con prob.

proporzionale a ταrsη

βrs

aggiornamento del feromone mediante demone (migliorisoluzioni)aggiornamento del feromone step–by–step condiminuzione (per favorire l’esplorazione)

Max–Min Ant System: feromone limitato in [τmin, τmax ] eaggiornato mediante demone (global best e iteration best)Hypercube Framework: feromone limitato in [0,1]





Sommario

1 Introduzione









Cenni storici

Ideata da Kennedy e Eberhart nel 1995Si ispira al comportamento degli stormi di uccelli, banchi dipesci, sciami di insettiModelli inizialmente studiati in ambiti diversidall’ottimizzazione

Computer GraphicsModelli comportamentali di gruppi di animali

Adatto ad ottimizzazione numerica





Sciami

Il comportamento di uno stormo è molto complessoCoordinamento senza leader, subentrano fattori dicomunicazione e di imitazioneUn modello semplice usa le seguente regole

1 Separazione: evitare collisione con i vicini (repulsione acorto raggio)

2 Allineamento: puntare verso la posizione media dellostormo

3 Coesione: puntare verso la posizione media dei vicini(attrazione a lungo raggio)





Particelle

La particella i al tempo t assume una posizione X ti ∈ R

D euna velocità V t

i ∈ RD

Esiste una funzione di fitness f : S → R, ove S ⊂ RD, chevaluta la bontà della posizione delle particelleOgni particella ha una memoria in cui tiene traccia dellamigliore posizione raggiuntaOgni particella conosce la migliore posizionecorrentemente assunta dai suoi vicini (comunicazione traparticelle)Perciò è in grado di ricordare la migliore posizioneraggiunta dai suoi vicini





Aggiornamento velocità e posizione

P ti migliore posizione raggiunta dalla particella i

Bti migliore posizione raggiunta da particelle dai vicini di i

velocità

V t+1ij = V t

ij + φ1r1(P tij − X t

ij ) + φ2r2(Btij − X t

ij )

posizioneX t+1

ij = X tij + V t+1

ij





Aggiornamento velocità e posizioneInterpretazione

Il termine (P tij − X t

ij ) è chiamato termine cognitivo

Il termine (Btij − X t

ij ) è chiamato termine socialeφ1, φ2 sono parametri di importanza (in letteratura è diffusol’uso di φ1 = φ2 = 2)r1, r2 sono numeri casuali in [0,1]

le velocità sono vincolate nell’intervallo [−Vmax ,Vmax ]





Vicinato

Esistono vari metodi per definire quando due particellepossono comunicareSi forma un grafo di “vicinanza”Si distinguono topologie statiche e dinamicheTra le topologie statiche troviamo

Global best: grafo completoLocal best: anello (grado K = 2)grafi con grado uniforme K > 2





Uno schema di algoritmo PSO

init_swarm()for t:= 1 to max_gen

update_best_positions()for i:=1 to m

update_velocity(i)update_position(i)

endendreturn best element





Varianti

Fattore di inerzia su V tij

V t+1ij = ωV t



ij )

Coefficienti di costrizione

V t+1ij = χ(V t



ij ))

oveχ =

2

φ− 2 +√φ2 − 4φ

φ = φ1 + φ2 > 4

Fully Informed Particle Swarm: il fattore sociale è la mediadelle posizioni di tutti i vicini





Applicazioni numeriche

L’ambito naturale di applicazione del PSO èl’ottimizzazione numericaE’ stato applicato in svariati problemi, dall’apprendimentodelle reti neurali, all’analisi di immagini e di video, dallaprogettazione di reti elettriche, al controllo automatico, . . .Esistono versioni in grado di lavorare anche con problemimulti–obiettivo





Ottimizzazione combinatorica

E’ possibile discretizzare PSODalla velocità V t

ij è possibile calcolare un valore S(V tij ) in

[0,1] che è usato come probabilità che X tij sia 1 (anzichè

0): PSO binarioIn maniera analoga è possibile generare posizioniappartenenti ad insiemi discreti: PSO multivalore





Sommario

1 Introduzione









Altri algoritmi euristici ed evolutivi

Programmazione geneticaStrategie evolutiveAlgoritmi memeticiSimulated annealingMetodi di ricerca locale. . .





Conclusioni

Sono stati presentati tre metodi euristici perl’ottimizzazione

Algoritmi geneticiAnt Colony OptimizationParticle Swarm Optimization

Si tratta di metodi che non garantiscono l’ottimalità dellesoluzioni trovateProducono (spesso) ottime soluzioniSono (sovente) (molto) più efficienti dei metodi classici





BibliografiaAlgoritmi genetici

Z. Michalewicz, 1999, Genetic Algorithms + DataStructures = Evolution Programs, Springer–Verlag.D. E. Goldberg, 1989, Genetic Algorithms in Search,Optimization and Machine Learning, Kluwer AcademicPublishers, Boston, MA.D. Whitley, A genetic algorithm tutorial. Statistics andComputing 4, 65-85, 1994





BibliografiaAnt Colony Optimization

M. Dorigo, T. Stützle, 2004. Ant Colony Optimization, MITPressM. Dorigo, C. Blum, Ant colony optimization theory: Asurvey. Theoretical Computer Science Volume 344, Issues2-3, Pages 243–278, 2005O. Cordon, F. Herrera, T. Stützle, A Review on the AntColony Optimization Metaheuristic: Basis, Models andNew Trends. Mathware and Soft Computing,9(2–3):141–175, 2002





BibliografiaParticle Swarm Optimization

M. Clerc. Particle Swarm Optimization. ISTE, 2006J. Kennedy and R. C. Eberhart. Swarm Intelligence.Morgan Kaufmann. 2001R. Poli, J. Kennedy, T. Blackwell, Particle SwarmOptimisation: an overview, Invited review paper for the firstissue of the Swarm Intelligence Journal, 1(1):33–57, June,2007


Algoritmi euristici ed evolutivi per l'ottimizzazione · Si basano sulla teoria darwiniana...

Documents

Transcript of Algoritmi euristici ed evolutivi per l'ottimizzazione · Si basano sulla teoria darwiniana...