معرفی الگوریتم Honey Bee و کاربرد آن در بهینه سازی

سلام خدمت TOSINSO ای های عزیز ، امروز تصمیم دارم یک معرفی اجمالی از الگوریتم زنبور عسل و کاربردآن در بهینه سازی را با هم بررسی کنیم .برای درک بهتر این الگوریتم و اینکه چرا زنبور عسل نامیده شد باید نگاهی به زندگی زنبورها داشته باشیم .هر کلونی زنبور عسل دارای زنبور تخم گذاری با عمر طولانی است که به عنوان زنبور ملکه شناخه می شود . همچنین تعداد 10000 تا 60000 زنبور کارگر نیز در هر کلونی وجود دارد . در فصل تابستان زنبورها باید به جمع آوری غذا بپردازند تا در زمستان که منابع غذایی موجود نمی باشد از آن استفاده کنند.

دوره های شبکه، برنامه نویسی، مجازی سازی، امنیت، نفوذ و ... با برترین های ایران

برای این امر هر کلونی بخشی از جمعیت زنبورهای بالغ خود که معمولا 25 درصد جمعیت اصلی هستند را تحت عنوان زنبورهای پیشاهنگ انتخاب کرده و منظور جستجو به فضای اطراف کندو می فرستد .این زنبورها به منظور یافتن منابع غذایی به صورت تصادفی حرکت می کنند . پیشاهنگ ها قابلیت یافتن منابع غذایی در نقاط دور از کندو را دارند و می توانند بدون مشکل به به کندو باز گردند . پیشاهنگ ها با یافتن هر منبع غذایی مقداری از نکتار آن منبع را برداشته و کیفیت ، فاصله تا کندو و انرژی مورد نیاز برای رسیدن به آن منبع را مشخص می نمایند .بعد از برگشت پیشاهنگ ها به کندو هرکدام نکتاری را که پیدا کرده اند آزاد می کنند . زنبورهایی که منابع بهتری پیداکرده اند موقعیت این منابع را به سایر زنبورها اطلاع می دهند.

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

این عمل در محل خاصی از کندو که در اصطلاح زمین رقص نامیده می شود تحت عنوان رقص انجام می شود . با این رقص سه نوع داده پایه شامل جهتی که منبع در آن است ، مسافت تا منبع و کیفیت منبع به سایر زنبورها اعلام می شود .بعد از این عمل زنبورهای رقصنده مجددا به سوی منابع یافت شده شان حرکت می کنند و اینبار توسط سایر زنبورهای کندو همراهی می شوند .همراهان هر پیشاهنگ بسته به کیفیت منبع یافت شده متفاوت است .

هدف اصلی زنبورهای عسل یافتن بهترین منبع غذایی با صرف کمترین انرژی و بیشترین سطح غذامی باشد . در واقع نوعی بهینه سازی برای یافتن منبع .الگوریتم بهینه سازی ارائه شده از همین رویه الهام گرفته . هر پاسخ در فضای راه حل به عنوان یک راه حل شناخته می شود . در ابتدا پیشاهنگ ها به صورت تصادفی در این فضا قرار می گیرند و با مقایسه تابع برازندگی که درواقع در نقش کیفیت منبع غذایی عمل می کند اطلاعات مورد نیاز از آن منبع را بدست می آورد . سپس این اطلاعات مرتب شده و سایر زنبورها مسئول جستجو در همسایگی این نواحی می باشند که نواحی بهتر زنبورهای بیشتری با خود همراه می کند. برای درک به پارامترها و شبه کد زیر توجه کنید (فرض میکنیم مساله بیشینه سازی است ) :

  • n = زنبورهای پیشاهنگ اولیه
  • m = مناطق اولیه یافت شده توسط پیشاهنگ ها
  • e = مرتب شده مناطق بر اساس کیفیت
  • nep = تعداد زنبورهایی که به سراغ p درصد مناطق بهتر میروند
  • nsp = تعداد زنبورهایی که به سراغ e-p منطقه باقی مانده میروند

1 - ابتدا n پاسخ تصادفی ایجاد شده .

2 - سپس میزان برازندگی هرکدام محاسبه می شود .

3 - سپس مرتب شده این برازندگی ها به صورت نزولی (چون مساله بیشینه سازی است ) در e ذخیره می شود .

4 - سپس برای 20 درصد مناطق با برازندگی بالاتر به شعاع همسایگی مشخص هر کدام ده نقطه جدید ایجاد می شود.

5 - برای 80 درصد مناطق باقیمانده با شعاع مشخص برای هرکدام 5 نقطه جدید ایجاد می¬شود .

6 – میزان برازندگی برای نقاط جدید محاسبه می شود .

7 – حال کل نقاط ایجاد شده را بر اسا س برازندگی مرتب کرده و مجددا n نقطه از بهترین ها ایجاد شده و به مرحله 3 برمیگردیم .

این عمل را آنقدر تکرار میکنیم تا به شرط خاتمه الگوریتم مثلا یک دقت خاص از جواب برسیم .

باید دقت کرد که مرحله 7 از بین کل نقاط موجود بهترین ها را جدا می کند . مثلا اگر 100 نقطه اولیه داشته باشیم کنار 20 تای آنها هرکدام 10 نقطه و کنار 80 تای آن ها هرکدام 5 نقطه ایجاد می¬شود که مجموعا می شود :

100 + (20 * 10 ) + (80  * 5 ) = 100 + 200 + 400 = 700

و باید از بین این 700 نقطه 100 تا از بهترین ها جدا شود . نتایج الگوریتم برای تابع زیر :

سلام خدمت TOSINSO ای های عزیز ، امروز تصمیم دارم یک معرفی اجمالی از الگوریتم زنبور عسل و کاربردآن در بهینه سازی را با هم بررسی کنیم .برای درک بهتر این الگوریتم و اینکه چرا زنبور عسل نامیده شد باید نگاهی به زندگی زنبورها داشته باشیم .هر کلونی زنبور عسل دارای زنبور تخم گذاری با عمر طولانی است که به عنوان زنبور ملکه شناخه می شود . همچنین تعداد 10000 تا 60000 زنبور کارگر نیز در هر کلونی وجود دارد . در فصل تابستان زنبورها باید به جمع آوری غذا بپردازند تا در زمستان که منابع غذایی موجود نمی باشد از آن استفاده کنند.

برای این امر هر کلونی بخشی از جمعیت زنبورهای بالغ خود که معمولا 25 درصد جمعیت اصلی هستند  را تحت عنوان زنبورهای پیشاهنگ انتخاب کرده و منظور جستجو به فضای اطراف کندو می فرستد .این زنبورها به منظور یافتن منابع غذایی به صورت تصادفی حرکت می کنند . پیشاهنگ ها قابلیت یافتن منابع غذایی در نقاط دور از کندو را دارند و می توانند بدون مشکل به به کندو باز گردند . پیشاهنگ ها با یافتن هر منبع غذایی مقداری از نکتار آن منبع را برداشته و کیفیت ، فاصله تا کندو  و انرژی مورد نیاز برای رسیدن به آن منبع را مشخص می نمایند .بعد از برگشت پیشاهنگ ها به کندو هرکدام نکتاری را که پیدا کرده اند آزاد می کنند . زنبورهایی که منابع بهتری پیداکرده اند موقعیت این منابع را به سایر زنبورها اطلاع می دهند.

||الگوریتم کندوی زنبور عسل::https://tosinso.com/files/get/bf1206ab-3854-4782-9fef-a4c680177dc7||

این عمل در محل خاصی از کندو که در اصطلاح زمین رقص نامیده می شود تحت عنوان رقص انجام می شود . با این رقص سه نوع داده پایه شامل جهتی که منبع در آن است ، مسافت تا منبع و کیفیت منبع به سایر زنبورها اعلام می شود .بعد از این عمل زنبورهای رقصنده مجددا به سوی منابع یافت شده شان حرکت می کنند و اینبار توسط سایر زنبورهای کندو همراهی می شوند .همراهان هر پیشاهنگ بسته به کیفیت منبع یافت شده متفاوت است .

هدف اصلی زنبورهای عسل یافتن بهترین منبع غذایی با صرف کمترین انرژی و بیشترین سطح غذامی باشد . در واقع نوعی بهینه سازی برای یافتن منبع .الگوریتم بهینه سازی ارائه شده از همین رویه الهام گرفته . هر پاسخ در فضای راه حل به عنوان یک راه حل شناخته می شود . در ابتدا پیشاهنگ ها به صورت تصادفی در این فضا قرار می گیرند و با مقایسه تابع برازندگی که درواقع در نقش کیفیت منبع غذایی عمل می کند اطلاعات مورد نیاز از آن منبع را بدست می آورد . سپس این اطلاعات مرتب شده و سایر زنبورها مسئول جستجو در همسایگی این نواحی می باشند که  نواحی بهتر زنبورهای بیشتری با خود همراه می کند. برای درک به پارامترها و شبه کد زیر توجه کنید (فرض میکنیم مساله بیشینه سازی است ) :

* n = زنبورهای پیشاهنگ اولیه
* m = مناطق اولیه یافت شده توسط پیشاهنگ ها
* e = مرتب شده مناطق بر اساس کیفیت
* nep  = تعداد زنبورهایی که به سراغ p درصد مناطق بهتر میروند
* nsp = تعداد زنبورهایی که به سراغ e-p منطقه باقی مانده میروند

1 - ابتدا n پاسخ تصادفی ایجاد شده .
2 -  سپس میزان برازندگی هرکدام محاسبه می شود .
3 -  سپس مرتب شده این برازندگی ها به صورت نزولی (چون مساله بیشینه سازی است ) در e ذخیره می شود .
4 -  سپس برای 20 درصد مناطق با برازندگی بالاتر به شعاع همسایگی مشخص هر کدام ده نقطه جدید ایجاد می شود.
5 - برای 80 درصد مناطق باقیمانده با شعاع مشخص برای هرکدام 5 نقطه جدید ایجاد می¬شود .
6 – میزان برازندگی برای نقاط جدید محاسبه می شود .
7 – حال کل نقاط ایجاد شده را بر اسا س برازندگی مرتب کرده و مجددا n نقطه از بهترین ها ایجاد شده و به مرحله 3 برمیگردیم .

این عمل را آنقدر تکرار میکنیم تا به شرط خاتمه الگوریتم مثلا یک دقت خاص از جواب برسیم .
باید دقت کرد که مرحله 7 از بین کل نقاط موجود بهترین ها را جدا می کند . مثلا اگر 100 نقطه اولیه داشته باشیم کنار 20 تای آنها هرکدام 10 نقطه و کنار 80 تای آن ها هرکدام 5 نقطه ایجاد می¬شود که مجموعا می شود :
<c#>
100 + (20 * 10 ) + (80  * 5 ) = 100 + 200 + 400 = 700
<c#>
و باید از بین این 700 نقطه 100 تا از بهترین ها جدا شود . نتایج الگوریتم برای تابع زیر :

||http://tosinso.com/files/get/942b48ee-145e-4542-a311-18f6d3442125||
نتایج پنج اجرای مستقل :
<left>
 10.8865- ,   10.9081- ,   10.9114-  ,   10.8995 - ,  10.9184-
<left>
جواب صحیح : 11-

نتایج پنج اجرای مستقل :

10.8865- , 10.9081- , 10.9114- , 10.8995 - , 10.9184-

جواب صحیح : 11-


نظرات