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

در این مقاله یک بهینه ساز فرا ابتکاری جدید، به نام الگوریتم جستجوی کلاغ (CSA)، مبتنی بر رفتار هوشمند کلاغ‌ها ارائه شده است. الگوریتم CSA یک روش مبتنی بر جمعیت است که بر اساس این ایده کار می‌کند که کلاغ‌ها غذای اضافی خود را در مکان‌های مخفی ذخیره کرده و در صورت نیاز به غذا آن را بازیابی می‌کنند.

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

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

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

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

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

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

کلیک کنید

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

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

x^i,iter=[x_۱^i,iter,x_۲^i,iter,…,x_d^i,iter]

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

حالت ۱: اطلاع نداشتن از زیر نظر بودن

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

که در رابطه بالا که r_i یک عدد تصادفی با توزیع یکنواخت بین ۰ و ۱ است و fl^i,iter طول پرواز کلاغ i را با تکرار iter می‌باشد. شکل ۱ شماتیک این حالت و تأثیر fl بر روی قابلیت جستجو را نشان می‌دهد. مقادیر کوچک fl منجر به جستجوی محلی می‌شود و مقادیر زیاد منجر به جستجوی سراسری می‌شود. همانطور که شکل ۱ (a) نشان می‌دهد، اگر مقدار fl کم‌تر از ۱ انتخاب شود، موقعیت بعدی کلاغ i روی خط تیره بین x^i,iter و m^i,iter است و همانطور که در شکل ۱ (b) نشان داده شده است ، اگر مقدار fl بیش از ۱ انتخاب شود ، موقعیت بعدی کلاغ i روی خط تیره است که ممکن است از mj فراتر رود.

حالت ۲: اطلاع داشتن از زیر نظر بودن

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

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

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

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

کلیک کنید

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

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

مرحله ۱: مقداردهی و تنظیم پارامترهای اولیه

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

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

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

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

مرحله ۳: ارزیابی تابع تناسب

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

مرحله ۴: ایجاد موقعیت جدید

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

مرحله ۵: بررسی امکان سنجی موقعیت‌های جدید

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

مرحله ۶: ارزیابی تابع تناسب برای موقعیت‌های جدید

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

مرحله ۷: بروزرسانی حافظه

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

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

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

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

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

کلیک کنید

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

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

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

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