الگوریتم کلونی زنبور عسل مصنوعی Artificial Bee Colony (ABC) Algorithm

الگوریتم جستجوی جدیدی مبتنی بر جمعیت به نام الگوریتم زنبور عسل (BA) ارایه شده است . الگوریتم  کلونی زنبور عسل رفتار جست و جوی غذای گروه زنبورهای عسل را تقلید می کند . در مدل پایه ای آن الگوریتم نوعی از جستجوی همسایگی ترکیب شده با جستجوی تصادفی را انجام می دهد و می تواند برای هر دوی بهینه سازی ترکیبی یا بهینه سازی تابعی مورد استفاده قرار گیرد.

مقدمه

طبیعت الهام بخش محققان برای توسعه مدل هایی برای حل مسائل و مشکلات آنهاست. به عنوان مثال “بهینه سازی” زمینه ای است که بارها این مدل ها توسعه و به کار برده شده اند . الگوریتم ژنتیک انتخاب طبیعی و عملگرهای ژنتیک را شبیه سازی می کند ، الگوریتم بهینه سازی خرده گروه ها ، دسته های پرندگان و مدرسه ماهی ها را شبیه سازی می کند، سیستم حفاظتی مصنوعی توده های سلولی سیستم حفاظتی را شبیه سازی می کند ، الگوریتم بهینه سازی کلونی مورچه ها رفتار کاوشی مورچه ها را شبیه سازی می کند و الگوریتم کلونی زنبورهای مصنوعی رفتار کاوشی زنبورهای عسل را شبیه سازی می کند. اینها نمونه هایی بود از الگوریتم های بهینه سازی الهام شده از طبیعت . الگوریتم دیگری که رفتار کاوشی زنبورها را با یک مدل الگوریتمی متفاوت شبیه سازی می کند الگوریتم زنبور عسل BA است .
در این مقاله دو الگوریتم کلونی زنبورهای مصنوعی و الگوریتم زنبور عسل را معرفی می کنیم.

۱٫ الگوریتم کلونی زنبورهای مصنوعی

الگوریتم کلونی زنبورهای مصنوعی (ABC) توسط کارابوگا در سال ۲۰۰۵ برای بهینه سازی واقعی پارامترها ارایه شد، این الگوریتم یک الگوریتم بهینه سازی جدیدا معرفی شده است و رفتار کاوشی کلونی زنبورها را برای مسایل بهینه سازی بدون محدودیت شبیه سازی می کند. برای حل مسائل بهینه سازی با محدودیت یک روش اداره محدودیت با این الگوریتم ترکیب می شود.

در یک کلونی زنبور عسل واقعی ، وظایفی وجود دارد که توسط افراد تخصصی شده انجام می شود. این زنبورهای متخصص تلاش می کنند تا میزان شهد ذخیره شده در کندو را با انجام تقسیم کار و خودسازماندهی موثر حداکثر کنند. مدل کمینه انتخاب جستجوی غذا توسط گروه های هوشمند زنبور در یک کلونی زنبور عسل ، که الگوریتم ABC اتخاذ کرده است ، شامل سه نوع زنبور است : زنبورهای کارگر ، زنبورهای ناظر ، و زنبورهای پیشاهنگ (یا دیده ور) .

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

۱- مقدار دهی اولیه به موقعیت های منابع غذایی
۲- هر زنبور کارگر یک منبع غذایی جدید در مکان منبع غذایی خود تولید می کند و منبع بهتر را استخراج می کند .
۳- هر زنبور دیده ور یک منبع را وابسته به کیفیت راه حلش انتخاب می کند و یک منبع غذایی جدید رادر مکان منبع غذایی انتخاب شده تولید می کند و منبع بهتر را استخراج می کند.
۴- تعیین منبعی که باید متروک شود و تخصیص زنبورهای کارگر آن به عنوان دیده ور برای جستجوی منابع غذایی جدید.
۵- بخاطر سپردن بهترین منبع غذایی پیدا شده تا کنون.
۶- تکرار مرحله های ۲ – ۵ تا زمانی که معیار توقف مقتضی شود.

در مرحله اول الگوریتم ، xi (i = 1, . . . , SN) راه حل ها به صورت تصادفی تولید می شوند که در آن SN تعداد منابع غذایی است . در مرحله دوم الگوریتم ، برای هر زنبور کارگر ، که تعداد کل آنها برابر با نصف تعداد منابع غذایی است ، یک منبع جدید بوسیله رابطه زیر تولید می شود:

vij = xij + φij (xij – xkj) (1

φij یک عدد تصادفی بطور یکنواخت توزیع شده در بازه [-۱,۱] است که تولید موقعیت منابع غذایی همسایه را در اطراف xij کنترل می کند، K شاخص راه حل است که به صورت تصادفی از کلونی انتخاب شده است (K=int(rand ∗ SN) + 1), j = 1, . . .,D و D ابعاد مسئله است . بعد از تولید vi این راه حل جدید با xi مقایسه می شود و زنبور کارگر منبع بهتر را استخراج می کند . در مرحله سوم الگوریتم ، یک زنبور ناظر یک منبع غذایی را با احتمال (۲) انتخاب می کند و منبع جدیدی را در مکان منبع غذایی انتخاب شده توسط (۱) تولید می کند و به همان شکل روش زنبور کارگر، منبع بهتر برای استخراج شدن مورد تصمیم گیری قرار می گیرد.

Fiti میزان شایستگی راه حل xi است.

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

بوسیله رابطه (۳) xij = xj min + (xj max – xjmin )*rand

منبع : http://www.ecg-pnum.ir

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

۲٫۱٫ زنبورها در طبیعت

یک کلونی زنبور عسل می تواند خود را در فواصل دور (بیشتر از ۱۰ کیلومتر) و به صورت هم زمان در چندین جهت گسترش دهد تا از تعداد زیادی از منابع غذایی بهره برداری کند. یک کلونی با گسترش زنبورهای دیده ور خود در دشتهای خوب به موفقیت دست می یابد. به طور کلی قطعه زمینهای گلدار با میزان شهد یا گرده فراوان که می توانند با تلاش کمتری جمع آوری شوند باید توسط زنبورهای بیشتری ملاقات شوند، در حالی که قطعه زمین های گلدار با شهد یا گرده کمتر باید زنبورهای کمتری را دریافت کنند.

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

هنگامی که زنبورها به کندو باز می گردند، آن زنبورهای دیده وری که قطعه زمینی آنها در درجه بالایی از یک حد آستانه معین ارزیابی شده اند (به عنوان ترکیبی از چند جزء اصلی،مثل ظرفیت شکر اندازه گیری شده است) شهد و گرده های خود را ذخیره کرده و به سالن رقص می روند تا رقصی را که به عنوان «رقص چرخشی» شناخته می شود انجام دهند.

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

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

زنبورهای پیرو بیشتری به قطعه زمین هایی با امید بخشی بیشتر فرستاده می شود این موضوع به کلونی اجازه می دهد تا غذا را سریعتر و کارآمدتر جمع آوری کند.

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

۲٫۲٫ الگوریتم زنبور عسل معرفی شده

همان طور که اشاره شد، الگوریتم زنبور عسل یک الگوریتم بهینه سازی است که از رفتار کاوشی طبیعی زنبورهای عسل برای پیدا کردن راه حل بهینه الهام شده است. شکل ۱ شبهه کد الگوریتم را در ساده ترین حالت آن نشان می دهد. این الگوریتم نیازمند تنظیم تعدادی پارامتر است: تعداد زنبورهای دیده ور (n)، تعداد مکانهای انتخاب شده از مکانهای بازدید شده (m)، تعداد بهترین مکان ها از مکانهای انتخاب شده (e)، تعداد زنبورهای تازه نفس استخدام شده برای بهترین مکانهای e (nep)، تعداد زنبورهای استخدام شده برای سایر (m-e) مکان های انتخاب شده (nsp)، اندازه اولیه قطعه زمینها (ngh) که شامل مکان و همسایه های آن می شود و معیار توقف الگوریتم.

الگوریتم با n زنبور دیده ور که به صورت تصادفی در فضای جستجو قرار می گیرند شروع می شود . تابع شایستگی مکان هایی که توسط زنبورهای دیده ور ملاقات می شوند در مرحله ۲ ارزیابی می شود.

۱- مقدار دهی اولیه جمعیت با راه حلهای تصادفی
۲- ارزیابی تابع شایستگی جمعیت
۳- تا زمانی که (شرط توقف ملاقات نشده است)
// تشکیل جمعیت جدید.
۴- انتخاب مکان هایی برای جستجوی همسایه ها
۵- استخدام زنبورها برای مکانهای جدید (زنبورهای بیشتر برای بهترین مکان های e)
۶- انتخاب مناسب ترین زنبور از هر قطعه زمین گل
۷- تخصیص زنبورهای باقی مانده برای جستجوی تصادفی و ارزیابی شایستگی های آنها
۸- پایان حلقه

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

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

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

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

منبع

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

یک کلونی زنبور عسل می‌تواند در مسافت زیادی و نیز در جهت‌های گوناگون پخش شود تا از منابع غذایی بهره‌برداری کند. قطعات گلدار با مقادیر زیادی نکتار و گرده که با تلاشی کم قابل جمع آوری است، به وسیله­ی تعداد زیادی زنبور بازدید می‌شود؛ به طوری که قطعاتی از زمین که گرده یا نکتار کمتری دارد، تعداد کمتری زنبور را جلب می‌کند. پروسهٔ جستجوی غذای یک کلونی به وسیلهٔ زنبورهای دیده­بان آغاز می‌شود که برای جستجوی گلزارهای امید بخش (دارای امید بالا برای وجود نکتار یا گرده) فرستاده می‌شوند. زنبورهای دیده‌بان به صورت کتره‌ای از گلزاری به گلزار دیگر حرکت می‌کنند. در طول فصل برداشت محصول (گل‌دهی)، کلونی با آماده نگه داشتن تعدادی از جمعیت کلونی به عنوان زنبور دیده‌بان به جستجوی خود ادامه می‌دهند.

هنگامی که جستجوی تمام گلزارها پایان یافت، هر زنبور دیده‌بان، بالای گلزاری که اندوختهٔ کیفی مطمئنی از نکتار و گرده دارد، رقص خاصی را اجرا می‌کند. این رقص که به نام رقص چرخشی شناخته می‌شود، اطلاعات مربوط به جهت تکه گلزار (نسبت به کندو)، فاصله تا گلزار و کیفیت گلزار را به زنبورهای دیگر انتقال می‌دهد. این اطلاعات زنبورهای اضافی و پیرو را به سوی گلزار می‌فرستد. بیش‌تر زنبورهای پیرو به سوی گلزارهایی می­روند که امید بخش­تر هستند و امید بیش‌تری برای یافتن نکتار و گرده در آن‌ها وجود دارد. وقتی همهٔ زنبورها به سمت ناحیه‌ای مشابه بروند، دوباره به صورت تصادفی و به علت محدوده­ی رقصشان در پیرامون گلزار پراکنده می‌شوند تا به موجب این کار سرانجام نه یک گلزار، بلکه بهترین گل­های موجود درون آن تعیین موقعیت شوند.

الگوریتم زنبور عسل هر نقطه را در فضای پارامتری – متشکل از پاسخ‌های ممکن- به عنوان منبع غذا تحت بررسی قرار می‌دهد. زنبورهای دیده‌بان – کارگزاران شبیه‌سازی شده – به صورت تصادفی فضای پاسخ­ها را ساده می­کنند و به وسیله­ی تابع شایستگی کیفیت موقعیت­های بازدید شده را گزارش می­دهند. جواب‌های ساده شده رتبه بندی می‌شوند و دیگر زنبورها نیروهای تازه­ای هستند که فضای پاسخ‌ها را در پیرامون خود برای یافتن بالاترین رتبه محل‌ها جستجو می‌کنند که گلزار نامیده می‌شود. الگوریتم به صورت گزینشی دیگر گلزارها را برای یافتن نقطه­ی بیشینه­ی تابع شایستگی جستجو می‌کند

کاربردها 

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

* آموزش شبکه عصبی برای الگو شناسی

* زمان بندی کارها برای ماشین‌های تولیدی

* دسته‌بندی اطلاعات

* بهینه‌سازی طراحی اجزای مکانیکی

* بهینه‌سازی چند گانه

* میزان کردن کنترل کننده‌های منطق فازی برای ربات‌های ورزشکار

هم چنبن نوشته ای با عنوان مقاله های الگوریتم کلونی زنبور عسل (Artificial Bee Colony (ABC) Algorithm) و کاربردهای آن شامل مقالات داخلی و خارجی در همین سایت قرار داده شده است.

الگوریتم زنبور شامل گروهی مبتنی بر الگوریتم جستجو است که اولین بار در سال ۲۰۰۵ توسعه یافت ؛ این الگوریتم شبیه سازی رفتار جستجوی غذای گروههای زنبور عسل است. در نسخه ابتدایی این الگوریتم، الگوریتم نوعی از جستجوی محلی انجام می دهد که با جستجوی کتره ای (Random) ترکیب شده و می تواند برای بهینه سازی ترکیبی {زمانی که بخواهیم چند متغیر را همزمان بهینه کنیم.}یا بهینه سازی تابعی به کار رود.

جستجوی غذا در طبیعت

یک کلونی زنبور عسل می تواند در مسافت زیادی و نیز در جهت های گوناگون پخش شود تا از منابع غذایی بهره برداری کند.
قطعات گلدار با مقادیر زیادی نکتار و گرده که با تلاشی کم قابل جمع آوری است،به وسیلهی تعداد زیادی زنبور بازدید می شود؛ به طوری که قطعاتی از زمین که گرده یا نکتار کمتری دارد، تعداد کمتری زنبور را جلب می کند.
پروسه ی جستجوی غذای یک کلونی به وسیله ی زنبورهای دیده بان آغاز می شود که برای جستجوی گلزار های امید بخش (دارای امید بالا برای وجود نکتار یا گرده) فرستاده می شوند.

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

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

الگوریتم

الگوریتم زنبور هر نقطه را در فضای پارامتری_ متشکل از پاسخ های ممکن_به عنوان منبع غذا تحت بررسی قرار می دهد.”زنبور های دیده بان”_ کارگزاران شبیه سازی شده _به صورت کتره ای (Random) فضای پاسخ ها را ساده می کنند و به وسیله ی تابع شایستگی کیفیت موقعیت های بازدید شده را گزار ش می دهند. جواب های ساده شده رتبه بندی می شوند، و دیگر “زنبورها” نیروهای تازه ای هستند که فضای پاسخ ها را در پیرامون خود برای یافتن بالا ترین رتبه محل ها جستجو می کنند(که “گلزار” نامیده می شود) الگوریتم به صورت گزینشی دیگر گلزار ها را برای یافتن نقطه ی بیشینه ی تابع شایستگی جستجو می کند.

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

الگوریتم زنبور شامل گروهی مبتنی بر الگوریتم جستجو است که اولین بار در سال ۲۰۰۵ توسعه یافت ؛ این الگوریتم شبیه سازی رفتار جستجوی غذای گروه های زنبور عسل است. در نسخه ابتدایی این الگوریتم نوعی از جستجوی محلی انجام می دهد که با جستجوی کتره ای{Random } ترکیب شده و می تواند برای بهینه سازی ترکیبی {زمانی که بخواهیم چند متغیر را همزمان بهینه کنیم.}یا بهینه سازی تابعی به کار رود.

جستجوی غذا در طبیعت

یک کلونی زنبور عسل می تواند در مسافت زیادی و نیز در جهت های گوناگون پخش شود تا از منابع غذایی بهره برداری کند.

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

پروسه ی جستجوی غذای یک کلونی به وسیله ی زنبورهای دیده بان آغاز می شود که برای جستجوی گلزار های امید بخش {دارای امید بالا برای وجود نکتار یا گرده}فرستاده می شوند. زنبورهای دیده بان به صورت کتره ای{Random } از گلزاری به گلزار دیگر حرکت می کنند.
در طول فصل برداشت محصول{گل دهی}، کلونی با آماده نگه داشتن تعدادی از جمعیت کلونی به عنوان زنبور دیده بان به جستجوی خود ادامه می دهند. هنگامی که جستجوی تمام گلزار ها پایان یافت، هر زنبور دیده -بان ، بالای گلزاری که اندوخته ی کیفی مطمئنی از نکتار و گرده دارد، رقص خاصی را اجرا می کند.
این رقص که به نام “رقص چرخشی”{حرکتی مانند حرکت قرقره} شناخته می شود، اطلاعات مربوط به جهت تکه گلزار{نسبت به کندو}، فاصله تا گلزار و کیفیت گلزار را به زنبور های دیگر انتقال می دهد. این اطلاعات زنبور های اضافی و پیرو را به سوی گلزار می فرستد.
بیشتر زنبور های پیرو به سوی گلزار هایی میروند که امید بخش تر هستند و امید بیشتری برای یافتن نکتار و گرده در آنها، وجود دارد.
وقتی همه ی زنبور ها به سمت ناحیه ای مشابه بروند، دوباره به صورت کتره ای {Random } و به علت محدوده ی رقصشان در پیرامون گلزار پراکنده می شوند تا به موجب این کار سرانجام نه یک گلزار ، بلکه بهترین گل های موجود درون آن تعیین موقعیت شوند.

الگوریتم زنبور هر نقطه را در فضای پارامتری- متشکل از پاسخ های ممکن- به عنوان منبع غذا تحت بررسی قرار می دهد.”زنبور های دیده بان”- کارگزاران شبیه سازی شده – به صورت کتره ای{Random } فضای پاسخ ها را ساده می کنند و به وسیله ی تابع شایستگی کیفیت موقعیت های بازدید شده را گزار ش می دهند. جوابهای ساده شده رتبه بندی می شوند، و دیگر “زنبورها” نیروهای تازه ای هستند که فضای پاسخ ها را در پیرامون خود برای یافتن بالا ترین رتبه محل ها جستجو می کنند{که “گلزار” نامیده می شود} الگوریتم به صورت گزینشی دیگر گلزار ها را برای یافتن نقطه ی بیشینه ی تابع شایستگی جستجو می کند.

حال در ادامه با دو الگوريتم از الگويتم های کلونی زنبورها آشنا خواهيم شد. اولين الگوريتم، الگوريتم کلونی زنبورهای مصنوعی است که کاربرد اصلی آن در بهينه سازی می باشد. الگوريتم دوم الگوريتم کاوش زنبورهای عسل میباشد که آن نيز در بهينه سازی کاربرد دارد.

منبع: http://faraebtekari.ir

الگوریتم های الهام گرفته شده از کلونی زنبورها

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

به علاوه آنها يک مدل کمينه از از رفتار کاوشگرانه زنبورها ارائه داند. اين مدل شامل سه مولفه مهم میباشد: ۱)منبع غذايي ۲(زنبورهای کارگر ۳(زنبورهای غيرکارگر. اين مدل دو نوع رفتار را دربرمیگيرد: سربازگيری برای يک منبع شهد و ترک منبع. Teodorovic پيشنهاد داد تا از هوش جمعی زنبورها در توسعه و بهبود سيستمهای مصنوعی با هدف حل مسائل پيچيده در حمل و نقل و ترافيک استفاده شود، همچنين او الگوريتم BCO (Bee Colony Optimization)را ارائه کرد که قادر است مسائل ترکيبی قطعی را همانند مسائل ترکيبی به خوبی حل نمايد. Drias يک روش هوشمندانه جديد را معرفی نمود با نام BSO که الهام گرفته از زنبورهای واقعی است. Wedde يک الگوريتم مسيريابی جديد با نام BeeHive ارائه کرد که الهام گرفته از متدهای ارتباطی و ارزيابی و همچنين رفتار زنبورهای عسل میباشد. در اين الگوريتم عاملها در منطقه شبکه که محدودهی کاوش ناميده میشود، در طول مسيرشان اطلاعات وضعيتی شبکه را به منظور بهنگام سازی جدول مسيريابی محلی جمع آوری می کنند.

کارهای انجام شده که در پاراگراف های قبلی ذکرشد، شامل انواع مختلفی از مسائل بود. تنها دو الگوريتم بهينه سازی عددی در مقالات مبتنی بر رفتار جمعی زنبورهای عسل وجود دارد. Yang الگوريتم زنبورهای مجازی برای حل( (VBAبهينه سازی توابع عددی ارائه داده است. در ابتدا يک تجمع از زنبورهای مجازی ايجاد میشود و تجمع شروع به حرکت کردن در فضای مسئله به صورت تصادفی مینمايد. اين زنبورها هنگامی که يک يا چند منبع غذايي را يافتند که متناظر است با يافتن مقدار تابع، با يکديگر تعامل برقرار میکنند راهحل برای مسئله بهينه سازی از شدت و قوت تعاملات زنبورها با يکديگر بدست خواهد آمد. برای بهينه سازی توابع چندمتغييره Karaboga الگوريتم کلونی زنبورهای مصنوعی ( ABC ) را ارئه داد که با الگوريتم زنبورهای مجازی تفاوت دارد.

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

الگوریتم کلونی زنبور عسل مانند سایر الگوریتم های هوش ازدحامی مرتبط بر رفتار تصادفی المان های آن است و برای حل مسائل بهینه سازی کاربرد دارد. بسیاری از الگوریتم های هوش ازدحامی با الهام گرفتن از طبیعت ایجاد شده اند مانند الگوریتم کلونی مورچگان، الگوریتم پرندگان، الگوریتم فاخته و الگوریتم کلونی زنبور عسل یا Artificial bee colony algorithm که به صورت مخفف BCO نامیده میشود (Bee Colony Optimization) .

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

یکی دیگر از روش های حل مسائل بهینه سازی الگوریتم های هوش ازدحامی است که الگوریتم زنبور عسل از جمله این الگوریتم ها است. الگوریتم زنبور (Bee Algorithm) یک الگوریتم گروهی مبتنی بر جستجو است که در سال ۲۰۰۵ میلادی ابداع شده است.این الگوریتم شبیه‌ سازی رفتار جستجوی غذای گروه‌های زنبور عسل است. در نسخه ابتدایی این الگوریتم، الگوریتم نوعی از جستجوی محلی انجام می‌دهد که با جستجوی تصادفی کتره­­ا ترکیب شده و می‌تواند برای بهینه سازی ترکیبی یا بهینه‌ سازی تابعی استفاده شود.

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

منبع: http://faraebtekari.ir

الگوریتم کلونی زنبور عسل (ABC)

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

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

این اطلاعات توسط جهش تصادفی تغییرمی یابد ، اما بطورواقعی نیروی محرکه باعث توسعه تکاملی درترکیب و جایگزینی مواد کروموزومی در طول تولید مثل میشود. اگر چه تلاش های متعددی برای گنجاندن این اصول در روال بهینه سازی دراوایل دهه ۱۹۶۰انجام شده ، الگوریتم های ژنتیک برای اولین بار بر یک مبنای نظری صوتی ایجاد شده بودند. این اصطلاح جمعی در حالت کلی برای اشاره به هر مجموعه دار از تعامل افراد مورد استفاده قرار می گیرد. به عنوان یک مثال کلاسیک از ازدحام زنبورهایی که در اطراف کندوی خود تجمع کردند ، اما در استعاره به راحتی می توان به سیستم هایی معماری مشابهی دارند توسعه داد. در کلونی مورچه ها،مورچه ها می توانند به عنوان گروهی ازعوامل تصور شوند ، همچنین ازدحام پرندگان گروهی از پرندگان است. یک سیستم ایمنی ، گروهی از سلول ها ومولکول ها است در حالی که یک جمعیت شامل گروهی از مردم است.

الگوریتم بهینه سازی ازدحام ذرات (PSO) شبیه سازی می کند رفتار اجتماعی پرندگان یا ماهی ها توسط ابرهارت و کندی در سال ۱۹۹۵ معرفی شده است. روش های گوناگونی به مدل رفتار هوشمند خاص ازدحام زنبور عسل پیشنهاد شده است و برای حل مسایل از نوع ترکیبی استفاده شده است.آنها یک ایده روبات بر رفتار جستجوی غذا از زنبورها را ایجاد کرده اند . معمولا ، همه این ربات از لحاظ فیزیکی و عملکرد یکسان هستند ، به طوری که هر ربات را می توان به طور تصادفی جایگزین دیگری کرد. ازدحام دارای تحمل قابل توجهی است ؛ شکست در یک عامل عملکرد کل سیستم را متوقف نمی کند. روبات های فردی ، مانند حشرات ، دارای قابلیت های محدود و دانش محدود از محیط زیست است. از سوی دیگر ، توسعه ازدحام هوش جمعی است. آزمایشات نشان داد که رباتها مانند حشرات مانند در انجام وظایف واقعی رباتیک موفق هستند.
آنها همچنین یک مدل انتخاب علوفه را توسعه داده اند که منجر به ظهور هوش جمعی می شود که متشکل از سه اجزای ضروری است: منابع غذایی ، کارگرهایی که پی علوفه می گردند و ، کارگرهایی که پی علوفه نمی گردند. این مدل دو رفتار برجسته را تعریف می کند: استفاده به یک منبع شهد و رها کردن یک منبع.
تئودور واس به استفاده از هوش جمعی زنبوردر توسعه سیستم های مصنوعی با هدف در حل مسایل پیچیده در ترافیک و حمل ونقل پیشنهاد داده است. تئودور واس همچنین پیشنهاد کرد بهینه سازی متا اکتشافی کلونی زنبور عسل (BCO) که قادر به حل قطعی مسائل ترکیبی ، و همچنین مسائل ترکیبی با مشخصه عدم قطعیت است[۱۱]. درایز و همکاران. معرفی یک رویکرد جدید هوشمند یا متا اکتشافی به نام ازدحام بهینه سازی زنبورها (BSO) است ، که از رفتار زنبور عسل واقعی الهام گرفته است . متا – اکتشافی برای حل مشکل ۳ – بعدی پایه ریزی شده روی روند تولید مثل زنبور عسل معرفی شده است. یک الگوریتم مسیر یابی جدید به نام کندوی عسل که از روش های ارزیابی ارتباطی و مشخص الهام گرفته شده زنبورهای عسل است.

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

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

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

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

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

درالگوریتم ABC ، موقعیت یک منبع غذایی یک راه حل مسئله بهینه سازی را نشان می دهند و مقدار شهد از منبع غذا مربوط به شایستگی راه حل همراه میشود. تعداد زنبورهای کارگر یا زنبورهای تماشاچی برابر با تعداد راه حل ها در جامعه است. دراولین قدم ، ABC جمعیت اولیه را به صورت تصادفی توزیع میکند P (G = 0) راه حل های SN (مواضع منبع غذایی) ، که در آن SN نشان دهنده اندازه جمعیت است.

هر راه حل (منبع غذایی) ( i = 1, 2, . . . , SN ) xi بردار D – بعدی است. در اینجا ،D تعداد پارامترهای بهینه سازی است. پس از مقداردهی اولیه ، جمعیت موقعیت ها (راه حل ها) در معرض تکرار چرخه است ، C = 1, 2, . . . ,Cmax؛ که C فرایندهای جستجوی زنبورهای کارگر و جستجوگر و طلایه دار است.

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

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

که در آن fit iمیزان شایستگی از راه حل i توسط زنبور کارگر آن ارزیابی شده است که ارزیابی متناسب با مقدار شهد منبع غذایی در موقعیت i است و SN تعدادی از منابع غذایی که برابر با تعداد زنبورهای کارگر (BN) است. در این روش، زنبورهای کارگر اطلاعات خود را با زنبورهای تماشاچی تبادل میکنند . به منظور تولید یک موقعیت غذایی انتخاب شده از قبلی ، ABC عبارت زیررا استفاده میکند:

که در آن {k ∈ {۱, ۲, . . . , BN و {j ∈ {۱, ۲, . . . ,D شاخص شان به صورت تصادفی انتخاب شده است . هر چندK به صورت تصادفی تعیین شده است ، آن متفاوت از i می باشد . φi,j یک عدد تصادفی بین -۱,۱]] است. آن تولید موقعیت منبع غذایی همسایه در اطراف xi,j را کنترل میکند ، وتغییرات مقایسه ای موقعیت های غذایی همسایه توسط زنبور عسل به صورت بصری را ارائه می شود . معادله ۲٫۲ پارامترهای مختلفی بین xi,j و xk,j نشان می دهد ، همچنین تغییرات در موقعیت xi,j ، کاهش می یابد. بنابراین ، به نوعی جستجو به راه حل بهینه در فضای جستجو نزدیک می شود ، گام مرحله طور تتاوقی کاهش می یابد . اگر پارامتر های تولید شده توسط این عملیات بیشتر ازحداز پیش تعیین شده خودش باشد ،پارامتر را می توان به عنوان مقدار قابل قبول انتخاب کرد. منبع غذایی که شهد آن توسط زنبورها رها شده با یک منبع ماده غذایی جدید توسط زنبورهای طلایه دار جایگزین میشود.

در الگوریتم ABC این با تولید موقعیت به صورت تصادفی شبیه سازی شده و جایگزین آن منبع رها شده میشود. در الگوریتم ABC ، اگر یک موقعیت بیشتر ازیک عدد از پیش تعیین شده چرخه به نام حد بهبود نیابد پس آن منبع غذایی فرض شده ترک خواهد شد.پس از انتخاب هر منبع ، موقعیت vi,j تولید شده و سپس توسط زنبور مصنوعی ارزیابی شد ، عملکرد آن با xi,j مقایسه میشود، اگر مواد غذایی جدید برابریا شهد بهتری از منبع قبلی داشت، آن را با قبلی در حافظه جایگزین میکند. در غیر این صورت ، آن قبلی را نگه میدارد. به عبارت دیگر ، یک مکانیسم انتخاب حریص عمل انتخاب بین منابع غذایی قبلی و فعلی را انجام میدهد.الگوریتم ABC در حقیقت چهار فرآیند مختلف انتخاب را به کار میگیرد :

(۱) فرآیند انتخاب جهانی توسط زنبورهای تماشاچی مصنوعی برای کشف مناطق امیدبخش که در(۲٫۱) شرح داده شده است ،
(۲) یک فرآیند انتخاب محلی در منطقه توسط زنبورهای کارگرمصنوعی انجام شده و تماشاچیان با توجه به اطلاعات محلی (در مورد زنبور عسل واقعی ،این اطلاعات شامل رنگ ، شکل و عطر گل) (زنبورها قادربه شناسایی نوع منبع شهد نمیشوند تا زمانی که به محل مناسب می رسند و بین منابع در حال رشد بر اساس عطر و بوی آنها تبعیض وجود دارد) برای تعیینیک همسایه منبع غذا در اطراف منبع موجود در حافظه که در (۲٫۲) تعریف شده است ،
(۳) روند انتخاب محلی به نام فرآیند انتخاب حریص توسط تمام زنبورها انجام میشود در آن اگر مقدار شهد منبع کاندید بهتر از فعلی باشد ، زنبورفعلی را فراموش میکند و منبع کاندید را حفظ میکند. در غیر این صورت ، زنبور فعلی را در حافظه نگه می دارد.
(۴) یک فرایند انتخاب تصادفی توسط زنبور طلایه دار انجام میشود.
ازتوضیحات فوق روشن است که سه پارامتر کنترل وجود دارد که در ABC اصلی استفاده می شود :
– تعداد منابع غذایی که با تعداد زنبورهای کارگر یا زنبورهای تماشاچی برابر است (SN) ،
– مقدار حد (the value of limit)،
-حداکثر تعداد چرخه (MCN).

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

توابع عددی

تابع مرکب است اگر آن دو یا چند بهینه محلی داشته باشد. تابع از متغیرهای جدا از هم است در صورتی که آن به عنوان یک مجموع توابع یک متغیر بازنویسی شود. مسئله سخت تر است اگر تابع مرکب باشد. فرایند جستجو باید قادر به دوری کردن ازمناطق اطراف مینیمم محلی به منظور تقریب زدن ، تا آنجا که ممکن ، برای مطلوب جهانی است. پیچیده ترین مورد زمانی به نظر می رسد که بهینه های های محلی به صورت تصادفی در فضای جستجو توزیع شده است.ابعاد فضای جستجو یکی از عوامل مهم دیگر در پیچیدگی مسئله است. مطالعه مسئله ابعاد و ویژگی های آن توسط فریدمن انجام شد . با استفاده از پنج تابع معیار کلاسیک تابع اول تابع Griewank که درمینیمم جهانی خود مقدار ۰ است . محدوده دهی اولیه برای تابع (۲و۲-) است. تابع Griewank اصطلاحی است که وابستگی متقابل بین متغیرها را تولید میکند . هدف غلبه بر شکست تکنیک هایی که هر متغیر را بطور مستقل بهینه سازی میکند . بهینه ی تابع Griewank به طور منظم توزیع شده است. از آنجا که تعداد بهینه ی محلی بوسیله ابعادافزایش می یابد .

تابع دوم تابع Rastrigin که مقدار ۰ است در مینیمم جهانی خود است . محدوده دهی اولیه برای تابع (۲و۲-) . این تابع مبتنی بر تابع Sphere به علاوه مدولاسیون کسینوس ،مینیمم محلی بسیاری را تولید میکند . بنابراین ،تابع مرکب است . نقاط مینیمم به طور منظم توزیع شده است. قسمت دشوار در پیدا کردن راه حل های بهینه در این تابع این است که یک الگوریتم بهینه سازی به راحتی می تواند به سمت بهینه جهانی شدن در بهینه محلی به دام بیفتد.

تابع سوم، تابع Rosenbrock که مقدار در مینیمم جهانی خود ۰ است. محدوده دهی اولیه برای تابع (۲و۲-)است. بهینه جهانی در داخل دره ژرف ، باریک ، به شکل سهمی وار مسطح می باشد. از آنجا که همگراشدن بهینه جهانی مشکل است ، متغیرها به شدت وابسته هستند وسطح شیب دار به طور کلی به سمت نقطه مطلوب نیست ، این مسئله ای است که بارها و بارها برای آزمایش کردن عملکرد الگوریتم های بهینه سازی مورد استفاده قرار گیرد.

تابع چهارم تابع Ackley است که درمینیمم جهانی مقدارش ۰ است. محدوده دهی اولیه برای تابع (۲و۲-) است. Ackleyیک اصطلاح نمایی که سطح خود را با مینیمم محلی متعدد پوشش می دهد. الگوریتمی که استفاده میشود در یک بهینه محلی به دام خواهد افتاده ، اما هر راهبرد جستجو که منطقه گسترده تر را تجزیه و تحلیل خواهد شد قادر به عبور از میان دره بهینه و دستیابی به نتایج بهتر است . به منظور به دست آوردن نتایج خوب برای این تابع ، استراتژی جستجو باید ترکیبی از اجزای های اکتشافی و استثمار کارآمد باشد .

تابع پنجم تابع Schwefel است که در بهینه جهانی خود مقدار ۰ است (۳٫۵). محدوده دهی اولیه برای تابع (۲و۲-) است. سطح تابع Schwefel از تعداد زیادی قله و دره متشکل است. تابع بهترین مینیمم ثانویه به دور از مینیمم جهانی دارد که در آن بسیاری از الگوریتم های جستجو دام افتاده است. علاوه بر این ، مینیمم جهانی نزدیک مرزهای دامنه است.

پیکر بندی برای الگوریتم ABC

پارامترهای کنترل الگوریتم ABC شامل :حداکثر تعداد چرخه (MCN) که با حداکثر تعداد نسل برابر است و سایز کلونی با اندازه جمعیت برابر است . درصد اززنبورهای ناظر ۵۰ ٪ از زنبورهای کارگرهستند وتعدادی از زنبور های طلایه دار به عنوان یک انتخاب بود. افزایش تعداد طلایه داران اکتشاف را ترغیب میکند همچنانکه که افزایش تماشاچیان بر روی منبع غذایی ،اکتشاف را افزایش می دهد . به طور متوسط مقادیر توابع از بهترین راه حلها پیدا شده توسط الگوریتم برای ابعاد مختلف ثبت شده است.

نتیجه گیری

در این مقاله تلاش شده است الگوریتم ABC یک الگوریتم هوش جمعی و مبتنی بر جمعیت است بررسی شده است.
الگوریتم ABC در توابع عددی دوبعدی بالا مورد آزمایش قرار گرفت. از شبیه سازی نتایج آن منعقد می شود که الگوریتم پیشنهاد شده توانایی خروجی مینیمم محلی را دارد و می تواند برای توابع چند متغیره و بهینه سازی توابع مرکب موثر باشد.

منبع: http://faraebtekari.ir

بهینه سازی کلونی زنبورها

حرکتی مساعی گونه برای حل مسائل حمل و نقل و جابجایی پیشرفته

چکیده

سیستمهای طبیعی مختلفی به ما یاد میدهند که ارگانیسمهای خارجی بسیار ساده ایی توان تولید سیستمهایی با قابلیت انجام کارهایی بسیار پیچیده به کمک برهم کنشهای پویا با هم را دارند.
متاهیوریستیک (ابرکشف) کلونی زنبورها (BCO) در این مقاله آورده شده است.کلونی مصنوعی زنبورها در پاره ایی نزدیک به هم و در مقایسه با کلونی زنبورهای طبیعی , متفاوت عمل میکنند.
BCO به همان میزان که قابلیت حل مسائل ترکیبی قطعی را دارد , قادر به حل مسائل ترکیبی ایی است که دارای عدم قطعیت نیز میباشند.
توسعه ی الگوریتم کشف کننده ی جدید برای حل مسئله ی Ride-Matching به کمک راه پیشنهاد شده (استفاده از کلونی زنبورها) راهی روشنگر برای نشان دادن قابلیتهای این روش محسوب میشود.

معرفی

شمار زیادی از مدلهای مهندسی و الگوریتمهایی که برای حل مسائل پیچیده به کار میرود بر اساس کنترل و مرکزگرایی بنا شده اند.برخی از سیستمهای طبیعی (کلونی های حشرات اجتماعی) به ما یاد میدهند که یک سری ارگانیسمهای ساده ی خارجی قابلیت تولید سیستمهایی را دارند که به کمک بر هم کنشهای پویا قابلیت انجام اعمال بسیار پیچیده را دارند.
گروه زنبورها به خاطر استقلال داخلی کلونی و عملکردهای توزیع شده و سیستم درون سازمانی یکی از بهترین کلونی ها برای توضیح این مسئله شناحته شده است.
در سالهای اخیر محققان برای تولید سیستمهای جدید مصنوعی (در حیطه ی هوش مصنوعی) شروع به تحقیق درباره ی طرز رفتار حشرات اجتماعی کرده اند.
(BCO ( Bee Colony Optimization که مسیر جدیدی را در هوش جمعی بررسی میکند در این مقاله بررسی شده است.هدف اصلی این مقاله بررسی این امکان است که به کمک سیستم مصنوعی زنبورها بتوان قدمی را در پیدا کردن راه حلهایی جامع برای حل مسائلی که با عدم قطعیت مواجه هستند برداشت.
ادامه ی مقاله در قسمتهای دوم و سوم آمده است.قسمت دوم به توضیح BCO میپردازد در حالیکه قسمت سوم به مطالعه ی موضوعی مربوط به مسئله Ride-Matching میپردازد.

The Bee Colony Optimization : The New Computational Paradigm

حشرات اجتماعی (زنبورعسل , زنبور معمولی , مورچه ها , موریانه ها) برای میلیونها سال بر روی کره زمین زندگی کرده اند , آشیانه های مختلف و بسیاری از ساخته های پیچیده تر ساخته اند و آذوقه شان را سازماندهی کرده اند.کلونی حشرات اجتماعی بسیار انعطاف پذیر محسوب میشود و به خوبی قابلیت همساز شدن با محیط جدید را دارند.این انعطاف پذیری این امکان را به کلونی میدهد تا بتواند حتی با مواجه شدن با شرایط سخت و مشکلات , به زندگی خود ادامه دهد.
پویاگرایی جمعیت حشرات نتیجه ایی از عملکردها و تعاملات بین حشرات با یکدیگر و با محیط اطراف است.تعاملات بین حشرات بر اساس یک سری عوامل فیزیکی و شیمیایی امکان پذیر شده است.محصول نهایی این تعاملات و عملکردها , رفتار اجتماعی این گونه حشرات محسوب میشود.
مثالی برای چنین رفتارهایی , رقص مورچه ها در هنگام جمع آوری محصول است.مثال دیگری برای این حالت ترشح فنومون (هورمون جنسی) در مورچه هاست که موجب راه گذاری برای مورچه های دیگر خواهد شد.این سیستمهای ارتباطی بین حشرات مختلف موجب به وجود آمدن مقوله ایی به نام “هوش اشتراکی” میشود.به این معنی که حشرات فوق به هنگام قرار گرفتن در کنار یکدیگر دارای فاکتوری هوشمند میشوند که در غیاب یکدیگر قادر به انجام چنین کاری نیستند.

۱٫ Bees In Nature

سیستم سازمانی زنبورها بر اساس یک سری قوائد ساده ی خارجی حشرات بنا شده است.با اینکه نژادهای بسیاری از حشرات مختلف بر روی کره ی زمین موجود هستند و همین باعث تفاوتهایی در الگوی رفتاری آنها میشود , ولی با اینحال این سری حشرات اجتماعی را میتوان دارای قابلیت حل مسائل پیچیده دانست.بهترین مثال برای این حالت روند تولید نکتار (شهد) محسوب میشود که در نوع خود یک فرایند ساماندهی شده ی پیشرفته محسوب میشود.هر زنبور ترجیح میدهد که راه قبلی زنبور هم کندوی خود را دنبال کند تا اینکه خود به دنبال گل جدید بگردد.
هر کندوی زنبور عسل دارای مکانی معروف به سالن رقص است که در آنجا زنبورها با انجام حرکتی خاص , هم کندوییهای خود را راضی میکنند تا راه آنها را برای رسیدن به گلها برگزینند.اگر یک زنبور تصمیم بگیرد که به دنبال نکتار برود , با انتخاب زنبور هم کندوی رقاص خود , راه قبلی را دنبال میکند تا به گل برسد.با رسیدن زنبور به گلها و جمع آوری شهد قادر به انجام کارهای زیر است :
الف : منبع غذا را رها کند و دوباره به دنبال زنبور رقصانی بگردد تا بتواند منبعی جدید پیدا کند.
ب : خود به دنبال منابع غذایی جدید بگردد.
ج : در کندو اقدام به رقصیدن کرده و زنبورهای جدیدی را به دنبال خود بکشاند.
بر اساس احتمالات اندازه گیری شده , زنبور اقدام به انجام یکی از حالات بالا میکند .در مکان رقص , زنبورها اقدام به پیشنهاد مکانهای مربوط به جمع آوری نکتار به دیگران میکنند.مکانیزم انتخاب یک زنبور توسط زنبوری دیگر هنوز شناخته شده نیست ولی تا به امروز روشن شده است که این امر بیشتر مربوط به کیفیت نکتار پیدا شده توسط زنبور رقاص است.
لوسیچ و تدوروویچ اولین کسانی بودند که از رویه های پایه و ساده ی زنبوری برای حل کردن مسائل ترکیبی بهینه سازی استفاده کردند.آنها سیستم زنبوری (BS) را معرفی کردند و از آن برای حل مساله ی معروف Travelling Salesman استفاده کردند.در ادامه به استفاده های BCO در حل مسائل پیشرفته اشاره خواهیم کرد.
در کلونی مصنوعی طراحی شده توسط ما شباهتها و تفاوتهایی با کلونهای واقعی زنبورها در طبیعت وجود دارد.در ادامه به معرفی FBS (Fuzzy Bee System) میپردازیم که قادر به حل مسائل ترکیبی *طرح شده توسط انسانها* است.به کمک FBS , Agent ها در ارتباطات با همدیگر از قوانین تقریبی دلیلگرایی و منطق Fuzzy استفاده میکنند.

۲٫ The Bee Colony Optimization Metaheuristic

در BCO , مامورهایی که ما به آنها “زنبور مصنوعی” میگوییم با همدیگر اجتماع میکنند تا بتوانند قادر به حل مسائل مشکلتر باشند.تمامی زنبورهای مصنوعی در ابتدای فرایند جستجو , در کندوی اصلی قرار دارند.در فرایند جستجو نیز , زنبورهای مصنوعی به طور کاملا مستقیم با یکدیگر ارتباط برقرار میکنند.هر زنبور مصنعوی یک سری حرکات محلی خاص انجام داده و به کمک آنها قادر خواهد بود تا راه حلی را بری مشکل فعلی خود پیدا کند.
این زنبورها تک تک راه حلهای کمکی و زیرپایه ایی را ارائه میدهند تا در آخر با ادغام این راه حلها , راه حل اصلی برای حل مسئله ی ترکیبی به دست بیاید.
روند جستجو از تکرارهای پشت سر هم تشکیل شده است.اولین تکرار زمانی پایان میابد که اولین زنبور راه حل زیر پایه ی خود را برای حل مسئله ی اصلی ارائه دهد.
بهترین راه حل زیرپایه در خلال اولین تکرار انتخاب شده و پس از آن , تکرار دوم شروع خواهد شد.در تکرار دوم , زنبورهای مصنوعی شروع به پیدا کردن راه حلی جدید برای مسئله ی زیر پایه میکنند و…
در پایان هر تکرار حداقل یک و یا چند راه حل ارائه شده وحود دارد , که آنالیست مقدار همگی آنها را مشخصی میکند.
به هنگام حرکت در فضا , زنبورهای مصنوعی ما یکی از دو حرکت “حرکت به سمت جلو” و یا “حرکت به سمت عقب” را انجام میدهند.
به هنگام “حرکت به سمت جلو” زنبورها راه و روشهای جدیدی را برای حل مسئله پیدا میکنند.آنها اینکار را به کمک یک سری جستجوهای شخصی و اطلاعات بدست آمده ی گذشته انجام میدهند.
بعد از آن , زنبورها عمل “حرکت به سمت عقب” را انجام میدهند که همان برگشتن به کندوی اصلی است.در کندو همگی زنبورها در یک فرایند “تصمیم گیری” شرکت میکنند.ما در نظر میگیریم که هر زنبوری قابلیت درک و دریافت اطلاعات زنبورهای دیگر را بر اساس کیفیت دارد.به کمک این روش , زنبورها این قابلیت را دارند که با استفاده از اطلاعات دیگران , راههای بهتر حل مسئله را پیدا کنند.
براساس اطلاعات جدیدی که در مورد کیفیت راه حل به دست می آید , زنبور میتواند تصمیم بگیرد که :
الف) منبع راه حل خود را رها کرده و در سالن رقص به دنبال کسی بگردد که منبعی با کیفیت بیشتر در اختیار دارد.
ب) بدون اینکه کسی را جذب کند , دوباره به سراغ منبع راه حل خود برود.
ج)در سالن رقص با انجام حرکاتی خاص (رقصیدن) سعی در جمع کردن زنبورهای دیگر به دور خود داشته باشد.
بر اساس میزان کیفیتی که زنبور از منبع خود به دست می آورد , فاکتوری به نام “وفاداری” در وی بوجود می آید که در واقع همان وفاداری به راهی است که خود زنبور انتخاب کرده است.بار دومی که زنبورهای مصنوعی برای پیدا کدن راه حل مسئله به حرکت در می آیند , اینبار سعی در پیدا کردن راههای جدیدی برای حل مسوله دارند و بعد از اینکار دوباره عمل “حرکت به سمت عقب” را انجام داده و به کندو برمیگردند و دوباره در کندو در بحثی که در مورد پیدا کردن بهترین راه شکل گرفته , شرکت میکنند.
این روند زمانی پایان میابد که یک راه حل تقریبا کامل برای مسئله پیدا شود.
مثل برنامه نویسی پویا , BCO نیز میتواند مسائل ترکیبی بهینه سازی را در هر مرحله (تکرار) به میزانی حل کند.هر کدام از مراحل مشخص شده دارای یک مقدار بهینه سازی خاص است.بگذارین اشاره کنیم که :
{ST={st1 + st2 + … + stm
همانطور که میبینید هر Stage (مرحله) شامل یک سری مراحل از قبل انتخاب شده است.در ادامه میبینید که به کمک کمیت B ما تعدا زنبورهایی را که در این فرایند شرکت میکنند را مشخص میکنیم و به کمک I , تعداد کل مراحل (تکرار) هایی را که انجام میپذیرند را نشان میدهیم.مجموعه ی تمامی راه حلهای زیرپایه را نیز به کمک Sj نشان میدهیم که در آن j دارای مقادیر ۱ تا m میباشد.

در زیر کد پیش ساخت BCO را مشاهده میکنید :

الف) شروع : مشخص کردن تعداد زنبورها (B) و تعداد تکرارها (I). مشخص نمودن تعداد مراحل (ST).پیدا کردن هر گونه راه حل قابل حل x از مسئله.
این راه حل در واقع بهترین و اولین راه حل انتخاب توسط ما خواهد بود.

ب) Set i:=1 , Until i=I و تکرار کن مراحل بعدی را

ج) Set j:=m , Until j=m و تکرار کن مراحل بعدی را

حرکت به سمت جلو : رفت : به زنبورها این امکان را میدهد که از کندو بیرون آمده و قابلیت انتخاب B راه حل را از مجموعه ی راه حلهای زیرپایه Sj در STj داشته باشند.

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

Set j:=j+1

د)اگر بهترین راه حلی (Xi) که در I امین تکرار بدست آمد , بهتر از بهترین راه اخیر بدست آمده بود , آنگاه فاکتور بهترین راه حل را به روز میکنیم : X:=xi

ه) ۱+Set i:=i
بطور کل حرکتهای جلویی و عقبی در BCO میتوانند نقش فرعی را بگیرند به این معنی که تا زمانیکه یکی از فاکتورهای مهم کامل نشده است , این دو به کار خود ادامه دهند.این فاکتور مهم به عنوان مثال میتواند “بیشترین مقدار رفت و برگشت ها” و یا برخی دیگر از موارد مورد نظر توسط خود اپراتور باشد.
در BCO , زیر مدلهای مختلفی که به توصیق چگونگی حالات زنبورها میپردازد و یا منطق گرایی آنها را مشخص میکند به راحتی قابلیت توسعه و تست شدن را دارند.به این معنی که الگوریتمهای متفاوتی از BCO را میتوان طراحی کرد.
این مدلها میتوانند به توصیف چگونگی ترک کردن منبع اولیه توسط زنبورها , ادامه دادن رفت و برگشت بین کندو و منبع توسط زنبور و یا چگونگی رقصیدن زنبور برای جمع کردن دیگر زنبورها به دود خود را توضیح دهند.

۳٫ The Fuzzy Bee System

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

الف) راه حل زیرپایه ی بعدی که باید به راه حل اصلی اضافه شود چیست ؟
ب) آیا باید راه حل زیرپایه ی فعلی را رها کرد و به دنبال راه حل زیرپایه ی جدیدی رفت ؟
ج)آیا باید به گسترش راه حل زیرپایه ی فعلی ادامه داد ولی فعلا بدنبال دیگر زنبورها نرفت ؟

بسیاری از مدلهای تصمیم گیری بر اساس ابزارهای مدلینگ مختلفی به وجود آمده اند.این حالات کاملا منطقی و عقلی هستند و بر اساس این اطلاعات بوجود آمده اند که ماموران تصمیم گیر (Decision Maker Agents) مامورانی با داشتن بیشترین اطلاعات هستند و همیشه بهترین راه حل را برای پایان دادن به حل مسئله در نظر میگیرند.برای اینکه بتوان مدلهای حل مسئله ی مختلفی را بوجود آورد محققان شروع به استفاده از راههای بی قاعده تری کردند.

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

منبع: http://faraebtekari.ir