Genetinis algoritmas GA algoritmas paremtas biologijos žiniomis apie gyvybės evoliuciją GA yra tam tikra klasė naudojant

Genetinis algoritmas (GA) – algoritmas, paremtas biologijos žiniomis apie gyvybės evoliuciją. GA yra tam tikra klasė, naudojanti gamtoje egzistuojančius gyvybės evoliucinius mechanizmus: paveldėjimą, mutaciją, natūraliąją atranką ir . Genetiniai algoritmai yra metodas analizuoti duomenis, jų dėka galima rasti apytikslį užduoties sprendimą. Sprendimas randamas naudojant evoliucinį , 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 , 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ą.

Bendras algoritmas

Pasirenkama pradinė populiacija;
Ciklo pradžia:
Pagal atrankos kriterijų įvertinamas tam tikros dydžio populiacijos individų tinkamumas;
Atrenkami geriausi kandidatai, iš kurių palikuonių bus sudaryta naujoji populiacija;
Atliekama reprodukcija, daromi pakeitimai (mutacijos ir rekombinacijos), gaunama nauja populiacija;
Ciklas kartojamas, jeigu netenkinama nutraukimo sąlyga.

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 , duomenų talpinimo, biudžeto paskirstymo ir kitas svarbias užduotis, kur galima pritaikyti kombinatorinį optimizavimą.

Pritaikymai

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 sritys

Pritaikymo sritys yra labai įvairios ir ne tik tos, kurios buvo paminėtos prieš tai buvusiame skyrelyje. Pateikiama tik dalis dabar egzistuojančių pritaikymų, kadangi jų tikrai daug, GA sparčiai vystosi ir yra pritaikomi naujose srityse.

Dirbtinio intelekto kūryba;
Automatizuotas eskizų, modelių kūrimas (taip pat ir ieškant modeliams), daugiafunkcinių detalių modelių kūrimas automobilių (ir kitose) pramonėje, vertinamas detalių tvirtumas, masės mažinimas ir kitos svarbios charakteristikos;
Žaidimų teorija (karo mokslas);
;
Techninės įrangos kūrimas;
Kriptografija - kodų nulaužimas;
Konteinerio užpildymo optimizavimas;
Vandentiekio ;
Kompiuteriniai tinklai;
;
Failų paskirstymas;
Biologijoje, ląstelių sąveikavimas;
Tvarkaraščių, grafikų sudarymas;
Biudžeto optimizavimas;
;
Keliaujančio pirklio uždavinys;
Elektroninių schemų kūrimas, vadinamosios evoliucionuojančios
Tekstinių dokumentų klasifikacija
Ir daugybė kitų sričių.

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 algoritmas detaliau

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 , 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 individams (sprendiniams) pereiti į naują populiacija nedalyvaujant atrankoje. Š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.

Kryžminimasis

Kryžminimasis (angl. crossover) yra būdas genetiniuose algoritmuose perteikti vienos chromosomos ar kelių chromosomų sandarą į kitą kartą. Ji yra biologinio kryžminimosi analogas.

Yra nemažai kryžminimosi būdų, kurie skirtingai perteikia biologinio kryžminimosi esmę:

Su vienu kryžminimosi tašku. Pasirenkamas rekombinacijos taškas tėvų duomenyse. Vėliau visi „tėvų“ (pav. parents) duomenys, buvę už taško, apkeičiami vietomis. Rezultatas – „vaikai“ (pav. Children), kurie turi dalį vieno ir kito tėvo (genetinių) duomenų.

Su dviem kryžminimosi taškais. Pasirenkami du kryžminimosi taškai tėvų duomenyse. Vėliau visi „tėvų“ duomenys, esantys tarp šių taškų sukeičiami vietomis. Rezultatas – „vaikai“, kurie turi dalį vieno ir kito tėvo duomenų.

„Pjaustymas“ – kryžminimosi technika, kai keičiamas „vaikų“ duomenų ilgis. Skirtumas nuo anksčiau minėtų technikų yra tas, kad čia tėvų duomenyse pasirenkami taškai skirtingose vietose.
Vienodas ir pusiau vienodas kryžminimasis. Abiejų technikų atvejais „tėvų“ duomenų pagrindu sukuriami du nauji „vaikai“. Pirmuoju atveju „tėvų“ duomenys sulyginami tarpusavyje ir sukeičiami vietomis su 50 proc. tikimybe. Pusiau vienodos rekombinacijos atveju sukeičiama vietomis pusė nesutampančių tėvų duomenų.

Proceso nutraukimas

Bendras sprendinių evoliucijos procesas yra cikliškai kartojamas kol pasiekiama nutraukimo sąlyga.

Dažniausios nutraukimo sąlygos: Sprendinys tenkina minimalų kriterijų;

Pasiektas nustatytas generacijų skaičius;
Tam skirtas biudžetas (laikas/pinigai) išnaudotas;
Pasiekta stabili būsena, kai nėra gaunama geresnių sprendinių;
Rankinis sustabdymas, atliekama rezultatų patikrinimas;
Aukščiau minėtų priežasčių kombinacijos.

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ą.

Ankstyvas konvergavimas

Sunkumų iškyla dirbant su dinaminiais duomenų rinkiniais, kai genomai pradeda anksti konverguoti, tokiu būdu nelieka reikalingų duomenų, iš jų sekančių sprendinių kūrimui.

Šiai problema spręsti variantai:

galima padidinti genetinį įvairumą, tokiu būdu bus išvengta ankstyvos konvergencijos,
galima padidinti mutacijos stiprumą, sukeliant vadinamas hipermutacijas (tačiau nukenčia kokybė),
galima retkarčiais įtraukti visiškai naujus, atsitiktinai generuotus, genų fondo elementus (vad. atsitiktiniais imigrantais),
naujausi tyrimai parodė preadaptacijos teikiama naudą sprendžiant šią problemą.

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

(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.

(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.

(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.

(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.

(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.

Literatūra

Fentress, Sam W (2005), Exaptation as a means of evolving complex solutions, MA Thesis, University of Edinburgh. (pdf)
Goldberg, David E (1989), Genetic Algorithms in Search, Optimization and Machine Learning, Kluwer Academic Publishers, Boston, MA.
Goldberg, David E (2002), The Design of Innovation: Lessons from and for Competent Genetic Algorithms, Addison-Wesley, Reading, MA.
Harvey, Inman (1992), Species Adaptation Genetic Algorithms: A basis for a continuing SAGA, in 'Toward a Practice of Autonomous Systems: Proceedings of the First European Conference on Artificial Life', F. J. Varela and P. Bourgine (eds.), MIT Press/Bradford Books, Cambridge, MA, pp. 346-354.
Holland, John H (1975), „Adaptation in Natural and Artificial Systems“, University of Michigan Press, Ann Arbor
Koza, John (1992), Genetic Programming: On the Programming of Computers by Means of Natural Selection
Matthews, Robert A J (1993), The use of genetic algorithms in cryptanalysis, Cryptologia vol 17 187-201
Michalewicz, Zbigniew (1999), Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag.
Mitchell, Melanie, (1996), An Introduction to Genetic Algorithms, MIT Press, Cambridge, MA.
Langdon, W. B., Poli, R. (2002), Foundations of Genetic Programming, Springer-Verlag
Poli, R., Langdon, W. B., McPhee, N. F. (2008), A Field Guide to Genetic Programming, freely available via Lulu.com.
Schmitt, Lothar M (2001), Theory of Genetic Algorithms, Theoretical Computer Science (259), pp. 1-61
Schmitt, Lothar M (2004), Theory of Genetic Algorithms II: models for genetic operators over the string - tensor representation of populations and convergence to global optima for arbitrary fitness function under scaling, Theoretical Computer Science (310), pp. 181-231
Vose, Michael D (1999), The Simple Genetic Algorithm: Foundations and Theory, MIT Press, Cambridge, MA.
Whitley, D. (1994). A genetic algorithm tutorial. Statistics and Computing 4, 65–85.

Nuorodos

JGap – atviro kodo genetinių algoritmų biblioteka.