Paraan ng particle swarm. Particle swarm method Scheme ng algorithm

"Particle swarm" bilang pinakasimpleng paraan ng evolutionary programming, batay sa ideya ng paglutas ng mga problema sa pag-optimize sa pamamagitan ng pagmomodelo ng pag-uugali ng mga grupo ng mga hayop. Scheme ng algorithm, compilation ng program code at flowchart.

Ipadala ang iyong mabuting gawa sa base ng kaalaman ay simple. Gamitin ang form sa ibaba

Ang mga mag-aaral, nagtapos na mga estudyante, mga batang siyentipiko na gumagamit ng base ng kaalaman sa kanilang pag-aaral at trabaho ay lubos na magpapasalamat sa iyo.

Na-post sa http://www.allbest.ru/

Panimula

Mula noong panahon ni Lamarck, ang pag-unlad ng buhay na mundo ay itinuturing na isang proseso ng patuloy na pagpapabuti (pagbagay) ng mga indibidwal sa ilalim ng impluwensya ng kapaligiran. Sa pamamagitan ng pagmomodelo ng pagpili ng pinakamahusay na mga plano bilang isang proseso ng ebolusyon sa isang populasyon ng mga indibidwal, posible na makakuha ng solusyon sa problema sa pag-optimize sa pamamagitan ng pagtatakda ng mga paunang kondisyon ng proseso ng ebolusyon, paglalagay sa virtual na uniberso ng mga nilalang na nagdadala ng impormasyon, at nagpapahiwatig ng layunin ng proseso ng ebolusyon.

Sa pamamagitan ng pagkopya sa mga aksyon ng kalikasan, ang tao ay lumilikha ng higit at mas advanced na mga algorithm sa pag-optimize. Para sa kanilang paglikha, ang mga halimbawa mula sa kalikasan ay kadalasang ginagamit, halimbawa: ang genetic code o pag-uugali ng mga ibon, pagmomodelo ng mga paglilipat ng isda o paglamig ng metal, atbp.

Sa kasalukuyan, ang mga algorithm ng pag-optimize ay malawakang ginagamit sa produksyon at negosyo, dahil ginagawa nilang posible na makatipid hindi lamang ng pera, kundi pati na rin ang oras, na patuloy na kulang.

Sa produksyon, salamat sa pag-optimize, maraming problemang nauugnay sa mga bagay tulad ng downtime ng makina, pag-apaw ng warehouse, o pag-redirect ng mga ekstrang bahagi sa iba pang mga makina kung sakaling masira.

Para sa gawaing ito, napili ang "particle swarm" na paraan ng pag-optimize. Ang algorithm ng pamamaraan, dahil sa pagiging simple at bilis nito, ay itinuturing na napaka-promising para sa mga problema sa pagpaplano.

1 . Pagbubuo ng problema

1.1 Matematikal na modelo

Ang "particle swarm" na paraan ay ang pinakasimpleng paraan ng evolutionary programming, na lumitaw noong kalagitnaan ng 90s, batay sa ideya na posible na malutas ang mga problema sa pag-optimize sa pamamagitan ng pagmomodelo ng pag-uugali ng mga grupo ng mga hayop. Ang pamamaraan ay batay sa katotohanan na kapag bumubuo ng isang kawan, ang mga ibon ay may posibilidad sa ilang sentro ng "gravity", unti-unting nagpapabagal sa kanilang bilis ng paglipad.

Kapag naghahanap ng pagkain ang isang kawan, titingnan ng mga miyembro ang nakapalibot na lugar at palipat-lipat sa kawan nang hiwalay sa isa't isa. Ang bawat kinatawan ay may antas ng kalayaan o randomness sa paggalaw, na nagbibigay ng pagkakataong makahanap ng akumulasyon ng pagkain. Kaya, maaga o huli, ang isa sa kanila ay makakahanap ng isang bagay na nakakain, at, bilang bahagi ng kawan, ay ipaalam sa iba. Ang natitira ay maaari ring lumapit sa pinagmumulan ng pagkain, at ang bawat kinatawan, salamat sa antas ng kalayaan at pagiging random ng paggalaw nito, ay makakahanap ng bagong akumulasyon ng pagkain.

Sa pagpapatupad ng algorithm na ito, ang multidimensional na espasyo sa paghahanap ay pinupuno ng isang kuyog ng mga particle (mga solusyon sa elementarya). Ang mga coordinate ng particle sa espasyo ay natatanging tinutukoy ang solusyon sa problema sa pag-optimize. Bilang karagdagan sa mga coordinate, ang bawat particle ay inilalarawan sa pamamagitan ng bilis ng paggalaw at pagbilis nito. Sa proseso ng paglipat, ang mga particle ay "nagsusuklay" sa espasyo ng solusyon at sa gayon ay nahanap ang kasalukuyang pinakamabuting kalagayan, kung saan ang natitirang mga particle ay nagmamadali sa susunod na hakbang. Naaalala ng bawat particle ang pinakamagandang posisyon nito, ang data tungkol sa kung saan ipinapadala sa mga kalapit na particle na nagsusumikap para sa halagang ito.

Upang ipasok ang isang random na bahagi sa proseso ng paghahanap, maaaring isama ang mga "baliw" na mga particle, ang batas ng paggalaw na naiiba sa batas ng paggalaw ng iba.

2 . Pagpapatupad ng algorithm

2.1 Scheme ng algorithm

Ang algorithm ay gumagana tulad ng sumusunod:

1. Isang paunang "random" na populasyon ng mga particle ay nilikha.

2. Para sa bawat particle, kinakalkula ang layunin ng function.

3. Ang pinakamahusay na butil mula sa punto ng view ng layunin function ay ipinahayag ang "sentro ng atraksyon".

4. Ang mga vector ng bilis ng lahat ng mga particle ay nagmamadali patungo sa "gitna" na ito, at kung mas malayo ang particle mula dito, mas malaki ang acceleration nito.

5. Kinakalkula ang mga bagong coordinate ng mga particle sa espasyo ng solusyon.

6. Ang mga hakbang 2-5 ay inuulit sa tinukoy na bilang ng beses o hanggang sa matugunan ang kondisyon ng paghinto.

7. Ang huling "center of gravity" ay ipinahayag na ang pinakamainam na solusyon na natagpuan.

2. 2 Codemga programa

#isama

#isama

#isama

#isama

const int n=200;

const int m=200;

int i, j, k, t=200;

dobleng F (dobleng x)

return pow(pow(x, 3) - 125.2);

(dobleng V[n] [m];

double lower_limit=1, upper_limit=300;

dobleng best_pos[n] [m];

dobleng cel[n] [m]; // hanay ng genotype

dobleng best_cel=1000; // pinakamahusay na pandaigdigang halaga

const double C1=0.7, C2=1.2, w=0.93;

double **X=bagong double*[n];

para sa (i=0; i

X[i]=bagong doble[m];

srand(oras(NULL));

// initialization ng particle position at velocities

para sa (i=0; i

para sa (j=0; j

X[i] [j]=lower_limit + (upper_limit - lower_limit)*rand()/RAND_MAX;

// Pagsisimula sa pinakamasamang kaso ng genotype ng mga particle

best_pos[i] [j]=1000;

para sa (k=0; k

// pagpuno sa hanay ng mga genotype

para sa (i=0; i

para sa (j=0; j

// pagpapasiya ng kasalukuyang genotype

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

// pag-save ng halaga ng pinakamahusay na genotype para sa bawat particle

kung (cel[i][j]

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

kung (best_pos[i] [j]

best_cel=best_pos[i] [j];

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

// I-update ang mga bilis at posisyon ng particle

para sa (i=0; i

para sa (j=0; j

R1 = 1.*rand()/RAND_MAX;

R2 = 1.*rand()/RAND_MAX;

V[i] [j] = w*V[i] [j] + C1*R1*(best_cel - X[i] [j]) + C2*R2*(best_pos[i] [j] - X[i ][j]);

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

2.3 Block diagram ng algorithm

Na-post sa http://www.allbest.ru/

Na-post sa http://www.allbest.ru/

3 . Teoretikal na pagtatasa ng pagiging kumplikado ng algorithm ng pag-optimize

Upang matantya sa teorya ang pagiging kumplikado ng isang algorithm, kinakailangan upang matukoy ang bilang ng mga elementarya na operasyon na dapat gawin upang malutas ang problema gamit ang algorithm na ito.

Ang ibig sabihin ng elementarya na mga operasyon ay mga operasyon na maaaring katawanin sa anyo ng elementarya na mga konstruksyon ng isang partikular na wika (ngunit hindi kinakailangan sa anyo ng isang utos ng makina), ibig sabihin, isasaalang-alang namin ang sumusunod bilang isang elementarya na operasyon:

1) pagpapatakbo ng pagtatalaga ab;

2) array indexing operation a[i];

3) mga pagpapatakbo ng aritmetika *,/,-+;

4) paghahambing na mga operasyon a< b;

5) mga lohikal na operasyon o, at, hindi.

Ang para sa loop ay hindi isang elementarya na operasyon, dahil maaaring kinakatawan bilang;

Kaya, ang pagbuo ng loop ay nangangailangan ng 2*N elementary operations:

F "cycle" = 2* N+ N* f "katawan ng loop".

Kaya, para sa aming programa nakukuha namin ang:

F=9+ // mga pare-pareho

2*200+200*(2*200+(8+6)*200)+ // pagsisimula ng posisyon at bilis

2*200+200*(2*200+200*(2*200+200*(6+20))+ // pinupunan ang hanay ng genotype at pinakamahusay na halaga

2*200+200*(2*200+200*(4+4+10+2+16)) // pag-update ng mga bilis at posisyon

Bilang resulta ng mga teoretikal na kalkulasyon, ang pagiging kumplikado ng programang ito ay F = 528800809 na mga operasyong elementarya.

Konklusyon

pagmomodelo ng algorithm ng programa

Kamakailan, maraming mga bagong algorithm ang nagsimulang lumitaw na batay sa imitasyon ng kalikasan, ngunit hindi lahat ng algorithm ay maaaring ipagmalaki ang kadalian ng pagpapatupad at pagka-orihinal ng ideya. Dahil sa randomness ng pamamahagi ng mga particle at ang kanilang magulong paggalaw, mayroong napakataas na posibilidad na makahanap ng pinakamainam na solusyon sa ilang mga pag-ulit, habang iniiwasan ang lokal na optima.

Ang karagdagang pag-unlad ng naturang mga algorithm ay ang susi sa mga bagong teknolohiya sa pag-optimize at pag-unlad sa pangkalahatan.

Listahan ng mga mapagkukunang ginamit

1. Ulyanov M.V., Sheptunov M.V. Logic ng matematika at teorya ng mga algorithm, bahagi 2: Teorya ng mga algorithm. - M.: MGAPI, 2003. - 80 p.

2. Mga tala sa panayam sa disiplina na "Mathematical logic at theory of algorithms."

3. Global Optimization Algorithm - Teorya at Aplikasyon.

4. http://ru.wikipedia.org

Nai-post sa Allbest.ru

Mga katulad na dokumento

Mga tampok ng mga problema sa linear programming. Simplex na paraan para sa paglutas ng mga problema sa linear programming. Pagkatwiran para sa pagpili ng wika, mga tool sa programming, listahan ng mga identifier at algorithm block diagram. Lohikal na diagram ng programa.

thesis, idinagdag noong 08/13/2011


Pagbuo ng library na magbibigay-daan sa iyong gayahin ang particle dynamics sa three-dimensional na graphics. Pagpili ng mga tool at pamamaraan ng pag-unlad. Mga opsyon para sa pagmomodelo ng mga sistema ng particle. Pagmomodelo ng vertex shader. Mga diagram ng klase ng Particle System at PSBehavior.

course work, idinagdag 02/07/2016


Pangunahing analitikal na relasyon. Block diagram at algorithm para sa paglutas ng problema. Sinusuri ang pagganap ng algorithm nang manu-mano. Talahanayan ng pagkakakilanlan ng variable. Mga anyo ng pag-print ng input at output. Pag-unlad at pag-debug ng programa. Mga tagubilin para sa pagtatrabaho sa programa.

course work, idinagdag noong 02/13/2012


Ang konsepto ng linear programming at optimization. Mga pangunahing kaalaman sa pagtatrabaho sa sistema ng MathCAD. User interface, wika ng pag-input at uri ng data. Mga yugto ng computer mathematical modelling. Isang halimbawa ng paglutas ng problema sa pag-optimize gamit ang MathCAD program.

course work, idinagdag noong 10/16/2011


Paglikha ng isang programa sa kapaligiran ng programming ng MatLab para sa paglutas ng isang one-dimensional na problema sa pag-optimize (paghahanap ng minimum at maximum ng mga ibinigay na function) gamit ang ginintuang pamamaraan ng seksyon, pagbuo ng isang block diagram ng algorithm at graphic na paglalarawan ng mga pinag-aralan na function.

abstract, idinagdag noong 06/14/2010


Delphi programming system, ang mga katangian nito. Mga pangunahing kinakailangan para sa programa ng pagsasanay. Pagguhit ng isang block diagram ng algorithm ng programang "Mathematics. 1st grade". Mga uri ng problema na dapat lutasin sa programa ng pagsasanay. Paglalarawan ng pagpapatakbo ng system, mga tagubilin para dito.

course work, idinagdag 06/17/2015


Pag-optimize ng solusyon sa problema gamit ang algorithm ng pagsusubo. Pagsusuri ng teorya ng pag-optimize bilang isang layunin na function. Paraan ng gradient descent. Mga variable at paglalarawan ng algorithm ng pagsusubo. Ang representasyon ng naglalakbay na problema sa tindero sa pamamagitan ng isang graph. Pagbawas ng problema sa mga variable at paglutas nito.

course work, idinagdag noong 05/21/2015


Konstruksyon ng isang matematikal na modelo ng paggalaw ng mga sisingilin na particle, pagpapatupad sa isang algorithmic na wika gamit ang isang computer. Paglalarawan ng lugar ng paksa. Simulation ng pakikipag-ugnayan ng dalawang magkasalungat na sisingilin na mga particle. Mga resulta ng programa, manwal ng gumagamit.

course work, idinagdag 02/26/2015


Pagbabago ng matrix ng isang sistema ng linear algebraic equation (SLAE) gamit ang Gaussian algorithm. Paglutas ng problema gamit ang isang simpleng paraan ng pag-ulit. Paglikha ng block diagram at teksto ng isang programa para sa paglutas ng mga SLAE, na ipinatupad sa Turbo Pascal programming language.

course work, idinagdag noong 06/15/2013


Pascal bilang isang propesyonal na programming language, na pinangalanan pagkatapos ng French mathematician at pilosopo na si Blaise Pascal, ang kasaysayan ng pag-unlad at functional na mga tampok nito. Problema sa paggamit ng two-dimensional array, pagguhit ng block diagram ng solusyon.

Ino-optimize ng MRF ang isang function sa pamamagitan ng pagpapanatili ng populasyon ng mga posibleng solusyon, na tinatawag na mga particle, at paglipat ng mga particle na iyon sa espasyo ng solusyon ayon sa isang simpleng formula. Ang mga displacement ay napapailalim sa prinsipyo ng pinakamahusay na posisyon na matatagpuan sa puwang na ito, na patuloy na nagbabago kapag ang mga particle ay nakahanap ng mas kapaki-pakinabang na mga posisyon.

Algorithm

Hayaan f: ℝ n→ ℝ ay ang layunin na function na kailangang mabawasan, S- ang bilang ng mga particle sa kuyog, ang bawat isa ay nauugnay sa isang coordinate x ako ∈ ℝ n sa espasyo at bilis ng solusyon v ako ∈ ℝ n. Hayaan din p i ang pinakakilalang posisyon ng particle i, A g- ang pinakakilalang estado ng kuyog sa kabuuan. Pagkatapos ang pangkalahatang anyo ng paraan ng particle swarm ay ang mga sumusunod.

• Para sa bawat butil i = 1, …, S gawin:
  • Bumuo ng paunang posisyon ng isang particle gamit ang isang random na vector x ako~ U(b lo, b up), pagkakaroon ng multivariate uniform distribution. b lo At b up ay ang ibaba at itaas na mga hangganan ng espasyo ng solusyon, ayon sa pagkakabanggit.
  • Italaga ang pinakakilalang posisyon ng particle sa paunang halaga nito: p ako ← x i.
  • kung ( f(p i)< f(g)), pagkatapos ay i-update ang pinakakilalang estado ng kuyog: g ← p i.
  • Magtalaga ng halaga ng bilis ng butil: v ako~ U(-(b up-b lo), (b up-b lo)).
• Hanggang sa matugunan ang pamantayan sa paghinto (halimbawa, maabot ang tinukoy na bilang ng mga pag-ulit o ang kinakailangang halaga ng layunin ng function), ulitin:
  • Para sa bawat butil i = 1, …, S gawin:
    • Bumuo ng mga random na vector r p, r g~ U(0,1).
    • I-update ang bilis ng particle: v ako ← ω v i + φ p r p×( p ako- x i) + φg r g×( g-x i), kung saan ang operasyon × ay nangangahulugan ng componentwise multiplication.
    • I-update ang posisyon ng particle na may pagsasalin x i sa bawat bilis ng vector: x ako ← x i+ v i. Tandaan na ang hakbang na ito ay ginagawa anuman ang pagpapabuti sa halaga ng layunin ng function.
    • kung ( f(x i)< f(p i)), pagkatapos ay gawin:
      • I-update ang pinakakilalang posisyon ng particle: p ako ← x i.
      • kung ( f(p i)< f(g)), pagkatapos ay i-update ang pinakakilalang estado ng kuyog sa kabuuan: g ← p i.
• Ngayon g naglalaman ng pinakamahusay na solusyon na natagpuan.

Ang mga parameter na ω, φ p, at φ g ay pinili ng computer at tinutukoy ang pag-uugali at kahusayan ng pamamaraan sa kabuuan. Ang mga parameter na ito ay paksa ng maraming pag-aaral (tingnan sa ibaba).

Pagpili ng mga parameter

Ang pagpili ng pinakamainam na mga parameter para sa pamamaraan ng particle swarm ay ang paksa ng isang makabuluhang halaga ng gawaing pananaliksik, tingnan, halimbawa, ang gawain nina Shea at Eberhart, Carlisle at Dozer, van den Bergh, Clerk at Kennedy, Trelea, Bratton at Blackwell , at Evers.

Ang isang simple at epektibong paraan upang piliin ang mga parameter ng pamamaraan ay iminungkahi ni Pedersen at iba pang mga may-akda. Nagsagawa rin sila ng mga numerical na eksperimento na may iba't ibang problema at parameter sa pag-optimize. Ang pamamaraan para sa pagpili ng mga parameter na ito ay tinatawag na meta-optimization, dahil ang ibang optimization algorithm ay ginagamit upang "i-tune" ang mga parameter ng MRF. Ang pinakamahusay na gumaganap na mga parameter ng input ng MFC ay natagpuan na salungat sa mga pangunahing prinsipyo na inilarawan sa panitikan at madalas na gumagawa ng mga kasiya-siyang resulta ng pag-optimize para sa mga simpleng kaso ng MFC. Ang kanilang pagpapatupad ay matatagpuan sa bukas na SwarmOps library.

Mga pagpipilian sa algorithm

Ang mga bagong variant ng particle swarm algorithm ay patuloy na iminungkahi upang mapabuti ang pagganap ng pamamaraan. Mayroong ilang mga uso sa pananaliksik na ito, ang isa ay nagmumungkahi ng paglikha ng isang hybrid na paraan ng pag-optimize gamit ang MRF kasama ng iba pang mga algorithm, tingnan ang halimbawa. Ang isa pang kalakaran ay nagmumungkahi sa paanuman na pabilisin ang pamamaraan, halimbawa, sa pamamagitan ng paglipat pabalik o pagbabago ng pagkakasunud-sunod ng paggalaw ng butil (para sa karagdagang impormasyon, tingnan). Mayroon ding mga pagtatangka na iakma ang mga parameter ng pag-uugali ng MRF sa panahon ng proseso ng pag-optimize.

Sumulat ng isang pagsusuri tungkol sa artikulong "Paraan ng particle swarm"

Mga Tala

1. (1995) "Pag-optimize ng Particle Swarm". Mga Pamamaraan ng IEEE International Conference on Neural Networks IV: 1942-1948.
2. (1998) "Isang binagong particle swarm optimizer". Mga Pamamaraan ng IEEE International Conference on Evolutionary Computation: 69-73.
3. Swarm Intelligence. - Morgan Kaufmann, 2001.
4. Poli, R. (2007). "". Teknikal na Ulat CSM-469(Department of Computer Science, University of Essex, UK).
5. Poli, R. (2008). "". : 1-10. DOI:10.1155/2008/685175.
6. (1998) "Pagpili ng parameter sa pag-optimize ng kuyog ng butil". Mga Pamamaraan ng Evolutionary Programming VII (EP98): 591-600.
7. (2000) "Paghahambing ng inertia weights at constriction factors sa particle swarm optimization". Mga Pamamaraan ng Kongreso sa Evolutionary Computation 1 : 84-88.
8. (2001) "Isang Off-The-Shelf PSO". Mga Pamamaraan ng Particle Swarm Optimization Workshop: 1-6.
9. van den Bergh F. Isang Pagsusuri ng Mga Particle Swarm Optimizer. - Unibersidad ng Pretoria, Faculty ng Natural at Agricultural Science, 2001.
10. (2002) "Ang particle swarm - pagsabog, katatagan, at convergence sa isang multidimensional complex space." Mga Transaksyon ng IEEE sa Evolutionary Computation 6 (1): 58-73.
11. Trelea, I.C. (2003). "Ang Particle Swarm Optimization Algorithm: pagtatasa ng convergence at pagpili ng parameter." Mga Liham sa Pagproseso ng Impormasyon 85 : 317-325.
12. (2008) "Isang Pinasimpleng Recombinant PSO". Journal ng Artipisyal na Ebolusyon at Aplikasyon.
13. Evers G.. - Ang Unibersidad ng Texas - Pan American, Departamento ng Electrical Engineering, 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). "". Inilapat na Soft Computing 10 : 618-628.
16. (2002) "The LifeCycle Model: pinagsasama-sama ang particle swarm optimization, genetic algorithms at hillclimbers." Proceedings of Parallel Problem Solving from Nature VII (PPSN): 621-630.
17. (2010) "Isang mahusay na hybrid na diskarte batay sa PSO, ACO at k-means para sa pagsusuri ng kumpol." Inilapat na Soft Computing 10 (1): 183-197.
18. (2002) "Extending Particle Swarm Optimizer na may Self-Organized Criticality". Mga Pamamaraan ng Ikaapat na Kongreso sa Evolutionary Computation (CEC) 2 : 1588-1593.
19. Xinchao, Z. (2010). "Isang nababagabag na particle swarm algorithm para sa numerical optimization." Inilapat na Soft Computing 10 (1): 119-124.
20. (2009) "Adaptive Particle Swarm Optimization." Mga Transaksyon ng IEEE sa Mga Sistema, Tao, at Cybernetics 39 (6): 1362-1381.

Mga link

• . Balita, tao, lugar, programa, artikulo, atbp. Sa partikular, tingnan ang kasalukuyang pamantayan ng MRF. (Ingles)

Isang sipi na nagpapakita ng Particle Swarm Method

Sa gabi ng parehong araw, nagkaroon ng masiglang pag-uusap sa pagitan ng mga opisyal ng squadron sa apartment ni Denisov.
"At sinasabi ko sa iyo, Rostov, na kailangan mong humingi ng tawad sa komandante ng regimental," sabi ng isang mataas na kapitan ng kawani na may kulay-abo na buhok, isang malaking bigote at malalaking katangian ng isang kulubot na mukha, lumingon sa pulang-pula, nasasabik na si Rostov.
Ang kapitan ng staff na si Kirsten ay na-demote sa pagiging sundalo ng dalawang beses para sa mga bagay na may karangalan at dalawang beses na nagsilbi.
- Hindi ako papayag na may magsabi sa akin na nagsisinungaling ako! - sigaw ni Rostov. "Sinabi niya sa akin na nagsisinungaling ako, at sinabi ko sa kanya na nagsisinungaling siya." Ito ay mananatiling gayon. Maaari niya akong italaga sa tungkulin araw-araw at ipaaresto ako, ngunit walang magpipilit sa akin na humingi ng tawad, dahil kung siya, bilang isang regimental commander, ay itinuturing ang kanyang sarili na hindi karapat-dapat na bigyan ako ng kasiyahan, kung gayon...
- Maghintay lamang, ama; "Makinig ka sa akin," pinutol ng kapitan ang punong-tanggapan sa kanyang bass voice, mahinahong hinihimas ang kanyang mahabang bigote. - Sa harap ng ibang mga opisyal, sasabihin mo sa regimental commander na nagnakaw ang opisyal...
"Hindi ko kasalanan na nagsimula ang pag-uusap sa harap ng ibang mga opisyal." Siguro hindi ako dapat magsalita sa harap nila, pero hindi ako diplomat. Pagkatapos ay sumama ako sa mga hussar, naisip ko na hindi na kailangan ng mga subtleties, ngunit sinabi niya sa akin na nagsisinungaling ako ... kaya bigyan niya ako ng kasiyahan ...
- Lahat ng ito ay mabuti, walang nag-iisip na ikaw ay isang duwag, ngunit hindi iyon ang punto. Tanungin si Denisov, mukhang isang bagay ba ito para sa isang kadete na humingi ng kasiyahan mula sa komandante ng regimental?
Si Denisov, na kinagat ang kanyang bigote, nakinig sa pag-uusap na may madilim na hitsura, tila hindi nais na makisali dito. Nang tanungin ng mga tauhan ng kapitan, negatibo siyang umiling.
"Sasabihin mo sa komandante ng regimental ang tungkol sa maruming panlilinlang na ito sa harap ng mga opisyal," patuloy ng kapitan. - Bogdanych (ang regimental commander ay tinawag na Bogdanych) kinubkob ka.
- Hindi niya siya kinubkob, ngunit sinabi na nagsisinungaling ako.
- Well, oo, at sinabi mo ang isang bagay na katangahan sa kanya, at kailangan mong humingi ng tawad.
- Hindi kailanman! - sigaw ni Rostov.
"Hindi ko inisip ito mula sa iyo," seryoso at mahigpit na sabi ng kapitan. "Ayaw mong humingi ng tawad, ngunit ikaw, ama, hindi lamang sa harap niya, ngunit sa harap ng buong regimen, bago sa ating lahat, ikaw ang ganap na sisihin." Ganito: kung naisip mo lang at nakonsulta mo kung paano haharapin ang usaping ito, kung hindi ay nakainom ka sa harap mismo ng mga opisyal. Ano ang dapat gawin ngayon ng regimental commander? Dapat bang ilagay sa paglilitis ang opisyal at marumi ang buong rehimyento? Dahil sa isang scoundrel, nadisgrasya ang buong regiment? Kaya, ano sa palagay mo? Ngunit sa aming opinyon, hindi ganoon. At magaling si Bogdanich, sinabi niya sa iyo na nagsisinungaling ka. Ito ay hindi kanais-nais, ngunit ano ang magagawa mo, ama, sila mismo ang umatake sa iyo. At ngayon, dahil gusto nilang patahimikin ang bagay na ito, dahil sa ilang uri ng panatismo ayaw mong humingi ng tawad, ngunit nais mong sabihin ang lahat. Nasasaktan ka na ikaw ay nasa tungkulin, ngunit bakit ka hihingi ng tawad sa isang matanda at tapat na opisyal! Kahit ano pa si Bogdanich, isa pa rin siyang tapat at matapang na matandang koronel, nakakahiya para sa iyo; Okay lang bang madumihan mo ang regiment? – Nagsimulang manginig ang boses ng kapitan. - Ikaw, ama, ay nasa rehimyento sa loob ng isang linggo; ngayon dito, bukas ay inilipat sa adjutants sa isang lugar; wala kang pakialam kung ano ang sinasabi nila: "may mga magnanakaw sa mga opisyal ng Pavlograd!" Pero nagmamalasakit kami. Kaya, ano, Denisov? Hindi lahat pareho?
Si Denisov ay nanatiling tahimik at hindi gumagalaw, paminsan-minsan ay sumulyap kay Rostov gamit ang kanyang nagniningning na itim na mga mata.
"Pahalagahan mo ang sarili mong panabery, ayaw mong humingi ng tawad," patuloy ng kapitan ng punong-tanggapan, "ngunit para sa amin na matatanda, kung paano kami lumaki, at kahit na kami ay namatay, sa loob ng Diyos, kami ay dadalhin sa regiment, kaya ang karangalan ng rehimyento ay mahal sa amin, at alam ito ni Bogdanich. Oh, anong daan, ama! At ito ay hindi maganda, hindi maganda! Ma-offend man o hindi, I will always tell the truth. Hindi maganda!
At ang kapitan ng punong-tanggapan ay tumayo at tumalikod mula sa Rostov.
- Pg "avda, chog" kunin mo na! - sigaw ni Denisov, tumatalon. - Well, G'skeleton!
Si Rostov, namumula at namumutla, ay tumingin muna sa isang opisyal, pagkatapos ay sa isa pa.
- Hindi, mga ginoo, hindi... huwag mong isipin... Naiintindihan ko talaga, mali ang pag-iisip mo sa akin ng ganyan... Ako... para sa akin... I'm for the honor of the rehimyento. Kaya ano? Ipapakita ko ito sa pagsasanay, at para sa akin ang karangalan ng banner... well, pareho lang talaga, ako ang may kasalanan!.. - Tumulo ang luha sa kanyang mga mata. - Ako ay nagkasala, ako ay nagkasala sa buong paligid!... Buweno, ano pa ang kailangan mo?...
"Iyon na, Count," sigaw ng kapitan ng mga tauhan, lumingon, tinamaan siya sa balikat ng kanyang malaking kamay.
"Sinasabi ko sa iyo," sigaw ni Denisov, "siya ay isang magandang maliit na tao."
"Mas mabuti iyan, Count," ulit ng kapitan ng punong-tanggapan, na para bang para sa kanyang pagkilala ay sinimulan nilang tawagan siya ng isang titulo. - Halika at humingi ng tawad, kamahalan, oo ginoo.
"Mga ginoo, gagawin ko ang lahat, walang makakarinig ng isang salita mula sa akin," sabi ni Rostov sa isang nagsusumamong boses, "ngunit hindi ako maaaring humingi ng tawad, sa pamamagitan ng Diyos, hindi ko magagawa, anuman ang gusto mo!" Paano ako hihingi ng tawad, tulad ng isang maliit, na humihingi ng kapatawaran?
Tumawa si Denisov.
- Ito ay mas masahol para sa iyo. Mapaghiganti si Bogdanich, babayaran mo ang katigasan ng ulo mo,” sabi ni Kirsten.
- Sa Diyos, hindi katigasan ng ulo! Hindi ko mailarawan sa iyo kung ano ang pakiramdam, hindi ko...

Algorithm

Hayaan f: ℝ n→ ℝ ay ang layunin na function na kailangang mabawasan, S- ang bilang ng mga particle sa kuyog, ang bawat isa ay nauugnay sa isang coordinate x ako ∈ ℝ n sa espasyo at bilis ng solusyon v ako ∈ ℝ n. Hayaan din p i ang pinakakilalang posisyon ng particle i, A g- ang pinakakilalang estado ng kuyog sa kabuuan. Pagkatapos ang pangkalahatang anyo ng paraan ng particle swarm ay ang mga sumusunod.

• Para sa bawat butil i = 1, …, S gawin:
  • Bumuo ng paunang posisyon ng isang particle gamit ang isang random na vector x ako~ U(b lo, b up), pagkakaroon ng multivariate uniform distribution. b lo At b up ay ang ibaba at itaas na mga hangganan ng espasyo ng solusyon, ayon sa pagkakabanggit.
  • Italaga ang pinakakilalang posisyon ng particle sa paunang halaga nito: p ako ← x i.
  • kung ( f(p i)< f(g)), pagkatapos ay i-update ang pinakakilalang estado ng kuyog: g ← p i.
  • Magtalaga ng halaga ng bilis ng butil: v ako~ U(-(b up-b lo), (b up-b lo)).
• Hanggang sa matugunan ang pamantayan sa paghinto (halimbawa, maabot ang tinukoy na bilang ng mga pag-ulit o ang kinakailangang halaga ng layunin ng function), ulitin:
  • Para sa bawat butil i = 1, …, S gawin:
    • Bumuo ng mga random na vector r p, r g~ U(0,1).
    • I-update ang bilis ng particle: v ako ← ω v i + φ p r p×( p ako- x i) + φg r g×( g-x i), kung saan ang operasyon × ay nangangahulugan ng componentwise multiplication.
    • I-update ang posisyon ng particle na may pagsasalin x i sa bawat bilis ng vector: x ako ← x i+ v i. Tandaan na ang hakbang na ito ay ginagawa anuman ang pagpapabuti sa halaga ng layunin ng function.
    • kung ( f(x i)< f(p i)), pagkatapos ay gawin:
      • I-update ang pinakakilalang posisyon ng particle: p ako ← x i.
      • kung ( f(p i)< f(g)), pagkatapos ay i-update ang pinakakilalang estado ng kuyog sa kabuuan: g ← p i.
• Ngayon g naglalaman ng pinakamahusay na solusyon na natagpuan.

Ang mga parameter na ω, φ p, at φ g ay pinili ng computer at tinutukoy ang pag-uugali at kahusayan ng pamamaraan sa kabuuan. Ang mga parameter na ito ay paksa ng maraming pag-aaral (tingnan sa ibaba).

Pagpili ng mga parameter

Ang pagpili ng pinakamainam na mga parameter para sa pamamaraan ng particle swarm ay ang paksa ng isang makabuluhang halaga ng gawaing pananaliksik, tingnan, halimbawa, ang gawain nina Shea at Eberhart, Carlisle at Dozer, van den Bergh, Clerk at Kennedy, Trelea, Bratton at Blackwell , at Evers.

Ang isang simple at epektibong paraan upang piliin ang mga parameter ng pamamaraan ay iminungkahi ni Pedersen at iba pang mga may-akda. Nagsagawa rin sila ng mga numerical na eksperimento na may iba't ibang problema at parameter sa pag-optimize. Ang pamamaraan para sa pagpili ng mga parameter na ito ay tinatawag na meta-optimization, dahil ang ibang optimization algorithm ay ginagamit upang "i-tune" ang mga parameter ng MRF. Ang pinakamahusay na gumaganap na mga parameter ng input ng MFC ay natagpuan na salungat sa mga pangunahing prinsipyo na inilarawan sa panitikan at madalas na gumagawa ng mga kasiya-siyang resulta ng pag-optimize para sa mga simpleng kaso ng MFC. Ang kanilang pagpapatupad ay matatagpuan sa bukas na SwarmOps library.

Mga pagpipilian sa algorithm

Ang mga bagong variant ng particle swarm algorithm ay patuloy na iminungkahi upang mapabuti ang pagganap ng pamamaraan. Mayroong ilang mga uso sa pananaliksik na ito, ang isa ay nagmumungkahi ng paglikha ng isang hybrid na paraan ng pag-optimize gamit ang MRF kasama ng iba pang mga algorithm, tingnan ang halimbawa. Ang isa pang kalakaran ay nagmumungkahi sa paanuman na pabilisin ang pamamaraan, halimbawa, sa pamamagitan ng paglipat pabalik o pagbabago ng pagkakasunud-sunod ng paggalaw ng butil (para sa karagdagang impormasyon, tingnan). Mayroon ding mga pagtatangka na iakma ang mga parameter ng pag-uugali ng MRF sa panahon ng proseso ng pag-optimize.

Tingnan din

• Algoritmo ng pukyutan
• Gravitational Search Algorithm

Mga Tala

1. (1995) "Pag-optimize ng Particle Swarm". Mga Pamamaraan ng IEEE International Conference on Neural Networks IV: 1942-1948.
2. (1998) "Isang binagong particle swarm optimizer". Mga Pamamaraan ng IEEE International Conference on Evolutionary Computation: 69-73.
3. Swarm Intelligence. - Morgan Kaufmann, 2001.
4. Poli, R. (2007). "Isang pagsusuri ng mga publikasyon sa mga application sa pag-optimize ng particle swarm." Teknikal na Ulat CSM-469(Department of Computer Science, University of Essex, UK).
5. Poli, R. (2008). "Pagsusuri ng mga publikasyon sa mga aplikasyon ng particle swarm optimization". : 1-10. DOI:10.1155/2008/685175.
6. (1998) "Pagpili ng parameter sa pag-optimize ng kuyog ng butil". Mga Pamamaraan ng Evolutionary Programming VII (EP98): 591-600.
7. (2000) "Paghahambing ng inertia weights at constriction factors sa particle swarm optimization". Mga Pamamaraan ng Kongreso sa Evolutionary Computation 1 : 84-88.
8. (2001) "Isang Off-The-Shelf PSO". Mga Pamamaraan ng Particle Swarm Optimization Workshop: 1-6.
9. van den Bergh F. Isang Pagsusuri ng Mga Particle Swarm Optimizer. - Unibersidad ng Pretoria, Faculty ng Natural at Agricultural Science, 2001.
10. (2002) "Ang particle swarm - pagsabog, katatagan, at convergence sa isang multidimensional complex space." Mga Transaksyon ng IEEE sa Evolutionary Computation 6 (1): 58-73.
11. Trelea, I.C. (2003). "Ang Particle Swarm Optimization Algorithm: pagtatasa ng convergence at pagpili ng parameter." Mga Liham sa Pagproseso ng Impormasyon 85 : 317-325.
12. (2008) "Isang Pinasimpleng Recombinant PSO". Journal ng Artipisyal na Ebolusyon at Aplikasyon.
13. Evers G. Isang Awtomatikong Regrouping Mechanism para Maharap ang Stagnation sa Particle Swarm Optimization. - Ang Unibersidad ng Texas - Pan American, Departamento ng Electrical Engineering, 2009.
14. Pedersen M.E.H. Pag-tune at Pagpapasimple ng Heuristic Optimization. - University of Southampton, School of Engineering Sciences, Computational Engineering and Design Group, 2010.
15. Pedersen, M.E.H.; Chipperfield, A.J. (2010). "Pagpapasimple ng particle swarm optimization". Inilapat na Soft Computing 10 : 618-628.
16. (2002) "The LifeCycle Model: pinagsasama-sama ang particle swarm optimization, genetic algorithms at hillclimbers." Proceedings of Parallel Problem Solving from Nature VII (PPSN): 621-630.
17. (2010) "Isang mahusay na hybrid na diskarte batay sa PSO, ACO at k-means para sa pagsusuri ng kumpol." Inilapat na Soft Computing 10 (1): 183-197.
18. (2002) "Extending Particle Swarm Optimizer na may Self-Organized Criticality". Mga Pamamaraan ng Ikaapat na Kongreso sa Evolutionary Computation (CEC) 2 : 1588-1593.
19. Xinchao, Z. (2010). "Isang nababagabag na particle swarm algorithm para sa numerical optimization." Inilapat na Soft Computing 10 (1): 119-124.
20. (2009) "Adaptive Particle Swarm Optimization." Mga Transaksyon ng IEEE sa Mga Sistema, Tao, at Cybernetics 39 (6): 1362-1381.

Mga link

• Particle Swarm Central. Balita, tao, lugar, programa, artikulo, atbp. Sa partikular, tingnan ang kasalukuyang pamantayan ng MRF. (Ingles)
• SwarmOps. Parameter selection/calibration ng MRF at iba pang meta-optimization method. Software library sa mga wikang C at C#.
• Ang EvA2 ay isang komprehensibong open source na evolutionary optimization at MRM tool na nakasulat sa Java.
• Ang ParadisEO ay isang malakas na C++ na balangkas na idinisenyo para sa paglikha ng iba't ibang metaheuristics, kabilang ang mga algorithm ng MRF. Mga algorithm na handa nang gamitin, maraming mga tutorial na makakatulong sa iyong mabilis na lumikha ng sarili mong bersyon ng MRF.
• MFC code sa FORTRAN Pagsukat ng pagganap sa mga function ng pagsubok.
• - GPLed computational intelligence simulation at research environment na nakasulat sa Java, kasama ang iba't ibang mga pagpapatupad ng PSO
• Paggamit ng Python na pagpapatupad ng MRF upang malutas ang isang palaisipan sa pagtawid ng hagdanan.
• ECF - Evolutionary Computation Framework iba't ibang algorithm, genotypes, parallelization, textbook.