U području umjetne inteligencije, evolucijski algoritam (EA) je podskup izračuna ukupne populacije na temelju metaheurističke optimizacije. EA koristi mehanizme inspirirane biološkim razvojem kao što su reprodukcija, mutacija, rekombinacija i selekcija. Kandidatno rješenje u problemu algoritama evolucijske optimizacije ima ulogu pojedinaca u populaciji. A također i fitness funkcija određuje kvalitetu odgovora.
Evolucijski algoritmi često dobro približavaju rješenja svih vrsta problema. Jer idealno bi bilo da ne daju nikakve pretpostavke o temeljnom fitness krajoliku. Metode koje se koriste za evolucijsko modeliranje i genetske algoritme obično su ograničene na proučavanje mikroevolucijskih procesa i modele planiranja na temelju staničnih stadija. U većini stvarnih EA aplikacija složenost računanja je previsoki faktor.
Zapravoovo je pitanje povezano s procjenom funkcije fitnessa. Aproksimacija kondicije jedno je rješenje za prevladavanje ove poteškoće. Međutim, naizgled jednostavan EA može riješiti često složene probleme. Stoga ne može postojati izravna veza između složenosti niza i problema. Više detalja možete pronaći u knjigama "Evolucijski algoritmi".
Provedba
Prvi korak je stvaranje početne populacije pojedinaca nasumce.
Drugi korak je procjena prikladnosti svakog pojedinca u ovoj grupi (vremensko ograničenje, dovoljna pripremljenost, itd.).
Treći korak - ponovite sljedeće korake regeneracije do završetka:
- Odaberite najprikladnije osobe za uzgoj (roditelje).
- Dovedite nove pojedince koji su prošli evolucijski algoritam koristeći križanje i mutaciju kako biste dobili potomstvo.
- Procijenite individualnu kondiciju novih ljudi.
- Zamijenite najmanje prikladnu populaciju njima.
Vrste
Genetski algoritam je evolucijski slijed, najpopularnija vrsta stručnog savjetnika. Rješenje problema se traži u obliku nizova brojeva (tradicionalno binarnih, iako su najbolji prikazi obično oni koji 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 često se koristi u problemima optimizacije. Drugi naziv za ovo je fetura (od latinskog za "rođenje"):
- Genetičko programiranje. Predstavlja rješenja kao računalne kodove, a njihovu prikladnost određuje njihova sposobnost obavljanja računalnih zadataka.
- Evolucijsko programiranje. Slično evolucijskom genetskom algoritmu, ali struktura je fiksna i njezini brojčani parametri se mogu mijenjati.
- Programiranje ekspresije gena. Razvija računalne aplikacije, ali istražuje sustav genotip-fenotip, gdje su projekti različitih veličina kodirani na linearnim kromosomima fiksne duljine.
- Strategija. Radi s vektorima realnih brojeva kao prikazima rješenja. Obično koristi samoprilagodljive algoritme brzine evolucije.
- Diferencijalni razvoj. Zasnovan na vektorskim razlikama i stoga prvenstveno pogodan za probleme numeričke optimizacije.
- Neuroevolucija. Slično evolucijskom programiranju i genetskim algoritmima. Ali potonje su umjetne neuronske mreže, koje opisuju strukturu i težinu veza. Kodiranje genoma može biti izravno ili neizravno.
Usporedba s 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 kako bi postalo zrelo. Smatra se da ovo neizravno kodiranje čini genetske pretrage pouzdanijima (tj. manja je vjerojatnost da će uzrokovati fatalne mutacije) i također može poboljšati sposobnost organizma da se razvije. Takvi neizravni (drugim riječima,generativna ili razvojna) kodiranja također omogućuju evoluciji da iskoristi pravilnost u okruženju.
Nedavni rad na umjetnoj embriogenezi ili razvojnim sustavima nastoji riješiti ove probleme. Prilikom programiranja ekspresije gena uspješno se istražuje regija genotip-fenotip, gdje se prva sastoji od linearnih multigenskih kromosoma fiksne duljine, a druga od mnogih stabala ekspresije ili računalnih programa različitih veličina i oblika.
Povezane tehnike
Algoritmi uključuju:
- Optimizacija kolonije mrava. Temelji se na ideji da kukci traže hranu povezujući se s feromonima kako bi formirali putove. Prvenstveno pogodan za kombinatornu optimizaciju i probleme s grafovima.
- Algoritam korijenskog klizača. Kreator je bio inspiriran funkcijom korijena biljaka u prirodi.
- Algoritam za umjetne pčelinje zajednice. Na temelju ponašanja 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 temelji se na ponašanju insekata u potrazi za hranom. Primijenjen je u mnogim aplikacijama kao što su usmjeravanje i zakazivanje.
- Optimizacija roja čestica - na temelju ideja ponašanja životinjskog krda. I također prvenstveno pogodan za numeričke procesne zadatke.
Druge popularne metaheurističke metode
- Traženje lova. Metoda koja se temelji na grupnom hvatanju određenih životinja, kao što su npr. vuk kojiraspodijele svoje dužnosti da okruže plijen. Svaki od članova evolucijskog algoritma na neki je način povezan s ostalima. To posebno vrijedi za vođu. Ovo je metoda kontinuirane optimizacije prilagođena kao metoda kombinatornog procesa.
- Traži po mjerama. Za razliku od metaheurističkih metoda temeljenih na prirodi, algoritam adaptivnog procesa ne koristi metaforu kao svoj glavni princip. Umjesto toga, koristi jednostavnu metodu orijentiranu na performanse koja se temelji na ažuriranju parametra omjera dimenzija pretraživanja pri svakoj iteraciji. Algoritam Firefly inspiriran je načinom na koji krijesnice privlače jedna drugu svojim blještavim svjetlom. Ovo je posebno korisno za multimodalnu optimizaciju.
- Tražite sklad. Na temelju ideja ponašanja glazbenika. U ovom slučaju, evolucijski algoritmi su put za kombinatornu optimizaciju.
- Gaussova adaptacija. Na temelju teorije 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 temeljena na ideji Richarda Dawkinsa o memu. Obično ima oblik algoritma koji se temelji na populaciji u kombinaciji s pojedinačnim postupcima učenja koji mogu izvesti lokalna poboljšanja. Naglašava korištenje znanja specifičnog za problem i pokušava organizirati detaljna i globalna pretraživanja na sinergijski način.
Evolucijskoalgoritmi 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 što drugo za što bi trebalo predugo za iscrpnu obradu. Kada se koriste samostalno, obično se koriste za kombinatorne probleme. Međutim, genetski algoritmi se često koriste zajedno 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) prilično je 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 će najsposobniji članovi 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 stvoriti skup rješenja. Populacija će sadržavati proizvoljan broj mogućih iskaza problema, koji se često nazivaju članovima. Često se generiraju nasumično (unutar ograničenja zadatka) ili, ako je poznato neko prethodno znanje, uvjetno su usredotočeni oko onoga što se smatra idealnim. Važno je da stanovništvo pokriva širok raspon rješenja,jer je u biti genofond. Stoga, ako netko želi istražiti mnoge različite mogućnosti unutar algoritma, treba nastojati imati mnogo različitih gena.
Izbor
Kada je populacija stvorena, njezini članovi sada se moraju procijeniti prema funkciji fitnessa. Funkcija fitnesa uzima karakteristike člana i daje numerički prikaz koliko je član u formi. Njihovo stvaranje često može biti vrlo teško. Važno je pronaći dobar sustav koji točno predstavlja podatke. Ovo je vrlo specifično za problem. Sada je potrebno izračunati podobnost svih sudionika i odabrati neke od najboljih članova.
Funkcije višestrukih ciljeva
EA se također mogu proširiti na korištenje ovih sustava. To donekle komplicira proces, jer umjesto identificiranja jedne optimalne točke, njihovim korištenjem dobiva se skup. Skup rješenja naziva se Pareto granica i sadrži elemente koji su jednako prikladni u smislu da nijedno od njih ne dominira ni nad jednim drugim.
Genetski operatori
Ovaj korak uključuje dva pod-koraka: križanje i mutaciju. Nakon odabira najboljih pojmova (obično prva dva, ali ovaj broj može varirati), oni se sada koriste za stvaranje sljedeće generacije u algoritmu. Primjenom karakteristika odabranih roditelja stvaraju se nova djeca koja su mješavina kvaliteta. To često može biti teško ovisno o vrsti podataka, ali obično u kombinatornim problemimasasvim je moguće miješati i proizvesti valjane kombinacije.
Sada je potrebno uvesti novi genetski materijal u generaciju. Ako se ovaj važan korak ne poduzme, znanstvenik će vrlo brzo zapeti 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 događa probabilistički, budući da je vjerojatnost da će je dijete dobiti, kao i njezina ozbiljnost, određena distribucijom.
Raskid
Na kraju algoritam mora završiti. To se obično događa u dva slučaja: ili je doseglo neko maksimalno vrijeme izvršenja ili je doseglo prag izvedbe. U ovom trenutku odabire se i vraća konačno rješenje.
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 svladavajući zemlju), optimizirajući strukturu svog tijela i primjenjujući snagu mišića. Iako gmazovi rane generacije nisu mogli hodati, savjetnik ih je tijekom vremena uspio evoluirati mutacijom i križanjem u oblik koji može hodati.
Ovi algoritmi postaju sve relevantniji u suvremenom svijetu, jer se rješenja temeljena na njima sve više koriste u industrijama kao što su digitalni marketing, financije 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. Ti su alati u središtu mnogih aplikacija i web-mjesta koje ljudi koriste svakodnevno, uključujući Google Maps, pa čak i igre poput The Sims. Osim toga, medicinsko područje koristi EA za pomoć u donošenju kliničkih odluka u vezi s liječenjem raka. Zapravo, evolucijski algoritmi su toliko robusni da se mogu koristiti za rješavanje gotovo svakog problema optimizacije.
Mooreov zakon
Rastuća prevalencija EO-a potaknuta je dvama glavnim čimbenicima: dostupnom računskom snagom i gomilanjem velikih skupova podataka. Prvi se može opisati Mooreovim zakonom, koji u biti kaže da se količina računalne snage u računalu udvostručuje otprilike svake dvije godine. Ovo predviđanje traje desetljećima. Drugi čimbenik odnosi se na sve veće oslanjanje na tehnologiju, koja institucijama omogućuje prikupljanje nevjerojatno velike količine podataka, što im omogućuje da analiziraju trendove i optimiziraju proizvode.
Kako evolucijski algoritmi mogu pomoći trgovcima?
Tržišni uvjeti se brzo mijenjaju i vrlo su konkurentni. To je natjeralo marketinške menadžere da se natječu za bolje donošenje odluka. Povećanje dostupnihračunalna snaga navela je radnike da koriste EA za rješavanje problema.
Optimizacija konverzije
Jedan od glavnih ciljeva je povećati stopu posjetitelja stranice. Ovaj se problem svodi na optimizaciju broja korisnika koji rade ono što marketer želi. Na primjer, ako tvrtka prodaje prijenosna računala, idealno je povećati broj posjetitelja stranice koji na kraju kupe proizvod. Ovo je bit optimizacije stope konverzije.
Jedan od iznenađujuće važnih aspekata je izbor korisničkog sučelja. Ako web dizajn nije vrlo jednostavan za korištenje, postoje oni koji na kraju ne kupuju proizvod iz ovog ili onog razloga. Cilj je onda smanjiti broj korisnika koji na kraju ne ostvare konverziju, što povećava ukupnu zaradu.
