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

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

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

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

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

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

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


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

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

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

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

در ابتدا جمعیت اولیه NS راه‌حل است که به‌صورت تصادفی تولیدشده‌اند. ازآنجاکه NS=NP/2 تعداد منابع غذایی می‌باشد و نیز برابر با تعداد زنبورهای کارگر است، NS سایز جمعیت می‌باشد که هر راه‌ حل xi (i=1,2,…,NS) به‌عنوان یک بردار چندبعدی است. سپس زنبورهای عسل یک جستجو گردشی را بر طبق قوانین خاص انجام می‌دهند. به‌منظور به‌روز سازی جواب‌های ممکن، هر زنبور کارگر یک کاندید جدید به‌عنوان منبع غذایی در نظر می‌گیرد. انتخاب بر پایه همسایگی‌های قبلی منابع غذایی صورت می‌پذیرد. راه‌حل کاندید vi می‌تواند توسط جواب‌های قبلی توسط رابطه زیر تولید شود.

که در آن k∈{1,2,…,NS} و j∈{1,2,…,n} اندیس‌هایی هستند که به‌صورت تصادفی انتخاب‌شده‌اند و برای تمایز آن‌ها از یکدیگر این اعداد توسط توزیعی تصادفی در بازه {-1,1} تولیدشده‌اند. راه‌حل‌های کاندید با قدیمی‌ها مقایسه می‌شوند و اگر منابع غذایی جدید کیفیت بهتر یا مساوی منابع غذایی قدیم داشتند، منابع غذایی قدیم با منابع غذایی جدید جایگزین می‌شود. در غیر این صورت منابع غذایی قدیم دست‌نخورده باقی خواهند ماند. زنبورهای کارگر به‌کندی بازگشته تا اطلاعات منابع غذایی با زنبورهای عسل ناظر تقسیم کنند. در فاز بعدی هر زنبور ناظر یکی از منابع غذایی را بنا به برازندگی آن انتخاب می‌کند.احتمالpi از هر ارزش غذایی می‌تواند توسط رابطه زیر محاسبه شود.

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

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

که طبق رابطه بالا، xjmax وxjmin مرزهای بالائی و پائینی متغیر xij هستند که خود xij یک عدد تصادفی بین [0,1] است که توسط توزیع یکنواخت تولیدشده است. این پروسه تا زمانی که تابع به میزان آستانه خود برسد، به‌صورت حلقه وار تکرار خواهد شد. بنابراین با بکارگیری الگوریتم زنبور عسل میتوان بهترین مسیر و راه حل را برای ارسال سیگنال های گره ها در شبکه های موردی خودرویی تعیین نمود.
یکی از مهمترین عملگر هایی که در الگوریتم زنبور عسل کاربرد دارد، عملگر برازش است که همین عملگر با کمک سایر عملگر ها بهینه ترین پاسخ ها را تولید می کند.
فرآیند انتقال پیام در شبکه موردی خودرویی بدین صورت است که گره های موجود در هر خوشه پیام خود را به سر خوشه ها ارسال نموده و سرخوشه ها نیز پیام های خود را به گره مرکزی ارسال می کنند. لذا از فرمول زیر جهت انتقال یک پیام از یک خوشه به گره مرکزی استفاده می گردد.

در رابطه بالا Energy بیانگر انرژی مصرفی برای انتقال یک پیام از خوشه به گره های مرکزی است. n تعداد گره های موجود در خوشه است و ENCHi میزان انرژی مصرفی برای ارسال یک پیام از گره های موجود در خوشه به گره سرخوشه می باشد. پارامتر ER میزان انرژی لازم برای دریافت پیام توسط گره CH است. EP نیز بیانگر میزان انرژی جهت پردازش و تجمیع داده ها توسط گره CH است. پارامتر CHSink نیز بیانگر میزان انرژی لازم برای ارسال سیگنال و پیام ها از گره سر خوشه به گره مرکزی است.

در محاسبه تابع برازش دو فاکتور مهم نقش دارند که عبارتند از: 1- فاصله ارسال 2- انرژی مصرفی جهت ارسال اطلاعات از خوشه به گره مرکزی. این دو فاکتور برای انجام یک مسیریابی درون برنامه ای بسیار موثر است. لذا هدف اصلی الگوریتم زنبور عسل کمینه کردن این فاکتور ها در شبکه موردی خودرویی به منظور بهبود مسیریابی درون خوشه ای است. علاوه بر آنها کاهش تعداد سرخوشه ها را نیز می توانیم در تابع مان لحاظ کنیم که این هم مانند کاهش فاصله ارسال می تواند در کارایی انرژی تأثیر بگذارد زیرا سرخوشه ها انرژی بیشتری نسبت به دیگر گره ها مصرف می کنند. بنابراین برازش که متشکل از گره های معمولی و گره های سرخوشه به بیت های صفر و یک است از رابطه زیر محاسبه می گردد:

در رابطه بالا N تعداد کل گره ها در شبکه بوده، TCH تعداد گره های سرخوشه را تعیین نموده، TD مجموع فاصله ها از تمام گره ها تا گره مرکزی را تعیین نموده و در نهایت RCSD مجموع فاصله از گره معمولی به سرخوشه ها به علاوه مجموع فاصله ها از تمام سرخوشه ها به گره مرکزی را مشخص می نماید.
انرژی مصرفی کمتر، فاصله ارسالی کوتاه تر یا تعداد کمتر سرخوشه ها باعث بیشتر شدن مقدار برازش هر فرد می شوند. الگوریتم زنبور عسل پیشنهادی ما سعی می کند با زیاد کردن ارزش برازش یک راه حل مناسب پیدا کند. بنابراین از کلیه عملگرهای ذکر شده در بالا جهت بهبود خوشه بندی و محاسبه پاسخ بهینه استفاده می گردد.
قسمت آخر رابطه به اهمیت تعداد سر خوشه ها بر می گردد. همان طور که قبلا اشاره شد گره های سر خوشه انرژی بیشتری را نسبت به دیگر گره ها مصرف می کنند. پس ما باید کاری کنیم که تعداد سرخوشه ها به حداقل ممکن برسد. برای این کار ما تعداد سرخوشه ها را در هر نسل از تعداد کل گره ها کم می کنیم که بیشتر شدن مقدار این تفاضل نشان دهنده کاهش تعداد سر خوشه هااست. برای نرمال سازی رابطه ما این قسمت را بر ثابت N تقسیم می کنیم، یعنی قسمت سوم رابطه را به صورت (N-TCH)/N می نویسیم که مانند بالا اگر بخواهیم تاثیر قسمت سوم یا همان تعداد سرخوشه ها را در محاسبه رابطه افزایش دهیم، می توانیم آن را در یک عدد ثابت ضرب کنیم.
بر اساس شبیه سازی های انجام شده ومقایسه بین تاثیر ارزش های متفاوت پارامترها در رابطه، در نهایت رابطه زیر برای محاسبه پیشنهاد می شود:

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

3264 بازدید