Մասնիկների հոտի մեթոդ. Մասնիկների հոտի մեթոդ Ալգորիթմի սխեման

«Մասնիկների հոտը»՝ որպես էվոլյուցիոն ծրագրավորման ամենապարզ մեթոդ, որը հիմնված է կենդանիների խմբերի վարքագծի մոդելավորման միջոցով օպտիմալացման խնդիրների լուծման հնարավորության գաղափարի վրա։ Ալգորիթմի սխեման, ծրագրային կոդի և սխեմայի կազմում:

Ուղարկել ձեր լավ աշխատանքը գիտելիքների բազայում պարզ է: Օգտագործեք ստորև ներկայացված ձևը

Ուսանողները, ասպիրանտները, երիտասարդ գիտնականները, ովքեր օգտագործում են գիտելիքների բազան իրենց ուսումնառության և աշխատանքի մեջ, շատ շնորհակալ կլինեն ձեզ:

Տեղադրված է http://www.allbest.ru/ կայքում

Ներածություն

Լամարկի ժամանակներից ի վեր կենդանի աշխարհի զարգացումը դիտարկվել է որպես շրջակա միջավայրի ազդեցության տակ գտնվող անհատների մշտական ​​կատարելագործման (ադապտացիայի) գործընթաց։ Լավագույն պլանների ընտրությունը որպես էվոլյուցիայի գործընթաց մոդելավորելով անհատների պոպուլյացիայի մեջ՝ հնարավոր է օպտիմալացման խնդրի լուծում ստանալ՝ սահմանելով էվոլյուցիոն գործընթացի սկզբնական պայմանները՝ վիրտուալ տիեզերքը բնակեցնելով տեղեկատվություն կրող արարածներով, և նշելով էվոլյուցիոն գործընթացի նպատակը:

Բնության գործողությունները պատճենելով՝ մարդը ստեղծում է ավելի ու ավելի առաջադեմ օպտիմալացման ալգորիթմներ։ Դրանց ստեղծման համար առավել հաճախ օգտագործվում են բնության օրինակներ, օրինակ՝ թռչունների գենետիկական ծածկագիրը կամ վարքագիծը, ձկան գաղթի մոդելավորումը կամ մետաղի սառեցումը և այլն։

Ներկայումս օպտիմիզացման ալգորիթմները լայնորեն կիրառվում են արտադրության և բիզնեսի մեջ, քանի որ դրանք հնարավորություն են տալիս խնայել ոչ միայն փողը, այլև ժամանակը, որը մշտապես պակասում է:

Արտադրության մեջ, օպտիմիզացիայի շնորհիվ, լուծվում են բազմաթիվ խնդիրներ, որոնք կապված են մեքենաների անգործության, պահեստի արտահոսքի կամ խափանման դեպքում պահեստամասերի վերահղման հետ:

Այս աշխատանքի համար ընտրվել է «մասնիկների պարս» օպտիմալացման մեթոդը։ Մեթոդի ալգորիթմը իր պարզության և արագության շնորհիվ համարվում է շատ խոստումնալից պլանավորման խնդիրների համար։

1 . Խնդրի ձևակերպում

1.1 Մաթեմատիկական մոդել

«Մասնիկների պարս» մեթոդը էվոլյուցիոն ծրագրավորման ամենապարզ մեթոդն է, որը հայտնվեց 90-ականների կեսերին՝ հիմնված այն մտքի վրա, որ հնարավոր է օպտիմալացման խնդիրները լուծել կենդանիների խմբերի վարքագծի մոդելավորման միջոցով։ Մեթոդը հիմնված է այն փաստի վրա, որ երամ կազմելիս թռչունները հակված են դեպի ինչ-որ «ծանրության կենտրոն»՝ աստիճանաբար դանդաղեցնելով իրենց թռիչքի արագությունը:

Երբ հոտը սնունդ է փնտրում, անդամները կստուգեն շրջակա տարածքը և պտտվում են հոտի շուրջը միմյանցից անկախ: Յուրաքանչյուր ներկայացուցիչ ունի շարժման մեջ ազատության կամ պատահականության աստիճան, ինչը նրան հնարավորություն է տալիս գտնել սննդի կուտակում։ Այսպիսով, նրանցից մեկը վաղ թե ուշ ուտելի բան կգտնի, իսկ հոտի մաս լինելով՝ մյուսներին կտեղեկացնի։ Մնացածը կարող է նաև մոտենալ սննդի աղբյուրին, և յուրաքանչյուր ներկայացուցիչ, իր շարժման ազատության և պատահականության աստիճանի շնորհիվ, կարող է գտնել սննդի նոր կուտակում։

Այս ալգորիթմի իրականացման ժամանակ բազմաչափ որոնման տարածքը բնակեցված է մասնիկների պարսով (տարրական լուծումներ): Տարածության մեջ մասնիկի կոորդինատները եզակիորեն որոշում են օպտիմալացման խնդրի լուծումը։ Բացի կոորդինատներից, յուրաքանչյուր մասնիկ նկարագրվում է իր շարժման արագությամբ և արագացումով։ Շարժման գործընթացում մասնիկները «սանրում» են լուծույթի տարածությունը և դրանով իսկ գտնում են ընթացիկ օպտիմալը, որին մնացած մասնիկները շտապում են հաջորդ քայլին: Յուրաքանչյուր մասնիկ հիշում է իր լավագույն դիրքը, որի մասին տվյալները փոխանցվում են հարևան մասնիկներին, որոնք ձգտում են այս արժեքին:

Որոնման գործընթացում պատահական բաղադրիչ ներմուծելու համար կարելի է ներառել «խելագար» մասնիկներ, որոնց շարժման օրենքը տարբերվում է մյուսների շարժման օրենքից։

2 . Ալգորիթմի իրականացում

2.1 Ալգորիթմի սխեման

Ալգորիթմն աշխատում է հետևյալ կերպ.

1. Ստեղծվում է մասնիկների սկզբնական «պատահական» պոպուլյացիա:

2. Յուրաքանչյուր մասնիկի համար հաշվարկվում է օբյեկտիվ ֆունկցիան:

3. Օբյեկտիվ ֆունկցիայի տեսանկյունից լավագույն մասնիկը հայտարարվում է «գրավչության կենտրոն»։

4. Բոլոր մասնիկների արագության վեկտորները շտապում են դեպի այս «կենտրոնը», և որքան հեռու է մասնիկը դրանից, այնքան մեծ է նրա արագացումը:

5. Հաշվարկվում են լուծույթի տարածության մասնիկների նոր կոորդինատները։

6. 2-5-րդ քայլերը կրկնվում են նշված քանակով կամ մինչև կանգառի պայմանը բավարարելը:

7. Վերջին «ծանրության կենտրոնը» հայտարարված է որպես հայտնաբերված օպտիմալ լուծում:

2. 2 Կոդծրագրերը

#ներառում

#ներառում

#ներառում

#ներառում

const int n=200;

const int m=200;

int i, j, k, t=200;

կրկնակի F (կրկնակի x)

վերադարձի հզորություն (pow(x, 3) - 125.2);

(կրկնակի V[n] [m];

կրկնակի ստորին_սահման=1, վերին_սահման=300;

կրկնակի best_pos[n] [m];

կրկնակի cel[n] [m]; // գենոտիպային զանգված

կրկնակի best_cel=1000; // լավագույն համաշխարհային արժեքը

const կրկնակի C1=0.7, C2=1.2, w=0.93;

կրկնակի **X=նոր կրկնակի*[n];

համար (i=0; i

X[i]=նոր կրկնակի[m];

srand (ժամանակ (NULL));

// մասնիկների դիրքի և արագությունների սկզբնավորում

համար (i=0; i

համար (j=0; j

X[i] [j]=ստորին_սահման + (վերին_սահման - ստորին_սահման)*rand()/RAND_MAX;

// Նախնականացում մասնիկների ամենավատ գենոտիպով

best_pos[i] [j]=1000;

համար (k=0; k

// լրացնում է գենոտիպերի զանգվածը

համար (i=0; i

համար (j=0; j

// ներկայիս գենոտիպի որոշում

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

// պահպանելով լավագույն գենոտիպի արժեքը յուրաքանչյուր մասնիկի համար

եթե (cel[i][j]

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

եթե (best_pos[i] [j]

best_cel=best_pos[i] [j];

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

// Թարմացնել մասնիկների արագությունները և դիրքերը

համար (i=0; i

համար (j=0; j

R1 = 1.*rand()/RAND_MAX;

R2 = 1.*rand()/RAND_MAX;

V[i] [j] = w*V[i] [j] + C1*R1*(լավագույն_cel - X[i] [j]) + C2*R2*(լավագույն_pos[i] [j] - X[i ][j]);

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

2.3 Ալգորիթմի բլոկային դիագրամ

Տեղադրված է http://www.allbest.ru/ կայքում

Տեղադրված է http://www.allbest.ru/ կայքում

3 . Օպտիմալացման ալգորիթմի բարդության տեսական գնահատում

Ալգորիթմի բարդությունը տեսականորեն գնահատելու համար անհրաժեշտ է որոշել տարրական գործողությունների քանակը, որոնք պետք է կատարվեն այս ալգորիթմի միջոցով խնդիրը լուծելու համար:

Տարրական գործողություններ ասելով մենք հասկանում ենք գործողություններ, որոնք կարող են ներկայացվել տվյալ լեզվի տարրական կառուցվածքների տեսքով (բայց պարտադիր չէ, որ մեկ մեքենայի հրամանի տեսքով), մասնավորապես, որպես մեկ տարրական գործողություն մենք կդիտարկենք հետևյալը.

1) հանձնարարական գործողություն աբ.

2) զանգվածի ինդեքսավորման գործողություն a[i];

3) թվաբանական գործողություններ *,/,-,+;

4) համեմատական ​​գործողություններ ա< b;

5) տրամաբանական գործողություններ կամ, և, ոչ:

For հանգույցը տարրական գործողություն չէ, քանի որ կարող է ներկայացվել որպես;

Այսպիսով, հանգույցի կառուցումը պահանջում է 2*N տարրական գործողություններ.

Ֆ «ցիկլ» = 2* Ն+ Ն* զ «օղակ մարմին»:

Այսպիսով, մեր ծրագրի համար մենք ստանում ենք.

F=9+ // հաստատուններ

2*200+200*(2*200+(8+6)*200)+ // դիրքի և արագությունների սկզբնավորում

2*200+200*(2*200+200*(2*200+200*(6+20))+ // լրացնում է գենոտիպերի և լավագույն արժեքների զանգվածը

2*200+200*(2*200+200*(4+4+10+2+16)) // արագությունների և դիրքերի թարմացում

Տեսական հաշվարկների արդյունքում այս ծրագրի բարդությունը եղել է F = 528800809 տարրական գործողություններ։

Եզրակացություն

ծրագրի ալգորիթմի մոդելավորում

Վերջերս սկսեցին հայտնվել բազմաթիվ նոր ալգորիթմներ, որոնք հիմնված են բնության իմիտացիայի վրա, բայց ոչ ամեն ալգորիթմ կարող է պարծենալ իրագործման նման հեշտությամբ և գաղափարի ինքնատիպությամբ: Մասնիկների բաշխման պատահականության և դրանց քաոսային շարժման պատճառով մի քանի կրկնություններում օպտիմալ լուծում գտնելու շատ մեծ հավանականություն կա՝ միաժամանակ խուսափելով տեղային օպտիմայից։

Նման ալգորիթմների հետագա զարգացումը նոր օպտիմալացման տեխնոլոգիաների և ընդհանրապես զարգացման բանալին է:

Օգտագործված աղբյուրների ցանկը

1. Ուլյանով Մ.Վ., Շեպտունով Մ.Վ. Մաթեմատիկական տրամաբանություն և ալգորիթմների տեսություն, մաս 2. Ալգորիթմների տեսություն. - M.: MGAPI, 2003. - 80 p.

2. Դասախոսության նշումներ «Մաթեմատիկական տրամաբանություն և ալգորիթմների տեսություն» առարկայի վերաբերյալ:

3. Գլոբալ օպտիմալացման ալգորիթմներ - տեսություն և կիրառություն:

4. http://ru.wikipedia.org

Տեղադրված է Allbest.ru-ում

Նմանատիպ փաստաթղթեր

Գծային ծրագրավորման խնդիրների առանձնահատկությունները. Գծային ծրագրավորման խնդիրների լուծման պարզ մեթոդ: Լեզվի, ծրագրավորման գործիքների, նույնացուցիչների ցանկի և ալգորիթմի բլոկային դիագրամի ընտրության հիմնավորում: Ծրագրի տրամաբանական դիագրամ.

թեզ, ավելացվել է 13.08.2011թ


Գրադարանի մշակում, որը թույլ կտա մոդելավորել մասնիկների դինամիկան եռաչափ գրաֆիկայում: Մշակման գործիքների և մեթոդների ընտրություն: Մասնիկների համակարգերի մոդելավորման տարբերակներ: Vertex shader մոդելավորում. Մասնիկների համակարգի և PSBehavior դասի դիագրամներ:

դասընթացի աշխատանք, ավելացվել է 02/07/2016 թ


Հիմնական վերլուծական հարաբերություններ. Բլոկային դիագրամ և խնդրի լուծման ալգորիթմ: Ստուգելով ալգորիթմի կատարումը ձեռքով: Փոփոխական նույնականացման աղյուսակ. Մուտքային և ելքային տպագրության ձևեր. Ծրագրի մշակում և վրիպազերծում: Ծրագրի հետ աշխատելու հրահանգներ.

դասընթացի աշխատանք, ավելացվել է 02/13/2012 թ


Գծային ծրագրավորման և օպտիմալացման հայեցակարգը: MathCAD համակարգում աշխատելու հիմունքները. Օգտագործողի միջերեսը, մուտքագրման լեզուն և տվյալների տեսակը: Համակարգչային մաթեմատիկական մոդելավորման փուլերը. MathCAD ծրագրի միջոցով օպտիմալացման խնդրի լուծման օրինակ։

դասընթացի աշխատանք, ավելացվել է 16.10.2011թ


MatLab ծրագրավորման միջավայրում միաչափ օպտիմիզացման խնդիր լուծելու (տրված ֆունկցիաների նվազագույն և առավելագույնը) լուծման համար ծրագրի ստեղծում ոսկե հատվածի մեթոդով, ալգորիթմի բլոկային դիագրամի կառուցում և ուսումնասիրված ֆունկցիաների գրաֆիկական պատկերում:

վերացական, ավելացվել է 14.06.2010թ


Դելֆի ծրագրավորման համակարգը, դրա բնութագրերը. Վերապատրաստման ծրագրի հիմնական պահանջները. «Մաթեմատիկա. 1-ին դասարան» ծրագրի ալգորիթմի բլոկ-սխեմայի կազմում. Վերապատրաստման ծրագրում լուծվող խնդիրների տեսակները. Համակարգի շահագործման նկարագրությունը, դրա համար հրահանգները:

դասընթացի աշխատանք, ավելացվել է 17.06.2015թ


Խնդիրների լուծման օպտիմիզացում՝ օգտագործելով եռացման ալգորիթմը: Օպտիմալացման տեսության վերլուծությունը որպես օբյեկտիվ ֆունկցիա: Գրադիենտ ծագման մեթոդ. Փոփոխականներ և եռացման ալգորիթմի նկարագրություն: Շրջիկ վաճառողի խնդրի ներկայացումը գրաֆիկի միջոցով: Խնդիրը փոփոխականների հասցնելը և դրա լուծումը:

դասընթացի աշխատանք, ավելացվել է 21.05.2015թ


Լիցքավորված մասնիկների շարժման մաթեմատիկական մոդելի կառուցում, իրականացում ալգորիթմական լեզվով համակարգչի միջոցով։ Թեմայի նկարագրությունը. Հակառակ լիցքավորված երկու մասնիկների փոխազդեցության մոդելավորում: Ծրագրի արդյունքներ, օգտագործողի ձեռնարկ.

դասընթացի աշխատանք, ավելացվել է 26.02.2015թ


Գծային հանրահաշվական հավասարումների համակարգի (SLAE) մատրիցայի փոխակերպումը Գաուսի ալգորիթմի միջոցով: Խնդրի լուծում՝ օգտագործելով պարզ կրկնման մեթոդ: Turbo Pascal ծրագրավորման լեզվով իրականացվող SLAE-ների լուծման ծրագրի բլոկային դիագրամի և տեքստի ստեղծում։

դասընթացի աշխատանք, ավելացվել է 15.06.2013թ


Pascal-ը որպես պրոֆեսիոնալ ծրագրավորման լեզու, որն անվանվել է ֆրանսիացի մաթեմատիկոս և փիլիսոփա Բլեզ Պասկալի պատվին, դրա զարգացման պատմությունը և ֆունկցիոնալ առանձնահատկությունները: Խնդիր՝ օգտագործելով երկչափ զանգված, կազմելով լուծման բլոկային դիագրամ:

MRF-ն օպտիմիզացնում է ֆունկցիան՝ պահպանելով հնարավոր լուծումների պոպուլյացիան, որը կոչվում է մասնիկներ, և տեղափոխելով այդ մասնիկները լուծման տարածության մեջ՝ համաձայն պարզ բանաձևի: Տեղաշարժերը ենթարկվում են այս տարածության մեջ հայտնաբերված լավագույն դիրքի սկզբունքին, որն անընդհատ փոխվում է, երբ մասնիկները գտնում են ավելի շահեկան դիրքեր։

Ալգորիթմ

Թող զ: ℝ n→ ℝ այն օբյեկտիվ ֆունկցիան է, որը պետք է նվազագույնի հասցվի, Ս- երամի մասնիկների թիվը, որոնցից յուրաքանչյուրը կապված է կոորդինատի հետ xես ∈ ℝ nլուծման տարածության և արագության մեջ vես ∈ ℝ n. Թող նաև էջ i-ն մասնիկի ամենահայտնի դիրքն է ես, Ա է- երամի ամենահայտնի վիճակը որպես ամբողջություն: Այնուհետև մասնիկների երամի մեթոդի ընդհանուր ձևը հետևյալն է.

• Յուրաքանչյուր մասնիկի համար ես = 1, …, Սանել:
  • Պատահական վեկտորի միջոցով ստեղծեք մասնիկի սկզբնական դիրքը xես ~ U(բ ահա, բ վեր), ունենալով բազմաչափ միատեսակ բաշխում։ բ ահաԵվ բ վերլուծումների տարածության ստորին և վերին սահմաններն են համապատասխանաբար:
  • Նշանակե՛ք մասնիկի ամենահայտնի դիրքը նրա սկզբնական արժեքին. էջես ← xես.
  • Եթե ​​( զ(էջ i)< զ(է)), այնուհետև թարմացրեք երամի ամենահայտնի վիճակը. է ← էջես.
  • Նշանակե՛ք մասնիկների արագության արժեք. vես ~ U(-(բ վեր-բ ահա), (բ վեր-բ ահա)).
• Քանի դեռ չի բավարարվել դադարեցման չափանիշը (օրինակ՝ հասնելով կրկնությունների նշված քանակին կամ օբյեկտիվ ֆունկցիայի պահանջվող արժեքին), կրկնել.
  • Յուրաքանչյուր մասնիկի համար ես = 1, …, Սանել:
    • Ստեղծեք պատահական վեկտորներ r p, r g~ U(0,1).
    • Թարմացնել մասնիկների արագությունը. vես ← ω v i + φ p r p×( էջես - x i) + φg r g×( է-x i), որտեղ × գործողությունը նշանակում է բաղադրիչի բազմապատկում:
    • Թարմացրեք մասնիկների դիրքը թարգմանությամբ x i արագության վեկտորի համար. xես ← xես+ vես. Նշենք, որ այս քայլը կատարվում է անկախ օբյեկտիվ ֆունկցիայի արժեքի բարելավումից:
    • Եթե ​​( զ(x i)< զ(էջ i)), ապա արեք.
      • Թարմացրեք մասնիկների ամենահայտնի դիրքը. էջես ← xես.
      • Եթե ​​( զ(էջ i)< զ(է)), այնուհետև թարմացրեք երամի ամենահայտնի վիճակը որպես ամբողջություն. է ← էջես.
• Հիմա էպարունակում է հայտնաբերված լավագույն լուծումը:

ω, φ p և φ g պարամետրերը ընտրվում են համակարգչի կողմից և որոշում են մեթոդի վարքն ու արդյունավետությունը որպես ամբողջություն: Այս պարամետրերը բազմաթիվ ուսումնասիրությունների առարկա են (տես ներքեւում).

Պարամետրերի ընտրություն

Մասնիկների պարանոցի մեթոդի համար օպտիմալ պարամետրերի ընտրությունը զգալի թվով հետազոտական ​​հոդվածների թեմա է, օրինակ, տե՛ս Շի և Էբերհարթի, Կարլայլի և Դոզերի, վան դեն Բերգի, Քլերքի և Քենեդու, Թրելեի, Բրատոնի և Բլեքվելի աշխատանքները: , և Էվերս.

Մեթոդի պարամետրերի ընտրության պարզ և արդյունավետ միջոց առաջարկվել է Պեդերսենի և այլ հեղինակների կողմից: Նրանք կատարել են նաև թվային փորձեր՝ օպտիմիզացման տարբեր խնդիրներով և պարամետրերով։ Այս պարամետրերի ընտրության տեխնիկան կոչվում է մետա-օպտիմալացում, քանի որ MRF պարամետրերը «կարգավորելու» համար օգտագործվում է օպտիմալացման այլ ալգորիթմ: Պարզվել է, որ MFC ներածման լավագույն պարամետրերը հակասում են գրականության մեջ նկարագրված հիմնական սկզբունքներին և հաճախ տալիս են օպտիմալացման բավարար արդյունքներ MFC պարզ դեպքերի համար: Դրանց իրականացումը կարելի է գտնել բաց SwarmOps գրադարանում:

Ալգորիթմի ընտրանքներ

Մեթոդի արդյունավետությունը բարելավելու համար մշտապես առաջարկվում են մասնիկների երախի ալգորիթմի նոր տարբերակներ: Այս հետազոտության մեջ կան մի քանի միտումներ, որոնցից մեկն առաջարկում է հիբրիդային օպտիմալացման մեթոդի ստեղծում՝ օգտագործելով MRF՝ այլ ալգորիթմների հետ համատեղ, տե՛ս օրինակ: Մեկ այլ միտում առաջարկում է ինչ-որ կերպ արագացնել մեթոդը, օրինակ՝ հետ շարժվելով կամ փոխելով մասնիկների շարժման կարգը (լրացուցիչ տեղեկությունների համար տե՛ս): Փորձեր են արվում նաև հարմարեցնել MRF-ի վարքային պարամետրերը օպտիմալացման գործընթացում:

Գրեք ակնարկ «Մասնիկների երախի մեթոդ» հոդվածի մասին

Նշումներ

1. (1995) «Particle Swarm Optimization». Նյարդային ցանցերի IEEE միջազգային կոնֆերանսի նյութեր IV: 1942-1948.
2. (1998) «Փոփոխված մասնիկների երամի օպտիմիզատոր». Էվոլյուցիոն հաշվարկի վերաբերյալ IEEE միջազգային կոնֆերանսի նյութեր: 69-73.
3. Swarm Intelligence. - Մորգան Կաուֆման, 2001 թ.
4. Poli, R. (2007). «». Տեխնիկական հաշվետվություն CSM-469(Համակարգչային գիտությունների ամբիոն, Էսեքսի համալսարան, Մեծ Բրիտանիա):
5. Poli, R. (2008). «». 1-10: DOI: 10.1155/2008/685175:
6. (1998) «Պարամետրերի ընտրությունը մասնիկների հոտի օպտիմալացման մեջ». Proceedings of Evolutionary Programming VII (EP98): 591-600.
7. (2000) «Համեմատելով իներցիայի կշիռները և կծկման գործոնները մասնիկների հոտի օպտիմալացման մեջ». Էվոլյուցիոն հաշվարկի կոնգրեսի նյութեր 1 : 84-88.
8. (2001) «An Off-The-Shelf PSO». Մասնիկների կուտակումների օպտիմալացման աշխատաժողովի նյութեր: 1-6.
9. վան դեն Բերգ Ֆ.Մասնիկների երամ օպտիմիզատորների վերլուծություն: - Պրետորիայի համալսարան, բնական և գյուղատնտեսական գիտությունների ֆակուլտետ, 2001 թ.
10. (2002) «Մասնիկների երամը՝ պայթյուն, կայունություն և կոնվերգենցիա բազմաչափ բարդ տարածության մեջ»: IEEE գործարքներ էվոլյուցիոն հաշվարկի վրա 6 (1): 58-73.
11. Trelea, I.C. (2003): «Մասնիկների կուտակումների օպտիմալացման ալգորիթմ. կոնվերգենցիայի վերլուծություն և պարամետրերի ընտրություն»: Տեղեկատվության մշակման նամակներ 85 : 317-325.
12. (2008) «Պարզեցված ռեկոմբինանտ PSO». Արհեստական ​​էվոլյուցիայի և հավելվածների ամսագիր.
13. Էվերս Գ.. - Տեխասի համալսարան - Pan American, Էլեկտրատեխնիկայի բաժին, 2009 թ.
14. Pedersen M.E.H.. - Սաութհեմփթոնի համալսարան, Ճարտարագիտական ​​գիտությունների դպրոց, Հաշվողական ճարտարագիտության և դիզայնի խումբ, 2010 թ.
15. Պեդերսեն, Մ.Է.Հ.; Չիպերֆիլդ, Ա.Ջ. (2010): «». Կիրառական փափուկ հաշվարկ 10 : 618-628.
16. (2002) «Կյանքի ցիկլի մոդել. միավորելով մասնիկների պարամի օպտիմալացումը, գենետիկական ալգորիթմները և լեռնագնացները»: Զուգահեռ խնդիրների լուծման նյութեր Բնությունից VII (PPSN): 621-630.
17. (2010) «Արդյունավետ հիբրիդային մոտեցում՝ հիմնված PSO-ի, ACO-ի և k-միջոցների վրա՝ կլաստերային վերլուծության համար»: Կիրառական փափուկ հաշվարկ 10 (1): 183-197.
18. (2002) «Extending Particle Swarm Optimisers with Self Organized Criticality». Էվոլյուցիոն հաշվարկի չորրորդ համագումարի (ԿԸՀ) նյութեր. 2 : 1588-1593.
19. Xinchao, Z. (2010). «Խանգարված մասնիկների պարամի ալգորիթմ թվային օպտիմալացման համար»: Կիրառական փափուկ հաշվարկ 10 (1): 119-124.
20. (2009) «Adaptive Particle Swarm Optimization»: IEEE գործարքներ համակարգերի, մարդու և կիբեռնետիկայի վերաբերյալ 39 (6): 1362-1381.

Հղումներ

• . Նորություններ, մարդիկ, վայրեր, հաղորդումներ, հոդվածներ և այլն: Մասնավորապես, տե՛ս ներկայիս MRF ստանդարտը: (անգլերեն)

Հատված, որը բնութագրում է Մասնիկների երախի մեթոդը

Նույն օրը երեկոյան Դենիսովի բնակարանում աշխույժ զրույց է տեղի ունեցել էսկադրիլիայի սպաների միջև։
«Եվ ես ասում եմ ձեզ, Ռոստով, որ դուք պետք է ներողություն խնդրեք գնդի հրամանատարից», - ասաց մոխրագույն մազերով, հսկայական բեղերով և կնճռոտ դեմքի խոշոր դիմագծերով մի բարձրահասակ շտաբի կապիտան, դառնալով բոսորագույն, հուզված Ռոստովը:
Շտաբի կապիտան Քիրսթենը պատվի հարցերով երկու անգամ իջեցվել է զինվորի և երկու անգամ ծառայել:
- Ես թույլ չեմ տա, որ որևէ մեկը ինձ ասի, որ ես ստում եմ: - Ռոստովը ճչաց. «Նա ինձ ասաց, որ ես ստում եմ, իսկ ես ասացի, որ ստում է»: Այդպես էլ կմնա։ Նա կարող է ինձ ամեն օր հերթապահել ու կալանքի տակ դնել, բայց ոչ ոք ինձ չի ստիպի ներողություն խնդրել, քանի որ եթե նա, որպես գնդի հրամանատար, իրեն անարժան է համարում ինձ բավարարվածություն տալու, ապա...
-Պարզապես սպասիր, հայրիկ; «Լսիր ինձ», - իր բաս ձայնով ընդհատեց շտաբը կապիտանը՝ հանգիստ հարթեցնելով երկար բեղերը։ -Մյուս սպաների աչքի առաջ գնդի հրամանատարին ասում եք, որ սպան գողացել է...
«Ես մեղավոր չեմ, որ խոսակցությունը սկսվեց մյուս սպաների առջև»։ Միգուցե ես չպետք է խոսեի նրանց առջև, բայց ես դիվանագետ չեմ. Հետո միացա հուսարներին, մտածեցի, որ նրբությունների կարիք չկա, բայց նա ինձ ասաց, որ ես ստում եմ... ուրեմն թող ինձ բավարարություն տա...
- Այս ամենը լավ է, ոչ ոք չի կարծում, որ դու վախկոտ ես, բայց հարցը դա չէ: Հարցրեք Դենիսովին, սա նման է մի բանի, որ կուրսանտը գնդի հրամանատարից գոհունակություն պահանջի։
Դենիսովը, կծելով բեղերը, մռայլ հայացքով լսեց խոսակցությունը՝ ըստ երևույթին չցանկանալով զբաղվել դրանով։ Կապիտանի անձնակազմի հարցմանը նա բացասաբար է շարժել գլուխը։
«Դուք գնդի հրամանատարին ասում եք սպաների աչքի առաջ այս կեղտոտ հնարքի մասին», - շարունակեց կապիտանը: - Բոգդանիչը (գնդի հրամանատարին Բոգդանիչ էին ասում) պաշարել է քեզ։
- Նա չպաշարեց նրան, այլ ասաց, որ ես սուտ եմ ասում:
- Դե, այո, և դու նրան հիմարություն ես ասել, և պետք է ներողություն խնդրես:
- Երբեք! - բղավեց Ռոստովը:
«Ես դա ձեզանից չէի մտածում», - լրջորեն և խստորեն ասաց կապիտանը: «Դու չես ուզում ներողություն խնդրել, բայց դու, հայրիկ, ոչ միայն նրա առջև, այլ ամբողջ գնդի, մեր բոլորի առաջ, դու լիովին մեղավոր ես»: Ահա թե ինչպես. եթե միայն մտածեիք և խորհրդակցեիք, թե ինչպես վարվել այս հարցի հետ, այլապես կխմեիք հենց սպաների աչքի առաջ։ Հիմա գնդի հրամանատարը ի՞նչ անի։ Պե՞տք է սպային դատեն ու ամբողջ գունդը կեղտոտվի՞։ Մի սրիկայի պատճառով ամբողջ գունդը խայտառակվա՞ծ է։ Այսպիսով, ինչ եք կարծում? Բայց մեր կարծիքով՝ այդպես չէ։ Իսկ Բոգդանիչը մեծ է, նա քեզ ասաց, որ դու սուտ ես ասում։ Տհաճ է, բայց ի՞նչ անես, հայրիկ, ինքդ հարձակվեցին քեզ վրա։ Եվ հիմա, քանի որ նրանք ուզում են լռեցնել այդ հարցը, ինչ-որ ֆանատիզմի պատճառով չես ուզում ներողություն խնդրել, այլ ուզում ես ամեն ինչ պատմել: Դուք վիրավորված եք, որ հերթապահում եք, բայց ինչո՞ւ պետք է ներողություն խնդրեք ծեր ու ազնիվ սպայից։ Ինչ էլ որ լինի Բոգդանիչը, նա դեռ ազնիվ և խիզախ ծեր գնդապետ է, ամոթ է ձեզ համար. Լա՞վ է, որ գունդը կեղտոտես։ - Նավապետի ձայնը սկսեց դողալ: -Դու, հայրիկ, մեկ շաբաթ է, ինչ գնդում ես; այսօր այստեղ, վաղը փոխանցված ադյուտանտներին ինչ-որ տեղ; ձեզ չի հետաքրքրում, թե ինչ են ասում. «Պավլոգրադի սպաների մեջ գողեր կան»: Բայց մենք հոգ ենք տանում: Դե ինչ, Դենիսով։ Նույնը չէ՞։
Դենիսովը լուռ մնաց և չշարժվեց՝ երբեմն-երբեմն իր փայլող սև աչքերով հայացք նետելով Ռոստովին։
«Դուք գնահատում եք ձեր սեփական երկրպագությունը, չեք ուզում ներողություն խնդրել,- շարունակեց շտաբի կապիտանը,- բայց մեր ծերերի համար, թե ինչպես ենք մենք մեծացել, և եթե նույնիսկ մահանանք, Աստծո կամոք, մեզ գունդ կբերեն, այնպես որ գնդի պատիվը մեզ համար թանկ է, և Բոգդանիչը դա գիտի»։ Ա՜խ, ի՜նչ ճանապարհ, հայրիկ։ Եվ սա լավ չէ, լավ չէ: Նեղանաք, թե ոչ, ես միշտ ճիշտը կասեմ. Ոչ լավ!
Իսկ շտաբի կապիտանը ոտքի կանգնեց ու շրջվեց Ռոստովից։
- Պգ «ավդա, չոգ» տար։ - վեր թռչելով բղավեց Դենիսովը: -Դե, Գ'կմախք:
Ռոստովը, կարմրելով և գունատվելով, նախ նայեց մի սպային, հետո՝ մյուսին։
- Ոչ, պարոնայք, ոչ... մի մտածեք... Ես իսկապես հասկանում եմ, դուք սխալվում եք, որ այդպես մտածում եք իմ մասին... ես... ինձ համար... Ես կողմ եմ պատիվին գունդը: Ես դա ցույց կտամ պրակտիկայում, և ինձ համար դրոշի պատիվը... դե, մեկ է, իսկապես, ես եմ մեղավոր... - Արցունքները կանգնեցին նրա աչքերում: - Ես մեղավոր եմ, ես մեղավոր եմ ամբողջ շրջապատում... Դե, էլ ի՞նչ է պետք...
«Ահա այն, կոմս», - բղավեց շտաբի կապիտանը, շրջվելով և մեծ ձեռքով հարվածելով նրա ուսին:
«Ես ձեզ ասում եմ,- բղավեց Դենիսովը,- նա գեղեցիկ փոքրիկ տղա է»:
«Դա ավելի լավ է, կոմս», - կրկնեց նավապետը, կարծես ճանաչման համար նրան սկսեցին կոչում անվանել: - Եկեք ներողություն խնդրեք, ձերդ գերազանցություն, այո պարոն։
«Պարոնայք, ես ամեն ինչ կանեմ, ոչ ոք ինձանից ոչ մի խոսք չի լսի», - ասաց Ռոստովը աղաչող ձայնով, - բայց ես չեմ կարող ներողություն խնդրել, Աստծո կողմից, չեմ կարող, ինչ ուզում եք: Ինչպես փոքրիկի պես ներողություն խնդրեմ՝ ներողություն խնդրելով։
Դենիսովը ծիծաղեց.
- Քեզ համար ավելի վատ է: Բոգդանիչը վրեժխնդիր է, դու կվճարես քո համառության համար»,- ասաց Քիրստենը։
-Աստված, ոչ թե համառություն։ Չեմ կարող քեզ նկարագրել, թե ինչ զգացողություն է, չեմ կարող...

Ալգորիթմ

Թող զ: ℝ n→ ℝ այն օբյեկտիվ ֆունկցիան է, որը պետք է նվազագույնի հասցվի, Ս- երամի մասնիկների թիվը, որոնցից յուրաքանչյուրը կապված է կոորդինատի հետ xես ∈ ℝ nլուծման տարածության և արագության մեջ vես ∈ ℝ n. Թող նաև էջ i-ն մասնիկի ամենահայտնի դիրքն է ես, Ա է- երամի ամենահայտնի վիճակը որպես ամբողջություն: Այնուհետև մասնիկների երամի մեթոդի ընդհանուր ձևը հետևյալն է.

• Յուրաքանչյուր մասնիկի համար ես = 1, …, Սանել:
  • Պատահական վեկտորի միջոցով ստեղծեք մասնիկի սկզբնական դիրքը xես ~ U(բ ահա, բ վեր), ունենալով բազմաչափ միատեսակ բաշխում։ բ ահաԵվ բ վերլուծումների տարածության ստորին և վերին սահմաններն են համապատասխանաբար:
  • Նշանակե՛ք մասնիկի ամենահայտնի դիրքը նրա սկզբնական արժեքին. էջես ← xես.
  • Եթե ​​( զ(էջ i)< զ(է)), այնուհետև թարմացրեք երամի ամենահայտնի վիճակը. է ← էջես.
  • Նշանակե՛ք մասնիկների արագության արժեք. vես ~ U(-(բ վեր-բ ահա), (բ վեր-բ ահա)).
• Քանի դեռ չի բավարարվել դադարեցման չափանիշը (օրինակ՝ հասնելով կրկնությունների նշված քանակին կամ օբյեկտիվ ֆունկցիայի պահանջվող արժեքին), կրկնել.
  • Յուրաքանչյուր մասնիկի համար ես = 1, …, Սանել:
    • Ստեղծեք պատահական վեկտորներ r p, r g~ U(0,1).
    • Թարմացնել մասնիկների արագությունը. vես ← ω v i + φ p r p×( էջես - x i) + φg r g×( է-x i), որտեղ × գործողությունը նշանակում է բաղադրիչի բազմապատկում:
    • Թարմացրեք մասնիկների դիրքը թարգմանությամբ x i արագության վեկտորի համար. xես ← xես+ vես. Նշենք, որ այս քայլը կատարվում է անկախ օբյեկտիվ ֆունկցիայի արժեքի բարելավումից:
    • Եթե ​​( զ(x i)< զ(էջ i)), ապա արեք.
      • Թարմացրեք մասնիկների ամենահայտնի դիրքը. էջես ← xես.
      • Եթե ​​( զ(էջ i)< զ(է)), այնուհետև թարմացրեք երամի ամենահայտնի վիճակը որպես ամբողջություն. է ← էջես.
• Հիմա էպարունակում է հայտնաբերված լավագույն լուծումը:

ω, φ p և φ g պարամետրերը ընտրվում են համակարգչի կողմից և որոշում են մեթոդի վարքն ու արդյունավետությունը որպես ամբողջություն: Այս պարամետրերը բազմաթիվ ուսումնասիրությունների առարկա են (տես ներքեւում).

Պարամետրերի ընտրություն

Մասնիկների պարանոցի մեթոդի համար օպտիմալ պարամետրերի ընտրությունը զգալի թվով հետազոտական ​​հոդվածների թեմա է, օրինակ, տե՛ս Շի և Էբերհարթի, Կարլայլի և Դոզերի, վան դեն Բերգի, Քլերքի և Քենեդու, Թրելեի, Բրատոնի և Բլեքվելի աշխատանքները: , և Էվերս.

Մեթոդի պարամետրերի ընտրության պարզ և արդյունավետ միջոց առաջարկվել է Պեդերսենի և այլ հեղինակների կողմից: Նրանք կատարել են նաև թվային փորձեր՝ օպտիմիզացման տարբեր խնդիրներով և պարամետրերով։ Այս պարամետրերի ընտրության տեխնիկան կոչվում է մետա-օպտիմալացում, քանի որ MRF պարամետրերը «կարգավորելու» համար օգտագործվում է օպտիմալացման այլ ալգորիթմ: Պարզվել է, որ MFC ներածման լավագույն պարամետրերը հակասում են գրականության մեջ նկարագրված հիմնական սկզբունքներին և հաճախ տալիս են օպտիմալացման բավարար արդյունքներ MFC պարզ դեպքերի համար: Դրանց իրականացումը կարելի է գտնել բաց SwarmOps գրադարանում:

Ալգորիթմի ընտրանքներ

Մեթոդի արդյունավետությունը բարելավելու համար մշտապես առաջարկվում են մասնիկների երախի ալգորիթմի նոր տարբերակներ: Այս հետազոտության մեջ կան մի քանի միտումներ, որոնցից մեկն առաջարկում է հիբրիդային օպտիմալացման մեթոդի ստեղծում՝ օգտագործելով MRF՝ այլ ալգորիթմների հետ համատեղ, տե՛ս օրինակ: Մեկ այլ միտում առաջարկում է ինչ-որ կերպ արագացնել մեթոդը, օրինակ՝ հետ շարժվելով կամ փոխելով մասնիկների շարժման կարգը (լրացուցիչ տեղեկությունների համար տե՛ս): Փորձեր են արվում նաև հարմարեցնել MRF-ի վարքային պարամետրերը օպտիմալացման գործընթացում:

տես նաեւ

• Bee ալգորիթմ
• Գրավիտացիոն որոնման ալգորիթմ

Նշումներ

1. (1995) «Particle Swarm Optimization». Նյարդային ցանցերի IEEE միջազգային կոնֆերանսի նյութեր IV: 1942-1948.
2. (1998) «Փոփոխված մասնիկների երամի օպտիմիզատոր». Էվոլյուցիոն հաշվարկի վերաբերյալ IEEE միջազգային կոնֆերանսի նյութեր: 69-73.
3. Swarm Intelligence. - Մորգան Կաուֆման, 2001 թ.
4. Poli, R. (2007). «Մասնիկների կուտակումների օպտիմալացման հավելվածների վերաբերյալ հրապարակումների վերլուծություն»: Տեխնիկական հաշվետվություն CSM-469(Համակարգչային գիտությունների ամբիոն, Էսեքսի համալսարան, Մեծ Բրիտանիա):
5. Poli, R. (2008). «Մասնիկների պարանոցի օպտիմալացման կիրառությունների վերաբերյալ հրապարակումների վերլուծություն». 1-10: DOI: 10.1155/2008/685175:
6. (1998) «Պարամետրերի ընտրությունը մասնիկների հոտի օպտիմալացման մեջ». Proceedings of Evolutionary Programming VII (EP98): 591-600.
7. (2000) «Համեմատելով իներցիայի կշիռները և կծկման գործոնները մասնիկների հոտի օպտիմալացման մեջ». Էվոլյուցիոն հաշվարկի կոնգրեսի նյութեր 1 : 84-88.
8. (2001) «An Off-The-Shelf PSO». Մասնիկների կուտակումների օպտիմալացման աշխատաժողովի նյութեր: 1-6.
9. վան դեն Բերգ Ֆ.Մասնիկների երամ օպտիմիզատորների վերլուծություն: - Պրետորիայի համալսարան, բնական և գյուղատնտեսական գիտությունների ֆակուլտետ, 2001 թ.
10. (2002) «Մասնիկների երամը՝ պայթյուն, կայունություն և կոնվերգենցիա բազմաչափ բարդ տարածության մեջ»: IEEE գործարքներ էվոլյուցիոն հաշվարկի վրա 6 (1): 58-73.
11. Trelea, I.C. (2003): «Մասնիկների կուտակումների օպտիմալացման ալգորիթմ. կոնվերգենցիայի վերլուծություն և պարամետրերի ընտրություն»: Տեղեկատվության մշակման նամակներ 85 : 317-325.
12. (2008) «Պարզեցված ռեկոմբինանտ PSO». Արհեստական ​​էվոլյուցիայի և հավելվածների ամսագիր.
13. Էվերս Գ.Ավտոմատ վերախմբավորման մեխանիզմ՝ մասնիկների կուտակումների օպտիմիզացման լճացման դեմ: - Տեխասի համալսարան - Pan American, Էլեկտրատեխնիկայի բաժին, 2009 թ.
14. Pedersen M.E.H.Կարգավորում և պարզեցում էվրիստիկական օպտիմալացում: - Սաութհեմփթոնի համալսարան, Ճարտարագիտական ​​գիտությունների դպրոց, Հաշվողական ճարտարագիտության և դիզայնի խումբ, 2010 թ.
15. Պեդերսեն, Մ.Է.Հ.; Չիպերֆիլդ, Ա.Ջ. (2010): «Պարզեցված մասնիկների պարանոցի օպտիմալացում»: Կիրառական փափուկ հաշվարկ 10 : 618-628.
16. (2002) «Կյանքի ցիկլի մոդել. միավորելով մասնիկների պարամի օպտիմալացումը, գենետիկական ալգորիթմները և լեռնագնացները»: Զուգահեռ խնդիրների լուծման նյութեր Բնությունից VII (PPSN): 621-630.
17. (2010) «Արդյունավետ հիբրիդային մոտեցում՝ հիմնված PSO-ի, ACO-ի և k-միջոցների վրա՝ կլաստերային վերլուծության համար»: Կիրառական փափուկ հաշվարկ 10 (1): 183-197.
18. (2002) «Extending Particle Swarm Optimisers with Self Organized Criticality». Էվոլյուցիոն հաշվարկի չորրորդ համագումարի (ԿԸՀ) նյութեր. 2 : 1588-1593.
19. Xinchao, Z. (2010). «Խանգարված մասնիկների պարամի ալգորիթմ թվային օպտիմալացման համար»: Կիրառական փափուկ հաշվարկ 10 (1): 119-124.
20. (2009) «Adaptive Particle Swarm Optimization»: IEEE գործարքներ համակարգերի, մարդու և կիբեռնետիկայի վերաբերյալ 39 (6): 1362-1381.

Հղումներ

• Particle Swarm Central. Նորություններ, մարդիկ, վայրեր, հաղորդումներ, հոդվածներ և այլն: Մասնավորապես, տե՛ս ներկայիս MRF ստանդարտը: (անգլերեն)
• SwarmOps. MRF-ի և մետաօպտիմալացման այլ մեթոդների պարամետրերի ընտրություն/չափորոշում: Ծրագրային գրադարան C և C# լեզուներով:
• EvA2-ը համապարփակ բաց կոդով էվոլյուցիոն օպտիմալացման և MRM գործիք է, որը գրված է Java-ով:
• ParadisEO-ն հզոր C++ շրջանակ է, որը նախատեսված է տարբեր մետահևրիստիկաներ ստեղծելու համար, ներառյալ MRF ալգորիթմները: Օգտագործման համար պատրաստի ալգորիթմներ, բազմաթիվ ձեռնարկներ, որոնք օգնում են ձեզ արագ ստեղծել MRF-ի ձեր սեփական տարբերակը:
• MFC կոդը FORTRAN-ում: Փորձարկման գործառույթների վրա կատարողականի չափում:
• - GPLed հաշվողական հետախուզության մոդելավորում և հետազոտական ​​միջավայր, որը գրված է Java-ով, ներառում է PSO-ի տարբեր իրականացումներ
• MRF-ի Python ներդրման օգտագործումը սանդուղքների հատման գլուխկոտրուկը լուծելու համար:
• ECF - Evolutionary Computation Framework տարբեր ալգորիթմներ, գենոտիպեր, զուգահեռացում, դասագրքեր: