U polju vještačke inteligencije, evolucijski algoritam (EA) je podskup proračuna ukupne populacije zasnovan na metaheurističkoj optimizaciji. EA koristi mehanizme inspirisane biološkim razvojem kao što su reprodukcija, mutacija, rekombinacija i selekcija. Kandidatno rješenje u problemu algoritama evolucijske optimizacije igra ulogu pojedinaca u populaciji. A također i fitnes funkcija određuje kvalitet odgovora.
Evolucijski algoritmi često dobro aproksimiraju rješenja svih vrsta problema. Jer idealno bi bilo da ne prave nikakve pretpostavke o osnovnom fitnes pejzažu. Metode koje se koriste za evoluciono modeliranje i genetske algoritme obično su ograničene na proučavanje mikroevolucionih procesa i modele planiranja zasnovane na ćelijskim fazama. U većini stvarnih EA aplikacija, složenost računara je previsoki faktor.
Zapravoovo pitanje je povezano s procjenom funkcije fitnesa. Aproksimacija kondicije jedno je rješenje za prevazilaženje ove poteškoće. Međutim, naizgled jednostavan EA može riješiti često složene probleme. Stoga ne može postojati direktna veza između složenosti niza i problema. Više detalja možete pronaći u knjigama "Evolucijski algoritmi".
Implementacija
Prvi korak je stvaranje početne populacije pojedinaca nasumice.
Korak dva je procijeniti podobnost svakog pojedinca u ovoj grupi (vremensko ograničenje, dovoljna pripremljenost, itd.).
Treći korak - ponovite sljedeće korake regeneracije do završetka:
- Odaberite najpogodnije ljude za uzgoj (roditelje).
- Dovedite nove pojedince koji su prošli evolucijski algoritam koristeći ukrštanje i mutaciju da biste dobili potomstvo.
- Procijenite individualnu sposobnost novih ljudi.
- Zamijenite najmanje prikladnu populaciju njima.
Vrste
Genetički algoritam je evolutivni niz, najpopularniji tip stručnog savjetnika. Rješenje problema se traži u obliku nizova brojeva (tradicionalno binarnih, iako su najbolje reprezentacije obično one koje više odražavaju problem koji se rješava) primjenom operatora kao što su rekombinacija i mutacija (ponekad jedan, u nekim slučajevima oba). Ova vrsta stručnog savjetnika se često koristi u problemima optimizacije. Drugi naziv za ovo je fetura (od latinskog za "rođenje"):
- Genetičko programiranje. Predstavlja rješenja kao kompjuterske kodove, a njihova prikladnost je određena njihovom sposobnošću da izvršavaju računske zadatke.
- Evoluciono programiranje. Slično evolucionom genetskom algoritmu, ali struktura je fiksna i njeni numerički parametri se mogu mijenjati.
- Programiranje ekspresije gena. Razvija kompjuterske aplikacije, ali istražuje sistem genotip-fenotip, gdje su projekti različitih veličina kodirani na linearnim hromozomima fiksne dužine.
- Strategija. Radi sa vektorima realnih brojeva kao reprezentacijama rješenja. Obično koristi samoprilagodljive algoritme brzine evolucije.
- Diferencijalni razvoj. Zasnovan na vektorskim razlikama i stoga prvenstveno pogodan za probleme numeričke optimizacije.
- Neuroevolution. Slično evolucionom programiranju i genetskim algoritmima. Ali potonje su umjetne neuronske mreže, koje opisuju strukturu i težinu veza. Kodiranje genoma može biti direktno ili indirektno.
Poređenje sa biološkim procesima
Moguće ograničenje mnogih evolucijskih algoritama je nedostatak jasne razlike između genotipa i fenotipa. U prirodi, oplođeno jaje prolazi kroz složeni proces poznat kao embriogeneza da bi postalo zrelo. Smatra se da ovo indirektno kodiranje čini genetske pretrage pouzdanijima (tj. manje je vjerovatno da će uzrokovati fatalne mutacije) i može također poboljšati sposobnost organizma da se razvija. Takvi indirektni (drugim riječima,generativna ili razvojna) kodiranja također omogućavaju evoluciji da iskoristi pravilnost u okruženju.
Nedavni rad na umjetnoj embriogenezi ili razvojnim sistemima nastoji riješiti ove probleme. Prilikom programiranja ekspresije gena uspješno se istražuje genotip-fenotipska regija, gdje se prva sastoji od linearnih multigenskih hromozoma fiksne dužine, a druga od mnogih stabala ekspresije ili kompjuterskih programa različitih veličina i oblika.
Srodne tehnike
Algoritmi uključuju:
- Optimizacija kolonije mrava. Zasnovan je na ideji da insekti traže hranu povezujući se s feromonima kako bi formirali staze. Prvenstveno pogodan za kombinatornu optimizaciju i probleme sa grafovima.
- Algoritam korijenskog klizača. Kreator je inspirisan funkcijom korijena biljaka u prirodi.
- Algoritam za vještačke pčelinje zajednice. Zasnovano na ponašanju medonosnih pčela. Prvenstveno je predložen za numeričku optimizaciju i proširen za rješavanje kombinatornih, ograničenih i višeciljnih problema. Pčelinji algoritam se zasniva na ponašanju insekata u potrazi za hranom. Primijenjen je u mnogim aplikacijama kao što su rutiranje i zakazivanje.
- Optimizacija roja čestica - zasnovana na idejama ponašanja životinjskog krda. I prvenstveno pogodan za numeričke procesne zadatke.
Druge popularne metaheurističke metode
- Traženje lova. Metoda zasnovana na grupnom hvatanju određenih životinja, kao što su vukovi, na primjer, kojiraspodijele svoje dužnosti da okruže plijen. Svaki od članova evolucijskog algoritma je na neki način povezan s ostalima. Ovo posebno važi za vođu. Ovo je metoda kontinuirane optimizacije prilagođena kao kombinatorna metoda procesa.
- Traži po mjerama. Za razliku od metaheurističkih metoda zasnovanih na prirodi, algoritam adaptivnog procesa ne koristi metaforu kao svoj glavni princip. Umjesto toga, koristi jednostavnu metodu orijentiranu na performanse zasnovanu na ažuriranju parametra omjera dimenzija pretraživanja pri svakoj iteraciji. Firefly algoritam je inspirisan načinom na koji krijesnice privlače jedna drugu svojim treptavim svjetlom. Ovo je posebno korisno za multimodalnu optimizaciju.
- Tražite harmoniju. Zasnovan na idejama ponašanja muzičara. U ovom slučaju, evolucijski algoritmi su put za kombinatornu optimizaciju.
- Gaussova adaptacija. Zasnovano na teoriji informacija. Koristi se za maksimiziranje performansi i prosječne dostupnosti. Primjer evolucijskih algoritama u ovoj situaciji: entropija u termodinamici i teoriji informacija.
Memetic
Hibridna metoda zasnovana na ideji Richarda Dawkinsa o memu. Obično ima oblik algoritma zasnovanog na populaciji u kombinaciji sa individualnim procedurama učenja koje mogu da izvrše lokalna poboljšanja. Naglašava korištenje specifičnog znanja o problemu i pokušava organizirati detaljna i globalna pretraživanja na sinergijski način.
Evolucionarnoalgoritmi su heuristički pristup problemima koji se ne mogu lako riješiti u polinomskom vremenu, kao što su klasični NP-teški problemi i bilo šta drugo za koje bi bilo potrebno predugo za iscrpnu obradu. Kada se koriste samostalno, obično se koriste za kombinatorne probleme. Međutim, genetski algoritmi se često koriste u tandemu s drugim metodama, djelujući kao brz način za pronalaženje više optimalnih početnih mjesta za rad.
Premisa evolucijskog algoritma (poznatog kao savjetnik) je prilično jednostavna s obzirom da ste upoznati s procesom prirodne selekcije. Sadrži četiri glavna koraka:
- inicijalizacija;
- izbor;
- genetski operatori;
- kraj.
Svaki od ovih koraka otprilike odgovara određenom aspektu prirodne selekcije i pruža jednostavne načine za modularizaciju te kategorije algoritama. Jednostavno rečeno, u EA, najsposobniji članovi će preživjeti i razmnožavati se, dok će nepodobni članovi umrijeti i neće doprinijeti genetskom fondu sljedeće generacije.
Inicijalizacija
Da biste pokrenuli algoritam, prvo morate kreirati skup rješenja. Populacija će sadržavati proizvoljan broj mogućih iskaza problema, koji se često nazivaju članovima. Često se generišu nasumično (unutar ograničenja zadatka) ili, ako je poznato neko prethodno znanje, probno se koncentrišu oko onoga što se smatra idealnim. Važno je da stanovništvo pokrije širok spektar rješenja,jer je u suštini genetski fond. Stoga, ako neko želi da istraži mnoge različite mogućnosti unutar algoritma, treba težiti tome da ima mnogo različitih gena.
Izbor
Kada je populacija stvorena, njeni članovi sada moraju biti procijenjeni prema funkciji fitnesa. Funkcija fitnesa uzima karakteristike člana i daje numerički prikaz koliko je član fit. Njihovo stvaranje često može biti veoma teško. Važno je pronaći dobar sistem koji tačno predstavlja podatke. Ovo je vrlo specifično za problem. Sada je potrebno izračunati podobnost svih učesnika i odabrati neke od najboljih članova.
Funkcije višestrukih ciljeva
EA se također mogu proširiti na korištenje ovih sistema. Ovo donekle komplikuje proces, jer umjesto identifikacije jedne optimalne tačke, prilikom njihove upotrebe dobija se skup. Skup rješenja naziva se Pareto granica i sadrži elemente koji su podjednako prikladni u smislu da nijedno od njih ne dominira ni nad jednim drugim.
Genetski operateri
Ovaj korak uključuje dva pod-koraka: ukrštanje i mutaciju. Nakon odabira najboljih termina (obično prva dva, ali ovaj broj može varirati), oni se sada koriste za kreiranje sljedeće generacije u algoritmu. Primenom karakteristika izabranih roditelja stvaraju se nova deca koja su mešavina kvaliteta. Ovo često može biti teško ovisno o vrsti podataka, ali obično u kombinatornim problemimasasvim je moguće miješati i ispisati valjane kombinacije.
Sada je potrebno uvesti novi genetski materijal u generaciju. Ako se ne preduzme ovaj važan korak, naučnik će vrlo brzo zaglaviti u lokalnim ekstremima i neće dobiti optimalne rezultate. Ovaj korak je mutacija, i to vrlo jednostavno, mijenjajući mali dio djece na način da oni pretežno ne odražavaju podskupove gena roditelja. Mutacija se obično javlja vjerovatno, jer je vjerovatnoća da će je dijete dobiti, kao i njena ozbiljnost, određena distribucijom.
Raskid
Na kraju, algoritam mora završiti. Ovo se obično dešava u dva slučaja: ili je dostiglo neko maksimalno vreme izvršenja, ili je dostiglo prag performansi. U ovom trenutku, konačno rješenje je odabrano i vraćeno.
Primjer evolucijskih algoritama
Sada, da biste ilustrirali rezultat ovog procesa, morate vidjeti savjetnika u akciji. Da bismo to učinili, možemo se prisjetiti kako je nekoliko generacija dinosaura naučilo hodati (postupno savladavajući zemlju), optimizirajući strukturu svog tijela i primjenjujući snagu mišića. Iako gmizavci rane generacije nisu mogli hodati, savjetnik ih je mogao evoluirati tokom vremena kroz mutaciju i ukrštanje u oblik koji može hodati.
Ovi algoritmi postaju sve relevantniji u modernom svijetu, jer se rješenja zasnovana na njima sve više koriste u industrijama kao što su digitalni marketing, finansije izdravstvo.
Gdje se koriste EA?
Šire, evolucijski algoritmi se koriste u širokom spektru aplikacija kao što su obrada slika, usmjeravanje vozila, optimizacija mobilnih komunikacija, razvoj softvera, pa čak i obuka umjetne neuronske mreže. Ovi alati su u srcu mnogih aplikacija i web stranica koje ljudi koriste na dnevnoj bazi, uključujući Google Maps, pa čak i igre poput The Sims. Osim toga, medicinska oblast koristi EA da pomogne u donošenju kliničkih odluka u vezi s liječenjem raka. U stvari, evolucijski algoritmi su toliko robusni da se mogu koristiti za rješavanje gotovo svakog problema optimizacije.
Mooreov zakon
Rastuća prevalencija EO vođena je dvama glavnim faktorima: dostupnom računarskom snagom i akumulacijom velikih skupova podataka. Prvi se može opisati Mooreovim zakonom, koji u suštini kaže da se količina računarske snage u računaru udvostručuje otprilike svake dvije godine. Ovo predviđanje traje decenijama. Drugi faktor se odnosi na sve veće oslanjanje na tehnologiju, koja omogućava institucijama da prikupe nevjerovatno veliku količinu podataka, što im omogućava da analiziraju trendove i optimiziraju proizvode.
Kako evolucijski algoritmi mogu pomoći trgovcima?
Uslovi na tržištu se brzo menjaju i veoma su konkurentni. Ovo je natjeralo marketinške menadžere da se takmiče za bolje donošenje odluka. Povećanje dostupnostiračunarska snaga je navela radnike da koriste EA za rješavanje problema.
Optimizacija konverzije
Jedan od glavnih ciljeva je povećanje broja posetilaca na sajtu. Ovaj problem se svodi na optimizaciju broja korisnika koji rade ono što marketer želi. Na primjer, ako kompanija prodaje prijenosna računala, idealno je povećati broj posjetitelja stranice koji na kraju kupe proizvod. Ovo je suština optimizacije stope konverzije.
Jedan od iznenađujuće važnih aspekata je izbor korisničkog interfejsa. Ako web dizajn nije baš prilagođen korisniku, postoje oni koji na kraju ne kupe proizvod iz ovog ili onog razloga. Cilj je onda smanjiti broj korisnika koji na kraju ne konvertiraju, što povećava ukupni profit.
