S06.genetski Algoritmi.ppt

Veštačka Inteligencija

Genetski algoritmi

Genetski algoritmi Uvod Mehanizam algoritma zasniva se na Darwinovoj teoriji evolucije (1859) i osnovama genetike. Može se primeniti na optimizaciju i pretragu. Charles Darwin (1809-1882) 2

Genetski algoritmi 



Genetski algoritam među elementima u celokupnom prostoru za pretragu radi paralelno sa više potencijalnih kandidata za rešenje. Elementi prostora predstavljaju moguća rešenja problema, i nazivamo ih jedinkama (individual).

3

Genetski algoritmi 



Zbir elemenata predstavlja populaciju (population), koji se smenjuju iz generacije u generaciju (generation) tokom izvršavanja algoritma. Kod genetskih algoritama potencijalna rešenja za dati problem (jedinke) skladištimo u strukturi koja nalikuje hromozomu (string).

4

Genetski algoritmi Kao i kod biološkog nasleđivanja algoritam se služi raznim rekombinacionim (evolucionim) operacijama. Prilikom ovih operacija u populaciji se iz generacije u generaciju imitiranjem biološkog razmnožavanja obezbeđuje širenje jedinki sa najboljim osobinama.

5

Genetski algoritmi Dešava se isto što se desilo i prilikom evolucije. Slabe jedinke odumiru, a najviše šanse za preživljavanje i širenje koje su najsnažnije, najotpornije i koji se najviše mogu prilagoditi okolini. Genetski algoritmi deluju u skladu sa istim ovakvim cikličnim principima.

6

Genetski algoritmi   



Izbor početne populacije. Priprema za generisanje sledeće generacije. Stvaranje novih jedinki uz pomoć operacija za reprodukciju. Određivanje nove generacije, izračunavanje dobrote novih jedinki, izbor iz najboljih jedinki od potomaka i roditelja.

7

Genetski algoritmi

8

Genetski algoritmi Izbor značajnih osobina i kodovanje sa tačke gledišta problema naziva se reprezentacija. Pojedina rešenja u populaciji treba da se skladište u fiksiranoj strukturi podataka. Ova struktura naziva se hromozom (chromosome). Hromozom se sastoji od gena, gde jedan gen sadrži jedan bit ili jedan broj (simbol). Genetski operatori (rekombinacija, mutacija) deluju na hromozomima, to jest na njenim9

Genetski algoritmi Druga osnovna komponenta genetskih algoritama je funkcija dobrote ili fitnes-funkcija. Ona reflektuje dobrotu pojedinih rešenja. Za stvaranje jedne nove generacije algoritam bira roditelje (selekcija), od kojih se primenom genetskih algoritama stvaraju potomci.

10

Genetski algoritmi Osnova za selekciju je fitnes jedinki. Jedinke sa veći fitnesom će sa većom verovatnoćom biti selektovane. Ovako algoritam imitira prirodnu pojavu po kojoj jedinke sa boljim osobinama imaju veću verovatnoću reprodukcije. Sledeći korak je pravljenje nove (sledeće) generacije primenom genetskih operacija rekombinacije i mutacije.

11

Genetski algoritmi Algoritam počinje sa polaznom populacijom (initial population), koji se sastoji od slučajno izabranih hromozoma. Nakon toga sledi vrednovanje kodovanih rešenja, a na osnovu toga se odlučuje kolika je reproduktivna mogućnost jedinki. Hromozomi koji predstavljaju bolja rešenja sa većom verovatnoćom mogu računati na preživljavanje.

12

Sledeći korak je pravljenje nove (sledeće) generacije primenom genetskih operacija rekombinacije i mutacije.

13

Primer: Lisice i zečevi Posmatrajmo primer populacije zečeva: 

Neki zečevi su brži od ostalih, i zato možemo da kažemo da ovi zečevi imaju izrazito visoke i dobre fitnes vrednosti, jer imaju veće šanse da pobegnu od lisica i da se posle razmnožavaju.



Zato će jedinke sa velikim fitnesom da opstanu, a ako oba roditelja imaju visok fitnes, tada će sa velikom verovatnoćom i njihov potomak imati visok fitnes, i imaće veće šanse za preživljavanje. 14

Biološka pozadina Svako živo biće se sastoji od ćelija. Svaka ćelija sadrži iste hromozome. Jedan hromozom može se podeliti na gene, koji pripadaju različitim funkcijama, i tako kodiraju po jednu belančevinu. Svaki gen opisuje jednu karakteristiku (npr. boja očiju). Svaki gen se nalazi na datom položaju (poziciji) u hromozomu (locus). 15

Biološka pozadina Mnoga živa bića sadrže više hromozoma unutar ćelija. Zbir hromozoma naziva se set gena (genome). Genotip (genotype) je konkretan skup gena sa datim varijantama. Ako dve jedinke imaju potpuno identičan set gena, onda imaju isti genotip. Na osnovu genotipa se razvija fenotip (phenotype). 16

Biološka pozadina Organizmi koji imaju duplirane hromozome nazivaju se diploidi, dok se oragnizmi koji imaju jednostruke hromozome nazivaju haploidi. Čovek ima 23 para hromozoma. U genetskim algoritmima rekombinacija se obično dešava između dva roditelja haploida. Mutacija slučajno menja vrednost gena.

17

Prirodna i veštačka genetska terminologija Prirodna

Veštačka

Hromozom (ćelijska materija koja String sadrži nasledne osobine ćelija) Gen (deo hromozoma, nosilac Osobina, karakteristika naslednih osobina, (molekul nukleinske kiseline)) Genotip (skup svih naslednih osobina )

Struktura stringa

Fenotip (skup svih morfoloških i Skup parametara životnih svojstava živog bića. Pojavni oblik uslovljen nasleđivanjem i uticajem sredine).

18

Genetski algoritmi Kod genetskih algoritama hromozom obeležava jedno moguće rešenje za dati problem, i često je kodovan kao string bitova. Datom položaju gena može pripadati 0 ili 1 (binaran slučaj), ili drugi broj ili simbol (nebinaran slučaj).

19

Kanonički genetski algoritmi Pretpostavimo da je dat jedan dobro definisan problem, jedna reprezentacija hromozoma za moguća rešenja i jedna funkcija cilja koja svakom rešenju dodeljuje jednu vrednost dobrote.

20

Kanonički genetski algoritmi

21

Kanonički genetski algoritmi Nakon inicijalizacije sledi jedan ciklus.

U ciklusu se dešava pretraga raznih jedinki. Iteracioni ciklus može se završiti na osnovu izlaznog uslova. 22

Inicijalizacija Populacija je skup hromozoma, to jest jedinki rešenja. Aktuelna populacija menja se iz generacije u generaciju, a u generacijama koje se obnavljaju uvek se rađaju nove populacije. Algoritam početnu populaciju određuje na slučajan način.

23

Inicijalizacija U kanoničkom genetskom algoritmu koristimo bit stringove dužine L po hromozomu. Svaki bit postavljamo na nulu (0) ili jedinicu (1) sa verovatnoćom od 50%. Svaka varijanta hromozoma može se desiti sa verovatnoćom 1/(2L). Veličina populacije je broj jedinki u njoj i najčešće je konstantan (N). 24

Primer za populaciju

25

Selekcija Selekcija bira neke jedinke iz populacije u zavisnosti od njihove fitnes vrednosti. Ova procedura liči na prirodnu selekciju. Sposobnost za reprodukciju zavisi od dobrote rešenja.

26

Selekcija Pre selekcije treba uraditi sledeće:  Izračunavati vrednosti ciljne funkcije (fi) za jedinke iz aktuelne populacije.  Odrediti vrednosti fitnesa skaliranjem. U našem primeru ciljna funkcija je kvadrat binarnog x-a (x=101, ciljna funkcija je 52=25).

27

Selekcija

28

Selekcija Kod kanoničkog algoritma koristimo najjednostavniji način selekcije. To je rulet-selekcija ili fitnes-proporcionalna selekcija (roulete wheel, fitness based). Iz generacije roditelja u jednom trenutku biramo jedan element tako, da verovatnoća selekcije svake jedinke iz populacije bude proporcionalna sa dobrotom. 29

Selekcija

Rulet selekcija (roulette wheel, fitness based) 30

Selekcija Pojedine hromozome možemo birati i više puta, pojedine operacije selekcije su međusobno nezavisne.

31

Selekcija Rulet-selekcija je jednostavna, ali se ponekad drugim načinima selekcije dobijaju bolji rezultati. Na primer:  

Selekcija na bazi redosleda (rank based) Takmičarska selekcija (tournament based)

32

Selekcija Algoritam selekcionu operaciju izvršava onoliki broj puta koliko elemenata ima populacija (N). Izabrane jedinke čine jednu novu, prelaznu populaciju. Ovim načinom izbora možemo obezbediti da se veličina populacije ne menja.

Nakon stvaranja prelazne populacije slede genetske operacije pomoću kojih se stvara populacija sledeće generacije. 33

Skaliranje fi ffi  f

fi

- vrednovanje date jedinke

f

- prosečna vrednost ciljne funkcije u datoj populaciji

ffi

- dobrota jedinke

34

Skaliranje U prethodnoj tabeli

f  25359 Fitnes prve jedinke je 24649/25359=0.972 Vrednost fitnesa određuje reproduktivnu šansu pojedine jedinke. Prilikom selekcije ova vrednost daje putokaz algoritmu od kojih hromozoma da vrši izbor iz populacije. Verovatnoća selekcije jedinki zavisi od njihove fitnes vrednosti. 35

Genetske operacije Izborom parova roditelja iz prelazne populacije stvaraju se potomci jedinki. t + 1/2

t +1’

(prelazno)

(potomci)

Dva najčešće korišćena genetska operatora su rekombinacija i mutacija. 36

Genetske operacije Prvo se vrši rekombinacija koji od jednog para roditelja i njihovim slučajnim kombinovanjem generiše dva nova potomka. Na ovako stvorenim potomcima primenjuje operaciju mutacije koji deluje samo na jednoj jedinki tako što joj slučajno promeni hromozom.

37

Genetske operacije Polazeći od ovako stvorenih jedinki stvara se sledeća generacija. t + 1/2 (prelazno)

rekombinacija

mutacija

t + 1’ (potomci) 38

Rekombinacija (ukrštanje) Operacija rekombinacije (recombination) od dve jedinke roditelja stvara jednog ili dva potomka.

U slučaju pojedinih parova roditelja algoritam će ih rekombinovati sa verovatnoćom pc. Ako ne dođe do rekombinacije, dva potomka će biti nepromenjena verzija roditelja.

39

Rekombinacija (ukrštanje) U slučaju bit-stringova najjednostavnija je rekombinacija u jednoj tački. Ovaj postupak uzima hromozome dva roditelja, oba preseče u slučajno izabranoj tački, i nakon promene ponovo ih slepi. Dve ovako generisane jedinke mogu se smatrati potomcima roditelja.

40

Rekombinacija (ukrštanje)

10000101 00110011

Nakon rekombinacije

10000011 00110101 41

Rekombinacija (ukrštanje)  

Pored rekombinacije sa jednom tačkom, postoje i njene uopštene varijante: Rekombinacija u dve tačke Rekombinacija u N tačaka

42

Uniformna rekombinacija Geni hromozoma potomaka dobijaju se od roditelja sa iste pozicije, obično sa verovatnoćom 0.5-0.5 od jednog, odnosno drugog roditelja.

43

Mutacija Operacija mutacije radi tako što jedan postojeći hromozom promeni u maloj meri. Najčešći način je da slučano izabere jedan od gena, pa njegovu vrednost promeni na neku drugu slučajno određenu vrednost. Najbitnija funkcija mutacije je otkrivanje novih teritorija u prostoru za pretragu.

44

Mutacija Operacija mutira dve prethodno generisana potomka (nezavisno jedno od drugog). Moguće je da se mutacija vrši u slučajno odabranoj poziciji, ili na svakoj poziciji nezavisno.

45

Mutacija Za ceo hromozom, to jest za pojedine bitove verovatnoća mutacije je pm. Nakon operacije algoritam potomke stavlja u novu populaciju. Mutacija dakle slučajno menja nekoliko bitova u hromozomu. 00110110

01110110

primer za mutaciju

Mutacija može da se dogodi na svakoj poziciji stringa sa određenom verovatnoćom. Ta verovatnoća je relativno mala (0.001). 46

Mutacija Mutaciji pripada još jedna specijalna operacija, a to je inverzija. Inverzija slučajno bira deo hromozoma, izvadi ga, pa ga vraća unatraške.

47

Reprodukcija Osnov za novu generaciju daje populacija potomaka. Nova populacija se stvara sa korakom reprodukcije na osnovu novih jedinki i stare generacije. I za ovo postoji više načina. Jednostavna ili generacijska reprodukcija (simple, generational) u potpunosti menja staru populaciju. Svi roditelji će biti izgubljeni, ostaće samo potomci.

48

Reprodukcija Kao dopunu obično koristimo elitizam (elitism): sačuvamo najbolju jedinku iz generacije roditelja, i prenesemo ga u novu generaciju. Pri tome, ili ćemo slučajno izbaciti jednu jedinku, ili ćemo izbaciti onu sa najlošijim fitnesom.

49

Kriterijum za zaustavljanje Završetkom rada algoritma upravlja izlazna funkcija, koja o završetku odlučuje na osnovu različitih kriterijuma: 1.

2.

Izvršavanje algoritma završava se nakon zadatog broja generacija. Zaustavljanje je nezavisno od dobrote aktuelne generacije i konvergencije. Stanje aktuelne generacije. Na primer ako odnos najboljeg fitnesa neke jedinke i prosečnog fitnesa generacije dostigne određenu vrednost, to jest u generaciji se može naći bar jedno jako dobro rešenje. Druga mogućnost za zaustavljanje je ako disperzija jedinki padne ispod neke vrednosti. To znači da je cela populacija u prostoru za pretragu koncentrisana na određenu površinu. 50

Kriterijum za zaustavljanje 3.

Zaustavljanje algoritma može zavisiti i od konvergencije populacije ili konvergencije njenog najboljeg člana. Konvergencija se može definisati na više načina. Jedan gen konvergira ako je unutar populacije vrednost gena ista u 95% slučajeva. Populacija konvergira ako svaki gen konvergira.

51

Napomene Tipičan broj generacija u genetskim algoritmima je između 50 i 500. Jedan kompletan niz generacija naziva se izvršavanjem. Pojedina izvršavanja mogu dati različite rezultate. Prikazani agoritam služi samo kao osnova za algoritme koji se koriste u praksi. Na uspešnost genetskih algoritama utiče veličina populacije (N), verovatnoća rekombinacije i mutacije (pc, pm), i još mnogo faktora. 52

GA – 8 kraljica Stanje 8-kraljica treba da specificira pozicije 8 kraljica, tako da nam je za reprezentaciju potrebno 8xlog28=24 bita. Stanja se mogu predstaviti i sa 8 cifara iz intervala 1-8. Slika (a) prikazuje populaciju koja se sastoji od 4 hromozoma koje od po 8 bita koje predstavljaju položaje kraljica.

53

GA – 8 kraljica

Populaciju sa slike (a) rangiramo na osnovu fitnes funkcije (b). Selektovane jedinke za reprodukciju prikazane su na slici (c). Potomci su prikazani na slici (d), i na njih još deluje i mutacija (e). 54

GA – 8 kraljica Stvaranje sledeće generacije je prikazano na slikama (a)-(e). Na slici (b) svako stanje rangiramo na osnovu evaluacione (fitnes) funkcije. Fitnes funkcija za bolja stanja treba da vrati višu vrednost. Kod 8-kraljica kao fitnes funkciju koristimo broj pari kraljica koa se ne napadaju. U slučaju rešenja ova vrednost je 28. Vrednosti za 4 prikazana stanja su 24, 23, 20 i 11. 55

GA – 8 kraljica Verovatnoća selekcije za reprodukciju je u direktnoj srazmeri sa vrednošću fitnesa. Procentualne vrednosti se mogu videti pored fitnes vrednosti. Na slici (c) slučajno biramo dva para za reprodukciju, u skladu sa verovatnoćama iz (b). Jednu jedinku smo izabrali dva puta, dok drugu nismo birali nijednom. 56

GA – 8 kraljica Kod svakog para za rekombinaciju biramo jednu tačku prekida (crossover point) u hromozomu (kod prvog para posle treće cifre, kod drugog para posle pete cifre). Na slici (d) vidimo generisanje potomaka, rekombinovanjem hromozoma roditelja u tačkama prekida. Prvi potomak prvog para dobija prve tri cifre od prvog roditelja, a ostale cifre od drugog. 57

GA – 8 kraljica

Prilikom rekombinacije zatamnjene kolone će se izgubiti, a nezatamnjene kolone će ostati Ako su stanja dva roditelja veoma različita, rezultat rekombinacije može biti veoma udaljen od oba roditelja. 58

GA – 8 kraljica Puno puta se dešava da je na početku pretrage populacija dosta raznolika, i rekombinacija grabi napred sa velikim koracima, dok kasnije, kad jedinke dosta liče jedna na drugu slede manji koraci. Na kraju na slici (e) svaki element hromozoma sa nekom malom verovatnoćom podvrgavamo mutaciji. 59

GA – 8 kraljica U prvom, trećem i petom potomku mutirali smo jednu cifru. Kod problema 8-kraljica ova operacija odgovara slučajnom izboru jedne kraljice i premeštanje te iste kraljice na drugo (slučajno odabrano) mesto u istoj koloni.

60

Genetski algoritmi Genetski algoritam kombinuje tendenciju penjanja, slučajno otkrivanje i razmenu informacija između paralelnih niti pretrage. Prednost genetskih rekombinacije.

algoritama

potiče

od

61

Teorija šema (schema) Ako prve tri kraljice smestimo na pozicije 2, 4, i 6 (ne napadaju se), napravićemo jedan koristan blok, koji u kombinaciji sa drugim blokovima može da da rešenje. Teorija genetskih algoritama funkcionisanje blokova objašnjava sa pojmom šeme (schema). Šema je deo hromozoma u kojem neke pozicije nisu specificirane. Šema 246***** opisuje sva stanja 8-kraljica gde su prve tri kraljice redom na 2., 4., i 6. poziciji. Hromozomi koji se prilagođavaju šemi (kao na primer 24613578) su primerci šeme. 62

Kraj