Бөлшектер тобы әдісі. Бөлшектер үйірмесі әдісі Алгоритм сұлбасы

Жануарлар топтарының мінез-құлқын модельдеу арқылы оңтайландыру мәселелерін шешу мүмкіндігі идеясына негізделген эволюциялық бағдарламалаудың қарапайым әдісі ретінде «бөлшектердің тобы». Алгоритмнің схемасы, программалық кодты және блок-схеманы құрастыру.

Жақсы жұмысыңызды білім қорына жіберу оңай. Төмендегі пішінді пайдаланыңыз

Білім қорын оқу мен жұмыста пайдаланатын студенттер, аспиранттар, жас ғалымдар сізге шексіз алғысын білдіреді.

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(pow(x, 3) - 125,2);

(қос V[n] [м];

қос төменгі_шегі=1, жоғарғы_шегі=300;

double best_pos[n] [m];

қос cel[n][m]; // генотип массиві

double best_cel=1000; // ең жақсы жаһандық мән

const қос C1=0,7, C2=1,2, w=0,93;

қос **X=жаңа қос*[n];

үшін (i=0; i

X[i]=жаңа қос[м];

srand(уақыт(NULL));

// бөлшектердің орнын және жылдамдықтарын инициализациялау

үшін (i=0; i

үшін (j=0; j

X[i] [j]=төменгі_шек + (жоғарғы_шек - төменгі_шек)*ранд()/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*(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 Алгоритмнің блок-схемасы

http://www.allbest.ru/ сайтында орналасқан.

http://www.allbest.ru/ сайтында орналасқан.

3 . Оңтайландыру алгоритмінің күрделілігін теориялық бағалау

Алгоритмнің күрделілігін теориялық бағалау үшін осы алгоритмді пайдаланып есепті шешу үшін орындалатын элементар операциялардың санын анықтау қажет.

Элементарлы операциялар деп біз берілген тілдің элементарлық конструкциялары түрінде (бірақ бір ғана машиналық команда түрінде міндетті емес) бейнеленуі мүмкін операцияларды түсінеміз, атап айтқанда, бір элементар операция ретінде мыналар қарастырылады:

1) тағайындау операциясы ab;

2) a[i] массивін индекстеу операциясы;

3) *,/,-,+ арифметикалық амалдар;

4) салыстыру операциялары а< b;

5) логикалық амалдар немесе, және, емес.

for циклі қарапайым операция емес, өйткені ретінде көрсетуге болады;

Осылайша, циклды құру үшін 2*N элементар операциялар қажет:

Ф «цикл» = 2* Н+ Н* f цикл денесі.

Осылайша, біздің бағдарламамыз үшін біз мыналарды аламыз:

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 бөлім: Алгоритм теориясы. – М.: МГАПИ, 2003. – 80 б.

2. «Математикалық логика және алгоритмдер теориясы» пәні бойынша дәріс конспектісі.

3. Жаһандық оңтайландыру алгоритмдері – Теория және қолдану.

4. http://ru.wikipedia.org

Allbest.ru сайтында орналастырылған

Ұқсас құжаттар

Сызықтық программалау есептерінің ерекшеліктері. Сызықтық программалау есептерін шешудің симплекс әдісі. Тілді таңдаудың негіздемесі, программалау құралдары, идентификаторлар тізімі және алгоритмнің блок-схемасы. Программаның логикалық схемасы.

диссертация, 13.08.2011 қосылған


Үш өлшемді графикадағы бөлшектердің динамикасын имитациялауға мүмкіндік беретін кітапхананы әзірлеу. Даму құралдары мен әдістерін таңдау. Бөлшектік жүйелерді модельдеу нұсқалары. Төбенің шейдерінде модельдеу. Бөлшектер жүйесінің диаграммалары және PSBehavior класы.

курстық жұмыс, 07.02.2016 қосылған


Негізгі аналитикалық қатынастар. Блок-схема және есепті шешу алгоритмі. Алгоритмнің өнімділігін қолмен тексеру. Айнымалыларды анықтау кестесі. Енгізу және шығаруды басып шығару формалары. Бағдарламаны әзірлеу және жөндеу. Бағдарламамен жұмыс істеу нұсқаулары.

курстық жұмыс, 13.02.2012 қосылған


Сызықтық бағдарламалау және оңтайландыру түсінігі. MathCAD жүйесіндегі жұмыс негіздері. Пайдаланушы интерфейсі, енгізу тілі және деректер түрі. Компьютерлік математикалық модельдеу кезеңдері. MathCAD бағдарламасы арқылы оңтайландыру есебін шешудің мысалы.

курстық жұмыс, 16.10.2011 қосылған


MatLab программалау ортасында алтын қима әдісін қолданып бір өлшемді оңтайландыру (берілген функциялардың минимумы мен максимумын табу) есебін шешуге арналған бағдарлама құру, алгоритмнің блок-схемасын құру және зерттелетін функцияларды графикалық бейнелеу.

аннотация, 14.06.2010 қосылған


Delphi программалау жүйесі, оның сипаттамалары. Оқыту бағдарламасына қойылатын негізгі талаптар. «Математика. 1-сынып» бағдарламасының алгоритмінің блок-схемасын құрастыру. Оқыту бағдарламасында шешілетін тапсырмалардың түрлері. Жүйе жұмысының сипаттамасы, оған нұсқаулар.

курстық жұмыс, 17.06.2015 жылы қосылған


Жасыту алгоритмі арқылы есептің шешімін оңтайландыру. Оптимизация теориясын мақсаттық функция ретінде талдау. Градиентті түсіру әдісі. Айнымалылар және күйдіру алгоритмінің сипаттамасы. Саяхатшы сатушы есебін график арқылы көрсету. Мәселені айнымалыларға келтіру және шешу.

курстық жұмыс, 21.05.2015 қосылған


Зарядталған бөлшектер қозғалысының математикалық моделін құру, компьютерді қолдану арқылы алгоритмдік тілде жүзеге асыру. Пән аймағының сипаттамасы. Қарама-қарсы зарядталған екі бөлшектің әрекеттесуін модельдеу. Бағдарлама нәтижелері, пайдаланушы нұсқаулығы.

курстық жұмыс, 26.02.2015 жылы қосылған


Гаусс алгоритмі арқылы сызықтық алгебралық теңдеулер жүйесін (SLAE) матрицалық түрлендіру. Қарапайым итерация әдісімен есепті шешу. Turbo Pascal программалау тілінде іске асырылған SLAE шешуге арналған программаның блок-схемасын және мәтінін құру.

курстық жұмыс, 15.06.2013 қосылған


Паскаль тілі француз математигі және философы Блез Паскальдың атымен аталған кәсіби бағдарламалау тілі ретінде, оның даму тарихы мен функционалдық ерекшеліктері. Екі өлшемді массивтің көмегімен есеп, шешімнің блок-схемасын құрастыру.

MFR бөлшектер деп аталатын ықтимал шешімдердің популяциясын сақтау және қарапайым формула бойынша осы бөлшектерді ерітінді кеңістігінде жылжыту арқылы функцияны оңтайландырады. Қозғалыстар осы кеңістікте табылған ең жақсы позиция принципіне бағынады, ол бөлшектер неғұрлым қолайлы позицияларды тапқан кезде үнемі өзгереді.

Алгоритм

Болсын f: ℝ n→ ℝ - минимумға келтірілетін мақсат функциясы, С- үйірдегі бөлшектердің саны, олардың әрқайсысы координатамен байланысты x i ∈ ℝ nшешім кеңістігінде және жылдамдықта v i ∈ ℝ n. Сондай-ақ болсын б i - бөлшектің ең белгілі орны мен, А gжалпы үйірдің ең белгілі күйі болып табылады. Сонда бөлшектер үйірмесі әдісінің жалпы түрі келесідей.

• Әрбір бөлшек үшін мен = 1, …, Сістеу:
  • Кездейсоқ вектор көмегімен бөлшектің бастапқы орнын жасаңыз xмен ~ У(б т.б, б жоғары) көпөлшемді біркелкі бөлуге ие. б т.бЖәне б жоғарысәйкесінше шешім кеңістігінің төменгі және жоғарғы шекаралары болып табылады.
  • Ең жақсы белгілі бөлшектердің орнын оның бастапқы мәніне тағайындаңыз: бмен ← xмен.
  • егер ( f(би)< f(g)), содан кейін топтың ең белгілі күйін жаңартыңыз: g ← бмен.
  • Бөлшектердің жылдамдығының мәнін тағайындаңыз: vмен ~ У(-(б жоғары-б т.б), (б жоғары-б т.б)).
• Тоқтату критерийі орындалғанша (мысалы, берілген итерация санына немесе мақсат функциясының қажетті мәніне жеткенше) қайталаңыз:
  • Әрбір бөлшек үшін мен = 1, …, Сістеу:
    • Кездейсоқ векторларды құру r p , r g~ У(0,1).
    • Бөлшектердің жылдамдығын жаңарту: v i ← w v i + φp r p×( бмен- x i) + φ г r g×( g-x i), мұндағы × операциясы құрамдас бөліктерге көбейтуді білдіреді.
    • Бөлшектердің орнын аударма арқылы жаңартыңыз x i жылдамдық векторына: xмен ← x i + vмен. Бұл қадам мақсат функциясының мәнін жақсартуға қарамастан орындалатынын ескеріңіз.
    • егер ( f(xи)< f(б i)), содан кейін орындаңыз:
      • Ең белгілі бөлшектердің орнын жаңартыңыз: бмен ← xмен.
      • егер ( f(би)< f(g)), содан кейін жалпы тобының ең белгілі күйін жаңартыңыз: g ← бмен.
• Қазір gтабылған шешімдердің ең жақсысын қамтиды.

ω, φ p және φ g параметрлерін калькулятор таңдайды және тұтастай әдістің әрекеті мен тиімділігін анықтайды. Бұл параметрлер көптеген зерттеулердің нысаны болып табылады. (төменде қараңыз).

Параметрлерді таңдау

Бөлшектер тобының әдісі үшін оңтайлы параметрлерді таңдау көптеген зерттеу жұмыстарының тақырыбы болып табылады, мысалы, Ши мен Эберхарттың, Карлайл мен Дозердің, ван ден Бергтің, Клерк пен Кеннедидің, Трелеяның, Браттон мен Блэквеллдің және Evers.

Әдістің параметрлерін таңдаудың қарапайым және тиімді әдісін Педерсен және басқа авторлар ұсынған. Олар сондай-ақ әртүрлі оңтайландыру мәселелерімен және параметрлерімен сандық эксперименттер жүргізді. Бұл параметрлерді таңдау әдістемесі мета оңтайландыру деп аталады, өйткені MFR параметрлерін «баптау» үшін басқа оңтайландыру алгоритмі қолданылады. Ең жақсы өнімділігі бар MFM кіріс параметрлері әдебиетте сипатталған негізгі принциптерге қайшы екендігі дәлелденді және көбінесе MFM қарапайым жағдайлары үшін қанағаттанарлық оңтайландыру нәтижелерін береді. Олардың орындалуын SwarmOps ашық бастапқы кітапханасынан табуға болады.

Алгоритм опциялары

Әдістің өнімділігін жақсарту үшін бөлшектер тобының алгоритмінің жаңа нұсқалары үнемі ұсынылып отырады. Бұл зерттеулерде бірнеше тенденциялар бар, олардың бірі басқа алгоритмдермен үйлесімде MFR пайдалана отырып, гибридті оңтайландыру әдісін құруды ұсынады, мысалы, қараңыз. Тағы бір тенденция - бұл әдісті қандай да бір жолмен жылдамдату, мысалы, артқа шегіну немесе бөлшектер қозғалысының ретін өзгерту (бұл туралы қараңыз). Оңтайландыру процесі кезінде MFR мінез-құлық параметрлерін бейімдеу әрекеттері де бар.

«Бөлшектер тобы әдісі» мақаласына пікір жазыңыз.

Ескертпелер

1. (1995) «Бөлшектер тобын оңтайландыру». Нейрондық желілер бойынша IEEE халықаралық конференциясының материалдары IV: 1942-1948.
2. (1998) «Өзгертілген бөлшектер тобын оңтайландырушы». Эволюциялық есептеулер бойынша IEEE халықаралық конференциясының материалдары: 69-73.
3. Үйір интеллект. - Морган Кауфман, 2001 ж.
4. Поли, Р. (2007). "". Техникалық есеп CSM-469(Информатика кафедрасы, Эссекс университеті, Ұлыбритания).
5. Поли, Р. (2008). "". : 1-10. DOI: 10.1155/2008/685175.
6. (1998) «Бөлшектер тобын оңтайландыруда параметрді таңдау». Эволюциялық бағдарламалау материалдары VII (EP98): 591-600.
7. (2000) «Бөлшектер тобын оңтайландырудағы инерция салмағы мен тарылу факторларын салыстыру». Эволюциялық есептеулер конгресінің материалдары 1 : 84-88.
8. (2001) «Сақтаудан тыс PSO». Бөлшектер тобын оңтайландыру семинарының материалдары: 1-6.
9. Ван ден Берг Ф.Бөлшектер тобын оңтайландырушылардың талдауы. - Претория университеті, жаратылыстану және ауылшаруашылық ғылымдары факультеті, 2001 ж.
10. (2002) «Бөлшектер тобы - көпөлшемді күрделі кеңістіктегі жарылыс, тұрақтылық және конвергенция». Эволюциялық есептеулер бойынша IEEE транзакциялары 6 (1): 58-73.
11. Trelea, I.C. (2003). «Бөлшектер тобын оңтайландыру алгоритмі: конвергенциялық талдау және параметрді таңдау». Ақпаратты өңдеу хаттары 85 : 317-325.
12. (2008) «Жеңілдетілген рекомбинантты PSO». Жасанды эволюция және қолданбалар журналы.
13. Эверс Г.. - Техас университеті - Панамерикандық, Электротехника бөлімі, 2009 ж.
14. Педерсен М.Е.Х.. - Саутгемптон университеті, Инженерлік ғылымдар мектебі, Есептеу техникасы және жобалау тобы, 2010 ж.
15. Педерсен, M.E.H.; Чипперфилд, А.Дж. (2010). "". Қолданбалы жұмсақ есептеулер 10 : 618-628.
16. (2002) «Өмірлік цикл моделі: бөлшектер тобын оңтайландыруды, генетикалық алгоритмдерді және альпинистерді біріктіру». Табиғаттан параллель есептерді шешу материалдары VII (PPSN): 621-630.
17. (2010) «Кластерлік талдау үшін PSO, ACO және k-құралдарына негізделген тиімді гибридті тәсіл». Қолданбалы жұмсақ есептеулер 10 (1): 183-197.
18. (2002) «Өздігінен ұйымдастырылған сынилікпен бөлшектер тобын оптимизаторларын кеңейту». Эволюциялық есептеулер бойынша төртінші конгресстің материалдары (CEC) 2 : 1588-1593.
19. Синчао, З. (2010). «Сандық оңтайландыруға арналған бұзылған бөлшектер тобының алгоритмі». Қолданбалы жұмсақ есептеулер 10 (1): 119-124.
20. (2009) Бейімделетін бөлшектер тобын оңтайландыру. Жүйелер, адам және кибернетика бойынша IEEE транзакциялары 39 (6): 1362-1381.

Сілтемелер

• . Жаңалықтар, адамдар, орындар, бағдарламалар, мақалалар және т.б. Атап айтқанда, ағымдағы MFR стандартын қараңыз. (ағылшын)

Бөлшектер тобы әдісін сипаттайтын үзінді

Сол күні кешке Денисовтың пәтерінде эскадрилья офицерлерінің арасында қызу әңгіме жүріп жатты.
«Бірақ мен сізге айтамын, Ростов, полк командирінен кешірім сұрауыңыз керек», - деді қызыл қызыл, қобалжыған Ростовқа бұрылып, шашы ағарған, үлкен мұрты және мыжылған беті бар жоғары штаб капитаны. .
Штаб капитаны Кирстен екі рет жауынгерлерге құрметті істері үшін төмендетілді және екі рет емделді.
«Мен өтірік айтып тұрғанымды ешкімге айтпаймын! — деп айқайлады Ростов. Ол маған өтірік айтты, мен оған өтірік айттым дедім. Және солай қалады. Олар мені күн сайын кезекшілікке қойып, қамауға алады, бірақ мені ешкім кешірім сұрауға мәжбүрлемейді, өйткені ол полк командирі ретінде өзін мені қанағаттандыруға лайық емес деп санаса, онда ...
– Иә, күте тұрыңыз, әке; Сіз мені тыңдаңыз, - капитан ұзын мұртын жайбарақат тегістеп, бас дауысымен таяқтың сөзін бөлді. - Сіз полк командиріне басқа офицерлердің көзінше офицер ұрлағанын айтасыз ...
– Әңгіменің басқа офицерлердің көзінше басталуы менің кінәм емес. Бәлкім, олардың алдында сөз айтпауым керек еді, бірақ мен дипломат емеспін. Мен гусарларға қосылдым да, мұнда нәзіктіктердің қажеті жоқ деп ойлап, бардым, бірақ ол маған өтірік айтып жатқанымды айтты ... сондықтан ол маған қанағаттансын ...
– Ештеңе емес, сені қорқақ деп ешкім ойламайды, бірақ мәселе онда емес. Денисовтан сұраңыз, полк командирінен қанағаттануды талап ету курсант үшін бірдеңе сияқты ма?
Мұртын тістеген Денисов әңгімені мұңайған кейіппен тыңдады, оған араласқысы келмеген сияқты. Капитанның қызметкерлері сұрағанда, ол теріс басын шайқады.
«Сіз полк командирімен офицерлердің көзінше осы арамдық туралы айтып отырсыз», - деп жалғастырды штаб капитаны. – Богданич (Богданич полк командирі деп аталды) сізді қоршауға алды.
- Ол қоршап алған жоқ, бірақ өтірік айтып жатырмын деді.
- Иә, сен оған ақымақтық айттың, кешірім сұрауың керек.
- Ешқашан! — деп айғайлады Ростов.
«Мен бұл сізден деп ойламадым», - деді штаб капитаны байсалды және қатаң түрде. – Кешірім сұрағың келмей, сен, әке, оның алдында ғана емес, бүкіл полк алдында, бәріміздің алдында айналаңа кінәлісің. Міне, мынау: егер сіз бұл мәселені қалай шешуге болатынын ойлап, кеңессеңіз, әйтпесе сіз тікелей, бірақ офицерлердің алдында ұрып-соғып. Полк командирі енді не істеуі керек? Офицерді сотқа беріп, бүкіл полкті бүлдіруіміз керек пе? Бір жауыздың кесірінен бүкіл полк ұятқа қалды ма? Сонымен, сіз қалай ойлайсыз? Бірақ біздің ойымызша олай емес. Ал жарайсың Богданич, сен шындықты айтпайсың деп айтты. Бұл жағымсыз, бірақ не істеу керек, әке, олар өздері соқтығысты. Ал енді олар істі жабуды қалайды, сондықтан сіз де қандай да бір фанатизмнің кесірінен кешірім сұрағыңыз келмей, бәрін айтқыңыз келеді. Кезекшілікте жүргеніңе ренжідің, ал қарт, адал офицерден кешірім сұрауың керек! Богданич қандай болса да, бәрі де адал да батыл, қарт полковник, сіз қатты ренжідіңіз; ал полкті бүлдіру саған жарай ма? – капитан таяқшасының дауысы дірілдей бастады. - Сіз, әке, жылсыз бір апта полктасыз; бүгін осында, ертең олар бір жерде адъютанттарға көшті; Олардың: «Павлоградтық офицерлердің арасында ұрылар бар!» - деп айтатындарына мән бермейсіз. Ал бізге бәрібір. Сонымен, не, Денисов? Бәрі бірдей емес пе?
Денисов үндемей, орнынан қозғалмады, анда-санда жарқыраған қара көздерімен Ростовқа жалт қарады.
«Сізге өз фанатизміңіз қымбат, кешірім сұрағыңыз келмейді, - деп жалғастырды штаб капитаны, - бірақ біз қарттар, қалай өскенбіз, Құдай қаласа, полкте өлеміз, сондықтан полктің абыройы. біз үшін қымбат, оны Богданич біледі. О, қандай қымбатты, әке! Және бұл жақсы емес, жақсы емес! Онда ренжімеңіз бе, жоқ па, бірақ мен әрқашан жатырқа шындықты айтамын. Дұрыс емес!
Ал капитанның штабы орнынан тұрып, Ростовтан бұрылды.
- Pg "авда, чог" алыңыз! — деп айғайлады Денисов орнынан секіріп. - Жарайды, G "қаңқасы! Жарайды!
Қызарып, бозарып кеткен Ростов алдымен бір офицерге, сосын екіншісіне қарады.
– Жоқ, мырзалар, жоқ... ойламаңыздар... мен өте жақсы түсінемін, мен туралы олай ойламауыңыз керек... мен... мен үшін... мен полктің намысын қорғаймын. бірақ не? Мен оны іс жүзінде көрсетемін, ал мен үшін тудың абыройы ... жарайды, бәрі бірдей, шынымен, мен кінәлімін! .. - Оның көзіне жас келді. - Мен кінәлімін, айналаның бәрі кінәлі! ... Ал, тағы не қалайсың? ...
«Болды, сана», - деп айқайлады капитан бұрылып, үлкен қолымен оның иығынан ұрып.
«Мен саған айтамын, - деп айқайлады Денисов, - ол жақсы кішкентай.
— Жақсырақ, граф, — деп қайталады штаб капитаны, оны мойындау үшін оны атақ деп атай бастағандай. - Барып кешірім сұраңыз, мәртебелі мәртебелі, иә с.
«Мырзалар, мен бәрін істеймін, ешкім менен бір сөз естімейді, - деді Ростов жалбарынған дауыспен, - бірақ мен кешірім сұрай алмаймын, құдайға ант етемін, сіз қалайсыз! Кішкентай сияқты кешірім сұрау үшін қалай кешірім сұраймын?
Денисов күлді.
- Саған одан да жаман. Богданыч кекшіл, қыңырлығыңның ақысын бер, – деді Кирстен.
– Құдаймен ант етемін, қыңырлық емес! Мен саған сезімді айтып жеткізе алмаймын, мен...

Алгоритм

Болсын f: ℝ n→ ℝ - минимумға келтірілетін мақсат функциясы, С- үйірдегі бөлшектердің саны, олардың әрқайсысы координатамен байланысты x i ∈ ℝ nшешім кеңістігінде және жылдамдықта v i ∈ ℝ n. Сондай-ақ болсын б i - бөлшектің ең белгілі орны мен, А gжалпы үйірдің ең белгілі күйі болып табылады. Сонда бөлшектер үйірмесі әдісінің жалпы түрі келесідей.

• Әрбір бөлшек үшін мен = 1, …, Сістеу:
  • Кездейсоқ вектор көмегімен бөлшектің бастапқы орнын жасаңыз xмен ~ У(б т.б, б жоғары) көпөлшемді біркелкі бөлуге ие. б т.бЖәне б жоғарысәйкесінше шешім кеңістігінің төменгі және жоғарғы шекаралары болып табылады.
  • Ең жақсы белгілі бөлшектердің орнын оның бастапқы мәніне тағайындаңыз: бмен ← xмен.
  • егер ( f(би)< f(g)), содан кейін топтың ең белгілі күйін жаңартыңыз: g ← бмен.
  • Бөлшектердің жылдамдығының мәнін тағайындаңыз: vмен ~ У(-(б жоғары-б т.б), (б жоғары-б т.б)).
• Тоқтату критерийі орындалғанша (мысалы, берілген итерация санына немесе мақсат функциясының қажетті мәніне жеткенше) қайталаңыз:
  • Әрбір бөлшек үшін мен = 1, …, Сістеу:
    • Кездейсоқ векторларды құру r p , r g~ У(0,1).
    • Бөлшектердің жылдамдығын жаңарту: v i ← w v i + φp r p×( бмен- x i) + φ г r g×( g-x i), мұндағы × операциясы құрамдас бөліктерге көбейтуді білдіреді.
    • Бөлшектердің орнын аударма арқылы жаңартыңыз x i жылдамдық векторына: xмен ← x i + vмен. Бұл қадам мақсат функциясының мәнін жақсартуға қарамастан орындалатынын ескеріңіз.
    • егер ( f(xи)< f(б i)), содан кейін орындаңыз:
      • Ең белгілі бөлшектердің орнын жаңартыңыз: бмен ← xмен.
      • егер ( f(би)< f(g)), содан кейін жалпы тобының ең белгілі күйін жаңартыңыз: g ← бмен.
• Қазір gтабылған шешімдердің ең жақсысын қамтиды.

ω, φ p және φ g параметрлерін калькулятор таңдайды және тұтастай әдістің әрекеті мен тиімділігін анықтайды. Бұл параметрлер көптеген зерттеулердің нысаны болып табылады. (төменде қараңыз).

Параметрлерді таңдау

Бөлшектер тобының әдісі үшін оңтайлы параметрлерді таңдау көптеген зерттеу жұмыстарының тақырыбы болып табылады, мысалы, Ши мен Эберхарттың, Карлайл мен Дозердің, ван ден Бергтің, Клерк пен Кеннедидің, Трелеяның, Браттон мен Блэквеллдің және Evers.

Әдістің параметрлерін таңдаудың қарапайым және тиімді әдісін Педерсен және басқа авторлар ұсынған. Олар сондай-ақ әртүрлі оңтайландыру мәселелерімен және параметрлерімен сандық эксперименттер жүргізді. Бұл параметрлерді таңдау әдістемесі мета оңтайландыру деп аталады, өйткені MFR параметрлерін «баптау» үшін басқа оңтайландыру алгоритмі қолданылады. Ең жақсы өнімділігі бар MFM кіріс параметрлері әдебиетте сипатталған негізгі принциптерге қайшы екендігі дәлелденді және көбінесе MFM қарапайым жағдайлары үшін қанағаттанарлық оңтайландыру нәтижелерін береді. Олардың орындалуын SwarmOps ашық бастапқы кітапханасынан табуға болады.

Алгоритм опциялары

Әдістің өнімділігін жақсарту үшін бөлшектер тобының алгоритмінің жаңа нұсқалары үнемі ұсынылып отырады. Бұл зерттеулерде бірнеше тенденциялар бар, олардың бірі басқа алгоритмдермен үйлесімде MFR пайдалана отырып, гибридті оңтайландыру әдісін құруды ұсынады, мысалы, қараңыз. Тағы бір тенденция - бұл әдісті қандай да бір жолмен жылдамдату, мысалы, артқа шегіну немесе бөлшектер қозғалысының ретін өзгерту (бұл туралы қараңыз). Оңтайландыру процесі кезінде MFR мінез-құлық параметрлерін бейімдеу әрекеттері де бар.

да қараңыз

• Ара алгоритмі
• Гравитациялық іздеу алгоритмі

Ескертпелер

1. (1995) «Бөлшектер тобын оңтайландыру». Нейрондық желілер бойынша IEEE халықаралық конференциясының материалдары IV: 1942-1948.
2. (1998) «Өзгертілген бөлшектер тобын оңтайландырушы». Эволюциялық есептеулер бойынша IEEE халықаралық конференциясының материалдары: 69-73.
3. Үйір интеллект. - Морган Кауфман, 2001 ж.
4. Поли, Р. (2007). «Бөлшектер тобын оңтайландыру қолданбалары бойынша жарияланымдарды талдау». Техникалық есеп CSM-469(Информатика кафедрасы, Эссекс университеті, Ұлыбритания).
5. Поли, Р. (2008). «Бөлшектер тобын оңтайландыруды қолдану бойынша жарияланымдарды талдау». : 1-10. DOI: 10.1155/2008/685175.
6. (1998) «Бөлшектер тобын оңтайландыруда параметрді таңдау». Эволюциялық бағдарламалау материалдары VII (EP98): 591-600.
7. (2000) «Бөлшектер тобын оңтайландырудағы инерция салмағы мен тарылу факторларын салыстыру». Эволюциялық есептеулер конгресінің материалдары 1 : 84-88.
8. (2001) «Сақтаудан тыс PSO». Бөлшектер тобын оңтайландыру семинарының материалдары: 1-6.
9. Ван ден Берг Ф.Бөлшектер тобын оңтайландырушылардың талдауы. - Претория университеті, жаратылыстану және ауылшаруашылық ғылымдары факультеті, 2001 ж.
10. (2002) «Бөлшектер тобы - көпөлшемді күрделі кеңістіктегі жарылыс, тұрақтылық және конвергенция». Эволюциялық есептеулер бойынша IEEE транзакциялары 6 (1): 58-73.
11. Trelea, I.C. (2003). «Бөлшектер тобын оңтайландыру алгоритмі: конвергенциялық талдау және параметрді таңдау». Ақпаратты өңдеу хаттары 85 : 317-325.
12. (2008) «Жеңілдетілген рекомбинантты PSO». Жасанды эволюция және қолданбалар журналы.
13. Эверс Г.Бөлшектер тобын оңтайландырудағы тоқыраумен күресуге арналған автоматты қайта топтау механизмі. - Техас университеті - Панамерикандық, Электротехника бөлімі, 2009 ж.
14. Педерсен М.Е.Х.Эвристикалық оңтайландыруды баптау және жеңілдету. - Саутгемптон университеті, Инженерлік ғылымдар мектебі, Есептеу техникасы және жобалау тобы, 2010 ж.
15. Педерсен, M.E.H.; Чипперфилд, А.Дж. (2010). Бөлшектер тобын оңтайландыруды жеңілдету. Қолданбалы жұмсақ есептеулер 10 : 618-628.
16. (2002) «Өмірлік цикл моделі: бөлшектер тобын оңтайландыруды, генетикалық алгоритмдерді және альпинистерді біріктіру». Табиғаттан параллель есептерді шешу материалдары VII (PPSN): 621-630.
17. (2010) «Кластерлік талдау үшін PSO, ACO және k-құралдарына негізделген тиімді гибридті тәсіл». Қолданбалы жұмсақ есептеулер 10 (1): 183-197.
18. (2002) «Өздігінен ұйымдастырылған сынилікпен бөлшектер тобын оптимизаторларын кеңейту». Эволюциялық есептеулер бойынша төртінші конгресстің материалдары (CEC) 2 : 1588-1593.
19. Синчао, З. (2010). «Сандық оңтайландыруға арналған бұзылған бөлшектер тобының алгоритмі». Қолданбалы жұмсақ есептеулер 10 (1): 119-124.
20. (2009) Бейімделетін бөлшектер тобын оңтайландыру. Жүйелер, адам және кибернетика бойынша IEEE транзакциялары 39 (6): 1362-1381.

Сілтемелер

• Орталық бөлшектер тобы. Жаңалықтар, адамдар, орындар, бағдарламалар, мақалалар және т.б. Атап айтқанда, ағымдағы MFR стандартын қараңыз. (ағылшын)
• SwarmOps. Параметрлерді таңдау / MFR калибрлеу және басқа мета оңтайландыру әдістері. C және C# тіліндегі бағдарламалық жасақтама кітапханасы.
• EvA2 — Java тілінде жазылған ашық бастапқы эволюциялық оңтайландыру және MFM құралы.
• ParadisEO - бұл PFM алгоритмдерін қоса алғанда, әртүрлі метаэвристиканы жасауға арналған қуатты C++ құрылымы. Пайдалануға дайын алгоритмдер, өзіңіздің жеке MFR-ді жылдам жасауға көмектесетін көптеген оқулықтар.
• FORTRAN жүйесіндегі MRCH коды Сынақ функцияларындағы өнімділікті өлшеу.
• - Java тілінде жазылған GPLed есептеу интеллектінің модельдеу және зерттеу ортасы әртүрлі PSO енгізулерін қамтиды
• Баспалдақтарды кесіп өту жұмбақ шешу үшін MFR Python іске асыруды пайдалану.
• ECF - Evolutionary Computation Framework әртүрлі алгоритмдер, генотиптер, параллелизация, оқулықтар.