Genetski algoritmi
Genetski algoritmi predstavljaju jednu od najpoznatijih metoda evolutivnog računarstva. Njihova osnovna ideja potiče iz prirodne evolucije: populacija mogućih rešenja se menja kroz generacije, bolja rešenja imaju veću šansu da opstanu, a nova rešenja nastaju kombinovanjem i malim promenama postojećih.
U prirodi se organizmi prilagođavaju okruženju kroz nasleđivanje, varijaciju i selekciju. Genetski algoritmi tu ideju prenose u računarstvo. Umesto živih organizama imamo moguća rešenja problema. Umesto biološke sposobnosti preživljavanja imamo funkciju prilagođenosti, odnosno fitness funkciju.
Genetski algoritam ne pokušava da odmah pronađe savršeno rešenje. On počinje od skupa početnih pokušaja, zatim ih procenjuje, bira bolje, kombinuje njihove osobine i uvodi male slučajne promene. Kroz više generacija, populacija se postepeno pomera ka boljim rešenjima.
Ovakav pristup posebno je koristan kada je prostor mogućih rešenja veoma veliki. Ako postoji ogroman broj kombinacija, klasično isprobavanje svih mogućnosti postaje presporo ili nemoguće. Genetski algoritmi tada nude praktičan način inteligentnog pretraživanja.
Tipični problemi u kojima se koriste genetski algoritmi uključuju optimizaciju funkcija, raspoređivanje poslova, planiranje ruta, izbor osobina u mašinskom učenju, podešavanje hiperparametara, dizajn sistema, inženjersku optimizaciju i kombinatorne probleme.
Osnovni pojam genetskog algoritma je populacija. Populacija je skup mogućih rešenja u jednom trenutku. Svako pojedinačno rešenje naziva se jedinka. Jedinka može predstavljati broj, niz brojeva, raspored elemenata, skup odluka ili bilo koju strukturu koja opisuje kandidat-rešenje.
Da bi algoritam mogao da radi sa rešenjem, ono mora biti predstavljeno u odgovarajućem obliku. Taj zapis se često naziva hromozom. Hromozom se sastoji od manjih delova, koje nazivamo genima. Geni nose pojedinačne informacije o rešenju.
Na primer, ako rešavamo problem izbora optimalnog skupa parametara, hromozom može biti niz vrednosti tih parametara. Ako rešavamo problem rasporeda, hromozom može biti permutacija elemenata. Ako rešavamo jednostavan binarni problem, hromozom može biti niz nula i jedinica.
Kodiranje rešenja je jedan od najvažnijih koraka u projektovanju genetskog algoritma. Loše kodiranje može otežati pretraživanje, dok dobro kodiranje može učiniti algoritam jednostavnijim, stabilnijim i efikasnijim.
U genetskim algoritmima često razlikujemo genotip i fenotip. Genotip je unutrašnji zapis rešenja, na primer niz brojeva ili bitova. Fenotip je stvarno značenje tog zapisa u problemu koji rešavamo. Algoritam radi nad genotipom, ali kvalitet rešenja ocenjujemo kroz fenotip.
Početna populacija se najčešće generiše slučajno. To omogućava raznovrsnost od samog početka. U nekim slučajevima deo početne populacije može biti zasnovan na poznatim dobrim rešenjima, iskustvu stručnjaka ili heuristikama.
Nakon što imamo populaciju, potrebno je oceniti svaku jedinku. To radi fitness funkcija. Ona svakom rešenju dodeljuje vrednost koja opisuje koliko je to rešenje dobro u odnosu na cilj problema.
Ako rešavamo problem minimizacije, dobro rešenje može imati manju vrednost greške, troška ili udaljenosti. Ako rešavamo problem maksimizacije, dobro rešenje može imati veću vrednost koristi, profita, tačnosti ili performanse.
Fitness funkcija je srce genetskog algoritma. Ona usmerava evoluciju. Ako fitness funkcija ne opisuje dobro ono što zaista želimo da postignemo, algoritam će optimizovati pogrešan cilj, čak i ako tehnički radi ispravno.
U realnim problemima često postoje ograničenja. Neka rešenja nisu dozvoljena, neka su preskupa, neka krše pravila sistema. Tada se koriste različiti pristupi: odbacivanje nevalidnih rešenja, popravljanje rešenja ili kaznene funkcije koje smanjuju kvalitet nedozvoljenih kandidata.
Kada su rešenja ocenjena, sledi selekcija. Selekcija bira jedinke koje će učestvovati u stvaranju nove generacije. Ideja je da bolja rešenja imaju veću šansu da prenesu svoje osobine, ali da ni slabija rešenja ne budu uvek potpuno isključena.
Ako bismo uvek birali samo najbolje jedinke, populacija bi brzo izgubila raznovrsnost i mogla bi prerano da se zaglavi. Ako bismo birali potpuno slučajno, algoritam ne bi dovoljno koristio informacije o kvalitetu rešenja. Zato je selekcija ravnoteža između pritiska i raznovrsnosti.
Postoji više metoda selekcije. Rulet selekcija daje veću verovatnoću izbora jedinkama sa boljim fitness vrednostima. Turnirska selekcija bira nekoliko kandidata i među njima izdvaja najboljeg. Rang selekcija koristi poredak jedinki umesto apsolutnih fitness vrednosti.
Posle selekcije sledi ukrštanje. Ukrštanje kombinuje delove dva ili više roditeljskih rešenja da bi se dobilo novo rešenje. Cilj je da se dobre osobine različitih jedinki spoje u potomku.
U binarnom kodiranju ukrštanje može značiti da prvi deo niza dolazi od jednog roditelja, a drugi deo od drugog. U realno kodiranim algoritmima ukrštanje može kombinovati numeričke vrednosti. U permutacionim problemima ukrštanje mora čuvati validan redosled elemenata.
Mutacija uvodi male slučajne promene u rešenja. Ona je važna zato što održava raznovrsnost populacije i omogućava algoritmu da istražuje delove prostora rešenja do kojih ukrštanje samo možda ne bi došlo.
Mutacija ne treba da bude previše jaka, jer bi algoritam postao gotovo slučajna pretraga. Ali ne treba da bude ni preslaba, jer populacija može izgubiti raznovrsnost. Njena uloga je mala, ali veoma značajna promena koja ponekad otvara put ka boljem rešenju.
Elitizam je mehanizam kojim se najbolja rešenja čuvaju i direktno prenose u sledeću generaciju. Time se sprečava da već pronađeno dobro rešenje nestane zbog slučajnog ukrštanja ili mutacije.
Osnovni ciklus genetskog algoritma obično izgleda ovako: napravi početnu populaciju, izračunaj fitness, izaberi roditelje, primeni ukrštanje, primeni mutaciju, formiraj novu generaciju i ponavljaj postupak dok se ne ispuni kriterijum zaustavljanja.
Kriterijum zaustavljanja može biti maksimalan broj generacija, dostignuta zadovoljavajuća fitness vrednost, prestanak značajnog poboljšanja ili vremensko ograničenje. U praksi se često kombinuje više kriterijuma.
Jedan od važnih pojmova je konvergencija. Konvergencija znači da se populacija sve više približava određenom delu prostora rešenja. To je poželjno kada vodi ka dobrom rešenju, ali može biti problem ako se dogodi prerano.
Prerana konvergencija nastaje kada populacija brzo izgubi raznovrsnost i zaglavi se oko lokalno dobrog, ali ne i globalno najboljeg rešenja. Zbog toga je diverzitet populacije veoma važan.
Diverzitet označava raznovrsnost rešenja u populaciji. Dovoljno raznovrsna populacija bolje istražuje prostor mogućnosti. Premalo raznovrsnosti vodi ka stagnaciji, a previše raznovrsnosti može usporiti usmereno poboljšavanje.
Podešavanje parametara genetskog algoritma ima veliki uticaj na rezultate. Veličina populacije, verovatnoća ukrštanja, verovatnoća mutacije, broj generacija, način selekcije i oblik kodiranja zajedno određuju ponašanje algoritma.
Ne postoji jedno univerzalno podešavanje koje je najbolje za sve probleme. Genetski algoritmi se obično podešavaju eksperimentalno. To znači da se pokreću više puta, porede rezultati i traži stabilna kombinacija parametara.
Genetski algoritmi mogu biti binarni, realno kodirani, celobrojni, permutacioni ili posebno prilagođeni određenom problemu. Izbor zavisi od toga kako prirodno izgleda rešenje koje optimizujemo.
Binarni genetski algoritmi koriste nizove nula i jedinica i često su istorijski prvi primer koji se uči. Realno kodirani algoritmi direktno rade sa decimalnim vrednostima. Permutacioni algoritmi se koriste za probleme redosleda, kao što su rute, rasporedi i sekvence.
U višekriterijumskoj optimizaciji ne postoji uvek jedno najbolje rešenje. Nekada želimo istovremeno smanjiti trošak, povećati kvalitet i smanjiti rizik. Ta rešenja se ne mogu uvek svesti na jedan broj bez gubitka značenja.
Pareto optimalnost uvodi ideju skupa dobrih kompromisa. Rešenje je Pareto optimalno ako ne možemo poboljšati jedan kriterijum, a da ne pogoršamo bar jedan drugi. Genetski algoritmi su posebno pogodni za ovakve probleme jer rade sa populacijom rešenja.
Genetski algoritmi se često kombinuju sa drugim metodama. Mogu se povezati sa lokalnom pretragom, heuristikama, fuzzy logikom, neuralnim mrežama, mašinskim učenjem i ekspertnim sistemima. Takvi pristupi nazivaju se hibridni genetski algoritmi.
U mašinskom učenju genetski algoritmi mogu pomoći u izboru osobina, podešavanju hiperparametara, izboru arhitekture modela ili optimizaciji pravila. Njihova prednost je što ne zahtevaju da problem bude gladak, diferencijabilan ili jednostavno matematički opisan.
Važno je razumeti i ograničenja. Genetski algoritmi ne garantuju uvek globalno najbolje rešenje. Mogu biti računarski zahtevni, posebno ako je fitness funkcija spora. Rezultati mogu zavisiti od slučajnosti, pa je često potrebno pokretati algoritam više puta.
Ipak, njihova snaga je u fleksibilnosti. Kada se problem može predstaviti kao skup mogućih rešenja i kada znamo kako da ocenimo kvalitet rešenja, genetski algoritam često može ponuditi dobar praktičan pristup.
U Pythonu se genetski algoritmi mogu pisati od nule, što je odličan način za učenje. Postoje i biblioteke koje olakšavaju rad sa populacijom, selekcijom, ukrštanjem, mutacijom i evaluacijom, ali razumevanje osnovnog ciklusa ostaje najvažnije.
Ovaj tutorijal je zamišljen kao postepen i praktičan ulazak u genetske algoritme. Ne polazimo od pretpostavke da čitalac već zna evolutivno računarstvo, već gradimo razumevanje od prirodne analogije ka konkretnom algoritmu i primeni.
Prvi deo praktikuma uvodi osnovne pojmove: šta su genetski algoritmi, kako su povezani sa prirodnom evolucijom, šta su populacija, jedinka, hromozom, gen, kodiranje rešenja, fitness funkcija, selekcija, ukrštanje, mutacija i elitizam.
Drugi deo praktikuma uvodi naprednije teme: osnovni ciklus algoritma, veličinu populacije, verovatnoće ukrštanja i mutacije, kriterijume zaustavljanja, konvergenciju, diverzitet, tipove genetskih algoritama, višekriterijumsku optimizaciju i Pareto optimalnost.
Zatim prelazimo na projektovanje, podešavanje i hibridne pristupe. Posebno ćemo obratiti pažnju na to kako se problem prevodi u hromozom, kako se bira fitness funkcija, kako se tumače rezultati i kako se algoritam proverava na realnim primerima.
Mini projekat na kraju povezuje sve oblasti u jedan praktičan tok rada: izbor problema, definisanje zapisa rešenja, izrada početne populacije, evaluacija fitness funkcije, selekcija, ukrštanje, mutacija, elitizam, testiranje i interpretacija rezultata.
Genetski algoritmi su put od evolucione ideje ka inteligentnoj optimizaciji. Kada razumemo taj put, možemo graditi sisteme koji ne traže rešenje naslepo, već uče iz populacije pokušaja, čuvaju dobre osobine i postepeno oblikuju sve kvalitetnije odgovore.