15. Algoritmi genetici

15.1. Generalităţi

Algoritmii genetici - AG reprezintă o soluţie a problemelor de optimizare, bazată pe mecanisme împrumutate din genetică. Un algoritm genetic menţine o populaţie de indivizi, fiecare individ reprezentând o soluţie potenţială a unei probleme de rezolvat. AG încearcă să amelioreze populaţia şi să găsească astfel o soluţie cât mai apropiată de cea optimă, printr-un proces iterativ care implică realizarea, în fiecare etapă, a următoarelor operaţii: evaluarea populaţiei curente

selecţia celor mai buni indivizi

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

AG furnizează o metodă de optimizare mai bună decât soluţiile clasice cunoscute, ca hill climbing sau simulated annealing. AG reprezintă instrumente eficace şi eficiente potrivite implementării în medii distribuite.

Domeniile de aplicare a algoritmiloor genetici sunt foarte diferite: optimizarea parametrilor

control optim

transport

optimizare combinatorială

desenare de grafuri

învăţare inductivă a regulilor de decizie

stabilirea cablajelor

planificarea

jocuri, modelarea cognitivă

optimizarea interogării bazelor de date.

Rezolvarea unei probleme poate fi percepută ca o căutare în spaţiul soluţiilor potenţiale. Aflarea celei mai bune soluţii transformă rezolvarea într-un proces de căutare. Pentru un spaţiu de soluţii redus se pot folosi metodele clasice exhaustive. Pentru un spaţiu de soluţii mare, se pot folosi tehnici de inteligenţă artificială, de exemplu algorimii genetici. Aceştia sunt algoritmi stochastici ale căror metode de căutare imită fenomenele naturale: moştenirea genetică, lupta pentru supravieţuire / selecţia naturală.

Algoritmii genetici împrumută vocabularul geneticii: soluţiile sunt indivizi, mulţimea soluţiilor potenţiale reprezintă o populaţie, în reprezentarea soluţiilor apar gene (caractere). 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.

15.2. Metode clasice de optimizare

Rezolvarea problemelor de optimizare se poate face folosind mai multe tehnici, dintre care vom trece pe scurt în revistă doua abordari. Problema pe care o ilustram este cautarea intr-un spatiu de siruri binare de 30 de biti, cu functia obiectiv

f(v) = | 11*one(v)-150|

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

Functia f(v) are un maxim global pentru vg = (1 1 1 1 …1), pentru care f(vg) = 180 si un maxim local pentru vl = (0 0 0 …0), pengtru care f(vl) = 150.

15.2.1. Algoritmul hill climbing

Procedeul căţărării (hillclimbing) aplică următorul algoritm:

procedure hillclimber

begin

t := 0

do t < MAX ->

local := false

selectează aleator sirul curent Vc

evalueaza Vc

do not local ->

gaseste Vn dintre vecinii cu cea mai mare valoare a

functiei obiectiv F

if F(Vc) < F(Vn) -> Vc := Vn

[] F(Vc) >= F(Vn) -> local := true

fi

od

t := t+1

od

end

Algoritmul se bazează pe alegerea aleatoare a unui punct de pornire în spaţiul soluţiilor şi pe încercarea de a îmbunătăţi treptat soluţia prin “mişcări pozitive” spre punctele vecine soluţiei curente. Căutarea se opreşte când astfel de mişcări nu mai sunt posibile.

Algoritmul prelucrează la un moment dat un singur punct din spaţiul stărilor. Pentru a mări şansa de găsire a unei soluţii bune, algoritmul se aplică repetat, pentru alte puncte de plecare alese aleator. Rezultatul este puternic dependent de şirul iniţial. Există o probabilitate mică de a găsi optimul global.

Pentru problema specificata la inceputul sectiunii, daca sirul de pornire are un numar de unitati mai mic sau egal cu 13 atunci se gaseste intotdeauna maximul local.

15.2.2. Algoritmul simulated annealing

Acest algoritm a fost inspirat de mecanica statistica si de anumite procedee de imbunatatire a calitatii unor materiale prin incalzirea lor la o temperatura ridicata urmata de racirea lor controlata, pentru a permite o aranjare favorabila la nivel molecular. El reprezinta un puternic instrument in rezolvarea unor probleme de optimizare. Principala forta a acestui algoritm este posibilitatea de a sari peste anumite optime locale nefavorabile, fiind permise nu doar "coborasuri" spre solutii ci si "urcusuri" (controlate de o anumita probabilitate) care departeaza cautarea de optimul cel mai apropiat. Parametrii importanti ai acestui tip de algoritm sunt temperatura initiala T, conditia de echilibru termic si temperatura de racire in care se desfasoara experimentul. Algoritmul poate utiliza o functie de penalizare a solutiilor intermediare deficitare. Metoda simulated annealing utilizează următorul algoritm:

procedure simulated-annealing

begin

t := 0

initializeaza temperatura T

selecteaza aleator sirul curent Vc

evalueaza Vc

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

fi

fi

od

T <- g(T,t)

t <- t+1

od

end

Condiţia de terminare verifică atingerea unui “echilibru termic” adică a situaţiei în care distribuţia probabilităţilor noilor şiruri selectate se apropie de distribuţia Bolzmann. Într-un caz mai simplu, bucla se repetă de K ori, unde K este un parametru. Deoarece g(T,t) < T, condiţia de stop echivalează cu atingerea de către T a unei anumite valori limită inferioară.

Ca şi metoda precedentă, simulated annealing urmăreşte îmbunătăţirea unei soluţii aleasă aleator. De data aceasta sunt acceptate şi “mutări negative”, spre soluţii mai proaste. Acceptarea se face cu o probabilitate care descreşte în timp. Mutările negative permit algoritmului să scape din capcana unor maxime locale şi să exploreze mai bine spaţiul soluţiilor.

Pentru problema sirurilor binare mentionata mai inainte, daca avem un sir v12 cu 12 unitati obtinem:

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

f(v13) = |11*13 – 150! = 7

Algoritmul accepta o noua solutie cu 13 unitati cu probabilitatea

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

15.3. Algoritmi genetici

Spre deosebire de metodele prezentate anterior, AG păstrează o populaţie de soluţii potenţiale. Ca urmare, sunt păstrate şi soluţii mai slabe, dar care prin încrucişare pot produce descendenţi mult mai puternici. AG realizează un echilibru între explorarea cât mai bună a spaţiului de căutare şi găsira cât mai rapidă a celor mai bune soluţii. În schimb, reprezentarea soluţiilor este uneori dificilă, ca în exemplul comis-voiajorului, iar funcţia de evaluare nu este mereu simplă (de exemplu în dilema prizonierului).

Conceptul de algoritm genetic este relativ recent, fiind folosit prima data in 1976 de John Holland, pentru o clasa de algoritmi care incearca sa imite procesul de evolutie naturala al unui grup indivizi, de-a lungul mai multor generatii. Odata cu dezvoltarea geneticii, s-au putut cunoaste anumite fenomene care au demonstrat ca proprietatile "exterioare" ale unei fiinte vii sunt datorate unor codificari interne, realizate prin intermediul cromozomilor, entitati organice elementare. Se accepta ideea ca o fiinta este creata (se dezvolta) si pe baza unui proces de decodificare a informatiei primare din cromozomi. Desi nu s-au explicat in totalitate aceste procedee de codificare - decodificare, se accepta ca evolutia se produce prin modificarea zestrei genetice (a calitatii cromozomilor detinuti), proces care are loc prin reproducere. Astfel, prin mutatie por apare la copii cromozomi diferiti de cei ai parintilor biologici, o alta posibilitate fiind recombinarea materialului genetic al parintilor biologici. De asemenea, procesul acesta al evolutiei nu are memorie, adica se pastreaza doar informatia "curenta" a unui individ, fara stocarea anumitor informatii despre generatiile anterioare. Acest proces evolutiv care duce la adaptarea continua la conditiile de mediu l-a facut pe Holland sa incerce "copierea" lui cu scopul rezolvarii anumitor probleme dificile.

Primii algoritmi genetici lucrau pe siruri de numere binare (0 si 1), care formau cromozomii. Un grup de cromozomi forma o populatie, materialul genetic existent intr-o populatie era "amestecat" prin reproducere, intr-o maniera nepreferentiala si fara nici un fel de informatie asupra problemei reale de rezolvat. Pentru a dirija oarecum evolutia s-a folosit o functie de evaluare a cromozomilor, pentru a permite selectionarea celor mai buni care sa participe apoi la procesul de reproducere. Cu astfel de algoritmi care nu faceau altceva decat sa manipuleze cromozomi, avand mecanisme simple de codificare si reproducere el a reusit rezolvarea unor probleme complicate. Evident, de atunci acesti algoritmi au fost studiati si imbunatatiti substantial, ajungand o alternativa deosebit de atractiva pentru solutionarea anumitor probleme. Desi s-a studiat mult pe aceasta tema nu s-au obtinut rezultate care sa revolutioneze domeniul care a inspirat acesti algoritmi, genetica. Acelasi lucru s-a intamplat insa si cu alte clase de algoritmi care au la baza procese naturale, si anume retelele neuronale si simulated annealing.

Pentru a rezolva o problema folosind algoritmi genetici trebuie facuta o legatura intre problema reala si lumea cromozomilor. In principal aceasta se face codificarea solutiei in cromozomi si prin gasirea unei functii de evaluare a cromozomilor, pentru a avea o masura a calitatii fiecarui cromozom. Tehnica codificarii solutiei in algoritmi variaza foarte mult de la problema la problema, neexistand o regula in acest sens. Prima codificare, folosita de Holland si colaboratorii sai utiliza siruri de biti, insa de atunci au fost folosite numeroase altele. Deoarece nu toate aceste tehnici dau aceleasi rezultate in rezolvarea aceleiasi probleme, se cere o anumita experienta in alegerea modalitatii optime de reprezentare. Functia de evaluare a cromozomilor face legatura cu problema reala, fiind pe post de mediu natural, ea intorcand ca rezultat o masura a performantelor cromozomilor. Pe baza acesteia se stabileste potrivirea ("conditia fizica" a) cromozomului, care va fi luata in considerare in procesul de reproducere.

Descrierea generala a unui algortim genetic este prezentată în continuare.

procedure algoritm_genetic

begin

t <- 0;

creaza o populatie initiala de cromozomi P(t);

evalueaza fiecare cromozom al populatiei initiale.

do t < MAX ot not conditie de terminare ->

t := t+1;

selecteaza parintii pentru reproducere;

creaza noi cromozomi prin imperechere si mutatie;

inlocuieste anumiti membri ai populatiei cu cei noi;

evalueaza cromozomii din noua populatie

od

end

În cele ce urmează, analizăm diferitele etape ale algoritmilor genetici. Analiza este însoţită de un exemplu referitor la partiţionarea grafurilor. Problema are următorul enunţ: 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 minim de muchii. Problema este NP completă, astfel că abordările practice vizează găsirea unor soluţii aproximative cât mai bune.

Fiecare soluţie este reprezentată ca un vector cu elemente binare, de dimensiune egală cu numărul nodurilor din graf. Un cromozom codifică o posibilă partiţionare a grafului, o genă fiind corespunzătoare unui nod. Valoarea 1 sau 0 a genei arată dacă

nodul respectiv aparţine primei partiţii sau celei de a doua. O populaţie poate fi reprezentată printr-un tablou de cromozomi.

15.3.1. Evaluarea

Deoarece problema cere partiţionarea grafului prin eliminarea numărului minim de muchii, funcţia de evaluare este definită ca:

eval(x) = cutsize(x)

unde cutsize(x) este numărul de muchii având un capăt în partiţia 1 şi celălalt în partiţia 2. Ca urmare, problema partiţionării grafului se reduce la una de căutare a minimului.

15.3.2. Generarea populaţiei iniţiale

Asa cum s-a mai spus anterior, modalitatea de reprezentare considerata este cea binara, fiecare cromozom fiind format dintr-un sir de biti al căror număr depinde de numărul de noduri ale grafului. Populatia initiala se poate forma aleator, prin generarea la intamplare a sirurilor de biti reprezentand cromozomii. Pentru a reprezenta soluţii valide, cromozomii sunt supuşi unor transformări al căror rezultat este egalizarea numărului de noduri din cele două partiţii. La acest aspect ne referim în altă secţiune a prezentării.

15.3.3. Selecţia parintilor pentru reproducere

Selecţia părinţilor este făcută în conformitate cu strategia ruletei. Aceasta acordă indivizilor mai buni şanse mai mari de a fi selectaţi pentru reproducere. Fiecărui individ i se alocă un sector de ruletă, al cărui unghi la centru este proporţional cu “calitatea” individului. Construcţia ruletei se face prin următorii paşi:

calculează eval(xi) pentru fiecare cromozom i = 1..pop-size

sortează populatia în ordinea crescătoare a valorilor eval

asociază cu fiecare cromozom o valoare de “potrivire”

f(xi) = max-fit - eval(xi)

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

calculează valorile de potrivire cumulative

cf(xi) = SUMA f(xj), j = 1..i

Fie cf-max potrivirea cumulativă a ultimului cromozom. Selecţia se face astfel:

generează un număr aleator rand în intervalul [o, cf-max]

if rand < cf(x1) -> alege primul cromozom x1 fi

if cf(xi-1) < rand < cf (xi) -> alege xi fi

Desi acest algoritm asigura alegerea aleatoarea a unui cromozom, sansa fiecaruia de a fi ales fiind direct proportionala cu valoarea sa, se poate intampla sa fie ales cel mai putin valoros cromozom. Acest lucru nu este deranjant daca nu se intampla foarte des, deoarece asigura realizarea unei diversitati in cadrul populatiei. Pentru aceasta este bine ca generatorul de numere aleatoare folosit sa fie cat mai sigur (perioada mare de repetabilitate), iar suplimentar se poate opta pentru ordonarea descrescatoarea a cromozomilor. Singura restrictie care se aplica cere ca potrivirile sa fie exprimate prin numere pozitive.

Un exemplu de functionare pentru o populatie nesortata este cel prezentat in Figura 1.

Exemplu selectie cromozomi Cromozom 1 2 3 4 5 6 7 8 9 10Potrivire 8 2 17 7 2 12 11 7 3 7

Potrivire cumulata 8 10 27 34 36 48 59 66 69 76

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

Figura 1. Exemplu de folosire a algoritmului ruletei

In figura 1 primul tabel prezinta modul in care sunt distribuiti cromozomii in cadrul unei populatii, impreuna cu numerele reprezentand potrivirile acestora. A treia linie contine valorile cumulate ale potrivirilor. Al doilea tabel prezinta numere generate aleator si cromozomul ales in fiecare caz. Se observa ca de fiecare data este ales cromozomul a carui potrivire cumulata depaseste numarul generat aleator (intre 0 si 76).

15.3.4. Reproducţia

Reproducţia este bazată pe operatorii genetici de mutatie si încrucişare (crossover), fiecare avand probabilitati proprii de activare. Acesti doi operatori pot constitui impreuna un meta-operator, sau, cum e mai natural, vor forma doua entitati distincte.

Procesul de reproducere consta in alegerea a doi cromozomi-parinti, asupra carora se vor aplica operatorii genetici pentru a da nastere unor cromozomi-copii. Se poate intampla ca cei doi copii sa difere de parintii lor, aducand elemente noi, asa cum la fel de bine ei pot fi identici cu parintii lor. Aceasta din urma situatie (care intuitiv reduce viteza de evolutie) poate apare in urmatoarele situatii:

daca parintii si-au atins maximul valorii lor;

prin jocul probabilitatilor de aplicare pentru operatorii genetici;

datorita structurii momentane a parintilor, legata de alegerea unor operatori genetici deficitari.

Dupa generarea numarului stabilit de generatii algoritmul se va opri, furnizand ca rezultat cel mai bine cotat cromozom.

15.3.4.1. Operatorul mutation

Aplicarea acestui operator asupra unui cromozom (sir de biti) presupune parcurgerea acestuia si inlocuirea fiecarui bit cu unul ales aleator, daca un anume test de probabilitate este indeplinit. Probabilitatea de aplicare trebuie sa aiba o valoare scazuta, care trebuie determinata prin incercari. Anumite variante de operatori ar putea sa interschimbe doi biti intre ei, in acest caz probabilitatea reala fiind dublul celei folosite pentru test. Modul de functionare al acestui operator este ilustrat in figura 2.

Aplicarea operatorului mutation pentru 0.08 Cromozom vechi 1 0 1 0 1 1 0 0 Probabilitate 0.80 0.11 0.27 0.45 0.12 0.05 0.15 0.03 Cromozom nou 1 0 1 0 1 0 0 1

Figura 2. Operatorul mutation.

15.3.4.2. Operatorul de încrucişare (crossover)

Acest operator este necesar deoarece doar cu selectia si mutatia nu s-ar putea realiza o evolutie a cromozomilor. Se poate considera ca daca se elimina acest operator, algoritmul nu mai poate fi considerat un algoritm genetic. Ideea acestui operator este recombinarea genelor a doi parinti, cu scopul obtinerii unor indivizi diferiti. Asa cum nici operatorul mutation nu poate garanta ca noul individ va fi mai valoros, fiind bazat pe numere aleatoare, nici operatorul crossover nu poate face acest lucru. Cei doi operatori realizeaza doar cadrul pentru diversitate, selectia fiind cea care va alege cei mai valorosi indivizi.

Exista mai multe variante ale acestui operator. Prima, numita crossover intr-un punct alege aleator o pozitie in cromozom, pozitie care va imparti fiecare cromozom in doua sectiuni A si B. In continuare se interschimba incrucisat cele doua sectiuni din fiecare cromozom: Sectiunea A din primul impreuna cu sectiunea B din al doilea vor forma un descendent, in timp ce sectiunea B din primul si sectiunea A din al doilea vor

forma al doilea descendent. Un exemplu de aplicare al acestui operator este prezentat in figura 3.

Aplicarea operatorului crossover pentru pozitia 6 Primul parinte 1 1 1 1 1 1 1 1 Al doilea parinte 0 0 0 0 0 0 0 0 Primul fiu 1 1 1 1 1 1 0 0 Al doilea fiu 0 0 0 0 0 0 1 1

Figura 3. Operatorul crossover

Aplicarea acestui operator poate duce la obtinerea unor descendenti total diferiti de parintii folositi, insa la fel de bine acestia pot fi identici. De exemplu, daca pe pozitiile care trebuie interschimbate cei doi parinti au aceleasi valori, nu se va intampla practic nimic. Studiile intreprinse de Holland au demonstrat ca operatorul crossover are o importanta mai mare, corespunzator va avea si o probabilitate de producere mai mare decat cea a operatorului mutation. Aceleasi studii au aratat ca se poate considera ca un cromozom contine anumite portiuni - scheme - care, daca reprezinta proprietati de valoare ar trebui pastrate de acest operator. Operatorul de selectie si cel de recombinare trebui sa asigure proliferarea schemelor mai avantajoase, in defavoarea celorlalte. Pentru a creste sansele de a obtine caracteristici noi la urmasi este indicat sa nu se permita combinarea a doi indivizi identici.

15.3.5. Corecţia soluţiilor

Operatorii genetici pot produce cromozomi care să nu aibă nici o semnificaţie pentru problema de rezolvat, din cauza folosirii întâmplării în obţinerea acestor cromozomi noi. De aceea, dacă această situaţie poate apare, este necesară folosirea unor operatori de corecţie, care să readucă un cromozom alterat la o formă consistentă.

De exemplu, în cazul problemei partiţionării grafului, un cromozom poate fi reprezentat printr-un şir de cifre binare, fiecare indicând partiţia din care face parte un anumit nod. Este evident că diferenţa între numărul de zerouri şi numărul de unităţi trebuie să fie zero (număr par de noduri în graf) sau unu (număr impar de noduri în graf).

În urma aplicării operatorilor genetici, echilibrul acesta între numărul de zerouri şi numărul de unităţi se poate strica, apărând partiţii inegale. Acest fenomen trebuie corectat prin folosirea unui operator care să echilibreze cele două partiţii. Corecţia poate fi făcută aleator, caz în care potrivirea cromozomului poate să scadă, sau într-o

manieră care să ţină cont de problema de rezolvat, realizându-se astfel şi o optimizare, dacă e posibil.

15.3.6. Îmbunatatirea algoritmului genetic

Performantele algoritmului genetic prezentat pot fi puternic imbunatatite pe mai multe cai, ce urmeaza a fi prezentate in continuare.

Prima modificare trebuie facuta in legatura cu functia de evaluare. Daca valorile intoarse de aceasta functie sunt foarte apropiate, nu se va mai putea face o separatie neta intre indivizi. Si deoarece functia de evaluare depinde de problema reala, nu se poate forta totdeauna felul rezultatelor intoarse. Pentru functia de evaluare următoare

222

222

6 )(*001.00.1

)(sin5.0),(

yx

yxyxf

.

care are valori în intervalul [0,1], o usoara modificare, ce nu ii modifica mai deloc comportamentul, poate duce la degradarea drastica a proprietatilor algoritmului genetic:

6'

6 5.999 ff

Pentru a inlatura acest neajuns, este necesara folosirea unei functii de potrivire diferite de functia de evaluare, insa care sa se bazeze pe aceasta. Exista doua moduri de rezolvare acestei probleme:

Prin ferestre: Se afla valoarea minima a functiei de evaluare, apoi se asigneaza fiecarui cromozom cantitatea cu care evaluarea sa depaseste valoarea minima gasita. Pentru a asigura o sansa si celui mai slab cromozom, se poate lasa un prag astfel incat nici unui cromozom sa nu i se asigneze valoarea zero.

Prin normalizare liniara: Se ordoneaza cromozomii in ordinea descrescatoare a evaluarii lor. Apoi se asigneaza valori descrescatoare, pornind de la o constanta, la fiecare nou cromozom sau noua valoare scazandu-se o valoare fixa. Bineinteles, se evita acordarea valorilor negative, care sunt contraindicate la folosirea metodei ruletei pentru selectie. Valoarea initiala de la care se porneste si valoarea care se scade reprezinta parametrii acestui procedeu. Asigurand o diferentiere neta intre cromozomi diferiti, cresc sansele cromozomilor mai valorosi.

O alta modificare priveste modul de inlocuire a unei generatii cu generatia urmatoare. Prin inlocuirea completa a tuturor indivizilor se pot pierde indivizi valorosi, purtatori de scheme pretioase. Deci ar fi indicata folosirea unei tehnici elitiste, care sa pastreze

de la o generatie la alta indivizii mai valorosi. Evident numarul indivizilor pastrati de la o generatie la alta constituie un parametru important. Aceasta strategie elitista poate duce rapid la aparitia unui super - individ care sa domine competitia, insa la echilibru se constata o imbunatatire a performantelor algoritmului genetic. Insa chiar si cu aceasta strategie elitista pot exista indivizi valorosi care sa nu participe la reproducere, lucru ce poate cauza pierderea genelor lor pretioase. De asemenea, operatorii genetici pot deteriora proprietatile bune ale unor cromozomi. Solutia pentru preintampinarea acestor neajunsuri ar fi ca la reproducere sa se inlocuiasca doar un numar mic de indivizi (1 sau 2), acesta constituind dealtfel un parametru important. Un aspect important care trebuie analizat este modul in care se trateaza duplicatele, adica acei cromozomi noi care au o structura genetica deja existenta. Evident, exista doua posibilitati: se elimina duplicatele sau li se permite "supravietuirea". In a doua situatie exista riscul aparitiei unei populatii "plate", putin diverse, in care sansele de evolutie sunt mai reduse. Deci ar fi de folosit prima metoda, care asigura aparitia unor indivizi diferiti de cei care exista deja, fapt ce duce la o mai eficienta explorare a spatiului solutiilor. Aceasta explorare mai buna se face pe seama cresterii timpului afectat unui experiment, din cauza verificarilor suplimentare care se fac si care cuprind intreaga populatie (care poate fi numeroasa).

Incercarea de a realiza un algoritm genetic cat mai eficient inseamna de multe ori specializarea lui, dependenta foarte stransa de problema reala pe care o rezolva. Astfel trebuie facuta o alegere: se doreste realizarea unui algoritm cat mai general, care sa fie aplicabil cat mai multor probleme, si care evident nu va fi foarte performant, sau se doreste rezolvarea cat mai eficienta a unei anumite probleme.

Modificari esentiale pot aduce operatorii genetici folositi. Primul aspect asupra caruia se poate interveni este modul de alegere al operatorilor genetici. Astfel, se poate folosi binecunoscuta metoda a ruletei la selectia unui operator dintr-o lista de operatori posibili. Astfel, pentru cazul clasic al utilizarii a doi operatori (mutation si crossover) se poate atasa fiecaruia un factor de potrivire (de exemplu 80% pentru crossover si 20% pentru mutation) care va fi folosit la alegere. Insa aceasta metoda nu precizeaza care este numarul de cromozomi - copii generati, putandu-se spune ca circa 80% vor fi rezultati prin aplicarea operatorului crossover, iar ceilalti 20% prin aplicarea operatorului mutation. Adica in 4 cazuri din 5 vor rezulta cate 2 cromozomi - copii, in timp ce intr-un caz din 5 va rezulta un singur cromozom descendent.

Insa principalelele modificari asupra operatorilor vizeaza modul de functionare al acestora. Astfel, prima observatie asupra operatorului crossover este aceea ca se pot alege doua puncte semnificative intre care sa se faca interschimbarea, asa cum se arata in figura 4:

Aplicarea operatorului crossover pentru pozitiile 3 si 6 Primul parinte 1 1 1 1 1 1 1 1 Al doilea parinte 0 0 0 0 0 0 0 0 Primul fiu 0 0 0 1 1 1 0 0 Al doilea fiu 1 1 1 0 0 0 1 1

Figura 4. Operatorul crossover in doua puncte

Desi folosirea acestui din urma tip de operator crossover duce la imbunatatirea performantelor algoritmului genetic, totusi, exista o mare sansa ca anumite scheme utile sa dispara. De aceea se poate recurge la generalizarea procedeului, adica alegerea unui numar de k puncte semnificative si interschimbarea alternativa a portiunilor din cromozomii - parinti cuprinse intre doua astfel de puncte. Insa nici aceasta generalizare nu conduce la remedierea tuturor deficientelor, solutia numindu-se crossover uniform. Acest algoritm functioneaza astfel: pentru fiecare pozitie din cei doi parinti selectati se verifica un test de probabilitate, valoarea acestuia (0 sau 1) hotarand care este parintele a carui gena va participa la formarea primului cromozom - copil. Al doilea cromozom - copil se va forma din genele parintelui care nu a trecut testul de probabilitate. Aceasta functionare este ilustrata in figura 5:

Aplicarea operatorului crossover uniform

Primul parinte 1 1 1 1 1 1 1 1 Al 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 Al doilea fiu 0 1 1 0 1 1 1 0

Figura 5. Operatorul crossover uniform

Prin aceasta modificare pozitia unei scheme in cadrul cromozomului nu mai are nici o importanta pentru operatorul genetic, disparand posibilitatea ca unele scheme sa fie favorizate sau impiedicate sa prolifereze.

In cele discutate pana acum s-a considerat ca toti parametrii care intervin in algoritmul genetic au valori constante in timp. Daca valorile acestora se modifica in timp (au valori diferite pentru generatiile de la inceputul experimentului si pentru cel de la sfarsitul acestuia) atunci se pot influenta performantele algoritmului genetic.

Evident, va fi necesar un studiu comparativ pentru a stabili felul variatiei. Suportul teoretic al acestei variatii este dat de efectele operatorilor. Spre exemplu, operatorul crossover realizeaza "amestecarea" unor caracteristici valoroase existente in parinti, in timp ce operatorul mutation realizeaza "explorarea locala", in jurul unui singur individ. De aceea apare ca naturala acordarea unor sanse mai mari pentru crossover la inceputul experimentului, pentru a initia combinarea schemelor existente in populatia initiala (aleatoare!), in aceasta perioada operatorul mutation fiind mai putin utilizat. Corespunzator, spre sfarsitul experimentului, cand evolutia a condus spre obtinerea unor indivizi mai dotati, e de preferat explorarea in vecinatatea acestora, acordand sanse mai mari operatorului mutation, deoarece crossover ar putea strica prin combinare indivizi valorosi. Se vor specifica valorile de inceput si de sfarsit pentru probabilitatile de activare a operatorilor genetici, pasul sau numarul de generatii dupa care se vor modifica valorile acestora.

In fine, o ultima modalitate de a obtine rezultate mai bune este folosirea unui operator suplimentar, heuristic. Acesta va trebui sa actioneze cunoscand problema concreta de rezolvat, aducand modificari cromozomului asupra caruia se aplica doar daca acestea ii sunt benefice cromozomului. In caz contrar, cromozomul nu va fi modificat. Datorita necesitatii verificarii fiecarui cromozom, operatie care poate consuma timp util, fara sa aduca un castig sigur, se recomanda folosirea acestui operator doar in prima parte a experimentului, cand exista mai multi indivizi cu potential neexplorat. Alegerea operatorului heuristic este puternic dependenta de problema rezolvata, putand fi folositi mai multi astfel de operatori, selectia celui care se va aplica fiind facuta printr-un mecanism de tip ruleta.

Ca in cazul multor alti algoritmi, o buna ridicare a nivelului de performanta poate fi obtinut daca se opteaza pentru paralelizarea algoritmilor genetici.

15.3.7. Justificarea funcţionării algoritmilor genetici

15.3.7.1. Schema

Fundamentarea teoretică a algoritmilor paraleli se bazează pe noţiunea de schemă. O schemă este un şir construit cu simbolurile 0, 1 şi * (don't care). Schema permite studierea similitudinilor între cromozomi. Schema are următoarele caracterristici:

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 şi n●2m scheme.

15.3.7.2. Proprietăţile schemelor

Ordinul unei scheme S, notat o(S) este numărul de poziţii fixe (0 sau 1) ale schemei. De el depinde probabilitatea de supravieţuire a schemei la mutaţii. Exemplu: schema S1 = (010***11***1) are o(S1) = 6.

Lungimea caracteristică a unei scheme S, notată (S), este distanţa între prima şi ultima poziţie fixă a schemei. De ea depinde probabilitatea de supravieţuire a schemei la încrucişări. Exemplu: (S1) = 11.

15.3.7.3. Evoluţia

Studiem evoluţia schemelor în operaţiile de selecţie, încrucişare şi mutaţie.

Selecţia

Fie pop_size dimensiunea populaţiei, m lungimea unui şir şi p = (S,t) numărul de şiruri din populaţia la momentul t având schema S. Ne interesează (S,t+1). Pentru aceasta considerăm potrivirea schemei S la momentul t, eval(S,t) definită ca media potrivirilor şirurilor din populaţia reprezentată de S. Fie p=(S,t) numărul acestora.

Atunci:

p

j

ij

p

vevaltSeval

1

)(),( . Dacă la o selecţie şirul vi are probabilitatea

)(

)(

tF

vevalp i

i de a fi selectat, unde

sizepop

iivevaltF

1

)()( este potrivirea totală, atunci:

Un şir care corespunde schemei S are probabilitatea de selecţie egală cu

)(

),(

tF

tSeval.

Numărul de şiruri care corespund schemei S este (S,t).

Numărul de selecţii este pop_size.

Rezultă: )(

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

tF

tSevalsizepoptStS , adică

———

)(

),(*),()1,(

tF

tSevaltStS (ecuaţia 1). În ecuaţia 1, numită ecuaţia creşterii

schemei reproductive, sizepop

tFtF

_

)()(

———

este protrivirea medie a populaţiei. O

schemă "peste medie" are 1)(

),(———

tF

tSeval şi primeşte un număr mai mare de indivizi în

noua populaţie. Deci, dacă )1()(),(____

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

sau tStS )1(*)0,(),( , adică numărul de indivizi este în creştere conform unei progresii geometrice.

Încrucişarea

Fie şirul (1110111101001) şi două scheme care-i corespund:

S0=(****111******), ( S0)=2

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

Dacă şirul este selectat pentru încrucişare şi poziţia de tăiere este 10, schema S0 se regăseşte într-unul din fii, în timp ce schema S1 are şanse foarte reduse de reproducere. Este clar că lungimea caracteristică joacă un rol important în reproductibilitatea schemei la încrucişare.

Avem următoarele:

Locul de încrucişare este selectat uniform între m-1 posibilităţi; rezultă că

probabilitatea de distrugere a schemei S este 1

)()(

m

SSpd

iar probabilitatea de

supravieţuire 1

)(1)(

m

SSps

. Considerând şi probabilitatea pc de selecţie pentru

încrucişare, avem de fapt 1

)(*1)(

m

SpSp cs

. Deoarece se pot combina indivizi

aparţinând unor scheme comune formula trebuie modificată astfel:

1

)(*1)(

m

SpSp cs

.

Efectul combinat al selecţiei şi încrucişării este reprezentat de următoarea formă a ecuaţiei de creştere a schemelor reproductibile:

)1

)(*1(*

)(

),(*),()1,(

———

m

Sp

tF

tSevaltStS c

(ecuaţia 2).

Mutaţia

Mutaţia afectează o schemă S dacă modifică una din poziţiile sale fixe, în număt de o(S). Deoarece probabilitatea mutaţiei unui singur bit este pm, probabilitatea

nemodificării sale este (1- pm). Mutaţia unui bit fiind independentă de celelalte, probabilitate ca o schemă S să supravieţuiască unei mutaţii este )()1()( So

ms pSp ;

deoarece pm<<1 rezultă )(*1)( SopSp ms . Efectul combinat al selecţiei,

încrucişării şi mutaţiei este dat de ecuaţia 3:

))(*1

)(*1(*

)(

),(*),()1,(

———Sop

m

Sp

tF

tSevaltStS mc

(ecuaţia 3)

care corespunde următorului enunţ

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

Consecinţa imediată este că un algoritm genetic explorează spaţiul soluţiilor prin scheme scurte, de ordin scăzut, care ulterior sunt folosite pentru schimb de informaţii prin încrucişare.

Ipoteza blocurilor constructive. Un algoritm genetic atinge performaţe aproape optime prin juxtapunerea unor scheme scurte, de ordin scăzut, de mare performaţă, numite blocuri constructive.

Pentru anumite probleme ipoteza este violată. De exemplu, schemele

S1=(111********)

S2=(*********11)

sunt peste medie, dar combinaţia lor

S3=(111******11)

este mai puţin potrivită ca

S4=(000******00)

Un algoritm genetic poate avea dificultăţi să conveargă spre un optim ca S0=(11111111111) şi poate cădea pe soluţii suboptime care se potrivesc cu S4. Fenomenul se numeşte falsificare (deception).

15.3.8. Considerarea constrângerilor în algoritmii genetici

În unele situaţii, aplicarea operatorilor genetici conduce la obţinerea unor indivizi care nu corespund soluţiilor potenţiale ale problemei de rezolvat. De exemplu, în cazul problemei partiţionării grafurilor, indivizii pentru care diferenţa dintre numărul de

zerouri şi numărul de unităţi este mai mare de unu nu corespund unei soluţii corecte, deoarece problema cere împărţirea nodurilor în două grupuri de dimensiuni egale.

Tratarea acestor situaţii, în care indivizii nu respectă constrângerile impuse de problemă, se poate face prin următoarele metode:

transformarea problemei într-una fără constrângeri, prin aplicarea unor penalizări indivizilor care nu respectă constrângerile impuse de problemă

eliminarea soluţiilor necorespunzătoare

aplicarea unor algoritmi de corecţie.

Să considerăm problema rucsacului. Enunţul problemei este următorul: date fiind o mulţime de ponderi W, profiturile asociate P şi capacitatea C a rucsacului, se cere să se găsească un vector binar X = <x1, x2, ..., xn> astfel că

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

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

15.3.8.1. Algoritm bazat pe penalizări

În acest caz, funcţia de evaluare a unei soluţii are forma

eval(X) = i = 1,n xi * pi - Pen(X)

unde Pen(X) = 0 pentru soluţiile fezabile şi

Pen(X) = 0 pentru soluţiile nefezabile.

Pentru funcţia de penalizare se poate alege una din următoarele variante:

logaritmică, Pen1(X) = log2 (1 + ( i = 1,n xi * wi - C))

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

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

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

Algoritmul bazat pe corecţia soluţiei foloseşte pentru evaluare formula

eval(X) = i = 1,n x'i * pi unde X’ este versiunea corectată a lui X.

procedure corectie (X)

begin

depasire := false

X’ := X

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

do depasire ->

i := selecteaza un element din sac

scoate elementul x’i := 0

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

od

end

Variantele de corecţie sunt incluse în selecteaza. Putem avea o alegere aleatoare sau un algoritm greedy, în care elementele sunt sortate în ordinea descrescătoare a rapoartelor pi / wi şi se alege întotdeauna ultimul element.

S-a constatat experimental că înlocuirea cromozomilor originali cu cromozomi reparaţi într-o proporţie de 5% conduce la performanţe mai bune decât pentru orice altă proporţie (regula 5%).

15.3.8.2. Algoritmul bazat pe decodificatori

Acest algoritm adoptă o reprezentare pentru care orice combinaţie rezultată în urma operaţiilor genetice reprezintă o soluţie validă. Un cromozom este interpretat ca o strategie de a incorpora elemente într-o soluţie. Fiecare cromozom este un vector de n întregi. Componenta i a vectorului este un întreg din domeniul 1..n-i+1 şi indică poziţia unui element al unei liste L, din care elementele selectate sunt eliminate pe măsura selecţiei.

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

Ca efect, la mutaţie, gena i poate lua orice valoare între 1 şi n-i+1, iar încrucişarea aplicată unor părinţi corecţi produce mereu descendenţi corecţi. Algoritmul de decodificare este următorul:

procedure decode (X)

begin

construieste o lista de elemente L

i := 1

suma-ponderi := 0

suma-profit := 0

do i <= n ->

j := xi

elimina elementul cu numarul de ordine j din L

if suma-ponderi + wj <= C ->

suma-ponderi := suma-ponderi + wj

suma-profit := suma-profit + pj

fi

i := i+1

od

end

Variantele pentru construieste sunt:

aleatoare, când ordinea elementelor din listă corespunde ordinii elementelor din fişierul de intrare (care este aleatoare)

greedy, când procedura creează o listă L punând elementele în ordinea descrescătoare a rapoartelor pi / wi; decodificarea lui X se face pe baza secvenţei sortate.

15.4. Algoritmi genetici paraleli

Doua au fost conditiile care au favorizat aparitia acetui tip de algoritmi: pe de o parte necesitatea de a putea rezolva cat mai rapid probleme foarte complexe (in care sa intervina populatii formate dintr-un numar mare de indivizi), iar pe de alta parte aparitia unor calculatoare paralele relativ ieftine si deci accesibile. Un algoritm genetic paralel poate fi obtinut dintr-unul secvential folosind mai multe cai de transformare, insa indiferent de metoda aleasa apar o serie de aspecte noi legate in special de necesitatea comunicarii intre diversele entitati care evolueaza in paralel; este foarte important ca aceasta comunicare sa nu consume mult timp si sa nu apara puncte de gatuire care sa determine cresterea suplimentara a timpului de executie. Indeplinirea acestor conditii va duce la realizarea unei implementari optime si la posibilitatea realizarii unor experimente deosebit de flexibile si in timp scurt.

Sa presupunem ca pe o masina paralela exista P procesoare disponibile. Prima idee ar fi paralelizarea operatiilor efectuate in cadrul rularii unui experiment. Daca admitem ca un procesor este necesar pentru a controla paralelismul celorlalte, inseamna ca raman P - 1 procesoare care pot alege in paralel P - 1 perechi de parinti pentru a le aplica tot in paralel (acelasi) operator crossover, iar apoi, dupa aplicarea (evident tot in paralel) a operatorului mutation se vor putea evalua in paralel cromozomii - copii rezultati. In acest fel durata in care o generatie este procesata se va reduce

considerabil daca se foloseste un numar mare de procesoare. Factorii care ar putea degrada performantele unui astfel de algoritm sunt posibilul overhead introdus de comunicatie si mecanismul de selectie folosit (exista o singura populatie la care fac acces cele P - 1 procesoare, deci un posibil punct de gatuire!). O varianta ar putea fi cea in care procesorul coordonator (cel care de fapt supervizeaza intreaga populatie) realizeaza selectia si trimite candidatii spre celelalte procesoare, care dupa aplicarea operatorilor trimit inapoi spre "centru" noii indivizi si eventual alte informatii.

Aceasta abordare are mai putin sprijin teoretic, deoarece in viata reala o astfel de populatie izolata nu ofera mari sanse de evolutie. De aceea este natural sa se opteze spre utilizarea unei populatii distribuite. Aceasta poate fi realizata fie prin existenta unei unice populatii in care fiecare individ interactioneaza doar cu cativa dintre vecinii sai, sau prin crearea mai multor subpopulatii (independente una fata de alta sau care pot interactiona intre ele). Procesoarele pot schimba intre ele cele mai bune solutii obtinute, comunicatia avand la baza o structura topologica spatiala. Pe baza acesteia se poate vorbi de granularitatea algoritmului genetic paralel.

O granularitate mare corespunde unei "lumi" formate din mai multe subpopulatii similare, asupra carora se aplica in paralel acelasi algoritm genetic. La anumite momente de timp unii indivizi vor putea trece de la o subpopulatie la alta, rostul acestor migratori fiind acela al cresterii gradului de diversitate. In functie de numarul de migratori si de populatiile spre care migreaza se pot obtine diferite variante de algoritmi. De asemea este importanta si frecventa cu care migratorii se pun in miscare si modul in care ei sunt selectati. Este recomandat ca numarul si frecventa acestor migratori sa nu fie mari pentru ca fiecare subpopulatie sa exploreze alta portiune din spatiul solutiilor (se presupune ca populatiile initiale sunt distincte iar un schimb exagerat de informatie genetica intre ele le-ar apropia foarte mult, scazand capacitatile algoritmului). Cea mai folosita topoplogie este cea de inel, insa se pot utiliza si altele (de exemplu tor).

Un algoritm de granularitate fina presupune ca in fiecare procesor se pastreaza un individ; acesta va putea interactiona cu cei din vecinatatea sa pentru recombinari. Aspectele importante in acest caz vor dimensiunea vecinatatii, topologia deconectarea a procesoarelor, procedeul folosit pentru inlocuirea generatiei curente. Spre exemplu pentru o topologie de tip tor bidimensional, cel mai valoros dintre cei 4 vecini ai elementului curent va fi ales pentru recombinare; daca elementul obtinut va fi mai bun il va inlocui pe cel curent.

Ca un rezumat al celor afirmate pana acum, iata o posibila clasificare a metodelor ce pot fi utilizate la rezolvarea unor probleme de cautare si optimizare folosind algoritmi genetici paraleli:

varianta de procesare independenta si identica (Identical, Independent Processing - IIP) in care acelasi algoritm genetic se executa pe procesoare diferite, pornind de la populatii initiale diferite si fara nici o interactiune intre populatii; cel mai bun rezultat obtinut in toate experimentele fiind considerat solutia problemei;

varianta Master-Slave in care procesul Master dirijeaza evolutia algoritmului, in timp ce procesele Slave executa doar calculele de evaluare a fiecarui individ;

varianta Parallel Genetic Algorithm, in care se ruleaza acelasi algoritm genetic pe sub-populatii diferite, aseamanator cu IIP, cu deosebirea ca anumiti indivizi (cei mai buni) migreaza cu o anumita frecventa de la populatia in care au aparut spre alte populatii;

varianta celulara, fiecare procesor se ocupa de un singur individ: operatorul mutation va fi strict local, in timp ce crossover va implica o colaborare intre doua procesoare vecine; migrarea poate fi introdusa ca o modalitate de a accelera difuzarea indivizilor mai performanti.

In timp ce primele trei variante se preteaza arhitecturilor MIMD, ultima e caracteristica masinilor SIMD, in care fiecare procesor executa la un moment dat aceeasi operatie asupra datelor existente in memorie.

Dintre acestea, varianta a treia, numita Parallel Genetic Algorithm, pare a oferi mai multa flexibilitate. Astfel caracteristicile globale ale populatiior nu trebuie sa fie aceleasi: numarul de indivizi din fiecare populatie poate fi altul si poate varia in timp; metoda de selectie a parintilor poate fi diferita si se poate modifica pe parcursul evolutiei; probabilitatile de activare a operatorilor genetici pot fi diferite si variabile in timp, se pot folosi operatori genetici diferiti pentru fiecare populatie; varianta de inlocuire a unei generatii cu una noua poate fi specifica unei populatii; modul de selectie al migratorilor poate fi altul de la o populatie la alta (se poate alege cel mai bun cromozom, cel mai slab, unul la intamplare, etc.).

La modul general adaptarea acestor parametri poate fi facuta la diferite nivele: individ, subpopulatie, populatie. De asemenea poate fi luat un exemplu des intalnit in lumea vie, acela al unor grupuri de indivizi care concureaza (lupta) pentru obtinerea acelorasi resurse vitale. In acest caz este evident ca nu se va mai face schimb de migratori, fiecare populatie luptand pentru sine, cautand sa gaseasca strategia optima de adaptare. Aceasta presupune ca dupa aparitia unei noi generatii intreaga subpopulatie va fi evaluata (ca un intreg), fiind favorizata in cazul in care este mai valoroasa decat cea pe care o va inlocui. Astfel, o populatie de dimensiune fixa poate fi impartita in grupuri de dimensiuni variabile, care trebuie sa simuleze lupta unor specii similare pentru hrana. Va fi nevoie de un criteriu de selectie bazat pe cel mai un

individ din grup (sau pe cei mai buni indivizi din ultimele k generatii). Pe baza lui va functiona criteriul calitate, care va determina cresterea dimensiunii grupului cu cea mai buna strategie si reducerea numarului membrilor celorlalte grupuri.

Alti algoritmi genetici care pot fi utilizati de populatiile implicate sunt urmatorii:

CHC: Caracteristica acestuia este modul in care se formeaza generatia noua, la aceasta participand atat generatia curenta (curenta cu o parte din indivizi), cat si generatia intermediara de indivizi noi, care completeaza noua generatie. Partile de participare sunt stabilite de regula la 50%, luandu-se de regula indivizii cei mai buni. Alegerea parintilor pentru reproducere se face cu evitarea incestului, pe baza distantei Hamming.

Genitor: Se bazeaza pe mentinerea unei populatii sortate. Exista insa si posibilitatea de a renunta la sortarea populatiei, fapt care ar aduce substantial un castig de timp: in urma unei selectii de tip turneu se aleg doi parinti care vor da nastere unui urmas; acesta va inlocui ultimul individ (cel mai slab) al populatiei.

Primul pas consta in realizarea unei treceri de la problema reala de optimizat la reprezentarea folosita de regula de un algoritm genetic. Adica va trebui de fapt sa gasim o codificare a solutiei pe care o cautam (cum va arata un cromozom).

Varianta de operator de încrucişare cea mai convenabilă este crossover uniform, in care pentru obtinerea copiilor se genereaza aleator o masca binara, de lungime egala cu dimensiunea cromozomilor. Fiecare parinte va copia in succesorul corespunzator pozitiile cu zero in masca binara si va completa celelalte pozitii cu valoarea de pe aceeasi pozitie din celalalt parinte. Operatorul crossover are asociata o probabilitate de activare pc. Daca testul de probabilitate este trecut se activeaza operatorul, care pe baza unei masti binare generate aleator va construi noii cromozomi. Dupa construire acesti cromozomi vor fi corectati daca este cazul. Daca testul de probabilitate nu a fost trecut, atunci cromozomii - copii se vor obtine prin simpla copiere a cromozomilor parinti.

Parinte 1 1 0 0 1 1 1 0 0 Parinte 2 0 0 1 1 0 1 1 0 Masca aleatoare 0 1 1 1 0 1 1 0 Copil 1 1 0 1 1 1 1 1 0 Copil 2 0 0 0 1 0 1 0 0 Copil 1 dupa corectie 1 0 0 0 1 1 1 0 Copil 2 dupa corectie 1 0 1 1 0 1 0 0

Figura 6. Operatorul crossover

Operatorul mutation mai des folosit schimba genele unui cromozom dintr-un interval generat aleator. Daca un test de probabilitate (cu o valoare pm) este trecut, gena corespunzatoare din intervalul ales este modificată.

Interval Parinte 0 1 1 0 1 0 1 0 Probabilitati generate .3 .5 .7 .1 (0.32 = limita) Copil dupa mutation 0 0 1 0 0 0 1 0 Copil dupa corectie 1 0 1 1 0 0 1 0

Figura 7. Operatorul mutation

15.5. Programe evolutive

Un program evolutiv este un algoritm iterativ probabilist care menţine o populaţie de indivizi, notată P(t) = {x1

t, x2t, ..., xn

t } pentru iteraţia t. Fiecare individ reprezintă o soluţie potenţială a unei probleme de rezolvat, fiind reprezentat ca o structură de date S, oricât de complexă. Structura unui program evolutiv este următoarea:

procedure program-evolutiv

begin

t := 0

initializeaza P(t)

evaluează P(t)

do not coditie-de-terminare ->

t := t+1

selecteaza P(t) din P(t-1)

modifica P(t)

evalueaza P(t)

od

end

Evaluarea lui P(t) înseamnă evaluarea fiecărei soluţii xit obţinându-se o măsură a

“potrivirii” sale. În pasul de selecţie, cei mai valoroşi indivizi formează o nouă populaţie. Prin aplicarea operatorilor genetici, acestei populaţii îi sunt adăugaţi noi indivizi. Operatorii genetici sunt: unari, de tip mutaţie n-ari, de tip încrucişare.

După un număr de generaţii, programul converge. Cei mai buni indivizi reprezintă soluţiile apropiate de optim.

Ideea programelor evolutive se bazează pe cea a algoritmilor genetici, dar:

foloseşte un set mai bogat de structuri de date (în timp ce AG clasici folosesc şiruri binare de lungime fixă)

foloseşte un set extins de operatori genetici (în timp ce AG folosesc mutaţia binară şi încrucişarea binară).

Un algoritm genetic clasic cere aducerea problemei la o formă potrivită prin găsirea unor corespondenţe între soluţiile potanţiale şi reprezentările binare, aplicarea corecţiilor necesare pentru respectarea constrângerilor problemi etc.

Problemã Algoritm genetic

Problemã modificatã

Figura 8. Algoritm genetic

Un program evolutiv lasă problema nemodificată, dar adaptează operatorii genetici la reprezentările cele mai potrivite ale soluţiilor.

Problema Algoritm genetic - AG

Program evolutiv

Figura 9. Program evolutiv

Un avantaj al algoritmilor genetici este independenta de domeniul specific problemei. Totusi, atunci cand intervin constrangeri complicatre, functiile de decodificare si de corectie a sirurilor de biti transforma algoritmul genetic intr-o metoda dependenta de problema. Pe de alta parte, programele evolutive ar putea deveni independente de problema daca s-ar crea structuri de date cat mai diverse si functii de evaluare corespunzatoare. Rezolvarea unei probleme s-ar transforma in cautarea structurilor potrivite problemei si aplicarea lor.

15.5.1. Un exemplu - Problema transportului

15.5.1.1. Enuntul problemei

Se cere sa se stabileasca un plan de transport cu cost minim pentru un singur gen de marfa, de la un numar de surse la un numar de destinatari, in urmatoarele conditii: o destinatie poate primi marfa de la mai multe surse costul unei rute este proportional cu cantitatea transportata (problema este lineara). Fie: n surse k destinatari sour[i] cantitatea furnizata de sursa i dest[j] cantitatea ceruta de destinatia j cost[i,j] costul unitar de transport intre I si j x[i,j] cantitatea transportata intre i si j Se cere sa se minimizeze

Σ Σ cost[i,j]*x[i,j] pentru i=1,n; j=1,k cu constrangerile

Σj=1,k x[i,j] <= sour[i]

Σi=1,n x[i,j] >= dest[j]

x[i][j] >= 0 pentru i=1,n; j=1,k

Problema este balansata atunci cand totalul furnizat de surse egaleaza totalul cerut de destinatari: cantitatea ceruta = cantitatea furnizata Cand sour[i] si dest[j] sunt intregi avem x[i,j] intregi si cel mult n+k-1 sunt pozitivi. Exemplu n = 3; sour = [15,25,5] k = 4; dest = [5,15,15,10]

Matricea de cost este urmatoarea:

10 0 20 11 12 7 9 20 0 14 16 18

Matricea X corespunzatoare planului optim de transport este urmatoarea (in reprezentare au fost adaugate: o coloana corespunzatoare vectorului sour si o linie corespunzatoare vectorului dest)

sour \ dest 5 15 15 10 15 0 5 0 10 25 0 10 15 0 5 5 0 0 0

Solutia are un cost total egal cu 315.

15.5.1.2. AG clasic

Fiecare solutie reprezentata ca un sir agregat de biti

v1,v2,…,vp

unde p = n*k

si vi sir binar de forma vi = wi0,…,wi

s

vi reprezinta un element x[j,m] asociat cu linia j coloana m ale matricei X, unde indecsii j si m sunt legati de pozitia i prin urmatoarele relatii (rezultate din procedeul de liniarizare a matricei X):

j = inf [(i-1)/k+1] m = (i-1) mod k +1

iar s este ales ca sa se poata reprezenta intregul maxim din problema. Consecinta acestei solutii este ca nu exista o definitie simpla si naturala a operatorilor genetici, producerea unor solutii care sa satisfaca constrangerile necesitand corectii complicate. De exemplu, mutatia inseamna modificarea unui singur bit al unei singure valori vi; ea atrage dupa sine alte modificari asupra valorilor vj (j≠i) cerute de respectarea constrangerilor problemei. Toate modificarile trebuie "judecate" pe liniile si coloanele matricei X desi in rezolvare se foloseste o reprezentare lineara in forma sirului agregat de biti v1,v2,…,vp.

15.5.1.3. Reprezentare vectoriala

O solutie a problemei este reprezentata ca un vector (sir) de p=n*k numere intregi cu valori in domeniul 1..p. Ea este interpretata ca o strategie de a incorpora elemente în soluţie, conform abordarii bazate pe codificatori. De data aceasta, fiecare numar indica o pozitie in matricea X considerand o linearizare pe linii, iar intregul vectorul arata ordinea in care trebuie completate elementele acestei matrice. De exemplu, operatia corespunzatoare primei pozitii a vectorului {7,....}este modificarea elementului din linia 2 coloana 3 a matricei X cu valoarea minima dintre sour[2] si dest[3], adica 15 urmata de diminuarea cu aceeasi valoare a elementelor sour[2] si dest[3].

5 15 15 (-15=0) 10 15 0 0 0 0

25 (-15=10) 0 0 15 0 5 0 0 0 0

Procedura de decodificare a unei solutii vecrotiale este urmatoarea: procedure initialization; begin seteaza ca nevizitate numerele de la 1 la p; do not toate nodurile vizitate -> select urmatorul numar q si marcheaza vizitat; {calc nr linie i si coloana j corespunzatoare} i = (q-1)/k+1; j=(q-1) mod k +1; val = min(sour[i], dest[j]); v[i][j] = val; sour[i] = sour[i]-val; dest[j] = dest[j] – val od end Solutia optima pentru problema de transport specificata anterior este produsa de secventa {7,9,4,2,6, *,*,*,*,*,*,*}.

5 15 15 10

15 0 5 0 10 25 0 10 15 0 5 5 0 0 0

Observatii orice permutare de numere cu valori intre 1 si p produce o solutie unica ce satisface constrangerile; operatorii genetici sunt simplu de realizat, dupa cum urmeaza. Mutatia se face prin interschimbarea a doua numere din sir. Pentru Incrucisare, se ia un subsir de numere (cele subliniate in exemplul de mai jos) din primul cromozom pastrandu-se pozitia lor, iar restul numerelor se pun in celelalte pozitii, in ordinea din al doilea cromozom. De exemplu, pentru perechea {1,2,3,4,5,6,7,8,9,10,11,12} {7,3,1,11,4,12,5,2,10,9,6,8} rezulta prin incrucisare {3,1,11, 4,5,6,7,12,2,10,9,8} Evaluarea Dintr-o reprezentare vectoriala (permutare) se obtine usor matricea x[i][j] corespunzatoare (conform procedurii initialization). Apoi, din matricea x[i][j] se calculeaza simplu costul total, dupa formula:

Σ Σ cost[i,j]*x[i,j] pentru i=1,n; j=1,k

15.5.1.4. Reprezentarea matriceala

O alta varianta este de a reprezenta o solutie chiar in forma originala a problemei, ca matricea

X = (x[i][j])i=1,n; j=1,k Satisfacerea restrictiilor problemei si evaluarea se realizeaza foarte simplu. Pentru operatorii genetici sunt posibile urmatoarele variante. Mutatia Pentru matricea X urmatoare (corespunzatoare unei probleme cu 4 surse si 5 destinatii) in care nu au mai fost reprezentati vectorii sour si dest,

0 0 5 0 3 0 4 0 0 0 0 0 5 7 0 3 1 0 0 2

se selecteaza o submatrice W care corespunde unui anumit subset de linii si unui anumit subset de coloane (de exemplu, liniile 2,4 si coloanele 2,3,5);

4 0 0 1 0 2

se calculeaza W' astfel incat sumele pe linii si coloane sa ramana aceleasi cu sumele corespunzatoare din W;

2 0 2 3 0 0

se inlocuieste W cu W' in X si se obtine o noua matrice:

3 5 10 7 5 8 0 0 5 0 3 4 0 2 0 0 2 12 0 0 5 7 0 6 3 3 0 0 0

Incrucisarea Fie X1 si X2 doua matrice selectate ca parinti. X1 X2

1 0 0 7 0 0 4 0 0 0 2 1 4 0 5 0 0 6 0 0

0 0 5 0 3 0 4 0 0 0 0 0 5 7 0 3 1 0 0 2

Algoritmul de incrucisare are urmatorii pasi. Se creeaza matricile DIV si REM astfel incat:

DIV[i,j] = inf ((X1[i,j] + X2[i,l])/2) REM[i,j] = (X1[i,j] + X2[i,j]) mod 2.

DIV (media)

REM (restul)

Se deriveaza din REM doua matrice REM1 si REM2 astfel incat

REM = REM1 + REM2 si

sour REM1[i] = sour REM2[i] = sour REM[i]/2, pentru i = 1..k

dest REM1[j] = dest REM2[j] = dest REM[j]/2, pentru j = 1..n

REM1 REM2

0 0 2 3 1 0 4 0 0 0 1 0 4 3 2 1 0 3 0 1

1 0 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0

0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0

1 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0

Calculeaza cei doi fii V3 si V4 astfel ca: V3 = DIV + REM1 V4 = DIV+REM2

15.6. Alta probleme de optimizare - Dilema prizonierului

15.6.1. Subiectul problemei

Problema cunoscuta sub numele de “dilema prizonierului” are urmatorul enunt. Doi prizonieri sunt tinuti in celule separate, fara posibilitatea de comunicare. Fiecare prizonier trebuie sa intreprinda una din urmatoarele actiuni, indepedent de celalalt: cooperare sau evadare. Daca doar un prizonier evadeaza, atunci este recompensat, iar celalalt este pedepsit. Daca nici unul nu evadeaza, atunci amandoi sunt rasplatiti foarte modest. Daca amandoi evadeaza, atunci ei sunt pedepsiti. Dilema prizonierului este de a decide sa coopereze sau sa evadeze.

Dilema prizonierului se poate juca in doi, fiecare jucator fiind un prizonier si trebuind sa ia o decizie. Scorul jocului poate fi dat de urmatorul punctaj, in functie de deciziile celor doi:

Jucatorul 1 Jucatorul 2 P1 P2 Comentariu Evadeaza Evadeaza Coopereaza Coopereaza

Evadeaza Coopereaza Evadeaza Coopereaza

1 5 0 3

1 0 5 3

pedeapsa pentru evadare simultana rasplata evadarii / pedeapsa cooperarii pedeapsa cooperarii / rasplata evadarii rasplata cooperarii

Algoritmii genetici pot fi folositi pentru a invata strategii de joc pentru aceasta problema a prizonierului.

0 0 3 3 2 0 4 0 0 0 1 1 4 4 2 2 0 3 0 1

1 0 2 4 1 0 4 0 0 0 1 0 5 3 3 1 1 3 0 1

15.6.2. Proiectarea algoritmului

Pentru reprezentarea cromozomilor se considera ca decizia curenta se face dupa trei mutari anterioare. Deoarece sunt patru alternative pentru fiecare mutare, sunt in total 43 = 64 cazuri posibile pentru cele trei mutari. Reprezentarea lor se poate face cu un numar de 6 biti (26 = 64). Pentru fiecare caz (fiecare istorie de trei mutari anterioare) sunt posibile doua mutari (Evadare sau Cooperare) care pot fi reprezentate ca valori binare. Daca un bit are valoarea 0, inseamna ca decizia jucatorului este de a Evada; pentru valoarea 1, decizia este de a Coopera. Rezulta 64 de biti pentru reprezentarea tuturor mutarilor curente posibile, in functie de cele trei mutari anterioare. In total, un cromozom are 70 = 6+64 biti si reprezinta o strategie de efectuare a mutarii curente in functie de trei mutari anterioare.

Un algoritm genetic are nevoie de o functie de evaluare pentru a selecta indivizii cei mai buni ai unei populatii. In cazul dilemei prizonierului, toti indivizii sunt pusi sa faca un numar de jocuri si se calculeaza o medie, impartind punctajul total obtinut la numarul de jocuri. Functia de evaluare a unui cromozom intoarce aceasta medie. Se considera ca un individ este mai bun decat altul daca are o medie mai mare, adica deciziile sale au fost mai bune.

Pasii algoritmului genetic sunt urmatorii:

Se considera o populatie initiala, in care fiecare jucator este reprezentat de un sir de 70 de biti generati aleator.

Se evalueaza strategia fiecarui jucator, prin calculul scorului mediu obtinut intr-un numar de jocuri stabilit

Se face selectia jucatorilor pentru inmultire. Pentru asta, juctorului cu un scor mijlociu i se acorda dreptul la o imperechere, celui cu scor superior dreptul la doua imperecheri, iar celui cu scor inferior nici un drept

Se face imperecherea jucatorilor selectati aplicandu-se operatiile de incrucisare si mutatie.

In final, se obtine o noua populatie si se reia ciclul