Ģenētiskais algoritms

Kas tas ir

Dabisko evolūciju var modelēt kā spēli, kurā organisms, kas labi spēlē dzīvības spēli, saņem atlīdzību par sava ģenētiskā materiāla nodošanu saviem pēctečiem un nepārtrauktu izdzīvošanu.^[2] Dabiskajā evolūcijā tas, cik labi indivīds darbojas, ir atkarīgs no tā, ar ko tas sadarbojas un ar ko konkurē, kā arī no vides. Ģenētiskie algoritmi ir dabiskās atlases simulācija optimizācijas problēmas risinājumu kandidātu populācijai (hromosomām, indivīdiem, būtnēm vai fenotipiem).

Kandidāti tiek izvērtēti un krustoti, mēģinot rast labus risinājumus. Šādi risinājumi var aizņemt daudz laika, un tie nav acīmredzami cilvēkam. Evolūcijas fāzi sāk ar nejauši ģenerētu būtņu populāciju. Katrā paaudzē tiek novērtēta katra populācijas indivīda piemērotība. Dažus no pašreizējās populācijas nejauši atlasa (pamatojoties uz to piemērotību) un pārveido (rekombinē un, iespējams, nejauši mutē), lai izveidotu jaunu populāciju. Ar šo jauno populāciju cikls atkārtojas. Algoritms beidzas vai nu pēc tam, kad ir pagājis noteikts paaudžu skaits, vai arī populācijai ir sasniegts labs piemērotības līmenis. Ja algoritms ir beidzies, jo sasniegts maksimālais paaudžu skaits, tas ne vienmēr nozīmē, ka ir sasniegts labs piemērotības līmenis.

Programmēšana datorā

Pseidokods ir šāds:

1. Inicializēšana: Tiek izveidoti daži iespējamie risinājumi; ļoti bieži tiem būs nejaušas vērtības.
2. Novērtēšana: Vērtēšana: Fitnesa funkcija novērtē katru risinājumu; rezultāts ir skaitlis, kas norāda, cik labi šis risinājums atrisina problēmu.
3. Turpmākie soļi tiek veikti, līdz tiek izpildīta prasība apstāties:
1. Atlase: Izvēlieties risinājumus/indivīdus nākamajai iterācijai.
2. Rekombinācija: Apvienojiet izvēlētos risinājumus
3. Mutācija: Jaunradītie risinājumi tiek nejauši mainīti.
4. Novērtēšana: Piemērojiet piemērotības funkciju, skatīt 2. soli.
5. Ja apstāšanās prasība nav izpildīta, sāciet no jauna ar atlases soli.

Piemērs

Iepriekš minētais apraksts ir abstrakts. Palīdz konkrēts piemērs.

Pieteikumi

Kopumā

Ģenētiskie algoritmi ir labi piemēroti tādu problēmu risināšanai, kas ietver laika grafiku sastādīšanu un plānošanu. Tie ir pielietoti arī inženierzinātnēs. Tos bieži izmanto, lai risinātu globālās optimizācijas problēmas.

Ģenētiskie algoritmi var būt noderīgi problēmsfērās, kurās ir sarežģīta fitnesa ainava, jo sajaukšana ir paredzēta populācijas pārvietošanai prom no lokālā optimuma, kurā tradicionālais kalna kāpšanas algoritms var iestrēgt. Parasti izmantotie krustošanas operatori nevar mainīt nevienu viendabīgu populāciju. Mutācija vien var nodrošināt ģenētiskā algoritma kopējā procesa ergodicitāti (uz to skatoties kā uz Markova ķēdi).

Ar ģenētisko algoritmu palīdzību atrisināto problēmu piemēri: spoguļi, kas paredzēti saules gaismas novadīšanai uz saules kolektoru, antenas, kas paredzētas radio signālu uztveršanai kosmosā, pastaigu metodes datora figūrām, aerodinamisko ķermeņu optimāla projektēšana sarežģītos plūsmas laukos.

Savā Algoritmu projektēšanas rokasgrāmatā Skiena iesaka neizmantot ģenētiskos algoritmus jebkuram uzdevumam: "Ir diezgan nedabiski modelēt lietojumus, izmantojot tādus ģenētiskos operatorus kā mutācija un krustošana bitu virknēs. Pseidobioloģija pievieno vēl vienu sarežģītības līmeni starp jums un jūsu problēmu. Otrkārt, ģenētisko algoritmu lietošana netriviālām problēmām aizņem ļoti ilgu laiku. [...] Analoģija ar evolūciju - kur ievērojams progress prasa [sic] miljoniem gadu - var būt diezgan piemērota. [...] Es nekad neesmu saskāries ar problēmu, kurā ģenētiskie algoritmi man šķistu pareizais veids, kā to risināt. Turklāt es nekad neesmu redzējis nekādus skaitļošanas rezultātus, par kuriem būtu ziņots, izmantojot ģenētiskos algoritmus, un kas būtu man atstājuši labvēlīgu iespaidu. Eiristiskās meklēšanas voodoo vajadzībām palieciet pie simulētās atvēlināšanas."

Galda spēles

Galda spēles ir ļoti nozīmīga daļa no ģenētisko algoritmu jomas, ko piemēro spēļu teorijas problēmām. Liela daļa agrīno darbu par skaitļošanas intelektu un spēlēm bija veltīti klasiskajām galda spēlēm, piemēram, tic-tac-toe,^[3] šahs un dambrete.^[4] Valdes spēles tagad vairumā gadījumu dators var spēlēt augstākā līmenī nekā labākie cilvēki, pat izmantojot aklas izsmeļošas meklēšanas metodes. Go ir ievērojams izņēmums no šīs tendences, un līdz šim tā ir izturējusi mašīnu uzbrukumus. Labākie Go datorspēlētāji šobrīd spēlē labā iesācēja līmenī.^[5][6] Tiek uzskatīts, ka Go stratēģija lielā mērā balstās uz rakstu atpazīšanu, nevis tikai uz loģisko analīzi, kā tas ir šahā un citās no figūrām neatkarīgās spēlēs. Augstas kvalitātes risinājumu atrašanai nepieciešamais milzīgais efektīvais sazarojuma koeficients ievērojami ierobežo gājienu secības meklēšanā izmantojamo skatījumu uz priekšu.

Datorspēles

Ģenētisko algoritmu var izmantot datorspēlēs, lai radītu mākslīgo intelektu (dators spēlē pret jums). Tas ļauj iegūt reālistiskāku spēles pieredzi; ja cilvēks spēlētājs var atrast soļu secību, kas vienmēr noved pie panākumiem, pat atkārtojot to dažādās spēlēs, izaicinājumu vairs nevar būt. Un otrādi, ja ar mācīšanās tehniku, piemēram, ģenētisko algoritmu stratēģis var izvairīties no iepriekš pieļauto kļūdu atkārtošanas, spēlei būs lielāka spēlēšanas iespēja.

Ģenētiskajiem algoritmiem nepieciešamas šādas daļas:

• Metode, kā attēlot izaicinājuma risinājumu (piemēram, karavīru novirzīšana uzbrukumā stratēģijas spēlē).
• Fitnesa vai novērtēšanas funkcija, lai noteiktu gadījuma kvalitāti (piemēram, pretiniekam nodarītā kaitējuma mērījums šāda uzbrukuma laikā).

Fitnesa funkcija pieņem mutētu būtnes instanciāciju un mēra tās kvalitāti. Šī funkcija ir pielāgota problēmas domēnam. Daudzos gadījumos, īpaši tajos, kas saistīti ar koda optimizāciju, piemērotības funkcija var būt vienkārši sistēmas laika funkcija. Kad ģenētiskais attēlojums un piemērotības funkcija ir definēti, ģenētiskais algoritms sākotnējos kandidātus instancē, kā aprakstīts iepriekš, un pēc tam uzlabo, atkārtoti piemērojot mutācijas, krustošanas, inversijas un atlases operatorus (kā noteikts atbilstoši problēmas domēnam).

Ierobežojumi

Ģenētiskā algoritma izmantošanai ir ierobežojumi salīdzinājumā ar alternatīviem optimizācijas algoritmiem:

• Atkārtota fitnesa funkcijas novērtēšana sarežģītām problēmām bieži vien ir mākslīgo evolūcijas algoritmu ierobežojošākais segments. Optimālā risinājuma atrašana sarežģītām problēmām bieži prasa ļoti dārgus fitnesa funkciju novērtējumus. Reālās pasaules problēmās, piemēram, strukturālās optimizācijas problēmās, vienas funkcijas novērtēšanai var būt nepieciešamas no vairākām stundām līdz pat vairākām dienām pilnīgai simulācijai. Tipiskās optimizācijas metodes nevar tikt galā ar šāda veida problēmām. Bieži vien ir nepieciešams izmantot aproksimāciju, jo precīza risinājuma aprēķināšana aizņem pārāk daudz laika. Ģenētiskie algoritmi dažkārt apvieno dažādus aproksimācijas modeļus, lai atrisinātu sarežģītas reālas problēmas.
• Ģenētiskie algoritmi nav labi mērogojami. Tas nozīmē, ka, ja mutācijai pakļauto elementu skaits ir liels, meklēšanas telpas izmērs bieži vien eksponenciāli palielinās. Tas ārkārtīgi apgrūtina šīs metodes izmantošanu tādu problēmu risināšanā kā dzinēja, mājas vai lidmašīnas projektēšana. Lai ģenētiskos algoritmus varētu izmantot šādām problēmām, tās ir jāsadala pēc iespējas vienkāršākā attēlojumā. Šā iemesla dēļ mēs redzam, ka evolūcijas algoritmi kodē ventilatoru lāpstiņu, nevis dzinēju projektus, ēku formas, nevis detalizētus celtniecības plānus, un aerodinamiskos plaknes, nevis veselu lidaparātu projektus. Otra sarežģītības problēma ir jautājums par to, kā aizsargāt daļas, kas ir attīstījušās, lai attēlotu labus risinājumus, no turpmākām destruktīvām mutācijām, jo īpaši tad, ja to piemērotības novērtējumam nepieciešams, lai tās labi kombinētos ar citām daļām.
• "Labāks" risinājums ir tikai salīdzinājumā ar citiem risinājumiem. Rezultātā apstāšanās kritērijs nav skaidrs katrā problēmā.
• Daudzās problēmās ģenētiskajiem algoritmiem ir tendence konverģēt uz lokālo optimumu vai pat patvaļīgiem punktiem, nevis uz problēmas globālo optimumu. Tas nozīmē, ka algoritms "nezina, kā" upurēt īstermiņa piemērotību, lai iegūtu ilgtermiņa piemērotību. Šādas situācijas iespējamība ir atkarīga no piemērotības funkcijas formas: dažas problēmas ļauj viegli atrast globālo optimumu, citās var būt vieglāk atrast lokālo optimumu. Šo problēmu var mazināt, izmantojot citu fitnesa funkciju, palielinot mutācijas ātrumu vai izmantojot atlases metodes, kas uztur daudzveidīgu risinājumu populāciju. Parasta metode daudzveidības uzturēšanai ir "nišas soda" izmantošana: jebkurai pietiekami līdzīgu indivīdu grupai (nišas rādiusam) tiek pievienots sods, kas samazina šīs grupas pārstāvniecību nākamajās paaudzēs, ļaujot populācijā saglabāt citus (mazāk līdzīgus) indivīdus. Tomēr šis triks var nebūt efektīvs atkarībā no problēmas ainavas. Cits iespējams paņēmiens būtu vienkārši aizstāt daļu populācijas ar nejauši ģenerētiem indivīdiem, ja lielākā daļa populācijas ir pārāk līdzīgi viens otram. Dažādība ir svarīga ģenētiskajos algoritmos (un ģenētiskajā programmēšanā), jo viendabīgas populācijas šķērsošana nedod jaunus risinājumus. Evolūcijas stratēģijās un evolucionārajā programmēšanā daudzveidība nav būtiska, jo vairāk paļaujas uz mutāciju.
• Darbība ar dinamiskām datu kopām ir sarežģīta, jo genomi agrīni sāk konverģēt uz risinājumiem, kas vēlākiem datiem var vairs nebūt derīgi. Ir ierosinātas vairākas metodes, kā to novērst, kaut kādā veidā palielinot ģenētisko daudzveidību un novēršot agrīnu konverģenci, vai nu palielinot mutācijas varbūtību, kad risinājuma kvalitāte pazeminās (tā sauktā iedarbinātā hipermutācija), vai arī laiku pa laikam ieviešot genofondu ar pilnīgi jauniem, nejauši ģenerētiem elementiem (tā sauktie nejaušie imigranti). Arī šajā gadījumā evolūcijas stratēģijas un evolucionāro programmēšanu var īstenot ar tā saukto "komata stratēģiju", kurā vecāki netiek uzturēti un jauni vecāki tiek atlasīti tikai no pēcnācējiem. Tā var būt efektīvāka dinamiskām problēmām.
• Ģenētiskie algoritmi nevar efektīvi risināt problēmas, kurās vienīgais piemērotības mērs ir vienīgais pareizais/nepareizais mērs (piemēram, lēmumu problēmas), jo nav iespējams konverģēt uz risinājumu (nav kalna, uz kura kāpt). Šādos gadījumos nejaušā meklēšana var atrast risinājumu tikpat ātri kā GA. Tomēr, ja situācija ļauj atkārtot veiksmes/neveiksmes mēģinājumu, iegūstot (iespējams) atšķirīgus rezultātus, tad veiksmju un neveiksmju attiecība ir piemērots piemērotības mērs.
• Konkrētām optimizācijas problēmām un problēmu gadījumiem citi optimizācijas algoritmi konverģences ātruma ziņā var būt efektīvāki par ģenētiskajiem algoritmiem. Alternatīvie un papildinošie algoritmi ir evolūcijas stratēģijas, evolūcijas programmēšana, simulētā atkurošana, Gausa adaptācija, kāpšana pa kalniem, kā arī saimes intelekts (piemēram: skudru koloniju optimizācija, daļiņu saimes optimizācija) un metodes, kuru pamatā ir integrāla lineārā programmēšana. Ģenētisko algoritmu piemērotība ir atkarīga no problēmas zināšanu apjoma; labi zināmām problēmām bieži vien ir labākas, specializētākas pieejas.

Vēsture

1950. gadā Alans Tjūrings ierosināja "mācīšanās mašīnu", kas darbotos paralēli evolūcijas principiem. Evolūcijas simulācija ar datoru sākās jau 1954. gadā, kad Nils Aals Barricelli (Nils Aall Barricelli) Prinstonas (Ņūdžersija) Padziļināto pētījumu institūtā (Institute for Advanced Study) izmantoja datoru. Viņa 1954. gada publikācija netika plaši pamanīta. Sākot ar 1957. gadu, austrāliešu kvantitatīvās ģenētikas speciālists Alekss Freizers (Alex Fraser) publicēja virkni darbu par mākslīgās atlases simulāciju organismiem ar vairākiem lokiem, kas kontrolē izmērāmu pazīmi. No šiem pirmsākumiem 1960. gadu sākumā bioloģu veiktā evolūcijas simulācija ar datoru kļuva arvien izplatītāka, un šīs metodes tika aprakstītas Frasera un Burnella (1970) un Krosbija (1973) grāmatās. Frasera simulācijās bija iekļauti visi mūsdienu ģenētisko algoritmu būtiskākie elementi. Turklāt 1960. gados Hanss-Joahims Bremermans (Hans-Joachim Bremermann) publicēja virkni darbu, kuros arī tika izmantota optimizācijas problēmu risinājuma populācija, kurā notiek rekombinācija, mutācija un atlase. Arī Bremermaņa pētījumi ietvēra mūsdienu ģenētisko algoritmu elementus. Citu ievērojamu agrīno pionieru vidū ir Ričards Frīdbergs, Džordžs Frīdmans un Maikls Konrāds. Daudzi agrīnie darbi ir pārpublicēti Fogel (1998).

Lai gan Barričelli 1963. gadā publicētajā darbā bija simulējis spēju evolūciju, lai spēlētu vienkāršu spēli, mākslīgā evolūcija kļuva par plaši atzītu optimizācijas metodi, pateicoties Ingo Rechenberga un Hansa Paula Švefela darbam 60. un 70. gadu sākumā - Rechenberga grupa spēja atrisināt sarežģītas inženiertehniskas problēmas, izmantojot evolūcijas stratēģijas. Cita pieeja bija Lorensa J. Fogela (Lawrence J. Fogel) evolūcijas programmēšanas metode, kas tika ierosināta mākslīgā intelekta ģenerēšanai. Evolūcijas programmēšana sākotnēji izmantoja galīgo stāvokļu mašīnas, lai prognozētu vidi, un izmantoja variācijas un atlasi, lai optimizētu prognozēšanas loģiku. Ģenētiskie algoritmi kļuva īpaši populāri, pateicoties Džona Holanda darbiem 70. gadu sākumā un jo īpaši viņa grāmatai Adaptācija dabiskās un mākslīgās sistēmās (1975). Viņa darbs aizsākās ar šūnu automātu pētījumiem, kurus Hollands un viņa studenti veica Mičiganas Universitātē. Holands ieviesa formalizētu sistēmu nākamās paaudzes kvalitātes prognozēšanai, kas pazīstama kā Holanda shēmas teorēma. Ģenētisko algoritmu pētījumi bija galvenokārt teorētiski līdz pat 80. gadu vidum, kad Pitsburgā, Pensilvānijas štatā, notika Pirmā starptautiskā konference par ģenētiskajiem algoritmiem.