الگوریتم بهینه سازی شیر — Lion Optimization Algorithm
در این مقاله آموزشی، به معرفی جامع الگوریتم بهینه سازی شیر یا 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، در سال 2016، برای اولین بار به چاپ رسیده و در واقع برای توسعه و تکمیل دو نظریه معروف محققان علوم کامپیوتر آقایان Wang و Rajakumar ارائه شده است.
وانگ و راجاکومار، در سال 2012 میلادی، هر کدام یک الگوریتم با الهام از چند شخصیت شیر پیشنهاد دادند. برای درک کامل نبودن این دو الگوریتم، مثال زیر را بررسی کنید. راجاکومار، پایه های اصلی الگوریتم شیر را چنین بیان نموده است:
- جفت گیری شیرها: به استخراج راه حل های جدید اشاره دارد.
- دفاع سرزمینی و تصرف سرزمینی: در این مرحله، بدترین راه حل با بهترین راه حل جدید جایگزین می شود.
الگوریتم شیر (Lion’s Algorithm) و بهینه ساز pride شیر (Lion pride optimizer)، مثال هایی برای آنچه گفته شد؛ هستند و بر اساس مبارزه بین افراد و جفت گیری آن ها طراحی شده اند. غافل از این که شیرها علاوه بر جفت گیری و جنگیدن، رفتارهای دیگری مانند شیوه خاص شکار، علامت گذاری سرزمینی، مهاجرت، انواع مختلف سبک زندگی کوچ نشینی و ساکن را از خود بروز می دهند.
در نتیجه، می توان گفت که هر دوی این نظریه ها، ناقص بودند و همواره نیاز به یک الگوریتم تکمیلی یا متفاوت، احساس می شد. تا این که، الگوریتم بهینه سازی شیر که از شبیه سازی رفتارهای انفرادی و مشارکتی شیرها الهام گرفته شده است؛ با الگوریتمی کاملاً متفاوت، ارائه گردید.
رفتار اجتماعی شیرها در داخل کلونی
شیرها گربه سانانی وحشی با دو نوع سازمان اجتماعی هستند که در داخل کلونی آن ها، سطوح بالایی از همکاری و تضاد، مشاهده می گردد. جالب است بدانید که سازمان اجتماعی شیرها هم مانند انسان ها، به دو دسته ساکن یا Resident و عشایر یا Nomad، تقسیم بندی می شود.
شیرها در سازمان اجتماعی ساکن، به صورت گروهی زندگی می کنند که Pride نام دارد. Pride شیرها معمولاً شامل پنج ماده، تولههای آن ها و یک یا چند نر بالغ بوده و پسران جوان، وقتی بالغ می شوند؛ از قلمرو تولد خود حذف می شوند.
دومین اجتماع سازمانی، عشایر نام دارد که در آن شیرها به صورت پراکنده، دوتایی یا منفرد حرکت کرده و جفت ها در میان مردان خویشاوندی که از Pride مادری خود طرد شده اند؛ بیشتر دیده می شود. البته همیشه این امکان وجود دارد که یک شیر، سبک زندگی خود را تغییر دهد. به بیان ساده تر، شیرهای ساکن ممکن است عشایر شوند یا برعکس.
شکار شیرها در داخل سازمان اجتماعی
برخلاف تمام گربه های دیگر، شیرها معمولاً همراه با سایر اعضای Pride خود شکار میکنند. چند شیر ماده یا Female line، با هم همکاری کرده؛ از نقاط مختلف طعمه را محاصره نموده و با یک حمله سریع، قربانی را می گیرند. شکار گروهی هماهنگ، احتمال موفقیت بیشتری را در شکار شیر به ارمغان می آورد. شیرهای نر یا Male line و برخی از شیر هی ماده، معمولاً در انتظار بازگشت شیرهای شکارچی مانده و استراحت می کنند.
تولید مثل شیرها در کلونی
شیرها در هر زمانی از سال، جفت گیری می کنند. بعضی ماده ها پلی استروس (Polyestrous) بوده و اگر شیرهای ماده ای، از بزرگ کردن توله هایشان امتناء کردند؛ نقش دایه را برای توله شیرها ایفا می نمایند. یک شیر زمانی که در گرما است؛ امکان دارد با چند شریک، جفت گیری نماید. در طبیعت، شیرهای نر و ماده، قلمرو خود و جاهای دیگر را با روش نشانه گذاری، مشخص می نمایند. در این فرآیند، برخی از شخصیت های شیرها به منظور طراحی یک الگوریتم بهینه سازی، به صورت ریاضی مدل سازی شده اند.
الگوریتم بهینهسازی شیر یا LOA
در الگوریتم شیر، یک جمعیت اولیه توسط مجموعهای از راه حلهای تولید شده تصادفی، به نام شیرها تشکیل می شود. برخی از شیرهای جمعیت اولیه (N%) به عنوان شیرهای عشایری انتخاب شده و جمعیت بقیه شیرهای ساکن به طور تصادفی به زیر مجموعه های P یا Pride تقسیم بندی می شوند. دوستان عزیز، S درصد از اعضای مجموعه P را ماده و بقیه را نر، فرض می کنیم.
برای هر شیر، بهترین راه حل به دست آمده در تکرارهای بعدی، بهترین موقعیت بازدید نامیده شده و در طی فرآیند بهینه سازی، به صورت تدریجی بروزرسانی می گردند. در الگوریتم LOA منطقه افتخار، منطقه ای است که از اعضای بهترین موقعیت بازدید شده، تشکیل شده است. در هر Pride تعدادی ماده که به صورت تصادفی انتخاب می شوند؛ به شکار خواهند رفت و شکارچیان برای محاصره و گرفتن طعمه، به سمت آن حرکت خواهند نمود. این درحالی است که بقیه ماده ها با خیال راحت، به سمت موقعیت های مختلف قلمرو حرکت می نمایند.
شیرهای نر Pride، در قلمرو پرسه می زنند. ماده های Pride با یک یا چند نر ساکن جفت شده؛ نرهای جوان از قلمرو مادری خود کنار گرفته؛ با رسیدن به بلوغ، کوچ نشین میشوند و قدرتشان کمتر از نرهای ساکن است. همچنین یک شیر عشایر، به صورت تصادفی در فضای جستجو برای یافتن مکان بهتر یا بهترین راه حل موجود، حرکت کرده و در طی این فرآیند، شیر نر عشایر، تبدیل به شیر ساکن می شود.
در سیر تکاملی الگوریتم بهینه سازی شیر، برخی از ماده های ساکن از یک Pride به Pride دیگر مهاجرت می کنند. شاید هم سبک زندگی خود را تغییر داده؛ عشایر شوند یا برعکس و بنابراین، در طی این فرآیند، به دلیل عوامل زیادی مانند کمبود غذا و رقابت، ضعیف ترین شیر مرده یا کشته می شود. فرآیند فوق تا زمانی که شرط توقف برآورده شود؛ ادامه خواهد یافت. در ادامه، مقاله به تشریح گام های الگوریتم LOA خواهیم پرداخت.
1- مقداردهی اولیه
عزیزان مجموعه پی استور، اولین گام، تولید تصادفی جمعیت در فضای راه حل می باشد. در این الگوریتم، به تک تک پاسخ های فرضی، شیر گفته می شود. در یک مسئله بهینه سازی ابعادی Nvar، یک شیر را با استفاده از رابطه زیر تعریف خواهیم کرد.
در فرمول بالا، ارزش تناسب شیرها با ارزیابی تابع هزینه محاسبه شده و از رابطه زیر، به دست می آید.
به این ترتیب، ابتدا راه حل های Npop به طور تصادفی، در فضای جستجو تولید شده و به تعداد N% از پاسخ های تولید شده، به صورت تصادفی به عنوان شیرهای عشایری انتخاب می گردند. حال ممکن است از خودتان بپرسید که تکلیف بقیه جمعیت چیست؟ در پاسخ، باید بگویم که بقیه شیرها به صورت تصادفی در دو گروه مجزا، قرار گرفته و در طی فرآیند بهینهسازی ثابت میمانند. در نظر داشته باشید که در هر Pride، بهترین موقعیتهای بازدید شده توسط اعضای آن، به عنوان موقعیت بهینه انتخاب می شود.
2- تشریح فرآیند شکار
در هر Pride، چند ماده در گروهی به دنبال طعمه می گردند تا برای قلمرو خود، غذا تهیه کنند. این شکارچیان، طی یک استراتژی های خاص، طعمه را محاصره کرده و آن را در تله می اندازند. به طور کلی، شیرها در هنگام شکار تقریباً از همان الگویی که در شکل زیر، نشان داده شده است؛ پیروی می کنند. در الگوی زیر، شیرها در 7 موقعیت بال چپ، مرکز و راست قرار گرفته و در طول شکار، هر شیر بر اساس موقعیت اعضای گروه، موقعیت خود را اصلاح می کند.
بر اساس این اصل که در حین شکار، برخی از این شکارچیان طعمه را محاصره کرده و از موقعیت مخالف طعمه حمله می نمایند؛ الگوریتم بهینه سازی شیر از یادگیری مبتنی بر مخالفت یا OBL استفاده می کند که روشی موثر برای حل مسائل بهینهسازی بوده؛ به صورت زیر، تعریف شده و دو فرمول اساسی مسئله را تولید می کند.
عزیزان، همواره این نکته را به یاد داشته باشید؛ در زمان هایی که PREY موقعیت فعلی شکار است؛ شکارچی در موقعیت جدید به منظور حمله به طعمه موردنظر قرار می گیرد و PI درصد بهبود تناسب اندام شکارچی خواهد بود. با دقت در تصویر زیر، به اهمیت این نکته پی خواهید برد.
فرمول های زیر، برای تقلید از فرآیند درگیر شدن طعمه های در حال احاطه توسط گروه های شکارچی و موقعیت های جدید مربوط به آن، پیشنهاد می گردد.
برای درک بهتر، مثالی از فرآیند احاطه کردن طعمه در الگوریتم فراابتکاری LOA توسط شیر مرکزی و شیر بال، آورده شده است. این استراتژی یک محله دایره ای شکل در اطراف طعمه ایجاد کرده و به شکارچیان اجازه می دهد تا از جهات مختلف به طعمه نزدیک شوند.
این استراتژی فرصتی برای راه حل ها، برای فرار از بهینه محلی را فراهم می کند. زیرا برخی از شکارچیان از موقعیت مخالف استفاده می کنند. بنابراین شکار در هر Pride را می توان به صورت شبه کد زیر، بیان کرد.
3- استراتژی حرکت به سمت مکان امن یا Safe place
همراهان گرامی، همانطور که قبلاً هم بیان گردید؛ در هر Pride تعدادی ماده به شکار رفته و ماده های باقی مانده به سمت یکی از مناطق قلمرو حرکت می نمایند. از آنجایی که قلمرو هر Pride از بهترین موقعیتهای شخصی هر عضو تشکیل شده و به الگوریتم بهینهسازی شیر، کمک میکند تا بهترین راه حلهای به دستآمده را در طول تکرار ذخیره کند؛ میتوان از آن به عنوان اطلاعات ارزشمند و قابل اعتماد برای بهبود مکان استفاده کرد. فرمول های مربوط به استراتژی حرکت به سمت مکان امن توسط شیرهای ماده در ادامه، آورده شده است.
شبه کد استراتژی فوق، نیز به این ترتیب خواهدبود:
همراهان گرامی، نمای شماتیک اندازه های مختلف در هر Pride از الگوریتم بهینه سازی شیر، در ادامه، آورده شده است.
4- پرسه زنی هدف دار شیر یا Roaming
رومینگ یک جستجوی محلی قوی است و به شیر کمک می کند تا نسبت به موقعیت فعلی خود، در جایگاه بهتری قرار بگیرد. برای تقلید از رفتار نرهای ساکن، R% از قلمرو Pride به صورت تصادفی انتخاب شده و توسط شیر فرضی، بازدید شده و در طول رومینگ، بهترین راه حل بازدید شده توسط شیر نر فرضی، بروز رسانی می گردد. این سیر صعودی موقعیت شیر، در شکل زیر نشان داده شده است.
در شکل بالا، کاملاً واضح است که شیر به سمت ناحیه انتخاب شده قلمرو با x واحد حرکت می کند که در آن x یک عدد تصادفی با توزیع یکنواخت است و d فاصله بین موقعیت شیر نر و ناحیه انتخاب شده قلمرو را نشان می دهد. به رابطه زیر، توجه کنید.
در شکل بالا، بردار با مبدأ موقعیت شیر نر و مقصد ناحیه انتخاب شده از قلمرو، جهت اصلی حرکت را نشان می دهد. برای ایجاد فرصتی با هدف جستجوی ناحیه وسیع تر در اطراف موقعیت فعلی و افزودن خاصیت تشدید به روش و جستجوی ناحیه وسیع تر، زاویه به این جهت اضافه می شود.
به نظر می رسد؛ زاویه ای که با توزیع یکنواخت بین بازه π/6 (rad)– و π/6 (rad) انتخاب می گردد؛ برای این هدف کافی باشد. در شبه کد زیر، رفتار شیر نر در اجتماعات سازمانی ساکن، نشان داده شده است.
در تکمیل آموزش الگوریتم بهینه سازی شیر، شبه کد، روابط و تصویر مربوط به رفتار شیر نر در اجتماعات عشایری نیز آورده شده است.
5- تکثیر نژاد یا Mating
Mating operation یک فرآیند ضروری است که بقای شیرها را تضمین کرده و فرصتی برای تبادل اطلاعات ژنتیکی بین اعضا را هم فراهم می کند. در هر قلمرو، Ma% از شیرهای ماده با یک یا چند نر ساکن، عملیات تکثیر نژاد را انجام می دهند.
در نظر بگیرید که نحوه انتخاب شیرهای نر به صورت تصادفی می باشد اما برای شیرهای از جامعه عشایر، یک تفاوت عمده وجود دارد و آن هم این است که یک ماده کوچ نشین فقط با یکی از نرهایی که به طور تصادفی انتخاب می شوند؛ جفت گیری خواهد نمود. عملگر جفت گیری یک والدین ترکیبی خطی برای تولید دو فرزند جدید است. طبق معادلات و تصویر زیر، توله های جدید پس از انتخاب شیر ماده و نر برای جفت گیری تولید می شوند.
6- دفاع یا Defense
شیرهای نر وقتی بالغ می شوند؛ پرخاشگر شده و با نرهای دیگر می جنگند. نرهای کتک خورده قلمرو خود را رها کرده و عشایر می شوند. از سوی دیگر، اگر شیر نر عشایری آنقدر قوی باشد که بخواهد با نبرد با نرها، قلمرو را تصاحب کند؛ شیر نر مقیم کتک خورده از قلمرو بیرون رانده شده و تبدیل به عشیره می شود.
بنابراین، اپراتور دفاعی در LOA به دو مرحله اصلی دفاع در برابر نرهای ساکن جدید بالغ و دفاع در برابر نرهای عشایر تقسیم می شود که در ادامه، شبه کد مربوط به هر کدام آورده شده است.
7- مهاجرت یا Migration و تعادل جمعیت شیرها یا Lions’ Population Equilibrium
با الهام از زندگی شیر، سوئیچ و رفتار مهاجرتی در طبیعت، زمانی که شیری از یک قلمرو به قلمرو دیگر سفر می کند یا سبک زندگی خود را تغییر می دهد و ماده ساکن عشایر می شود و بالعکس، تنوع قلمرو هدف را با موقعیتش در قلمرو قبلی افزایش می دهد. از طرف دیگر، مهاجرت شیرها و تغییر سبک زندگی، پلی برای تبادل اطلاعات ایجاد می کند.
از آنجایی که همیشه در جمعیت شیرها تعادل وجود دارد؛ در پایان هر تکرار، تعداد شیرهای زنده کنترل می شود. جهت رعایت حداکثر تعداد مجاز هر جنسیت در عشایر، شیرهای عشایری با کمترین ارزش تناسب اندام حذف خواهند شد. شکل زیر، نمونه ای از اپراتور مهاجرت و تعادل جمعیت شیرها را نشان می دهد.
پاورپوینت آماده الگوریتم بهینه سازی شیر LOA
پاورپوینت الگوریتم بهینه سازی شیر — Lion Optimization Algorithm در 36 اسلاید با فرمت pptx. برای ارائه درسی با قابلیت ویرایش همراه با اصول آکادمیک برای ارائه کلاسی تنظیم و آماده شده است. برای تهیه این پاورپوینت کلیک کنید.
کلام آخر در رابطه با الگوریتم بهینه سازی شیر
الگوریتم LOA بر اساس شبیه سازی رفتارهای انفرادی و مشارکتی شیرها مانند شکار، جفت گیری، دفاع و سایر رفتارها ساخته شده است. نتایج به دست آمده از ارزیابی عملکرد LOA نشان می دهد که در بیشتر موارد، نتایج برتری را در مقایسه با سایر الگوریتم های فراابتکاری، به دست می دهد و در همه موارد، با الگوریتم های متاهیوریستیک قابل مقایسه است. در انتها، خواهشمندیم نظرات و پیشنهادات خود را با ما در میان بگذارید. موفق باشید.
درباره زهرا یاوری
کارشناس ارشد رشته علوم کامپیوتر از دانشگاه تبریز، مشاور و برنامهریز آزمونهای کارشناسی ارشد، پژوهشگر در حوزه علوم کامپیوتر، علاقمند به فعالیتهای تیمی، طراح صفحات وب، تحلیلگر سیستم، ایشان تحلیلگر ارشد شرکت بیمه البرز هستند و در زمینه علوم کامپیوتر سابقه تدریس دارند.
سلام بر شما
بسیار مچکرم بابت آموزش عالی
لطفا درمورد الگوریتم های فرا ابتکاری بیشتر مطلب بگذارید
مجددا سپاس گذارم از شما
خیلی ممنون از شما