calcul evolutiv

download calcul evolutiv

of 45

  • date post

    10-Jul-2015
  • Category

    Documents

  • view

    166
  • download

    0

Embed Size (px)

Transcript of calcul evolutiv

Elemente de calcul 1 evolutivCatalin Stoean catalin.stoean@inf.ucv.ro 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 anteri