Википедија

Genetski algoritam

(преусмерено са Генетички алгоритам)

U oblasti veštačke inteligencije genetski algoritam (GA) je pretraživačka heuristika koja oponaša proces prirodne selekcije. Ova heuristika (takođe ponekad nazivana metaheuristika) se rutinski koristi da generiše korisna rešenja za optimizaciju i probleme pretrage.[1] Genetski algoritmi pripadaju većoj klasi evolucionih algoritama (EA) koji generišu rešenja za optimizaciju problema korišćenjem tehnika insprisanih prirodnom evolucijom, kao što su nasleđivanje, mutacija, selekcija i krosing-over.

Princip rada

уреди

Rad GA se može opisati u osam odnosno sedam koraka[2]:

  1. Definisanje svih potrebnih parametara problema i GA
  2. Formiranje početne populacije
  3. Dekodiranje hromozoma — ovaj korak se javlja samo kod binarnih GA
  4. Određivanje cena hromozomima (fitnes funkcijom)
  5. Odabir selekcije hromozoma koji će opstati za parenje
  6. Parenje — obično se iz boljeg dela populacije odabiru roditelji koji će na neki način ukrstiti svoj genetski materijal i dati jednog ili više potomaka koji obično zamene nekog od lošijih hromozoma
  7. Mutacije, pri kojima se menja genetski sadržaj hromozoma
  8. Ispitivanje konvergencije, da bi se utvrdilo da li ima osnova da se tok algoritma prekine. Ukoliko nije ispunjen uslov konvergencije, vratiti se na korak 3 odnosno 4.

Metodologija

уреди

Problemi optimizacije

уреди

U genetskom algoritmu, populacija rešenja kandidati (tzv. pojedinaca, bića ili fenotipa) problema optimizacije evoluira ka boljim rešenjima. Svako rešenje kandidat ima skup osobina (svojih hromozoma ili genotipa) koji može da bude mutiran ili izmenjen; tradicionalno rešenja su predstavljena binarno, kao nizovi nula i jedinica, ali i druga kodiranja su takođe moguća.

Evolucija obično počinje od populacije nasumično generisanih pojedinaca, i to je proces koji se ponavlja, sa populacijom koja se u svakoj iteraciji zove generacija. U svakoj generaciji fitnes svakog pojedinca u populaciji se ocenjuje; fitnes je obično vrednost objektne funkcije u problemu optimizacije koji se rešava. Što više fit (zdravi) pojedinci su stohastički selektovani iz trenutne populacije, i genom svake idividue se menja (kombinovan i eventualno slučajno mutiran) kako bi se formirala nova generacija. Nova generacija dobijenih rešenja kandidata se zatim koristi u sledećoj iteraciji algoritma. Uglavnom, algoritam se završava ili kada je proizveden maksimalni broj generacija ili je dostignut zadovoljavajući nivo fitnesa za populaciju.

Tipičan genetski algoritam zahteva:

  1. Genetski prikaz domena rešenja
  2. Funkciju fitnes za procenu domena rešenja

Standardna reprezentacija svakog rešenja kandidata je niz bitova.[3]Nizovi drugih tipova i struktura se u suštini mogu koristiti na isti nači. Glavna osobina koji čini ove genetske reprezentacije pogodne je da su njihovi delovi jako usklađeni zbog fiksne veličine što olakšava jednostavne operecije krosing-overa. Promenljiva dužina reprezentacije se takođe može koristiti, ali je implementacija krosing-overa u ovom slučaju složenija. Reprezentacije poput stabla su istražene u genetskom programiranju i reprezentacije forme grafa su istražene u evolucionom programiranju; mešavina oba, linearnih hromozoma i stabala je istražena u programiranju zasnovanom na prikazu gena.

Kada su genetska reprezentacija i fitnes funkcija definisani, GA nastavlja da pokreće populaciju rešenja i poboljšava je periodično primenom mutacija, krosing-overa, inverzija i selekcije.

Inicijalizacija

уреди

Veličina populacije zavisi od prirode problema, ali obično sadrži nekoliko stotina ili hiljada mogućih rešenja. Često se početna populacija generiše nasumično, čime se omogućava čitav niz mogućih rešenja (prostor pretrage). Povremeno, rešenja mogu biti „posejana“ u oblastima gde je moguće naći optimalna rešenja.

Selekcija

уреди

Tokom svake sledeće generacije deo postojeće populacije je izabran da odgoji novu generaciju. Individualna rešenja su izabrana pomoču procesa baziranog na fitnesu(zdravlju), gde više fit(zdravija, sa boljom kondicijom) rešenja(merena fitnes funkcijom) imaju veće šanse da budu izabrana. Određene metode selekcije ocenjuju kondiciju svakog rešenja i prvenstveno će izabrati najbolja rešenja.

Funkcija fitnes je definisana u genetskoj reprezentaciji i meri kvalitet prdstavljenog rešenja. Funkcija fitnes uvek zavisi od problema. Na primer u problemu ranca, neko želi najveću ukupnu vrednost predmeta koja se može staviti u ranac fiksnog kapaciteta. Reprezentacija rešenja može biti niz bitova, gde će svaki bit predstavljati drugi predmet, i vrednost bita (0 ili 1) da li je ili ne predmet u rancu. Nije svaka ovakva reprezentacija dobra, jer veličina predmeta može biti veća od kapaciteta ranca. Fitnes rešenje je zbir vrednosti svih objekata u rancu ukoliko je reprezentacija validna, ili 0 u suprotnom.

U nekim slučajevima, teško je ili nemoguće odredititi fitnes. Ako je tako, može se iskoristiti simulacija da odredi vrednost fitnes funkcije za fenotip (npr. Računarska dinamika fluida se koristi da se utvrdi otpor vazduha automobila čiji je oblik kodiran kao fenotip) ili se čak koristi interaktivni genetički algoritam.

Genetski operatori

уреди

Sledeći korak je generisati drugu generaciju populacije rešenja od onih izabranih kroz kombinaciju genetskih operatora: krosing-overa(naziva se i rekombinacija) i mutacije.

Za svako novo rešenje koje će se proizvesti, bira se par „roditeljskih“ rešenja za razmnožavanje iz bazena prethodno izabranih.

Stvaranjem rešenja „deteta“ korišćenjem gore navedenih metoda krosing-overa i mutacije kreirano je novo rešenje koje obično ima mnoge karatkeristike svojih „roditelja“. Za svako novo dete se biraju novi roditelji i proces se nastavlja sve dok nova populacija rešenja ne dostigne odgovarajuću veličinu. Iako su metodi reprodukcije koji se zasnivaju na korišćenju dva roditelja „biološki podstaknuti“ neka istraživanja[4][5] sugerišu da se korišćenjem više od dva „roditelja“ generiše kvalitetnije hromozome.

Ovi procesi na kraju doode do sledeće generacije populacije hromozoma koja se razlikuje od početne generacije. Generalno, prosečna kondicija će porasti ovim procesima za populaciju, jer su izabrani samo najbolji organizmi iz prve generacije za razmnožavanje, zajedno sa malim procentom manje podobnih rešenja. Ova manje fit rešenja garantuju genetsku raznolikost unutar genetskog bazena roditelja i stoga garantuju genetsku raznolikost narednih generacija dece.

Mišljenje je podeljeno oko važnosti krosing-overa naspram mutacija. Postoje mnoge reference u Fogelovom radu (2006) koje podržavaju značaj pretraga baziranih na mutacijama.

Iako su krosing-overi i mutacije poznati kao glavni genetski operatori, moguće je koristiti i druge operatore kao što su pregrupisanje, kolonizacije-istrebljenja ili migracije u genetskim algoritmima.[6]

Vredi podesiti parametre kao što su verovatnoća mutacije, verovatnoća krosing-overa i veličina populacija da bi se pronašla razumna podešavanja za klasu problema na kojoj se radi. Veoma mala stopa mutacija vodi do genetičkog drifta (koji nije ravnomerno raspoređen u prirodi). Stopa rekombinacije koja je previsoka može dovesti do prerane konvergencije genetskog algoritma. Stopa mutacija koja je previsoka može dovesti do gubitka dobrih rešenja, osim ako je iskorišćen elitistički izbor.

Završetak

уреди

Ovaj generacijski proces se ponavlja sve dok se ne postigne uslov prekida. Opšti uslovi završetka su:

  • Rešenje koje je pronađeno zadovoljava minimalne kriterijume
  • Dostignut je fiksiran broj generacija
  • Dodeljen budžet (izrčunava se vreme / novac) je potrošen
  • Fitnes rešenja koje je najviše rankirano dostiže ili je dostigao plato takav da uzastopne iteracije ne daju bolje rezultate
  • Ručno proveravanje
  • Kombinacija navedenih uslova

Hipoteza gradivnog bloka

уреди

Genetički algoritmi su jednostavni za implementaciju ali njihovo ponašanje je teško razumeti. Tačnije, teško je razumeti zašto ovi algoritmi često uspevaju da generišu rešenja visokog fitnesa kada se primene na određen problem. Hipoteza gradivnog bloka (eng: building block hypothesis, BBH) se sastoji od:

  1. Opis heuristike koja obavlja adaptaciju tako što identifikuje i kombinuje gradivne blokove, npr. shema niskog reda sa fitnesom iznad proseka.
  2. Hipoteza kojom genetički algoritam vrši implicitnu adaptaciju i efikasno implementira ovu heuristiku.

Goldberg opisuje heuristiku na sledeći način:

„Kratke sheme niskog reda i sa visokim fitnesom se uzorkuju (uzimaju uzorci), kobinuju i ponovo uzorkuju kako bi napravili stringove potencijalno većeg fitnesa. Radeći sa ovim shemama (tj. gradivnim blokovima), smanjili smo složenost našeg problema; umesto da pravimo vrlo efikasne stringove pokašavajući sa svakom mogućom kombinacijom, mi pravimo sve bolje i bolje stringove koristeći najbolja parcijalna rešenja prethodnog uzorkovanja.“
"Kako kratke sheme niskog reda sa visokog fitnesa igraju veoma bitnu ulogu u genetskim algoritmima, dali smo im specijalno ime: gradivni blokovi. Baš kao što dete pravi veličanstvene tvrđave slažući jednostavne blokove drveta, tako i genetski algoritam postiže skoro optimalne performanse slažući krate sheme niskog reda i visokih performansi, tj. gradivne blokove."[7]

Ograničenja

уреди

Postoje ograničenja upotrebe genetskog algoritma u odnosu na alternativne algoritme za optimizaciju:

  • Ponovljena procena fitnes funkcije za složene probleme je zaštitnički i ograničavajući segment veštačkih evolucionih algoritama. Pronalaženje optimalnog rešenja za složene visoko-dimenzione, multimodalne probleme često zahteva veoma skupe procene fitnes funkcija. U realnom svetu problemni kao što su strukturni problemi optimizacije evaluacija jedne funkcije može da zahteva od nekoliko sati do nekoliko dana potpune simulacije. Tipični metodi optimizacije ne mogu da se bave takvim vrstama problema. U ovom slučaju može biti neophodno da se odreknu tačne procene i koriste približnu fitnes koja je računski efikasna. Očigledano je da spoj pribižnih modela može biti jedan od najperspektivnijih pristupa da se ubedljivo koriste GA za rešavanje kompleksnih problema iz realnog života.
  • Genetski algoritmi ne rade dobro srazmerno složenosti. To jest, kada je broj elemenata koji su izloženi mutaciji veliki često postoji eksponencijalni porast u veličini prostora za pretragu. Zbog toga je izuzetno teško koristiti tehniku na problemima kao što su projektovanje motora, kuće ili aviona. Kako bi takvi problemi bili povodljivi evolucionoj potrazi oni moraju biti razbijeni na što jednostavnije moguće reprezentacije. Stoga obično vidimo evolucione algoritme za kodiranje dizajna za lopatice ventiatora umesto motora, modelovanje oblika umesto detaljnih planova konstrukcije, krila aviona umesto dizajna čitavih aviona. Drugi problem kompleksnosti je kako zaštititi delove koji su evoluirali da predstavljaju dobra rešenja od daljih destruktivnih mutacija, naročito kada njihova procena fitnesa zahteva da se kombinuje sa drugim delovima.
  • „Bolje“ rešenje je samo u poređenju sa drugim rešenjima. Kao rezultat, kriterijum zaustavljanja nije jasan u svakom problemu,
  • U mnogim problemima, GA-mi imaju tendenciju da se prilagode prema lokalnim optimumima ili čak proizvoljnim tačkama, pre nego globalnim optimumima problema. Ovo znači da ono ne „zna kako“ da žrtvuje kratkoročnu kondiciju da stekne dugoročnu kondiciju. Verovatnoća da se to dešava zavisi od oblika fitnes pejzaža: određeni problemi mofu da obezbede lak uspon ka globalnom optimumu, drugi mogu olakšati funkciji da pronađe lokalne optimume. Ovaj problem se može ublažiti korišćenjem druge fitnes funkcije, povećanjem stope mutacija ili pomoću tehnika selekcije koje održavaju raznolikost populacije rešenja[8], iako „Nema besplatnog ručka“ teorema[9] dokazuje da ne postoji opšte rešenje ovog problema. Uobičajena tehnika za održavanje raznolikosti je da nametne „kaznu“ gde bilo koja grupa pojedinaca sa dovoljno sličnosti dobiju kaznu, što će smanjiti zastubljenost te grupe u narednim generacijama, omogućavajući drugim (manje sličnim) pojedincima da opstanu u populaciji. Ovaj trik, međutim, možda neće biti efikasan, u zavisnosti od predela problema. Još jedna moguća tehnika bi bila da se jednostavno zamene delovi populacije sa slučajno generisanim pojedincima, kada je većina populacije previše slična jedna drugima. Raznolikost je važna u genetskim algoritmima (i genetskom programiranju) jer prelazak preko homogene populacije ne daje nova rešenja. U evolucionim strategijama i evolucionom programiranju, raznolikost nije od suštinskog značaja zbog većeg oslanjanja na mutacije.
  • Rad na dinamičkom setu podataka je težak, kako genomi počnu da konvergiraju rano prema rešenjima koja možda više neče važiti za kasnije podatke. Nekoliko metoda je predloženo da se popravi ovo povečanjem genetske raznolikosti nekako i sprečavanjem rane konvergencije, bilo povećanjem verovatnoće mutacije kada je rešenje kvalitet kapi (nazivano započeta hipermutacija), ili povremeno uvođenjem poptuno novih, slučajno generisanih elemeanta u genomu (nazivaju se i slučajni imigranti). Evolucione strategije i evoluciono programiranje mogu se implementirati sa takozvanom „zarez strategijom“ u kojoj roditelji nisu održavani i novi roditelji se biraju samo od potomstva. Ovo može biti efikasnije na dinamičkim problemima.
  • Genetski algoritmi ne mogu efikasno rešiti probleme u kojima je jedina mera za fitnes tačno/netačno (kao problemi odluke), kako ne postoji način da se koncentrišu na rešenja (nema brda da se popne). U ovim slučajevima, slučajna pretraga može naći rešenje brzo kao i genetski algoritam. Međutim, ako situacija dozvoljava uspeh/neuspeh suđenje da se ponovi, davajuću (eventualno) različiti rezultat, onda odnos uspeha neuspeha pruža određenu meru fitnesa.
  • Za specifične probleme optimizacije i instance problema, drugi algoritmi optimizacije mogu biti efikasniji od genetskih algoritama u pogledu brzine konvergencije. Alternativni i komplementarni algoritmi uključuju evolucione strategije, evoluciono programiranje, Gausovu adaptaciju, pretraživanje usponom i inteligenciju jata (npr. optimizacija kolonije mrava, optimizacija čestica roja) metodi bazirani na celobrojnom linearnom programiranju. Pogodnost genetskih algoritama zavisi od količine znanja o problemu; dobro poznati problemi često imaju bolje, specijalizovanije pristupe.

Varijante

уреди

Reprezentacija hromozoma

уреди

Najjednostavniji algoritam predstavlja svaki hromozom kao niz bitova. Numerički parametri se uglavnom mogu predstaviti celim brojevima (eng. integer), ali je moguće korisiti i reprezentaciju u pokretnom zarezu. Reprezentacija u pokretnom zarezu je prirodna za evolucione strategije i evoluciono programiranje. Pojam genetskih algoritama realnih vrednosti je bio predložen, ali je to pogrešan naziv, jer ne prezentuje teoriju gradivnog bloka koju je predložio John Henry Holland 1970ih. Ova teorija ima podršku, zasnovanu na teoretskim i eksperimentalnim rezultatima. Osnovni algoritam izvršava prelazak (crossover) i mutaciju na nivou bitova. Druge varijante tretiraju hromozome kao listu brojeva koji su pokazivači na povezane liste, asocijativne nizove, objekte ili bilo koje druge zamislive strukture podataka. Krosing-over i mutacija se izvršavaja tako da poštuju granice tipa elementa. Za većinu tipova podataka se mogu konstruisati operatori za varijacije. Različiti tipovi podataka kojima se predstavljaju hromozomi rade bolje ili lošije za različite domene problema.

Kada se korsite reprezentacije u vidu nizova bitova, često se primenjuje Grejev kod. Na ovaj način, male promene u broju mogu biti prouzrokovane mutacijama i prelascima. Ovako se sprečava prevremena konvergencija ka takozvanim Hamingovim zidovima (eng. Hamming walls), gde se vrlo mnogo simultanih mutacija (ili prelazaka) mora desiti da bi se hromozom promenio na bolje.

Drugi pristupi uključuju korišćenje nizova realnih brojeva umesto nizova bitova za reprezentaciju hromozoma. Rezultati teorije shema predlažu da što je manji alfabet, bolje su performanse, ali je na početku istraživačima bilo vrlo neobično da su dobijali dobre rezultate korsteći ovakav prikaz hromozoma. Ovo je objašnjeno skupom realnih vrednosti u konačnoj populaciji hromozoma koji formira virtuelni alfabet (kada su selekcija i kombinacija dominantne) sa manjom kardinalnosti od one očekivane od reprezentacije u pokretnom zarezu.[10][11]

Proširenje pristupačnog domena problema Genetskog Algoritma se može postići kroz kompleksno kodiranje skupa rešenja nadovezivanjem nekoliko tipova heterogeno kodiranih gena u jedan hromozom.[12] Ovaj pristup dozvoljava rešavanje problema optimizacije koji zahtevaju veoma različite definicije domena za parametre problema.

Elitizam

уреди

Praktična varijanta procesa konstruisanja nove populacije je dozvoliti da se najbolji organizam (tj. organizmi) trenutne generacije prenese u sledeću, nepromenjen. Ova strategija je poznata kao elitistička selekcija i osigruava da se kvalitet rešenja dobijenog genetskim algoritmom neće smanjivati iz generacije u generaciju.[13]

Paralelna implementacija

уреди

Paralelne implementacije genetskih algoritama dolaze u dve vrste. „Krupnozrnasti“ (eng. coarse-grained) paralelni genetski algoritmi pretpostavljaju da postoji populacija na svakom čvoru i migracija pojedinaca između čvorova. „Sitnozrnasti“ (eng. fine-grained) paralelni genetski algoritmi pretpostavljaju da postoji pojedinac na svakom čvoru koji interaguje sa susednim pojedincima radi selekcije i reprodukcije. Druge varijante, kao na primer genetski algoritmi za online probleme optimizacije, uvode zavisnost od vremena ili „buku“ u fitnes funkciji.

Prilagodljivi Genetski Algoritmi

уреди

Genetski algoritmi sa prilagodljivim parametrima (prilagodljivi genetski algoritmi, PGA-mi) su još jedna važna i obećavajuća varijanta genetskih algoritama. Verovatnoća prelaska i mutacije značajno utiču na preciznost rešenja i brzinu konvergencije koju algoritmi mogu da postignu. Umesto da koriste fiksne vrednosti za ove verovatnoće, PGA-mi koriste informacije o populaciji u svakoj generaciji i prilagodljivo podešavaju verovatnoće prelaska i mutacije kako bi zadržali raznolikost populacije ali i održali kapacitet konvergencije. U PGA-mima[14] podeševanja verovatnoća zavise od vrednosti fitnesa rešenja. U PGA-mima zasnovanim na grupisanju (eng. clustering-based adaptive genetic algorithm),[15] kroz korišćenje analize grupisanja radi procene stanja optimizacije populacije, podešavanja verovatnoća prelaska i mutacije zavise od ovih stanja optimizacije. Kombinovanje genetskog algoritma sa drugim metodama optimizacije može biti vrlo efikasno. Genetski algoritam je vrlo dobar za pronalaženje dobrih globalnih rešenja, ali isto tako vrlo neefikasan u pronalaženju poslednjih nekoliko mutacija radi pronalaženja apsolutnog optimuma. Druge tehnike (kao na primer pretraživanje usponom (eng. hill climbing)) su vrlo dobre u pronalaženju apsolutnog optimuma u ograničenom intervalu. Mešanje genetskog algoritma i pretrage usponom može poboljšati efikasnost genetskog algoritma i smanjiti grubost pretrage usponom.

Ovo znači da pravila genetske varijacije mogu imati drugačija značenja u prirodi. Na primer - ako su koraci sačuvani uzastupno - prelazak može da sumira broj koraka majčine DNK dodajući korake očeve DNK itd. Štaviše, inverzni operator ima priliku da složi korake uzastupno ili u nekom drugom pogodnom poretku, radi preživljavanja ili efikasnosti. (Videti na primer[16] ili primer u problemu trgovačkog putnika, a posebno korišćenje operatora kombinacije).

Varijanta, gde populacija kao celina evoluira umesto njenih pojedinačnih pripadnika, je poznata kao kombinacija genetskog bazena.

Razvijen je veliki broj varijanti kako bi se poboljšale performanse genetskih algoritama koji rade na problemima sa visokim stepenom epistaze fithensa, npr. kada se fitnes rešenja sastoji od podskupova varijabli koji međusobno interaguju. Ovi algoritmi teže tome da prvo nauče a tek onda iskoriste ponašanje ovih korisnih fenotipskih interakcija. Kao takvi, slažu se sa hipotezom gradivnog bloka u prilagodljivom smanjivanju loših kombinacija. Istaknuti primeri ovog pristupa su mGA[17], GEMGA[18] i LLGA.[19]

Domeni problema

уреди

Problemi koje je vrlo prikladno rešavati genetskim algoritmom su problemi pravljenja rasporeda i mnogi softtver koji radi na pravljenju rasporeda je zasnovan na genetskim algoritmima. Genetski algoritmi se mogu primeniti i na inženjerstvo.[20] Genetski algoritmi se često primenjuju za rešavanje problema globalne optimizacije.

Kao generalno pravilo, genetski algoritmi mogu biti korisni u domenu problema koji imaju kompleksan pejzaš fitnesa, kako je mešanje, na primer mutacija i prelazaka, stvoreno da bi se populacija pomerila od lokalnog optimuma, na kome se algoritam pretrage usponom može zaglaviti. Može se primetiti da se operatori prelaska koji se često koriste ne mogu promeniti uniformnu populaciju.

Primeri problema koje rešava genetski algoritam su: ogledala koja su napravljena da skuplja sunčevu svetlost u solarni kolektor[21], antene napravljene da primaju radio signale u svemiru[22], i metodi za hodanje kod kompjuterskih figura.[23]

U svom Algorithm Design Manual, Skiena je protiv korišćenja genetskih algoritama u bilo koje svrhe:

„Neprirodno je modelovati aplikacije u pogledu genetskih operatora kao što su mutacije ili krosing-over nizova bitova. Pseudobiologija dodaje još jedan nivo kompleksnosti između tebe i tvog problema. Takođe, genetski algoritmi se dugo izvršavaju nad netrivijalnim problemima. [...] Analogija sa evolucijom — gde značajan napredak zahteva milione godina — može biti vrlo prikladna.
Nikada nisam naišao na problem za koji su mi genetski algoritmi izgledali kao pravi način za rešavanje. Takođe, nikada nisam video neke rezultate koji su dobijeni genetskim algoritmima koji su me oduševili.“
- Steven Skiena[24]‍:267

Komercijalni proizvodi

уреди

Kasnih 1980ih, General Electric su počeli sa prodajom prvog genetskog algoritma, alat baziran na mainframe-u napravljen za potrebe industrijede. 1989, Axcelis Inc. šalju na tržište Evolver, prvi komercijalni softver koji koristi genetski algoritam za desktop računare. John Markoff, kolumnista The New York Times-a zadužen za tehnologije, je pisao[25] o Evolveru, 1990., i Evolver je bio jedini interaktivni komercijalni genetski algoritam sve do 1995.[26] Evolver je kupio Palisade 1997. godine, preveden je na nekoliko jezika, i trenutno je u svojoj šestoj verziji..[27]

Srodne tehnike

уреди

Roditeljske oblasti

уреди

Genetski algoritmi su podoblast:

Srodne oblasti

уреди

Evolucioni algoritmi

уреди

Evolucioni algoritmi su podoblast evolucionog porgramiranja.

  • Evolucione strategije razvijaju pojedince sredstvima za mutaciju i putem posredne ili diskretne rekombinacije. Ovi algoritmi su posebno dizajnirani da reše probleme u domenu realnih vrednosti. Koriste samostalnu adaptaciju da prilagode parametre pretrage. Smanjivanje samostalne adaptacije je dovelo do savremene evolucione strategije adaptacije kovariacionih matrica (CMA-ES).
  • Evoluciono programiranje obuhvata populaciju rešenja sa prvenstveno mutacijom i selekcijom i proizvoljnom reprezentacijom. Oni koriste samostalnu adaptaciju da prilagode parametre, i mogu da ukjuče druge varijacije operacija kao što je kombinovanje operacija od više roditelja.
  • Programiranje zasnovano na prikazu gena takođe koristi populacije kompjuterskih programa. Ovi kompleksni kompjuterski programi su kodirani jednostavnijim linearnim hromozomima fiksne dužine, koji su kasnije izražena kao stabla izraza. Stabla izraza kompjuterskog programa se razvijaju zato što hromozomi prolaze mutaciju i rekombinaciju na način sličan kakonskom GA. Zahvaljujući specijalnoj organizaciji GEP hromozoma, ove genetske modifikacije uvek kao rezultat daju validne kompjuterske programe.[28]
  • Genetsko programiranje je srodna tehnika koju je učinio popularnom Džon Koza (eng. John Koza) u kojoj su kompjuterski programi, umesto parametara funkcije, optimizovani. Genetsko programiranje često koristi strukture podataka bazirane na stablima za predstavljanje kompjuterskih programa za adaptaciju umesto strukturu listi tipičnu za genetske algoritme.
  • Interaktivni evolucioni algoritmi su evolucioni algoritmi koji koriste ljudsku evoluciju. Često su primenjeni u domenima gde je teško dizajnirati računsku fitnes funkciju, na primer, razvijanje slika, muzika, umetnički dizajn i oblici koji će se uklopiti u estetski ukus korisnika.

Inteligencija roja

уреди

Inteligencija roja je podoblast evolucionog programiranja.

  • Optimizacija kolonije mrava koristi mnogo mrava da prolaze kroz prostor rešenja i pronađu lokalne produktivne oblasti. Iako je inače lošiji u odnosu na genetske algoritme i druge oblike lokalne pretrage, u stanju je da proizvede rešenja za probleme za koje ne može da se postigne ni globalna ni najnovija perspektiva, pa samim tim ni druge metode ne mogu biti primenjene.
  • Optimizacija roja čestica (PSO) je računska metoda za optimizaciju više parametara koji se koriti u pristupu zasnovanom na populaciji. Populacija (jato) kandidatskih rešenja (čestica) se kreće u potrazi za prostorom, i na kretanje čestica utiču i njihova najbolja pozicija i najbolja pozicija jata. Kao i genetski algoritam, ovaj metod zavisi od informacija koje se dele između članova populacije. Kod nekih problema PSO je često računski efikasniji od GA-a, pogotovo kod nekonstantnih problema sa stalnim promenljivama.[29]

Drugi evolucioni kompjuterski algoritmi

уреди

Evolutivno izračunavanje je podoblast metaheurističkih metoda

  • Bakteriološki algoritmi (BA) su inspirisani evolutivnom ekologijom i, još preciznije, bakeriološkom adaptacijom. Evolutivna ekologija je oblast proučavanja živih organizama u smislu njihovog okruženja sa ciljem da otkrije kako se oni prilagođavaju. Osnovni koncept je da u heterogenoj sredini se ne može pronaći jedna jedinka koja se uklapa u celu okolinu. Dakle, treba da se razmišlja na nivou cele populacije. Takođe se veruje da se BA-i mogu uspešno primeniti na složene probleme pozicioniranja(antena za mobilne telefone, urnbanistički planovi itd.) ili data mining.[30]

Druge metode metaheuristike

уреди

Metaheurističke metode široko spadaju u stohastičke metode za optimizaciju

  • Tabu pretraga: prelazi po polju rešenja testiranjem mutacija pojedinačnog rešenja. Generiše mnogo mutiranih rešenja i prelazi na rešnje najmanje energije od svih generisanih. Kako bi se izbeglo vrtenje u krug i podržala što raznovrsnije kretanje kroz prostor rešenja, čuva se tabu lista parcijalnih ili kompletnih rešenja. Zabranjeno je preći u rešenje koje sadrži elemente iz liste, koja se redovno menja i dopunjuje.
  • Optimizacija ekstremuma: Za razliku od genetskih algoritama, koji rade sa populacijom rešenja kandidata, ovaj algoritam razvija jedinstveno rešenje i pravi modifikacije nad najgorim komponentama. Glavni princip iza ovog algoritma je poboljšavanje kroz selektivno uklanjanje komponenti lošeg kvaliteta i menjanje istih nasumično izabranim komponentama. Ovo je definitivno suprotno od genetskog algoritma koji bira dobra rešenja i pokušava da napravi još bolja.

Druge stohastičke metode optimizacije

уреди
  • Metod unakrsne entropije generiše rešenja kandidate preko parametrizovane raspodele verovatnoće. Parametri se ažuriraju putem minimizacije unakrsnom entropijeom, kako bi se generisali bolji uzorci u sledećoj iteraciji.
  • Reaktivna optimizacija pretrage (eng. reactive search optimization (RSO)) podržava integraciju tehnika mašinskog učenja u heuristiku pretrage za rešavanje kompleksnih problema optimizacije. Reč „reaktivna“ nagoveštava postojanje spremnog odgovora na događaje tokom pretrage kroz petlju internih online povratnih informacija radi samopodešavanja kritičnih parametara. Metodologije od interesa za reaktivnu pretragu uključuju mašinsko učenje i statistiku.

Vidi još

уреди

Reference

уреди
  1. ^ Mitchell, Melanie (1996). An Introduction to Genetic Algorithms. Cambridge: MA: MIT Press. стр. 2. ISBN 9780585030944. 
  2. ^ Haupt i Haupt, pp. 29 i 52
  3. ^ Whitley, Darrell (1994). "A genetic algorithm tutorial". Statistics and Computing. стр. 65—85. 
  4. ^ Eiben, A. E. et al . "Genetic algorithms with multi-parent recombination". PPSN III: Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature: 78-87. . 1994. ISBN 978-3-540-58484-1.  Недостаје или је празан параметар |title= (помоћ)
  5. ^ Ting, Chuan-Kang . "On the Mean Convergence Time of Multi-parent Genetic Algorithms Without Selection". Advances in Artificial Life: 403-412. . 2005. ISBN 978-3-540-28848-0.  Недостаје или је празан параметар |title= (помоћ)
  6. ^ Akbari, Ziarati (2010). "A multilevel evolutionary algorithm for optimizing numerical functions" IJIEC 2 (2011): 419-430 [1]
  7. ^ Goldberg, David (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Reading: MA: Addison-Wesley Professional. стр. 41. ISBN 978-0201157673. 
  8. ^ Taherdangkoo, Mohammad; Paziresh, Mahsa; Yazdi, Mehran; Bagheri, Mohammad (2013). „An efficient algorithm for function optimization: Modified stem cells algorithm”. Open Engineering. 3 (1): 36—50. Bibcode:2013CEJE....3...36T. S2CID 108711765. doi:10.2478/s13531-012-0047-8. .
  9. ^ Wolpert, D.H., Macready, W.G., 1995. No Free Lunch Theorems for Optimisation. Santa Fe Institute, SFI-TR-05-010, Santa Fe.
  10. ^ Goldberg, David E. (1991). „The theory of virtual alphabets”. Parallel Problem Solving from Nature. Parallel Problem Solving from Nature, Lecture Notes in Computer Science. Lecture Notes in Computer Science. 496. стр. 13—22. ISBN 3-540-54148-9. doi:10.1007/BFb0029726. Приступљено 2. 7. 2013. 
  11. ^ Janikow, C. Z.; Michalewicz, Z. (1991). „An Experimental Comparison of Binary and Floating Point Representations in Genetic Algorithms” (PDF). Proceedings of the Fourth International Conference on Genetic Algorithms: 31—36. Приступљено 2. 7. 2013. 
  12. ^ Patrascu, M.; Stancu, A.F.; Pop, F. (2014). „HELGA: a heterogeneous encoding lifelike genetic algorithm for population evolution modeling and simulation”. Soft Computing. 18 (12): 2565—2576. S2CID 254036442. doi:10.1007/s00500-014-1401-y. 
  13. ^ Baluja, Shumeet; Caruana, Rich (1995). Removing the genetics from the standard genetic algorithm (PDF). ICML. 
  14. ^ Srinivas. M and Patnaik. L, "Adaptive probabilities of crossover and mutation in genetic algorithms," IEEE Transactions on System, Man and Cybernetics, vol.24, no.4, pp. 656-667, 1994.
  15. ^ ZHANG. J, Chung. H and Lo. W. L, "Clustering-Based Adaptive Crossover and Mutation Probabilities for Genetic Algorithms", IEEE Transactions on Evolutionary Computation vol.11, no.3. стр. 326-335, 2007.
  16. ^ „Evolution-in-a-nutshell”. Архивирано из оригинала 15. 4. 2016. г. Приступљено 19. 5. 2016. 
  17. ^ D.E. Goldberg, B. Korb, and K. Deb (октобар 1989). „Messy genetic algorithms: Motivation, analysis, and first results”. Complex Systems. 5 (3): 493—530. 
  18. ^ Gene expression: The missing link in evolutionary computation
  19. ^ G. Harik. Learning linkage to efficiently solve problems of bounded difficulty using genetic algorithms. PhD thesis, Dept. Computer Science, University of Michigan, Ann Arbour, 1997
  20. ^ Tomoiagă, Bogdan; Chindriş, Mircea; Sumper, Andreas; Sudria-Andreu, Antoni; Villafafila-Robles, Roberto (2013). „Pareto Optimal Reconfiguration of Power Distribution Systems Using a Genetic Algorithm Based on NSGA-II”. Energies. 6 (3): 1439—1455. doi:10.3390/en6031439  . .
  21. ^ Gross, Bill. „A solar energy system that tracks the sun”. TED. Приступљено 20. 11. 2013. 
  22. ^ Hornby, G. S.; Linden, D. S.; Lohn, J. D., Automated Antenna Design with Evolutionary Algorithms (PDF) 
  23. ^ Flexible Muscle-Based Locomotion for Bipedal Creatures
  24. ^ Skiena, Steven (2010). The Algorithm Design Manual (2nd изд.). Springer Science+Business Media. ISBN 978-1-84996-720-4. 
  25. ^ Markoff, John (29. 8. 1990). „What's the Best Answer? It's Survival of the Fittest”. New York Times. Приступљено 9. 8. 2009.  Проверите вредност парамет(а)ра за датум: |year= / |date= mismatch (помоћ)
  26. ^ Ruggiero, Murray A.. (2009-08-01) Fifteen years and counting Архивирано на сајту Wayback Machine (30. јануар 2016). Futuresmag.com. Приступљено 2013-08-07.
  27. ^ Evolver: Sophisticated Optimization for Spreadsheets. Palisade. Приступљено 2013-08-07.
  28. ^ Ferreira, C. „Gene Expression Programming: A New Adaptive Algorithm for Solving Problems” (PDF). Complex Systems, Vol. 13, issue 2: 87-129. 
  29. ^ Rania Hassan, Babak Cohanim, Olivier de Weck, Gerhard Vente r (2005) A comparison of particle swarm optimization and the genetic algorithm
  30. ^ Baudry, Benoit; Fleurey, Franck; Jean-Marc Jézéquel; Yves Le Traon (2005). „Automatic Test Case Optimization: A Bacteriologic Algorithm” (PDF). IEEE Software. IEEE Computer Society. 22 (2): 76—82. S2CID 3559602. doi:10.1109/MS.2005.30. Приступљено 9. 8. 2009. 
  31. ^ Civicioglu, P. (2012). „Transforming Geocentric Cartesian Coordinates to Geodetic Coordinates by Using Differential Search Algorithm”. Computers &Geosciences. 46: 229—247. Bibcode:2012CG.....46..229C. doi:10.1016/j.cageo.2011.12.011. 

Spoljašnje veze

уреди

Resursi

уреди

Priručnici

уреди
Преузето из „https://sr.wikipedia.org/w/index.php?title=Genetski_algoritam&oldid=27740991”