Evolúciós modellezés

Az evolúciós számítások Darwin elméletének jellemzőit használják  fel intelligens rendszerek felépítésére (csoportszámítási módszerek, genetikai algoritmusok ). A mesterséges intelligencia  - számítástechnikai intelligencia szélesebb területének része .

Az evolúciós modellezés már meglehetősen bejáratott terület, amelyen megkülönböztethető:

1. a molekuláris genetikai információs rendszerek megjelenésének modelljei;
2. az evolúció általános mintáinak modellezése ( Evolúciós algoritmusok ). Ezek olyan rendszerek, amelyek csak evolúciós elveket használnak. Sikeresen alkalmazták funkcionális optimalizálási típusú problémákra, és könnyen leírhatók matematikai nyelven. Ezek közé tartoznak az evolúciós algoritmusok, például az evolúciós programozás , a genetikai algoritmusok , az evolúciós stratégiák , a genetikai programozás ;
3. evolúciós modellek. Ezek olyan rendszerek, amelyek biológiailag reálisabbak, mint az evolúciós algoritmusok, de alkalmazott értelemben nem bizonyultak hasznosnak. Inkább biológiai rendszerekre hasonlítanak, és kevésbé összpontosítanak a technikai problémák megoldására. Bonyolult és érdekes viselkedésük van, és úgy tűnik, hamarosan gyakorlati alkalmazásuk is lesz. Ezek a rendszerek magukban foglalják az úgynevezett mesterséges életet .
4. alkalmazott evolúciós modellezés.

Történelem

A darwini elvek alkalmazása az automatizált problémamegoldásban az 1950-es években kezdődött. 1960-ra ennek az elképzelésnek három különböző értelmezése alakult ki három különböző helyen. Az evolúciós programozást Lawrence J. Vogel vezette be az Egyesült Államokban, míg John Henry Holland genetikai algoritmusnak nevezte módszerét . Németországban Ingo Rechenberg és Hans-Paul Schwefel vezette be az evolúciós stratégiai megközelítést . Ezeket a területeket mintegy 15 éve külön-külön fejlesztik. Az 1990-es évek eleje óta egyetlen technológia, az evolúciós számítástechnika "dialektusaiként" egyesítik őket. Ezenkívül a kilencvenes évek elején megjelent egy negyedik folyam - a genetikai programozás . Az 1990-es évek óta az evolúciós számítástechnika nagyrészt a raj-intelligencia gondolatához kapcsolódik , és a természet által inspirált algoritmusok egyre jelentősebb részeivé válnak ennek a trendnek.

Így az „evolúciós programozás”, „evolúciós stratégiák”, „genetikai algoritmusok” és „genetikai programozás” kifejezések az „evolúciós számítástechnika” vagy „evolúciós modellezés” általános kifejezések speciális eseteinek tekinthetők.

Az evolúció modellezése az evolúciós algoritmusok és a mesterséges élet ötletei alapján Niels Aall Barricelli munkásságával kezdődött az 1960-as években, és kiterjesztette Alex Fraser által, aki számos munkát publikált a mesterséges szelekció modellezéséről . [1] Az evolúciós algoritmusok az 1960-as és 1970-es évek elején Ingo Rechenberg munkájának eredményeként váltak bevett optimalizálási technikává, aki összetett mérnöki problémák megoldására használta őket. [2] A genetikai algoritmusok John Holland munkásságának köszönhetően váltak különösen népszerűvé . [3] Az akadémiai érdeklődés növekedésével párhuzamosan a számítógépek teljesítményének drámai növekedése lehetővé tette a gyakorlati alkalmazásokat, beleértve a számítógépes programok automatikus fejlődését. [4] Az evolúciós algoritmusokat jelenleg a többdimenziós problémák hatékonyabb megoldására használják, mint az ember által fejlesztett szoftvereket. [5]

Általános ötlet

Az ábra az evolúciós számítások egyik változatának, a genetikai algoritmusnak (GA) működésének diagramját mutatja, de felhasználható a megközelítés általános gondolatának megértéséhez.

A kezdeti sokaság alatt bizonyos számú, általában véletlenszerűen megszerzett objektumot értünk. A GA-ban az ilyen objektumok gének vektorai („genotípusai”), ahol minden gén lehet bit, szám vagy más objektum. Az evolúciós stratégia (ES) valós számok vektoraival működik. A genetikai (GP) és evolúciós (EP) programozásban az objektumok szerepét azok a programok töltik be, amelyek egyre jobban (egy bizonyos fitnesz függvény szerint) megoldják a felállított számítási problémát.

Mutációk és keresztek

A mutáció egy "genotípus" véletlenszerű változása. A GA-ban és az ES-ben a mutációs operátor úgy valósítható meg, hogy egyszerűen hozzáadunk egy normális eloszlású valószínűségi változót a vektor minden komponenséhez. A GP-ben és az EP-ben ez a művelet erősen függ a kifejlett programok kódolási módjától. Például fa kódolással (lásd az ábrát) ez megtehető egy csomópont információjának véletlenszerű megváltoztatásával, vagy egy csomópont vagy egy teljes részfa hozzáadásával vagy törlésével.

A „crossover” operátor a jelölt megoldások rekombinációját állítja elő, amelynek szerepe hasonló a természetben a crossover szerepéhez. Az evolúciós számítások szerint a szaporodás általában ivaros – több szülő kell, általában kettő, hogy utódokat hozzon létre. A reprodukálás a különböző algoritmusokban eltérően van definiálva – ez természetesen az adatábrázolástól függ. A szaporodás fő követelménye, hogy az utódnak vagy utódoknak lehetősége legyen mindkét szülő tulajdonságait átörökíteni, azokat valamilyen módon "keverni".

Kiválasztás (kiválasztás)

A kiválasztási szakaszban ki kell választani a teljes népesség egy bizonyos hányadát, amely az evolúció ezen szakaszában "életben" marad. Különféle módon lehet kiválasztani. Az egyed h túlélési valószínűségének az úgynevezett Fitness(h) fitness függvény értékétől kell függnie. Ezt a függvényt úgy kell beállítani, hogy egy adott genotípusra (génvektorra, a termesztés alatt álló program eredményeire) vonatkozó értéke alapján meg lehessen ítélni egy adott genotípus sikerességének mértékét. Maga az s túlélési arány általában a genetikai algoritmus paramétere, és egyszerűen előre megadva. A szelekció eredményeként a H populáció N egyedéből sN egyedeknek kell maradniuk, amelyek bekerülnek a végső H' populációba. A többi egyed meghal.

Modellek a molekuláris genetikai információs rendszerek kialakulásához

Az 1970-es évek elején a Nobel-díjas M. Eigen lenyűgöző kísérletet tett arra, hogy modelleket építsen a molekuláris genetikai információfeldolgozó rendszerek megjelenésére a Föld korai bioszférájában [6] . Közülük a leghíresebb a „kvázifaj” modell, amely a polinukleotid (információs) szekvenciák egyszerű fejlődését írja le. Eigen nyomán 1980-ban V. Ratner és V. Shamin novoszibirszki tudósok javasolták a "méretezők" modelljét [7] .

A kvázifajok modellje az információs sorozatok ( vektorok ) populációjának fokozatos fejlődését veszi figyelembe , amelynek összetevői kis számú diszkrét értéket kapnak. A modellekben szereplő „egyedek” fittségét vektorok függvényében adjuk meg. Minden szakaszban a következő generáció populációjában kiválasztott egyedek alkalmasak az alkalmasságukkal arányos valószínűséggel, valamint az egyedek mutációi - a vektorkomponensek véletlenszerű kiegyensúlyozott helyettesítése.

A sizer modell a legegyszerűbb esetben három típusú makromolekulából álló rendszert vesz figyelembe : egy polinukleotid templátot és az e templát által kódolt transzlációs és replikációs enzimeket . A polinukleotid mátrix olyan, mint egy memóriaeszköz, amely információkat tárol a méretmérő - enzimek - funkcionális egységeiről. A transzlációs enzim egy tetszőleges enzim "termelését" biztosítja a mátrixban rögzített információk szerint. A replikációs enzim biztosítja a polinukleotid templát másolását. A méretezők elegendőek az önreprodukcióhoz . A polinukleotid templát által kódolt további enzimek beépítésével a méretmérő sémába lehetővé válik, hogy a méretező bármilyen tulajdonsággal rendelkezzen, például bizonyos enzimek szintézisének szabályozására és a külső környezet változásaihoz való alkalmazkodásra. [nyolc]

Alkalmazás funkcionális optimalizálási problémákban

Az evolúciós számítástechnikát (EC) gyakran alkalmazzák a sztochasztikus keresés megszervezésére, különösen multimodális problémák esetén, amikor a determinisztikus optimalizálási módszerek vagy az egyszerűbb sztochasztikus módszerek nem teszik lehetővé a célfüggvény viselkedésének vizsgálatát a lokális optimumok tartományain kívül. Az EV módszerek nem garantálják a globális optimum megtalálását polinomiális időben. Az irántuk való gyakorlati érdeklődés annak tudható be, hogy ezek a módszerek – amint azt a gyakorlat mutatja – lehetővé teszik, hogy nagyon nehéz keresési problémákra rövidebb idő alatt jobb (vagy „elég jó”) megoldást találjunk, mint az ilyen esetekben szokásosan alkalmazott módszerek. Használatuk tipikus korlátja a célfüggvény ismételt kiszámításának szükségessége (a jó megoldás elkészítéséhez) (a "ismétlődően" szó általában száztól millióig terjedő számokat jelent). Mindazonáltal az EV-módszerek meglehetősen hatékonynak bizonyultak számos valós probléma megoldásában a mérnöki tervezésben, tervezésben, útválasztásban és elhelyezésben, portfóliókezelésben, a kémiai és molekuláris szerkezetek optimális energiaállapotának keresésében, valamint sok más olyan területen, amelyek lehetővé teszik megfelelő reprezentációk, operátorok, populációk mennyiségei és struktúrái stb.

Az evolúciós modellezés mint kutatási módszer a számítástechnikában

Mivel úgy tűnik, hogy az evolúció a természetes rendszerek információfeldolgozási mechanizmusának alapja, a kutatók olyan elméleti és számítógépes modellek felépítésére törekednek, amelyek ténylegesen megmagyarázzák ennek a mechanizmusnak az alapelveit (lásd: „ Természetes számítástechnika ”). Az ezen a területen végzett kutatásokat az a felfogás jellemzi, hogy a modelleknek nem csak a populációk születését és halálát kell tartalmazniuk, hanem valamit a kettő között is. Leggyakrabban a következő fogalmak szerepelnek.

A rajintelligencia egy decentralizált önszerveződő rendszer kollektív viselkedését írja le .  A mesterséges intelligencia elméletében optimalizálási módszernek tekintik. A kifejezést Gerardo Beni és Wang Jing vezette be 1989-ben, a celluláris robotrendszerrel összefüggésben [9] . A raj-intelligencia rendszerek általában egy sor ágensből állnak ( Multi-agent system ), amelyek lokálisan kölcsönhatásba lépnek egymással és a környezettel. Maguk az ágensek általában meglehetősen egyszerűek, de mind együtt, helyi kölcsönhatásban hozzák létre az úgynevezett rajintelligenciát. Példa erre a természetben egy hangyakolónia , egy méhraj , egy madárraj, hal...

A kollektív intelligencia  egy olyan kifejezés, amely az 1980-as évek közepén jelent meg a szociológiában, amikor a kollektív döntéshozatal folyamatát tanulmányozták. Az NJIT kutatói a kollektív intelligenciát úgy határozták meg, mint egy csoport azon képességét, hogy olyan problémákra találjanak megoldást, amelyek jobbak, mint az adott csoport legjobb egyéni megoldása.

Szociológiai irány - mivel az emberi társadalom valóságos, ráadásul jól megfigyelhető és dokumentált (ellentétben az emberi aggyal), információfeldolgozó eszköz, a szociológiai metaforák és visszaemlékezések már a kezdetektől jelen vannak a kibernetikával és a kapcsolódó területekkel foglalkozó művekben. Ha a rajintelligencia arra koncentrál, hogy egyszerű elemekből komplex viselkedést nyerjen egy rendszerben, akkor ez a megközelítés éppen ellenkezőleg, az egyszerű és különleges objektumok felépítését kutatja összetett és univerzális objektumok alapján: „az állam hülyébb, mint a legtöbb tagja. ” [10] . Ezt az irányt az a vágy jellemzi, hogy a számítástechnika területéről származó szociológiai fogalmakat meghatározzák. Tehát a [11]-ben az elitet a való világ egy bizonyos magánmodelljének hordozójaként határozzák meg, és az alap (vagyis a nép) az elitek közötti döntőbíró szerepét tölti be. Az evolúciós folyamat az elitek létrejöttében és halálában áll. A bázis nem képes megérteni az elit által bemutatott elképzelések, modellek lényegét, és nem is tűz ki magának ilyen feladatot. Azonban éppen az érintettség hiánya miatt megőrzi a világos érzelmi értékelés képességét, amely lehetővé teszi számára, hogy könnyen megkülönböztesse a karizmatikus elitet a hanyatlótól, akik megpróbálják fenntartani kiváltságaikat, felismerve, hogy elképzelésük vagy modelljük nem nyert megerősítést.

Jelentősebb konferenciák

• Nemzetközi Konferencia az Evolúciós Számításelméletről és Alkalmazásokról (ECTA, 2013.09.20-22. Vilamoura, Portugália) [12]
• IEEE Congress on Evolutionary Computation (CEC)
• Genetikai és Evolúciós Számítási Konferencia (GECCO) [13]
• Nemzetközi konferencia a természetből származó párhuzamos problémamegoldásról (PPSN) [14]

Jegyzetek

1. ↑ Fraser AS Monte Carlo genetikai modellek elemzései   // Természet . - 1958. - 1. évf. 181. sz . 4603 . - P. 208-209 . - doi : 10.1038/181208a0 . — PMID 13504138 .
2. ↑ Rechenberg, Ingo. Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (PhD-dolgozat)  (német) . Fromman-Holzboog, 1973.
3. ↑ Holland, John H. Alkalmazkodás természetes és mesterséges rendszerekben  . - University of Michigan Press , 1975. - ISBN 0-262-58111-6 .
4. ↑ Koza, John R. Genetikai programozás  (határozatlan) . - MIT Press , 1992. - ISBN 0-262-11170-5 .
5. ↑ Jamshidi M. Eszközök az intelligens vezérléshez: fuzzy vezérlők, neurális hálózatok és genetikai algoritmusok  (angol)  // Filozófiai tranzakciók. A sorozat, Matematikai, fizikai és műszaki tudományok : folyóirat. - 2003. - 1. évf. 361. sz . 1809 . - P. 1781-1808 . doi : 10.1098 / rsta.2003.1225 . — PMID 12952685 .
6. ↑ Eigen M., Schuster P. Hiperciklus. A makromolekulák szerveződésének elvei / Per. angolról. szerk. M. V. Volkenstein és D. S. Csernavszkij. — M.: Mir, 1982. — 270 p.
7. ↑ Ratner V. A., Shamin V. Sizers: A molekuláris biológiai szerveződés alapvető jellemzőinek modellezése. A makromolekulacsoportok közös tulajdonságainak és tervezési jellemzőinek megfeleltetése // Zh. teljes biológia. - 1983. - T.44. Nem. 1. - c.51-61.
8. ↑ Arutsev A. A., Ermolaev B. V., Kutateladze I. O., Slutsky M. S. A modern természettudomány fogalmai. oktatóanyag. - M., 2007.
9. ↑ Beni, G., Wang, J. Swarm Intelligence in Cellular Robotic Systems, Folytatás. NATO Advanced Workshop on Robots and Biological Systems, Toszkána, Olaszország, június 26-30 (1989)
10. ↑ Wiener N. Kibernetika, vagy Irányítás és kommunikáció az állatban és a gépben. / Per. angolról. I. V. Szolovjov és G. N. Povarov; Szerk. G. N. Povarova. — 2. kiadás. — M.: Nauka; Kiadványok főkiadása külföld számára, 1983. - 344 p.
11. ↑ Igor Weisband. 5000 éves számítástechnika. M. - "Fekete mókus", 2010
12. ↑ Nemzetközi konferencia az evolúciós számításelméletről és -alkalmazásokról (elérhetetlen link) . ECTA. Letöltve: 2013. április 29. Az eredetiből archiválva : 2013. május 10. (határozatlan) 
13. ↑ A genetikai és evolúciós számításokkal foglalkozó speciális érdekcsoport (a hivatkozás nem elérhető) . SIGEVO. Letöltve: 2013. április 29. Az eredetiből archiválva : 2012. július 15. (határozatlan) 
14. ↑ Párhuzamos problémamegoldás a természetből (downlink) . Letöltve: 2012. március 6. Az eredetiből archiválva : 2012. május 4.. (határozatlan) 

Irodalom

• Emelyanov VV, Kureichik VV, Kureichik VM Az evolúciós modellezés elmélete és gyakorlata. - M. : Fizmatlit, 2003. - 432 p. — ISBN 5-9221-0337-7 .
• Kureichik V. M., Lebedev B. K., Lebedev O. K. Keresési adaptáció: elmélet és gyakorlat. - M. : Fizmatlit, 2006. - 272 p. — ISBN 5-9221-0749-6 .
• Gladkov L. A., Kureichik V. V., Kureichik V. M. Genetic Algorithms: Textbook. - 2. kiadás - M . : Fizmatlit, 2006. - 320 p. - ISBN 5-9221-0510-8 .
• Gladkov L.A., Kureichik V.V., Kureichik V.M. és munkatársai Bioinspirált módszerek az optimalizálásban: monográfia. - M. : Fizmatlit, 2009. - 384 p. - ISBN 978-5-9221-1101-0 .
• Rutkovsky L. A mesterséges intelligencia módszerei és technológiái. - M. : Hotline-Telecom, 2010. - 520 p. — ISBN 5-9912-0105-6 .
• Rutkowska D., Pilinsky M., Rutkowski L. Neurális hálózatok, genetikai algoritmusok és fuzzy rendszerek = Sieci neuronowe, algorytmy genetyczne i systemy rozmyte. - 2. kiadás - M . : Hotline-Telecom, 2008. - 452 p. — ISBN 5-93517-103-1 .

Szótárak és enciklopédiák	Britannica (online)
Bibliográfiai katalógusokban	J9U : 987007546715505171 LCCN : sh95003989 NKC : ph643130