الگوریتم جستجوی کلاغ CSA

الگوریتم جستجوی کلاغ

در این پست در مورد الگوریتم جستجوی کلاغ یا همان الگوریتم CSA صحبت خواهیم کرد. این الگوریتم در مقاله ای با عنوان A novel metaheuristic method for solving constrained engineering optimization problems: Crow search algorithm از ژورنال معتبر Computers and Structures در انتشارات الزویر در سال 2016 به چاپ رسیده است. در این مقاله یک بهینه ساز فراابتکاری جدید، به نام الگوریتم جستجوی کلاغ (CSA)، مبتنی بر رفتار هوشمند کلاغ ها ارائه شده است. الگوریتم CSA یک روش مبتنی بر جمعیت است که بر اساس این ایده کار می کند که کلاغ ها غذای اضافی خود را در مکان های مخفی ذخیره می کنند و در صورت نیاز به غذا آن را بازیابی می کنند. در ادامه بصورت کامل این الگوریتم تشریح می شود. برای دانلود مقاله اصلی روی لینک زیر کلیک فرمایید.

دانلود مقاله اصلی

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

الگوریتم جستجوی کلاغ

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

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

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

تشریح تئوری الگوریتم جستجوی کلاغ

در تشریح تئوری الگوریتم فرض بر این است که یک محیط d بعدی شامل تعدادی کلاغ وجود دارد. تعداد کلاغ ها (اندازه گروه ) N است و موقعیت کلاغ i در زمان (تکرار iter) در فضای جستجو توسط یک بردار xi,iter مشخص می شود. که در آن i=1,2,3,…,N و iter=1,2,3,…,Maxiter تعریف می شود. xi,iter در فضای d بعدی به صورت زیر محاسبه می شود.

xi,iter=[x1i,iter,x2i,iter,…,xdi,iter]

هر کلاغ حافظه ای دارد که در آن موقعیت مخفیگاه آن حفظ می شود. در تکرار iter، موقعیت مخفیگاه کلاغ i توسط mi,iter نشان داده می شود. این بهترین موقعیتی است که کلاغ i تاکنون بدست آورده است. در واقع، به یاد هر کلاغ موقعیت بهترین تجربه آن حفظ شده است. کلاغ ها در محیط حرکت می کنند و به دنبال منابع غذایی بهتر (مخفیگاه ها) می گردند. فرض کنید که در تکرار iter، کلاغ j می خواهد از مخفیگاه خود یعنی mj,iter دیدن کند. در این تکرار، کلاغ i تصمیم می گیرد کلاغ j را دنبال کند تا به مخفیگاه کلاغ j نزدیک شود. در این حالت، دو حالت ممکن است رخ دهد:

حالت 1:

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

الگوریتم جستجوی کلاغ فرمول 1

که در رابطه بالا که ri یک عدد تصادفی با توزیع یکنواخت بین 0 و 1 است و fli,iter طول پرواز کلاغ i را با تکرار iter می باشد. شکل 1 شماتیک این حالت و تأثیر fl بر روی قابلیت جستجو را نشان می دهد. مقادیر کوچک fl منجر به جستجوی محلی می شود و مقادیر زیاد منجر به جستجوی سراسری می شود. همانطور که شکل 1 (a) نشان می دهد ، اگر مقدار fl کمتر از 1 انتخاب شود ، موقعیت بعدی کلاغ i روی خط تیره بین xi,iter و mi,iter است. و همانطور که در شکل 1 (b) نشان داده شده است ، اگر مقدار fl بیش از 1 انتخاب شود ، موقعیت بعدی کلاغ i روی خط تیره است که ممکن است از mj فراتر رود.

الگوریتم جستجوی کلاغ برای تعیین موقیت کلاغ

حالت 2:

کلاغ j می داند که کلاغ i آن را دنبال می کند. در نتیجه، کلاغ j برای محافظت از حافظه پنهان خود در برابر سرقت، با رفتن به موقعیت دیگری از فضای جستجو، کلاغ را فریب می دهد. در کل ، حالت های 1 و 2 را می توان به صورت زیر بیان کرد:

الگوریتم جستجوی کلاغ فرمول 2

که در آن rj یک عدد تصادفی با توزیع یکنواخت بین 0 و 1 و APj,iter بیانگر احتمال آگاهی کلاغ j در تکرار iter است. الگوریتم های فرا ابتکاری باید تعادل خوبی بین تنوع (diversification) و تشدید (intensification) ایجاد کند. در الگوریتم CSA ، شدت و تنوع عمدتاً توسط پارامتر احتمال آگاهی (AP) کنترل می شود. با کاهش مقدار احتمال آگاهی ، الگوریتم تمایل به جستجو در منطقه ای محلی دارد که یک راه حل خوب در حال حاضر در این منطقه پیدا شده است. در نتیجه، استفاده از مقادیر کم AP، شدت را افزایش می دهد. از طرف دیگر ، با افزایش مقدار احتمال آگاهی، احتمال جستجو در مجاورت راه حل های خوب فعلی کاهش می یابد و CSA تمایل دارد فضای جستجو را در مقیاس سراسری (تصادفی سازی) کشف کند. در نتیجه ، استفاده از مقادیر زیاد AP تنوع را افزایش می دهد.

روش پیاده سازی الگوریتم جستجوی کلاغ

شبه کد الگوریتم جستجوی کلاغ در شکل 2 نشان داده شده است. روش مرحله ای اجرای الگوریتم در این بخش آورده شده است.

شبه کد الگوریتم جستجوی کلاغ

مرحله 1:

مقداردهی و تنظیم پارامترهای اولیه
مسئله بهینه سازی، متغیرهای تصمیم گیری و محدودیت ها تعریف شده است سپس پارامترهای قابل تنظیم اندازه گروه یا جمعیت اولیه (N)، حداکثر تعداد تکرار (itermax) ، طول پرواز (fl) و احتمال آگاهی (AP) ارزیابی می شوند.

مرحله 2:

مقداردهی موقعیت اولیه و حافظه کلاغ ها

در ابتدا تعداد N کلاغ به طور اعضای گروه یا جمعیت به طور تصادفی در یک فضای جستجوی d بعدی قرار می گیرند. هر کلاغ بیانگر یک حل عملی از مسئله است و d تعداد متغیرهای تصمیم گیری است.

ماتریس کلاغ ها در الگوریتم جستجوی کلاغ

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

حافظه کلاغ ها در الگوریتم جستجوی کلاغ

مرحله 3:

ارزیابی تابع تناسب

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

مرحله 4:

ایجاد موقعیت جدید

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

مرحله 5:

بررسی امکان سنجی موقعیت های جدید

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

مرحله 6:

ارزیابی تابع تناسب برای موقعیت های جدید

مقدار عملکرد تابع تناسب برای موقعیت جدید هر کلاغ محاسبه می شود.

مرحله 7:

بروزرسانی حافظه

کلاغ ها حافظه خود را به صورت زیر به روز می کنند:

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

مرحله 8:

بررسی شرایط خاتمه الگوریتم

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

فلوچارت الگوریتم جستجوی کلاغ

نتیجه گیری

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

منابع

Alireza Askarzadeh, A novel metaheuristic method for solving constrained engineering optimization problems: Crow search algorithm, Computers and Structures 169 (2016) 1–12

فیلم آموزش الگوریتم جستجوی کلاغ در متلب

مطالب زیر را حتما بخوانید

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

این سایت از اکیسمت برای کاهش هرزنامه استفاده می کند. بیاموزید که چگونه اطلاعات دیدگاه های شما پردازش می‌شوند.