Partikelsvärmmetod. Partikelsvärmmetod Schema för algoritmen

"Svärm av partiklar" som den enklaste metoden för evolutionär programmering, baserad på idén om möjligheten att lösa optimeringsproblem genom att modellera beteendet hos grupper av djur. Schema för algoritmen, upprättande av programkod och flödesschema.

Skicka ditt goda arbete i kunskapsbasen är enkelt. Använd formuläret nedan

Studenter, doktorander, unga forskare som använder kunskapsbasen i sina studier och arbete kommer att vara er mycket tacksamma.

Hosted på http://www.allbest.ru/

Introduktion

Sedan Lamarcks tid har utvecklingen av den levande världen betraktats som en process av ständig förbättring (anpassning) av individer under påverkan av miljön. Genom att modellera valet av de bästa planerna som en evolutionsprocess i en population av individer är det möjligt att få en lösning på optimeringsproblemet genom att ställa in de initiala förutsättningarna för evolutionsprocessen, befolka det virtuella universum med varelser - informationsbärare och indikera målet för den evolutionära processen.

Genom att kopiera naturens handlingar skapar en person mer och mer perfekta optimeringsalgoritmer. För deras skapande används oftast exempel från naturen, till exempel: den genetiska koden eller fåglarnas beteende, simulering av fiskvandringar eller kylning av metall etc.

För närvarande används optimeringsalgoritmer i stor utsträckning i produktion och affärer, eftersom de gör det möjligt att spara inte bara pengar utan också tid, vilket ständigt saknas.

I produktionen, tack vare optimering, löses många problem i samband med sådant som maskinstillestånd, lagerspill eller omdirigering av reservdelar till andra maskiner i händelse av haveri.

För detta arbete valdes optimeringsmetoden "partikelsvärm". Metodens algoritm, på grund av sin enkelhet och snabbhet, anses mycket lovande för planeringsproblem.

1 . Formulering av problemet

1.1 Matematisk modell

Partikelsvärmmetoden är den enklaste evolutionära programmeringsmetoden som dök upp i mitten av 90-talet, baserad på idén att det är möjligt att lösa optimeringsproblem genom att modellera beteenden hos grupper av djur. Metoden bygger på det faktum att när fåglar bildar en flock tenderar fåglarna till en viss "tyngdpunkt", vilket gradvis saktar ner sin flyghastighet.

När en förpackning letar efter mat, kommer medlemmar av förpackningen att kontrollera omgivningen och flytta runt förpackningen självständigt. Varje representant har en viss grad av frihet eller slumpmässighet i rörelse, vilket ger honom möjlighet att hitta en ansamling av mat. Så, förr eller senare, kommer en av dem att hitta något ätbart och, som en del av förpackningen, kommer att informera de andra. Resten kan då också närma sig matkällan, och redan kan varje representant, tack vare graden av frihet och slumpmässighet i hans rörelse, hitta en ny ansamling av mat.

Vid implementeringen av denna algoritm är det flerdimensionella sökutrymmet befolkat av en svärm av partiklar (elementära lösningar). Partikelkoordinaterna i rymden bestämmer unikt lösningen på optimeringsproblemet. Förutom koordinaterna beskrivs var och en av partiklarna av rörelsens hastighet och acceleration. Under förflyttningen "kammar" partiklarna lösningsutrymmet och hittar därigenom strömoptimum, dit resten av partiklarna rusar i nästa steg. Varje partikel kommer ihåg sin bästa position, vars data överförs till angränsande partiklar, som tenderar till detta värde.

För att introducera en slumpmässig komponent i sökprocessen kan "galna" partiklar inkluderas, vars rörelselag skiljer sig från restens rörelselag.

2 . Implementering av algoritmen

2.1 Schema för algoritmen

Schemat för algoritmen är som följer:

1. En initial "slumpmässig" population av partiklar skapas.

2. En objektiv funktion beräknas för varje partikel.

3. Den bästa partikeln när det gäller den objektiva funktionen förklaras som "tyngdpunkten".

4. Hastighetsvektorerna för alla partiklar rusar till detta "centrum", medan ju längre partikeln är från den, desto större acceleration har den.

5. Beräkning av nya koordinater för partiklar i lösningsutrymmet utförs.

6. Steg 2-5 upprepas det angivna antalet gånger eller tills stoppvillkoret är uppfyllt.

7. Den sista "tyngdpunkten" förklaras vara den hittade optimala lösningen.

2. 2 Kodenprogram

#omfatta

#omfatta

#omfatta

#omfatta

const int n=200;

const int m=200;

int i, j, k, t=200;

dubbel F (dubbel x)

return pow(pow(x, 3) - 125,2);

(dubbel V[n] [m];

dubbel nedre_gräns=1, övre_gräns=300;

dubbelt bästa_pos[n] [m];

dubbelcel[n][m]; // genotyp array

dubbelt bästa_cel=1000; // bästa globala värde

konstant dubbel Cl=0,7, C2=1,2, w=0,93;

dubbel **X=ny dubbel*[n];

för (i=0; i

X[i]=ny dubbel[m];

srand(tid(NULL));

// initiering av partiklarnas position och hastigheter

för (i=0; i

för (j=0; j

X[i] [j]=undre_gräns + (övre_gräns - nedre_gräns)*rand()/RAND_MAX;

// Initiera med den värsta partikelgenotypen

best_pos[i][j]=1000;

för (k=0; k

// fylla i arrayen av genotyper

för (i=0; i

för (j=0; j

// bestämning av den aktuella genotypen

cel[i][j]=F(X[i][j]);

// lagra värdet av den bästa genotypen för varje partikel

om (cel[i][j]

best_pos[i][j]=cel[i][j];

if (bästa_pos[i][j]

best_cel=bästa_pos[i][j];

printf("%f\n",x);

// Uppdatera partikelhastigheter och positioner

för (i=0; i

för (j=0; j

R1 = 1.*rand()/RAND_MAX;

R2 = 1.*rand()/RAND_MAX;

V[i] [j] = w*V[i] [j] + C1*R1*(bästa_cel - X[i] [j]) + C2*R2*(bästa_pos[i] [j] - X[i ][j]);

X[i] [j] = X[i] [j] + V[i] [j];

2.3 Blockschema över algoritmen

Hosted på http://www.allbest.ru/

Hosted på http://www.allbest.ru/

3 . Teoretisk uppskattning av optimeringsalgoritmens komplexitet

För en teoretisk bedömning av algoritmens komplexitet är det nödvändigt att bestämma antalet elementära operationer som måste utföras för att lösa problemet med denna algoritm.

Med elementära operationer menar vi operationer som kan representeras i form av elementära konstruktioner av ett givet språk (men inte nödvändigtvis i form av en enda maskininstruktion), nämligen följande kommer att betraktas som en elementär operation:

1) uppdragsoperation ab;

2) operationen att indexera matrisen a[i];

3) aritmetiska operationer *,/,-,+;

4) jämförelseoperationer a< b;

5) logiska operationer eller, och, inte.

For-slingan är inte en elementär operation, eftersom kan representeras som;

Således kräver slingkonstruktionen 2*N elementära operationer:

F "cykel" = 2* N+ N* f cykla kroppen.

För vårt program får vi alltså:

F=9+ // konstanter

2*200+200*(2*200+(8+6)*200)+ // positions- och hastighetsinitiering

2*200+200*(2*200+200*(2*200+200*(6+20))+ // fylla i arrayen av genotyp och bästa värden

2*200+200*(2*200+200*(4+4+10+2+16)) // uppdatera hastigheter och positioner

Som ett resultat av den teoretiska beräkningen var komplexiteten för detta program F= 528800809 elementära operationer.

Slutsats

programalgoritmmodellering

På senare tid har många nya algoritmer börjat dyka upp som är baserade på imitation av naturen, men inte alla algoritmer kan skryta med en så enkel implementering och originalitet av idén. På grund av den slumpmässiga fördelningen av partiklar och deras slumpmässighet i rörelse är det mycket stor sannolikhet att hitta den optimala lösningen i flera iterationer, samtidigt som man undviker lokala optima.

Ytterligare utveckling av sådana algoritmer är nyckeln till ny teknik för optimering och utveckling i allmänhet.

Lista över använda källor

1. Ulyanov M.V., Sheptunov M.V. Matematisk logik och algoritmteori, del 2: Algoritmteori. - M.: MGAPI, 2003. - 80 sid.

2. Sammanfattning av föreläsningar om disciplinen "Matematisk logik och teori om algoritmer".

3. Globala optimeringsalgoritmer - teori och tillämpning.

4. http://ru.wikipedia.org

Hosted på Allbest.ru

Liknande dokument

Funktioner av linjär programmeringsproblem. Enkel metod för att lösa linjära programmeringsproblem. Motivering för val av språk, programmeringsverktyg, en lista med identifierare och ett flödesschema över algoritmen. Det logiska schemat för programmet.

avhandling, tillagd 2011-08-13


Utveckling av ett bibliotek som låter dig simulera partiklarnas dynamik i tredimensionell grafik. Valet av medel och utvecklingsmetoder. Alternativ för modellering av partikelsystem. Modellering på vertex shader. Diagram över partikelsystemet och PSBehavior-klassen.

terminsuppsats, tillagd 2016-07-02


Grundläggande analytiska relationer. Blockschema och algoritm för att lösa problemet. Kontrollera prestanda för algoritmen manuellt. Variabel identifieringstabell. Former för in- och utskrift. Programutveckling och felsökning. Instruktioner för att arbeta med programmet.

terminsuppsats, tillagd 2012-02-13


Konceptet linjär programmering och optimering. Grunderna i arbetet i MathCAD-systemet. Användargränssnitt, inmatningsspråk och datatyp. Stadier av matematisk datormodellering. Ett exempel på att lösa ett optimeringsproblem med hjälp av programmet MathCAD.

terminsuppsats, tillagd 2011-10-16


Skapande av ett program i MatLabs programmeringsmiljö för att lösa problemet med endimensionell optimering (att hitta minimum och maximum av givna funktioner) med hjälp av gyllene snittmetoden, konstruera ett flödesschema över algoritmen och grafisk representation av de studerade funktionerna.

abstrakt, tillagt 2010-06-14


Delphi programmeringssystem, dess egenskaper. Grundkrav för utbildningsprogrammet. Rita upp ett blockschema över algoritmen för programmet "Matematik. Betyg 1". Typer av uppgifter som ska lösas i utbildningsprogrammet. Beskrivning av systemets funktion, instruktioner för det.

terminsuppsats, tillagd 2015-06-17


Optimering av problemlösningen med hjälp av glödgningsalgoritmen. Analys av teorin om optimering som objektiv funktion. Gradient descent metod. Variabler och beskrivning av glödgningsalgoritmen. Representation av resandeförsäljarproblemet genom en graf. Reducering av problemet till variabler och lösning.

terminsuppsats, tillagd 2015-05-21


Konstruktion av en matematisk modell av laddade partiklars rörelse, implementering i ett algoritmiskt språk med hjälp av en dator. Beskrivning av ämnesområdet. Simulering av växelverkan mellan två motsatt laddade partiklar. Resultatet av programmet, användarhandbok.

terminsuppsats, tillagd 2015-02-26


Matristransformation av ett system av linjära algebraiska ekvationer (SLAE) med hjälp av Gauss-algoritmen. Lösning av problemet genom metoden med enkel iteration. Skapande av ett blockschema och text till ett program för att lösa SLAE, implementerat i programmeringsspråket Turbo Pascal.

terminsuppsats, tillagd 2013-06-15


Pascal som ett professionellt programmeringsspråk, som är uppkallat efter den franske matematikern och filosofen Blaise Pascal, historien om dess utveckling och funktionella funktioner. Problem med att använda en tvådimensionell array, rita ett flödesschema över lösningen.

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örelserna är föremål för principen om den bästa positionen som finns i detta utrymme, som ständigt förändras när partiklarna hittar mer gynnsamma positioner.

Algoritm

Låta f: ℝ n→ ℝ - objektiv funktion som ska minimeras, S- antalet partiklar i svärmen, som var och en är associerad med en koordinat x jag ∈ ℝ n i lösningsutrymme och hastighet v jag ∈ ℝ n. Låt också sid i är den mest kända positionen för partikeln i, a gär det mest kända tillståndet för svärmen som helhet. Då är den allmänna formen för partikelsvärmmetoden följande.

• För varje partikel i = 1, …, S do:
  • Generera startpositionen för partikeln med hjälp av en slumpmässig vektor x jag ~ U(b lo, b upp) som har en flerdimensionell enhetlig fördelning. b lo och b uppär de nedre och övre gränserna för lösningsutrymmet, respektive.
  • Tilldela den mest kända partikelpositionen till dess initiala värde: sid jag ← x jag .
  • Om en ( f(sid i)< f(g)), uppdatera sedan det mest kända tillståndet för svärmen: g ← sid jag .
  • Tilldela partikelhastighetsvärde: v jag ~ U(-(b upp-b lo), (b upp-b lo)).
• Tills stoppkriteriet är uppfyllt (till exempel nå ett givet antal iterationer eller det erforderliga värdet för målfunktionen), upprepa:
  • För varje partikel i = 1, …, S do:
    • Generera slumpmässiga vektorer r p , r g~ U(0,1).
    • Uppdatera partikelhastighet: v i ← w v i + φp r p×( sid jag- x i) + φg r g×( g-x i), där operationen × betyder komponentvis multiplikation.
    • Uppdatera partikelposition med translation x i till hastighetsvektorn: x jag ← x i + v jag . Observera att detta steg utförs oavsett förbättringen i värdet av målfunktionen.
    • Om en ( f(x i)< f(sid i)), gör sedan:
      • Uppdatera mest kända partikelposition: sid jag ← x jag .
      • Om en ( f(sid i)< f(g)), uppdatera sedan det mest kända tillståndet för svärmen som helhet: g ← sid jag .
• Nu g innehåller de bästa av de hittade lösningarna.

Parametrarna ω, φ p och φ g väljs av räknaren och bestämmer beteendet och effektiviteten för metoden som helhet. Dessa parametrar är föremål för många studier. (se nedan).

Val av parametrar

Valet av optimala parametrar för partikelsvärmmetoden är föremål för ett betydande antal forskningsartiklar, se till exempel arbetet av Shea och Eberhart, Carlisle och Dozer, van den Berg, Clerk och Kennedy, Trelea, Bratton och Blackwell, och Evers.

Ett enkelt och effektivt sätt att välja parametrar för metoden föreslogs av Pedersen och andra författare. De genomförde även numeriska experiment med olika optimeringsproblem och parametrar. Tekniken för att välja dessa parametrar kallas metaoptimering, eftersom en annan optimeringsalgoritm används för att "justera" MFR-parametrarna. MFM-inmatningsparametrarna med bäst prestanda har visat sig strida mot de huvudprinciper som beskrivs i litteraturen och ger ofta tillfredsställande optimeringsresultat för enkla fall av MFM. Deras implementering kan hittas i SwarmOps open source-bibliotek.

Algoritmalternativ

Nya varianter av partikelsvärmalgoritmen föreslås ständigt för att förbättra metodens prestanda. Det finns flera trender i dessa studier, varav en föreslår att skapa en hybridoptimeringsmetod med hjälp av MFR i kombination med andra algoritmer, se t.ex. En annan trend är att på något sätt skynda på metoden, till exempel genom att gå tillbaka eller ändra ordningen för partikelrörelser (se om detta). Det finns också försök att anpassa beteendeparametrarna för MFR under optimeringsprocessen.

Skriv en recension om artikeln "Partikelsvärmmetod"

Anteckningar

1. (1995) "Partikelsvärmoptimering". Proceedings of IEEE International Conference on Neural Networks IV: 1942-1948.
2. (1998) "En modifierad partikelsvärmoptimerare". Proceedings of IEEE International Conference on Evolutionary Computation: 69-73.
3. Svärm intelligens. - Morgan Kaufmann, 2001.
4. Poli, R. (2007). "". Teknisk rapport CSM-469(Institutionen för datavetenskap, University of Essex, Storbritannien).
5. Poli, R. (2008). "". : 1-10. DOI:10.1155/2008/685175.
6. (1998) "Parameterval i partikelsvärmoptimering". Proceedings of Evolutionary Programmering VII (EP98): 591-600.
7. (2000) "Jämföra tröghetsvikter och sammandragningsfaktorer vid optimering av partikelsvärm". Proceedings of the Congress on Evolutionary Computation 1 : 84-88.
8. (2001) "An Off-The-Shelf PSO". Proceedings of the Particle Swarm Optimization Workshop: 1-6.
9. van den Bergh F. En analys av partikelsvärmoptimerare. - University of Pretoria, fakulteten för natur- och jordbruksvetenskap, 2001.
10. (2002) "Partikelsvärmen - explosion, stabilitet och konvergens i ett flerdimensionellt komplext utrymme". IEEE-transaktioner på evolutionär beräkning 6 (1): 58-73.
11. Trelea, I.C. (2003). "The Particle Swarm Optimization Algorithm: konvergensanalys och parameterval". Informationsbehandlingsbrev 85 : 317-325.
12. (2008) "En förenklad rekombinant PSO". Journal of Artificial Evolution and Applications.
13. Evers G.. - University of Texas - Pan American, Institutionen för elektroteknik, 2009.
14. Pedersen M.E.H.. - University of Southampton, School of Engineering Sciences, Computational Engineering and Design Group, 2010.
15. Pedersen, M.E.H.; Chipperfield, A.J. (2010). "". Tillämpad Soft Computing 10 : 618-628.
16. (2002) "Livscykelmodellen: en kombination av partikelsvärmoptimering, genetiska algoritmer och bergsklättrare". Proceedings of Parallel Problem Solving from Nature VII (PPSN): 621-630.
17. (2010) "En effektiv hybridmetod baserad på PSO, ACO och k-medel för klusteranalys". Tillämpad Soft Computing 10 (1): 183-197.
18. (2002) "Utvidga partikelsvärmoptimerare med självorganiserad kritik". Proceedings of the Fourth Congress on Evolutionary Computation (CEC) 2 : 1588-1593.
19. Xinchao, Z. (2010). "En störd partikelsvärmalgoritm för numerisk optimering". Tillämpad Soft Computing 10 (1): 119-124.
20. (2009) Adaptiv partikelsvärmoptimering. IEEE-transaktioner på system, människa och cybernetik 39 (6): 1362-1381.

Länkar

• . Nyheter, personer, platser, program, artiklar etc. Se särskilt gällande MFR-standard. (Engelsk)

Ett utdrag som karakteriserar partikelsvärmmetoden

På kvällen samma dag pågick ett livligt samtal i Denisovs lägenhet bland officerarna i skvadronen.
"Men jag säger till dig, Rostov, att du måste be regementschefen om ursäkt," sa han och vände sig till den karmosinröda, upprörda Rostov, högkvarterets kapten, med grått hår, enorma mustascher och stora drag av ett rynkigt ansikte. .
Stabskaptenen Kirsten blev två gånger degraderad till soldaterna för hedersgärningar och två gånger botad.
"Jag låter ingen säga att jag ljuger!" ropade Rostov. Han sa till mig att jag ljög och jag sa till honom att han ljög. Och så kommer det att förbli. De kan sätta mig i tjänst även varje dag och sätta mig i arrest, men ingen kommer att få mig att be om ursäkt, för om han som regementschef anser sig vara ovärdig att ge mig tillfredsställelse, då ...
– Ja, vänta du, far; du lyssnar på mig, - avbröt kaptenen staven med sin basröst och jämnade lugnt ut sin långa mustasch. - Du berättar för regementschefen inför andra officerare att officeren stal ...
– Det är inte mitt fel att samtalet startade inför andra poliser. Jag kanske inte borde ha talat inför dem, men jag är ingen diplomat. Jag gick sedan med husarerna och gick och tänkte att finesser inte behövs här, men han säger till mig att jag ljuger ... så låt honom ge mig tillfredsställelse ...
– Det är helt okej, ingen tror att du är en fegis, men det är inte meningen. Fråga Denisov, ser det ut som något för en kadett att kräva tillfredsställelse av en regementschef?
Denisov, som bet i mustaschen, lyssnade på konversationen med en dyster blick och ville uppenbarligen inte ingripa i det. På frågan från kaptenens stab skakade han negativt på huvudet.
"Du pratar med regementschefen om detta smutsiga trick inför officerarna", fortsatte högkvarterets kapten. - Bogdanich (Bogdanich kallades regementschefen) belägrade dig.
– Han belägrade inte, utan sa att jag ljuger.
- Ja, och du sa något dumt till honom, och du måste be om ursäkt.
- Aldrig! ropade Rostov.
"Jag trodde inte att det var från dig," sa högkvarterets kapten allvarligt och strängt. – Du vill inte be om ursäkt, och du, far, inte bara inför honom, utan inför hela regementet, inför oss alla, är du skyldig överallt. Och så här: om du bara tänkte och rådfrågade hur du ska hantera denna fråga, annars du direkt, men framför officerarna, och dunkade. Vad ska regementschefen göra nu? Ska vi ställa officeren inför rätta och förstöra hela regementet? Skam hela regementet på grund av en skurk? Så vad tycker du? Men enligt vår mening är det inte det. Och bra jobbat Bogdanich, han sa till dig att du inte talar sanning. Det är obehagligt, men vad ska man göra, far, de stötte på det själva. Och nu, eftersom de vill tysta ner saken, så vill du, på grund av något slags fanabili, inte be om ursäkt, utan vill berätta allt. Du är kränkt över att du är i tjänst, men varför ska du be en gammal och ärlig officer om ursäkt! Vad Bogdanich än må vara, men all ärlig och modig, gamle överste, du är så kränkt; och att förstöra regementet är okej för dig? – Rösten från kaptenspersonalen började darra. – Du, far, är i regementet en vecka utan år; idag här, imorgon flyttade de till adjutanter någonstans; du bryr dig inte ett dugg om vad de kommer att säga: "Tjuvar är bland Pavlograd-officerarna!" Och vi bryr oss inte. Så, vadå, Denisov? Inte likadant?
Denisov förblev tyst och rörde sig inte och tittade då och då med sina lysande svarta ögon på Rostov.
"Ditt eget fanaberi är dig kärt, du vill inte be om ursäkt", fortsatte högkvarterets kapten, "men vi gamla människor, hur vi växte upp, och om Gud vill, kommer att dö i regementet, så regementets ära är kär för oss, och Bogdanich vet det. Åh, vad kära, far! Och det här är inte bra, inte bra! Ta illa upp där eller inte, men jag kommer alltid att berätta sanningen för livmodern. Inte bra!
Och kaptenens stab reste sig och vände sig bort från Rostov.
- Pg "avda, chog" ta det! ropade Denisov och hoppade upp. - Tja, G "skelett! Tja!
Rostov, rodnande och blekande, tittade först på en officer, sedan på en annan.
- Nej, mina herrar, nej ... tror inte ... jag förstår mycket väl, ni ska inte tycka så om mig ... jag ... för mig ... jag är för regementets ära. men vad? Jag ska visa det i praktiken, och för mig äran med banderollen ... ja, det är likadant, verkligen, det är mitt fel! .. - Tårar stod i hans ögon. - Jag är skyldig, allt runt om att skylla! ... Tja, vad vill du mer? ...
"Det är det, greven", ropade kaptenen, vände sig om och slog honom på axeln med sin stora hand.
"Jag säger dig," skrek Denisov, "han är en trevlig liten.
"Det är bättre, greve," upprepade stabens kapten, som om han för sitt erkännande började kalla honom en titel. - Gå och be om ursäkt, ers excellens, ja s.
"Mine herrar, jag kommer att göra allt, ingen kommer att höra ett ord från mig," sa Rostov med bönande röst, "men jag kan inte be om ursäkt, gud, jag kan inte, som du vill!" Hur ska jag be om ursäkt, som en liten, för att be om förlåtelse?
Denisov skrattade.
- Det är värre för dig. Bogdanych är hämndlysten, betala för din envishet, - sa Kirsten.
– Herregud, inte envishet! Jag kan inte beskriva känslan för dig, jag kan inte...

Algoritm

Låta f: ℝ n→ ℝ - objektiv funktion som ska minimeras, S- antalet partiklar i svärmen, som var och en är associerad med en koordinat x jag ∈ ℝ n i lösningsutrymme och hastighet v jag ∈ ℝ n. Låt också sid i är den mest kända positionen för partikeln i, a gär det mest kända tillståndet för svärmen som helhet. Då är den allmänna formen för partikelsvärmmetoden följande.

• För varje partikel i = 1, …, S do:
  • Generera startpositionen för partikeln med hjälp av en slumpmässig vektor x jag ~ U(b lo, b upp) som har en flerdimensionell enhetlig fördelning. b lo och b uppär de nedre och övre gränserna för lösningsutrymmet, respektive.
  • Tilldela den mest kända partikelpositionen till dess initiala värde: sid jag ← x jag .
  • Om en ( f(sid i)< f(g)), uppdatera sedan det mest kända tillståndet för svärmen: g ← sid jag .
  • Tilldela partikelhastighetsvärde: v jag ~ U(-(b upp-b lo), (b upp-b lo)).
• Tills stoppkriteriet är uppfyllt (till exempel nå ett givet antal iterationer eller det erforderliga värdet för målfunktionen), upprepa:
  • För varje partikel i = 1, …, S do:
    • Generera slumpmässiga vektorer r p , r g~ U(0,1).
    • Uppdatera partikelhastighet: v i ← w v i + φp r p×( sid jag- x i) + φg r g×( g-x i), där operationen × betyder komponentvis multiplikation.
    • Uppdatera partikelposition med translation x i till hastighetsvektorn: x jag ← x i + v jag . Observera att detta steg utförs oavsett förbättringen i värdet av målfunktionen.
    • Om en ( f(x i)< f(sid i)), gör sedan:
      • Uppdatera mest kända partikelposition: sid jag ← x jag .
      • Om en ( f(sid i)< f(g)), uppdatera sedan det mest kända tillståndet för svärmen som helhet: g ← sid jag .
• Nu g innehåller de bästa av de hittade lösningarna.

Parametrarna ω, φ p och φ g väljs av räknaren och bestämmer beteendet och effektiviteten för metoden som helhet. Dessa parametrar är föremål för många studier. (se nedan).

Val av parametrar

Valet av optimala parametrar för partikelsvärmmetoden är föremål för ett betydande antal forskningsartiklar, se till exempel arbetet av Shea och Eberhart, Carlisle och Dozer, van den Berg, Clerk och Kennedy, Trelea, Bratton och Blackwell, och Evers.

Ett enkelt och effektivt sätt att välja parametrar för metoden föreslogs av Pedersen och andra författare. De genomförde även numeriska experiment med olika optimeringsproblem och parametrar. Tekniken för att välja dessa parametrar kallas metaoptimering, eftersom en annan optimeringsalgoritm används för att "justera" MFR-parametrarna. MFM-inmatningsparametrarna med bäst prestanda har visat sig strida mot de huvudprinciper som beskrivs i litteraturen och ger ofta tillfredsställande optimeringsresultat för enkla fall av MFM. Deras implementering kan hittas i SwarmOps open source-bibliotek.

Algoritmalternativ

Nya varianter av partikelsvärmalgoritmen föreslås ständigt för att förbättra metodens prestanda. Det finns flera trender i dessa studier, varav en föreslår att skapa en hybridoptimeringsmetod med hjälp av MFR i kombination med andra algoritmer, se t.ex. En annan trend är att på något sätt skynda på metoden, till exempel genom att gå tillbaka eller ändra ordningen för partikelrörelser (se om detta). Det finns också försök att anpassa beteendeparametrarna för MFR under optimeringsprocessen.

se även

• Bee Algoritm
• Gravitationssökningsalgoritm

Anteckningar

1. (1995) "Partikelsvärmoptimering". Proceedings of IEEE International Conference on Neural Networks IV: 1942-1948.
2. (1998) "En modifierad partikelsvärmoptimerare". Proceedings of IEEE International Conference on Evolutionary Computation: 69-73.
3. Svärm intelligens. - Morgan Kaufmann, 2001.
4. Poli, R. (2007). "En analys av publikationer om partikelsvärmoptimeringsapplikationer". Teknisk rapport CSM-469(Institutionen för datavetenskap, University of Essex, Storbritannien).
5. Poli, R. (2008). "Analys av publikationerna om tillämpningarna av partikelsvärmoptimering". : 1-10. DOI:10.1155/2008/685175.
6. (1998) "Parameterval i partikelsvärmoptimering". Proceedings of Evolutionary Programmering VII (EP98): 591-600.
7. (2000) "Jämföra tröghetsvikter och sammandragningsfaktorer vid optimering av partikelsvärm". Proceedings of the Congress on Evolutionary Computation 1 : 84-88.
8. (2001) "An Off-The-Shelf PSO". Proceedings of the Particle Swarm Optimization Workshop: 1-6.
9. van den Bergh F. En analys av partikelsvärmoptimerare. - University of Pretoria, fakulteten för natur- och jordbruksvetenskap, 2001.
10. (2002) "Partikelsvärmen - explosion, stabilitet och konvergens i ett flerdimensionellt komplext utrymme". IEEE-transaktioner på evolutionär beräkning 6 (1): 58-73.
11. Trelea, I.C. (2003). "The Particle Swarm Optimization Algorithm: konvergensanalys och parameterval". Informationsbehandlingsbrev 85 : 317-325.
12. (2008) "En förenklad rekombinant PSO". Journal of Artificial Evolution and Applications.
13. Evers G. En automatisk omgrupperingsmekanism för att hantera stagnation i partikelsvärmoptimering. - University of Texas - Pan American, Institutionen för elektroteknik, 2009.
14. Pedersen M.E.H. Trimma och förenkla heuristisk optimering. - University of Southampton, School of Engineering Sciences, Computational Engineering and Design Group, 2010.
15. Pedersen, M.E.H.; Chipperfield, A.J. (2010). Förenkla optimering av partikelsvärm. Tillämpad Soft Computing 10 : 618-628.
16. (2002) "Livscykelmodellen: en kombination av partikelsvärmoptimering, genetiska algoritmer och bergsklättrare". Proceedings of Parallel Problem Solving from Nature VII (PPSN): 621-630.
17. (2010) "En effektiv hybridmetod baserad på PSO, ACO och k-medel för klusteranalys". Tillämpad Soft Computing 10 (1): 183-197.
18. (2002) "Utvidga partikelsvärmoptimerare med självorganiserad kritik". Proceedings of the Fourth Congress on Evolutionary Computation (CEC) 2 : 1588-1593.
19. Xinchao, Z. (2010). "En störd partikelsvärmalgoritm för numerisk optimering". Tillämpad Soft Computing 10 (1): 119-124.
20. (2009) Adaptiv partikelsvärmoptimering. IEEE-transaktioner på system, människa och cybernetik 39 (6): 1362-1381.

Länkar

• Partikelsvärm central . Nyheter, personer, platser, program, artiklar etc. Se särskilt gällande MFR-standard. (Engelsk)
• SwarmOps. Val av parametrar / kalibrering av MFR och andra metaoptimeringsmetoder. Programvarubibliotek i C och C#.
• EvA2 är ett omfattande evolutionärt optimerings- och MFM-verktyg med öppen källkod skrivet i Java.
• ParadisEO är ett kraftfullt C++ ramverk designat för att skapa olika metaheuristik, inklusive PFM-algoritmer. Klara att använda algoritmer, massor av tutorials som hjälper dig att snabbt skapa din egen MFR.
• MRCH-kod på FORTRAN Prestandamätning på testfunktioner.
• - GPLed computational intelligence simulering och forskningsmiljö skriven i Java, inkluderar olika PSO-implementationer
• Använda en Python-implementering av MFR för att lösa ett trapppassningspussel.
• ECF - Evolutionary Computation Framework olika algoritmer, genotyper, parallellisering, tutorials.