Evolúciós algoritmusok: mi ezek és mire szolgálnak

A terület mesterséges intelligencia erődítmények Az evolúciós algoritmus (EA) a teljes populáció számításainak részhalmaza metaheurisztikus optimalizálás alapján. Az EA a biológiai fejlődés által inspirált mechanizmusokat használja, mint például a szaporodás, mutáció, rekombináció és szelekció. A jelölt megoldása az evolúciós optimalizálási algoritmusok problémájában az egyének szerepét játssza a populációban. A fitnesz funkció meghatározza a válaszok minőségét is.

Az evolúciós algoritmusok gyakran jól közelítik meg a megoldásokat minden típusú problémára. Mert ideális esetben nem tesznek feltételezéseket a mögöttes fitnesz tájról. Az evolúciós modellezéshez és a genetikai algoritmusokhoz használt módszerek általában a mikroevolúciós folyamatok tanulmányozására és a sejtfázisokon alapuló tervezési modellekre korlátozódnak. A legtöbb valós szakértői tanácsadó alkalmazásban, a számítások összetettsége olyan tényező, amely tiltja.

Valójában ez a probléma a fitnesz funkció értékeléséhez kapcsolódik. A fitnesz közelítése az egyik megoldás ennek a nehézségnek a leküzdésére. Úgy tűnik azonban, hogy egy egyszerű EA képes megoldani gyakran összetett problémákat. Ezért nem lehet közvetlen kapcsolat a szekvencia összetettsége és a probléma között. Bővebben az "evolúciós algoritmusok"című könyvekben olvashat.

Végrehajtás

Első lépés-az egyének kezdeti populációjának létrehozása véletlenszerű sorrendben.

Második lépés-az egyes személyek alkalmasságának értékelése ebben a csoportban (határidő, megfelelő felkészültség,. stb..).

Harmadik lépés-a következő regenerációs pontok ismétlése a befejezésig:

1. Válassza ki a reprodukcióhoz legmegfelelőbb embereket (szülők).
2. Új egyedek tenyésztése, akik átmentek az evolúciós algoritmuson crossover és mutáció segítségével, hogy utódokat kapjanak.
3. Értékelje az új emberek egyéni alkalmasságát.
4. Cserélje ki velük a legkevésbé alkalmazkodó populációt.

Típusok

A genetikai algoritmus evolúciós szekvencia, a legnépszerűbb tanácsadó típus. Keresünk a probléma megoldása érdekében a a húrok formája számok (hagyományosan bináris, bár a legjobb ábrázolások általában azok, amelyek jobban tükrözik a megoldandó problémát) alkalmazásával olyan operátorok, mint a rekombináció és a mutáció (néha egy, egyes esetekben mindkettő). Ez a típus a szakértői tanácsadót gyakran használják az optimalizálási feladatokban. Ennek másik neve a fetura (a Latin "születés"):

1. Genetikai programozás. Ebben a megoldásokat számítógépes kódok formájában mutatják be, alkalmasságukat pedig a számítási feladatok elvégzésének képessége határozza meg.
2. Evolúciós programozás. Hasonló az evolúciós genetikai algoritmushoz, de a szerkezet rögzített, numerikus paraméterei változhatnak.
3. A 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ű projekteket rögzített hosszúságú lineáris kromoszómákban kódolják.
4. Stratégia. Valós számok vektoraival működik, mint megoldások ábrázolása. Általában önadaptív evolúciós mutációs sebesség algoritmusokat használ.
5. Differenciális fejlődés. Vektorkülönbségek alapján készült, ezért elsősorban numerikus optimalizálási problémákra alkalmas.
6. Neuroevolúció. Hasonló az evolúciós programozáshoz és a genetikai algoritmusokhoz. De az utóbbiak mesterséges neurális hálózatok, amelyek leírják a kapcsolatok szerkezetét és súlyát. A genom kódolása lehet közvetlen vagy közvetett.

Összehasonlítás a biológiai folyamatokkal

Számos evolúciós algoritmus lehetséges korlátja a genotípus és a fenotípus közötti egyértelmű különbség hiánya. A természetben a megtermékenyített petesejt éretté válik az embriogenezis néven ismert összetett folyamaton. Úgy gondolják, hogy ez a közvetett kódolás megbízhatóbbá teszi a genetikai keresést (vagyis csökkenti a halálos mutációk valószínűségét), valamint javíthatja a szervezet fejlődési képességét. Az ilyen közvetett (más szóval generatív vagy fejlődési) kódolások lehetővé teszik az evolúció számára a rendszeresség kihasználását is környezet.

A mesterséges embriogenezis vagy a fejlesztési rendszerek területén végzett legújabb munka e problémák megoldására törekszik. A génexpresszió programozásakor sikeresen megvizsgálják a genotípus-fenotípus domént, ahol az első rögzített hosszúságú lineáris multigenikus kromoszómákból áll, a második pedig különféle expressziós fákból vagy különböző méretű és alakú számítógépes programokból áll.

Kapcsolódó technikák

Az algoritmusok a következők:

1. A hangya kolónia optimalizálása. Azon az ötleten alapul, hogy a rovarok élelmet keresnek a feromonokkal való kommunikáció segítségével az utak kialakításához. Elsősorban kombinatorikus optimalizálásra és gráfproblémákra alkalmas.
2. A root Runner algoritmus. Az alkotót a növényi gyökerek funkciója ihlette a természetben.
3. A mesterséges méhcsaládok algoritmusa. A mézelő méhek viselkedése alapján. Elsősorban numerikus optimalizálásra javasolt, és kombinatorikus, korlátozott és többcélú problémák megoldására is kiterjesztették. A méhek algoritmusa a rovarok takarmányozási viselkedésén alapul. Számos alkalmazásban alkalmazták, mint például az Útválasztás és az ütemezés.
4. Részecske Raj optimalizálás-az állatállomány viselkedésének ötletei alapján. Elsősorban numerikus folyamatproblémákra is alkalmas.

Egyéb populációalapú metaheurisztikus módszerek

1. Vadászat keresés. Olyan módszer, amely egyes állatok, például farkasok Csoportos halászatán alapul, akik feladataikat elosztják a zsákmány körül. Az evolúciós algoritmus minden tagja valamilyen módon kapcsolódik a többiekhez. Ez különösen igaz a vezetőre. Ez egy folyamatos optimalizálási módszer, amelyet kombinatorikus folyamat módszereként alkalmaznak.
2. Keresés méretek szerint. A természeten alapuló metaheurisztikus módszerekkel ellentétben az adaptív folyamatok algoritmusa nem metaforát használ fő elvként. Inkább egy egyszerű teljesítményorientált módszert alkalmaz, amely a keresési dimenzióarány paraméter frissítésén alapul minden iterációnál. A Firefly algoritmust a szentjánosbogarak viselkedése ihlette, amelyek villogó fénnyel vonzzák egymást. Ez különösen hasznos a multimodális optimalizáláshoz.
3. A harmónia keresése. A zenészek viselkedésének ötletei alapján. Ebben az esetben az evolúciós algoritmusok olyan módszer, amely alkalmas kombinatorikus optimalizálásra.
4. Gauss-adaptáció. Információelmélet alapján. A teljesítmény és az átlagos fitnesz maximalizálása. 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, amely Richard Dawkins mém ötletén alapul. Általában aggregátum alapú algoritmus formájában valósul meg, kombinálva a helyi finomítások elvégzésére képes egyedi képzési eljárásokkal. Hangsúlyozza a problémaspecifikus ismeretek használatát, és megpróbálja szinergikus módon megszervezni a pontos és globális keresést.

Az evolúciós algoritmusok olyan problémák heurisztikus megközelítését jelentik, amelyeket nem lehet könnyen megoldani polinom időben, mint például a klasszikusan NP-nehéz problémák és bármi más, ami túl sokba kerül a kimerítő feldolgozáshoz. Ha önállóan használják, általában kombinatorikus problémákra használják őket. A genetikai algoritmusokat azonban gyakran más módszerekkel párhuzamosan használják, gyors módja annak, hogy több optimális kiindulási helyet találjanak dolgozni.

Az evolúciós algoritmus (tanácsadó néven ismert) előfeltétele meglehetősen egyszerű, tekintve, hogy ismeri a természetes szelekció folyamatát. Négy fő szakaszból áll:

• inicializálás;
• választás;
• genetikai operátorok;
• Befejezés.

E lépések mindegyike nagyjából megfelel a természetes szelekció bizonyos aspektusainak, és egyszerű módszereket kínál az algoritmusok ezen kategóriájának moduláris megvalósítására. Egyszerűen fogalmazva, az EA-ban a szerelő tagok túlélnek és szaporodnak, míg az alkalmatlan tagok meghalnak, és nem járulnak hozzá a következő generációk génkészletéhez.

Inicializálás

Az algoritmus elindításához először létre kell hoznia egy sor megoldást. A lakosság tetszőleges számú lehetséges megoldást tartalmaz a problémára, gyakran résztvevőknek hívják. Gyakran véletlenszerűen jönnek létre (a feladat korlátain belül), vagy ha valamilyen előzetes tudás ismert, akkor nagyjából az ideálisnak tekintett köré összpontosulnak. Fontos, hogy a populáció a megoldások széles skáláját lefedje, mert lényegében génkészlet. Ezért, ha az algoritmus keretein belül sokféle lehetőséget kell feltárni, arra kell törekedni, hogy sok különböző gén legyen.

Kiválasztás

Miután létrejött egy populáció, tagjait most a fitnesz funkció szerint kell értékelni. A fitness függvény egy tag jellemzőit veszi fel, és számszerűen ábrázolja, hogy mennyire életképes. Ezek létrehozása gyakran nagyon nehéz lehet. Fontos megtalálni egy jó rendszert, amely pontosan képviseli az adatokat. Ez nagyon specifikus a problémára. Most meg kell számítani a fitness minden résztvevő, majd válassza ki néhány, a legjobb tagok.

Több célfunkció

A szakértői tanácsadók ezen rendszerek használatára is kiterjeszthetők. Ez némileg bonyolítja a folyamatot, mert egy optimális pont azonosítása helyett egy készletet kapunk azok használatakor. A megoldások halmazát Pareto határnak nevezzük, és olyan elemeket tartalmaz, amelyek egyformán alkalmasak abban az értelemben, hogy egyikük sem uralja a másikat.

Genetikai operátorok

Ez a lépés két allépést tartalmaz: crossover és mutáció. Miután kiválasztotta a legjobb tagokat (általában a legjobb 2, de ez a szám változhat), most felhasználják őket a következő generáció létrehozására az algoritmusban. A kiválasztott szülők jellemzőinek alkalmazásával új gyermekek jönnek létre, amelyek a tulajdonságok keveréke. Ez az adattípustól függően gyakran nehéz lehet, de kombinatorikus problémák esetén általában reális az érvényes kombinációk keverése és kimenete.

Most új genetikai anyagot kell bevezetni a generációba. Ha ez a fontos a lépés nem történik meg, a tudós nagyon gyorsan elakad a helyi szélsőségekben, és nem fog optimális eredményeket elérni. Ez a lépés egy mutáció, amelyet egyszerűen úgy hajtanak végre, hogy a gyermekek egy kis részét úgy változtatják meg, hogy 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ég szerint fordul elő, 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

Végül az algoritmusnak véget kell érnie. Ez általában két esetben fordul elő: vagy elérte a maximális végrehajtási időt, vagy egy teljesítményküszöböt. Ebben a szakaszban kiválasztják a végső megoldást, majd visszaküldik.

Példa az evolúciós algoritmusokra

Most, hogy bemutassa ennek a folyamatnak az eredményét, meg kell tekintenie a szakértői tanácsadót. Ehhez emlékeztethetünk arra, hogy a dinoszauruszok több generációja hogyan tanult meg járni (fokozatosan elsajátítva a földet), optimalizálva testük szerkezetét és izomerőt alkalmazva. Annak ellenére, hogy a korai generáció hüllői nem tudtak járni, a tanácsadó idővel mutációval és crossoverrel képes volt járni.

Ezek az algoritmusok egyre fontosabbá válnak a modern világban, mivel az ezeken alapuló megoldásokat egyre inkább használják olyan iparágakban, mint a digitális marketing, a pénzügy és az egészségügy.

Ahol az EA-t használják?

Tágabb értelemben az evolúciós algoritmusokat használják széles választék alkalmazások, például képfeldolgozás, járműirányítás, mobil kommunikáció optimalizálása, , szoftverfejlesztés , sőt mesterséges neurális hálózatok képzése is. Ezek az eszközök számos olyan alkalmazás és webhely középpontjában állnak, amelyeket az emberek naponta használnak, beleértve a Google Térképet, sőt olyan játékokat is, mint a The Sims. Ezenkívül az orvosi terület az EA-t használja a rák kezelésével kapcsolatos klinikai döntések meghozatalában. Valójában az evolúciós algoritmusok annyira megbízhatóak, hogy szinte bármilyen optimalizálási probléma megoldására felhasználhatók.

Moore törvénye

Az EO növekvő elterjedtsége két fő tényezőnek köszönhető: a rendelkezésre álló számítási teljesítménynek és a nagy adatkészletek felhalmozódásának. . Az elsőt Moore törvénye írja le, amely valójában kimondja, hogy a számítógép számítási teljesítménye körülbelül kétévente megduplázódik. Ezt az előrejelzést évtizedek óta tartják. A második tényező a technológiától való növekvő függőséghez kapcsolódik, amely lehetővé teszi az intézmények számára, hogy hihetetlenül nagy mennyiségű adatot gyűjtsenek, ami lehetővé teszi számukra a trendek elemzését és a termékek optimalizálását.

Hogyan segíthetnek az evolúciós algoritmusok a marketingszakembereknek?

A piaci helyzet gyorsan változik, és nagyon versenyképes. Ez arra kényszerítette a marketing menedzsereket, hogy versenyezzenek a jobbért döntéshozatal. A rendelkezésre álló számítási teljesítmény növekedése vezette a munkavállalókat az EA használata a problémák megoldására.

Konverzió optimalizálás

Az egyik fő cél a webhely látogatottságának növelése. Ez a probléma abból áll, hogy optimalizálja azon felhasználók számát, akik azt teszik, amit a marketingszakértő akar. Például, ha egy vállalat laptopokat értékesít, ideális esetben növelni kell a webhely látogatóinak 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 webdesign nem túl felhasználóbarát, vannak olyanok, akik végül nem vásárolják meg a terméket egy vagy másik okból. Ezután a cél az, hogy csökkentse azoknak a felhasználóknak a számát, akik végül nem konvertálnak, ami növeli a teljes nyereséget.