Algoritmer för myrkolonioptimering

Myrbeteende var inspirationen till den metaheuristiska optimeringstekniken

När en koloni av myror ställs inför valet att nå sin mat via två olika vägar, varav den ena är mycket kortare än den andra, är deras val helt slumpmässigt. De som använder den kortare vägen når dock maten snabbare och går därför oftare fram och tillbaka mellan myrstacken och maten.

Inom datavetenskap och operationsforskning är myrkolonioptimeringsalgoritmen ( ACO ) en probabilistisk teknik för att lösa beräkningsproblem som kan reduceras till att hitta bra vägar genom grafer . Konstgjorda myror står för multi-agent metoder inspirerade av beteendet hos riktiga myror . Den feromonbaserade kommunikationen av biologiska myror är ofta det dominerande paradigmet som används. Kombinationer av konstgjorda myror och lokala sökalgoritmer har blivit en valmetod för många optimeringsuppgifter som involverar någon sorts graf , t.ex. fordonsdirigering och internetdirigering .

är myrkolonioptimering en klass av optimeringsalgoritmer som är modellerade på en myrkolonis handlingar . Konstgjorda "myror" (t.ex. simuleringsmedel) lokaliserar optimala lösningar genom att röra sig genom ett parameterutrymme som representerar alla möjliga lösningar. Riktiga myror lägger ner feromoner som leder varandra till resurser samtidigt som de utforskar sin miljö. De simulerade "myrorna" registrerar på samma sätt sina positioner och kvaliteten på sina lösningar, så att i senare simuleringsiterationer hittar fler myror bättre lösningar. En variant på detta tillvägagångssätt är bins algoritm , som är mer analog med födosöksmönstren hos honungsbiet , en annan social insekt.

Denna algoritm är en medlem av familjen myrkolonialgoritmer, i svärmintelligensmetoder , och den utgör några metaheuristiska optimeringar. Ursprungligen föreslog Marco Dorigo 1992 i sin doktorsavhandling, den första algoritmen syftade till att söka efter en optimal väg i en graf, baserat på beteendet hos myror som söker en väg mellan sin koloni och en källa till mat. Den ursprungliga idén har sedan dess diversifierats för att lösa en bredare klass av numeriska problem, och som ett resultat har flera problem dykt upp, som bygger på olika aspekter av myrors beteende. Ur ett bredare perspektiv utför ACO en modellbaserad sökning och delar vissa likheter med uppskattning av distributionsalgoritmer .

Översikt

I den naturliga världen vandrar myror av vissa arter (till en början) slumpmässigt och när de hittar mat återvänder de till sin koloni medan de lägger ner feromonspår . Om andra myror hittar en sådan väg kommer de sannolikt inte att fortsätta resa på måfå, utan istället följa spåret, återvända och förstärka det om de så småningom hittar mat (se Myrkommunikation ) .

Med tiden börjar dock feromonspåret avdunsta, vilket minskar dess attraktiva styrka. Ju mer tid det tar för en myra att färdas längs vägen och tillbaka igen, desto mer tid har feromonerna på sig att avdunsta. En kort väg, som jämförelse, marscheras över oftare, och därmed blir feromontätheten högre på kortare vägar än längre. Feromonavdunstning har också fördelen att man undviker konvergensen till en lokalt optimal lösning. Om det inte fanns någon avdunstning alls, skulle de vägar som de första myrorna valde tenderar att vara överdrivet attraktiva för de följande. I så fall skulle utforskningen av lösningsutrymmet vara begränsad. Påverkan av feromonavdunstning i riktiga myrsystem är oklart, men den är mycket viktig i artificiella system.

Det övergripande resultatet är att när en myra hittar en bra (dvs kort) väg från kolonin till en födokälla, är det mer sannolikt att andra myror följer den vägen, och positiv feedback leder så småningom till att många myror följer en enda väg . Tanken med myrkolonialgoritmen är att efterlikna detta beteende med "simulerade myror" som går runt grafen som representerar problemet att lösa.

Omgivande nätverk av intelligenta objekt

Nya koncept krävs eftersom "intelligens" inte längre är centraliserad utan kan hittas i alla små objekt. Antropocentriska koncept har varit kända för att leda till produktion av IT-system där databehandling, styrenheter och beräkningskrafter centraliseras. Dessa centraliserade enheter har kontinuerligt ökat sin prestanda och kan jämföras med den mänskliga hjärnan. Modellen av hjärnan har blivit den ultimata visionen för datorer. Omgivande nätverk av intelligenta objekt och, förr eller senare, en ny generation av informationssystem som är ännu mer spridda och baserade på nanoteknik, kommer att på djupet förändra detta koncept. Små apparater som kan jämföras med insekter förfogar inte över en hög intelligens på egen hand. Deras intelligens kan faktiskt klassas som ganska begränsad. Det är till exempel omöjligt att integrera en högpresterande kalkylator med kraften att lösa alla slags matematiska problem i ett biochip som implanteras i människokroppen eller integreras i en intelligent tagg som är designad för att spåra kommersiella artiklar. Men när dessa objekt väl är sammankopplade har de en form av intelligens som kan jämföras med en koloni av myror eller bin. Vid vissa problem kan denna typ av intelligens vara överlägsen resonemanget i ett centraliserat system som liknar hjärnan.

Naturen ger flera exempel på hur små organismer, om de alla följer samma grundregel, kan skapa en form av kollektiv intelligens på det makroskopiska planet. Kolonier av sociala insekter illustrerar perfekt denna modell som skiljer sig mycket från mänskliga samhällen. Denna modell bygger på samarbete mellan oberoende enheter med enkelt och oförutsägbart beteende. De rör sig genom sitt omgivande område för att utföra vissa uppgifter och har endast en mycket begränsad mängd information för att göra det. En koloni av myror, till exempel, representerar många egenskaper som också kan appliceras på ett nätverk av omgivande objekt. Kolonier av myror har en mycket hög kapacitet att anpassa sig till förändringar i miljön samt en enorm styrka i att hantera situationer där en individ misslyckas med att utföra en given uppgift. Denna typ av flexibilitet skulle också vara mycket användbar för mobila nätverk av objekt som ständigt utvecklas. Paket med information som flyttar från en dator till ett digitalt objekt beter sig på samma sätt som myror skulle göra. De rör sig genom nätverket och passerar från en knut till nästa med målet att nå sin slutdestination så snabbt som möjligt.

Konstgjorda feromonsystem

Feromonbaserad kommunikation är ett av de mest effektiva kommunikationssätten som är allmänt observerad i naturen. Feromon används av sociala insekter som bin, myror och termiter; både för kommunikation mellan agenter och agent-svärm. På grund av dess genomförbarhet har konstgjorda feromoner antagits i multirobot- och svärmrobotsystem. Feromonbaserad kommunikation implementerades på olika sätt, såsom kemiska eller fysiska (RFID-taggar, ljus, ljud) sätt. Dessa implementeringar kunde dock inte replikera alla aspekter av feromoner som ses i naturen.

Att använda projicerat ljus presenterades i ett IEEE-dokument från 2007 av Garnier, Simon, et al. som en experimentell uppsättning för att studera feromonbaserad kommunikation med mikroautonoma robotar. En annan studie presenterade ett system där feromoner implementerades via en horisontell LCD-skärm på vilken robotarna rörde sig, där robotarna hade nedåtriktade ljussensorer för att registrera mönstren under dem.

Algoritm och formel

I myrkolonioptimeringsalgoritmerna är en artificiell myra en enkel beräkningsagent som söker efter bra lösningar på ett givet optimeringsproblem. För att tillämpa en myrkolonialgoritm måste optimeringsproblemet omvandlas till problemet att hitta den kortaste vägen på en viktad graf. I det första steget av varje iteration konstruerar varje myra stokastiskt en lösning, det vill säga i vilken ordning kanterna i grafen ska följas. I det andra steget jämförs de vägar som de olika myrorna hittat. Det sista steget består av att uppdatera feromonnivåerna på varje kant.

    
 proceduren  ACO_MetaHeuristic  är  medan den inte  avslutas  gör  generSolutions() daemonActions() pheromoneUpdate()  upprepa  slutprocedur 

Kantval

Varje myra behöver konstruera en lösning för att röra sig genom grafen. För att välja nästa kant i sin tur, kommer en myra att överväga längden på varje kant som är tillgänglig från dess nuvarande position, såväl som motsvarande feromonnivå. Vid varje steg i algoritmen flyttar varje myra från ett tillstånd $x$ till ett tillstånd $y$ , vilket motsvarar en mer komplett mellanlösning. Således beräknar varje ant $k$ en uppsättning $A_{k}(x)$ av möjliga expansioner till sitt nuvarande tillstånd i varje iteration, och flyttar till en av dessa med sannolikhet. För ant $k$ beror sannolikheten $p_{xy}^{k}$ för att flytta från tillstånd $x$ till tillstånd $y$ på kombinationen av två värden, attraktionskraften $\eta _{xy}$ för draget, beräknat av någon heuristik som indikerar det a priori önskvärda draget och spårnivån $\tau _{xy }$ av flytten, vilket indikerar hur skickligt det har varit tidigare att göra just det flytten. Lednivån i efterhand om önskvärdheten av den rörelsen.

I allmänhet flyttar $k$ th myran från tillstånd $x$ till tillstånd $y$ med sannolikhet

$p_{xy}^{k }={\frac {(\tau _{xy}^{\alpha })(\eta _{xy}^{\beta})}{\sum _{z\in \mathrm {tillåtet} _{x} }(\tau _{xz}^{\alpha })(\eta _{xz}^{\beta })}}$

där $\tau _{xy}$ är mängden feromon som avsatts för övergång från tillstånd $x$ till $y$ , 0 ≤ $\alpha$ är en parameter för att kontrollera påverkan av $\tau _{xy}$ , $\eta _{xy}$ är önskvärdheten av tillståndsövergång $xy$ ( a priori kunskap, typiskt $1/d_{xy}$ , där $d$ är avståndet) och $\beta$ ≥ 1 är en parameter för att styra påverkan av ${ \displaystyle \eta _{xy}}$ . $\tau _{xz}$ och $\eta _{xz}$ representerar spårnivån och attraktiviteten för de andra möjliga tillståndsövergångarna.

Feromonuppdatering

Spår uppdateras vanligtvis när alla myror har slutfört sin lösning, vilket ökar eller minskar nivån på spår som motsvarar rörelser som var en del av "bra" respektive "dåliga" lösningar. Ett exempel på en global feromonuppdateringsregel är

$\tau _{xy}\leftarrow (1-\rho )\tau _{xy}+\summa _{k }^{m}\Delta \tau _{xy}^{k}$

där $\tau _{xy}$ är mängden feromon avsatt för en tillståndsövergång ${\displaystyle xy} ,$ ρ $\displaystyle \rho }$ är feromonens avdunstningskoefficient , $m$ är antalet myror och $\Delta \tau _{xy}^{k}$ är mängden feromon som deponeras av ${\displaystyle k}:$ e myran, vanligtvis ges för ett TSP -problem (med rörelser som motsvarar grafens bågar) av

$\Delta \tau _{xy}^{k}={\begin{cases}Q/L_{k} &{\mbox{if ant }}k{\mbox{ använder kurva }}xy{\mbox{ i sin tur}}\\0&{\mbox{annars}}\end{cases}}$

där $L_{k}$ är kostnaden för $k$ th myrans tur (typiskt längd) och $Q$ är en konstant.

Vanliga tillägg

Här är några av de mest populära varianterna av ACO-algoritmer.

Myrsystem (AS)

Myrsystemet är den första ACO-algoritmen. Denna algoritm motsvarar den som presenteras ovan. Det utvecklades av Dorigo.

Myrkolonisystem (ACS)

I myrkolonisystemets algoritm modifierades det ursprungliga myrsystemet i tre aspekter:

1. Kantvalet är partiskt mot exploatering (dvs. gynnar sannolikheten att välja de kortaste kanterna med en stor mängd feromon);
2. Medan man bygger en lösning ändrar myror feromonnivån på kanterna de väljer genom att tillämpa en lokal feromonuppdateringsregel;
3. I slutet av varje iteration får endast den bästa myran uppdatera spåren genom att tillämpa en modifierad global feromonuppdateringsregel.

Elitistiskt myrsystem

I den här algoritmen avsätter den globala bästa lösningen feromon på sitt spår efter varje iteration (även om det här spåret inte har återbesökts), tillsammans med alla andra myror. Den elitistiska strategin har som mål att styra sökandet av alla myror för att konstruera en lösning som innehåller länkar till den nuvarande bästa vägen.

Max-min myrsystem (MMAS)

Denna algoritm styr maximala och lägsta feromonmängder på varje spår. Endast den globala bästa turnén eller iterationens bästa turné tillåts lägga till feromon till dess spår. För att undvika stagnation av sökalgoritmen är intervallet för möjliga feromonmängder på varje spår begränsad till ett intervall [τ _max ,τ _min ]. Alla kanter initieras till τ _max för att tvinga fram en högre utforskning av lösningar. Lederna återinitieras till τ _max när de närmar sig stagnation.

Rankbaserat myrsystem (ASrank)

Alla lösningar rangordnas efter deras längd. Endast ett fast antal av de bästa myrorna i denna iteration får uppdatera sina försök. Mängden feromon avsatt viktas för varje lösning, så att lösningar med kortare vägar avsätter mer feromon än lösningar med längre vägar.

Parallell myrkolonioptimering (PACO)

Ett myrkolonisystem (ACS) med kommunikationsstrategier utvecklas. De konstgjorda myrorna är uppdelade i flera grupper. Sju kommunikationsmetoder för att uppdatera feromonnivån mellan grupper i ACS föreslås och arbetar med resandeförsäljarproblemet.

Kontinuerlig ortogonal myrkoloni (COAC)

Feromonavsättningsmekanismen för COAC är att göra det möjligt för myror att söka efter lösningar tillsammans och effektivt. Genom att använda en ortogonal designmetod kan myror i den genomförbara domänen snabbt och effektivt utforska sina valda regioner, med förbättrad global sökförmåga och precision. Den ortogonala designmetoden och den adaptiva radiejusteringsmetoden kan också utökas till andra optimeringsalgoritmer för att leverera bredare fördelar vid lösning av praktiska problem.

Rekursiv myrkolonioptimering

Det är en rekursiv form av myrsystem som delar upp hela sökdomänen i flera underdomäner och löser målet på dessa underdomäner. Resultaten från alla underdomäner jämförs och de bästa av dem marknadsförs till nästa nivå. De underdomäner som motsvarar de valda resultaten delas upp ytterligare och processen upprepas tills en utdata med önskad precision erhålls. Denna metod har testats på illa ställda geofysiska inversionsproblem och fungerar bra.

Konvergens

För vissa versioner av algoritmen är det möjligt att bevisa att den är konvergent (dvs. den kan hitta det globala optimum i ändlig tid). Det första beviset på konvergens för en myrkolonialgoritm gjordes 2000, den grafbaserade myrsystemalgoritmen, och senare för ACS- och MMAS-algoritmerna. Liksom de flesta metaheuristik är det mycket svårt att uppskatta den teoretiska konvergenshastigheten. En prestandaanalys av en kontinuerlig myrkolonialgoritm med avseende på dess olika parametrar (kantvalsstrategi, avståndsmått och feromonavdunstningshastighet) visade att dess prestanda och konvergenshastighet är känsliga för de valda parametervärdena, och särskilt för värdet av feromonavdunstningshastigheten. 2004 visade Zlochin och hans kollegor att algoritmer av COAC-typ kunde assimileras metoder för stokastisk gradientnedstigning, på korsentropi och uppskattning av distributionsalgoritm . De föreslog dessa metaheuristiker som en "forskningsbaserad modell".

Ansökningar

Ryggsäcksproblem : Myrorna föredrar den mindre droppen honung framför det rikligare, men mindre näringsrika, sockret

Algoritmer för myrkolonioptimering har tillämpats på många kombinatoriska optimeringsproblem , allt från kvadratisk tilldelning till proteinveckning eller routing av fordon och många härledda metoder har anpassats till dynamiska problem i verkliga variabler, stokastiska problem, multi-targets och parallella implementeringar. Det har också använts för att ta fram närmast optimala lösningar på resandeförsäljarproblemet . De har en fördel jämfört med simulerad glödgning och genetiska algoritmer för liknande problem när grafen kan förändras dynamiskt; myrkolonialgoritmen kan köras kontinuerligt och anpassas till förändringar i realtid. Detta är av intresse för nätverksdirigering och stadstransportsystem.

Den första ACO-algoritmen kallades myrsystemet och den syftade till att lösa problemet med resande försäljare, där målet är att hitta den kortaste rundresan för att länka samman en rad städer. Den allmänna algoritmen är relativt enkel och baserad på en uppsättning myror som var och en gör en av de möjliga rundresorna längs städerna. I varje skede väljer myran att flytta från en stad till en annan enligt några regler:

Visualisering av myrkolonialgoritmen tillämpad på resandeförsäljarproblemet. De gröna linjerna är de vägar som varje myra väljer. De blå linjerna är de vägar den kan ta vid varje punkt. När myran slutar, representeras feromonnivåerna i rött.

1. Den måste besöka varje stad exakt en gång;
2. En avlägsen stad har mindre chans att bli vald (synligheten);
3. Ju mer intensiv feromonspåret är utlagt på en kant mellan två städer, desto större är sannolikheten att den kanten kommer att väljas;
4. Efter att ha avslutat sin resa avsätter myran fler feromoner på alla kanter den korsar, om resan är kort;
5. Efter varje iteration avdunstar spår av feromoner.

Schemaläggningsproblem

• Sekventiella beställningsproblem (SOP)
• Job-shop schemaläggningsproblem (JSP)
• Schemaläggningsproblem med öppen butik (OSP)
• Permutation flow shop problem (PFSP)
• Enstaka maskins totala förseningsproblem (SMTTP)
• Enstaka maskins totalviktade förseningsproblem (SMTWTP)
• Resursbegränsade projektschemaläggningsproblem (RCPSP)
• Schemaläggningsproblem för gruppbutiker (GSP)
• Total förseningsproblem för en maskin med sekvensberoende inställningstider (SMTTPDST)
• Flerstegs flowshop-schemaläggningsproblem (MFSP) med sekvensberoende inställnings-/växlingstider
• Assembly Sequence Planning (ASP) problem

Problem med fordonsdirigering

• Capacitated vehicle routing problem (CVRP)
• Multi-depå vehicle routing problem (MDVRP)
• Period fordonsdirigeringsproblem (PVRP)
• Problem med delat leveransfordon (SDVRP)
• Stokastiskt fordonsdirigeringsproblem (SVRP)
• Problem med fordonsdirigering med hämtning och leverans (VRPPD)
• Fordonsdirigeringsproblem med tidsfönster (VRPTW)
• Tidsberoende fordonsdirigeringsproblem med tidsfönster (TDVRPTW)
• Fordonsdirigeringsproblem med tidsfönster och flera servicearbetare (VRPTWMS)

Uppdragsproblem

• Quadratic assignment problem (QAP)
• Generalized assignment problem (GAP)
• Frekvenstilldelningsproblem (FAP)
• Redundansallokeringsproblem (RAP)

Ställ in problem

• Ställ in lockproblem (SCP)
• Partitionsproblem (SPP)
• Viktbegränsad grafträdpartitionsproblem (WCGTPP)
• Arc-weighted l-cardinality tree problem (AWlCTP)
• Flera ryggsäcksproblem (MKP)
• Maximalt oberoende uppsättningsproblem (MIS)

Problem med anordningsstorlek i fysisk design av nanoelektronik

• Myrkolonioptimering (ACO)-baserad optimering av 45 nm CMOS-baserad avkänningsförstärkarkrets skulle kunna konvergera till optimala lösningar på mycket minimal tid.
• Myrkolonioptimering (ACO) baserad reversibel kretssyntes kan förbättra effektiviteten avsevärt.

Antenner optimering och syntes

Loopback vibratorer 10×10, syntetiserade med hjälp av ACO-algoritm

Unloopback vibratorer 10×10, syntetiserade med hjälp av ACO-algoritm

För att optimera formen på antenner kan myrkolonialgoritmer användas. Som exempel kan betraktas antenner RFID-taggar baserade på myrkolonialgoritmer (ACO), loopback och unloopback vibratorer 10×10

Bildbehandling

ACO-algoritmen används vid bildbehandling för bildkantsdetektering och kantlänkning.

• Kantdetektering:

Grafen här är 2D-bilden och myrorna passerar från en pixel som avsätter feromon. Myrors rörelse från en pixel till en annan styrs av den lokala variationen av bildens intensitetsvärden. Denna rörelse gör att den högsta densiteten av feromonet avsätts vid kanterna.

Följande är stegen som är involverade i kantdetektering med ACO:

Steg 1: Initiering. Placera slumpmässigt $K$ myror på bilden $I_{M_{1}M_{2}}$ där $K=( M_{1}*M_{2})^{\tfrac {1}{2}}$ . Feromonmatris $\tau _{(i,j)}$ initieras med ett slumpmässigt värde. Den stora utmaningen i initieringsprocessen är att bestämma den heuristiska matrisen.

Det finns olika metoder för att bestämma den heuristiska matrisen. För exemplet nedan beräknades den heuristiska matrisen baserat på den lokala statistiken: den lokala statistiken vid pixelpositionen ( $\displaystyle (i,j)}$ .

$\eta _{(i,j)}={\tfrac {1}{Z}}*Vc*I_{( I j)},$

där $I$ är bilden av storlek $M_{1}*M_{2}$ ,

$Z=\summa _{i=1:M_{1}}\summa _{j=1: M_{2}}Vc(I_{i,j})$

är en normaliseringsfaktor, och

${\ start{aligned}Vc(I_{i,j})=&f\left(\left\vert I_{(i-2,j-1)}-I_{(i+2,j+1)}\right\ vert +\left\vert I_{(i-2,j+1)}-I_{(i+2,j-1)}\right\vert \right.\\&+\left\vert I_{(i -1,j-2)}-I_{(i+1,j+2)}\right\vert +\left\vert I_{(i-1,j-1)}-I_{(i+1, j+1)}\right\vert \\&+\left\vert I_{(i-1,j)}-I_{(i+1,j)}\right\vert +\left\vert I_{( i-1,j+1)}-I_{(i-1,j-1)}\right\vert \\&+\left.\left\vert I_{(i-1,j+2)}- I_{(i-1,j-2)}\right\vert +\left\vert I_{(i,j-1)}-I_{(i,j+1)}\right\vert \right)\ end{aligned}}$

$f(\cdot )$ kan beräknas med hjälp av följande funktioner:

$f(x)=\lambda x,\quad {\text{för x ≥ 0; (1)}}$

$f(x)=\lambda x^{2},\quad {\text{för x ≥ 0; (2)}}$

$f(x)={\begin{cases}\sin({\frac {\pi x}{2\lambda }}),&{\text{för 0 ≤ x ≤}} \lambda {\text{; (3)}}\\0,&{\text{else}}\end{cases}}$

$f(x)={\begin{cases}\pi x\sin({\frac {\pi x}{2\lambda }}),&{\text{för 0 ≤ x ≤}}\lambda {\text{; (4)}}\\0,&{\text{else}}\end{cases}}$

Parametern $\lambda$ i var och en av ovanstående funktioner justerar funktionernas respektive former.

Steg 2: Byggprocess. Myrans rörelse baseras på 4-anslutna pixlar eller 8-anslutna pixlar . Sannolikheten för att myran rör sig ges av sannolikhetsekvationen $P_{x,y}$

Steg 3 och Steg 5: Uppdateringsprocessen. Feromonmatrisen uppdateras två gånger. i steg 3 uppdateras myrans spår (given av ${\displaystyle \tau _{(x,y)}} )$ där som i steg 5 uppdateras spårets avdunstningshastighet, vilket ges förbi:

$\tau _{ny}\vänsterpil (1-\psi)\tau _{gammal}+\psi \tau _{0}$ ,

där $\psi$ är feromonavklingskoefficienten $0<\tau <1$

Steg 7: Beslutsprocess. När väl K-myrorna har flyttat ett fast avstånd L för N iteration, baseras beslutet om det är en kant eller inte på tröskelvärdet T på feromonmatrisenτ. Tröskeln för exemplet nedan beräknas utifrån Otsus metod .

Bildkant upptäckt med ACO: Bilderna nedan genereras med olika funktioner som ges av ekvationen (1) till (4).

• Kantlänkning: ACO har också visat sig vara effektiv i kantlänkningsalgoritmer.

Andra applikationer

• Konkursprognos
• Klassificering
• Anslutningsorienterad nätverksrouting
• Anslutningsfri nätverksrouting
• Data mining
• Diskonterade kassaflöden i projektplanering
• Distribuerad informationssökning
• Energi- och elnätskonstruktion
• Problem med schemaläggning av rutnätsarbetsflöde
• Hämmande peptiddesign för proteinproteininteraktioner
• Intelligent testsystem
• Kraft elektronisk krets design
• Proteinvikning
• Systemidentifiering

Definitionssvårighet

Med en ACO-algoritm byggs den kortaste vägen i en graf, mellan två punkter A och B, av en kombination av flera vägar. Det är inte lätt att ge en exakt definition av vad algoritm är eller inte är en myrkoloni, eftersom definitionen kan variera beroende på författarna och användningsområdena. Generellt sett betraktas myrkolonialgoritmer som befolkade metaheuristik där varje lösning representeras av en myra som rör sig i sökutrymmet. Myror markerar de bästa lösningarna och tar hänsyn till tidigare markeringar för att optimera sin sökning. De kan ses som probabilistiska multiagentalgoritmer som använder en sannolikhetsfördelning för att göra övergången mellan varje iteration . I sina versioner för kombinatoriska problem använder de en iterativ konstruktion av lösningar. Enligt vissa författare är det som skiljer ACO-algoritmer från andra släktingar (som algoritmer för att uppskatta distributionen eller partikelsvärmoptimering) just deras konstruktiva aspekt. I kombinatoriska problem är det möjligt att den bästa lösningen så småningom hittas, även om ingen myra skulle visa sig effektiv. Således, i exemplet med resande säljareproblem, är det inte nödvändigt att en myra faktiskt åker den kortaste vägen: den kortaste vägen kan byggas från de starkaste segmenten av de bästa lösningarna. Denna definition kan dock vara problematisk när det gäller problem i verkliga variabler, där det inte finns någon struktur av "grannar". Sociala insekters kollektiva beteende förblir en inspirationskälla för forskare. Den stora variationen av algoritmer (för optimering eller inte) som söker självorganisering i biologiska system har lett till konceptet " svärmintelligens ", som är ett mycket allmänt ramverk där myrkolonialgoritmer passar.

Stigmergy algoritmer

Det finns i praktiken ett stort antal algoritmer som hävdar att de är "myrkolonier", utan att alltid dela det allmänna ramverket för optimering av kanoniska myrkolonier. I praktiken anses användningen av informationsutbyte mellan myror via miljön (en princip som kallas " stigmergi ") vara tillräckligt för att en algoritm ska tillhöra klassen av myrkolonialgoritmer. Denna princip har fått vissa författare att skapa termen "värde" för att organisera metoder och beteenden baserat på matsökning, sortering av larver, arbetsfördelning och kooperativa transporter.

Relaterade metoder

Genetiska algoritmer (GA)

Dessa upprätthåller en pool av lösningar snarare än bara en. Processen att hitta överlägsna lösningar efterliknar evolutionens, med lösningar som kombineras eller muteras för att förändra poolen av lösningar, med lösningar av sämre kvalitet som kasseras.

Estimation of distribution algorithm (EDA)

En evolutionär algoritm som ersätter traditionella reproduktionsoperatorer med modellstyrda operatorer. Sådana modeller lärs från befolkningen genom att använda maskininlärningstekniker och representeras som probabilistiska grafiska modeller, från vilka nya lösningar kan samplas eller genereras från guidad crossover.

Simulerad glödgning (SA)

En relaterad global optimeringsteknik som korsar sökutrymmet genom att generera närliggande lösningar till den aktuella lösningen. En överordnad granne accepteras alltid. En sämre granne accepteras sannolikt baserat på skillnaden i kvalitet och en temperaturparameter. Temperaturparametern ändras allteftersom algoritmen fortskrider för att ändra sökningens karaktär.

Reaktiv sökoptimering

Fokuserar på att kombinera maskininlärning med optimering, genom att lägga till en intern återkopplingsslinga för att självjustera de fria parametrarna för en algoritm till egenskaperna hos problemet, instansen och den lokala situationen kring den aktuella lösningen.

Tabu-sökning (TS)

Liknar simulerad glödgning genom att båda korsar lösningsutrymmet genom att testa mutationer av en individuell lösning. Medan simulerad glödgning bara genererar en muterad lösning, genererar tabu-sökning många muterade lösningar och går till lösningen med den lägsta konditionen av de som genereras. För att förhindra cykling och uppmuntra till större rörelse genom lösningsutrymmet, upprätthålls en tabulista över partiella eller kompletta lösningar. Det är förbjudet att flytta till en lösning som innehåller delar av tabulistan, som uppdateras när lösningen passerar lösningsutrymmet.

Artificiellt immunsystem (AIS)

Modellerat på ryggradsdjurens immunsystem.

Partikelsvärmsoptimering (PSO)

En svärmintelligensmetod .

Intelligenta vattendroppar (IWD)

En svärmbaserad optimeringsalgoritm baserad på naturliga vattendroppar som rinner i floder

Gravitationssökningsalgoritm (GSA)

En svärmintelligensmetod .

Ant colony clustering method (ACCM)

En metod som använder sig av klustringsmetod som utökar ACO.

Stokastisk diffusionssökning (SDS)

En agentbaserad probabilistisk global sök- och optimeringsteknik som är bäst lämpad för problem där den objektiva funktionen kan delas upp i flera oberoende delfunktioner.

Historia

Kronologi för COA-algoritmer

Kronologi för myrkolonioptimeringsalgoritmer.

• 1959 uppfann Pierre-Paul Grassé teorin om stigmergi för att förklara beteendet för att bygga bo hos termiter ;
• 1983 studerade Deneubourg och hans kollegor myrors kollektiva beteende ;
• 1988, och Moyson Manderick har en artikel om självorganisering bland myror;
• 1989, arbetet av Goss, Aron, Deneubourg och Pasteels om argentinska myrors kollektiva beteende , vilket kommer att ge idén om algoritmer för optimering av myrkolonier;
• 1989, implementering av en beteendemodell för mat av Ebling och hans kollegor;
• 1991 föreslog M. Dorigo myrsystemet i sin doktorsavhandling (som publicerades 1992). En teknisk rapport extraherad från avhandlingen och medförfattare av V. Maniezzo och A. Colorni publicerades fem år senare;
• of British Telecommunications Plc den första applikationen för telekommunikationsnätverk
• 1995, Gambardella och Dorigo föreslog ant-q , den preliminära versionen av myrkolonisystemet som första estension av myrsystemet;.
• 1996, Gambardella och Dorigo föreslog myrkolonisystem
• 1996, publicering av artikeln om myrsystem;
• 1997 föreslog Dorigo och Gambardella myrkolonisystem hybridiserat med lokal sökning;
• 1997 publicerade Schoonderwoerd och hans kollegor en förbättrad applikation för telekommunikationsnätverk ;
• 1998 lanserar Dorigo den första konferensen dedikerad till ACO-algoritmerna;
• 1998, Stützle föreslår initiala parallella implementeringar ;
• 1999 föreslog Gambardella, Taillard och Agazzi macs-vrptw , det första multi-myrkolonisystemet som tillämpades på fordonsdirigeringsproblem med tidsfönster,
• 1999 publicerar Bonabeau, Dorigo och Theraulaz en bok som främst handlar om konstgjorda myror
• 2000, specialnummer av Future Generation Computer Systems-tidskriften om myralgoritmer
• 2000, Hoos och Stützle uppfinner max-min ant-systemet ;
• 2000, första ansökningarna till schemaläggning , schemaläggning sekvens och tillfredsställelse av begränsningar ;
• 2000 ger Gutjahr det första beviset på konvergens för en algoritm av myrkolonier
• 2001, den första användningen av COA-algoritmer av företag ( Eurobios och AntOptima );
• 2001 publicerade Iredi och hans kollegor den första multi-objektiva algoritmen
• 2002, första tillämpningar i utformningen av schema, Bayesian nätverk;
• 2002 föreslog Bianchi och hennes kollegor den första algoritmen för stokastiska problem;
• 2004 publicerar Dorigo och Stützle boken Ant Colony Optimization med MIT Press
• , Zlochin och Dorigo visar att vissa algoritmer är ekvivalenta med den stokastiska gradientnedstigningen , korsentropimetoden och algoritmer för att uppskatta distribution
• 2005, första ansökningarna på problem med proteinveckning .
• 2012, Prabhakar och kollegor publicerar forskning som rör hur enskilda myror kommunicerar i tandem utan feromoner, vilket speglar principerna för datornätverksorganisation. Kommunikationsmodellen har jämförts med Transmission Control Protocol .
• 2016, första ansökan till peptidsekvensdesign.
• 2017, framgångsrik integration av multikriteriebeslutsmetoden PROMETHEE i ACO-algoritmen ( HUMANT-algoritmen ).

Publikationer (utvalda)

• M. Dorigo , 1992. Optimering, lärande och naturliga algoritmer , doktorsavhandling, Politecnico di Milano, Italien.
• M. Dorigo, V. Maniezzo & A. Colorni, 1996. " Ant System: Optimization by a Colony of Cooperating Agents ", IEEE Transactions on Systems, Man, and Cybernetics–Del B, 26 (1): 29–41.
• M. Dorigo & LM Gambardella , 1997. " Myrkolonisystem: ett kooperativt lärande tillvägagångssätt för det resande säljarproblemet" . IEEE Transactions on Evolutionary Computation, 1 (1): 53–66.
• M. Dorigo, G. Di Caro & LM Gambardella, 1999. " Myralgoritmer för diskret optimering " . Artificiellt liv, 5 (2): 137–172.
•   E. Bonabeau, M. Dorigo och G. Theraulaz, 1999. Swarm Intelligence: From Natural to Artificial Systems, Oxford University Press. ISBN 0-19-513159-2
•   M. Dorigo & T. Stützle, 2004. Ant Colony Optimization , MIT Press. ISBN 0-262-04219-3
• M. Dorigo, 2007. "Optimering av myrkolonier" . Scholarpedia.
• C. Blum, 2005 " Myrkolonioptimering: Introduktion och senaste trender ". Physics of Life Reviews, 2: 353-373
• M. Dorigo, M. Birattari & T. Stützle, 2006 Myrkolonioptimering: artificiella myror som en beräkningsintelligensteknik . TR/IRIDIA/2006-023
•   Mohd Murtadha Mohamad,"Articulated Robots Motion Planning Using Foraging Ant Strategy", Journal of Information Technology - Special Issues in Artificial Intelligence, Vol.20, Nr. 4 s. 163–181, december 2008, ISSN 0128-3790 .
•   N. Monmarché, F. Guinand & P. ​​Siarry (red), "Artificial Ants", augusti 2010 Inbunden 576 s. ISBN 978-1-84821-194-0 .
• A. Kazharov, V. Kureichik, 2010. " Myrkolonioptimeringsalgoritmer för att lösa transportproblem ", Journal of Computer and Systems Sciences International, Vol. 49. Nr 1. s. 30–43.
•   CENTIMETER. Pintea, 2014, Advances in Bio-Inspired Computing for Combinatorial Optimization Problem , Springer ISBN 978-3-642-40178-7
•   K. Saleem, N. Fisal, MA Baharudin, AA Ahmed, S. Hafizah och S. Kamilah, "Myrkoloniinspirerat självoptimerat routingprotokoll baserat på tvärskiktsarkitektur för trådlösa sensornätverk", WSEAS Trans. Commun., vol. 9, nr. 10, s. 669–678, 2010. ISBN 978-960-474-200-4
•   K. Saleem och N. Fisal, "Enhanced Ant Colony algorithm for self-optimized data assured routing in wireless sensor networks", Networks (ICON) 2012 18th IEEE International Conference on, s. 422–427. ISBN 978-1-4673-4523-1
• Abolmaali S, Roodposhti FR. Portföljoptimering med antkolonimetoden en fallstudie på Teherans börs. Journal of Accounting. 2018 Mar;8(1).

externa länkar

• Scholarpedia Myrkolonioptimeringssida
• Hemsida för myrkolonioptimering
• "Ant Colony Optimization" - ryskt vetenskapligt och forskarsamhälle
• AntSim - Simulering av myrkolonialgoritmer
• MIDACO-Solver Allmänt optimeringsprogram baserad på myrkolonioptimering (Matlab, Excel, VBA, C/C++, R, C#, Java, Fortran och Python)
• University of Kaiserslautern, Tyskland, AG Wehn: Myrkolonioptimeringsapplet Visualisering av resande säljare löst av myrsystem med många alternativ och parametrar (Java-applet)
• Ant Farm Simulator
• Ant algoritm simulering (Java Applet)
• Java Ant Colony System Framework
• Implementering av myrkolonioptimeringsalgoritm (Python Notebook)