Genetinis algoritmas

Genetinis algoritmas (GA) – algoritmas, paremtas biologijos žiniomis apie gyvybės evoliuciją. GA yra tam tikra evoliucinių algoritmų klasė, naudojanti gamtoje egzistuojančius gyvybės evoliucinius mechanizmus: paveldėjimą, mutaciją, natūraliąją atranką ir rekombinaciją. Genetiniai algoritmai yra metodas analizuoti duomenis, jų dėka galima rasti apytikslį užduoties sprendimą. Sprendimas randamas naudojant evoliucinį ciklą, veikiantį gamtoje. Genetiniai algoritmai tinka ne visur, tačiau jais galima rasti palyginti neblogus sprendinius užduočių, kurių tikslaus sprendimo algoritmai nežinomi.
GA yra priemonė kompiuteryje atkartoti tam tikros populiacijos (vad. chromosomomis) ir sprendimų kandidatų (vad. individais) evoliuciją, artėjant prie geriausio užduoties sprendimo. Tradiciškai naudojami dvejetainis kodavimas, sudarytas iš 0 ir 1, tačiau galimas ir kitoks kodavimas.

Algoritmas

Pasirinkus pradinę populiaciją, evoliucija prasideda nuo visiškai atsitiktinių kitimų. Gavus naują populiacijos kartą (kandidatus) įvertinamas jos tinkamumas, atrenkamas tam tikras naujos kartos individų skaičius, pagal atrankos kriterijų. Atrinktieji individai pakeičiami darant mutacijas arba rekombinacijas ir sukuriama nauja populiacija. Vėliau viskas kartojama, atrenkant naujus tinkamiausius individus, sukuriant naują populiaciją. Ciklas kartojamas, kol gaunamas užduotį tenkinantis sprendimą.

Istorija

Genetiniai algoritmai kilo studijuojant ląstelių mechanizmą. Tyrimus vykdė John Holland vadovaujama grupė iš JAV Mičigano universiteto. Apie 1985-sius Ilinojaus universitete įvyko Pirmoji tarptautinė konferencija skirta genetiniams algoritmams, iki tol genetinių algoritmų tyrimai buvo daugiausia tik teoriniai. Augant akademiniam susidomėjimui bei vystantis kompiuterijai atsirado galimybė praktiniam genetinių algoritmų įgyvendinimui. 1989 m. JAV laikraštis The New York Times išspausdino rašytojo John Markoff straipsnį apie pirmą komercinę genetinį algoritmą naudojančią programą Evolver. Vėliau atsirado įvairios kompiuterinės programos skirtos įvairioms sritims. Dabartiniu metu programas naudojančias genetinius algoritmus naudoja didžioji dalis Fortune 500 kompanijų, išspręsti tvarkaraščių, duomenų talpinimo, biudžeto paskirstymo ir kitas svarbias užduotis, kur galima pritaikyti kombinatorinį optimizavimą.

Dažniausi pritaikymai

Ypatingai tinkamos genetinių algoritmų panaudojimui užduotys yra tvarkaraščių ir grafikų sudarymas, todėl daugybė šios srities programinės įrangos paketų yra paremta genetiniais algoritmais. Genetiniai algoritmai naudojami inžinerijoje bei spręsti globalias optimizavimo problemas.
Genetiniai algoritmai panaudojami ir ten, kur tradiciniai laiptiniai algoritmai (angl. hill climbing algorithms) gali užstrigti. Genetiniai algoritmai gali būti naudojami ten, kur užduoties struktūra ganėtinai sudėtinga, dėl rekombinacijos jie nuo minimumo gali judėti toliau link teisingo sprendinio, ko nesugeba laiptiniai algoritmai.

Pritaikymo elementai

GA panaudojimui ieškant užduoties sprendimo reikalingi du pagrindiniai elementai: tinkama pradinė duomenų struktūra ir atrankos kriterijus. Algoritmui paprastai reikia, jog uždavinio sprendimas galėtų būti pateikiamas kaip duomenų struktūra, kad būtų galima nesunkiai kurti šios struktūros pakeistas kopijas. Antrasis elementas tam tikras atrankos metodas – funkcija, aprašanti atrankos kriterijų. Jos dėka galima taikyti kiekybinius atrankos kriterijus, atrenkant geresnius ir blogesnius sprendinius.

GA pritaikymo pavyzdys

Pavyzdžiui, užduotis yra kuo didesnę masę sutalpinti į krepšį, jo nesuplėšius. Sprendimas gali būti vaizduojamas kaip bitų eilutė, kur kiekvienas bitas reiškia atskirą krovinį (turintį savo masę), o bito reikšmė (0 arba 1) reiškia buvo krovinys įdėtas į krepšį ar ne. Sprendimo tinkamumą parodo gauta bendra masė. Kuo didesnė masė gaunama susumavus visas įdėtų krovinių mases, tuo tinkamesnis sprendimas.

GA pradžia

Pradžioje daug individualių sprendimų yra atsitiktinai generuojami suformuojant atsitiktinę pradinę populiaciją. Populiacijos dydis pasirenkamas pagal užduoties sudėtingumą. Dažniausiai populiaciją sudaro keletas šimtų ar net tūkstančių galimų sprendimų. Tradiciškai populiacija generuojama atsitiktinai, apimant didelį sprendinių paieškos diapazoną. Kartais nubrėžiamos tam tikros ribos, kuriose sprendinys tikėtinai turėtų būti, tokiu būdu sutrumpinamas paieškos laikas.

Atranka

Iš populiacijos atrenkama dalis tinkamiausių sprendinių (sėkmingiausių „palikuonių“), iš kurių bus kuriama naujoji populiacija. Atrankos kriterijų aprašo tinkamumo funkcija, kuri ir lemia atranką. Dažniausiai taikomas metodas, kai iš visos populiacijos atrenkami labiausiai tinkami sprendiniai. Tačiau yra ir kitas atrankos metodas, kurio metu yra vertinami tik atsitiktinai populiacijos sprendiniai. Šis, antrasis metodas, yra mažiau efektyvus nei pirmasis, kadangi šiuo metodu tiksliausio sprendimo paieška trunka žymiai ilgiau.
Dauguma atrankos funkcijų yra tikimybinės ir sukurtos taip, kad atrinktų tinkamais ir nedidelę dalį sprendinių, kuri yra mažiau tinkama. Tokiu būdu užtikrinimą, kad išliktų įvairovė ir išvengiama pirmalaikės konvergencijos bei nukrypimo į netinkamus sprendinius. Dažniausi ir daugiausiai išstudijuoti atrankos metodai: ruletės ir turnyrinė atranka.

Elito atranka

Ignoruojantis įprastą eigą, tačiau labai efektyvus yra variantas, kai konstruojant naują populiaciją, leidžiama keliems sėkmingiausiems organizmams (sprendiniams) pereiti į naują populiacijai visai nepakitus. Ši strategija vadinama elito atranka (angl. elitist selection).

Mutacija ir rekombinacija

Antrosios ir kitų populiacijų kūrimą sudaro genetinių mechanizmų: rekombinacijos ir mutacijos – pritaikymas. Rekombinaciją ir mutacija yra biologinių mechanizmų analogai.
Kiekvieno naujo sprendinio sukūrimui iš populiacijos imama pora sprendinių „tėvų“, kurie sukryžminami ir mutacijos ar rekombinacijos būdu gaunamas sprendinys „vaikas“. Toliau imama kita „tėvų“ pora ir vėl sukuriamas „vaikas“ ir taip tęsiama kol pasiekiamas tam tikras naujos kartos individų skaičius, sukuriama pilna nauja sprendinių populiacija.
Galiausiai po šių procesų naująsias kartas sudarys individai, kurių chromosomos (sandara) yra visiškai skirtinga nei pradinės populiacijos. Bendras populiacijos tinkamumo vidurkis taip pat pakils, kadangi išliks tik geriausi individai (sprendiniai) ir dalis mažiau tinkamų individų (priežastys paminėtos prieš tai skyriuje „Atranka“.)

Mutacija

Mutacija yra būdas genetiniuose algoritmuose išlaikyti genetinę įvairovę. Mutacija naudojama GA yra biologinės mutacijos analogas, kadangi jos mechanizmas buvo kuriamas pagal biologinę mutaciją. Mutacijos padeda išvengti populiacijos chromosomų supanašėjimo (lokalaus konvergavimo), o tai vestų į evoliucijos sulėtėjimą ar net visišką stagnaciją. Tai taip pat paaiškina, kodėl GA sistemos vengia naudoti tokį atrinkimo būdą, kai atrenkami vien tik geriausi.
Klasikinį mutacijų operatoriaus veikimą sudaro atsitiktinai generuojami skaičiai, kurie nurodo įvyks ar neįvyks mutaciją tam tikrai duomenų daliai.

Stebėjimai

Yra keletas pagrindinių stebėjimų susijusių su GA. Dauguma GA problemų kyla dėl didelio jų sudėtingumo.

Lokalus konvergavimas

GA gali turėti tendenciją konverguoti link lokalaus (riboto) sprendimo, vietoje globalaus (visa apimančio) tinkamiausio sprendimo. Šios problemos tikėtinumas priklauso nuo architektūrinės tinkamumo formos. Tam tikrų problemų sprendimai lengviau krypsta link globalaus sprendinio, kitoms funkcijos lengviau rasti vietinį tinkamiausią sprendinį.
Ją sumažinti ar net visai išspręsti gali skirtingos atrankos funkcijos, arba metodai naudojami išlaikyti kuo įvairiapusiškesnę sprendinių populiaciją.

Mutacija ar rekombinacija?

Atranka yra pats svarbiausias veiksnys, tačiau yra dvi vyraujančios nuomonės dėl to kas svarbiau mutacija ar rekombinacija. Rekombinaciją palaikantieji teigia, kad ji svarbiausia, o mutacija tik užtikrinanti, kad nebūtų prarastas sprendimo potencialas. Kiti teigia, kad rekombinacija reikalinga tik tam, kad paskleistų naujoves, sukurtas mutacijų. Ir tam kad, nepastoviose populiacijose rekombinacija yra tapati didelei mutacijai (kuri dažniausiai būna katastrofiška). Dažniausiai GA greitai lokalizuoja gerą sprendimą, net ir sudėtingose paieškos srities vietose.

Optimizavimo užduotys

Specifinėms optimizavimo užduotims, paprastesni optimizavimo algoritmai gali rasti geresni sprendimą nei genetiniai algoritmai, jeigu būtų duotas tas pats skaičiavimams laikas. GA naudotojai gali pamėginti papildomai naudoti kitus algoritmus, kadangi GA negali efektyviai spręsti tų užduočių, kur negalima nustatyti, kuris variantas yra geresnis ar blogesnis, todėl negali konverguoti link tam tikro geriausio sprendimo.

Parametrų suderinimas

Visoms mašinoms (programoms), kurios ieško užduočių sprendimų yra būtina teisingai suderinti parametrus, būtinus geram sprendimo paieškos veikimui, atsižvelgiant į užduoties sudėtingumą ir tipą. Reikia suderinti šiuos parametrus: mutacijos parametrą (tikimybę, dydį), rekombinacijos parametrą (tikimybę, dydį), populiacijos dydį. Pernelyg mažas mutacijų dažnumas gali vesti link genetinio dreifo ar pirmalaikės konvergencijos į lokalų sprendinį. Jei mutacijų parametras yra per didelis, gali vesti link gerų sprendimų praradimų. Yra mėginama nustatyti šiuos rėžius, tačiau kol kas tai daroma tik teoriškai. Kitas nemažiau svarbus veiksnys yra atrankos funkcijos greitis ir efektyvumas, nuo to priklauso algoritmo darbas. Siekiama, kad atrankos funkcijos greitis ir efektyvumas būtų kuo didesni.

Variantai

Paprasčiausias algoritmo duomenų struktūros variantas, kai kiekvieną chromosomą išreiškiama bitų eilute. Dažnai parametrai užrašomi integer (sveikaisiais) tipo skaičiais, tačiau galima juos užrašyti ir real (slankiojančio kablelio, dešimtainiai ir kt.) tipo skaičiais. Algoritmo pagrindas yra mutacijos ir rekombinacijos mechanizmai atliekami bitų lygyje. Kiti duomenų struktūros variantai: chromosoma yra žymima skaičių sąrašu, kuris indeksuojamas instrukcijų lentelėje, taškais susietais su sąrašu, objektais ir kitomis duomenų struktūromis. Rekombinacija ir mutacija atliekamos taip, kad būtų paisoma duomenų struktūros elementų ribų. Daugumai duomenų tipų galima sukurti specifinius operatorius. Skirtingi chromosomų duomenų tipai veikia nevienodai sprendžiant skirtingų sričių užduotis.
Kai bitų eilutės naudoja integer tipo duomenis, dažnai naudojamas Grėjaus kodavimas (ang. Gray coding) – specifinis dvejetainio kodo išdėstymas. Šiuo kodavimu lengvai padaromi maži pakeitimai, sukelti mutacijų ir rekombinacijų. Tai taip pat padeda išvengti pirmalaikio konvergavimo, kai turėtų įvykti tuo pat metu daugybė mutacijų (ar rekombinacijų), kad būtų pasiektas pokytis link geresnio sprendimo radimo.
Kiti būdai siejami su masyvais, naudojančiais real tipo skaičius, kuriais išreiškiama chromosoma. Teoriškai turėtų būti, kad kuo mažesnis alfabetas, tuo geresnis veikimas ir rezultatas, tačiau iš tikrųjų yra atvirkščiai, kadangi geriausi rezultatai gaunami naudojant būtent real tipo chromosomas.

Paralelinis įgyvendinimas

Paralelinis GA įgyvendinimo gali būti du variantai. Prastai padarytas paralelinis genetinis algoritmas apima populiacijas, esančias kiekviename kompiuterio taške ir migraciją tarp jų. Gerai padarytas paralelinis genetinis algoritmas apima individą kiekviename procesoriaus taške, kuris sąveikauja su kitais „kaimyniniais“ individais, pasirinkdamas ir daugindamasis. Kiti variantai kai GA naudojamas tinklinio optimizavimo užduotims prideda papildomas laiko ar netvarkos priklausomybes atrankos funkcijoje.

Giminingos metodikos

Genetinis programavimas (angl. Genetic programming) – naudojamas medžio tipo duomenų struktūrose, vaizduojant kompiuterio programų adaptaciją, vietoje sąrašo ar masyvo, kurį dažniausiai naudoja genetiniai algoritmai. Genetinio programavimo algoritmai dažniausiai reikalauja ilgesnio veikimo laiko, tačiau jų didesnis galingumas. Jie gali būti pritaikomi spręsti tuos uždavinius, kuriuos spręsti sunkiai pavyksta su genetiniais algoritmais.
Sąveikaujantys genetiniai algoritmai (angl. Interactive genetic algorithms) – genetiniai algoritmai, kurie naudoja žmogaus įvertinimą. Jie naudojami srityse, kur sunku aprašyti atrankos funkciją. Pavyzdžiui, evoliucionuojantys vaizdai, muzika, kitos meninės formos, kurios priklauso nuo naudotojų estetinio pasirinkimo.
angl. Simulated annealing (SA) – siejami su globaliais optimizavimo metodais, kurie keliauja paieškos erdve, bandydami įvairias mutacijas ir individualius sprendimus. Priimama ta mutacija kuri padidina veikimo efektyvumą. Mutacija, kuri mažina efektyvumą priimama tikimybiškai priklausomai nuo tinkamumo pasiskirstymo, dažniausiai mažinant temperatūros parametrą. Egzistuoja skirtingi prioritetų vystymo keliai: pagal vieną siekiama suvartoti kuo mažiau energijos, pagal kitą siekiama didžiausio sprendimo tinkamumo. SA gali būti naudojami GA viduje, paprasčiausiai pradedama naudojant didesnį mutacijų dažnį, kuris vėliau pagal grafiką mažinamas.
Tabu tyrimai (angl. Tabu search, (TS)) – panašūs į SA, abiejuose ieškoma sprendimo keliaujant paieškos erdve ir bandomos įvairios mutacijas bei individualūs sprendimai. SA generuoja vieną mutavusį sprendimą, o TS generuoja daugybę mutavusių sprendinių, bet ima mažiausia tinkamumą (sveikumą) pademonstravusį sprendinį. Tam kad būtų išvengta cikliškumo užtikrinama didesnė judėjimo laisvė sprendinių erdvėje. Tabu sąrašą sudaro daliniai arba pilni sprendiniai. Yra draudžiama imti sprendinį iš tabu sąrašo, kuris atnaujinamas vykstant sprendinio paieškai.
Skruzdėlių kolonijos optimizavimas (angl. Ant colony optimization) naudoja daug skruzdėlių (agentų), kurios keliauja sprendimų erdvėje ir ieško produktyviausių vietų. Skruzdėlių kolonijos optimizavimas gali būti naudojamas spręsti uždaviniams, kurie nėra globalūs ar neturi naujausios informacijos, kurios reikia kitiems metodams, todėl gali būti pritaikytas ten kur kiti negali veikti.
Memetitinis algoritmas (angl. Memetic algorithm, MA) – terminas, kurį naudoja mokslininkai įvardindami gentinių algoritmus, kurie yra kombinuoti su kitomis lokalių paieškų formomis, tokiomis kaip SA. Kai kurie mokslininkai juos įvardija kaip genetinių algoritmų ir paralelinių genetinių algoritmų hibridus. Memetiniai algoritmai yra efektyvesni už genetinius algoritmus ieškant sprendimo kai kuriose srityse.