Genetski algoritem

Kaj je to

Naravno evolucijo je mogoče prikazati kot igro, v kateri je nagrada za organizem, ki dobro igra igro življenja, prenos genskega materiala na naslednike in nadaljnje preživetje.^[2] V naravni evoluciji je to, kako dobro posameznik deluje, odvisno od tega, s kom sodeluje in s kom tekmuje, pa tudi od okolja. Genetski algoritmi so simulacija naravne selekcije na populaciji kandidatnih rešitev optimizacijskega problema (kromosomov, posameznikov, bitij ali fenotipov).

Kandidate ocenjujemo in križamo, da bi našli dobre rešitve. Takšne rešitve lahko vzamejo veliko časa in človeku niso očitne. Evolucijska faza se začne s populacijo naključno ustvarjenih bitij. V vsaki generaciji se oceni primernost vsakega posameznika v populaciji. Nekateri se naključno izberejo iz trenutne populacije (na podlagi njihove primernosti) in spremenijo (rekombinirajo in po možnosti naključno mutirajo), da se oblikuje nova populacija. S to novo populacijo se cikel ponovi. Algoritem se konča, ko preteče določeno število generacij ali ko je dosežena dobra raven fitnesa populacije. Če se algoritem konča zaradi doseganja največjega števila generacij, to ne pomeni nujno, da je bila dosežena dobra raven fitnesa.

Programiranje tega v računalniku

Psevdokoda je naslednja:

1. Inicializacija: Ustvari se nekaj možnih rešitev; zelo pogosto imajo naključne vrednosti.
2. Ocenjevanje: Funkcija fitnes oceni vsako rešitev; rezultat je število, ki pove, kako dobro ta rešitev rešuje problem.
3. Naslednji koraki se izvajajo, dokler ni izpolnjena zahteva za ustavitev:
1. Izbor: Izberite rešitve/posameznike za naslednjo iteracijo
2. Rekombinacija: Združite izbrane rešitve
3. Mutacija: Naključno spremenite novo ustvarjene rešitve
4. Ocenjevanje: Uporabite funkcijo primernosti, glejte korak 2.
5. Če zahteva za ustavitev ni izpolnjena, ponovno začnite s korakom izbire.

Primer

Zgornji opis je abstrakten. Pomaga konkretni primer.

Aplikacije

Na splošno

Genetski algoritmi so dobri pri reševanju problemov, ki vključujejo načrtovanje urnikov in razporejanje. Uporabljajo se tudi v inženirstvu. Pogosto se uporabljajo za reševanje globalnih optimizacijskih problemov.

Na splošno velja, da so genetski algoritmi lahko uporabni na problemskih področjih, ki imajo zapleteno pokrajino fitnesa, saj je mešanje namenjeno premikanju populacije stran od lokalnih optimumov, v katerih bi lahko obtičal tradicionalni algoritem za vzpenjanje po hribu. Običajno uporabljeni operatorji križanja ne morejo spremeniti nobene enotne populacije. Samo mutacija lahko zagotovi ergodičnost celotnega procesa genetskega algoritma (ki se obravnava kot Markovova veriga).

Primeri problemov, ki jih rešujejo genetski algoritmi, so: zrcala za usmerjanje sončne svetlobe v sončni kolektor, antene za sprejemanje radijskih signalov v vesolju, metode hoje za računalniške figure, optimalno oblikovanje aerodinamičnih teles v kompleksnih pretočnih poljih

Skiena v svojem Priročniku za načrtovanje algoritmov odsvetuje genetske algoritme za katero koli nalogo: "Povsem nenaravno je modelirati aplikacije z genetskimi operatorji, kot sta mutacija in križanje na bitnih nizih. Psevdobiologija dodaja še eno raven zapletenosti med vas in vaš problem. Drugič, genetski algoritmi za netrivialne probleme potrebujejo zelo veliko časa. [...] Analogija z evolucijo - kjer je za pomemben napredek potrebnih [sic] več milijonov let - je lahko precej primerna. [...] Nikoli nisem naletel na problem, pri katerem bi se mi genetski algoritmi zdeli pravi način za reševanje. Poleg tega še nikoli nisem videl nobenih računalniških rezultatov, ki bi me navdušili z uporabo genetskih algoritmov. Za potrebe hevrističnega iskanja se držite simuliranega žarjenja."

Namizne igre

Namizne igre so zelo pomemben del področja genetskih algoritmov, ki se uporabljajo za probleme teorije iger. Veliko zgodnjega dela na področju računalniške inteligence in iger je bilo usmerjeno v klasične družabne igre, kot je tic-tac-toe,^[3] šah in dama.^[4] Namizne igre lahko zdaj v večini primerov računalnik igra na višji ravni kot najboljši ljudje, celo s slepimi izčrpnimi tehnikami iskanja. Go je znana izjema od tega trenda in se je do zdaj upiral strojnim napadom. Najboljši računalniški igralci Go zdaj igrajo na ravni dobrega začetnika.^[5][6] Strategija igre Go naj bi bila v veliki meri odvisna od prepoznavanja vzorcev in ne le od logične analize kot pri šahu in drugih igrah, ki so bolj odvisne od figur. Velik faktor učinkovitega razvejanja, ki je potreben za iskanje kakovostnih rešitev, močno omejuje pogled naprej, ki ga je mogoče uporabiti pri iskanju zaporedja potez.

Računalniške igre

Genetski algoritem se lahko uporablja v računalniških igrah za ustvarjanje umetne inteligence (računalnik igra proti vam). To omogoča bolj realistično igralno izkušnjo; če lahko človeški igralec najde zaporedje korakov, ki vedno vodijo do uspeha, tudi če jih ponovi v različnih igrah, ne more biti več izziva. In obratno, če se lahko učna tehnika, kot je genetski algoritem za stratega, izogne ponavljanju preteklih napak, bo igra imela večjo igralnost.

Genetski algoritmi potrebujejo naslednje dele:

• metoda za predstavitev izziva v smislu rešitve (npr. usmerjanje vojakov v napadu v strateški igri)
• Funkcija primernosti ali vrednotenja za določitev kakovosti primera (npr. merjenje škode, povzročene nasprotniku pri takem napadu).

Funkcija fitnes sprejme mutirano instanco entitete in izmeri njeno kakovost. Ta funkcija je prilagojena problemski domeni. V številnih primerih, zlasti tistih, ki vključujejo optimizacijo kode, je lahko funkcija primernosti preprosto funkcija časovnega usklajevanja sistema. Ko sta genetska predstavitev in funkcija primernosti opredeljena, genetski algoritem instancira začetne kandidate, kot je opisano prej, nato pa jih izboljša s ponavljajočo se uporabo operatorjev mutacije, križanja, inverzije in izbire (kot je opredeljeno glede na problemsko področje).

Omejitve

Uporaba genetskega algoritma ima v primerjavi z drugimi optimizacijskimi algoritmi določene omejitve:

• Ponavljajoče se vrednotenje funkcije primernosti za kompleksne probleme je pogosto najbolj omejujoč segment umetnih evolucijskih algoritmov. Iskanje optimalne rešitve zapletenih problemov pogosto zahteva zelo draga vrednotenja funkcije fitnes. Pri realnih problemih, kot so problemi strukturne optimizacije, lahko ena sama ocena funkcije zahteva od več ur do več dni popolne simulacije. Tipične optimizacijske metode se s takšnimi vrstami problemov ne morejo spopasti. Pogosto je treba uporabiti približek, saj izračun natančne rešitve traja predolgo. Genetski algoritmi včasih kombinirajo različne aproksimacijske modele za reševanje zapletenih realnih problemov.
• Genetskih algoritmov ni mogoče dobro skalirati. To pomeni, da se pri velikem številu elementov, ki so izpostavljeni mutaciji, velikost iskalnega prostora pogosto eksponentno poveča. Zaradi tega je izjemno težko uporabiti to tehniko pri problemih, kot so načrtovanje motorja, hiše ali letala. Če želimo genetske algoritme uporabiti pri takšnih problemih, jih je treba razčleniti na najpreprostejšo možno predstavitev. Zaradi tega vidimo evolucijske algoritme, ki kodirajo zasnove lopatic ventilatorjev namesto motorjev, oblike stavb namesto podrobnih gradbenih načrtov in zračne krivulje namesto zasnov celotnega letala. Drugi problem kompleksnosti je vprašanje, kako zaščititi dele, ki so se razvili kot dobre rešitve, pred nadaljnjo uničujočo mutacijo, zlasti kadar je za njihovo oceno primernosti potrebno, da se dobro kombinirajo z drugimi deli.
• "Boljša" rešitev je le v primerjavi z drugimi rešitvami. Zato merilo za ustavitev ni jasno pri vsakem problemu.
• Pri številnih problemih so genetski algoritmi nagnjeni k zbliževanju k lokalnim optimumom ali celo poljubnim točkam namesto h globalnemu optimumu problema. To pomeni, da algoritem ne "ve", kako žrtvovati kratkoročni fitnes za pridobitev dolgoročnega fitnesa. Verjetnost, da se to zgodi, je odvisna od oblike funkcije fitnesa: pri nekaterih problemih je enostavno najti globalni optimum, pri drugih pa lahko funkcija lažje najde lokalne optime. To težavo lahko zmanjšamo z uporabo drugačne funkcije fitnesa, povečanjem stopnje mutacije ali uporabo tehnik izbire, ki ohranjajo raznoliko populacijo rešitev. Pogosta tehnika za ohranjanje raznolikosti je uporaba "kazni za nišo": vsaki skupini posameznikov z zadostno podobnostjo (radij niše) se doda kazen, ki zmanjša zastopanost te skupine v naslednjih generacijah, kar omogoči, da se v populaciji ohranijo drugi (manj podobni) posamezniki. Vendar ta trik morda ne bo učinkovit, odvisno od pokrajine problema. Druga možna tehnika bi bila, da se del populacije preprosto nadomesti z naključno ustvarjenimi osebki, kadar si je večina populacije preveč podobna. Raznolikost je pri genetskih algoritmih (in genetskem programiranju) pomembna, saj križanje homogene populacije ne prinaša novih rešitev. Pri evolucijskih strategijah in evolucijskem programiranju raznolikost ni bistvena zaradi večjega zanašanja na mutacije.
• Delovanje na dinamičnih podatkovnih nizih je težavno, saj se genomi začnejo zgodaj zbliževati k rešitvam, ki za poznejše podatke morda ne veljajo več. Predlaganih je bilo več metod, kako to odpraviti s povečanjem genetske raznolikosti in preprečevanjem zgodnje konvergence, bodisi s povečanjem verjetnosti mutacije, ko kakovost rešitve pade (t. i. sprožena hipermutacija), bodisi z občasnim uvajanjem povsem novih, naključno ustvarjenih elementov v genski sklad (t. i. naključni priseljenci). Evolucijske strategije in evolucijsko programiranje se lahko ponovno izvajajo s tako imenovano "strategijo vejice", pri kateri se starši ne ohranjajo, novi starši pa se izbirajo samo iz potomcev. To je lahko učinkovitejše pri dinamičnih problemih.
• Genetski algoritmi ne morejo učinkovito reševati problemov, pri katerih je edino merilo primernosti eno samo merilo prav/neprav (kot so problemi odločanja), saj ni načina za konvergenco rešitve (ni hriba, na katerega bi se lahko povzpeli). V teh primerih lahko naključno iskanje najde rešitev enako hitro kot GA. Če pa razmere omogočajo, da se poskus uspeha/neuspeha ponovi in da (morda) dobimo različne rezultate, je razmerje med uspehi in neuspehi primerno merilo primernosti.
• Za določene optimizacijske probleme in primere problemov so lahko drugi optimizacijski algoritmi glede hitrosti konvergence učinkovitejši od genetskih algoritmov. Alternativni in dopolnilni algoritmi vključujejo evolucijske strategije, evolucijsko programiranje, simulirano žarjenje, Gaussovo prilagajanje, vzpenjanje po hribu in inteligenco roja (npr.: optimizacija kolonije mravelj, optimizacija roja delcev) ter metode, ki temeljijo na celoštevilskem linearnem programiranju. Primernost genetskih algoritmov je odvisna od količine znanja o problemu; dobro znani problemi imajo pogosto boljše, bolj specializirane pristope.

Zgodovina

Leta 1950 je Alan Turing predlagal "učni stroj", ki bi deloval vzporedno z načeli evolucije. Računalniška simulacija evolucije se je začela že leta 1954 z delom Nilsa Alla Barricellija, ki je uporabljal računalnik na Inštitutu za napredne študije v Princetonu v New Jerseyju. Njegova objava iz leta 1954 ni bila deležna večje pozornosti. Avstralski kvantitativni genetik Alex Fraser je od leta 1957 objavljal vrsto člankov o simulaciji umetne selekcije organizmov z več lokusi, ki nadzorujejo merljivo lastnost. Od teh začetkov je računalniško simuliranje evolucije s strani biologov postalo pogostejše v zgodnjih šestdesetih letih, metode pa so bile opisane v knjigah Fraserja in Burnella (1970) ter Crosbyja (1973). Fraserjeve simulacije so vključevale vse bistvene elemente sodobnih genetskih algoritmov. Poleg tega je Hans-Joachim Bremermann v šestdesetih letih prejšnjega stoletja objavil vrsto člankov, v katerih je prav tako prevzel populacijo rešitev optimizacijskih problemov, ki je bila podvržena rekombinaciji, mutaciji in selekciji. Bremermannove raziskave so prav tako vključevale elemente sodobnih genetskih algoritmov. Med drugimi pomembnimi zgodnjimi pionirji so tudi Richard Friedberg, George Friedman in Michael Conrad. Številni zgodnji članki so ponovno natisnjeni v Fogel (1998).

Čeprav je Barricelli v svojem delu, o katerem je poročal leta 1963, simuliral razvoj sposobnosti igranja preproste igre, je umetna evolucija postala splošno priznana metoda optimizacije zaradi dela Inga Rechenberga in Hansa-Paula Schwefla v šestdesetih in zgodnjih sedemdesetih letih prejšnjega stoletja - Rechenbergova skupina je lahko z evolucijskimi strategijami reševala zapletene inženirske probleme. Drug pristop je bila tehnika evolucijskega programiranja Lawrencea J. Fogla, ki je bila predlagana za generiranje umetne inteligence. Evolucijsko programiranje je prvotno uporabljalo stroje končnih stanj za napovedovanje okolij, za optimizacijo napovednih logik pa je uporabljalo variacijo in selekcijo. Genetski algoritmi so postali priljubljeni zlasti zaradi dela Johna Hollanda v zgodnjih sedemdesetih letih prejšnjega stoletja, zlasti njegove knjige Adaptation in Natural and Artificial Systems (1975). Njegovo delo je izhajalo iz študij celičnih avtomatov, ki so jih Holland in njegovi študenti izvajali na Univerzi v Michiganu. Holland je predstavil formaliziran okvir za napovedovanje kakovosti naslednje generacije, znan kot Hollandov teorem o shemi. Raziskave na področju generičnih algoritmov so bile večinoma teoretične do sredine osemdesetih let prejšnjega stoletja, ko je v Pittsburghu v Pensilvaniji potekala prva mednarodna konferenca o genetskih algoritmih (The First International Conference on Genetic Algorithms).