calcul evolutiv

download calcul evolutiv

of 45

Transcript of calcul evolutiv

Elemente de calcul 1 evolutivCatalin Stoean [email protected] http://inf.ucv.ro/~cstoean

Eiben and J. E. Smith, Introduction to Evolutionary Computing

1A.E.

Catalin Stoean

Inteligenta Artificiala

Ce este calculul evolutiv?Calculul evolutiv reprezint un domeniu de cercetare al informaticii.Dup cum sugereaz i numele, sunt implicate calcule, ns domeniul este inspirat din procesul evoluiei naturale.

Algoritmii care apar n acest domeniu se numesc algoritmi evolutivi i ei includ subdomenii precum:programarea evolutiv strategii evolutive algoritmi genetici programare genetic2/45

Catalin Stoean

Inteligenta Artificiala

Ce urmrim astzi?Concepte de baz ale calculului evolutiv:Metafora evolutiv Componentele unui algoritm evolutiv Aplicaii pe probleme concreteProblema damelor Optimizarea unei funcii

3/45

Catalin Stoean

Inteligenta Artificiala

Metafora evolutivPuterea evoluiei n natur este evident, deci este normal ca evoluia natural s fie o surs de inspiraie pentru cercettori. Metafora fundamental a calculului evolutiv leag evoluia natural de un anumit tip de rezolvare de probleme, ncercare-i-eroare. Evoluia natural poate fi descris astfel: ntr-un mediu se gsete o populaie de indivizi care se lupt pentru supravieuire i are capacitatea de a se reproduce. Performana acestor indivizi este strns legat de felul n care indivizii se adapteaz la mediul nconjurtor i de modul n care indivizii reuesc s i ating scopurile. Performana fiecrui individ influeneaz n mod direct ansa lui de a se multiplica i de a supravieui.4/45

Catalin Stoean

Inteligenta Artificiala

Metafora evolutiv 2ntr-o astfel de vedere macroscopic a evoluiei, un rol cheie este jucat de selecie. Avnd un mediu care poate conine doar un numr redus de indivizi dotai cu instinctul primar al reproducerii, selecia este un factor inerent n cazul n care se dorete ca marimea populaiei s nu creasc exponenial. Selecia natuaral i favorizeaz, ca i n natur, pe indivizii care se lupt cel mai bine pentru resurse, altfel spus pe cei care se adapteaz cel mai bine la mediu. Este ceea ce se numete supravieuirea celor mai puternici.5/45

Catalin Stoean

Inteligenta Artificiala

Metafora evolutiv 3Analogia ntre contextul rezolvrii de probleme de tip ncercarei-eroare i evoluia natural se face n felul urmtor: Mediul n care se afl indivizii se identific cu problema de rezolvat Indivizii sunt poteniale soluii ale problemei Msura de performan va contoriza n acest caz ct de bun calitativ este soluia curent n rezolvarea problemei. Soluii poteniale sunt iniial generate iar cele care sunt mai bune calitativ au cele mai mari anse s fie pstrate i s participe la procesul de recombinare.6/45

Catalin Stoean

Inteligenta Artificiala

Metafora evolutiv 4EVOLUTIE Mediu Individ Performana REZOLVAREA DE PROBLEME Problem Soluie candidat Calitatea

Performana influeneaz ansele de reproducere i supravieuire Calitatea influeneaz ansele de a forma noi soluii7/45

Catalin Stoean

Inteligenta Artificiala

Ideile principaleO populaie cu indivizi exist ntr-un mediu cu resurse limitate. Competiia pentru aceste resurse face ca selecia s i avantajeze pe indivizii mai buni care s-au adaptat mai bine la mediu. Aceti indivizi acioneaz ca prini ai generaiei de noi indivizi obinui prin recombinare i mutaie. Noii indivizi sunt evaluai si lupt pentru supravieuire cu generaia anterioar (posibil chiar cu prinii lor). Selecia natural face ca performana populaiei s creasc odat cu trecerea timpului. Operatorii de variaie (mutaia i recombinarea) creeaz diversitatea necesar n populaii i aduc noutate. Selecia reduce diversitatea i acioneaz ca o for care duce la creterea calitii.

8/45

Catalin Stoean

Inteligenta Artificiala

Cautarea singulara vs. Cautarea din cadrul algoritmilor evolutiviCautarea singulara (hill climbing, simulated annealing) folosete o singur soluie care sufer transformri.Dezavantaj: se blocheaz des n maxime (optime) locale.

Algoritmii evolutivi folosesc multe soluii care evolueaz (sufer transformri) simultan figur dreapta.

Spaiul soluiilor

Spaiul soluiilor9/45

Catalin Stoean

Inteligenta Artificiala

Ce urmrim astzi?Concepte de baz ale calculului evolutiv:Metafora evolutiv Componentele unui algoritm evolutiv Aplicaii pe probleme concreteProblema damelor Optimizarea unei funcii

10/45

Catalin Stoean

Inteligenta Artificiala

Schema unui algoritm evolutivEvaluri Iniializare i evaluare6 2 7 6 7 4 3

Populaia9

Evaluarea

Selecia4

2

3

9

Mutaia

Reproducerea

11/45

Catalin Stoean

Inteligenta Artificiala

Schema unui algoritm evolutiv1. Se iniializeaz populaia cu indivizi generai aleator; 2. Se evalueaz fiecare individ; 3. Ct timp (condiia de terminare nu este satisfcut) execut 3.1 Se selecteaz prinii; 3.2 Se recombin perechi de prini; 3.3 Se aplic mutaia asupra descendenilor obinui dup recombinare; 3.4 Se evalueaz fiecare descendent; 3.5 Se selecteaz indivizii care vor forma urmtoarea generaie; 4. Sfrit ct timp12/45

Catalin Stoean

Inteligenta Artificiala

Componentele unui algoritm evolutivReprezentarea Evaluarea Populaia Selecia prinilor Operatorii variaionaliRecombinarea Mutaia

Iniializarea i terminarea13/45

Catalin Stoean

Inteligenta Artificiala

ReprezentareaSoluiile candidat ale problemei de rezolvat trebuie reprezentate (codificate) sub form de indivizi (cromozomi). Fiecare cromozom conine gene. Orice element din spaiul soluiilor trebuie s aib corespondent n spaiul cromozomilor i invers. Pentru fiecare problem trebuie aleas o reprezentare ct mai potrivit.

14/45

Catalin Stoean

Inteligenta Artificiala

Reprezentarea pentru problema damelor

Potenial soluie: o configuraie a celor 8 dame Cromozomul: o permutare a primelor 8 cifre.

Codificare

1 3 5 2 6 4 7 815/45

Catalin Stoean

Inteligenta Artificiala

Problema comis voiajoruluiProblema: Se dau n orae S se gseasc un tur complet de lungime minimal Reprezentare: Etichetm oraele 1, 2, , n Un tur complet este o permutare (pt. n =4: [1,2,3,4], [3,4,2,1]) Spaiul de cutare este imens: pentru 30 de orae sunt 30! 1032 tururi posibile!16/45

Catalin Stoean

Inteligenta Artificiala

Reprezentare pentru optimizarea unei funcii (gsirea maximului pe un interval)Imaginai-v c v dau z = f(x) puncte n plus la examen. f(x) = x sin(10 x) Gsii-l pe x n intervalul [-1, 2] astfel nct z s fie ct mai mare (ca s ctigai ct mai multe puncte)! Altfel spus, gsii x0 din [-1, 2] cu proprietatea c f(x0) f(x), pentru orice x din [-1, 2] In acest caz, spaiul soluiilor se poate identifica cu spaiul cromozomilor.

17/45

Catalin Stoean

Inteligenta Artificiala

Reprezentarea funciei

f(x) = x sin(10 x), pe intervalul [-1, 2].

18/45

Catalin Stoean

Inteligenta Artificiala

Componentele unui algoritm evolutivReprezentarea Evaluarea Populaia Selecia prinilor Operatorii variaionaliRecombinarea Mutaia

Iniializarea i terminarea19/45

Catalin Stoean

Inteligenta Artificiala

Funcia obiectivnainte de a defini funcia de performan, trebuie stabilit obiectivul problemei, care este sarcina care trebuie ndeplinit. Este vorba de gsirea funciei obiectiv. n cazul problemei comis-voiajorului, obiectivul se refer la minimizarea drumului pe care l parcurge comisvoiajorul prin vizitarea fiecrui ora o singur dat cu ntoarcere n oraul de pornire. Pentru problema damelor, obiectivul este de a aeza cele 8 dame ntr-o configuraie astfel nct s nu se atace reciproc.20/45

Catalin Stoean

Inteligenta Artificiala

Funcia de evaluare (performan)Rolul funciei de performan (sau de evaluare, ori de calitate) este de a msura ct de bine se adapteaz indivizii la mediu. Pentru unele probleme poate fi aceeai cu funcia obiectiv (de exemplu, n optimizarea de funcii). Funcia de evaluare atribuie fiecrui individ o valoare (de obicei, real) care reprezint ct de bun (de performant) este cromozomul respectiv. Se dorete maximizarea performanei indivizilor, ceea ce duce de obicei la dorina de a maximiza valorile funciei de performan (nu n tot timpul este cazul ns, vezi funcia de performan la problema damelor).21/45

Catalin Stoean

Inteligenta Artificiala

Funcia de performan pentru problema damelorPenalizarea unei dame este proporional cu numrul de dame pe care le atac. Penalizarea unei configuraii este dat de suma penalizrilor pentru fiecare dam. Scopul => de a minimiza numrul total de penalizri!22/45

Catalin Stoean

Inteligenta Artificiala

Componentele unui algoritm evolutivReprezentarea Evaluarea Populaia Selecia prinilor Operatorii variaionaliRecombinarea Mutaia

Iniializarea i terminarea23/45

Catalin Stoean

Inteligenta Artificiala

PopulaiaPopulaia const dintr-o mulime de indivizi care nu sunt neaprat toi diferii ntre ei. Mrimea populaiei reprezint numrul de indivizi pe care i conine populaia. De obicei acest numr este constant! Operatorii de selecie iau n considerare ntreaga populaie de la generaia curent. Populaia este cea care evolueaz de-a lungul generaiilor, nu indivizii n particular.24/45

Catalin Stoean

Inteligenta Artificiala

Componentele unui algoritm evolutivReprezentarea Evaluarea Populaia Selecia prinilor Operatorii variaionaliRecombinarea Mutaia

Iniializarea i terminarea25/45

Catalin Stoean

Inteligenta Artificiala

SeleciaProcesul de selecie apare de dou ori n cursul unei parcurgeri a ciclului ct timp a algoritmului evolutiv prezentat anterior. Selecia pentru reproducere (selecia prinilor), cnd sunt alei prinii generaiei urmtoare Selecia pentru nlocuire (selecia pentru supravieuire), care apare cnd indivizii care vor forma populaia din urmtoarea generaie sunt alei dintre descendenii obinui i indivizii din populaia curent. Modul n care crete calitatea general a soluiilor depinde de ambele tipuri de selecie.26/45

Catalin Stoean

Inteligenta Artificiala

Selecia pentru reproducereSelecia pentru reproducere are rolul de a alege, n funcie de calitatea indivizilor din populaia curent, care sunt cei considerai pentru a se aplica operatori de variaie asupra lor n vederea obinerii de noi soluii candidat. Selecia pentru reproducere este probabilist; indivizii foarte performani au anse bune de a fi selectai pentru reproducere, n timp ce indivizii cu valori mici pentru funcia de performan au anse mici s devin prini. Natura probabilist a seleciei este cea care face cutarea s scape de optimele locale.27/45

Catalin Stoean

Inteligenta Artificiala

Selecia turnirSe selecteaz n mod aleator k indivizi i sunt evaluai. Cel mai bun dintre acetia este selectat ca i printe pentru populaia din generaia urmtoare. Algoritmul de mai jos selecteaz N prini din generaia curent. i=1 Ct timp i < N execut Selecteaz k indivizi n mod aleator din ntreaga populaie Selecteaz-l pe cel mai performant individ s din cei k prini[i] = s i=i+1 Sfrit ct timp28/45

Catalin Stoean

Inteligenta Artificiala

Selecia pentru supravieuireSelecia pentru supravieuire decide care indivizi din populaia curent mpreun cu descendenii obinui sunt oprii pentru a forma populaia generaiei urmtoare. Cum numrul de indivizi din populaie este de obicei constant, selecia pentru supravieuire intervine cu scopul de a pstra aceeai mrime a populaiei. De obicei decizia depinde i n acest caz de performana indivizilor, cei mai buni fiind favorizai.29/45

Catalin Stoean

Inteligenta Artificiala

Componentele unui algoritm evolutivReprezentarea Evaluarea Populaia Selecia prinilor Operatorii variaionaliRecombinarea Mutaia

Iniializarea i terminarea30/45

Catalin Stoean

Inteligenta Artificiala

Operatorii de variaieOperatorul de selecie are rolul de a concentra cutarea pe regiunile cele mai promitoare din spaiul de cutare. Rolul operatorilor de variaie este de a crea noi soluii candidat din cele vechi, de a mri diversitatea populaiei. Operatorii de variaie sunt dependeni de reprezentarea utilizat, astfel c pentru reprezentri diferite trebuie definii operatori specifici. n funcie de aritate, operatorii de variaie sunt mprii n:Aritate = 1 => Mutaie Aritatea > 1 => Recombinare31/45

Catalin Stoean

Inteligenta Artificiala

MutaiaAcioneaz asupra unui individ i produce un altul. Dup ce se aplic asupra unui individ, rezultatul (descendent) conine mici modificri fa de individul iniial. Operatorul face ca toate valorile unei gene s fie disponibile pentru procesul de cutare. Genele ale cror valori sunt considerate pentru a fi schimbate sunt alese printr-o manier probabilist. Un parametru al algoritmului evolutiv este dat de probabilitatea de mutaie.32/45

Catalin Stoean

Inteligenta Artificiala

Cum se aplica mutaiaPresupunem c avem probabilitatea de mutaie pm = 0.3. Notm mrimea populaiei cu N. Pentru i = 1 pn la N executPentru j = 1 pn la numrul de gene ale cromozomului execut

g = numr aleator n intervalul [0, 1]; Dac g < pm atunci

Aplic mutaia pentru gena j a individului i Sfrit dac Sfrit pentru Sfrit pentru33/45

Catalin Stoean

Inteligenta Artificiala

Mutaia pentru problema damelor i pentru comis-voiajorO mic variaie ntr-o permutare:Se aleg dou valori n mod aleator (5 i 7 n imaginea din stnga). Poziiile celor dou valori sunt interschimbate.

1 3 5 2 6 4 7 8

1 3 7 2 6 4 5 8

34/45

Catalin Stoean

Inteligenta Artificiala

Mutaia pentru reprezentarea realn cazul optimizrii unei funcii, de exemplu, avem un individ X = (x1, x2, ..., xp), unde xi [ai, bi]. Se poate obine un individ X = (x1, x2, ..., xp), unde xi este ales n mod aleator n intervalul [ai, bi]. Exemplu:X = (0.4, 0.7, 0.3, 0.9) cu toate genele din [0, 1]. Dac gena a doua sufer mutaie, individul ar putea deveni X = (0.4, 0.1, 0.3, 0.9).

35/45

Catalin Stoean

Inteligenta Artificiala

RecombinareaRecombinarea sau ncruciarea implic doi sau mai muli indivizi (prini) alei cu o anumit probabilitate de ncruciare n scopul de a genera unul, doi sau mai muli indivizi prin combinarea genelor prinilor. Recombinarea reprezint un operator stochastic devreme ce alegeri precum ce pri s fie motenite de la un printe i ce pri de la alt printe sau modul n care prile acestea sunt combinate sunt fcute n mod aleator. Prin mpreunarea a doi indivizi cu caracteristici diferite, este obinut un descendent (sau doi) care combin aceste caracteristici.36/45

Catalin Stoean

Recombinarea pentru problema damelor i pentru comis-voiajorCombinarea a dou permutri n dou noi permutri: Se alege n mod aleator un punct de ncruciare (linia vertical) Se copiaz primele dou pri n cei doi descendeni

Inteligenta Artificiala

A doua parte se completeaz prin inserarea de valori de la cellalt printe:n ordinea n care apar acolo ncepnd cu punctul de dup tietur Srind valorile care se gsesc deja n descendent

1 3 5 2 6 4 7 8 8 7 6 5 4 3 2 1

1 3 5 4 2 8 7 6 8 7 6 2 4 1 3 537/45

Catalin Stoean

Inteligenta Artificiala

Recombinarea pentru reprezentarea realDiscretFiecare gen vine de la unul din prini cu probabilitate egal

IntermediarExploateaz ideea de a crea descendeni ntre prini zi = xi + (1 - ) yi Parametrul poate fiConstant Variabil (s depind de vrsta populaiei) Ales aleator de fiecare dat.38/45

unde : 0 1.

Catalin Stoean

Inteligenta Artificiala

Recombinarea pentru reprezentarea real Prinii: (x1,,xn) i (y1,,yn) Se alege un numr k aleator Descendentul este (x1,, xk-1, yk+ (1 - ) xk, ..., xn) Invers pentru cellalt descendent. La exemplul de mai jos, pentru = 0.5...

39/45

Catalin Stoean

Inteligenta Artificiala

Recombinarea cea mai folosit pentru reprezentarea real Prinii: (x1,,xn) i (y1,,yn) Fiecare gen xk se calculeaz dup formula xk = yk+ (1 - ) xk Invers pentru cellalt descendent. La exemplul de mai jos, pentru = 0.5...

40/45

Catalin Stoean

Inteligenta Artificiala

Componentele unui algoritm evolutivReprezentarea Evaluarea Populaia Selecia prinilor Operatorii variaionaliRecombinarea Mutaia

Iniializarea i terminarea41/45

Catalin Stoean

Inteligenta Artificiala

Iniializarea i condiia de terminareDe obicei iniializarea se face n mod aleator.n populaia iniial se pot include i soluii existente.

Condiia de terminare se verific la fiecare generaieAtingerea unei anumite performane Ajungerea la un anumit numr maxim de generaii Ajungerea la un nivel foarte mic de diversitate n populaie Atingerea unui anumit numr de generaii fr s se mai fi ctigat performan.42/45

Catalin Stoean

Inteligenta Artificiala

Comportamentul tipic al unui algoritm evolutivSituaii n optimizarea unei funcii de o singur variabil Faz de nceput: Distribuia populaiei este qvasialeatoare Faz de mijloc: Populaia aranjat n jurul / pe dealuri Faz de final: Populaia este concentrat pe dealurile nalte43/45

Catalin Stoean

Inteligenta Artificiala

Ct s dureze o rulare?Cel mai performant individ

Progres n a doua jumtate Progres n prima jumtate

Timp (numrul de generaii)

44/45

Catalin Stoean

Inteligenta Artificiala

RecapitulareAlgoritmii evolutivi sunt inspirai din modul n care au evoluat lucrurile n natur. Folosesc mulimi de poteniale soluii pe care le evolueaz de-a lungul mai multor generaii. Operatorul de selecie este cel care face ca performana medie a populaiei s creasc o dat cu trecerea generaiilor. Pentru introducerea de noi soluii sunt folosii operatori de variaie precum mutaia i recombinarea.45/45