Evolucijski algoritmi: šta su i čemu služe

Na terenu umjetne 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. Rješenje kandidata u problemu algoritama evolucijske optimizacije igra ulogu pojedinaca u populaciji. A također i fitnes funkcija određuje kvalitetu odgovora.

Evolucijski algoritmi često dobro približavaju rješenja za sve vrste problema. Jer idealno ne prave nikakve pretpostavke o osnovnom fitnes pejzažu. Metode koje se koriste za evolucijsko modeliranje i genetske algoritme obično su ograničene na proučavanje mikroevolucijskih procesa i modele planiranja zasnovane na ćelijskim fazama. U većini aplikacija za Stručne savjetnike u stvarnom svijetu, složenost proračuna je faktor koji zabranjuje.

Zapravo, ovaj problem je vezan za procjenu fitnes funkcije. Aproksimacija fitnesa jedno je od rješenja za prevladavanje ove poteškoće. Međutim, čini se da 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 možete pročitati u knjigama "evolucijski algoritmi".

Implementacija

Prvi korak-stvaranje početne populacije pojedinaca nasumičnim redoslijedom.

Drugi korak-procjena podobnosti svakog pojedinca u ovoj grupi (vremensko ograničenje, dovoljna spremnost,. itd..).

Treći korak - ponavljanje sljedećih tačaka regeneracije do završetka:

1. Odaberite najprikladnije ljude za reprodukciju (roditelji).
2. Za uzgoj novih pojedinaca koji su prošli evolucijski algoritam koristeći crossover i mutaciju za potomstvo.
3. Procijenite individualnu kondiciju novih ljudi.
4. Zamijenite njima najmanje prilagođenu populaciju.

Vrste

Genetski algoritam je evolucijski slijed, najpopularniji tip savjetnika. Tražimo za rješenje problema in oblik žica brojeva (tradicionalno binarni, iako su najbolji prikazi obično oni koji više odražavaju problem koji se rješava) korištenjem operatori kao što su rekombinacija i mutacija (ponekad jedan, u nekim slučajevima oba). Ovaj tip stručni savjetnik se često koristi u zadacima optimizacije. Drugi naziv za ovo je fetura (od latinskog "rođenje"):

1. Genetičko programiranje. U njemu su rješenja predstavljena u obliku računarskih kodova, a njihova prikladnost određena je sposobnošću obavljanja računarskih zadataka.
2. Evolucijsko programiranje. Slično evolucijskom genetičkom algoritmu, ali struktura je fiksna i njegovi numerički parametri se mogu promijeniti.
3. Programiranje ekspresije gena. Razvija kompjuterske aplikacije, ali istražuje sistem genotip-fenotip, gdje su projekti različitih veličina kodirani u linearnim hromozomima fiksne dužine.
4. Strategija. Radi sa vektorima realnih brojeva kao prikazima rješenja. Obično koristi samo-prilagodljive algoritme za evolucijsku stopu mutacija.
5. Diferencijalni razvoj. Kreiran na osnovu vektorskih razlika i stoga je prvenstveno pogodan za probleme numeričke optimizacije.
6. Neuroevolucija. Slično evolucijskom programiranju i genetičkim algoritmima. Ali potonje su vještačke 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žen proces poznat kao embriogeneza da bi sazrelo. Vjeruje se da ovo indirektno kodiranje čini genetsku pretragu pouzdanijom (odnosno smanjuje vjerovatnoću fatalnih mutacija), a također može poboljšati sposobnost tijela da se razvije. Takva indirektna (drugim riječima, generativna ili Razvojna) kodiranja također omogućavaju evoluciji da iskoristi pravilnost u okruženje.

Nedavni rad na polju umjetne embriogeneze ili razvojnih sistema nastoji riješiti ove probleme. Prilikom programiranja ekspresije gena uspješno se istražuje domen genotip-fenotip, gdje se prvi sastoji od linearnih multigenskih hromozoma fiksne dužine, a drugi se sastoji od raznih stabala ekspresije ili kompjuterskih programa različitih veličina i oblika.

Srodne tehnike

Algoritmi uključuju:

1. Optimizacija kolonije mrava. Zasnovan je na idejama traženja hrane od strane insekata koristeći komunikaciju s feromonima za formiranje puteva. Prvenstveno pogodan za kombinatornu optimizaciju i probleme sa grafikom.
2. Algoritam slider-root. Stvoritelj je inspirisan funkcijom biljnog korijena u prirodi.
3. Algoritam vještačkih pčelinjih zajednica. Na osnovu ponašanja medonosnih pčela. Prvenstveno se predlaže za numeričku optimizaciju i proširuje za rješavanje kombinatornih, ograničenih i višenamjenskih problema. Algoritam pčela zasnovan je na ponašanju insekata u potrazi za hranom. Primjenjuje se u mnogim aplikacijama kao što su usmjeravanje i zakazivanje.
4. Optimizacija roja čestica-zasnovana na idejama ponašanja stada životinja. A također je prvenstveno pogodan za numeričke procesne probleme.

Druge metaheurističke metode zasnovane na populaciji

1. Potraga za lovom. Metoda zasnovana na grupnom ribolovu nekih životinja, kao što su, na primjer, vukovi, koji raspoređuju svoje dužnosti da okružuju plijen. Svaki od članova evolucionog algoritma se na neki način odnosi na ostale. Ovo se posebno odnosi na lidera. Ovo je metoda kontinuirane optimizacije prilagođena kao metoda kombinatornog procesa.
2. Traži po dimenzijama. Za razliku od metaheurističkih metoda zasnovanih na prirodi, algoritam adaptivnih procesa ne koristi metaforu kao glavni princip. Umjesto toga, primjenjuje jednostavnu metodu orijentiranu na performanse zasnovanu na ažuriranju parametra omjera dimenzije pretrage pri svakoj iteraciji. Algoritam Firefly inspirisan je ponašanjem krijesnica koje privlače jedna drugu trepćućim svjetlom. Ovo je posebno korisno za multimodalnu optimizaciju.
3. Potraga za harmonijom. Na osnovu ideja ponašanja muzičara. U ovom slučaju, evolucijski algoritmi su metoda koja je pogodna za kombinatornu optimizaciju.
4. Gaussova adaptacija. Na osnovu teorije informacija. Koristi se za maksimiziranje performansi i prosječne kondicije. Primjer evolucijskih algoritama u ovoj situaciji: entropija u termodinamici i teorija informacija.

Memetic

Hibridna metoda zasnovana na ideji Richarda Dawkinsa o memu. Obično ima oblik algoritma zasnovanog na agregatu u kombinaciji sa pojedinačnim procedurama obuke sposobnim za obavljanje lokalnih poboljšanja. Naglašava upotrebu znanja specifičnih za probleme i pokušava da organizuje preciznu i globalnu pretragu na sinergetski način.

Evolucijski algoritmi su heuristički pristup problemima koji se ne mogu lako riješiti u polinomskom vremenu, kao što su klasično NP-teški problemi i sve ostalo što će uzeti previše 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 nekoliko optimalnih početnih mjesta na posao.

Premisa evolucijskog algoritma (poznata kao savjetnik) prilično je jednostavna, s obzirom na to da ste upoznati s procesom prirodne selekcije. Sadrži četiri glavne faze:

• inicijalizacija;
• izbor;
• genetski operatori;
• završetak.

Svaki od ovih koraka otprilike odgovara određenom aspektu prirodne selekcije i pruža jednostavne načine za implementaciju ove kategorije algoritama na modularni način. Jednostavno rečeno, u EA, monteri će preživjeti i reproducirati se, dok će nepodobni članovi umrijeti i neće doprinijeti genskom fondu narednih generacija.

Inicijalizacija

Da biste pokrenuli algoritam, prvo morate stvoriti skup rješenja. Stanovništvo će sadržavati proizvoljan broj mogućih rješenja problema, koja se često nazivaju učesnicima. Često se stvaraju nasumično (u okviru ograničenja zadatka) ili su, ako je poznato neko prethodno znanje, grubo centrirani oko onog koji se smatra idealnim. Važno je da populacija pokriva širok spektar rješenja, jer je to u osnovi genski fond. Stoga, ako je potrebno istražiti mnogo različitih mogućnosti u okviru algoritma, treba nastojati imati mnogo različitih gena.

Boja označenog prostora

Jednom kada se stvori populacija, njene članove sada treba ocjenjivati u skladu sa fitnes funkcijom. Fitnes funkcija poprima karakteristike člana i daje numerički prikaz koliko je održiva. Njihovo stvaranje često može biti veoma teško. Važno je pronaći dobar sistem koji tačno predstavlja podatke. Ovo je veoma specifično za problem. Sada je potrebno izračunati kondiciju svih učesnika i odabrati neke od najboljih članova.

Višestruke ciljne funkcije

Stručni savjetnici se također mogu proširiti za korištenje ovih sistema. Ovo donekle komplikuje proces, jer se, umjesto identifikacije jedne optimalne tačke, dobija skup kada se koristi. Skup rješenja naziva se Pareto granica i sadrži elemente koji su podjednako pogodni u smislu da nijedno od njih ne dominira nijednom drugom.

Genetski operatori

Ovaj korak uključuje dva podkoraka: ukrštanje i mutaciju. Nakon odabira najboljih članova (obično top 2, ali ovaj broj može varirati), oni se sada koriste za kreiranje 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 je u kombinatornim problemima sasvim realno miješati i izlaziti važeće kombinacije.

Sada je potrebno uvesti novi genetski materijal u generaciju. Da ovo važno korak se ne preduzima, naučnik će vrlo brzo zaglaviti u lokalnim ekstremima i neće postići optimalne rezultate. Ovaj korak je mutacija, a to se radi jednostavno promjenom malog dijela djece na takav način da ona pretežno ne odražavaju podskupove gena roditelja. Mutacija se obično javlja vjerovatno, jer mogućnost da je dijete primi, kao i njena težina, određuju se distribucijom.

Prekid

Na kraju bi algoritam trebao prestati. Ovo se obično dešava u dva slučaja: ili je dostiglo neko maksimalno vreme izvršenja, ili prag performansi. U ovoj fazi se bira i vraća konačno rješenje.

Primjer evolucijskih algoritama

Sada, da biste ilustrirali rezultat ovog procesa, morate pogledati stručnog savjetnika u akciji. Da bismo to učinili, možemo se prisjetiti kako je nekoliko generacija dinosaurusa naučilo hodati (postepeno savladavajući zemlju), optimizirajući strukturu svog tijela i primjenjujući snagu mišića. Uprkos činjenici da gmizavci rane generacije nisu mogli hodati, savjetnik ih je uspio evoluirati s vremenom mutacijom i ukrštanjem u oblik sposoban za hodanje.

Ovi algoritmi postaju sve relevantniji u savremenom svijetu, jer se rješenja zasnovana na njima sve više koriste u industrijama kao što su digitalni marketing, finansije i zdravstvo.

Gde se EA koristi?

U širem smislu, evolutivni algoritmi se koriste u veliki izbor aplikacija, kao što su obrada slike, usmjeravanje vozila, optimizacija mobilne komunikacije, , razvoj softvera , pa čak i obuka vještačkih neuronskih mreža. Ovi alati su u središtu mnogih aplikacija i web stranica koje ljudi svakodnevno koriste, uključujući Google mape, pa čak i igre poput the Simsa. Pored toga, medicinska oblast koristi EA za pomoć u donošenju kliničkih odluka u vezi sa lečenjem raka. Zapravo, evolucijski algoritmi su toliko pouzdani da se mogu koristiti za rješavanje gotovo svakog problema optimizacije.

Mooreov zakon

Rastuća prevalencija EO-a je posledica dva glavna faktora: dostupne računarske snage i akumulacije velikih skupova podataka. . Prvi se može opisati Mooreovim Zakonom, koji, zapravo, kaže da se količina računarske snage računara udvostručuje otprilike svake dvije godine. Ova prognoza se održava decenijama. Drugi faktor je povezan sa rastućom zavisnošću od tehnologije, što omogućava institucijama da prikupe neverovatno veliku količinu podataka, što im omogućava da analiziraju trendove i optimizuju proizvode.

Kako evolucijski algoritmi mogu pomoći trgovcima?

Situacija na tržištu se brzo mijenja i veoma je konkurentna. Ovo je primoralo menadžere marketinga da se takmiče za bolje donošenje odluka. Povećanje dostupne računarske snage vodio radnike koristiti EA za rješavanje problema.

Optimizacija konverzije

Jedan od glavnih ciljeva je povećanje stope posjetitelja na sajtu. Ovaj problem se svodi na optimizaciju broja korisnika koji rade ono što marketer želi. Na primer, ako kompanija prodaje laptop računare, idealno je da se poveća broj posetilaca sajta 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 veoma jednostavan za korišćenje, postoje oni koji na kraju ne kupuju proizvod iz jednog ili drugog razloga. Tada je cilj smanjiti broj korisnika koji na kraju ne konvertuju, što povećava ukupni profit.