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. 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: Definisanje svih potrebnih parametara problema i GA Formiranje početne populacije Dekodiranje hromozoma — ovaj korak se javlja samo kod binarnih GA Određivanje cena hromozomima (fitnes funkcijom) Odabir selekcije hromozoma koji će opstati za parenje 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 Mutacije, pri kojima se menja genetski sadržaj hromozoma 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 individue 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: Genetski prikaz domena rešenja Funkciju fitnes za procenu domena rešenja
Standardna reprezentacija svakog rešenja kandidata je niz bitova.Nizovi drugih tipova i struktura se u suštini mogu koristiti na isti način. Glavna osobina koji čini ove genetske reprezentacije pogodne je da su njihovi delovi jako usklađeni zbog fiksne veličine što olakšava jednostavne operacije 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 predstavljenog 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 odrediti 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 karakteristike 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. PPSN III: Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature: 78-87. . Advances in Artificial Life: 403-412. sugerišu da se korišćenjem više od dva „roditelja“ generiše kvalitetnije hromozome.
Ovi procesi na kraju dovode 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. IJIEC
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 (izračunava se vreme / novac) je potrošen Fitnes rešenja koje je najviše rangirano 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: Opis heuristike koja obavlja adaptaciju tako što identifikuje i kombinuje gradivne blokove, npr. shema niskog reda sa fitnesom iznad proseka. 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), kombinuju 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šljavajuć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."
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 problemi 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čigledno je da spoj približ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 ventilatora 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,