الگوریتم زنبور عسل

در علوم کامپیوتر و عملیات تحقیق، الگوریتم زنبورعسل یک الگوریتم جستجو مبتنی بر جمعیت است که در سال ۲۰۰۵ میلادی توسط دکتر فام و دکتر افشین قنبرزاده توسعه یافت.[۱] این الگوریتم تقلید رفتار جستجوگری مواد غذایی زنبورهای عسل است. در نسخهٔ اولیهٔ این الگوریتم یک نوع جستجوی محلی همراه با جستجوی جهانی انجام می‌دهد و می‌تواند برای هر دو بهینه‌سازی ترکیبی و بهینه‌سازی مستمر مورد استفاده قرار گیرد. تنها شرط استفاده از الگوریتم زنبورعسل این است که برخی اندازه‌گیری‌های فاصله توپولوژیکی بین راه حل‌ها تعریف شده‌است. اثربخشی و توانایی‌های خاص الگوریتم زنبور عسل در تعدادی از مطالعات ثابت شده‌است.[۲][۳]

الگوریتم زنبور عسل از رفتار جستجوگری زنبورهای عسل الهام گرفته‌است.

استراتژی جستجوی غذای زنبور عسل در طبیعت

[ویرایش]

یک کلونی از زنبورهای عسل می‌توانند در طول فواصل بلند (بیش از ۱۴ کیلومتر)[۴] و در جهات مختلف به‌طور هم‌زمان به برداشت شهد یا گرده از منابع غذایی متعدد پراکنده شوند. بخش کوچکی از این کلونی به‌طور مداوم محیط زیست را برای پیدا کردن تکه‌های گل جدید جستجو می‌کنند. این زنبورهای دیده‌بان به‌طور تصادفی در منطقه اطراف کندو حرکت می‌کنند و به ارزیابی سودآوری (عملکرد خالص انرژی) منابع غذایی وارد شده می‌پردازند.[۴] وقتی آن‌ها به کندو باز می‌گردنند، دیده‌بان‌ها مواد غذایی برداشت شده را ذخیره می‌کنند. آن دسته از زنبورهایی که منبع غذایی بسیار سود آوری پیدا کردند به یک منطقه در کندو به نام «پیست رقص» رفته و آیینی به نام «رقص حرکتی» را اجرا می‌کنند.[۵] در حین این رقص زنبوردیده بان در مورد محلی که کشف کرده با تماشچیان بیکارصحبت می‌کند که به بهره‌برداری از گل‌ها بپیوندند. از آنجا که طول رقص متناسب با امتیاز دیده‌بان از منبع غذایی است، کاوشگرهای بیشتری برای برداشت تکه‌های گل با بهترین امتیاز استخدام می‌شوند. بعد از رقص دیده‌بان برای جمع‌آوری بیشتر غذا به محلی که کشف کرده‌است می‌رود. تا زمانی که این محل‌ها سودآور تلقی شوند، موقع برگشت این منابع غذایی غنی توسط دیده‌بان‌ها تبلیغ می‌شوند. کاوشگرهای استخدام شده نیز ممکن است این رقص را انجام دهند، تا میزان استخدام برای پیدا کردن گل‌های پر ارزش افزایش یابد. به لطف این فرایند اتوکاتالیزوری، کلونی زنبور عسل می‌تواند با سرعت زیاد تمرکز را به جستجو برای گل‌های سودآور تغییر دهد.[۴]

الگوریتم زنبور عسل

[ویرایش]

الگوریتم زنبور عسل[۲][۶] تقلید استراتژی جستجوی غذای زنبورعسل به دنبال بهترین راه حل برای مشکل بهینه‌سازی است. هر راه حل کاندید، به عنوان یک منبع غذایی (گل) است و جمعیت (کلنی)n عوامل (زنبور) برای جستجوی فضای راه حل استفاده می‌شود. هر بار زنبور عسل مصنوعی به دیدار گل می‌رود (به یک راه حل رسیده)، سود آن را ارزیابی می‌کند (سازگاری). الگوریتم زنبور عسل شامل روش اولیه نصب یک چرخه جستجوی اصلی که برای تعداد داده شده T بار تکرار می‌شود یا تا زمانی که یک راه حل سازگار و قابل قبول پیدا شود. هر چرخه جستجو متشکل از پنج روش:استخدام، جستجوی محلی، کوچک شدن محله، متروکه شدن محل و جستجوی کلی است.

شبه کد استاندارد الگوریتم زنبور عسل[۲] 

 1 for i=1,…,ns
 i scout[i]=Initialise_scout()
 ii flower_patch[i]=Initialise_flower_patch(scout[i])
 2 do until stopping_condition=TRUE
 i Recruitment()
 ii for i =1,…,nb
 1 flower_patch[i]=Local_search(flower_patch[i])
 2 flower_patch[i]=Site_abandonment(flower_patch[i])
 3 flower_patch[i]=Neighbourhood_shrinking(flower_patch[i])
 iii for i = nb,…,ns
 1 flower_patch[i]=Global_search(flower_patch[i])}

در روال اولیه نصب تعداد ns زنبورهای عسل دیده‌بان به‌طور تصادفی در فضای جستجو قرار می‌گیرند و سازگاری محلی که در آن قرار دارند را ارزیابی می‌کنند. برای هر راه حل، یک محله (به نام راه گل) مشخص شده‌است. در روش استخدام، دیده‌بان‌هایی که به تعداد nb<=ns راه حل‌های سازگارمراجعه کرده‌اند (بهترین محل‌ها) «رقص حرکتی» را انجام می‌دهند. آن است که، کاوشگرهایی استخدام می‌کنند تا به جستجوی محلات دور از محلات راه حل‌های امیدوارکننده بپردازند. دیده‌بان‌های واقع در بهترین محلات ne<=nb راه حل (محل‌های برگزیده شده) هر کدام nre کاوشگر استخدام می‌کنند، در حالی که nb-ne دیده‌بان باقی‌مانده هر کدام nrb<=nre کاوشگر استخدام می‌کنند. به این ترتیب، تعداد کاوشگرهای استخدام شده به سوددهی منبع غذایی ربط دارد. در روش جستجوی محلی، کاوشگرهای استخدام شده به‌طور تصادفی در تکه‌های گل پراکنده شده و راه حل‌های مراجعه شده توسط دیده‌بان‌ها را در میان می‌گذارند (بهره‌برداری محلی). اگر یکی از کاوشگرها راه حل سازگارتری نسبت به راه حل ارائه شده توسط دیده‌بان ارائه دهد، کاوشگر دیده‌بان می‌شود. اگر کاوشگر دیگری راه حل سازگارتری ارائه ندهد، اندازه تکه گل کوچک می‌شود (روش کوچک شدن محله). معمولاً، تکه‌های گل در ابتدا یک محل بزرگ تعریف شده و اندازه آن‌ها به تدریج توسط روش کوچک شدن محله کوچک می‌شود. در نتیجه، حوزه اکتشاف محلی به تدریج روی محلهٔ بلافاصله نزدیک به بهترین محل سازگار متمرکز می‌شود. اگر هیچ بهبودی در سازگاری تکه گل برای یک تعداد چرخه جستجوی از پیش تعیین شده ثبت نشود، ماکزیمم سازگاری محلی یافت شده فرض می‌شود، این محل متروکه می‌ماند (متروکه شدن محل) و یک دیده‌بان جدید به‌طور تصادفی حاصل می‌شود. مانند گروه‌های زنبور عسل بیولوژیکی،[۴] تعداد کمی از دیده‌بان‌ها به جستجوی فضای راه حل برای یافتن مناطق جدیدی با سازگاری بالا ادامه می‌دهند (جستجوی کلی). روش جستجوی کلی تعداد ns-nb گل‌های آخر با راه حل‌های به وجود آمده تصادفی دوباره مقدار دهی می‌کند. در پایان یک چرخه جستجو، جمعیت دیده‌بان‌ها دوباره برابر ns می‌شود:تعداد nr دیده‌بان تشکیل شده در روش جستجوی محلی (که برخی از آن‌ها ممکن است توسط روش متروکه شدن محل دوباره مقدار دهی شوند) وns-nb دیده‌بان تشکیل شده در روش جستجوی کلی. سایز کل گروه زنبور عسل مصنوعی برابر است با:n=ne*nre+(nb-ne)*nrb+ns(کاوشگران محل‌های گلچین شده+کاوشگران بهترین محل‌های باقی‌مانده+دیده‌بان‌ها) زنبور عسل

کاربردها

[ویرایش]

الگوریتم زنبورها کاربردهای زیادی در مهندسی پیدا کرده‌است مانند:

  • بهینه‌سازی طبقه/سیستم‌های خوشه بندی
  • ساخت
  • کنترل
  • مهندسی زیست
  • سایر مسائل بهینه‌سازی
  • بهینه‌سازی چند هدفه

Optimisation of classifiers / clustering systems[۷][۸][۹]

Manufacturing[۱۰][۱۱][۱۲][۱۳][۱۴][۱۵]

Control[۱۶][۱۷][۱۸][۱۹]

Bioengineering[۲۰][۲۱]

Other optimisation problems[۲۲][۲۳][۲۴][۲۵][۲۶]

Multi-objective optimisation[۲۷][۲۸][۲۹][۳۰]

جستارهای وابسته

[ویرایش]

منابع

[ویرایش]
  1. ↑ Pham DT, Ghanbarzadeh A, Koc E, Otri S, Rahim S and Zaidi M. The Bees Algorithm. Technical Note, Manufacturing Engineering Centre, Cardiff University, UK, 2005.
  2. ↑ ۲٫۰ ۲٫۱ ۲٫۲ Pham, D.T. , Castellani, M. (2009), The Bees Algorithm – Modelling Foraging Behaviour to Solve Continuous Optimisation Problems بایگانی‌شده در ۹ نوامبر ۲۰۱۶ توسط Wayback Machine. Proc. ImechE, Part C, 223(12), 2919-2938.
  3. ↑ Pham, D.T. and Castellani, M. (2013), Benchmarking and Comparison of Nature-Inspired Population-Based Continuous Optimisation Algorithms, Soft Computing, 1-33.
  4. ↑ ۴٫۰ ۴٫۱ ۴٫۲ ۴٫۳ Tereshko V. , Loengarov A. , (2005) Collective Decision-Making in Honey Bee Foraging Dynamics بایگانی‌شده در ۱ فوریه ۲۰۱۴ توسط Wayback Machine. Journal of Computing and Information Systems, 9(3), 1-7.
  5. ↑ Von Frisch, K. (1967) The Dance Language and Orientation of Bees. Harvard University Press, Cambridge, MA.
  6. ↑ Pham D.T. , Ghanbarzadeh A. , Koc E. , Otri S. , Rahim S. , Zaidi M. , The Bees Algorithm, A Novel Tool for Complex Optimisation Problems, Proc 2nd Int Virtual Conf on Intelligent Production Machines and Systems (IPROMS 2006), Oxford: Elsevier, pp. 454-459, 2006.
  7. ↑ Pham D.T. , Zaidi M. , Mahmuddin M. , Ghanbarzadeh A. , Koç E. , Otri S. (2007), Using the bees algorithm to optimise a support vector machine for wood defect classification, IPROMS 2007 Innovative Production Machines and Systems Virtual Conference.
  8. ↑ Pham D.T. , Darwish A.H. (2010), Using the bees algorithm with Kalman filtering to train an artificial neural network for pattern classification بایگانی‌شده در ۶ ژوئیه ۲۰۱۵ توسط Wayback Machine, Journal of Systems and Control Engineering 224(7), 885-892.
  9. ↑ Pham D.T. , Suarez-Alvarez M.M. , Prostov Y.I. (2011), Random search with k-prototypes algorithm for clustering mixed datasets, Proceedings Royal Society, 467, 2387-2403.
  10. ↑ Pham D.T. , Castellani M. , Ghanbarzadeh A. (2007), Preliminary design using the Bees Algorithm, Proceedings Eighth LAMDAMAP International Conference on Laser Metrology, CMM and Machine Tool Performance. Cardiff - UK, 420-429.
  11. ↑ Pham, D.T. , Otri S. , Darwish A.H. (2007), Application of the Bees Algorithm to PCB assembly optimisation, Proceedings 3rd International Virtual Conference on Intelligent Production Machines and Systems (IPROMS 2007), Whittles, Dunbeath, Scotland, 511-516.
  12. ↑ Pham D.T. , Koç E. , Lee J.Y. , Phrueksanant J. (2007), Using the Bees Algorithm to Schedule Jobs for a Machine, Proceedings 8th international Conference on Laser Metrology, CMM and Machine Tool Performance (LAMDAMAP). Cardiff, UK, Euspen, 430-439.
  13. ↑ Baykasoğlu A. , Özbakır L. , Tapkan P. (2009), The bees algorithm for workload balancing in examination job assignment, European Journal Industrial Engineering 3(4) 424-435.
  14. ↑ Özbakır L. , Tapkan P. (2011), Bee colony intelligence in zone constrained two-sided assembly line balancing problem, Expert Systems with Applications 38, 11947-11957.
  15. ↑ Xu W. , Zhou Z. , Pham D.T. , Liu Q. , Ji C. , Meng W. (2012), Quality of service in manufacturing networks: a service framework and its implementation, International Journal Advanced Manufacturing Technology, 63(9-12), 1227-1237.
  16. ↑ Pham D.T. , Darwish A.H. , Eldukhri E.E. (2009), Optimisation of a fuzzy logic controller using the Bees Algorithm, International Journal of Computer Aided Engineering and Technology, 1, 250-264.
  17. ↑ Alfi A. , Khosravi A. , Razavi S.E. (2011), Bee Algoritm–Based Nolinear Optimal Control Applied To A Continuous Stirred-Tank Chemical Reactor, Global Journal of Pure & Applied Science and Technology - GJPAST 1(2), 73-79.
  18. ↑ Fahmy A.A. , Kalyoncu M. , Castellani M. (2012), Automatic Design of Control Systems for Robot Manipulators Using the Bees Algorithm[پیوند مرده], Proceedings of the Institution of Mechanical Engineers, Part I: Journal of Systems and Control Engineering, 226(4), 497-508.
  19. ↑ Castellani M. , Pham Q.T. , Pham D.T. (2012), Dynamic Optimisation by a Modified Bees Algorithm[پیوند مرده], Proceedings of the Institution of Mechanical Engineers, Part I: Journal of Systems and Control Engineering, 226(7), 956–971.
  20. ↑ Bahamish H.A.A. , Abdullah R. , Salam R.A. (2008), Protein Conformational Search Using Bees Algorithm, Second Asia International Conference on Modeling & Simulation (AICMS 08), Kuala Lumpur, Malaysia, IEEE Press, 911-916.
  21. ↑ Ruz G.A. , Goles E. (2013), Learning gene regulatory networks using the bees algorithm, Neural Computing and Applications, 22(1), 63-70.
  22. ↑ Guney K. , Onay M. (2010), Bees algorithm for interference suppression of linear antenna arrays by controlling the phase-only and both the amplitude and phase, Expert Systems with Applications 37, 3129–3135.
  23. ↑ Xu S. , Yu F. , Luo Z. , Ji Z. , Pham D.T. , Qiu R. (2011), Adaptive Bees Algorithm - Bioinspiration from Honeybee Foraging to Optimize Fuel Economy of a Semi-Track Air-Cushion Vehicle, The Computer Journal 54(9), 1416-1426.
  24. ↑ Pham D.T. , Koç E. (2011), Design of a two-dimensional recursive filter using the bees algorithm, International Journal Automation and Computing 7(3) 399-402.
  25. ↑ Kavousi A. , Vahidi B. , Salehi R. , Bakhshizadeh M.K. , Farokhnia N. , Fathi S.H. (2012), Application of the Bee Algorithm for Selective Harmonic Elimination Strategy in Multilevel Inverters, IEEE Transactions on Power Electronics 27(4) 1689-1696.
  26. ↑ Jevtic A. , Gutierrez-Martin A. , Andina D.A. , Jamshidi M. (2012), Distributed Bees Algorithm for Task Allocation in Swarm of Robots, IEEE Systems Journal 6(2) 296-304.
  27. ↑ Morsali, Roozbeh; Mohammadi, Mohsen; Maleksaeedi, Iman; Ghadimi, Noradin. "A new multiobjective procedure for solving nonconvex environmental/economic power dispatch". Complexity. 20 (2): 47–62. doi:10.1002/cplx.21505.
  28. ↑ Lee J.Y. , Darwish A.H. (2008), Multi-objective Environmental/Economic Dispatch Using the Bees Algorithm with Weighted Sum, Proceedings of the EU-Korea Conference on Science and Technology (EKC2008), Ed. S.D. Yoo, Heidelberg, D, Springer Berlin Heidelberg, 267-274.
  29. ↑ Sayadi F. , Ismail M. , Misran N. , Jumari K. (2009), Multi-Objective Optimization Using the Bees Algorithm in Time-Varying Channel for MIMO MC-CDMA Systems, European Journal of Scientific Research 33(3), 411-428.
  30. ↑ Mansouri Poor M. , Shisheh Saz M. (2012), Multi-Objective Optimization of Laminates with Straight Free Edges and Curved Free Edges by Using Bees Algorithm, American Journal of Advanced Scientific Research 1(4), 130-136.

پیوند به بیرون

[ویرایش]
در ویکی‌انبار پرونده‌هایی دربارهٔ الگوریتم زنبور عسل موجود است.