Na področju umetne inteligence je evolucijski algoritem (EA) podmnožica izračunov celotne populacije, ki temelji na metahevristični optimizaciji. EA uporablja mehanizme, ki jih navdihuje biološki razvoj, kot so razmnoževanje, mutacija, rekombinacija in selekcija. Kandidatna rešitev v problemu algoritmov evolucijske optimizacije igra vlogo posameznikov v populaciji. In tudi funkcija fitnesa določa kakovost odgovorov.
Evolucijski algoritmi pogosto dobro približajo rešitve vseh vrst problemov. Ker v idealnem primeru ne delajo nobenih predpostavk o osnovni fitnes pokrajini. Metode, ki se uporabljajo za evolucijsko modeliranje in genetske algoritme, so običajno omejene na študije mikroevolucijskih procesov in modelov načrtovanja, ki temeljijo na celičnih fazah. V večini resničnih aplikacij EA je zapletenost računanja previsoka.
Pravzapravto vprašanje je povezano z oceno funkcije fitnesa. Približevanje telesne pripravljenosti je ena od rešitev za premagovanje te težave. Vendar pa lahko na videz preprost EA reši pogosto zapletene probleme. Zato ne more biti neposredne povezave med kompleksnostjo zaporedja in problemom. Več podrobnosti je na voljo v knjigah "Evolucijski algoritmi".
Izvedba
Prvi korak je ustvariti začetno populacijo posameznikov naključno.
Drugi korak je oceniti primernost vsakega posameznika v tej skupini (časovna omejitev, zadostna pripravljenost itd.).
tretji korak - ponovite naslednje korake regeneracije do konca:
- Izberite najprimernejše osebe za vzrejo (starše).
- Pripeljite nove posameznike, ki so prestali evolucijski algoritem z uporabo križanja in mutacije, da dobite potomce.
- Ocenite individualno kondicijo novih ljudi.
- Zamenjajte najmanj primerno populacijo z njimi.
Vrste
Genetski algoritem je evolucijsko zaporedje, najbolj priljubljena vrsta strokovnega svetovalca. Rešitev problema se išče v obliki nizov števil (tradicionalno binarnih, čeprav so najboljše predstavitve običajno tiste, ki bolj odražajo problem, ki se rešuje) z uporabo operatorjev, kot sta rekombinacija in mutacija (včasih ena, v nekaterih primerih oba). Ta vrsta strokovnega svetovalca se pogosto uporablja pri optimizacijskih težavah. Drugo ime za to je fetura (iz latinščine za "rojstvo"):
- Genetsko programiranje. Rešitve predstavlja kot računalniške kode, njihovo primernost pa določa njihova sposobnost izvajanja računskih nalog.
- Evolucijsko programiranje. Podobno evolucijskemu genetskemu algoritmu, vendar je struktura fiksna in njeni številčni parametri se lahko spremenijo.
- Programiranje genske ekspresije. Razvija računalniške aplikacije, vendar raziskuje sistem genotip-fenotip, kjer so projekti različnih velikosti kodirani na linearnih kromosomih s fiksno dolžino.
- Strategija. Deluje z vektorji realnih števil kot predstavitvami rešitev. Običajno uporablja samoprilagodljive algoritme stopnje evolucijske mutacije.
- Diferencialni razvoj. Temelji na vektorskih razlikah in je zato primeren predvsem za probleme numerične optimizacije.
- Nevroevolucija. Podobno kot pri evolucijskem programiranju in genetskih algoritmih. Toda slednje so umetne nevronske mreže, ki opisujejo strukturo in težo povezav. Kodiranje genoma je lahko neposredno ali posredno.
Primerjava z biološkimi procesi
Možna omejitev številnih evolucijskih algoritmov je pomanjkanje jasnega razlikovanja med genotipom in fenotipom. V naravi je oplojeno jajčece podvrženo zapletenemu procesu, znanemu kot embriogeneza, da postane zrelo. To posredno kodiranje naj bi naredilo genetsko iskanje bolj zanesljivo (tj. manj verjetno, da bo povzročilo usodne mutacije) in bi lahko izboljšalo tudi sposobnost organizma za razvoj. Takšne posredne (z drugimi besedami,generativna ali razvojna) kodiranja omogočajo tudi evoluciji, da izkorišča pravilnost v okolju.
Zadnje delo v umetni embriogenezi ali razvojnih sistemih poskuša obravnavati ta vprašanja. Pri programiranju genske ekspresije se uspešno raziskuje področje genotip-fenotip, kjer prvo sestavljajo linearni multigenski kromosomi fiksne dolžine, drugo pa iz številnih ekspresijskih dreves ali računalniških programov različnih velikosti in oblik.
Sorodne tehnike
Algoritmi vključujejo:
- Optimizacija kolonij mravlja. Temelji na ideji, da žuželke iščejo hrano tako, da se povezujejo s feromoni in tvorijo poti. Primerno predvsem za kombinatorno optimizacijo in težave z grafom.
- Algoritem korenskega drsnika. Ustvarjalca je navdihnila funkcija rastlinskih korenin v naravi.
- Algoritem za umetne čebelje družine. Na podlagi obnašanja čebel. Predlagana je predvsem za numerično optimizacijo in razširjena za reševanje kombinatornih, omejenih in večobjektivnih problemov. Algoritem čebel temelji na vedenju žuželk pri iskanju hrane. Uporabljen je bil v številnih aplikacijah, kot sta usmerjanje in razporejanje.
- Optimizacija roja delcev - na podlagi idej o obnašanju čred živali. In predvsem primerna za naloge numeričnih procesov.
Druge priljubljene metahevristične metode
- Iskanje lova. Metoda, ki temelji na skupinskem lovu določenih živali, kot so na primer volkovi, kirazdelijo svoje dolžnosti, da obkrožijo plen. Vsak od članov evolucijskega algoritma je na nek način povezan z drugimi. To še posebej velja za vodjo. To je metoda kontinuirane optimizacije, prilagojena kot metoda kombinatornega procesa.
- Išči po meritvah. Za razliko od metahevrističnih metod, ki temeljijo na naravi, algoritem adaptivnega procesa ne uporablja metafore kot svojega glavnega načela. Namesto tega uporablja preprosto zmogljivo metodo, ki temelji na posodabljanju parametra razmerja razsežnosti iskanja pri vsaki ponovitvi. Algoritem Firefly se zgleduje po tem, kako kresnice pritegnejo drug drugega s svojo utripajočo lučjo. To je še posebej uporabno za multimodalno optimizacijo.
- Išči harmonijo. Na podlagi zamisli o obnašanju glasbenikov. V tem primeru so evolucijski algoritmi prava pot za kombinatorno optimizacijo.
- Gaussova prilagoditev. Na podlagi informacijske teorije. Uporablja se za povečanje zmogljivosti in povprečne razpoložljivosti. Primer evolucijskih algoritmov v tej situaciji: entropija v termodinamiki in teoriji informacij.
Memetic
Hibridna metoda, ki temelji na zamisli Richarda Dawkinsa o memu. Običajno ima obliko algoritma, ki temelji na populaciji, v kombinaciji s posameznimi učnimi postopki, ki lahko izvajajo lokalne izboljšave. Poudarja uporabo znanja, specifičnega za problem, in poskuša organizirati drobnozrnatega in globalnega iskanja na sinergističen način.
EvolucijskoAlgoritmi so hevristični pristop k problemom, ki jih ni mogoče zlahka rešiti v polinomskem času, kot so klasično NP-težki problemi in karkoli drugega, kar bi trajalo predolgo za izčrpno obdelavo. Kadar se uporabljajo samostojno, se običajno uporabljajo za kombinatorne probleme. Vendar pa se genetski algoritmi pogosto uporabljajo v tandemu z drugimi metodami, saj delujejo kot hiter način za iskanje več optimalnih izhodišč za delo.
Premisa evolucijskega algoritma (znanega kot svetovalec) je precej preprosta glede na to, da poznate proces naravne selekcije. Vsebuje štiri glavne korake:
- inicializacija;
- izbira;
- genetski operaterji;
- konec.
Vsak od teh korakov približno ustreza določenemu vidiku naravne selekcije in ponuja preproste načine za modularizacijo te kategorije algoritmov. Preprosto povedano, v EA bodo najbolj primerni člani preživeli in se razmnoževali, medtem ko bodo neprimerni člani umrli in ne bodo prispevali k genskemu skladu naslednje generacije.
Inicializacija
Za zagon algoritma morate najprej ustvariti nabor rešitev. Populacija bo vsebovala poljubno število možnih navedb problemov, ki jih pogosto imenujemo člani. Pogosto se generirajo naključno (v okviru omejitev naloge) ali, če je znano nekaj predhodnega znanja, okvirno osredotočene na tisto, kar velja za idealno. Pomembno je, da populacija pokriva širok nabor rešitev,ker je v bistvu genski bazen. Če torej želimo raziskati veliko različnih možnosti znotraj algoritma, si moramo prizadevati za veliko različnih genov.
Izbira
Ko je populacija ustvarjena, je treba njene člane zdaj oceniti glede na funkcijo fitnesa. Funkcija fitnesa prevzame značilnosti člana in poda številčni prikaz tega, kako fit je član. Njihovo ustvarjanje je pogosto lahko zelo težko. Pomembno je najti dober sistem, ki natančno predstavlja podatke. To je zelo specifično za problem. Zdaj je treba izračunati primernost vseh udeležencev in izbrati nekaj najboljših članov.
Funkcije več ciljev
EA je mogoče tudi razširiti za uporabo teh sistemov. To nekoliko oteži postopek, saj namesto identifikacije ene optimalne točke z njihovo uporabo dobimo nabor. Nabor rešitev se imenuje Paretova meja in vsebuje elemente, ki so enako primerni v smislu, da nobena od njih ne prevladuje nad nobeno drugo.
Genetski operaterji
Ta korak vključuje dva podkoraka: križanje in mutacijo. Po izbiri najboljših izrazov (običajno prvih 2, vendar se to število lahko razlikuje), se zdaj uporabljajo za ustvarjanje naslednje generacije v algoritmu. Z uporabo značilnosti izbranih staršev nastajajo novi otroci, ki so mešanica lastnosti. To je lahko pogosto težavno, odvisno od vrste podatkov, običajno pa pri kombinatornih težavahje povsem mogoče mešati in izpisovati veljavne kombinacije.
Zdaj je treba v generacijo uvesti nov genski material. Če tega pomembnega koraka ne storite, se bo znanstvenik zelo hitro zataknil v lokalne skrajnosti in ne bo dosegel optimalnih rezultatov. Ta korak je mutacija in se izvede precej preprosto, tako da se majhen del otrok spremeni na način, da večinoma ne odražajo podskupine genov staršev. Mutacija se običajno pojavi verjetnostno, saj je verjetnost, da jo bo otrok dobil, pa tudi njena resnost določena z porazdelitvijo.
prekinitev
Na koncu se mora algoritem končati. To se običajno zgodi v dveh primerih: bodisi je dosegel določen maksimalni čas izvedbe ali pa je dosegel prag zmogljivosti. Na tej točki je izbrana in vrnjena končna rešitev.
Primer evolucijskih algoritmov
Zdaj, da ponazorimo rezultat tega postopka, morate videti svetovalca v akciji. Da bi to naredili, se lahko spomnimo, kako se je več generacij dinozavrov naučilo hoditi (postopno obvladovati zemljo), optimizirati strukturo svojega telesa in uporabljati mišično moč. Čeprav plazilci zgodnje generacije niso mogli hoditi, jih je svetovalec sčasoma z mutacijo in križanjem razvil v obliko, ki je lahko hodila.
Ti algoritmi postajajo vse bolj pomembni v sodobnem svetu, saj se rešitve, ki temeljijo na njih, vse pogosteje uporabljajo v panogah, kot so digitalni marketing, finance inzdravstvo.
Kje se uporabljajo EA?
Na splošno se evolucijski algoritmi uporabljajo v najrazličnejših aplikacijah, kot so obdelava slik, usmerjanje vozil, optimizacija mobilnih komunikacij, razvoj programske opreme in celo usposabljanje umetnega nevronskega omrežja. Ta orodja so v središču številnih aplikacij in spletnih mest, ki jih ljudje uporabljajo vsakodnevno, vključno z Google Zemljevidi in celo igrami, kot je The Sims. Poleg tega medicinsko področje uporablja EA za pomoč pri kliničnih odločitvah glede zdravljenja raka. Pravzaprav so evolucijski algoritmi tako robustni, da jih je mogoče uporabiti za reševanje skoraj vseh optimizacijskih problemov.
Moorov zakon
Naraščajoča razširjenost EO je posledica dveh glavnih dejavnikov: razpoložljive računalniške moči in kopičenja velikih podatkovnih nizov. Prvo je mogoče opisati z Moorovim zakonom, ki v bistvu pravi, da se količina računalniške moči v računalniku podvoji približno vsaki dve leti. Ta napoved velja že desetletja. Drugi dejavnik se nanaša na vse večjo odvisnost od tehnologije, ki institucijam omogoča, da zberejo neverjetno veliko količino podatkov, kar jim omogoča analiziranje trendov in optimizacijo izdelkov.
Kako lahko evolucijski algoritmi pomagajo tržnikom?
Tržni pogoji se hitro spreminjajo in so zelo konkurenčni. To je vodje trženja prisililo, da tekmujejo za boljše odločanje. Povečanje na voljoračunalniška moč je delavce pripeljala do uporabe EA za reševanje problemov.
Optimizacija konverzij
Eden od glavnih ciljev je povečati število obiskovalcev spletnega mesta. Ta problem se nanaša na optimizacijo števila uporabnikov, ki delajo, kar hoče tržnik. Na primer, če podjetje prodaja prenosne računalnike, je idealno povečati število obiskovalcev spletnega mesta, ki na koncu kupijo izdelek. To je bistvo optimizacije stopnje konverzije.
Eden od presenetljivo pomembnih vidikov je izbira uporabniškega vmesnika. Če spletno oblikovanje ni zelo prijazno do uporabnika, obstajajo tisti, ki na koncu izdelka iz enega ali drugega razloga ne kupijo. Cilj je torej zmanjšati število uporabnikov, ki na koncu ne izvedejo konverzije, kar poveča skupni dobiček.
