Svärm intelligens

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

Svärmintelligens ( RI) 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 [1] . Idén diskuterades dock tidigare i detalj av Stanisław Lem i romanen Invincible (1964) [2] och essän Weapon Systems of the Twenty-First Century, or Upside Down Evolution (1983).

Svärmintelligenssystem består som regel av många agenter ( Boids ) som lokalt interagerar med varandra och med omgivningen. Idéer om beteende kommer som regel från naturen och i synnerhet från biologiska system. Varje boyid följer mycket enkla regler, och även om det inte finns något centraliserat beteendekontrollsystem för att tala om för var och en av dem vad de ska göra, leder lokala och i viss mån slumpmässiga interaktioner till uppkomsten av ett intelligent gruppbeteende utanför individuella kroppars kontroll. Den exakta definitionen av svärmintelligens är fortfarande inte formulerad. Generellt sett bör RI vara ett system med flera agenter som skulle ha ett självorganiserande beteende, som totalt sett borde uppvisa ett rimligt beteende.

Tillämpningen av svärmprinciper inom robotik kallas grupprobotik , medan svärmintelligens hänvisar till en mer allmän uppsättning algoritmer. "Svärmprognos" används för att lösa vissa problem med prognoser.

Exempel på algoritmer

Partikelsvärmmetod

Partikelsvärmoptimering (PSO ) är en  numerisk optimeringsmetod som inte kräver att man känner till den exakta gradienten för den funktion som optimeras. MFR bevisades av Kennedy, Eberhart och Shea, var ursprungligen avsedd att efterlikna socialt beteende. Algoritmen har förenklats och befunnits vara lämplig för att utföra optimering . Kennedy och Eberharts bok beskriver många av de filosofiska aspekterna av MFR och den så kallade svärmintelligensen. Mycket forskning om tillämpningarna av MFR har gjorts av Paul [3] [4] .

MFR optimerar funktionen genom att upprätthålla en population av möjliga lösningar, kallade partiklar, och flytta runt dessa partiklar i lösningsutrymmet enligt en enkel formel. Rörelsen följer principen om den bästa positionen som finns i detta utrymme, och förändras ständigt när partiklarna hittar gynnsamma positioner.

Myralgoritm

Algoritm för myrkolonioptimering ( myrkolonioptimering, ACO ) är en av  de effektiva polynomalgoritmerna för att hitta ungefärliga lösningar på resandeförsäljarproblemet , såväl som liknande problem med att hitta rutter på grafer. Ett tillvägagångssätt som föreslagits av den belgiske forskaren Marco Dorigo .

Kärnan i tillvägagångssättet är att analysera och använda beteendemodellen för myror som letar efter vägar från kolonin till mat. Algoritmen är baserad på beteendet hos en myrkoloni som markerar framgångsrika vägar med en stor mängd feromoner . Arbetet börjar med placeringen av myror vid toppen av grafen (städerna), sedan börjar myrornas rörelse - riktningen bestäms av en probabilistisk metod, baserad på formeln:

,

var:

 - Sannolikhet att korsa vägen ,  — Längden på den e övergången,  — Antal feromoner vid korsningen,  - Värdet som bestämmer algoritmens "girighet",  — Värdet som bestämmer "flockningen" av algoritmen i .

Bee Algorithm

Artificiell bikolonioptimering (ABC ) är en svärmalgoritm baserad på en metaheuristisk algoritm som introducerades av Karabog 2005 [ 5] .  Det efterliknar beteendet hos honungsbin. ABC-algoritmen består av tre steg: ett arbetsbi, ett vaktbi och ett scoutbi. Bina använder en lokal sökalgoritm i närheten av lösningar utvalda baserat på deterministiskt urval av arbetsbin och probabilistiskt urval av vaktbin. Scoutbiet utför avvisande av utarmade matkällor i utfodringsprocessen. I denna analogi kasseras lösningar som inte längre är användbara för att hitta en lösning och nya lösningar läggs till (likt att utforska nya regioner på jakt efter källor).

Artificiellt immunförsvar

Ett artificiellt immunsystem (AIS) är ett adaptivt datorsystem som använder modeller, principer, mekanismer och funktioner som beskrivs i teoretisk immunologi och som används för att lösa tillämpade problem [6] .

Trots det faktum att naturliga immunsystem är långt ifrån att förstås fullt ut, finns det idag minst tre teorier som förklarar immunsystemets funktion och beskriver interaktionen mellan dess element, nämligen: teorin om negativt urval, teorin om klonal selektion och teorin om immunnätverket. De utgjorde grunden för skapandet av tre algoritmer för hur IIS fungerar.

Grå vargalgoritm

Bat-algoritm

Gravitationssökningsalgoritm

Gravitational Search Algorithm ( GSA ) är en  sökalgoritm baserad på lagen om universell gravitation och begreppen massinteraktion. Algoritmen bygger på teorin om attraktion från Newtons fysik . Algoritmen använder gravitationsmassor som sökagenter.

Under de senaste åren har olika heuristiska optimeringsalgoritmer utvecklats . Många av dessa algoritmer är baserade på naturfenomen. Om vi ​​jämför gravitationssökningsalgoritmen med andra algoritmer, så är denna algoritm en av de mest effektiva för att lösa olika problem med att optimera olinjära funktioner.

Altruismalgoritm

Schweiziska forskare har utvecklat en algoritm baserad på Hamiltons familjevalsregel. Algoritmen visar hur en individs altruism i en svärm kan utvecklas över tid och leda till ett mer effektivt svärmbeteende [7] [8] .

Firefly-algoritm

Vattendroppealgoritm

Intelligent Water Droplet Algorithm ( IWD )  är en svärmalgoritmbaserad optimeringsalgoritm som använder metoderna för naturliga floder och hur de hittar nästan optimala vägar till en destination.

Den hittar optimala eller nästan optimala vägar som härrör från reaktioner som äger rum mellan vattendroppar när vattnet rinner genom flodbädden. I IWD-algoritmen är flera konstgjorda vattendroppar beroende av varandra och kan förändra sin miljö på ett sådant sätt att de hittar den bästa vägen på vägen för minst motstånd. Så, IWD-algoritmen är en konstruktiv befolkningsorienterad optimeringsalgoritm [9] .

Flodbildningsmetod

Självgående partikelmetod

Stokastisk diffusionssökning

Multiswarm optimering

Gökens algoritm

Cuckoo-sökalgoritmen är en optimerad algoritm som utvecklades av Xin-She Yang och Suash Deb 2009.

Inspirationen till dess skapelse var boparasitismen hos vissa gökarter som lägger sina ägg i bon hos andra fåglar (andra fågelarter). En del av boägarna kan komma i direkt konflikt med göken som bryter sig in på dem. Till exempel, om boets ägare upptäcker att äggen inte är hans, då kommer han antingen att slänga dessa främmande ägg eller helt enkelt lämna boet och skapa ett nytt någon annanstans.

Vissa gökarter, såsom boparasiter från Nya världen som den randiga eller fyrvingade gökgöken ( Tapera naevia ), har utvecklats på ett sådant sätt att honor mycket ofta specialiserar sig på att efterlikna färgerna och strukturen hos ägg från utvalda värdfågelarter [10 ] .

Bakterierörelseoptimering

Se även

Litteratur

Anteckningar

  1. 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)
  2. Inklusive i kapitlet "Laudahypotesen" finns frasen "svärmen förvandlas till en sådan "molnhjärna"" (rój układa się w ten jakiś "chmuromózg").
  3. Parsopoulos, K.E.; Vrahatis, MN Nya strategier för globala optimeringsproblem genom partikelsvärmoptimering   // Natural Computing : journal. - 2002. - Vol. 1 , nej. 2-3 . - s. 235-306 . - doi : 10.1023/A:1016568309421 .
  4. Particle Swarm Optimization Arkiverad 22 februari 2014 på Wayback Machine av Maurice Clerc, ISTE, ISBN 1-905209-04-5 , 2006.
  5. Karaboga, Dervis (2010) Artificiell bikolonialgoritm Arkiverad 3 april 2014 på Wayback Machine Scholarpedia , 5 (3):6915.
  6. de Castro, Leandro N.; Timmis, Jonathan. Artificiella immunsystem: en ny beräkningsintelligensmetod . - Springer , 2002. - S. 57-58. ISBN 1852335947 , 9781852335946.  
  7. Altruism hjälper svärmande robotar att flyga bättre Arkiverad 15 september 2012 på Wayback Machine genevalunch.com , 4 maj 2011.
  8. Waibel M, Floreano1 D och Keller L (2011) "A quantitative test of Hamilton's rule for the evolution of altruisism" PLoS Biology , 9 (5): e1000615. doi : 10.1371/journal.pbio.1000615
  9. Shah-Hosseini, Hamed. Den intelligenta vattendropparalgoritmen: en naturinspirerad svärmbaserad optimeringsalgoritm  (engelska)  // International Journal of Bio-Inspired Computation : journal. - 2009. - Vol. 1 , nej. 1/2 . - S. 71-79 .
  10. R.B. Payne, M.D. Sorenson och K. Klitz, The Cuckoos, Oxford University Press, (2005).