A mesterséges intelligencia területén az evolúciós algoritmus (EA) a metaheurisztikus optimalizáláson alapuló teljes populáció számítások egy részhalmaza. Az EA olyan biológiai fejlődés által inspirált mechanizmusokat alkalmaz, mint a szaporodás, a mutáció, a rekombináció és a szelekció. Az evolúciós optimalizálási algoritmusok problémájában a megoldásjelölt az egyedek szerepét tölti be a populációban. És a fitnesz funkció is meghatározza a válaszok minőségét.
Az evolúciós algoritmusok gyakran jól közelítik minden típusú probléma megoldását. Mert ideális esetben nem tesznek feltételezéseket a mögöttes fitneszkörnyezetről. Az evolúciós modellezéshez és a genetikai algoritmusokhoz használt módszerek általában a mikroevolúciós folyamatok vizsgálatára és a sejtszinteken alapuló tervezési modellekre korlátozódnak. A legtöbb valódi EA-alkalmazásban a számítási bonyolultság tiltó tényező.
Tulajdonképpenez a probléma az erőnléti funkció becsléséhez kapcsolódik. A fitnesz közelítése az egyik megoldás ennek a nehézségnek a leküzdésére. Egy látszólag egyszerű EA azonban gyakran összetett problémákat is megoldhat. Ezért nem lehet közvetlen kapcsolat a sorozat összetettsége és a probléma között. További részletek az "Evolúciós algoritmusok" című könyvekben találhatók.
Megvalósítás
Az első lépés az egyedek kezdeti populációjának véletlenszerű létrehozása.
A második lépés az ebbe a csoportba tartozó egyének alkalmasságának felmérése (időkorlát, megfelelő felkészültség stb.).
Harmadik lépés – ismételje meg a következő regenerálási lépéseket a befejezésig:
- Válassza ki a tenyésztésre legalkalmasabb személyeket (szülőket).
- Hozzon új egyedeket, akik átestek az evolúciós algoritmuson keresztezés és mutáció segítségével, hogy utódokat szerezzenek.
- Felmérje fel új emberek egyéni alkalmasságát.
- Cserélje le velük a legkevésbé fitt populációt.
Típusok
A Genetic Algorithm egy evolúciós sorozat, az Expert Advisor legnépszerűbb típusa. A probléma megoldását számsorok formájában keresik (hagyományosan binárisak, bár a legjobb reprezentációk általában azok, amelyek többet tükröznek a megoldandó problémában), olyan operátorok alkalmazásával, mint a rekombináció és a mutáció (néha egy, bizonyos esetekben mindkettő). Az ilyen típusú Expert Advisort gyakran használják optimalizálási problémák esetén. Ennek egy másik neve fetura (a latin "születés" szóból):
- Genetikus programozás. A megoldásokat számítógépes kódként mutatja be, alkalmasságukat pedig a számítási feladatok elvégzésére való képességük határozza meg.
- Evolúciós programozás. Hasonló az evolúciós genetikai algoritmushoz, de a szerkezet rögzített és a numerikus paraméterei változhatnak.
- Génexpresszió programozása. Számítógépes alkalmazásokat fejleszt, de feltárja a genotípus-fenotípus rendszert, ahol a különböző méretű projektek rögzített hosszúságú lineáris kromoszómákon vannak kódolva.
- Stratégia. Valós számok vektoraival dolgozik, mint megoldások reprezentációi. Általában önadaptív evolúciós mutációs ráta algoritmusokat használ.
- Differenciális fejlesztés. Vektorkülönbségeken alapul, ezért elsősorban numerikus optimalizálási feladatokra alkalmas.
- Neuroevolúció. Hasonlóan az evolúciós programozáshoz és a genetikai algoritmusokhoz. Ez utóbbiak azonban mesterséges neurális hálózatok, amelyek leírják a kapcsolatok szerkezetét és súlyát. A genomkódolás lehet közvetlen vagy közvetett.
Összehasonlítás a biológiai folyamatokkal
Sok evolúciós algoritmus lehetséges korlátja a genotípus és a fenotípus közötti egyértelmű különbségtétel hiánya. A természetben a megtermékenyített petesejt az embriogenezisnek nevezett összetett folyamaton megy keresztül, hogy éretté váljon. Úgy gondolják, hogy ez a közvetett kódolás megbízhatóbbá teszi a genetikai kereséseket (azaz kevésbé valószínű, hogy végzetes mutációkat okoz), és javíthatja a szervezet fejlődési képességét is. Az ilyen közvetett (más szóvala generatív vagy fejlesztési) kódolások lehetővé teszik az evolúció számára a környezet szabályszerűségének kihasználását is.
A mesterséges embriogenezissel vagy a fejlesztési rendszerekkel kapcsolatos közelmúltbeli munkák ezekre a problémákra keresnek választ. A génexpresszió programozása során sikeresen feltárjuk a genotípus-fenotípus régiót, ahol az első rögzített hosszúságú lineáris multigén kromoszómákból, a második pedig számos különböző méretű és alakú expressziós fából vagy számítógépes programból áll.
Kapcsolódó technikák
Az algoritmusok a következők:
- Hangyakolónia optimalizálás. Azon az elgondoláson alapul, hogy a rovarok feromonokkal kapcsolódva keresnek táplálékot, hogy utakat alakítsanak ki. Elsősorban kombinatorikus optimalizálásra és gráffeladatokra alkalmas.
- Gyökércsúszka-algoritmus. Az alkotót a növényi gyökerek természetben betöltött funkciója ihlette.
- Algoritmus mesterséges méhcsaládokhoz. A mézelő méhek viselkedése alapján. Elsősorban numerikus optimalizálásra javasolt, és kiterjeszti kombinatorikus, korlátos és többobjektív problémák megoldására. A méhek algoritmusa a rovarok táplálékkeresési viselkedésén alapul. Számos alkalmazásban alkalmazták, például az útválasztásban és az ütemezésben.
- Részecskeraj-optimalizálás – állatállomány viselkedési ötletek alapján. És elsősorban numerikus folyamatfeladatokra alkalmas.
Más népszerű metaheurisztikus módszerek
- Vadászat keresés. Bizonyos állatok, például farkasok csoportos kifogásán alapuló módszer, amelyelosztják feladataikat a zsákmány körül. Az evolúciós algoritmus minden tagja valamilyen módon kapcsolódik a többihez. Ez különösen igaz a vezetőre. Ez egy kombinatorikus folyamatmódszerként adaptált folyamatos optimalizálási módszer.
- Keresés mérések szerint. A természet alapú metaheurisztikus módszerekkel ellentétben az adaptív folyamatalgoritmus nem a metaforát használja fő elvként. Inkább egy egyszerű, teljesítményorientált módszert használ, amely a keresési dimenzióarány paraméter frissítésén alapul minden iterációnál. A Firefly algoritmust az ihlette, hogy a szentjánosbogarak hogyan vonzzák egymást villogó fényükkel. Ez különösen hasznos a multimodális optimalizáláshoz.
- Keresd a harmóniát. A zenészek magatartásának elképzelései alapján. Ebben az esetben az evolúciós algoritmusok jelentik a kombinatorikus optimalizálás útját.
- Gauss adaptáció. Információelmélet alapján. A teljesítmény és az átlagos rendelkezésre állás maximalizálására szolgál. Példa az evolúciós algoritmusokra ebben a helyzetben: entrópia a termodinamikában és az információelméletben.
Memetic
Hibrid módszer Richard Dawkins mémötletén alapul. Általában populáció alapú algoritmus formájában valósul meg, kombinálva olyan egyéni tanulási eljárásokkal, amelyek képesek helyi finomításra. Hangsúlyozza a probléma-specifikus ismeretek felhasználását, valamint a finomszemcsés és globális keresések szinergikus szervezésére tett kísérleteket.
EvolúciósAz algoritmusok olyan problémák heurisztikus megközelítését jelentik, amelyeket nem lehet könnyen megoldani polinomiális időben, mint például a klasszikusan NP-nehéz problémák és bármi más, amelynek kimerítő feldolgozása túl sokáig tartana. Önálló használat esetén általában kombinatorikus problémákra használják őket. A genetikai algoritmusokat azonban gyakran más módszerekkel párhuzamosan alkalmazzák, így gyorsan meg lehet találni több optimális kiindulási helyet a munkához.
Az evolúciós algoritmus (mint tanácsadó) előfeltétele meglehetősen egyszerű, tekintve, hogy Ön ismeri a természetes kiválasztódás folyamatát. Négy fő lépést tartalmaz:
- inicializálás;
- választás;
- genetikai operátorok;
- vége.
E lépések mindegyike nagyjából megfelel a természetes szelekció egy bizonyos aspektusának, és egyszerű módokat kínál az algoritmusok ezen kategóriájának modularizálására. Egyszerűen fogalmazva, az EA-ban a legrátermettebb tagok túlélnek és szaporodnak, míg az alkalmatlanok meghalnak, és nem járulnak hozzá a következő generáció génállományához.
Inicializálás
Az algoritmus elindításához először létre kell hoznia egy megoldáskészletet. A sokaság tetszőleges számú lehetséges problémamegjelentést tartalmaz majd, amelyeket gyakran tagoknak neveznek. Ezeket gyakran véletlenszerűen generálják (a feladat korlátai között), vagy ha ismertek bizonyos előzetes ismereteket, akkor kísérletileg az ideálisnak tartott dolgok köré összpontosulnak. Fontos, hogy a lakosság sokféle megoldást lefedjen,mert lényegében egy génállomány. Ezért, ha valaki egy algoritmuson belül sok különböző lehetőséget akar feltárni, akkor arra kell törekednie, hogy sok különböző génje legyen.
Choice
Miután a sokaság létrejött, a tagjait most ki kell értékelni a fitnesz függvény szerint. A fitnesz függvény figyelembe veszi a tag jellemzőit, és számszerűen ábrázolja a tag fittségét. Létrehozásuk gyakran nagyon nehéz lehet. Fontos egy jó rendszert találni, amely pontosan reprezentálja az adatokat. Ez nagyon specifikus a problémára. Most ki kell számítani az összes résztvevő alkalmasságát, és ki kell választani néhányat a legjobb tagok közül.
Több célfüggvény
Az EA-k ezen rendszerek használatára is kiterjeszthetők. Ez némileg bonyolítja a folyamatot, mert ahelyett, hogy egy optimális pontot azonosítanánk, egy halmazt kapunk használatuk során. A megoldások halmazát Pareto-határnak nevezik, és olyan elemeket tartalmaz, amelyek egyformán alkalmasak abban az értelemben, hogy egyik sem dominál a másikon.
Genetikai operátorok
Ez a lépés két allépést tartalmaz: keresztezést és mutációt. A legjobb kifejezések kiválasztása után (általában az első 2, de ez a szám változhat), most ezek alapján hozzuk létre az algoritmus következő generációját. A kiválasztott szülők sajátosságait alkalmazva új gyerekek születnek, amelyek a tulajdonságok keveréke. Ez gyakran nehéz lehet az adatok típusától függően, de általában kombinatorikus problémák eseténteljesen lehetséges az érvényes kombinációk keverése és kiadása.
Most új genetikai anyagot kell bevinni a generációba. Ha ezt a fontos lépést nem teszik meg, a tudós nagyon gyorsan elakad a helyi szélsőségekben, és nem ér el optimális eredményt. Ez a lépés egy mutáció, és egészen egyszerűen megtörténik, a gyerekek egy kis részét oly módon változtatják meg, hogy azok túlnyomórészt ne tükrözzék a szülők génjeinek részhalmazait. A mutáció általában valószínűségi alapon következik be, mivel annak valószínűségét, hogy egy gyermek megkapja, valamint annak súlyosságát az eloszlás határozza meg.
Felmondás
A végén az algoritmusnak véget kell vetni. Ez általában két esetben fordul elő: vagy elért valamilyen maximális végrehajtási időt, vagy elért egy teljesítményküszöböt. Ezen a ponton a rendszer kiválasztja és visszaadja a végső megoldást.
Példa evolúciós algoritmusokra
A folyamat eredményének szemléltetéséhez látnia kell a tanácsadót működés közben. Ennek érdekében felidézhetjük, hogyan tanult meg a dinoszauruszok több generációja járni (fokozatosan elsajátítani a földet), testük felépítését optimalizálva és izomerőt alkalmazva. Annak ellenére, hogy a korai generációs hüllők nem tudtak járni, a tanácsadó képes volt idővel mutációval és kereszteződéssel olyan formává alakítani őket, amely képes járni.
Ezek az algoritmusok egyre fontosabbá válnak a modern világban, mivel az ezeken alapuló megoldásokat egyre gyakrabban alkalmazzák az olyan iparágakban, mint a digitális marketing, a pénzügy és aegészségügy.
Hol használják az EA-kat?
Tágabb értelemben az evolúciós algoritmusokat sokféle alkalmazásban használják, például képfeldolgozásban, járműútválasztásban, mobilkommunikációs optimalizálásban, szoftverfejlesztésben és még mesterséges neurális hálózatok képzésében is. Ezek az eszközök sok olyan alkalmazás és webhely középpontjában állnak, amelyet az emberek naponta használnak, beleértve a Google Térképet és még az olyan játékokat is, mint a The Sims. Ezenkívül az orvostudomány az EA-t használja a rákkezeléssel kapcsolatos klinikai döntések meghozatalához. Valójában az evolúciós algoritmusok annyira robusztusak, hogy szinte bármilyen optimalizálási probléma megoldására használhatók.
Moore törvénye
Az EO növekvő elterjedését két fő tényező okozza: a rendelkezésre álló számítási teljesítmény és a nagy adatkészletek felhalmozódása. Az elsőt Moore-törvénnyel írhatjuk le, amely lényegében kimondja, hogy egy számítógép számítási teljesítménye körülbelül kétévente megduplázódik. Ez a jóslat évtizedek óta bevált. A második tényező a technológiától való növekvő függőséggel kapcsolatos, amely lehetővé teszi az intézmények számára, hogy hihetetlenül nagy mennyiségű adatot gyűjtsenek össze, ami lehetővé teszi számukra a trendek elemzését és a termékek optimalizálását.
Hogyan segíthetik az evolúciós algoritmusok a marketingeseket?
A piaci feltételek gyorsan változnak, és nagyon versenyképesek. Ez arra kényszerítette a marketingvezetőket, hogy versenyezzenek a jobb döntéshozatalért. A rendelkezésre álló mennyiség növekedésea számítási teljesítmény arra késztette a dolgozókat, hogy az EA-t használják problémamegoldásra.
Konverzióoptimalizálás
Az egyik fő cél az oldal látogatóinak növelése. Ez a probléma abban rejlik, hogy optimalizáljuk azon felhasználók számát, akik azt csinálják, amit a marketinges akar. Például, ha egy cég laptopokat árul, az ideális az, ha növeli azon webhelylátogatók számát, akik végül megvásárolják a terméket. Ez a konverziós arány optimalizálásának lényege.
Az egyik meglepően fontos szempont a felhasználói felület kiválasztása. Ha a webdizájn nem túl felhasználóbarát, van, aki ilyen vagy olyan okból nem veszi meg a terméket. A cél tehát azoknak a felhasználóknak a csökkentése, akik végül nem konvertálnak, ami növeli a teljes nyereséget.
