APD - Prezentari Curs - 14

Universitatea Politehnica Bucuresti - Facultatea de Automatica si Calculatoare

AlgoritmiAlgoritmi geneticigenetici paraleliparaleli

12/01.2010 Algoritmi Paraleli si Distribuiti – Curs 14 1


Introducere

• Algoritmii genetici (AG): – reprezintă o soluţie a problemelor de optimizarereprezintă o soluţie a problemelor de optimizare– bazati pe mecanisme împrumutate din genetică.

• Un AG:– menţine o populaţie de indivizi, – fiecare individ reprezinta o soluţie potenţială a unei

blprobleme• AG realizeaza, în fiecare etapă, următoare operaţii:

evaluarea populaţiei curente– evaluarea populaţiei curente– selecţia celor mai buni indivizi– transformarea populaţiei folosind operatori genetici de

Algoritmi Paraleli si Distribuiti – Curs 14 2

transformarea populaţiei folosind operatori genetici de încrucişare şi mutaţie.

12/01.2010


Domeniile de aplicare

• optimizarea parametrilor• control optim• control optim• transport• optimizare combinatorială• optimizare combinatorială• desenare de grafuri

învăţare inductivă a regulilor de decizie• învăţare inductivă a regulilor de decizie• stabilirea cablajelor

l ifi• planificarea• jocuri, modelarea cognitivă


• optimizarea interogării bazelor de date.

12/01.2010


Vocabular

• AG împrumută vocabularul geneticii: p g– soluţiile sunt indivizi, – mulţimea soluţiilor potenţiale reprezintă o populaţie– în reprezentarea soluţiilor apar gene (caractere)p ţ p g ( )

• Un AG are următoarele componente:– o reprezentare genetică a soluţiilor– o cale de generare a primei populaţii– o funcţie de evaluare a “calităţii” soluţiilor– operatori genetici– valori pentru parametri - dimensiunea populaţiei, probabilitatea aplicării

operatorilor genetici.

Algoritmi Paraleli si Distribuiti – Curs 14 412/01.2010


Metode clasice de optimizare

• Problema:t i t ti d i i bi d 30– cautarea intr-un spatiu de siruri binare de 30

de biti, cu functia obiectiv: f( ) | 11*one( ) 150 |f(v) = | 11*one(v)-150 |

– unde one(v) este numarul de unitati din vectorul binar vvectorul binar v.

– Functia f(v) are :• un maxim global pentru v = (1 1 1 1 1) pentru• un maxim global pentru vg = (1 1 1 1 …1), pentru

care f(vg) = 180

• un maxim local pentru vl = (0 0 0 …0), pentru care


un maxim local pentru vl (0 0 0 …0), pentru care f(vl) = 150.

12/01.2010


Algoritmul hill climbingd i iprocedure hillclimber

begint := 0do t < MAX >do t < MAX ->

local := falseselectează aleator sirul curent Vcevalueaza Vcevalueaza Vcdo not local ->

gaseste Vn dintre vecinii cu cea mai mare valoare a functiei obiectiv Fif F(Vc) < F(Vn) -> Vc := Vn[] F(Vc) >= F(Vn) -> local := truefi

dod t := t+1

od end


endObs: daca sirul de pornire are cel mult 13 unitati atunci se gaseste

intotdeauna maximul local12/01.2010


Algoritmul hill climbing (2)



Algoritmul simulated annealingd i iprocedure simulated-annealing

begint := 0initializeaza temperatura Tinitializeaza temperatura Tselecteaza aleator sirul curent Vcevalueaza Vcdo not cond-stop ->do not cond stop >

do not cond-terminare ->selecteaza un nou sir Vn vecin cu Vc if F(Vc) < F(Vn) -> Vc := Vn[] F(Vc) >= F(Vn) ->

if random[0,1)< exp((F(Vn)-F(Vc))/T)-> Vc:=Vn fifidod

T := g(T,t)t := t+1

od


od end

12/01.2010


Algoritmul simulated annealing (2)P bl i il biPentru problema sirurilor binare:• daca v12 are 12 unitati:

f(v12) = |11*12 – 150| = 18f(v13) = |11*13 – 150| = 7

• Algoritmul accepta o noua solutie cu 13 unitati cu probabilitatea:probabilitatea:

p = exp((f(Vn)-f(Vc))/T) = exp((7-18)/T)= exp((7 18)/T) = 0.576 > 0.5

pentru T=20.


pentru T 20.

12/01.2010


Algoritmi genetici

• AG păstrează o populaţie de soluţii potenţialepotenţiale

• Legatura intre problema reala si cromozomi:cromozomi:– populatia – grup de cromozomi– codificarea solutiei in cromozomicodificarea solutiei in cromozomi– functii de evaluare a cromozomilor, pentru a

avea o masura a calitatii fiecarui cromozom– potrivirea ("conditia fizica" a) cromozomului,

care va fi luata in considerare in procesul de d


reproducere

12/01.2010


Algoritmi genetici (2)

procedure algoritm_geneticbegin

t := 0;creaza o populatie initiala de cromozomi P(t);evalueaza fiecare cromozom al populatiei initiale.evalueaza fiecare cromozom al populatiei initiale.do t < MAX ot not conditie de terminare ->

t := t+1;l t i tii t dselecteaza parintii pentru reproducere;

creaza noi cromozomi prin imperechere si mutatie;inlocuieste anumiti membri ai populatiei cu cei noi;evalueaza cromozomii din noua populatie

odend


end

12/01.2010


P blAlgoritmi genetici (3)

• Problema:– Dat fiind graful G = (V, E) să se găsească o partiţionare a sa în două

subgrafuri având acelaşi număr de noduri, prin eliminarea unui număr i i d hiiminim de muchii.

• Problema este NP completă.• Rezolvare cu alg genetici:

– soluţia reprezentată ca un vector cu elemente binare, de dimensiune egală cu numărul nodurilor din graf

– un cromozom codifica o posibila partitionare a grafuluip p g– o gena corespunde unui nod:

• 1 = nod in prima partitie • 0 = nod in a doua partitie• 0 = nod in a doua partitie

1. Evaluarea solutiei: eval(x) = cutsize(x)2. Generarea populatiei initiale:


– aleator cu corectii (orice cromozom sa aiba acelasi numar de 0 si 1 (±1) )

12/01.2010


Algoritmi genetici (4)3. Selectia parintilor pt reproducere – strategia ruletei:Constructia ruletei:calculează eval(xi) pentru fiecare cromozom i = 1..pop-size

Selecţia:generează un număr aleator rand în intervalul ( ) p p p

sortează populatia în ordinea crescătoare a valorilor evalasociază cu fiecare cromozom o valoare de “potrivire”

f(xi) = max-fit - eval(xi)astfel că f(xi) > 0 pentru orice i = 1 pop-size

g[o, cf-max]if rand < cf(x1) -> alege primul cromozom x1 fi

if cf(xi-1) < rand < cf (xi) -> alege xi fiastfel că f(xi) > 0 pentru orice i = 1..pop-size

calculează valorile de potrivire cumulativecf(xi) = SUMA f(xj), j = 1..i

Exemplu selectie cromozomiExemplu selectie cromozomiCromozom 1 2 3 4 5 6 7 8 9 10

Potrivire 8 2 17 7 2 12 11 7 3 7Potrivire cumulata 8 10 27 34 36 48 59 66 69 76

Numar aleator 23 49 76 13 1 27 57


Numar aleator 23 49 76 13 1 27 57Cromozom ales 3 7 10 3 1 3 7

12/01.2010


Algoritmi genetici (5)4. Reproducerea• Operatorul mutation

A li t l i t ti t b bilit t 0 08Aplicarea operatorului mutation pentru probabilitatea 0.08Cromozom vechi 1 0 1 0 1 1 0 0Probabilitate 0 80 0 11 0 27 0 45 0 12 0 05 0 15 0 03

• Operatorul de încrucişare (crossover)

Probabilitate 0.80 0.11 0.27 0.45 0.12 0.05 0.15 0.03Cromozom nou 1 0 1 0 1 0 0 1

Operatorul de încrucişare (crossover)

Aplicarea operatorului crossover intr-un punct (6)Primul parinte 1 1 1 1 1 1 1 1Al doilea parinte 0 0 0 0 0 0 0 0

Primul fiu 1 1 1 1 1 1 0 0


Primul fiu 1 1 1 1 1 1 0 0Al doilea fiu 0 0 0 0 0 0 1 1

12/01.2010


Algoritmi genetici (6)Aplicarea operatorului crossover pentru pozitiile 3 si 6

Primul parinte 1 1 1 1 1 1 1 1Al doilea parinte 0 0 0 0 0 0 0 0Al doilea parinte 0 0 0 0 0 0 0 0


Aplicarea operatorului crossover uniformP i l i t 1 1 1 1 1 1 1 1Primul parinte 1 1 1 1 1 1 1 1Al doilea parinte 0 0 0 0 0 0 0 0

Probabilitati 1 0 0 1 0 0 0 1

Primul fiu 1 0 0 1 0 0 0 1



12/01.2010


Justificarea funcţionării algoritmilor genetici

• Schema– un şir construit cu simbolurile 0, 1 şi * (don't care)– o schemă reprezintă toate şirurile care coincid cu ea în poziţiile

diferite de *– o schemă cu r simboluri * are drept corespondente 2r şiruri– un şir de lungime m poate fi pus în corespondenţă cu 2m scheme– există 3m scheme posibile de lungime m– intr-o populaţie de dimensiune n pot fi reprezentate între 2m şiintr o populaţie de dimensiune n pot fi reprezentate între 2 şi

n2m scheme

• Proprietăţile schemelorOrdin l o(S) n mar l de po itii fi e

De el depinde probabilitatea de s pra ieţ ire a schemei la m taţii– Ordinul o(S) = numarul de pozitii fixe

S1 = (010***11***1) are o(S1) = 6– Lungimea caracteristică (S) = distanţa între prima şi ultima

supravieţuire a schemei la mutaţii.


poziţie fixă(S1) = 11

De ea depinde probabilitatea de supravieţuire a schemei la încrucişări.

12/01.2010


Evoluţia schemelor - Selectia• pop_size dimensiunea populaţiei • m lungimea unui cromozom• p = (S t) numărul de şiruri vij care corespund la momentul t cup = (S,t) numărul de şiruri vij care corespund la momentul t cu

schema S. • Potrivirea schemei S la momentul t:

p

j

ij

pveval

tSeval1

)(),(

Media potrivirilor şirurilor din populaţia reprezentată de S

• Şirul vi are probabilitatea de selectie conform ruletei:

j p1

)()(

tFveval

p ii

sizepop

Media potrivirilor şirurilor din populaţia reprezentată de S.

• Potrivirea totală:

• Probabilitatea de selecţie a unui şir care corespunde schemei S =

i

ivevaltF1

)()(

),( tSevalţ ş p

• Numar de selectii este pop_size• Rezulta:

)( tSeval

)(tF


)(),(*_*),()1,(

tFtSevalsizepoptStS

12/01.2010


Evoluţia schemelor – Selectia (2)

———)(

),(*),()1,(tF

tSevaltStS

sizepoptFtF

_)()(

———cu potrivirea medie a populatiei

1),( tSevalO schemă "peste medie" are

i i t ă i d i di i i î l ţi

1)(

),(——— tF

si primeşte un număr mai mare de indivizi în noua populaţie.

Dacă

avem )1(*)()1( tStS)1()(),(

____ tFtSeval

avem

sau

)1(),()1,( tStStStS )1(*)0,(),(


numărul de indivizi este în creştere conform unei progresii geometrice.12/01.2010


Evolutia schemelor - Încrucişarea

Fie şirul (1110111101001) selectat pentru incrucisare şi doua scheme care ii corespund:ş p

S0=(****111******), ( S0)=2S1=(111********01), ( S1)=12

Dacă poziţia de tăiere = 10, schema S0 se regăseşte într-unul din fii, în timp ce schema S1 are şanse foarte reduse de reproducerede reproducere.

lungimea caracteristică importanta în reproductibilitatea schemei

• m-1 posibilităţi selectie loc de încrucişare• probabilitatea de distrugere a schemei S este 1

)()(

m

SSpd

)(S


• probabilitatea de supravieţuire1)(1)(

mSSps

12/01.2010


Evolutia schemelor – Încrucişarea (2)

• cu prob. de selectie pentru incrucisare pc: 1)(*1)(

SpSp cs

p p pc:

• deoarece se pot combina indivizi aparţinând unor scheme

1)(

mpp cs

deoarece se pot combina indivizi aparţinând unor scheme comune:

1)(*1)(

mSpSp cs

• efect combinat selectie & incrucisare:

1m

)1)(*1(*

)(

),(*),()1,( ———

mSp

tF

tSevaltStS c


)(tF

12/01.2010


Evolutia schemelor - Mutaţia• probabilitatea mutaţiei unui singur bit este pm

• probabilitatea nemodificării sale este (1- pm).

• probabilitate ca o schemă S să supravieţuiască unei mutaţii:• probabilitate ca o schemă S să supravieţuiască unei mutaţii:

• deoarece pm<<1:

)()1()( Soms pSp

)(*1)( SompSsp

• efectul combinat al selecţiei, încrucişării şi mutaţiei este

))(*1)(*1(*

)(

),(*),()1,( ——— Sopm

SpF

tSevaltStS mc

• Teorema schemei. Schemele scurte, de ordin scăzut şi peste medie cresc exponenţial de-a lungul generaţiilor unui algoritm

1)( mtF

medie cresc exponenţial de a lungul generaţiilor unui algoritm genetic.

• Ipoteza blocurilor constructive. Un algoritm genetic atinge performaţe aproape optime prin juxtapunerea unor scheme scurte de


performaţe aproape optime prin juxtapunerea unor scheme scurte, de ordin scăzut, de mare performaţă, numite blocuri constructive.

12/01.2010


Constrângerile în algoritmii genetici• Metode:

– penalizări pentru solutii ce nu respecta constrângeri– eliminarea soluţiilor necorespunzătoare– eliminarea soluţiilor necorespunzătoare– aplicarea unor algoritmi de corecţie.

E bl l i• Ex: problema rucsacului. – date fiind o mulţime de ponderi W, profiturile asociate

P şi capacitatea C a rucsacului, să se găsească un p gvector binar X = <x1, x2, ..., xn> a.i.

i 1 xi * wi <= C şi i = 1,n xi wi < C şi

P(X) = i = 1 n xi * pi este maxim.


( ) i 1,n i pi

12/01.2010


Algoritm bazat pe penalizari

• Functia de evaluare: eval(X) = i = 1,n xi * pi - Pen(X)– unde Pen(X) = 0 pentru soluţiile fezabile şiunde Pen(X) = 0 pentru soluţiile fezabile şi

Pen(X) ≠ 0 pentru soluţiile nefezabile (suma > C).

• Variante:– logaritmică, Pen1(X) = log2 (1 + ( i = 1 n xi * wi - C))g , 1( ) g2 ( ( i = 1,n i i ))

– liniară, Pen2(X) = ( i = 1,n xi * wi - C)

– pătratică, Pen3(X) = ( ( i = 1,n xi * wi - C))2

d MAX { / }


• unde = MAX i = 1,n { pi / wi}

12/01.2010


Algoritmul bazat pe corecţia soluţiei

• Functia de evaluare: eval(X) = i = 1,n x'i * pi– unde X’ este versiunea corectată a lui X

procedure corectie (X)begin

depasire := falseX’ := X

if i x’i * wi > C -> depasire := true fiif i = 1,n x i wi > C > depasire : true fido depasire ->

i := selecteaza un element din sac0scoate elementul x'i := 0

if i = 1,n x'i * wi <= C -> depasire := false fiod


end

12/01.2010


Algoritmul bazat pe decodificatori

• Un cromozom este interpretat ca o strategie de a incorpora elemente într-o soluţie.

• Fiecare cromozom este un vector de n întregi• Fiecare cromozom este un vector de n întregi. • Componenta i a vectorului

– este un întreg din domeniul 1..n-i+1– indică poziţia unui element al unei liste L– elementele selectate sunt eliminate din lista.

• Exemplu:– fie L = (1,2,3,4,5,6). – Vectorul <4,3,4,1,1,1> este decodificat ca secvenţa 4, 3, 6, 1, 2, 5. – 6 este al 4-lea element după eliminarea lui 4 şi a lui 3– 6 este al 4-lea element după eliminarea lui 4 şi a lui 3

• Ca efect, – la mutaţie, gena i poate lua orice valoare între 1 şi n-i+1,

î i ă i i i d d d i i


– încrucişarea unor părinţi corecţi produce descendenţi corecţi.

12/01.2010


Algoritmul bazat pe decodificatori (2)procedure decode (X)

construieste o lista de elemente Li := 1suma ponderi : 0suma-ponderi := 0suma-profit := 0do i <= n ->

j := xij : xielimina elementul cu numarul de ordine j din Lif suma-ponderi + wj <= C ->

suma-ponderi := suma-ponderi + wjsuma-profit := suma-profit + pj

fii := i+1

odend

Variante pentru construiestel taleator

greedy - elementele în ordinea descrescătoare a rapoartelor pi / wi;Algoritmi Paraleli si Distribuiti – Curs 14 2612/01.2010


Algoritmi genetici paraleli• Abordari

– paralelizarea operatorilor geneticidi t ib i l ti i– distribuirea populatiei.

• Paralelizarea operatorilor genetici– partitionare functionala: paralelizarea buclei care– partitionare functionala: paralelizarea buclei care

produce noua generatie– se mentine o singura populatie– operatorii genetici sunt aplicati in paralel:

• functia de potrivire si mutatia aplicate in paralel i di i ilindivizilor

• crossover la doi indivizi– potrivit pentru memorie partajata


potrivit pentru memorie partajata

12/01.2010


Di t ib i l ti iAlgoritmi genetici paraleli (2)

• Distribuirea populatiei:– corespunde descompunerii domeniului – prelucrari facute in paralel pe diferite sub-populatiip p p p p– exploreaza mai bine spatiul solutiilor– PGAs mentin sub-populatii separate care evolueaza independent

=> granularitatea algoritmilor paraleli=> granularitatea algoritmilor paraleli• PGAs de granularitate fina:

– Asigneaza un individ fiecarui task / procesor– Fiecare task foloseste indivizi din vecinatatea sa– Ajuta migrarea indivizilor

• Intrebari: – care este tolopogia de inter-conectare ?– care este dimensiunea vecinatatii ?– care este schema de inlocuire pentru includerea migratorilor in


– care este schema de inlocuire pentru includerea migratorilor in sub-populatia tinta ?

12/01.2010


Algoritmi genetici paraleli (2)• PGAs de granularitate mare:

– Fiecare sub-populatie contine un numar mare de indivizi– AG se executa independent pe fiecare sub-populatie si produce o solutie a problemei

Rezultatul final este obtinut prin selectia celei mai bune solutii– Rezultatul final este obtinut prin selectia celei mai bune solutii– Indivizii migreaza periodic de la o sub-populatie la alta

• Synchronous Island PGAs– migrarea are loc dupa un anumit numar de generatiig p g

• Asynchronous Island PGAs– migrarea intre doua sub-populatii nu este corelata cu restul migrarilor– mai aproape de migrarea din natura– mai potrivita cu algoritmi distribuiti

• Intrebari– care este topologia proceselor?

este reteaua omogena sau nu?– este reteaua omogena sau nu? – care este rata de migrare? – cati migratori sunt inter-schimbati? – cum sunt selectati migratorii?


g– cum sunt combinati cu populatia tinta?

12/01.2010


Asynchronous Island PGAs

• Modelul "replicated workers"



EExamen



Un model de subiect de examen la APD

Subiectul 1 (2 puncte) Ceasuri logice vectoriale Tratati:Subiectul 1. (2 puncte) Ceasuri logice vectoriale. Tratati:1.1 Conceptul general (0.7 p)

Motivatia folosirii ceasurilor logice: de ce este nevoie de ele (ce aduce nou fata de alte metode).

Principiul ceasurilor logice vectoriale. 1.2 Pentru procesele din figura, precizati vectorii de timp asociati

evenimentelor specificate. Axele orizontale reprezinta timpul. (0.3 p)1 3 Aplicatie - ordonarea cauzala multicast (1 p)1.3 Aplicatie - ordonarea cauzala multicast. (1 p)

Specificarea problemei.Solutia, cu descrierea actiunilor la trimiterea, receptia si livrarea mesajelor.

P1 a c

P2 f b


P3d e

12/01.2010


Subiectul 2. (1 punct)

Propuneti un algoritm de tip heartbeat pentru calculul sumei a n2 valoride tip intreg. Pentru aceasta folositi n2 procese dispuse intr-ogrila neperiodica. Deci, fiecare proces poate comunica cu veciniide la est, vest, nord si sud (cu restrictiile de rigoare la margini).Fiecare proces detine initial o singura valoare v. In final fiecare

t b i d ti l i C l l tiproces va trebui sa detina valoarea sumei. Calculaticomplexitatea solutiei oferite.



S bi t l 3 (1 t) T t ti l di bi t l t l lSubiectul 3. (1 punct) Tratati unul din subiectele urmatoare, la alegere:

3.1. Cautarea paralela. Prezentarea problemei (0.2 p)Descrierea algoritmului (0.4 p) Analiza complexitatii (0.4 p)

3.2. Problema cititorilor si scriitorilor Prezentarea problemei (0.2 p) e e ta ea p ob e e (0 p)Descrierea algoritmului (0.4 p) Politici cu prioritate asupra cititorilor si asupra scriitorilor (0.4 p)



ConditiiTimp de lucru: 2 oreFara documentatie



Hinturi de rezolvareSubiectul 1. Ceasuri logice vectoriale (subiect tratat pe larg in cursul 8). g ( p g )1.1 Conceptul general

Motivatia: cu solutia Lamport, din amprentele logice nu se poate deduce ordinea evenimentelor. Justificare, eventual pe un exemplu.

Principiul: rolul vectorilor V(i) si modul de actualizare; compararea vectorilor si p ( ) ; pdeducerea relatiei cauzale a evenimentelor corespunzatoare.

1.2 Exemplul din figuraVezi exemplul de la curs

1.3 Aplicatie1.3 AplicatieSpecificarea: descrierea dependentei cauzale a mesajelor; atentie la notiunea de

livrare a mesajelor! Solutia: Descrierea operatiilor; nu trebuie uitata livrarea mesajelor.

P1 a c

P2 f b

P3d e

12/01.2010


Subiectul 2. (1 punct)

Algoritmi de tip heartbeat au fost ilustrati pentru mai multe probleme sidiverse topologii, de ex. in stabilirea topologiei (cursul 10) sau cailustrare a algoritmilor unda (cursul 9). Pentru problema de fatase cere o solutie, nu neaparat optima. Trebuie asigurat ca:

fiecare proces insumeaza toate valorileo valoare nu este considerata de mai multe ori.

12/01.2010


S bi t l 3Subiectul 3.

Problema 3.1 – (cursul 5)Problema 3.2 – (cursul 4 – si tema de casa)

La ambele probleme:La ambele probleme:la descrierea algoritmului se acorda punctaj maxim (0.4 p) pentru o

descriere coerenta in pseudocod.

La problema 3.2:punctaj maxim pentru analiza detaliata a politicilor de prioritate cu

exemplificare pe pseudocod.exemplificare pe pseudocod.

12/01.2010


Observatii:

• Punctajul este afisat pe site (plus actualizarea de astazi – nelamuriri?)actualizarea de astazi – nelamuriri?)

• Nu aveti voie sa veniti cu alta grupa decatcu aprobarea mea (pentru problemecu aprobarea mea (pentru problemespeciale contactati-ma)

• Pentru nelamuriri documentatie/explicatiiPentru nelamuriri, documentatie/explicatiisuplimentare – open office, EG303, [email protected] @ p

• …Poza dePoza de grupgrupPoza de Poza de grupgrup

12/01.2010

Date post:	23-Jun-2015
Category:	Documents
Upload:	ssh-das
View:	259 times
Download:	5 times

APD - Prezentari Curs - 14

Documents