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.
Rad GA se može opisati u osam odnosno sedam koraka[2]:
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:
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.
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.
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.
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.
Ovaj generacijski proces se ponavlja sve dok se ne postigne uslov prekida. Opšti uslovi završetka su:
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:
Goldberg opisuje heuristiku na sledeći način:
Postoje ograničenja upotrebe genetskog algoritma u odnosu na alternativne algoritme za optimizaciju:
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.
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]
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.
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]
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:
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]
Genetski algoritmi su podoblast:
Evolucioni algoritmi su podoblast evolucionog porgramiranja.
Inteligencija roja je podoblast evolucionog programiranja.
Evolutivno izračunavanje je podoblast metaheurističkih metoda
Metaheurističke metode široko spadaju u stohastičke metode za optimizaciju
|title=
|year= / |date= mismatch