Evolutionär modellering

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 30 september 2017; kontroller kräver 8 redigeringar .

Evolutionära beräkningar använder funktionerna i Darwins teori för att  bygga intelligenta system (metoder för gruppredovisning, genetiska algoritmer ). Det är en del av det bredare området artificiell intelligens  - beräkningsintelligens .

Evolutionär modellering är redan ett ganska etablerat område där det är möjligt att särskilja:

  1. modeller för uppkomsten av molekylärgenetiska informationssystem;
  2. modellering av allmänna evolutionsmönster ( Evolutionära algoritmer ). Detta är system som endast använder evolutionära principer. De har framgångsrikt använts för problem med funktionsoptimering och kan enkelt beskrivas i matematiskt språk. Dessa inkluderar evolutionära algoritmer som evolutionär programmering , genetiska algoritmer , evolutionära strategier , genetisk programmering ;
  3. evolutionära modeller. Detta är system som är mer biologiskt realistiska än evolutionära algoritmer men som inte har visat sig vara användbara i tillämpad mening. De är mer som biologiska system och mindre fokuserade på att lösa tekniska problem. De har ett komplext och intressant beteende, och kommer tydligen snart att ha praktiska tillämpningar. Dessa system inkluderar det så kallade artificiella livet .
  4. tillämpad evolutionär modellering.

Historik

Användningen av darwinistiska principer för automatiserad problemlösning började på 1950-talet. År 1960 utvecklades tre olika tolkningar av denna idé på tre olika platser. Evolutionär programmering introducerades av Lawrence J. Vogel i USA, medan John Henry Holland kallade sin metod för den genetiska algoritmen . I Tyskland introducerade Ingo Rechenberg och Hans-Paul Schwefel den evolutionära strategin . Dessa områden har utvecklats separat i cirka 15 år. Sedan början av 1990-talet har de förenats som "dialekter" av en enda teknik som kallas evolutionär datoranvändning. Dessutom, i början av nittiotalet, dök en fjärde ström upp - genetisk programmering . Sedan 1990-talet har evolutionär datoranvändning till stor del blivit förknippad med idén om svärmintelligens , och naturinspirerade algoritmer blir en allt viktigare del av denna trend.

Således betraktas termerna "evolutionär programmering", "evolutionära strategier", "genetiska algoritmer" och "genetisk programmering" som specialfall av den allmänna termen "evolutionär beräkning" eller "evolutionär modellering".

Modelleringen av evolution med hjälp av idéerna om evolutionära algoritmer och artificiellt liv började med Niels Aall Barricellis arbete på 1960-talet och utökades av Alex Fraser, som publicerade ett antal arbeten om modellering av artificiellt urval . [1] Evolutionära algoritmer blev en etablerad optimeringsteknik som ett resultat av Ingo Rechenbergs arbete på 1960- och början av 1970-talet, som använde dem för att lösa komplexa tekniska problem. [2] Genetiska algoritmer blev särskilt populära tack vare John Hollands arbete . [3] Tillsammans med det växande akademiska intresset har den dramatiska ökningen av datorernas kraft möjliggjort praktiska tillämpningar, inklusive den automatiska utvecklingen av datorprogram. [4] Evolutionära algoritmer används för närvarande för att lösa flerdimensionella problem mer effektivt än mänskligt utvecklad programvara. [5]

Allmän idé

Figuren visar ett diagram över funktionen av en av varianterna av evolutionära beräkningar - en genetisk algoritm (GA), men den kan användas för att förstå den allmänna idén om tillvägagångssättet.

Den initiala populationen förstås som ett visst antal objekt som erhållits, vanligtvis slumpmässigt. I GA är sådana objekt vektorer ("genotyper") av gener, där varje gen kan vara en bit, ett nummer eller något annat objekt. Den evolutionära strategin (ES) arbetar med vektorer av reella tal. I genetisk (GP) och evolutionär (EP) programmering spelas objektens roll av program som bättre och bättre (enligt en viss konditionsfunktion) löser det inställda beräkningsproblemet.

Mutationer och korsningar

En mutation är en slumpmässig förändring i en "genotyp". I GA och ES kan mutationsoperatorn implementeras genom att helt enkelt lägga till en normalfördelad slumpmässig variabel till varje komponent i vektorn. I GP och EP beror denna operation starkt på sättet att koda odlade program. Till exempel, med trädkodning (se figur), kan det göras genom att slumpmässigt ändra informationen i en nod eller genom att lägga till eller ta bort en nod eller ett helt underträd.

"Crossover"-operatören producerar en rekombination av kandidatlösningar, vars roll liknar rollen för crossover i naturen. Reproduktion i evolutionära beräkningar är vanligtvis sexuell - det krävs flera föräldrar, vanligtvis två, för att få avkomma. Reproduktion i olika algoritmer definieras olika - det beror naturligtvis på datarepresentationen. Huvudkravet för reproduktion är att avkomman eller avkomman har möjlighet att ärva båda föräldrarnas egenskaper, "blanda" dem på något sätt.

Urval (val)

I urvalsstadiet är det nödvändigt att välja ut en viss andel av hela befolkningen som kommer att förbli "levande" i detta evolutionsstadium. Det finns olika sätt att välja. Överlevnadssannolikheten för en individ h måste bero på värdet av den så kallade fitnessfunktionen Fitness(h). Denna funktion bör ställas in på ett sådant sätt att dess värde för en given genotyp (genvektor, resultat av programmet som odlas) kan användas för att bedöma graden av framgång för en given genotyp. Själva överlevnadsgraden är vanligtvis en parameter för den genetiska algoritmen, och den ges helt enkelt i förväg. Som ett resultat av selektion, av N individer av population H, måste sN-individer finnas kvar, som kommer att inkluderas i den slutliga populationen H'. Resten av individerna dör.

Modeller för uppkomsten av molekylärgenetiska informationssystem

I början av 1970-talet gjorde Nobelpristagaren M. Eigen ett imponerande försök att bygga modeller för uppkomsten av molekylärgenetiska informationsbearbetningssystem i jordens tidiga biosfär [6] . Den mest kända av dem är modellen "quasispecies", som beskriver den enkla utvecklingen av polynukleotidsekvenser (information). Efter Eigen 1980 föreslog Novosibirsk-forskarna V. Ratner och V. Shamin en modell av "sizers" [7] .

Modellen av kvasiarter beaktar den gradvisa utvecklingen av en population av informationssekvenser ( vektorer ), vars komponenter får ett litet antal diskreta värden. Lämpligheten för "individer" i modellerna ges som en funktion av vektorer. I varje steg finns det ett urval av individer i populationen av nästa generation med sannolikheter proportionella mot deras kondition, såväl som mutationer av individer - slumpmässiga, lika sannolika ersättningar av vektorkomponenter.

Sizer-modellen betraktar i det enklaste fallet ett system av tre typer av makromolekyler : en polynukleotidmall och translations- och replikationsenzymer som kodas av denna mall. En polynukleotidmatris är som en minnesenhet som lagrar information om de funktionella enheterna hos sizer - enzymer. Översättningsenzymet säkerställer "produktionen" av ett godtyckligt enzym enligt informationen som registreras i matrisen. Replikationsenzymet tillhandahåller kopiering av polynukleotidmallen. Storlekarna är tillräckliga för självreproduktion . Genom att inkludera ytterligare enzymer som kodas av polynukleotidmallen i storleksschemat är det möjligt att förse storleksanordningen med vilka egenskaper som helst, till exempel förmågan att reglera syntesen av vissa enzymer och anpassa sig till förändringar i den yttre miljön. [åtta]

Applikation i funktionsoptimeringsproblem

Evolutionary computing (EC) används ofta för att organisera stokastisk sökning, särskilt i fallet med multimodala problem, när deterministiska optimeringsmetoder eller enklare stokastiska metoder inte tillåter att man studerar beteendet hos den objektiva funktionen utanför regionerna för lokala optima. EV-metoder garanterar inte att hitta det globala optimum i polynomtid. Det praktiska intresset för dem beror på att dessa metoder, som praxis visar, gör det möjligt att hitta bättre (eller ”tillräckligt bra”) lösningar på mycket svåra sökproblem på kortare tid än andra metoder som vanligtvis används i dessa fall. En typisk begränsning för deras användning är behovet (att bygga en bra lösning) att upprepade gånger beräkna den objektiva funktionen (ordet "upprepade gånger" betyder vanligtvis siffror från hundratals till miljoner). Ändå har EV-metoder visat sig vara ganska effektiva för att lösa ett antal verkliga problem inom teknisk design, planering, routing och placering, portföljhantering, sökning efter optimala energitillstånd för kemiska och molekylära strukturer, såväl som inom många andra områden som tillåter en lämplig uppsättning representationer, operatörer, volymer och strukturer av populationer, etc.

Evolutionär modellering som forskningsmetod inom datavetenskap

Eftersom evolution verkar vara grunden för informationsbehandlingsmekanismen i naturliga system, strävar forskare efter att bygga teoretiska och datormodeller som faktiskt förklarar principerna för denna mekanism (se " Naturlig datavetenskap "). Forskningen inom detta område kännetecknas av förståelsen att modeller inte bara ska innehålla befolkningars födelse och död, utan också något däremellan. Följande begrepp är oftast inblandade.

Svärmintelligens beskriver det  kollektiva beteendet hos ett decentraliserat självorganiserande system. Anses i teorin om artificiell intelligens som en optimeringsmetod. Termen introducerades av Gerardo Beni och Wang Jing 1989, i samband med det cellulära robotsystemet [9] . Svärmintelligenssystem består som regel av en uppsättning agenter ( Multi-agent system ) som lokalt interagerar med varandra och med omgivningen. Agenterna i sig är vanligtvis ganska enkla, men tillsammans skapar de, som interagerar lokalt, den så kallade svärmintelligensen. Ett exempel i naturen är en koloni av myror , en binsvärm , en flock fåglar, fiskar ...

Kollektiv intelligens  är en term som dök upp i sociologin i mitten av 1980-talet när man studerade processen för kollektivt beslutsfattande. Forskare vid NJIT har definierat kollektiv intelligens som förmågan hos en grupp att hitta lösningar på problem som är bättre än den bästa individuella lösningen i den gruppen.

Sociologisk riktning - eftersom det mänskliga samhället är ett verkligt, dessutom, väl observerbart och dokumenterat (till skillnad från den mänskliga hjärnan), har informationsbearbetningsverktyg, sociologiska metaforer och reminiscenser funnits i arbeten om cybernetik och relaterade områden sedan själva starten. Om svärmintelligens är fokuserad på att erhålla komplext beteende i ett system från enkla element, utforskar detta tillvägagångssätt tvärtom konstruktionen av enkla och speciella objekt på grundval av komplexa och universella: "staten är dummare än de flesta av dess medlemmar ” [10] . Denna riktning kännetecknas av viljan att ge definitioner till sociologiska begrepp från datavetenskapens område. Så i [11] definieras eliten som bärare av en viss privat modell av den verkliga världen, och basen (det vill säga folket) spelar rollen som en skiljedomare mellan eliterna. Den evolutionära processen består i generation och död av eliter. Grunden kan inte förstå kärnan i de idéer och modeller som presenteras av eliten, och ställer sig inte på en sådan uppgift. Men just på grund av sitt icke-engagemang behåller han förmågan till en tydlig känslomässig bedömning, vilket gör att han enkelt kan skilja karismatiska eliter från förfallna som försöker behålla sina privilegier, och inser att deras idé eller modell inte har bekräftats.

Stora konferenser

Anteckningar

  1. ↑ Fraser AS Monte Carlo analyser av genetiska modeller   // Nature . - 1958. - Vol. 181 , nr. 4603 . - S. 208-209 . - doi : 10.1038/181208a0 . — PMID 13504138 .
  2. ↑ Rechenberg, Ingo. Evolutionsstrategie - Optimering tekniska Systeme nach Prinzipien der biologischen Evolution (PhD-avhandling)  (tyska) . Fromman-Holzboog, 1973.
  3. ↑ Holland, John H. Anpassning i naturliga och konstgjorda system  . - University of Michigan Press , 1975. - ISBN 0-262-58111-6 .
  4. ↑ Koza, John R. Genetisk programmering  (obestämd) . - MIT Press , 1992. - ISBN 0-262-11170-5 .
  5. ↑ Jamshidi M. Verktyg för intelligent kontroll: suddiga kontroller, neurala nätverk och genetiska algoritmer  (engelska)  // Filosofiska transaktioner. Serie A, Matematisk, fysik och ingenjörsvetenskap : journal. - 2003. - Vol. 361 , nr. 1809 . - P. 1781-1808 . doi : 10.1098 / rsta.2003.1225 . — PMID 12952685 .
  6. ↑ Eigen M., Schuster P. Hypercycle. Principer för organisering av makromolekyler / Per. från engelska. ed. M.V. Volkenstein och D.S. Chernavsky. — M.: Mir, 1982. — 270 sid.
  7. ↑ Ratner V. A., Shamin V. Sizers: modellering av grundläggande egenskaper hos molekylärbiologisk organisation. Överensstämmelse mellan gemensamma egenskaper och designegenskaper för grupper av makromolekyler // Zh. total biologi. - 1983. - T.44. Nej. 1. - c.51-61.
  8. ↑ Arutsev A. A., Ermolaev B. V., Kutateladze I. O., Slutsky M. S. Concepts of modern natural science. Handledning. - M., 2007.
  9. ↑ Beni, G., Wang, J. Swarm Intelligence in Cellular Robotic Systems, Fortsätt. NATO Advanced Workshop on Robots and Biological Systems, Toscana, Italien, 26-30 juni (1989)
  10. ↑ Wiener N. Cybernetik, eller Kontroll och kommunikation i djuret och maskinen. / Per. från engelska. I.V. Solovyov och G.N. Povarov; Ed. G. N. Povarova. — 2:a upplagan. — M.: Nauka; Huvudupplaga av publikationer för främmande länder, 1983. - 344 sid.
  11. ↑ Igor Weisband. 5000 år av datavetenskap. M. - "Black Squirrel", 2010
  12. ↑ Internationell konferens om evolutionär beräkningsteori och tillämpningar (otillgänglig länk) . ECTA. Hämtad 29 april 2013. Arkiverad från originalet 10 maj 2013. 
  13. ↑ Specialintressegrupp för genetisk och evolutionär beräkning (länk inte tillgänglig) . SIGEVO. Hämtad 29 april 2013. Arkiverad från originalet 15 juli 2012. 
  14. ↑ Parallell problemlösning från naturen (nedlänk) . Hämtad 6 mars 2012. Arkiverad från originalet 4 maj 2012. 

Litteratur

  Gå till Wikidata-objektet  Ordböcker och uppslagsverk
I bibliografiska kataloger