الگوریتم بهینه سازی شیر مورچه — The Ant Lion Optimizer

فلسفه طراحی الگوریتم های بهینه سازی

اگر شما یک محقق، در زمینه الگوریتم های بهینه سازی هستید؛ این قسمت را با دقت مطالعه کنید. همان طور که می‌دانید؛ امروزه یعنی تا اواسط سال ۲۰۲۲ میلادی، الگوریتم های فراابتکاری به عنوان تکنیک‌های اولیه برای به دست آوردن راه حل های بهینه مسائل Np-hard مهندسی استفاده شده است. در علوم کامپیوتر Non-Deterministic Polynomial ها همان مسائل پیچیده واقعی تلقی می‌شوند که دارای پیچیدگی محاسباتی بوده و برای آن‌ها در زمان معقول، راه حل سریع یافته نشده است.

از آن‌جایی که مسائل واقعی دارای تعداد بسیار زیادی راه حل محلی (Local solutions) هستند؛ الگوریتم های قطعی (Deterministic algorithms)، قابلیت اطمینان خود را در یافتن بهینه سراسری (Global optimum) از دست داده؛ دیگر صلاحیت لازم برای یافتن پاسخ بهینه برای مسائل واقعی پیچیده مهندسی را نخواهند داشت. در این زمان است که از طریق الگوریتم‌های بهینه‌سازی تصادفی می‌توان به پاسخ بهینه دست یافت.

الگوریتم های بهینه‌سازی تصادفی، به خانواده الگوریتم‌هایی با عملگرهای تصادفی از جمله الگوریتم های تکاملی (Evolutionary algorithms) اشاره دارند که تصادفی بودن مشخصه اصلی الگوریتم های تصادفی (Stochastic algorithms) بوده و هنگام جستجوی بهینه سراسری در فضاهای جستجو از عملگرهای تصادفی استفاده می‌کنند. در واقع، می‌توان نتیجه گرفت که الگوریتم های تکاملی، با ایجاد یک یا چند راه حل تصادفی برای مسئله مورد بررسی، بهینه سراسری را در فضای جستجو، جستجو کرده؛ راه حل‌های کاندید را تولید نموده؛ سپس مراحل بهبود مجموعه کاندیداها را پشت سر هم طی می‌کند تا زمانی که شرط پایانی مسئله، برآورده شود.

از جمله مهم‌ترین الگوریتم های فراابتکاری می‌توان به الگوریتم شبیه ساز حرارتی (Simulated Annealing)، الگوریتم ژنتیک (Genetic Algorithm)، الگوریتم جستجوی متغیر محلی (Variable Neighborhood Search)، الگوریتم متاهیوریستیک رقابت استعماری (Imperialistic Competitive Algorithm)، الگوریتم بهینه سازی جستجوی گرانشی (Gravitational Search Algorithm)، الگوریتم بهینه سازی مبتنی بر یادگیری و آموزش (Teaching-Learning-Based Optimization) و غیره اشاره کرد.

درباره مقاله

این پست آموزشی، یک الگوریتم جدید بر پایه قوانین و اصول مبتنی بر طبیعت به نام Ant Lion Optimizer (ALO) یا الگوریتم بهینه سازی شیر مورچه را بررسی می‌نماید که برای اولین بار در سال ۲۰۱۵ در دانشکده فناوری اطلاعات و ارتباطات (School of Information and Communication Technology) از دانشگاه گریفیث Griffith University استرالیا و بار دیگر در موسسه تجارت و فناوری کوئینزلند (Queensland Institute of Business and Technology) استرالیا توسط آقای سید علی میرجلیلی (Seyedali Mirjalili) معرفی و ارائه گردید.

زیست شناسی مورچه‌ها

مورچه‌های Doodlebugs که اصطلاحاً شام پشت نیز نامیده می‌شوند؛ متعلق به خانواده Myrmeleontidae و راسته Neuroptera یا حشرات بال‌دار هستند و اغلب در ایالات متحده آمریکا زیست می‌نمایند. چرخه زندگی این نوع مورچه‌ها، شامل دو مرحله اصلی است:

• لارو (Larvae)
• بالغ (Adult)

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

یک لارو مورچه، با حرکت در امتداد یک مسیر دایره‌ای (Circular path) و پرتاب شن‌ها با فک عظیم و قدرتمند خود، گودالی مخروطی شکل (Cone-shaped pits) را در ماسه حفر کرده؛ در زیر مخروط به عنوان شکارچی اُتراق کرده و منتظر می‌ماند تا حشرات کوچک از قبیل دیگر مورچه‌ها یا هر نوع حشره ریزجثه دیگری، را در گودال به دام بیندازد. در شکل زیر، نحوه حفر گودال و استتار لارو مورچه، به نمایش گذاشته شده است.

لبه مخروط (Edge of the cone) به اندازه کافی تیز است تا حشرات را به راحتی، به پایین تله (Trap) هدایت کند. هنگامی که لارو مورچه متوجه می‌شود که طعمه ای در تله افتاده است؛ مانند هر موجود زنده دیگری، سعی می‌نماید تا آن را اسیر کند. با این حال، حشرات معمولاً بلافاصله گرفتار نمی‌شوند و در ابتدا سعی می‌کنند تا از تله فرار کنند.

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

مورچه‌ها پس از مصرف طعمه، باقیمانده آن را به بیرون از گودال پرتاب کرده و گودال را برای شکار بعدی، اصلاح می‌کنند. دوستان عزیز، شاید باورتان نشود؛ رفتار جالب دیگری که در سبک زندگی مورچه‌ها مشاهده شده است؛ مربوط بودن اندازه تله و دو مورد دیگر اعم از: میزان گرسنگی (Level of hunger) و شکل ماه (Shape of the moon) است. بله! تعجب نکنید. شکل ماه هم در سبک زندگی مورچه شام پشت، تأثیر می‌گذارد.

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

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

الگوریتم متاهیوریستیک ALO

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

در رابطه بالا، زمانی که Cumsum مجموع تجمعی را محاسبه می‌کند؛ n حداکثر تعداد تکرار خواهد بود و همچنین در این حالت، t مرحله پیاده روی تصادفی را نشان داده و r(t) یک تابع تصادفی است و به صورت زیر، تعریف می‌گردد که در آن، t مرحله پیاده روی تصادفی را نشان داده و rand، یک عدد تصادفی است که با توزیع یکنواخت در بازه [۰،۱] تولید می‌شود.

برای داشتن تصویری از پیاده روی تصادفی مورچه در الگوریتم بهینه سازی شیر مورچه، شکل زیر، ارائه گردیده است. در این شکل، ۳ پیاده روی تصادفی در ۵۰۰ تکرار نشان داده شده است. شکل زیر، نشان می‌دهد که پیاده روی تصادفی مورد استفاده، ممکن است به طور چشمگیری در اطراف مبدأ، نوسان (منحنی قرمز)، روند افزایشی (منحنی سیاه) یا رفتار نزولی (منحنی آبی) داشته باشد.

در ادامه، روابط مربوط به الگوریتم متاهیوریستیک ALO، موقعیت مورچه‌ها (Position of ants) در طول بهینه سازی، در ماتریس (Matrix) زیر، ذخیره و استفاده می‌گردد.

زمانی که MAnt ماتریس ذخیره موقعیت هر مورچه فرض می‌گردد؛ n تعداد مورچه‌ها و d تعداد متغیرها را نشان می‌دهد. لازم به ذکر است که مورچه‌ها مشابه ذرات در الگوریتم بهینه سازی PSO یا افراد در الگوریتم متاهیوریستیک GA هستند. فراموش نکنید که موقعیت یک مورچه، به پارامترهای یک راه حل خاص اشاره دارد.

ماتریس MAnt برای ذخیره موقعیت همه مورچه‌ها یا متغیرهای همه راه حل‌ها (Variables of all solutions)، در طول بهینه سازی در نظر گرفته شده؛ برای ارزیابی هر مورچه، یک تابع تناسب یا Fitness function یا تابع هدف (Objective function) در طول بهینه‌سازی استفاده می‌شود و ماتریس زیر، ارزش تناسب یا Fitness value مربوط به همه مورچه‌ها را ذخیره می‌نماید.

ماتریس بالا، ماتریس صرفه جویی در تناسب هر مورچه است. n تعداد مورچه‌ها و f تابع هدف را نشان داده و در طول بهینه سازی، شرایط زیر برای الگوریتم بهینه سازی شیر مورچه اعمال می‌شود:

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

در ادامه به توضیح و تشریح هر کدام از مراحل این الگوریتم بهینه سازی، خواهیم پرداخت.

۱- فرآیند راه رفتن تصادفی مورچه‌ها (Random walks of ants)

در یک بیان ساده و قابل فهم، فرآیند راه رفتن تصادفی مورچه‌ها به این صورت است که مورچه‌ها موقعیت خود را با پیاده روی تصادفی، در هر مرحله از بهینه سازی، به روز (Update) می‌کنند و از آن‌جایی که هر فضای جستجو (Search space)، دارای یک مرز یا محدوده متغیر (Range of variable) است.

به منظور حفظ پیاده‌روی‌های تصادفی در فضای جستجو، آن‌ها را با استفاده از معادله زیر نرمال سازی (min–max normalization) می‌نماییم که در آن ai حداقل گام تصادفی متغیر i بوده و bi حداکثر پیاده روی تصادفی در متغیر c می‌باشد. فراموش نشود که معادله زیر، باید در هر تکرار اعمال شود تا وقوع پیاده روی‌های تصادفی، در فضای جستجو تضمین گردد.

۲- فرآیند به دام افتادن حشره در داخل چاله حفر شده توسط مورچه (Trapping in antlion’s pits)

در این مرحله از الگوریتم متاهیوریستیک شیر مورچه، معادلات مربوط به مدل سازی ریاضی تله مورچه‌ها در ادامه، آورده شده است.

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

۳- بررسی ساختار فیزیکی تله (Building trap)

دوستان عزیز، به منظور مدل سازی قابلیت شکار مورچه‌ها، از چرخه رولت (Roulette wheel) استفاده می‌شود. در الگوریتم ALO، برای استفاده از اُپراتور چرخه رولت و همچنین برای انتخاب مورچه‌های شکارچی، داشتن اطلاعات مربوط به تناسب اندام آن‌ها، در طول بهینه سازی، مورد نیاز است. این مکانیسم، شانس بالایی به مورچه‌های مناسب تر برای شکار بهینه، می‌دهد.

۴- فرآیند لغزش طعمه به سمت شکارچی (Sliding ants towards antlion)

همراهان گرامی، با مکانیسم‌هایی که تاکنون ارائه شده است؛ مورچه‌ها می‌توانند تله‌هایی متناسب با تناسب اندام خود بسازند و همواره باید به صورت تصادفی، حرکت کنند. با این حال، شکارچی هنگامی که متوجه می‌شود؛ شکار در داخل تله، به دام افتاده است؛ شن‌ها را به سمت بیرون از مرکز گودال پرتاب کرده و با این رفتارخود، طعمه به دام افتاده را که سعی در فرار دارد؛ به سمت پایین تله، می‌لغزاند. برای مدل‌سازی ریاضی این رفتار، شعاع کره (Hyper-sphere) راه رفتن تصادفی مورچه‌ها، به صورت تطبیقی (Adaptively) کاهش یافته و برای شبیه سازی آن، از معادلات زیر استفاده می‌گردد.

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

۵- فرآیند هلاک شدن شکار و بازسازی گودال (Catching prey and re-building the pit)

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

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

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

۶- فرآیند نخبه گرایی (Elitism)

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

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

کلام آخر در رابطه با الگوریتم بهینه سازی شیر مورچه

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

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