الگوریتم سنجاب پرنده — Squirrel Search Algorithm

مقدمه الگوریتم سنجاب پرنده

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

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

تکنیک بهینه‌سازی مبتنی بر راه‌حل منفرد با الهام از پدیده بازپخت متالورژی به نام تبرید یا شبیه ساز حرارتی (SA) طراحی شده است. بهینه سازی ازدحام ذرات (PSO)، بهینه سازی کلونی مورچه ها ACO و کلونی زنبورهای مصنوعی ABC دیگر الگوریتم های بهینه سازی هوشمند یا فراابتکاری هستند که الهام گرفته از رفتار اجتماعی و طبیعت هستند.

الگوریتم سنجاب پرنده در سال ۲۰۱۹ توسط Mohit Jain و همکارانش تحت عنوان مقاله‌ای با نام A novel nature-inspired algorithm for optimization: Squirrel search algorithm در ژورنال معروف Swarm and Evolutionary Computation از انشارات Elsevier منتشر شده است. این مقاله را می‌توانید از اینجا (+) دانلود کنید. در ادامه به تشریح این الگوریتم می‌پردازیم.

زندگی و رفتار سنجاب های پرنده

سنجاب‌های پرنده Flying squirrels گروهی از جوندگان درختی و شب‌زی هستند که با سر خوردن (gliding locomotion) یا پرش حرکت می‌کنند. بر اساس مطالعات جانورشناسی در حال حاضر ۱۵ نوع و ۴۴ گونه سنجاب پرنده شناسایی شده است که اکثریت آ‌ن‌ها در جنگل‌های اروپا و آسیا به ویژه جنوب شرق آسیا یافت می‌شوند. سنجاب‌های پرنده از نظر آیرودینامیکی، پیچیده‌ترین سنجاب‌ها هستند که دارای غشایی چتر مانند (patagia) هستند، که به سنجاب در سر خوردن از درختی به درخت دیگر کمک می‌کند و آن‌ها را قادر می‌سازد که عملیات لیفت و پرش را انجام دهند.

• پاورپوینت آماده الگوریتم سنجاب پرنده (SSA) — کلیک کنید

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

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

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

این رفتار جستجوی پویا هوشمند سنجاب پرنده، منبع اصلی انگیزه برای الگوریتم SSA است. در این الگو، استراتژی جستجوی پویا و مکانیسم سر خوردن سنجاب‌های پرنده به صورت ریاضی برای طراحی SSA برای بهینه‌سازی مدل‌سازی می‌‎شود.

• لیست الگوریتم های فرا ابتکاری — بیشتر بخوانید

الگوریتم سنجاب پرنده SSA

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

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

در طول زمستان، با از بین رفتن پوشش برگ رختان در جنگل‌های برگریز منجر به افزایش خطر شکار می‌شود و از این رو سنجاب‌های پرنده فعالیت خود را کاهش می‌دهند اما در زمستان به خواب زمستانی نمی‌روند. در پایان فصل زمستان، سنجاب های پرنده دوباره فعال می‌شوند. این یک روند تکراری است و تا طول عمر یک سنجاب پرنده ادامه می‌یابد و پایه و اساس SSA را تشکیل می‌دهد. برای ساده سازی مدل ریاضی مفروضات زیر در نظر گرفته شده است:

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

مدل سازی ریاضی الگوریتم سنجاب پرنده

الگوریتم SSA با مکان یابی اولیه تصادفی سنجاب‌های پرنده، شبیه به سایر الگوریتم های مبتنی بر جمعیت شروع می‌شود. مکان (Position) یک سنجاب پرنده با یک بردار در فضای جستجوی d بعدی نشان داده می‌شود.

مقدار دهی اولیه تصادفی

تعداد n سنجاب پرنده (flying squirrels) یا FS در یک جنگل وجود دارد و مکان این سنجاب پرنده را می‌توان با یک بردار مشخص کرد. مکان همه سنجاب های پرنده را می توان با ماتریس زیر نشان داد:

که در آن FS_i,j نشان دهنده بعد j ام سنجاب پرنده i است. توزیع یکنواخت (uniform distribution) برای تخصیص مکان اولیه هر سنجاب پرنده طبق فرمول ۲ استفاده می‌شود.

که در آن FS_L و FS_U به ترتیب کران‌های پایین و بالایی سنجاب پرنده در بعد jام هستند و (۰,۱) U یک عدد تصادفی توزیع شده یکنواخت در محدوده [۰,۱] است.

تابع تناسب

تابع تناسب مکان برای هر سنجاب پرنده با قرار دادن مقادیر متغیر تصمیم (بردار راه حل) در یک تابع تناسب تعریف شده توسط کاربر محاسبه شده و مقادیر مربوطه در ماتریس F زیر ذخیره می‌شود:

مرتب سازی، اعلان و انتخاب تصادفی

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

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

 ایجاد موقعیت (مکان) جدید

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

مورد ۱: سنجاب های پرنده که روی درختان بلوط (FSat) هستند ممکن است به سمت درخت هیکوری حرکت کنند. در این صورت مکان جدید سنجاب‌ها را می‌توان به صورت زیر بدست آورد:

که در آن d_g فاصله سر خوردن تصادفی، R_۱ یک عدد تصادفی در محدوده [۰، ۱]، FS^t_at مکان سنجاب پرنده ای است که به درخت هیکوری رسیده است و t نشان دهنده تکرار فعلی است. تعادل بین اکتشاف exploration و بهره برداری exploitation با کمک G_c ثابت سر خوردن در مدل ریاضی به دست می‌آید و مقدار آن به طور قابل توجهی بر عملکرد الگوریتم تأثیر می‌گذارد.

مورد ۲: سنجاب های پرنده روی درختان معمولی (FS_nt) ممکن است به سمت درختان بلوط حرکت کنند تا نیازهای انرژی روزانه خود را برآورده کنند. در این حالت مکان جدید سنجاب‌ها را می‌توان به صورت زیر بدست آورد:

که در آن R2 یک عدد تصادفی در محدوده [۰، ۱] است.

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

که در آن R3 یک عدد تصادفی در محدوده [۰، ۱] است. احتمال حضور شکارچی P_dp در همه موارد برای کار حاضر ۰,۱ در نظر گرفته شده است. شکل زیر مدل مفهومی حرکت سرخوردن را نشان می‌دهد که توسط سنجاب های پرنده برای حرکت موثر آن‌ها در هنگام جستجوی غذا در شب استفاده می‌شود.

آیرودینامیک سرخوردن

مکانیسم سر خوردن سنجاب های پرنده با سر خوردن تعادلی توصیف می‌شود که در آن مجموع نیروی بالابر (L) و درگ (D) نیروی حاصل (R) ایجاد می‌کند که قدرمطلق آن برابر و مخالف جهت وزن سنجاب پرنده (Mg) است. بنابراین، R یک مسیر پروازی برای سنجاب پرنده با سرعت ثابت (V) فراهم می‌کند. در این کار یک مدل تقریبی از رفتار سر خوردن در طراحی الگوریتم بهینه‌سازی استفاده شده است. یک سنجاب پرنده که با سرعت ثابت سر می‌خورد همیشه با زاویه ϕ نسبت به افقی و نسبت بالابر به کشش یا نسبت سر خوردن پایین می‌آید که به صورت زیر تعریف می‌شود:

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

که در آن ρ (=۱.۲۰۴ kgm ^-۳) چگالی هوا است، C_L به عنوان ضریب بالابر نامیده می‌شود، V (=5.25 ms ^-۱) سرعت و S (=154 cm ^-۲) مساحت سطح بدن است. کشش اصطکاکی به صورت زیر تعریف می‌شود:

که در آن C_D ضریب درگ اصطکاکی است. در سرعت کم، این مولفه درگ بسیار زیاد است در حالی که در سرعت بالا کوچک‌تر می‌شود. از این رو از معادله (۷) زاویه سر خوردن در حالت ثابت به صورت زیر تعیین می‌شود:

فاصله تقریبی سر خوردن (dg) به صورت زیر محاسبه می‌شود (شکل 3b):

سنجاب‌های پرنده معمولاً یک مسافت افقی از ۵ تا ۲۵ متر را در یک سر خوردن طی می‌کنند. فاصله سر خوردن در مدل پیشنهادی در محدوده ۹ تا ۲۰ متر در نظر گرفته شده است.

وضعیت پایش فصلی

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

• پاورپوینت های آماده الگوریتم های فرا ابتکاری — کلیک کنید

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

• الف: ابتدا ثابت فصلی (Sc) را با استفاده از معادله محاسبه می‌شود:

که در آن t = 1، ۲، ۳.

• ب: شرایط پایش فصلی را بررسی کنید، یعنی S^t_c <Smin که در آن Smin حداقل مقدار ثابت فصلی محاسبه شده به صورت زیر است:

که در آن t و t_m به ترتیب مقادیر فعلی و حداکثر تکرار هستند. مقدار Smin بر قابلیت‌های اکتشاف و بهره‌برداری روش پیشنهادی تأثیر می‌گذارد. ارزش بزرگتر Smin کاوش را ترویج می‌کند در حالی که مقادیر کوچک‌تر Smin قابلیت بهره برداری الگوریتم را افزایش می‌دهد. برای هر الگوریتم فراابتکاری موثر، باید تعادل مناسبی بین این دو مرحله وجود داشته باشد.

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

جابجایی تصادفی در پایان فصل زمستان

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

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

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

این توزیع اغلب با فرمول قانون توان بیان می‌شود. توزیع Levy به صورت ریاضی به‌صورت زیر بیان می‌شود:

در جایی که ra و rb دو عدد تصادفی معمولی توزیع شده در [۰، ۱] هستند، β ثابتی است که در کار حاضر ۱.۵ در نظر گرفته می‌شود و σ به صورت زیر محاسبه می‌شود:

معیار توقف

تحمل تابع یک معیار همگرایی رایج است که در آن یک مقدار آستانه مجاز اما کوچک بین دو نتیجه متوالی آخر تعریف می‌شود. گاهی اوقات حداکثر زمان اجرا نیز به عنوان معیار توقف استفاده می‌شود. در پژوهش حاضر حداکثر تعداد تکرار به عنوان معیار توقف در نظر گرفته شده است. شبه کد SSA در الگوریتم ۱ ارائه شده است.

• آموزش الگوریتم های بهینه سازی هوشمند — کلیک کنید

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

نتیجه گیری مقاله الگوریتم سنجاب پرنده

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

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