Genetinis algoritmas

Kas tai yra

Natūralią evoliuciją galima modeliuoti kaip žaidimą, kuriame gerai žaidžiančiam organizmui atlygis yra genetinės medžiagos perdavimas įpėdiniams ir tolesnis išlikimas.^[2] Natūralioje evoliucijoje individo rezultatai priklauso nuo to, su kuo jis dirba ir su kuo konkuruoja, taip pat nuo aplinkos. Genetiniai algoritmai - tai natūralios atrankos imitavimas optimizavimo uždavinio kandidatų sprendinių (chromosomų, individų, būtybių arba fenotipų) populiacijoje.

Kandidatai vertinami ir kryžminami, siekiant rasti gerus sprendimus. Tokie sprendimai gali užtrukti daug laiko ir žmogui nėra akivaizdūs. Evoliucijos etapas pradedamas nuo atsitiktinai sukurtos būtybių populiacijos. Kiekvienos kartos metu įvertinamas kiekvieno populiacijos individo tinkamumas. Kai kurie atsitiktinai atrenkami iš esamos populiacijos (atsižvelgiant į jų tinkamumą) ir modifikuojami (rekombinuojami ir galbūt atsitiktinai mutuojami), kad būtų suformuota nauja populiacija. Su šia nauja populiacija ciklas kartojasi. Algoritmas baigiamas arba praėjus nustatytam kartų skaičiui, arba pasiekus gerą populiacijos tinkamumo lygį. Jei algoritmas baigėsi dėl to, kad buvo pasiektas didžiausias kartų skaičius, tai nebūtinai reiškia, kad buvo pasiektas geras tinkamumo lygis.

Programavimas kompiuteryje

Pseudokodas yra toks:

1. Inicializacija: Sukuriami kai kurie galimi sprendiniai; labai dažnai jie turi atsitiktines reikšmes.
2. Vertinimas: Taikant tinkamumo funkciją, kiekvienas sprendinys įvertinamas balais; balas yra skaičius, kuris parodo, kaip gerai šis sprendinys išsprendžia problemą.
3. Toliau nurodyti veiksmai atliekami tol, kol įvykdomas reikalavimas sustoti:
1. Atranka: Pasirinkite sprendimus / asmenis kitai iteracijai
2. Rekombinacija: Sujunkite pasirinktus sprendimus
3. Mutacija: Atsitiktinai pakeiskite naujai sukurtus sprendimus
4. Vertinimas: Pritaikykite tinkamumo funkciją, žr. 2 žingsnį.
5. Jei stabdymo reikalavimas neįvykdytas, iš naujo pradėkite atrankos etapą.

Pavyzdys

Šis aprašymas yra abstraktus. Padeda konkretus pavyzdys.

Programos

Apskritai

Genetiniai algoritmai gerai sprendžia tvarkaraščių sudarymo ir planavimo problemas. Jie taip pat taikomi inžinerijoje. Jie dažnai naudojami globalioms optimizavimo problemoms spręsti.

Bendroji taisyklė yra ta, kad genetiniai algoritmai gali būti naudingi problemų srityse, kuriose yra sudėtingas tinkamumo kraštovaizdis, nes maišymas yra skirtas populiacijai atitolinti nuo vietinių optimumų, kuriuose tradicinis kopimo į kalną algoritmas gali įstrigti. Įprastai naudojami kryžminimo operatoriai negali pakeisti jokios vienodos populiacijos. Vien mutacija gali užtikrinti viso genetinio algoritmo proceso (vertinamo kaip Markovo grandinė) ergodiškumą.

Genetiniais algoritmais sprendžiamų uždavinių pavyzdžiai: veidrodžiai, skirti saulės šviesai nukreipti į saulės kolektorių, antenos, skirtos radijo signalams kosmose priimti, kompiuterinių figūrų vaikščiojimo metodai, optimalus aerodinaminių kūnų projektavimas sudėtinguose srauto laukuose.

Savo Algoritmų projektavimo vadove Skiena pataria nenaudoti genetinių algoritmų bet kokiai užduočiai: "Gana nenatūralu modeliuoti programas naudojant tokius genetinius operatorius kaip mutacija ir kryžminimas bitų eilutėse. Pseudobiologija prideda dar vieną sudėtingumo lygį tarp jūsų ir jūsų problemos. Antra, genetiniai algoritmai labai ilgai užtrunka sprendžiant netrivialias problemas. [...] Analogija su evoliucija - kai reikšmingai pažangai reikia [sic] milijonų metų - gali būti gana tinkama. [...] Niekada nesusidūriau su problema, kuriai spręsti genetiniai algoritmai man atrodytų tinkamas būdas. Be to, niekada nemačiau jokių skaičiavimo rezultatų, pateiktų naudojant genetinius algoritmus, kurie man padarytų teigiamą įspūdį. Savo euristinės paieškos vudu poreikiams tenkinti naudokite imituojamą atkaitinimą."

Stalo žaidimai

Stalo žaidimai yra labai svarbi genetinių algoritmų, taikomų žaidimų teorijos problemoms spręsti, srities dalis. Daug ankstyvojo darbo, susijusio su kompiuteriniu intelektu ir žaidimais, buvo skirta klasikiniams stalo žaidimams, tokiems kaip tik-tak-taka,^[3] šachmatai ir šaškės.^[4] Dabar daugeliu atvejų stalo žaidimus kompiuteris gali žaisti aukštesniu lygiu nei geriausi žmonės, net ir naudodamas aklos išsamios paieškos metodus. Go yra pastebima šios tendencijos išimtis ir iki šiol buvo atsparus mašinų atakoms. Geriausi Go kompiuteriniai žaidėjai dabar žaidžia gero naujoko lygiu.^[5][6] Teigiama, kad Go strategija labai priklauso nuo modelių atpažinimo, o ne tik nuo loginės analizės, kaip šachmatų ir kitų nuo figūrų labiau nepriklausomų žaidimų atveju. Didžiulis efektyvus šakojimo koeficientas, reikalingas kokybiškiems sprendimams rasti, labai apriboja ėjimų sekos paieškos galimybę.

Kompiuteriniai žaidimai

Genetinis algoritmas gali būti naudojamas kompiuteriniuose žaidimuose dirbtiniam intelektui sukurti (kompiuteris žaidžia prieš jus). Tai leidžia sukurti tikroviškesnę žaidimo patirtį; jei žmogus žaidėjas gali rasti veiksmų seką, kuri visada veda į sėkmę net ir kartojant skirtinguose žaidimuose, gali nelikti jokio iššūkio. Ir atvirkščiai, jei mokymosi metodas, pavyzdžiui, genetinis algoritmas strategui gali padėti išvengti praeities klaidų kartojimo, žaidimas turės daugiau galimybių žaisti.

Genetiniams algoritmams reikalingos šios dalys:

• metodas, skirtas iššūkiui atvaizduoti sprendžiant uždavinį (pvz., karių nukreipimas puolimo metu strateginiame žaidime).
• tinkamumo arba vertinimo funkcija, skirta nustatyti atvejo kokybę (pvz., žalos, padarytos priešininkui per tokią ataką, matas).

Tinkamumo funkcija priima mutuotą esybės atmainą ir matuoja jos kokybę. Ši funkcija pritaikoma prie problemos srities. Daugeliu atvejų, ypač susijusių su kodo optimizavimu, tinkamumo funkcija gali būti tiesiog sistemos laiko funkcija. Apibrėžus genetinį atvaizdavimą ir tinkamumo funkciją, genetinis algoritmas sukuria pradinius kandidatus, kaip aprašyta anksčiau, o tada tobulina juos pakartotinai taikydamas mutacijos, kryžminimo, inversijos ir atrankos operatorius (apibrėžtus pagal probleminę sritį).

Apribojimai

Genetinio algoritmo naudojimas, palyginti su alternatyviais optimizavimo algoritmais, turi tam tikrų apribojimų:

• Pakartotinis tinkamumo funkcijos įvertinimas sprendžiant sudėtingas problemas dažnai yra labiausiai ribojantis dirbtinių evoliucinių algoritmų segmentas. Norint rasti optimalų sudėtingų problemų sprendimą, dažnai reikia atlikti labai brangius tinkamumo funkcijų vertinimus. Sprendžiant realias problemas, pavyzdžiui, struktūrinio optimizavimo problemas, vienai funkcijai įvertinti gali prireikti nuo kelių valandų iki kelių dienų pilno modeliavimo. Įprasti optimizavimo metodai negali susidoroti su tokio tipo problemomis. Dažnai tenka naudoti aproksimaciją, nes tikslaus sprendinio apskaičiavimas užtrunka pernelyg ilgai. Genetiniai algoritmai kartais derina skirtingus aproksimacijos modelius, kad išspręstų sudėtingas realias problemas.
• Genetiniai algoritmai nėra gerai mastelizuojami. Tai reiškia, kad kai mutacijai veikiamų elementų skaičius yra didelis, paieškos erdvės dydis dažnai padidėja eksponentiškai. Dėl to šį metodą labai sunku naudoti sprendžiant tokias problemas, kaip variklio, namo ar lėktuvo projektavimas. Norint genetinius algoritmus naudoti tokioms problemoms spręsti, juos reikia išskaidyti į kuo paprastesnį atvaizdavimą. Dėl šios priežasties evoliuciniais algoritmais koduojami ne variklių, o ventiliatorių menčių projektai, ne detalūs statybų planai, o pastatų formos, ne detalūs statybų planai, ir ne lėktuvų projektai, o aerodinaminės plokštumos. Antroji sudėtingumo problema - klausimas, kaip apsaugoti dalis, kurios evoliucionavo kaip geri sprendimai, nuo tolesnių destruktyvių mutacijų, ypač kai jų tinkamumo įvertinimas reikalauja, kad jos gerai derėtų su kitomis dalimis.
• "Geresnis" sprendimas yra tik lyginant su kitais sprendimais. Todėl ne kiekviename uždavinyje yra aiškus sustojimo kriterijus.
• Sprendžiant daugelį problemų, genetiniai algoritmai yra linkę konverguoti į vietinius optimumus arba net į savavališkus taškus, o ne į visuotinį problemos optimumą. Tai reiškia, kad algoritmas "nemoka" aukoti trumpalaikio tinkamumo, kad gautų ilgalaikį tinkamumą. Tokio reiškinio tikimybė priklauso nuo tinkamumo funkcijos formos: kai kuriose problemose lengva rasti visuotinį optimumą, kitose funkcijai gali būti lengviau rasti vietinį optimumą. Šią problemą galima sumažinti naudojant kitokią tinkamumo funkciją, didinant mutacijos dažnį arba taikant atrankos metodus, kurie palaiko įvairią sprendinių populiaciją. Įprastas metodas įvairovei palaikyti yra "nišos nuobaudos" naudojimas: bet kuriai pakankamo panašumo individų grupei (nišos spindulys) pridedama nuobauda, kuri sumažins tos grupės atstovavimą kitose kartose, leisdama populiacijoje išlaikyti kitus (mažiau panašius) individus. Tačiau ši gudrybė gali būti neveiksminga, priklausomai nuo problemos kraštovaizdžio. Kitas galimas metodas būtų tiesiog pakeisti dalį populiacijos atsitiktinai sugeneruotais individais, kai didžioji populiacijos dalis yra pernelyg panaši viena į kitą. Įvairovė svarbi genetiniuose algoritmuose (ir genetiniame programavime), nes kryžminant vienalytę populiaciją negaunama naujų sprendimų. Evoliucijos strategijose ir evoliuciniame programavime įvairovė nėra labai svarbi, nes labiau pasikliaujama mutacijomis.
• Dinaminių duomenų rinkinių valdymas yra sudėtingas, nes genomai anksti pradeda konverguoti prie sprendimų, kurie gali būti nebetinkami vėlesniems duomenims. Buvo pasiūlyta keletas metodų, kaip tai išspręsti, kaip nors padidinant genetinę įvairovę ir užkertant kelią ankstyvai konvergencijai, didinant mutacijos tikimybę, kai sprendinio kokybė sumažėja (vadinamoji sukelta hipermutacija), arba kartais į genofondą įvedant visiškai naujus, atsitiktinai sukurtus elementus (vadinamieji atsitiktiniai imigrantai). Vėlgi evoliucijos strategijos ir evoliucinis programavimas gali būti įgyvendinami taikant vadinamąją "kablelio strategiją", kai tėvai neišlaikomi, o nauji tėvai atrenkami tik iš palikuonių. Tai gali būti veiksmingiau sprendžiant dinamiškas problemas.
• Genetiniai algoritmai negali veiksmingai spręsti uždavinių, kurių vienintelis tinkamumo matas yra vienintelis teisingas/neteisingas matas (pvz., sprendimo uždaviniai), nes nėra būdo konverguoti prie sprendinio (nėra kalno, į kurį reikėtų lipti). Tokiais atvejais atsitiktinė paieška gali rasti sprendimą taip pat greitai kaip ir GA. Tačiau jei situacija leidžia pakartoti sėkmės / nesėkmės bandymą ir gauti (galbūt) skirtingus rezultatus, tuomet sėkmių ir nesėkmių santykis yra tinkamas tinkamumo matas.
• Konkrečioms optimizavimo problemoms ir problemų atvejams kiti optimizavimo algoritmai gali būti efektyvesni už genetinius algoritmus konvergencijos greičio požiūriu. Alternatyvūs ir papildantys algoritmai yra evoliucijos strategijos, evoliucinis programavimas, imituojamas atkaitinimas, Gauso adaptacija, kopimas į kalną, rojaus intelektas (pvz., skruzdžių kolonijų optimizavimas, dalelių rojaus optimizavimas) ir metodai, pagrįsti sveikųjų skaičių tiesiniu programavimu. Genetinių algoritmų tinkamumas priklauso nuo žinių apie problemą apimties; gerai žinomoms problemoms spręsti dažnai taikomi geresni, labiau specializuoti metodai.

Istorija

1950 m. Alanas Tiuringas (Alan Turing) pasiūlė "mokymosi mašiną", kuri atitiktų evoliucijos principus. Evoliuciją kompiuteriu imituoti pradėta jau 1954 m., kai Prinstono (Naujojo Džersio valstija) Pažangiųjų studijų institute (Institute for Advanced Study) Nilsas Aalas Barricelis (Nils Aall Barricelli) naudojo kompiuterį. Jo 1954 m. publikacija nebuvo plačiai pastebėta. Nuo 1957 m. australų kiekybinės genetikos specialistas Aleksas Fraseris (Alex Fraser) paskelbė seriją straipsnių apie dirbtinės atrankos modeliavimą organizmų, turinčių kelis lokusus, kontroliuojančius išmatuojamą požymį. Nuo šios pradžios septintojo dešimtmečio pradžioje biologai pradėjo dažniau kompiuteriu modeliuoti evoliuciją, o metodai buvo aprašyti Fraser ir Burnell (1970) ir Crosby (1973) knygose. Fraserio modeliavimuose buvo visi esminiai šiuolaikinių genetinių algoritmų elementai. Be to, XX a. septintajame dešimtmetyje Hansas-Joachimas Bremermannas (Hans-Joachim Bremermann) paskelbė seriją straipsnių, kuriuose taip pat priėmė optimizavimo uždavinių sprendimo populiaciją, kurioje vyksta rekombinacija, mutacija ir atranka. Bremermanno tyrimuose taip pat buvo šiuolaikinių genetinių algoritmų elementų. Kiti verti dėmesio ankstyvieji pradininkai yra Ričardas Friedbergas, Džordžas Friedmanas ir Maiklas Konradas. Daug ankstyvųjų darbų perspausdinta Fogel (1998).

Nors 1963 m. Barricelli savo darbe, apie kurį pranešė 1963 m., imitavo gebėjimo žaisti paprastą žaidimą evoliuciją, dirbtinė evoliucija tapo plačiai pripažintu optimizavimo metodu dėl Ingo Rechenbergo ir Hanso-Paulio Schwefelio darbų septintajame dešimtmetyje ir aštuntojo dešimtmečio pradžioje - Rechenbergo grupė sugebėjo išspręsti sudėtingas inžinerines problemas naudodama evoliucijos strategijas. Kitas metodas buvo Lawrence'o J. Fogelio evoliucinio programavimo metodas, pasiūlytas dirbtiniam intelektui generuoti. Iš pradžių evoliucinis programavimas naudojo baigtinių būsenų mašinas aplinkai prognozuoti, o prognozuojančioms logikoms optimizuoti naudojo variaciją ir atranką. Genetiniai algoritmai ypač išpopuliarėjo dėka Džono Holando (John Holland) darbų aštuntojo dešimtmečio pradžioje, ypač jo knygos Adaptacija natūraliose ir dirbtinėse sistemose (1975 m.). Jo darbas kilo iš ląstelinių automatų tyrimų, kuriuos Hollandas ir jo studentai atliko Mičigano universitete. Hollandas pristatė formalizuotą kitos kartos kokybės prognozavimo sistemą, žinomą kaip Hollando schemos teorema. Iki aštuntojo dešimtmečio vidurio, kai Pitsburge (Pensilvanijos valstija) buvo surengta Pirmoji tarptautinė genetinių algoritmų konferencija, GA tyrimai išliko daugiausia teoriniai.