V oblasti umelej inteligencie je evolučný algoritmus (EA) podmnožinou výpočtov celkovej populácie založenej na metaheuristickej optimalizácii. EA využíva mechanizmy inšpirované biologickým vývojom, ako je reprodukcia, mutácia, rekombinácia a selekcia. Kandidátske riešenie problému evolučných optimalizačných algoritmov zohráva úlohu jednotlivcov v populácii. A tiež fitness funkcia určuje kvalitu odpovedí.
Evolučné algoritmy často dobre aproximujú riešenia všetkých typov problémov. Pretože v ideálnom prípade nerobia žiadne predpoklady o základnej kondícii. Metódy používané na evolučné modelovanie a genetické algoritmy sú zvyčajne obmedzené na štúdium mikroevolučných procesov a plánovacie modely založené na bunkových štádiách. Vo väčšine skutočných aplikácií EA je výpočtová zložitosť obmedzujúcim faktorom.
V skutočnostitento problém súvisí s odhadom fitness funkcie. Kondičná aproximácia je jedným z riešení, ako prekonať tento problém. Zdanlivo jednoduchý EA však dokáže vyriešiť často zložité problémy. Preto nemôže existovať priamy vzťah medzi zložitosťou postupnosti a problémom. Viac podrobností nájdete v knihách "Evolučné algoritmy".
Implementácia
Prvým krokom je vytvorenie počiatočnej populácie náhodne.
Druhým krokom je posúdenie vhodnosti každého jednotlivca v tejto skupine (časový limit, dostatočná pripravenosť atď.).
Tretí krok – dokončenie zopakujte nasledujúce regeneračné kroky:
- Vyberte najvhodnejších ľudí na chov (rodičov).
- Priveďte nových jedincov, ktorí prešli evolučným algoritmom pomocou kríženia a mutácie, aby ste získali potomstvo.
- Posúďte individuálnu zdatnosť nových ľudí.
- Nahradte nimi najmenej zdatnú populáciu.
Typy
Genetický algoritmus je evolučná sekvencia, najobľúbenejší typ odborného poradcu. Riešenie problému sa hľadá vo forme reťazcov čísel (tradične binárnych, aj keď najlepšie reprezentácie sú zvyčajne tie, ktoré viac odrážajú riešený problém) použitím operátorov, ako je rekombinácia a mutácia (niekedy jeden, v niektorých prípadoch oboje).). Tento typ odborného poradcu sa často používa pri problémoch s optimalizáciou. Iný názov je fetura (z latinčiny pre „narodenie“):
- Genetické programovanie. Prezentuje riešenia ako počítačové kódy a ich vhodnosť je určená ich schopnosťou vykonávať výpočtové úlohy.
- Evolučné programovanie. Podobne ako pri evolučnom genetickom algoritme, ale štruktúra je pevná a jej číselné parametre sa môžu meniť.
- Programovanie génovej expresie. Vyvíja počítačové aplikácie, ale skúma systém genotyp-fenotyp, kde sú projekty rôznych veľkostí kódované na lineárnych chromozómoch s pevnou dĺžkou.
- Stratégia. Pracuje s vektormi reálnych čísel ako reprezentáciami riešení. Zvyčajne používa samoprispôsobivé algoritmy rýchlosti evolučnej mutácie.
- Rozdielový rozvoj. Založené na vektorových rozdieloch, a preto vhodné predovšetkým pre numerické optimalizačné problémy.
- Neuroevolúcia. Podobne ako evolučné programovanie a genetické algoritmy. Ale posledné sú umelé neurónové siete, ktoré popisujú štruktúru a váhu spojení. Kódovanie genómu môže byť priame alebo nepriame.
Porovnanie s biologickými procesmi
Možným obmedzením mnohých evolučných algoritmov je nedostatok jasného rozlíšenia medzi genotypom a fenotypom. V prírode prechádza oplodnené vajíčko zložitým procesom známym ako embryogenéza, aby sa stalo zrelým. Predpokladá sa, že toto nepriame kódovanie robí genetické vyhľadávanie spoľahlivejším (t. j. s menšou pravdepodobnosťou spôsobí fatálne mutácie) a môže tiež zlepšiť schopnosť organizmu vyvíjať sa. Takéto nepriame (inými slovami,generatívne alebo vývojové) kódovania tiež umožňujú evolúcii využívať pravidelnosť v prostredí.
Nedávna práca v oblasti umelej embryogenézy alebo vývojových systémov sa snaží riešiť tieto problémy. Pri programovaní génovej expresie sa úspešne skúma genotyp-fenotypová oblasť, kde prvá pozostáva z lineárnych multigénových chromozómov pevnej dĺžky a druhá z mnohých expresných stromov alebo počítačových programov rôznych veľkostí a tvarov.
Súvisiace techniky
Algoritmy zahŕňajú:
- Optimalizácia kolónie mravcov. Je založená na myšlienke, že hmyz hľadá potravu tak, že sa spája s feromónmi a vytvára cestičky. Vhodné predovšetkým pre kombinatorickú optimalizáciu a problémy s grafmi.
- Rootový posuvný algoritmus. Tvorca sa inšpiroval funkciou koreňov rastlín v prírode.
- Algoritmus pre umelé včelstvá. Na základe správania včiel medonosných. Je primárne navrhnutý pre numerickú optimalizáciu a rozšírený na riešenie kombinatorických, ohraničených a viaccieľových problémov. Včelí algoritmus je založený na správaní sa hmyzu pri hľadaní potravy. Používa sa v mnohých aplikáciách, ako je smerovanie a plánovanie.
- Optimalizácia roja častíc – založená na nápadoch na správanie sa stád zvierat. A tiež primárne vhodný pre numerické procesné úlohy.
Iné populárne metaheuristické metódy
- Hľadanie na love. Metóda založená na skupinovom odchyte určitých zvierat, ako sú napríklad vlci, ktorírozdeľujú svoje povinnosti tak, aby obkľúčili korisť. Každý z členov evolučného algoritmu nejakým spôsobom súvisí s ostatnými. To platí najmä pre vodcu. Toto je kontinuálna optimalizačná metóda prispôsobená ako kombinatorická procesná metóda.
- Vyhľadávanie podľa meraní. Na rozdiel od metaheuristických metód založených na prírode, algoritmus adaptívneho procesu nepoužíva metaforu ako svoj hlavný princíp. Skôr používa jednoduchú metódu orientovanú na výkon založenú na aktualizácii parametra pomeru dimenzie vyhľadávania pri každej iterácii. Algoritmus Firefly je inšpirovaný tým, ako sa svetlušky navzájom priťahujú svojim blikajúcim svetlom. Toto je obzvlášť užitočné pri multimodálnej optimalizácii.
- Hľadajte harmóniu. Na základe predstáv o správaní hudobníkov. V tomto prípade sú evolučné algoritmy cestou kombinatorickej optimalizácie.
- Gaussova adaptácia. Na základe teórie informácie. Používa sa na maximalizáciu výkonu a priemernej dostupnosti. Príklad evolučných algoritmov v tejto situácii: entropia v termodynamike a teórii informácie.
Memetic
Hybridná metóda založená na myšlienke mému Richarda Dawkinsa. Zvyčajne má formu algoritmu založeného na populácii v kombinácii s individuálnymi postupmi učenia, ktoré sú schopné vykonávať lokálne spresnenia. Zdôrazňuje využitie znalostí špecifických pre daný problém a pokúša sa synergicky organizovať jemné a globálne vyhľadávania.
EvolučnéAlgoritmy sú heuristickým prístupom k problémom, ktoré sa nedajú ľahko vyriešiť v polynomiálnom čase, ako sú klasicky NP-ťažké problémy a čokoľvek iné, čo by trvalo príliš dlho na úplné spracovanie. Pri samostatnom použití sa zvyčajne používajú na kombinatorické problémy. Genetické algoritmy sa však často používajú v tandeme s inými metódami, čo predstavuje rýchly spôsob, ako nájsť viacero optimálnych východiskových miest pre prácu.
Premisa evolučného algoritmu (známeho ako poradca) je pomerne jednoduchá, keďže poznáte proces prirodzeného výberu. Obsahuje štyri hlavné kroky:
- initialization;
- choice;
- genetické operátory;
- end.
Každý z týchto krokov zhruba zodpovedá určitému aspektu prirodzeného výberu a poskytuje jednoduché spôsoby modularizácie danej kategórie algoritmov. Jednoducho povedané, v EA najschopnejší členovia prežijú a rozmnožia sa, zatiaľ čo nevhodní členovia zomrú a nebudú prispievať do genofondu ďalšej generácie.
Inicializácia
Ak chcete spustiť algoritmus, musíte najskôr vytvoriť súbor riešení. Populácia bude obsahovať ľubovoľný počet možných problémových vyhlásení, často označovaných ako členovia. Často sú generované náhodne (v rámci obmedzení úlohy) alebo, ak sú známe nejaké predchádzajúce znalosti, sú predbežne sústredené okolo toho, čo sa považuje za ideálne. Je dôležité, aby obyvateľstvo pokrývalo širokú škálu riešení,pretože ide v podstate o genofond. Preto, ak chce niekto preskúmať veľa rôznych možností v rámci algoritmu, mal by sa snažiť mať veľa rôznych génov.
Výber
Po vytvorení populácie musia byť jej členovia teraz hodnotení podľa funkcie fitness. Funkcia fitness berie charakteristiky člena a poskytuje číselnú reprezentáciu toho, ako je daný člen fit. Ich vytvorenie môže byť často veľmi ťažké. Je dôležité nájsť dobrý systém, ktorý presne zobrazuje údaje. Toto je veľmi špecifické pre daný problém. Teraz je potrebné vypočítať vhodnosť všetkých účastníkov a vybrať niektorých z najlepších členov.
Funkcie viacerých cieľov
EA môžu byť rozšírené aj na používanie týchto systémov. To trochu komplikuje proces, pretože namiesto identifikácie jedného optimálneho bodu sa pri ich použití získa množina. Súbor riešení sa nazýva Paretova hranica a obsahuje prvky, ktoré sú rovnako vhodné v tom zmysle, že žiadne z nich nedominuje žiadnemu inému.
Genetické operátory
Tento krok zahŕňa dva čiastkové kroky: kríženie a mutáciu. Po výbere najlepších výrazov (zvyčajne prvých 2, ale toto číslo sa môže líšiť) sa teraz použijú na vytvorenie ďalšej generácie v algoritme. Aplikovaním vlastností vybraných rodičov vznikajú nové deti, ktoré sú zmesou vlastností. To môže byť často ťažké v závislosti od typu údajov, ale zvyčajne v kombinatorických problémochje celkom možné miešať a vytvárať platné kombinácie.
Teraz je potrebné zaviesť do generácie nový genetický materiál. Ak sa tento dôležitý krok neurobí, vedec veľmi rýchlo uviazne v lokálnych extrémoch a nedosiahne optimálne výsledky. Tento krok je mutácia a robí sa celkom jednoducho, mení sa malá časť detí tak, aby prevažne neodrážali podskupiny génov rodičov. Mutácia sa zvyčajne vyskytuje pravdepodobnostne, pretože pravdepodobnosť, že ju dostane dieťa, ako aj jej závažnosť sú určené distribúciou.
Ukončenie
Nakoniec musí algoritmus skončiť. To sa zvyčajne stáva v dvoch prípadoch: buď dosiahol určitý maximálny čas vykonania, alebo dosiahol hranicu výkonu. V tomto bode sa vyberie a vráti konečné riešenie.
Príklad evolučných algoritmov
Na ilustráciu výsledku tohto procesu musíte teraz vidieť poradcu v akcii. K tomu si môžeme pripomenúť, ako sa niekoľko generácií dinosaurov naučilo chodiť (postupne zvládať zem), optimalizovať stavbu svojho tela a uplatňovať svalovú silu. Aj keď plazy ranej generácie nevedeli chodiť, poradca ich časom dokázal vyvinúť mutáciou a krížením do formy, ktorá by mohla chodiť.
Tieto algoritmy sú v modernom svete čoraz relevantnejšie, keďže riešenia na nich založené sa čoraz častejšie používajú v odvetviach, ako je digitálny marketing, financie azdravotníctvo.
Kde sa používajú EA?
Vo všeobecnosti sa evolučné algoritmy používajú v širokej škále aplikácií, ako je spracovanie obrazu, smerovanie vozidiel, optimalizácia mobilnej komunikácie, vývoj softvéru a dokonca aj trénovanie umelých neurónových sietí. Tieto nástroje sú základom mnohých aplikácií a webových stránok, ktoré ľudia denne používajú, vrátane Máp Google a dokonca hier ako The Sims. Okrem toho oblasť medicíny využíva EA na pomoc pri prijímaní klinických rozhodnutí týkajúcich sa liečby rakoviny. V skutočnosti sú evolučné algoritmy také robustné, že ich možno použiť na vyriešenie takmer akéhokoľvek optimalizačného problému.
Mooreov zákon
Rastúca prevalencia EO je spôsobená dvoma hlavnými faktormi: dostupným výpočtovým výkonom a hromadením veľkých súborov údajov. Prvý môže byť opísaný Moorovým zákonom, ktorý v podstate hovorí, že množstvo výpočtového výkonu v počítači sa zdvojnásobí približne každé dva roky. Táto predpoveď platí už desaťročia. Druhý faktor súvisí s rastúcou závislosťou od technológie, ktorá inštitúciám umožňuje zbierať neuveriteľne veľké množstvo údajov, čo im umožňuje analyzovať trendy a optimalizovať produkty.
Ako môžu evolučné algoritmy pomôcť obchodníkom?
Trhové podmienky sa rýchlo menia a sú veľmi konkurenčné. To prinútilo marketingových manažérov súťažiť o lepšie rozhodovanie. Zvýšenie dostupnostivýpočtový výkon viedol pracovníkov k tomu, aby na riešenie problémov používali EA.
Optimalizácia konverzie
Jedným z hlavných cieľov je zvýšiť mieru návštevnosti stránky. Tento problém sa scvrkáva na optimalizáciu počtu používateľov, ktorí robia to, čo chce obchodník. Ak napríklad firma predáva notebooky, ideálne je zvýšiť počet návštevníkov stránky, ktorí si produkt nakoniec kúpia. Toto je podstata optimalizácie konverzného pomeru.
Jedným z prekvapivo dôležitých aspektov je výber používateľského rozhrania. Ak webdizajn nie je príliš užívateľsky prívetivý, nájdu sa aj takí, ktorí si produkt z jedného alebo druhého dôvodu nekúpia. Cieľom je potom znížiť počet používateľov, ktorí nakoniec nekonvertujú, čo zvyšuje celkový zisk.
