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

در علوم کامپیوتر و عملیات تحقیق ، الگوریتم زنبورعسل یک الگوریتم جستجو مبتنی بر جمعیت است که در سال ۲۰۰۵ میلادی توسط دکتر فام و دکتر افشین قنبرزاده توسعه یافت. این الگوریتم تقلید رفتار جستجوگری مواد غذایی زنبورهای عسل است. در نسخه اولیه این الگوریتم یک نوع جستجوی محلی همراه با جستجوی جهانی انجام می‌دهد و می‌تواند برای هر دو بهینه‌سازی ترکیبی و بهینه‌سازی مستمر مورد استفاده قرار گیرد. تنها شرط استفاده از الگوریتم زنبورعسل این است که برخی اندازه‌گیری‌های فاصله توپولوژیکی بین راه حل‌ها تعریف شده‌است. اثربخشی و توانایی‌های خاص الگوریتم زنبور عسل در تعدادی از مطالعات ثابت شده‌است.
الگوریتم زنبور عسل از رفتار جستجوگری زنبورهای عسل الهام گرفته‌است.
استراتژی جستجوی غذای زنبور عسل در طبیعت
یک کلنی از زنبورهای عسل می‌توانند در طول فواصل بلند (بیش از ۱۴ کیلومتر) و در جهات مختلف به‌طور هم‌زمان به برداشت شهد یا گرده از منابع غذایی متعدد پراکنده شوند. بخش کوچکی از این کلنی به‌طور مداوم محیط زیست را برای پیدا کردن تکه‌های گل جدید جستجو می‌کنند. این زنبورهای دیده‌بان به‌طور تصادفی در منطقه اطراف کندو حرکت می‌کنند و به ارزیابی سودآوری (عملکرد خالص انرژی) منابع غذایی وارد شده می‌پردازند. وقتی آن‌ها به کندو باز می‌گردنند، دیده‌بان‌ها مواد غذایی برداشت شده را ذخیره می‌کنند. آن دسته از زنبورهایی که منبع غذایی بسیار سود آوری پیدا کردند به یک منطقه در کندو به نام «پیست رقص» رفته و آیینی به نام «رقص حرکتی» را اجرا می‌کنند. در حین این رقص زنبوردیده بان در مورد محلی که کشف کرده با تماشچیان بیکارصحبت می‌کند که به بهره‌برداری از گل‌ها بپیوندند. از آنجا که طول رقص متناسب با امتیاز دیده‌بان از منبع غذایی است، کاوشگرهای بیشتری برای برداشت تکه‌های گل با بهترین امتیاز استخدام می‌شوند. بعد از رقص دیده‌بان برای جمع‌آوری بیشتر غذا به محلی که کشف کرده‌است می‌رود. تا زمانی که این محل‌ها سودآور تلقی شوند، موقع برگشت این منابع غذایی غنی توسط دیده‌بان‌ها تبلیغ می‌شوند. کاوشگرهای استخدام شده نیز ممکن است این رقص را انجام دهند، تا میزان استخدام برای پیدا کردن گل‌های پر ارزش افزایش یابد. با تشکر از فرایند اتوکاتالیزوری این کلنی زنبور عسل قادر است سریع تمرکز را به جستجو برای گل‌های سودآور تغییر دهد.
الگوریتم زنبور عسل
الگوریتم زنبور عسل تقلید استراتژی جستجوی غذای زنبورعسل به دنبال بهترین راه حل برای مشکل بهینه‌سازی است. هر راه حل کاندید، به عنوان یک منبع غذایی (گل) است و جمعیت (کلنی)n عوامل (زنبور) برای جستجوی فضای راه حل استفاده می‌شود. هر بار زنبور عسل مصنوعی به دیدار گل می‌رود (به یک راه حل رسیده)، سود آن را ارزیابی می‌کند (سازگاری).
الگوریتم زنبور عسل شامل روش اولیه نصب یک چرخه جستجوی اصلی که برای تعداد داده شده T بار تکرار می‌شود یا تا زمانی که یک راه حل سازگار و قابل قبول پیدا شود. هر چرخه جستجو متشکل از پنج روش:استخدام، جستجوی محلی، کوچک شدن محله، متروکه شدن محل و جستجوی کلی است.
شبه کد استاندارد الگوریتم زنبور عسل
1 for i=1,…,ns
i scouti=Initialise_scout()
ii flower_patchi=Initialise_flower_patch(scouti)
2 do until stopping_condition=TRUE
i Recruitment()
ii for i =1,…,nb
1 flower_patchi=Local_search(flower_patchi)
2 flower_patchi=Site_abandonment(flower_patchi)
3 flower_patchi=Neighbourhood_shrinking(flower_patchi)
iii for i = nb,…,ns
1 flower_patchi=Global_search(flower_patchi)
در روال اولیه نصب تعداد 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
بهینه‌سازی (ریاضیات)
الگوریتم‌های فراابتکاری
محاسبات فرگشتی
هوش ازدحامی
روش بهینه‌سازی ازدحام ذرات
الگوریتم کلونی مورچگان
الگوریتم کلونی زنبور عسل
الگوریتم چکه آب‌های هوشمند
Lévy flight foraging hypothesis
Manufacturing Engineering Centre