در این مقاله آموزشی، به معرفی جامع الگوریتم بهینه سازی شیر یا Lion Optimization Algorithm با نام اختصاری LOA خواهیم پرداخت. الگوریتم متاهیوریستیک بهینه سازی شیر یا Metaheuristic algorithm for Lion optimization از جمله محبوبترین، الگوریتم های فراابتکاری واقع شده است. چرا که سبک زندگی ویژه شیرها و نحوه عملکرد آنها در قلمرو، محور توسعه این الگوریتم NI بوده است. اگر آماده یادگیری حل مسئله به روش الگوریتم LOA هستید؛ تا انتهای این مقاله، با ما همراه باشید.
مقدمه ای بر الگوریتم های بهینه سازی
همان طور که میدانید؛ یافتن پاسخ برای بسیاری از مسائل بهینه سازی مهندسی Np-hard، معمولاً بسیار دشوار بوده؛ بسیاری از برنامهها، باید با این مسائل پیچیده مقابله کنند و زمانی که فضای جستجو به صورت تصاعدی با اندازه مسئله، افزایش مییابد. در نتیجه، روشهای سنتی بهینه سازی، راه حل مناسبی برای حل این چنین مسائل، ارائه نمیدهند. بنابراین، امروزه الگوریتم های فراابتکاری متنوعی برابر با نیاز محقق، برای حل چنین مسائلی طراحی شدهاند.
برای مثال، الگوریتم ژنتیک یا Genetic algorithm ارائه شده تا به روش شبیه سازی مفاهیم تکامل داروین (Darwnian evolution) به حل مسائل بهینه سازی بپردازد یا سیستمهای ایمنی مصنوعی (Artificial Immune Systems)، سیستمهای ایمنی بیولوژیکی (Biological immune systems) را برای بهینه سازی شبیه سازی میکنند.
در مثالهای مشابه، الگوریتم بهینهسازی کلونی مورچهها (Ant Colony Optimization) از رفتار مورچهها در جستجوی غذا برای حل مسئله استفاده مینماید. بهینه سازی ازدحام ذرات (Particle Swarm Optimization) رفتار اجتماعی دستهای از پرندگان مهاجری را تقلید میکند که تلاش میکنند به مقصدی ناشناخته برسند یا حتی الگوریتم ازدواج در زنبور عسل بهینه سازی (MBO) پیشنهاد شده تا با استفاده از تقلید فرآیندهای تولید مثل در کلونی زنبور عسل به حل مسائل پیچیده بپردازد.
درباره الگوریتم بهینه سازی شیر
ما هم در این آموزش، به معرفی یک الگوریتم فراابتکاری جدید خواهیم پرداخت. الگوریتم معرفی شده، برگرفته از مقاله Lion Optimization Algorithm (LOA): A nature-inspired metaheuristic algorithm نوشته آقایان Maziar Yazdani و Fariborz Jolai میباشد که در ژورنال معتبر Journal of Computational Design and Engineering، در سال ۲۰۱۶، برای اولین بار به چاپ رسیده و در واقع برای توسعه و تکمیل دو نظریه معروف محققان علوم کامپیوتر آقایان Wang و Rajakumar ارائه شده است.
وانگ و راجاکومار، در سال ۲۰۱۲ میلادی، هر کدام یک الگوریتم با الهام از چند شخصیت شیر پیشنهاد دادند. برای درک کامل نبودن این دو الگوریتم، مثال زیر را بررسی کنید. راجاکومار، پایههای اصلی الگوریتم شیر را چنین بیان نموده است:
- جفت گیری شیرها: به استخراج راه حلهای جدید اشاره دارد.
- دفاع سرزمینی و تصرف سرزمینی: در این مرحله، بدترین راه حل با بهترین راه حل جدید جایگزین میشود.
الگوریتم شیر (Lion’s Algorithm) و بهینه ساز pride شیر (Lion pride optimizer)، مثالهایی برای آنچه گفته شد؛ هستند و بر اساس مبارزه بین افراد و جفت گیری آنها طراحی شدهاند. غافل از این که شیرها علاوه بر جفت گیری و جنگیدن، رفتارهای دیگری مانند شیوه خاص شکار، علامت گذاری سرزمینی، مهاجرت، انواع مختلف سبک زندگی کوچ نشینی و ساکن را از خود بروز میدهند.
در نتیجه، میتوان گفت که هر دوی این نظریهها، ناقص بودند و همواره نیاز به یک الگوریتم تکمیلی یا متفاوت، احساس میشد. تا این که، الگوریتم بهینه سازی شیر که از شبیه سازی رفتارهای انفرادی و مشارکتی شیرها الهام گرفته شده است؛ با الگوریتمی کاملاً متفاوت، ارائه گردید.
رفتار اجتماعی شیرها در داخل کلونی
شیرها گربه سانانی وحشی با دو نوع سازمان اجتماعی هستند که در داخل کلونی آنها، سطوح بالایی از همکاری و تضاد، مشاهده میگردد. جالب است بدانید که سازمان اجتماعی شیرها هم مانند انسانها، به دو دسته ساکن یا Resident و عشایر یا Nomad، تقسیم بندی میشود.
شیرها در سازمان اجتماعی ساکن، به صورت گروهی زندگی میکنند که Pride نام دارد. Pride شیرها معمولاً شامل پنج ماده، تولههای آنها و یک یا چند نر بالغ بوده و پسران جوان، وقتی بالغ میشوند؛ از قلمرو تولد خود حذف میشوند.
دومین اجتماع سازمانی، عشایر نام دارد که در آن شیرها به صورت پراکنده، دوتایی یا منفرد حرکت کرده و جفتها در میان مردان خویشاوندی که از Pride مادری خود طرد شدهاند؛ بیشتر دیده میشود. البته همیشه این امکان وجود دارد که یک شیر، سبک زندگی خود را تغییر دهد. به بیان سادهتر، شیرهای ساکن ممکن است عشایر شوند یا برعکس.
شکار شیرها در داخل سازمان اجتماعی
برخلاف تمام گربههای دیگر، شیرها معمولاً همراه با سایر اعضای Pride خود شکار میکنند. چند شیر ماده یا Female lion، با هم همکاری کرده؛ از نقاط مختلف طعمه را محاصره نموده و با یک حمله سریع، قربانی را میگیرند. شکار گروهی هماهنگ، احتمال موفقیت بیشتری را در شکار شیر به ارمغان میآورد. شیرهای نر یا Male lion و برخی از شیرهای ماده، معمولاً در انتظار بازگشت شیرهای شکارچی مانده و استراحت میکنند.
تولید مثل شیرها در کلونی
شیرها در هر زمانی از سال، جفت گیری می٬کنند. بعضی مادهها پلی استروس (Polyestrous) بوده و اگر شیرهای مادهای، از بزرگ کردن تولههایشان امتناء کردند؛ نقش دایه را برای توله شیرها ایفا مینمایند. یک شیر زمانی که در گرما است؛ امکان دارد با چند شریک، جفت گیری نماید. در طبیعت، شیرهای نر و ماده، قلمرو خود و جاهای دیگر را با روش نشانه گذاری، مشخص مینمایند. در این فرآیند، برخی از شخصیتهای شیرها به منظور طراحی یک الگوریتم بهینه سازی، به صورت ریاضی مدل سازی شدهاند.
الگوریتم بهینهسازی شیر یا LOA
در الگوریتم شیر، یک جمعیت اولیه توسط مجموعهای از راه حلهای تولید شده تصادفی، به نام شیرها تشکیل میشود. برخی از شیرهای جمعیت اولیه (%N) به عنوان شیرهای عشایری انتخاب شده و جمعیت بقیه شیرهای ساکن به طور تصادفی به زیر مجموعههای P یا Pride تقسیم بندی میشوند. دوستان عزیز، S درصد از اعضای مجموعه P را ماده و بقیه را نر، فرض میکنیم.
برای هر شیر، بهترین راه حل به دست آمده در تکرارهای بعدی، بهترین موقعیت بازدید نامیده شده و در طی فرآیند بهینه سازی، به صورت تدریجی بروزرسانی میگردند. در الگوریتم LOA منطقه افتخار، منطقهای است که از اعضای بهترین موقعیت بازدید شده، تشکیل شده است. در هر Pride تعدادی ماده که به صورت تصادفی انتخاب میشوند؛ به شکار خواهند رفت و شکارچیان برای محاصره و گرفتن طعمه، به سمت آن حرکت خواهند نمود. این درحالی است که بقیه مادهها با خیال راحت، به سمت موقعیتهای مختلف قلمرو حرکت مینمایند.
شیرهای نر Pride، در قلمرو پرسه میزنند. مادههای Pride با یک یا چند نر ساکن جفت شده؛ نرهای جوان از قلمرو مادری خود کنار گرفته؛ با رسیدن به بلوغ، کوچ نشین میشوند و قدرتشان کمتر از نرهای ساکن است. همچنین یک شیر عشایر، به صورت تصادفی در فضای جستجو برای یافتن مکان بهتر یا بهترین راه حل موجود، حرکت کرده و در طی این فرآیند، شیر نر عشایر، تبدیل به شیر ساکن میشود.
در سیر تکاملی الگوریتم بهینه سازی شیر، برخی از مادههای ساکن از یک Pride به Pride دیگر مهاجرت میکنند. شاید هم سبک زندگی خود را تغییر داده؛ عشایر شوند یا برعکس و بنابراین، در طی این فرآیند، به دلیل عوامل زیادی مانند کمبود غذا و رقابت، ضعیفترین شیر مرده یا کشته میشود. فرآیند فوق تا زمانی که شرط توقف برآورده شود؛ ادامه خواهد یافت. در ادامه، مقاله به تشریح گامهای الگوریتم LOA خواهیم پرداخت.
۱- مقداردهی اولیه
عزیزان مجموعه پی استور، اولین گام، تولید تصادفی جمعیت در فضای راه حل میباشد. در این الگوریتم، به تک تک پاسخهای فرضی، شیر گفته میشود. در یک مسئله بهینه سازی ابعادی Nvar، یک شیر را با استفاده از رابطه زیر تعریف خواهیم کرد.
در فرمول بالا، ارزش تناسب شیرها با ارزیابی تابع هزینه محاسبه شده و از رابطه زیر، به دست میآید.
به این ترتیب، ابتدا راه حلهای Npop به طور تصادفی، در فضای جستجو تولید شده و به تعداد N% از پاسخهای تولید شده، به صورت تصادفی به عنوان شیرهای عشایری انتخاب میگردند. حال ممکن است از خودتان بپرسید که تکلیف بقیه جمعیت چیست؟ در پاسخ، باید بگویم که بقیه شیرها به صورت تصادفی در دو گروه مجزا، قرار گرفته و در طی فرآیند بهینهسازی ثابت میمانند. در نظر داشته باشید که در هر Pride، بهترین موقعیتهای بازدید شده توسط اعضای آن، به عنوان موقعیت بهینه انتخاب میشود.
۲- تشریح فرآیند شکار
در هر Pride، چند ماده در گروهی به دنبال طعمه میگردند تا برای قلمرو خود، غذا تهیه کنند. این شکارچیان، طی یک استراتژیهای خاص، طعمه را محاصره کرده و آن را در تله میاندازند. به طور کلی، شیرها در هنگام شکار تقریباً از همان الگویی که در شکل زیر، نشان داده شده است؛ پیروی میکنند. در الگوی زیر، شیرها در ۷ موقعیت بال چپ، مرکز و راست قرار گرفته و در طول شکار، هر شیر بر اساس موقعیت اعضای گروه، موقعیت خود را اصلاح میکند.
بر اساس این اصل که در حین شکار، برخی از این شکارچیان طعمه را محاصره کرده و از موقعیت مخالف طعمه حمله مینمایند؛ الگوریتم بهینه سازی شیر از یادگیری مبتنی بر مخالفت یا OBL استفاده میکند که روشی موثر برای حل مسائل بهینهسازی بوده؛ به صورت زیر، تعریف شده و دو فرمول اساسی مسئله را تولید میکند.
عزیزان، همواره این نکته را به یاد داشته باشید؛ در زمانهایی که PREY موقعیت فعلی شکار است؛ شکارچی در موقعیت جدید به منظور حمله به طعمه موردنظر قرار میگیرد و PI درصد بهبود تناسب اندام شکارچی خواهد بود. با دقت در تصویر زیر، به اهمیت این نکته پی خواهید برد.
فرمولهای زیر، برای تقلید از فرآیند درگیر شدن طعمههای در حال احاطه توسط گروههای شکارچی و موقعیتهای جدید مربوط به آن، پیشنهاد میگردد.
برای درک بهتر، مثالی از فرآیند احاطه کردن طعمه در الگوریتم فراابتکاری LOA توسط شیر مرکزی و شیر بال، آورده شده است. این استراتژی یک محله دایرهای شکل در اطراف طعمه ایجاد کرده و به شکارچیان اجازه میدهد تا از جهات مختلف به طعمه نزدیک شوند.
این استراتژی فرصتی برای راه حلها، برای فرار از بهینه محلی را فراهم میکند. زیرا برخی از شکارچیان از موقعیت مخالف استفاده میکنند. بنابراین شکار در هر Pride را میتوان به صورت شبه کد زیر، بیان کرد.
۳- استراتژی حرکت به سمت مکان امن یا Safe place
همراهان گرامی، همانطور که قبلاً هم بیان گردید؛ در هر Pride تعدادی ماده به شکار رفته و مادههای باقی مانده به سمت یکی از مناطق قلمرو حرکت مینمایند. از آنجایی که قلمرو هر Pride از بهترین موقعیتهای شخصی هر عضو تشکیل شده و به الگوریتم بهینهسازی شیر، کمک میکند تا بهترین راه حلهای به دستآمده را در طول تکرار ذخیره کند؛ میتوان از آن به عنوان اطلاعات ارزشمند و قابل اعتماد برای بهبود مکان استفاده کرد. فرمولهای مربوط به استراتژی حرکت به سمت مکان امن توسط شیرهای ماده در ادامه، آورده شده است.
شبه کد استراتژی فوق، نیز به این ترتیب خواهدبود:
همراهان گرامی، نمای شماتیک اندازههای مختلف در هر Pride از الگوریتم بهینه سازی شیر، در ادامه، آورده شده است.
۴- پرسه زنی هدف دار شیر یا Roaming
رومینگ یک جستجوی محلی قوی است و به شیر کمک میکند تا نسبت به موقعیت فعلی خود، در جایگاه بهتری قرار بگیرد. برای تقلید از رفتار نرهای ساکن، R% از قلمرو Pride به صورت تصادفی انتخاب شده و توسط شیر فرضی، بازدید شده و در طول رومینگ، بهترین راه حل بازدید شده توسط شیر نر فرضی، بروز رسانی میگردد. این سیر صعودی موقعیت شیر، در شکل زیر نشان داده شده است.
در شکل بالا، کاملاً واضح است که شیر به سمت ناحیه انتخاب شده قلمرو با x واحد حرکت میکند که در آن x یک عدد تصادفی با توزیع یکنواخت است و d فاصله بین موقعیت شیر نر و ناحیه انتخاب شده قلمرو را نشان میدهد. به رابطه زیر، توجه کنید.
در شکل بالا، بردار با مبدأ موقعیت شیر نر و مقصد ناحیه انتخاب شده از قلمرو، جهت اصلی حرکت را نشان میدهد. برای ایجاد فرصتی با هدف جستجوی ناحیه وسیعتر در اطراف موقعیت فعلی و افزودن خاصیت تشدید به روش و جستجوی ناحیه وسیعتر، زاویه به این جهت اضافه میشود.
به نظر میرسد؛ زاویهای که با توزیع یکنواخت بین بازه π/۶ (rad)– و π/۶ (rad) انتخاب میگردد؛ برای این هدف کافی باشد. در شبه کد زیر، رفتار شیر نر در اجتماعات سازمانی ساکن، نشان داده شده است.
در تکمیل آموزش الگوریتم بهینه سازی شیر، شبه کد، روابط و تصویر مربوط به رفتار شیر نر در اجتماعات عشایری نیز آورده شده است.
۵- تکثیر نژاد یا Mating
Mating operation یک فرآیند ضروری است که بقای شیرها را تضمین کرده و فرصتی برای تبادل اطلاعات ژنتیکی بین اعضا را هم فراهم میکند. در هر قلمرو، Ma% از شیرهای ماده با یک یا چند نر ساکن، عملیات تکثیر نژاد را انجام میدهند.
در نظر بگیرید که نحوه انتخاب شیرهای نر به صورت تصادفی میباشد اما برای شیرهای از جامعه عشایر، یک تفاوت عمده وجود دارد و آن هم این است که یک ماده کوچ نشین فقط با یکی از نرهایی که بهطور تصادفی انتخاب میشوند؛ جفت گیری خواهد نمود. عملگر جفت گیری یک والدین ترکیبی خطی برای تولید دو فرزند جدید است. طبق معادلات و تصویر زیر، تولههای جدید پس از انتخاب شیر ماده و نر برای جفت گیری تولید میشوند.
۶- دفاع یا Defense
شیرهای نر وقتی بالغ میشوند؛ پرخاشگر شده و با نرهای دیگر میجنگند. نرهای کتک خورده قلمرو خود را رها کرده و عشایر میشوند. از سوی دیگر، اگر شیر نر عشایری آنقدر قوی باشد که بخواهد با نبرد با نرها، قلمرو را تصاحب کند؛ شیر نر مقیم کتک خورده از قلمرو بیرون رانده شده و تبدیل به عشیره میشود.
بنابراین، اپراتور دفاعی در LOA به دو مرحله اصلی دفاع در برابر نرهای ساکن جدید بالغ و دفاع در برابر نرهای عشایر تقسیم میشود که در ادامه، شبه کد مربوط به هر کدام آورده شده است.
۷- مهاجرت یا Migration و تعادل جمعیت شیرها یا Lions’ Population Equilibrium
با الهام از زندگی شیر، سوئیچ و رفتار مهاجرتی در طبیعت، زمانی که شیری از یک قلمرو به قلمرو دیگر سفر میکند یا سبک زندگی خود را تغییر میدهد و ماده ساکن عشایر میشود و بالعکس، تنوع قلمرو هدف را با موقعیتش در قلمرو قبلی افزایش میدهد. از طرف دیگر، مهاجرت شیرها و تغییر سبک زندگی، پلی برای تبادل اطلاعات ایجاد میکند.
از آنجایی که همیشه در جمعیت شیرها تعادل وجود دارد؛ در پایان هر تکرار، تعداد شیرهای زنده کنترل میشود. جهت رعایت حداکثر تعداد مجاز هر جنسیت در عشایر، شیرهای عشایری با کمترین ارزش تناسب اندام حذف خواهند شد. شکل زیر، نمونهای از اپراتور مهاجرت و تعادل جمعیت شیرها را نشان میدهد.
کلام آخر در رابطه با الگوریتم بهینه سازی شیر
الگوریتم LOA بر اساس شبیه سازی رفتارهای انفرادی و مشارکتی شیرها مانند شکار، جفت گیری، دفاع و سایر رفتارها ساخته شده است. نتایج به دست آمده از ارزیابی عملکرد LOA نشان میدهد که در بیشتر موارد، نتایج برتری را در مقایسه با سایر الگوریتم های فراابتکاری، به دست میدهد و در همه موارد، با الگوریتم های متاهیوریستیک قابل مقایسه است. در انتها، خواهشمندیم نظرات و پیشنهادات خود را با ما در میان بگذارید. موفق باشید.