الگوریتم سنجاب پرنده — Squirrel Search Algorithm
در این مقاله یک الگوریتم بهینهسازی با نام الگوریتم سنجاب پرنده Squirrel search algorithm به اختصار SSA معرفی و تشریح می شود. این بهینه ساز رفتار جستجوی پویای سنجاب های پرنده و روش حرکت کارآمد آنها یعنی سر خوردن را تقلید می کند. سر خوردن یک مکانیسم موثر برای پیمودن مسافت های طولانی است که این پستانداران کوچک از آن برای جستجوی غذا و بقای خود از آن استفاده می کنند. در این مقاله به صورت ریاضی این رفتار برای تحقق فرآیند بهینه سازی مدل می شود.
مقدمه
بهینه سازی فرآیند جستجوی بهترین راه حل ممکن برای یک مسئله یا مشکل خاص، تحت شرایط معین است. در سالهای اخیر مسائل بهینهسازی پیچیده ای در دنیای واقعی در زمینههای مختلف مهندسی، تجارت و اقتصاد پدیدار شده است که با روشهای کلاسیک نمیتوان آنها را در زمان یا دقت کافی حل کرد.
روش ها و اصول فراوانی در پیرامون ما و در طبیعت وجود دارد که برای طراحی روشهای هوش محاسباتی بهمنظور رسیدگی به چنین مسائل بهینهسازی مورد استفاده قرار گیرد. در چند دهه گذشته، محققان الگوریتم های بهینهسازی الهام گرفته از طبیعت را توسعه دادهاند که برخی از رفتارهای بیولوژیکی یا پدیدههای فیزیکی را تقلید میکنند. به عنوان مثال، الگوریتم ژنتیک (GA) را بر اساس مفهوم بقای برترین، یعنی نظریه تکامل داروینی پیشنهاد کرده اند. الگوریتم GA یکی از محبوب ترین و مشهورترین تکنیک های بهینه سازی مبتنی بر جمعیت است.
تکنیک بهینهسازی مبتنی بر راهحل منفرد با الهام از پدیده بازپخت متالورژی به نام تبرید یا شبیه ساز حرارتی (SA) طراحی شده است. بهینه سازی ازدحام ذرات (PSO)، بهینه سازی کلونی مورچه ها ACO و کلونی زنبورهای مصنوعی ABC دیگر الگوریتم های بهینه سازی هوشمند یا فراابتکاری هستند که الهام گرفته از رفتار اجتماعی و طبیعت هستند.
الگوریتم سنجاب پرنده در سال 2019 توسط Mohit Jain و همکارانش تحت عنوان مقاله ای با نام A novel nature-inspired algorithm for optimization: Squirrel search algorithm در ژورنال معروف Swarm and Evolutionary Computation از انشارات Elsevier منتشر شده است. این مقاله را می توانید از اینجا (+) دانلود کنید. در ادامه به تشریح این الگوریتم می پردازیم.
زندگی و رفتار سنجاب های پرنده
سنجابهای پرنده Flying squirrels گروهی از جوندگان درختی و شبزی هستند که با سر خوردن (gliding locomotion) یا پرش حرکت می کنند. بر اساس مطالعات جانورشناسی در حال حاضر 15 نوع و 44 گونه سنجاب پرنده شناسایی شده است که اکثریت آنها در جنگل های اروپا و آسیا به ویژه جنوب شرق آسیا یافت می شوند. سنجابهای پرنده از نظر آیرودینامیکی، پیچیدهترین سنجابها هستند که دارای غشایی چتر مانند (patagia) هستند، که به سنجاب در سر خوردن از درختی به درخت دیگر کمک میکند و آنها را قادر میسازد که عملیات لیفت و پرش را انجام دهند.
جالبترین واقعیت در مورد سنجابهای پرنده این است که آنها پرواز نمیکنند، در عوض از یک روش حرکتی ویژه یعنی سر خوردن استفاده میکنند، سر خوردن یا همان سریدن از نظر انرژی ارزان و مقرون به صرفه است و به پستانداران کوچک اجازه میدهد تا فواصل بزرگ را به سرعت و کارآمد طی کنند. شکل a تصویر واقعی سنجاب در حال پرواز را هنگام سر خوردن و شکل b توالی حرکت آهسته سنجاب پرنده را قبل از فرود بر روی درخت نشان می دهد.
سنجابها میتوانند با نشان دادن رفتار جستجوی پویای خود از منابع غذایی استفاده بهینه کنند. به عنوان مثال، برای برآوردن نیازهای تغذیه ای در پاییز، ترجیح می دهند که بلوط معمولی (mast nut) بخورند زیرا به وفور در دسترس است و در عین حال سایر مواد غذایی را در لانه ها، حفره های دیگر و گاهی در زمین ذخیره می کنند.
در طول زمستان که نیازهای غذایی به دلیل دمای پایین بیشتر است، میوه های دانه درشت (hickory nuts) به سرعت در محل کشف در هنگام جستجوی خورده می شود و همچنین از مکان های مواد غذایی ذخیره خارج می شود. بنابراین، خوردن انتخابی برخی مواد غذایی و ذخیره برخی دیگر بسته به نیازهای غذایی، امکان استفاده بهینه از هر دو نوع مواد غذایی موجود را فراهم می کند.
این رفتار جستجوی پویا هوشمند سنجاب پرنده، منبع اصلی انگیزه برای الگوریتم SSA است. در این الگو، استراتژی جستجوی پویا و مکانیسم سر خوردن سنجابهای پرنده به صورت ریاضی برای طراحی SSA برای بهینهسازی مدلسازی می شود.
الگوریتم سنجاب پرنده SSA
فرآیند جستجو زمانی آغاز می شود که سنجاب های پرنده شروع به جستجوی غذا می کنند. در طول هوای گرم (پاییز)، سنجابها با سر خوردن از درختی به درخت دیگر به دنبال منابع غذایی میگردند. در حین انجام این کار، آنها مکان خود را تغییر می دهند و مناطق مختلف جنگل را کشف می کنند. از آنجایی که شرایط آب و هوایی به اندازه کافی گرم است، آنها می توانند نیازها و انرژی روزانه خود را با رژیم غذایی بلوط های موجود به وفور برآورده کنند و از این رو بلافاصله پس از یافتن بلوط، آنها را مصرف می کنند.
سنجاب ها پس از برآورده کردن انرژی مورد نیاز روزانه خود، شروع به جستجوی منبع غذایی بهینه برای زمستان می کنند (مواد مغذی دانه درشت). ذخیره سازی دانه درشت ها به آنها کمک می کند تا انرژی مورد نیاز خود را در آب و هوای بسیار سخت حفظ کنند و سفرهای پرهزینه جستجوی غذایی را کاهش دهند و در نتیجه احتمال بقا را افزایش دهند.
در طول زمستان، با از بین رفتن پوشش برگ رختان در جنگل های برگریز منجر به افزایش خطر شکار می شود و از این رو سنجاب های پرنده فعالیت خود را کاهش می دهند اما در زمستان به خواب زمستانی نمی روند. در پایان فصل زمستان، سنجاب های پرنده دوباره فعال می شوند. این یک روند تکراری است و تا طول عمر یک سنجاب پرنده ادامه می یابد و پایه و اساس SSA را تشکیل می دهد. برای ساده سازی مدل ریاضی مفروضات زیر در نظر گرفته شده است:
- تعداد n سنجاب پرنده در یک جنگل وجود دارد و فرض بر این است یک سنجاب پرنده در یک درخت وجود دارد.
- هر سنجاب پرنده به طور جداگانه به جستجوی غذا می پردازد و با نشان دادن یک رفتار پویا در جستجوی غذا از منابع غذایی موجود، استفاده بهینه می کند.
- در جنگل فقط سه نوع درخت وجود دارد. درخت معمولی، درخت بلوط (منبع غذایی بلوط معمولی) و درخت هیکوری (منبع غذایی بلوط درشت).
- منطقه جنگلی مورد نظر شامل سه درخت بلوط معمولی و یک درخت بلوط درشت فرض می شود.
مدل سازی ریاضی الگوریتم سنجاب پرنده
الگوریتم SSA با مکان یابی اولیه تصادفی سنجاب های پرنده، شبیه به سایر الگوریتم های مبتنی بر جمعیت شروع می شود. مکان (Position) یک سنجاب پرنده با یک بردار در فضای جستجوی d بعدی نشان داده می شود.
مقدار دهی اولیه تصادفی
تعداد n سنجاب پرنده (flying squirrels) یا FS در یک جنگل وجود دارد و مکان این سنجاب پرنده را میتوان با یک بردار مشخص کرد. مکان همه سنجاب های پرنده را می توان با ماتریس زیر نشان داد:
که در آن FSi,j نشان دهنده بعد j ام سنجاب پرنده i است. توزیع یکنواخت (uniform distribution) برای تخصیص مکان اولیه هر سنجاب پرنده طبق فرمول 2 استفاده می شود.
که در آن FSL و FSU به ترتیب کران های پایین و بالایی سنجاب پرنده در بعد jام هستند و (0,1) U یک عدد تصادفی توزیع شده یکنواخت در محدوده [0,1] است.
تابع تناسب
تابع تناسب مکان برای هر سنجاب پرنده با قرار دادن مقادیر متغیر تصمیم (بردار راه حل) در یک تابع تناسب تعریف شده توسط کاربر محاسبه می شود و مقادیر مربوطه در ماتریس F زیر ذخیره می شود:
مرتب سازی، اعلان و انتخاب تصادفی
پس از ذخیره مقادیر تابع تناسب برای مکان هر سنجاب پرنده، ماتریس به صورت صعودی مرتب می شود. سنجاب پرنده با حداقل ارزش تناسب روی درخت هیکوری (دارای میوه های دانه درشت) اعلان می شود. سه تا از بهترین سنجاب پرنده بعدی روی درختان بلوط در نظر گرفته می شوند و فرض بر این است که سنجاب ها به سمت درخت هیکوری حرکت می کنند. قرار است سنجاب های پرنده باقی مانده روی درختان معمولی باشند.
از طریق انتخاب تصادفی، برخی از سنجابها با این فرض که انرژی مورد نیاز روزانه خود را برآورده کردهاند، در نظر گرفته می شود و به سمت درخت هیگوری حرکت میکنند. سنجابهای باقیمانده به سمت درختان بلوط (برای برآوردن نیاز انرژی روزانه خود) پیش میروند. این رفتار جستجوی سنجاب پرنده همیشه تحت تأثیر حضور شکارچیان است. این رفتار طبیعی با استفاده از مکانیسم بهروزرسانی مکان با احتمال حضور شکارچی (Pdp) مدلسازی میشود.
ایجاد موقعیت (مکان) جدید
همانطور که قبلاً بحث شد، سه موقعیت ممکن است در طول جستجوی پویا سنجابهای پرنده رخ دهد. در هر موقعیتی فرض بر این است که در غیاب شکارچی، سنجاب پرنده سر می خورد و به طور موثر در سراسر جنگل برای یافتن غذای مورد علاقه خود جستجو می کند، در حالی که وجود شکارچی باعث می شود سنجاب پرنده محتاط باشد و مجبور است از پیاده روی تصادفی random walk کوچک برای جستجوی مکان مخفیگاه نزدیک استفاده کند. رفتار جستجوی پویا را می توان به صورت ریاضی به صورت زیر مدل کرد:
مورد 1: سنجاب های پرنده که روی درختان بلوط (FSat) هستند ممکن است به سمت درخت هیکوری حرکت کنند. در این صورت مکان جدید سنجاب ها را می توان به صورت زیر بدست آورد:
که در آن dg فاصله سر خوردن تصادفی، R1 یک عدد تصادفی در محدوده [0، 1]، FStat مکان سنجاب پرنده ای است که به درخت هیکوری رسیده است و t نشان دهنده تکرار فعلی است. تعادل بین اکتشاف exploration و بهره برداری exploitation با کمک Gc ثابت سر خوردن در مدل ریاضی به دست می آید و مقدار آن به طور قابل توجهی بر عملکرد الگوریتم تأثیر می گذارد.
مورد 2: سنجاب های پرنده روی درختان معمولی (FSnt) ممکن است به سمت درختان بلوط حرکت کنند تا نیازهای انرژی روزانه خود را برآورده کنند. در این حالت مکان جدید سنجاب ها را می توان به صورت زیر بدست آورد:
که در آن R2 یک عدد تصادفی در محدوده [0، 1] است.
مورد 3: برخی از سنجاب هایی که روی درختان معمولی هستند و قبلاً بلوط مصرف کرده اند ممکن است به سمت درخت هایی حرکت کنند تا مواد غذایی درخت های درشت دانه را ذخیره کنند که می تواند در زمان کمبود غذا مصرف شود. در این حالت مکان جدید سنجاب ها را می توان به صورت زیر بدست آورد:
که در آن R3 یک عدد تصادفی در محدوده [0، 1] است. احتمال حضور شکارچی Pdp در همه موارد برای کار حاضر 0,1 در نظر گرفته شده است. شکل زیر مدل مفهومی حرکت سرخوردن را نشان می دهد که توسط سنجاب های پرنده برای حرکت موثر آن ها در هنگام جستجوی غذا در شب استفاده می شود.
آیرودینامیک سرخوردن
مکانیسم سر خوردن سنجاب های پرنده با سر خوردن تعادلی توصیف می شود که در آن مجموع نیروی بالابر (L) و درگ (D) نیروی حاصل (R) ایجاد می کند که قدرمطلق آن برابر و مخالف جهت وزن سنجاب پرنده (Mg) است. بنابراین، R یک مسیر پروازی برای سنجاب پرنده با سرعت ثابت (V) فراهم می کند. در این کار یک مدل تقریبی از رفتار سر خوردن در طراحی الگوریتم بهینهسازی استفاده شده است. یک سنجاب پرنده که با سرعت ثابت سر میخورد همیشه با زاویه ϕ نسبت به افقی و نسبت بالابر به کشش یا نسبت سر خوردن پایین میآید که به صورت زیر تعریف میشود:
سنجاب های پرنده می توانند طول مسیر سر خوردن خود را با ایجاد زاویه سر خوردن کوچکتر (φ) افزایش دهند و بنابراین نسبت بالابر به درگ افزایش می یابد. در اینجا، بالابر ناشی از انحراف رو به پایین هوای عبوری از روی بال ها است و به صورت زیر تعریف می شود:
که در آن ρ (=1.204 kgm -3) چگالی هوا است، CL به عنوان ضریب بالابر نامیده می شود، V (=5.25 ms -1) سرعت و S (=154 cm -2) مساحت سطح بدن است. کشش اصطکاکی به صورت زیر تعریف می شود:
که در آن CD ضریب درگ اصطکاکی است. در سرعت کم، این مولفه درگ بسیار زیاد است در حالی که در سرعت بالا کوچکتر می شود. از این رو از معادله (7) زاویه سر خوردن در حالت ثابت به صورت زیر تعیین می شود:
فاصله تقریبی سر خوردن (dg) به صورت زیر محاسبه می شود (شکل 3b):
سنجابهای پرنده معمولاً یک مسافت افقی از 5 تا 25 متر را در یک سر خوردن طی میکنند. فاصله سر خوردن در مدل پیشنهادی در محدوده 9 تا 20 متر در نظر گرفته شده است.
وضعیت پایش فصلی
تغییرات فصلی به طور قابل توجهی بر فعالیت جستجوی غذای سنجاب های پرنده تأثیر می گذارد. آنها در دماهای پایین، از دست دادن گرمای قابل توجهی را متحمل می شوند، زیرا دارای دمای بدن بالا و اندازه کوچک هستند که به دلیل وجود شکارچیان فعال، هزینه جستجوی غذا را بالا و همچنین خطرناک می کند.
شرایط آب و هوایی آنها را مجبور می کند در زمستان ها نسبت به پاییز کمتر فعال باشند. بنابراین حرکت سنجابهای پرنده تحتتاثیر تغییرات آبوهوا قرار میگیرد و گنجاندن چنین رفتاری ممکن است رویکرد واقعیتری را برای بهینهسازی ارائه دهد. بنابراین یک شرایط پایش فصلی در SSA معرفی میشود که از به دام افتادن الگوریتم پیشنهادی در راهحلهای بهینه محلی جلوگیری میکند. مراحل زیر در مدل سازی رفتار دخیل است:
- الف: ابتدا ثابت فصلی (Sc) را با استفاده از معادله محاسبه می شود:
که در آن t = 1، 2، 3.
- ب: شرایط پایش فصلی را بررسی کنید، یعنی Stc <Smin که در آن Smin حداقل مقدار ثابت فصلی محاسبه شده به صورت زیر است:
که در آن t و tm به ترتیب مقادیر فعلی و حداکثر تکرار هستند. مقدار Smin بر قابلیتهای اکتشاف و بهرهبرداری روش پیشنهادی تأثیر میگذارد. ارزش بزرگتر Smin کاوش را ترویج می کند در حالی که مقادیر کوچکتر Smin قابلیت بهره برداری الگوریتم را افزایش می دهد. برای هر الگوریتم فراابتکاری موثر، باید تعادل مناسبی بین این دو مرحله وجود داشته باشد.
- ج: اگر شرایط پایش فصلی درست تشخیص داده شود (یعنی فصل زمستان به پایان رسیده است)، به طور تصادفی سنجاب های پرنده ای را که نمی توانند جنگل را برای منبع غذایی بهینه در زمستان کاوش کنند، جابه جا کنید.
جابجایی تصادفی در پایان فصل زمستان
همانطور که قبلاً گفته شد، پایان فصل زمستان سنجابهای پرنده را به دلیل هزینه کم غذا، فعال میکند. سنجابهای پرندهای که نمیتوانستند جنگل را برای منبع غذایی بهینه در زمستان کاوش کنند و هنوز زنده ماندهاند، ممکن است در مسیرهای جدیدی جستجو کنند.
ادغام این رفتار در مدل سازی ممکن است قابلیت اکتشاف الگوریتم سنجاب پرنده را افزایش دهد. فرض بر این است که فقط آن دسته از سنجاب هایی که نتوانسته اند منبع غذایی درشت مغذی را جستجو کنند و هنوز زنده مانده اند به جهات مختلف حرکت می کنند تا منبع غذایی بهتری پیدا کنند. جابجایی چنین سنجابهای پرنده از طریق معادله زیر مدلسازی میشود:
جایی که توزیع Levy کاوش فضای جستجوی بهتر و کارآمد را تشویق می کند. پرواز Levy یک ابزار ریاضی قدرتمند است که توسط محققان برای بهبود قابلیت اکتشاف سراسری الگوریتمهای فراابتکاری مختلف استفاده میشود. پروازهای Levy به یافتن راهحلهای نامزد جدید بسیار دور از بهترین راهحل فعلی کمک میکنند. این یک نوع پیاده روی تصادفی است که در آن طول گام از توزیع Levy ترسیم می شود.
این توزیع اغلب با فرمول قانون توان بیان می شود. توزیع Levy به صورت ریاضی به صورت زیر بیان می شود:
در جایی که ra و rb دو عدد تصادفی معمولی توزیع شده در [0، 1] هستند، β ثابتی است که در کار حاضر 1.5 در نظر گرفته می شود و σ به صورت زیر محاسبه می شود:
معیار توقف
تحمل تابع یک معیار همگرایی رایج است که در آن یک مقدار آستانه مجاز اما کوچک بین دو نتیجه متوالی آخر تعریف می شود. گاهی اوقات حداکثر زمان اجرا نیز به عنوان معیار توقف استفاده می شود. در پژوهش حاضر حداکثر تعداد تکرار به عنوان معیار توقف در نظر گرفته شده است. شبه کد SSA در الگوریتم 1 ارائه شده است.
شبه کد الگوریتم سنجاب پرنده
نتیجه گیری
در این پست، الگوریتم جستجوی سنجاب الهام گرفته از طبیعت برای مسائل بهینه سازی نامحدود به طور کامل تشریح گردید. در الگوریتم جستجوی سنجاب های پرنده رفتار جستوجوی سنجابهای پرنده جنوبی مورد مطالعه و مدلسازی ریاضی قرار گرفته است که شامل تک تک ویژگیهای جستجوی غذای آنها برای بهینهسازی مورد نظر میشود. در مقاله اصلی الگوریتم سنجاب با استفاده از چندین توابع معیار بدون محدودیت کلاسیک و مدرن آزمایش شده است. از تجزیه و تحلیل آماری مقایسه ای مشاهده می شود که SSA به راه حل های بهینه سراسری با رفتار همگرایی قابل توجه در مقایسه با سایر بهینه سازهای گزارش شده دست می یابد.
درباره امین جلیل زاده رزین
پایه گذار و موسس وب سایت آموزشی پی استور، مدرس دانشگاه فنی و حرفه ای، برنامه نویس و تحلیل گر سیستم، پژوهشگر در حوزه الگوریتم های ابتکاری، فرا ابتکاری، یادگیری ماشین، شبکه و پایگاه داده. ایشان در زبان های برنامه نویسی متعدد، نظیر ++C، سی شارپ، PHP ،Java، متلب MATLAB و Python تسلط و سابقه تدریس فعال دارند.