Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Метод рою часток МРЧ англ Particle Swarm Optimization PSO метод чисельної оптимізації для використання якого не потрібно

Метод рою часток

Метод рою часток

Метод рою часток, МРЧ (англ. Particle Swarm Optimization, PSO) — метод чисельної оптимізації, для використання якого не потрібно знати точного градієнта оптимізованої функції. МРЧ був доведений , і Ші і спочатку призначався для імітації . Алгоритм був спрощений, і було зауважено, що він придатний для виконання оптимізації. Книга Кеннеді й Еберхарта описує багато філософських аспектів МРЧ і так званого ройового інтелекту. Велике дослідження застосувань МРЧ зроблене Полі. МРЧ оптимізує функцію, підтримуючи популяцію можливих розв'язків, називаних частками, і переміщаючи ці частки в просторі розв'язків згідно із простою формулою. Переміщення підпорядковуються принципу найкращого знайденого в цьому просторі положення, що постійно змінюється при знаходженні частками вигідніших положень.

image
Рій часток, що шукає глобальний мінімум функції

Алгоритм

Нехай f: ℝn →ℝ — цільова функція, яку потрібно мінімізувати, S — кількість часток у рою, кожній з яких зіставлена координата xi ∈ ℝn у просторі рішень і швидкість vi ∈ ℝn. Нехай також pi — найкраще з відомих положень частки i, а g — найкращий відомий стан рою в цілому. Тоді загальний вигляд методу рою часток такий.

  • Для кожної частки i = 1, …, S зробити:
    • Згенерувати початкове положення частки за допомогою випадкового вектора xi ~ U(blo, bup), що має багатовимірний рівномірний розподіл. blo і bup — нижня й верхня границі простору рішень відповідно.
    • Присвоїти найкращому відомому положенню частки його початкове значення: pi ← xi.
    • Якщо (f(pi) < f(g)), то оновити найкращий відомий стан рою: g ← pi.
    • Присвоїти значення швидкості частки: vi ~ U(-(bup-blo), (bup-blo)).
  • Поки не виконаний критерій зупинки (наприклад, досягнення заданого числа ітерацій або необхідного значення цільової функції), повторювати:
    • Для кожної частки i = 1, …, S зробити:
      • Згенерувати випадкові вектори rp, rg ~ U(0,1).
      • Оновити швидкість частки: vi ← ω vi + φprp × (pi-xi) + φgrg × ( g-xi), де операція × означає покомпонентне множення.
      • Оновити положення частки переносом xi на вектор швидкості: xi ← xi + vi. Зауважимо, що цей крок виконується незалежно від поліпшення значення цільової функції.
      • Якщо (f(xi) < f(pi)), то робити:
        • Оновити найкраще відоме положення частки: pi ← xi.
        • Якщо (f(pi) < f(g)), то оновити найкращий відомий стан рою в цілому: g ← pi.
  • Тепер g містить найкраще зі знайдених рішень.

Параметри ω, φp, і φg вибираються обчислювачем і визначають поведінку й ефективність методу в цілому. Ці параметри є предметом багатьох досліджень (див. нижче).

Підбір параметрів

Вибір оптимальних параметрів методу рою часток — тема значної кількості дослідницьких робіт, див., наприклад, роботи Ші й Еберхарта, Карлісла й Дозера, ван ден Берга, Клерка й Кеннеді, Трелеа, Браттона й Блеквела, а також Еверса.

Простий і ефективний шлях добору параметрів методу запропонований Педерсеном й іншими авторами. Вони ж провели чисельні експерименти з різними оптимізаційними задачами й параметрами. Техніка вибору цих параметрів називається мета-оптимізацією, тому що інший оптимізаційний алгоритм використовується для «налаштовування» параметрів МРЧ. Вхідні параметри МРЧ із найкращою продуктивністю виявилися суперечним основним принципам, описаним у літературі, і часто дають задовільні результати оптимізації для простих випадків МРЧ. Реалізацію їх можна знайти у відкритій бібліотеці SwarmOps.

Варіанти алгоритму

Постійно пропонуються нові варіанти алгоритму рою часток для поліпшення продуктивності методу. Існує кілька тенденцій у цих дослідженнях, одна з яких пропонує створити гібридний оптимізаційний метод, що використовує МРЧ у комбінації з іншими алгоритмами, див. наприклад. Інша тенденція пропонує яким-небудь чином прискорити роботу методу, наприклад, відходом назад або зміною порядку руху часток (про це див.). Також є спроби адаптувати поведінкові параметри МРЧ у процесі оптимізації.

Див. також

Примітки

  1. Kennedy J., Eberhart R. (1995). Particle Swarm Optimization. Proceedings of IEEE International Conference on Neural Networks. Т. IV. с. 1942—1948.
  2. Shi Y., Eberhart R.C. (1998). A modified particle swarm optimizer. Proceedings of IEEE International Conference on Evolutionary Computation. с. 69—73.
  3. Kennedy J., Eberhart R.C. (2001). Swarm Intelligence. Morgan Kaufmann. ISBN .
  4. Poli R. An analysis of publications on particle swarm optimisation applications // Technical Report CSM-469. — Department of Computer Science, University of Essex, UK, 2007. з джерела 16 липня 2011. Процитовано 8 червня 2011.
  5. Poli, R. (2008). Analysis of the publications on the applications of particle swarm optimisation (PDF). Journal of Artificial Evolution and Applications: 1—10. doi:10.1155/2008/685175.{{}}: Обслуговування CS1: Сторінки із непозначеним DOI з безкоштовним доступом ()
  6. Shi Y., Eberhart R.C. (1998). Parameter selection in particle swarm optimization. Proceedings of Evolutionary Programming VII (EP98). с. 591—600.
  7. Eberhart R.C., Shi Y. (2000). Comparing inertia weights and constriction factors in particle swarm optimization. Proceedings of the Congress on Evolutionary Computation. Т. 1. с. 84—88.
  8. Carlisle A., Dozier G. (2001). An Off-The-Shelf PSO. Proceedings of the Particle Swarm Optimization Workshop. с. 1—6.
  9. Van den Bergh, F. (2001). An Analysis of Particle Swarm Optimizers (PhD thesis). University of Pretoria, Faculty of Natural and Agricultural Science.
  10. Clerc M., Kennedy J. (2002). The particle swarm - explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation. 6 (1): 58—73.
  11. Trelea, I.C. (2003). The Particle Swarm Optimization Algorithm: convergence analysis and parameter selection. Information Processing Letters. 85: 317—325.
  12. Bratton D., Blackwell T. (2008). A Simplified Recombinant PSO. Journal of Artificial Evolution and Applications.
  13. Evers, G. (2009). (Master's thesis). The University of Texas - Pan American, Department of Electrical Engineering. Архів оригіналу за 18 травня 2011. Процитовано 8 червня 2011.
  14. Pedersen, M.E.H. (2010). (PDF) (PhD thesis). University of Southampton, School of Engineering Sciences, Computational Engineering and Design Group. Архів оригіналу (PDF) за 26 липня 2011. Процитовано 8 червня 2011.
  15. Pedersen, M.E.H.; Chipperfield, A.J. (2010). (PDF). Applied Soft Computing. 10: 618—628. Архів оригіналу (PDF) за 24 січня 2014. Процитовано 8 червня 2011.
  16. Lovbjerg M., Krink T. (2002). The LifeCycle Model: combining particle swarm optimisation, genetic algorithms and hillclimbers. Proceedings of Parallel Problem Solving from Nature VII (PPSN). с. 621—630.
  17. Niknam T., Amiri B. (2010). An efficient hybrid approach based on PSO, ACO and k-means for cluster analysis. Applied Soft Computing. 10 (1): 183—197.
  18. Lovbjerg M., Krink T. (2002). Extending Particle Swarm Optimisers with Self-Organized Criticality. Proceedings of the Fourth Congress on Evolutionary Computation (CEC). Т. 2. с. 1588—1593.
  19. Xinchao, Z. (2010). A perturbed particle swarm algorithm for numerical optimization. Applied Soft Computing. 10 (1): 119—124.
  20. Zhan Z-H., Zhang J., Li Y., Chung H.S-H. (2009). Adaptive Particle Swarm Optimization. IEEE Transactions on Systems, Man, and Cybernetics. 39 (6): 1362—1381.

Посилання

  • Particle Swarm Central. Новини, люди, місця, програми, статті й ін. Зокрема, див. поточний стандарт МРЧ. (англ.)
  • SwarmOps. Підбор параметрів / калібрування МРЧ і інші мета-оптимізаційні методи. Програмна бібліотека на мовах C і C#.
  • EvA2 — комплексний інструмент еволюційних методів оптимізації й МРЧ із відкритим вихідним кодом, написаний на Java.
  • ParadisEO потужний C++ фреймворк, призначений для створення різних метаевристик, включаючи алгоритми МРЧ. Готові до використання алгоритми, багато підручників, що допомагають швидко створити власний варіант МРЧ.
  • Вимірювання продуктивності на тестових функціях.
  • JSwarm-PSO Пакет МРЧ-оптимізації
  • Модуль МРЧ на Perl
  • Модуль МРЧ на Lua
  • Java-аплет для 3D-візуалізації МРЧ із вихідним кодом
  • Посилання на вихідні коди алгоритмів МРЧ
  • CILib — GPLed computational intelligence simulation and research environment written in Java, includes various PSO implementations
  • МРЧ-модуль для MATLAB
  • Використання реалізації МРЧ на Python для розв'язання головоломки про перетинання сходів.
  • МРЧ-проект на Scheme
  • ECF — Evolutionary Computation Framework різні алгоритми, генотипи, розпаралелювання, підручники.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Metod royu chastok MRCh angl Particle Swarm Optimization PSO metod chiselnoyi optimizaciyi dlya vikoristannya yakogo ne potribno znati tochnogo gradiyenta optimizovanoyi funkciyi MRCh buv dovedenij i Shi i spochatku priznachavsya dlya imitaciyi Algoritm buv sproshenij i bulo zauvazheno sho vin pridatnij dlya vikonannya optimizaciyi Kniga Kennedi j Eberharta opisuye bagato filosofskih aspektiv MRCh i tak zvanogo rojovogo intelektu Velike doslidzhennya zastosuvan MRCh zroblene Poli MRCh optimizuye funkciyu pidtrimuyuchi populyaciyu mozhlivih rozv yazkiv nazivanih chastkami i peremishayuchi ci chastki v prostori rozv yazkiv zgidno iz prostoyu formuloyu Peremishennya pidporyadkovuyutsya principu najkrashogo znajdenogo v comu prostori polozhennya sho postijno zminyuyetsya pri znahodzhenni chastkami vigidnishih polozhen Rij chastok sho shukaye globalnij minimum funkciyiAlgoritmNehaj f ℝ n ℝ cilova funkciya yaku potribno minimizuvati S kilkist chastok u royu kozhnij z yakih zistavlena koordinata xi ℝ n u prostori rishen i shvidkist vi ℝ n Nehaj takozh pi najkrashe z vidomih polozhen chastki i a g najkrashij vidomij stan royu v cilomu Todi zagalnij viglyad metodu royu chastok takij Dlya kozhnoyi chastki i 1 S zrobiti Zgeneruvati pochatkove polozhennya chastki za dopomogoyu vipadkovogo vektora xi U blo bup sho maye bagatovimirnij rivnomirnij rozpodil blo i bup nizhnya j verhnya granici prostoru rishen vidpovidno Prisvoyiti najkrashomu vidomomu polozhennyu chastki jogo pochatkove znachennya pi xi Yaksho f pi lt f g to onoviti najkrashij vidomij stan royu g pi Prisvoyiti znachennya shvidkosti chastki vi U bup blo bup blo Poki ne vikonanij kriterij zupinki napriklad dosyagnennya zadanogo chisla iteracij abo neobhidnogo znachennya cilovoyi funkciyi povtoryuvati Dlya kozhnoyi chastki i 1 S zrobiti Zgeneruvati vipadkovi vektori rp rg U 0 1 Onoviti shvidkist chastki vi w vi fprp pi xi fgrg g xi de operaciya oznachaye pokomponentne mnozhennya Onoviti polozhennya chastki perenosom xi na vektor shvidkosti xi xi vi Zauvazhimo sho cej krok vikonuyetsya nezalezhno vid polipshennya znachennya cilovoyi funkciyi Yaksho f xi lt f pi to robiti Onoviti najkrashe vidome polozhennya chastki pi xi Yaksho f pi lt f g to onoviti najkrashij vidomij stan royu v cilomu g pi Teper g mistit najkrashe zi znajdenih rishen Parametri w fp i fg vibirayutsya obchislyuvachem i viznachayut povedinku j efektivnist metodu v cilomu Ci parametri ye predmetom bagatoh doslidzhen div nizhche Pidbir parametrivVibir optimalnih parametriv metodu royu chastok tema znachnoyi kilkosti doslidnickih robit div napriklad roboti Shi j Eberharta Karlisla j Dozera van den Berga Klerka j Kennedi Trelea Brattona j Blekvela a takozh Eversa Prostij i efektivnij shlyah doboru parametriv metodu zaproponovanij Pedersenom j inshimi avtorami Voni zh proveli chiselni eksperimenti z riznimi optimizacijnimi zadachami j parametrami Tehnika viboru cih parametriv nazivayetsya meta optimizaciyeyu tomu sho inshij optimizacijnij algoritm vikoristovuyetsya dlya nalashtovuvannya parametriv MRCh Vhidni parametri MRCh iz najkrashoyu produktivnistyu viyavilisya superechnim osnovnim principam opisanim u literaturi i chasto dayut zadovilni rezultati optimizaciyi dlya prostih vipadkiv MRCh Realizaciyu yih mozhna znajti u vidkritij biblioteci SwarmOps Varianti algoritmuPostijno proponuyutsya novi varianti algoritmu royu chastok dlya polipshennya produktivnosti metodu Isnuye kilka tendencij u cih doslidzhennyah odna z yakih proponuye stvoriti gibridnij optimizacijnij metod sho vikoristovuye MRCh u kombinaciyi z inshimi algoritmami div napriklad Insha tendenciya proponuye yakim nebud chinom priskoriti robotu metodu napriklad vidhodom nazad abo zminoyu poryadku ruhu chastok pro ce div Takozh ye sprobi adaptuvati povedinkovi parametri MRCh u procesi optimizaciyi Div takozhRojovij intelekt Murashinij algoritm Bdzholinij algoritm Diferencialna evolyuciya Genetichnij algoritm Algoritm imitaciyi vidpalu Garmonijnij poshuk Algoritm intelektualnih krapel Promenevij poshuk Gravitational Search AlgorithmPrimitkiKennedy J Eberhart R 1995 Particle Swarm Optimization Proceedings of IEEE International Conference on Neural Networks T IV s 1942 1948 Shi Y Eberhart R C 1998 A modified particle swarm optimizer Proceedings of IEEE International Conference on Evolutionary Computation s 69 73 Kennedy J Eberhart R C 2001 Swarm Intelligence Morgan Kaufmann ISBN 1 55860 595 9 Poli R An analysis of publications on particle swarm optimisation applications Technical Report CSM 469 Department of Computer Science University of Essex UK 2007 z dzherela 16 lipnya 2011 Procitovano 8 chervnya 2011 Poli R 2008 Analysis of the publications on the applications of particle swarm optimisation PDF Journal of Artificial Evolution and Applications 1 10 doi 10 1155 2008 685175 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Cite journal title Shablon Cite journal cite journal a Obslugovuvannya CS1 Storinki iz nepoznachenim DOI z bezkoshtovnim dostupom posilannya Shi Y Eberhart R C 1998 Parameter selection in particle swarm optimization Proceedings of Evolutionary Programming VII EP98 s 591 600 Eberhart R C Shi Y 2000 Comparing inertia weights and constriction factors in particle swarm optimization Proceedings of the Congress on Evolutionary Computation T 1 s 84 88 Carlisle A Dozier G 2001 An Off The Shelf PSO Proceedings of the Particle Swarm Optimization Workshop s 1 6 Van den Bergh F 2001 An Analysis of Particle Swarm Optimizers PhD thesis University of Pretoria Faculty of Natural and Agricultural Science Clerc M Kennedy J 2002 The particle swarm explosion stability and convergence in a multidimensional complex space IEEE Transactions on Evolutionary Computation 6 1 58 73 Trelea I C 2003 The Particle Swarm Optimization Algorithm convergence analysis and parameter selection Information Processing Letters 85 317 325 Bratton D Blackwell T 2008 A Simplified Recombinant PSO Journal of Artificial Evolution and Applications Evers G 2009 Master s thesis The University of Texas Pan American Department of Electrical Engineering Arhiv originalu za 18 travnya 2011 Procitovano 8 chervnya 2011 Pedersen M E H 2010 PDF PhD thesis University of Southampton School of Engineering Sciences Computational Engineering and Design Group Arhiv originalu PDF za 26 lipnya 2011 Procitovano 8 chervnya 2011 Pedersen M E H Chipperfield A J 2010 PDF Applied Soft Computing 10 618 628 Arhiv originalu PDF za 24 sichnya 2014 Procitovano 8 chervnya 2011 Lovbjerg M Krink T 2002 The LifeCycle Model combining particle swarm optimisation genetic algorithms and hillclimbers Proceedings of Parallel Problem Solving from Nature VII PPSN s 621 630 Niknam T Amiri B 2010 An efficient hybrid approach based on PSO ACO and k means for cluster analysis Applied Soft Computing 10 1 183 197 Lovbjerg M Krink T 2002 Extending Particle Swarm Optimisers with Self Organized Criticality Proceedings of the Fourth Congress on Evolutionary Computation CEC T 2 s 1588 1593 Xinchao Z 2010 A perturbed particle swarm algorithm for numerical optimization Applied Soft Computing 10 1 119 124 Zhan Z H Zhang J Li Y Chung H S H 2009 Adaptive Particle Swarm Optimization IEEE Transactions on Systems Man and Cybernetics 39 6 1362 1381 PosilannyaParticle Swarm Central Novini lyudi miscya programi statti j in Zokrema div potochnij standart MRCh angl SwarmOps Pidbor parametriv kalibruvannya MRCh i inshi meta optimizacijni metodi Programna biblioteka na movah C i C EvA2 kompleksnij instrument evolyucijnih metodiv optimizaciyi j MRCh iz vidkritim vihidnim kodom napisanij na Java ParadisEO potuzhnij C frejmvork priznachenij dlya stvorennya riznih metaevristik vklyuchayuchi algoritmi MRCh Gotovi do vikoristannya algoritmi bagato pidruchnikiv sho dopomagayut shvidko stvoriti vlasnij variant MRCh Vimiryuvannya produktivnosti na testovih funkciyah JSwarm PSO Paket MRCh optimizaciyi Modul MRCh na Perl Modul MRCh na Lua Java aplet dlya 3D vizualizaciyi MRCh iz vihidnim kodom Posilannya na vihidni kodi algoritmiv MRCh CILib GPLed computational intelligence simulation and research environment written in Java includes various PSO implementations MRCh modul dlya MATLAB Vikoristannya realizaciyi MRCh na Python dlya rozv yazannya golovolomki pro peretinannya shodiv MRCh proekt na Scheme ECF Evolutionary Computation Framework rizni algoritmi genotipi rozparalelyuvannya pidruchniki

Дата публікації:
Топ