Evolucijske Strategije

Monika Čeri Iva Malović

Evolucijske strategije, Projekt, Monika Čeri, Iva Malović

  1. Rad - PDF: Evolucijske strategije [PDF]
  2. Rad - DOC: Evolucijske strategije [DOC]
  3. Programska rješenja - RAR: Evolucijske strategije [RAR]

Problem trgovačkog putnika, Završni rad, Iva Malović

  1. Rad - PDF: TSP [PDF]
  2. Prezentacija - PPTX: TSP [PPTX]
  3. Programsko rješenje - RAR: TSP [RAR]

Evolucijske strategije


1. Uvod

Evolucijske strategije su jedna od tehnika optimizacije iz područja evolucijskih algoritama. Razvoj evolucijskih strategija započeli su Ingo Rechenberg i Hans Peter Schwefel, studenti berlinskog Tehničkog fakulteta 60-ih godina 20. stoljeća. Oni su razvili prve sheme za razvoj optimalnih oblika tijela s minimalnim trenjem u aerodinamici koristeći Darwinovu teoriju evolucije. [2]

Evolucijske strategije su optimizacijske tehnike bazirane na prilagođavanju i evoluciji. Njihova središnja ideja je stvaranje jednog ili λ potomaka operacijom mutacije iz jednog ili μ roditelja. U sljedeću se generaciju prenosi ili μ roditelja i λ potomaka ili samo λ potomaka. Roditelji i potomci predstavljaju potencijalno rješenje optimizacijskog problema.

Potencijalna rješenja prikazuju se pomoću vektora realnih brojeva. Broj na određenom mjestu unutar vektora opisuje neku karakteristiku samog rješenja. Kako bi se došlo do rješenja određenog problema koristi se operator mutacije na samim vektorima, a rjeđe se upotrebljava i operacija rekombinacije. U sljedeću generaciju odlaze samo najbolje jedinke koje se odabiru procesom selekcije.

2. Evolucijske strategije

Pod sljedećim podnaslovima dan je opis selekcije, genetskih operatora koji se koriste u evolucijskim strategijama, klasifikacija evolucijskih strategija, te je detaljno iznesen algoritam i princip rada evolucijskih strategija.

2.1 Selekcija

Pretpostavimo da postoji neka početna populacija jedinki. Uloga selekcije je čuvanje i prenošenje dobrih svojstava jedinki iz trenutne populacije na sljedeću generaciju jedinki. Njom se odabiru one jedinke koje će sudjelovati u reprodukciji u sljedećem koraku i time prenijeti svoj genetski materijal na sljedeću populaciju. Dakle, selekcija čuva dobre, a odbacuje loše jedinke iz populacijskog rješenja. Kako bi se odredilo koje su jedinke kvalitetnije tj. koje će jedinke prijeći u sljedeću populaciju, koristi se funkcija dobrote. [4]

2.1.1 Funkcija dobrote

Funkcija dobrote (fitness) ili funkcija ocjene kvalitete jedinke ekvivalent je funkciji f koju treba optimizirati:

dobrota(v) = f(x)

gdje binarni vektor v predstavlja neki realan broj x. [6]

Što je dobrota jedinke veća, jedinka ima veću vjerojatnost preživljavanja, a time i veću mogućnost prijenosa svojih gena na sljedeću populaciju.

Zbog toga je upravo funkcija dobrote ključ za proces selekcije. Tijekom procesa evolucije ukupna dobrota bi trebala biti sve bolja i bolja ukoliko je zadani evolucijski algoritam dobar. Time bi se na samom kraju, prilikom odabira jedinki s najboljim vrijednostima funkcije dobrote, dobilo optimalno rješenje za neki problem.

2.2 Genetski operatori

Druga važna karakteristika evolucijskih strategija je reprodukcija. Općenito, reprodukcija je proces razmnožavanja u kojem sudjeluju jedinke koje su preživjele proces selekcije u prethodnoj populaciji. Razmnožavanje se obavlja pomoću genetskih operatora koji djeluju na same jedinke. Kod evolucijskih strategija najviše se primjenjuje operator mutacije, a nešto manje operator rekombinacije.

2.2.1 Mutacija

Mutacija je operator karakterističan za proces rekombinacije kod evolucijskih strategija. Ovaj operator je unarni operator jer djeluje samo nad jednom jedinkom. Mutacija je slučajna promjena jednog ili više gena kako bi se dobila genetska raznolikost sljedeće generacije rješenja. Najjednostavniji primjer mutacije je vjerojatnost da se neki bit u genetskom kodu promijeni iz svog originalnog stanja u neko novo stanje.

Mutacija sprječava da neka rješenja unutar populacije postanu slična drugima i na taj način uspore ili potpuno zaustave proces evolucije. Mutacija kod evolucijskih strategija najčešće mijenja element xi vektora x u broj izabran iz normalne razdiobe N(xi, σi^2). [4]

Kod evolucijskih strategija postoji važno pravilo koje je definirao Rechenberg prilikom svojih istraživanja. Pravilo se naziva pravilo 1/5 uspjeha. Samo pravilo predviđa optimalne performanse za vrijeme trajanja mutacija i to kada od svih mutacija koje se provedu 20% njih daje uspješne potomke. To znači da kvocijent broja uspješnih mutacija i ukupnog broja mutacija unutar neke populacije mora biti približno 1/5. Ukoliko je taj kvocijent manji od 1/5, vrijednost parametra σ u normalnoj razdiobi se mora smanjiti. Nasuprot tome, ukoliko je kvocijent veći od 1/5, vrijednost parametra σ se mora povećati. [3]

Mutacijom se pretražuje prostor rješenja što daje mutaciji jednu od najvažnijih osobina. Naime, ovim postupkom se omogućava izbjegavanje lokalnih minimuma. Ako cijela populacija završi u nekom lokalnom minimumu, mutacija će slučajnim pretraživanjem prostora (izborom elementa pomoću normalne razdiobe) pronaći bolje rješenje.

2.2.2 Rekombinacija

Rekombinacija ili križanje je operator koji se rjeđe upotrebljava od operatora mutacije. U samom procesu rekombinacije stvaraju se nove jedinke koje sadrže kombinirane informacije sadržane u dva roditelja. Dakle, križanje je binarni operator jer djeluje na dvije jedinke u populaciji istovremeno. To se postiže kombinacijom varijabli koje sadržavaju roditelji. Zbog toga je najvažnija karakteristika križanja da potomci nasljeđuju svojstva svojih roditelja. Ako su roditelji dobri, tada će najvjerojatnije i potomak koji nastaje njihovim križanjem biti dobar, ako ne i bolji od svojih roditelja.

Križanje se definira proizvoljnim brojem prekidnih točaka. Ovisno o izboru tih točaka postoji nekoliko vrsta križanja:

  • križanje u jednoj točki (one-point crossover)
  • križanje u dvije točke (two-point crossover)
  • križanje rezanjem i spajanjem (cut and splice crossover)
  • uniformno križanje (uniform crossover)
  • polu-uniformno križanje (half-uniform crossover)
2.3 Klasifikacija evolucijskih strategija

Evolucijske strategije dijele se s obzirom na različite tipove evolucijskih procesa koje oni koriste. Razlika je u samom izboru roditelja i upotrebi rekombinacije.

Pretpostavimo da je broj roditelja u nekoj generaciji γ označen sa μ, a broj potomaka u generaciji γ označen sa λ. Postoji sedam različitih tipova evolucijskih procesa koje koriste evolucijske strategije.[1]


  1. (1+1)-ES

    U populaciji postoje samo dvije jedinke. Jedna jedinka je roditelj iz kojeg nakon reprodukcije procesom mutacije nastaje potomak. Proces selekcije se obavlja između te dvije jedinke, a u sljedeću generaciju ide ona jedinka koja je bolja, tj. koja ima bolji faktor dobrote.

  2. (μ +1)-ES

    Populacija se sastoji od μ jedinki roditelja. Mutacijom jedne jedinke nastaje jedan potomak koji se konstantno reproducira. Iz spojenog seta potomaka izabrane jedinke i trenutne populacije odbacuje se jedinka koja ima najmanji faktor dobrote.

  3. (μ + λ)-ES

    U ovom slučaju iz μ jedinki roditelja nastaje λ potomaka procesom mutacije. Uvjet za ovaj proces je da je nastalo više djece nego što je roditelja, dakle λ>μ. Svaki od λ potomaka ima svoj faktor dobrote, kao što imaju i svi roditelji. Najboljih μ jedinki iz skupa roditelja i potomaka zajedno prelazi u sljedeću generaciju.

  4. (μ , λ)-ES

    Populacija se sastoji od μ jedinki roditelja, koji procesom mutacije daju λ potomaka, s time da vrijedi λ>μ. Svaki od λ potomaka ima svoj faktor dobrote. Za razliku od prethodnog slučaja, ovdje se za prijelaz u novu generaciju promatraju samo potomci, dakle roditelji ne ulaze u izbor. Iz λ potomaka izabire se μ najboljih jedinki koje prelaze u sljedeću generaciju.

  5. (μ/ρ , λ)-ES

    Ova strategija je (μ, λ) strategija uz dodatak parametra ρ. Ovaj parametar označava broj jedinki roditelja koji se upotrebljava u procesu reprodukcije. Ukoliko je ρ=1, ova strategija je analogna strategiji (μ, λ)-ES, tj. prilikom reprodukcije koristi se samo jedna jedinka iz populacije roditelja, što znači da se upotrebljava operator mutacije. Ukoliko je ρ=2, prilikom reprodukcije se koriste dvije jedinke iz populacije roditelja, što znači da se upotrebljava operator rekombinacije. Selekcija je analogna selekciji kod (μ , λ)-ES.

  6. (μ/ρ + λ)-ES

    Ova strategija je (μ + λ) strategija uz ponovni dodatak parametra ρ. Za reprodukciju vrijede ista pravila kao i kod (μ/ρ , λ) strategije, a selekcija je analogna selekciji kod
    (μ + λ)-ES.

  7. (μ' , λ'(μ , λ)γ)-ES

    Kod ove strategije se iz populacije roditelja veličine μ' kreira λ' potomaka i izolira na γ generacija. U svakoj od γ generacija stvara se λ potomaka od kojih samo μ najboljih prelazi u sljedeću generaciju. Nakon γ generacija izabiru se najbolje jedinke od γ izoliranih populacija i krug kreće ponovno sa λ' novih jedinki potomaka.

2.4 Algoritam evolucijskih strategija

Kao što je ranije navedeno, evolucijska strategija ima kao svoj cilj stvoriti populaciju potomaka pomoću procesa rekombinacije ili mutacije iz početne populacije roditelja. Postupak mutacije i rekombinacije se ponavlja i nastaju nove generacije potomaka, sve dok se ne dođe do optimuma nekog zadanog problema. Ovaj proces prikazan je pseudokodom na Slici 2.1. [5]

Proces stvaranja nove generacije može se opisati kroz sljedeće korake:

  1. stvori λ novih jedinki:
    1. odaberi slučajnih ρ≤μ roditelja
    2. križaj ρ roditelja kako bi dobio potomka
    3. odredi novu vrijednost parametra p prema normalnoj razdiobi
    4. mutiraj dijete pomoću nove vrijednosti parametra p
  2. odaberi novu populaciju na temelju funkcije dobrote:
    1. iz populacije djece ukoliko se radi o (λ , μ)-ES
    2. iz populacije djece i roditelja ukoliko se radi o (λ + μ)-ES.

Dijagram tijeka evolucijske strategije prikazan je na Slici 2.2. [7]



3. Primjena evolucijskih strategija

Evolucijske strategije imaju vrlo široku primjenu u poljima optimizacije, uključujući optimizacijske probleme u kontinuiranom i diskretnom vremenu, vektorsku optimizaciju i kombinatorne probleme sa i bez ograničenja. [2]Koriste se u data miningu, u izradi kompliciranih vremenskih rasporeda, u kemiji, za nalaženje izvora emisije iz atmosferskih promatranja, za geometriju (npr. kod izrade mostova), rekonstrukciju površina, za rješavanje raznih verzija problema trgovačkog putnika, u optici i obradi slike, u aproksimaciji polinomnih funkcija, itd... [1, 8]

4. Problem trgovačkog putnika

4.1 Opis problema i aplikacija

Problem trgovačkog putnika očituje se u potrazi za najkraćim putem koji putnik mora prijeći tako da, krenuvši od početnog grada N1, obiđe sve zadane gradove točno jednom i ponovno se vrati u grad N1. Matematička definicija bi bila:

Neka je zadan cijeli broj n≥3 i n x n matrica C = (Cij), gdje je Cij poprima nenegativne cjelobrojne vrijednosti. Traži se permutacija π cijelih brojeva od 1 do n koja minimizira sumu. [9]

Kroz godine ovaj problem je okupirao umove mnogih istražitelja zbog mnogih razloga. Prvo, problem trgovačkog putnika je vrlo lako za opisati, ali predstavlja veliki problem prilikom rješavanja. Nije poznat niti jedan vremenski polinomni algoritam kojim se on može riješiti. Nedostatak tih polinomnih algoritama je karakteristika klase NP – teških algoritama.

Drugo, problem je široko primjenjiv na različite probleme usmjeravanja i raspoređivanja. Na kraju, kako je poznato mnogo informacija o ovom problemu, postao je neka vrsta testnog problema za sve nove kombinatoričke metode optimizacije.

4.2 Programsko rješenje

Aplikacija prikazuje problem riješen pomoću evolucijskih strategija. [10] Traži se optimalna ruta između deset unaprijed zadanih gradova. Korisnik može sam izabrati jednu od četiri vrste ES. U ovom slučaju se umjesto oznaka μ i λ koriste p i c. Tako je moguće pokrenuti aplikaciju korištenjem (p, c) – ES, (p+c) – ES, (p/r+c) – ES, te (p/r, c) – ES.

Nadalje, korisnik može izabrati broj roditelja i djece, a ako koristi jednu od zadnje dvije spomenute strategije, u kojima se koristi i rekombinacija, onda može izabrati vrstu rekombinacije i broj rekombinata. Na samom kraju bira broj generacija. Na lijevoj strani može se vidjeti izabrana ruta u određenom koraku, a ispod slike se ispisuje vrijednost funkcije dobrote.

5. Zaključak

U radu su prezentirane evolucijske strategije kao jedna od tehnika optimiranja. Korištenje osnovnih operatora, selekcije i mutacije, omogućava uspješno rješavanje nekog složenog optimizacijskog problema. Evolucijske strategije mogu se upotrebljavati za rješavanje raznovrsnih problema. Tako je pokazana njihova uspješna upotreba pri rješavanju NP – teškog problema trgovačkog putnika koristeći dvije strategije: (µ+λ) – ES i (µ, λ) – ES. Uz pomoć računala problem trgovačkog putnika sa 50 gradova može se riješiti za samo nekoliko sekundi.

6. Literatura
  1. Weise Thomas: Global Optimization Algorithms,
    http://www.it-weise.de/projects/book.pdf, 24.10.2007.
  2. http://en.wikipedia.org/wiki/Evolution_strategy, 24.10.2007.
  3. http://www.techfak.uni-bielefeld.de/bcd/Curric/ProtEn/112.html, 24.10.2007.
  4. http://ls11-www.cs.uni-dortmund.de/people/kursawe/Demos/EvoNet/EStheory.html, 24.10.2007.
  5. Pielić Marko: Pregled evolucijskih algoritama
    http://www.zemris.fer.hr/~golub/ga/studenti/seminari/2007_pielic/Pregled%20evolucijskih%
    20algoritama%5B2007%5DPielic_Marko.htm
    , 24.10.2007.
  6. Golub, Marin: Genetski algoritam
    http://www.zemris.fer.hr/~golub/ga/ga_skripta1.pdf 24.10.2007.
  7. Petrović, Juraj: Evolucijski algoritmi http://www.zemris.fer.hr/~yeti/studenti/radovi/Petrovic_Juraj_Seminar.pdf, 24.10.2007.
  8. Evolution Strategy in Action, 10 ES-Demonstrations
    http://www.bionik.tu-berlin.de/user/giani/esdemos/evo.html, 27.10.2007.
  9. Larranaga P., Tackling the Travelling Salesman problem with Evolutionary Algorithms: Representations and Operators:
    http://citeseer.ist.psu.edu/cache/papers/cs/9133/http:zSzzSzwww.sc.ehu.eszSzcc
    wbayeszSzpostscriptzSzehu-kzaa-ik-2-94.pdf/tackling-the-travelling-salesman.pdf
    , 7.11.2007.
  10. Craenen B., Travelling Salesman – Solving TSP using Evolution Strategies
    http://evonet.lri.fr/CIRCUS2/node.php?node=81, 29.10.2007.