در این پست آموزشی، به تشریح الگوریتم بهینه سازی شیر مورچه یا The Ant Lion Optimizer خواهیم پرداخت. الگوریتم ALO، از سری الگوریتم های فرا ابتکاری [1] یا فرااکتشافی (Hyperinnovative algorithms)، برگرفته از طبیعت یا بر پایه الگوریتم های NI بوده و در طی فرآیند بهینه سازی [2] (Optimization)، مکانیسم شکار مورچه ها را در طبیعت تقلید می‌کند. این الگوریتم متاهیوریستیک (Metaheuristic algorithm)، در طی 6 مرحله اصلی شکار طعمه، مانند راه رفتن تصادفی مورچه ها، ساخت تله ها، به دام افتادن مورچه ها در تله ها، شکار طعمه ها، ساخت مجدد تله ها و نخبه گرایی، پیاده سازی می‌شود که در ادامه، به تشریح هر کدام از این مراحل خواهیم پرداخت.
فلسفه طراحی الگوریتم های بهینه سازی
اگر شما یک محقق، در زمینه الگوریتم های بهینه سازی هستید؛ این قسمت را با دقت مطالعه کنید. همان طور که می‌دانید؛ امروزه یعنی تا اواسط سال 2022 میلادی، الگوریتم های فراابتکاری به عنوان تکنیک های اولیه برای به دست آوردن راه حل های بهینه مسائل Np-hard مهندسی استفاده شده است. در علوم کامپیوتر [4] Non-Deterministic Polynomial ها همان مسائل پیچیده واقعی تلقی می‌شوند که دارای پیچیدگی محاسباتی بوده و برای آن ها در زمان معقول، راه حل سریع یافته نشده است.
از آنجایی که مسائل واقعی دارای تعداد بسیار زیادی راه حل محلی (Local solutions) هستند؛ الگوریتم های قطعی (Deterministic algorithms)، قابلیت اطمینان خود را در یافتن بهینه سراسری (Global optimum) از دست داده؛ دیگر صلاحیت لازم برای یافتن پاسخ بهینه برای مسائل واقعی پیچیده مهندسی را نخواهند داشت. در این زمان است که از طریق الگوریتم‌های بهینه‌سازی تصادفی می‌توان به پاسخ بهینه دست یافت.
الگوریتم های بهینه‌سازی تصادفی، به خانواده الگوریتم هایی با عملگرهای تصادفی از جمله الگوریتم های تکاملی (Evolutionary algorithms) اشاره دارند که تصادفی بودن مشخصه اصلی الگوریتم های تصادفی (Stochastic algorithms) بوده و هنگام جستجوی بهینه سراسری در فضاهای جستجو [5] از عملگرهای تصادفی استفاده می‌کنند. در واقع، می‌توان نتیجه گرفت که الگوریتم های تکاملی، با ایجاد یک یا چند راه حل تصادفی برای مسئله مورد بررسی، بهینه سراسری را در فضای جستجو، جستجو کرده؛ راه حل های کاندید را تولید نموده؛ سپس مراحل بهبود مجموعه کاندیداها را پشت سر هم طی می‌کند تا زمانی که شرط پایانی مسئله، برآورده شود.
از جمله مهم ترین الگوریتم های فراابتکاری می‌توان به الگوریتم شبیه ساز حرارتی [6] (Simulated Annealing)، الگوریتم ژنتیک [7] (Genetic Algorithm)، الگوریتم جستجوی متغیر محلی [8] (Variable Neighborhood Search)، الگوریتم متاهیوریستیک رقابت استعماری [9] (Imperialistic Competitive Algorithm)، الگوریتم بهینه سازی جستجوی گرانشی [10] (Gravitational Search Algorithm)، الگوریتم بهینه سازی مبتنی بر یادگیری و آموزش [11] (Teaching-Learning-Based Optimization) و غیره اشاره کرد.
درباره مقاله
این پست آموزشی، یک الگوریتم جدید بر پایه قوانین و اصول مبتنی بر طبیعت به نام Ant Lion Optimizer (ALO) یا الگوریتم بهینه سازی شیر مورچه را بررسی می‌نماید که برای اولین بار در سال 2015 در دانشکده فناوری اطلاعات و ارتباطات (School of Information and Communication Technology) از دانشگاه گریفیث Griffith University استرالیا و بار دیگر در موسسه تجارت و فناوری کوئینزلند (Queensland Institute of Business and Technology) استرالیا توسط آقای سید علی میرجلیلی (Seyedali Mirjalili [12]) معرفی و ارائه گردید.
زیست شناسی مورچه ها
مورچه‌های Doodlebugs که اصطلاحاً شام پشت نیز نامیده می‌شوند؛ متعلق به خانواده Myrmeleontidae و راسته Neuroptera یا حشرات بال‌دار هستند و اغلب در ایالات متحده آمریکا زیست می‌نمایند. چرخه زندگی این نوع مورچه ها، شامل دو مرحله اصلی است:
- لارو (Larvae)
- بالغ (Adult)
طول عمر کل طبیعی شام پشت ها، می تواند تا 3 سال طول بکشد که بیشتر در لاروها رخ می‌دهد و در واقع، فقط 3 تا 5 هفته از طول عمر این نوع مورچه ها شامل دوره بزرگسالی می‌گردد. مورچه ها در یک پیله دگردیسی کرده و فرآیند بالغ شدن را طی می‌کنند. آن ها بیشتر در مرحله لارو در حال شکار هستند و جالب است بدانید که حتی نام آن ها از رفتار منحصر به فرد شکار و طعمه مورد علاقه شان، نشأت می گیرد. لابد، از خودتان می‌پرسید که در دوره بزرگسالی بر مورچه ها چه می‌گذرد؟! در پاسخ به این سؤال باید بگویم که شام پشت ها، دوره بزرگسالی را برای تولیدمثل سپری می‌نمایند.
یک لارو مورچه، با حرکت در امتداد یک مسیر دایره ای (Circular path) و پرتاب شن ها با فک عظیم و قدرتمند خود، گودالی مخروطی شکل (Cone-shaped pits) را در ماسه حفر کرده؛ در زیر مخروط به عنوان شکارچی اُتراق کرده و منتظر می‌ماند تا حشرات کوچک از قبیل دیگر مورچه ها یا هر نوع حشره ریزجثه دیگری، را در گودال به دام بیندازد. در شکل زیر، نحوه حفر گودال و استتار لارو مورچه، به نمایش گذاشته شده است.
لبه مخروط (Edge of the cone) به اندازه کافی تیز است تا حشرات را به راحتی، به پایین تله (Trap) هدایت کند. هنگامی که لارو مورچه متوجه می‌شود که طعمه ای در تله افتاده است؛ مانند هر موجود زنده دیگری، سعی می‌نماید تا آن را اسیر کند. با این حال، حشرات معمولاً بلافاصله گرفتار نمی‌شوند و در ابتدا سعی می‌کنند تا از تله فرار کنند.
یکی از حیرت های آفرینش، این است که در هنگام فرار طعمه، لارو مورچه به صورت کاملاً غریزی و البته به طور هوشمندانه (Intelligently)، ماسه ها را به سمت لبه گودال پرتاب می‌کند تا طعمه را به ته گودال بلغزاند. باید به اطلاعتان برسانم؛ فک لارو مورچه، به قدری قدرتمند است که می‌تواند طعمه ای که در آن گرفتار می‌شود را به زیر خاک کشیده و مصرف کند.
مورچه ها پس از مصرف طعمه، باقیمانده آن را به بیرون از گودال پرتاب کرده و گودال را برای شکار بعدی، اصلاح می‌کنند. دوستان عزیز، شاید باورتان نشود؛ رفتار جالب دیگری که در سبک زندگی مورچه ها مشاهده شده است؛ مربوط بودن اندازه تله و دو مورد دیگر اعم از: میزان گرسنگی (Level of hunger) و شکل ماه (Shape of the moon) است. بله! تعجب نکنید. شکل ماه هم در سبک زندگی مورچه شام پشت، تأثیر می‌گذارد.
مورچه ها با گرسنگی بیشتر و یا زمانی که ماه کامل می‌شود؛ تمایل دارند تله های بزرگتری را حفر کنند. آن ها برای بهبود شانس بقای خود، به این روش تکامل یافته و سازگار شده اند. همچنین کشف شده است که یک مورچه به طور مستقیم، شکل ماه را برای تصمیم گیری در مورد اندازه تله، مشاهده نمی‌کند اما دارای یک ساعت قمری داخلی برای چنین تصمیماتی است.
الگوریتم متاهیوریستیک ALO
اگر بخواهیم در یک جمله و به صورت خلاصه نحوه عملکرد الگوریتم شیر مورچه را توضیح دهیم؛ این گونه می‌توان بیان کرد که الگوریتم ALO تعامل بین مورچه ها و نحوه رفتار آن ها را در تله، تقلید می‌کند. برای مدل‌سازی چنین فعل و انفعالی، مورچه‌ها باید در فضای جستجو حرکت کنند. مورچه‌ها اجازه دارند تا آن ها را شکار نمایند و با استفاده از تله ها بهتر شوند. از آنجایی که مورچه ها، هنگام جستجوی غذا در طبیعت و به صورت کاملاً تصادفی حرکت می‌کنند؛ یک معادله راه رفتن تصادفی، برای مدل سازی حرکت مورچه ها به شرح زیر، انتخاب می‌شود.
در رابطه بالا، زمانی که Cumsum مجموع تجمعی را محاسبه می‌کند؛ n حداکثر تعداد تکرار خواهد بود و همچنین در این حالت، t مرحله پیاده روی تصادفی را نشان داده و r(t) یک تابع تصادفی است و به صورت زیر، تعریف می‌گردد که در آن، t مرحله پیاده روی تصادفی را نشان داده و rand، یک عدد تصادفی است که با توزیع یکنواخت در بازه [0،1] تولید می‌شود.
برای داشتن تصویری از پیاده روی تصادفی مورچه در الگوریتم بهینه سازی شیر مورچه، شکل زیر، ارائه گردیده است. در این شکل، 3 پیاده روی تصادفی در 500 تکرار نشان داده شده است. شکل زیر، نشان می‌دهد که پیاده روی تصادفی مورد استفاده، ممکن است به طور چشمگیری در اطراف مبدأ، نوسان (منحنی قرمز)، روند افزایشی (منحنی سیاه) یا رفتار نزولی (منحنی آبی) داشته باشد.
در ادامه، روابط مربوط به الگوریتم متاهیوریستیک ALO، موقعیت مورچه ها (Position of ants) در طول بهینه سازی، در ماتریس (Matrix) زیر، ذخیره و استفاده می‌گردد.
زمانی که MAnt ماتریس ذخیره موقعیت هر مورچه فرض می‌گردد؛ n تعداد مورچه ها و d تعداد متغیرها را نشان می‌دهد. لازم به ذکر است که مورچه ها مشابه ذرات در الگوریتم بهینه سازی PSO [14] یا افراد در الگوریتم متاهیوریستیک GA هستند. فراموش نکنید که موقعیت یک مورچه، به پارامترهای یک راه حل خاص اشاره دارد. ماتریس MAnt برای ذخیره موقعیت همه مورچه ها یا متغیرهای همه راه حل ها (Variables of all solutions)، در طول بهینه سازی در نظر گرفته شده؛ برای ارزیابی هر مورچه، یک تابع تناسب یا Fitness function یا تابع هدف (Objective function) در طول بهینه‌سازی استفاده می‌شود و ماتریس زیر، ارزش تناسب یا Fitness value مربوط به همه مورچه‌ها را ذخیره می‌نماید.
ماتریس بالا، ماتریس صرفه جویی در تناسب هر مورچه است. n تعداد مورچه ها و f تابع هدف را نشان داده و در طول بهینه سازی، شرایط زیر برای الگوریتم بهینه سازی شیر مورچه اعمال می‌شود:
- مورچه ها با استفاده از پیاده روی های تصادفی مختلف، در فضای جستجو حرکت می‌کنند.
- فرآیند پیاده روی تصادفی، برای تمام ابعاد مورچه ها اعمال شده و تحت تأثیر تله های مورچه ها قرار می‌گیرند.
- مورچه ها می‌توانند متناسب با تناسب اندام خود، گودال بسازند و در واقع، هر چه تناسب اندام هر مورچه، بیشتر باشد؛ گودال نیز بزرگتر خواهد بود.
- مورچه هایی با گودال های بزرگتر، احتمال بیشتری برای گرفتن طعمه، دارند.
- هر طعمه را می توان توسط یک مورچه شکارچی، در هر تکرار و نخبگان (مناسب ترین مورچه ها) شکار کرد.
- دامنه راه رفتن تصادفی به صورت تطبیقی، همواره در حال کاهش خواهد بود.
در ادامه به توضیح و تشریح هر کدام از مراحل این الگوریتم بهینه سازی، خواهیم پرداخت.
1- فرآیند راه رفتن تصادفی مورچه ها (Random walks of ants)
در یک بیان ساده و قابل فهم، فرآیند راه رفتن تصادفی مورچه ها به این صورت است که مورچه ها موقعیت خود را با پیاده روی تصادفی، در هر مرحله از بهینه سازی، به روز (Update) می‌کنند و از آنجایی که هر فضای جستجو (Search space)، دارای یک مرز یا محدوده متغیر (Range of variable) است.
به منظور حفظ پیاده‌روی‌های تصادفی در فضای جستجو، آن ها را با استفاده از معادله زیر نرمال سازی (min–max normalization) می‌نماییم که در آن ai حداقل گام تصادفی متغیر i بوده و bi حداکثر پیاده روی تصادفی در متغیر c می‌باشد. فراموش نشود که معادله زیر، باید در هر تکرار اعمال شود تا وقوع پیاده روی های تصادفی، در فضای جستجو تضمین گردد.
2- فرآیند به دام افتادن حشره در داخل چاله حفر شده توسط مورچه (Trapping in antlion’s pits)
در این مرحله از الگوریتم متاهیوریستیک شیر مورچه، معادلات مربوط به مدل سازی ریاضی تله مورچه ها در ادامه، آورده شده است.
نکته جالب این که با کمی دقت، متوجه خواهید شد؛ معادلات بالا، نشان می دهد که مورچه ها به طور تصادفی در یک هایپر راه می‌روند. کره ای که توسط بردارهای c و d در اطراف یک مورچه انتخاب شده؛ به عنوان مدل ریاضی تله، تعریف می‌گردد. در شکل زیر، یک مدل مفهومی از این رفتار، نشان داده شده است که در آن، یک فضای جستجوی دو بعدی تصویرسازی شده است. بنابراین، می‌توان نتیجه گرفت که مورچه ها باید در یک ابرکره حرکت کنند.
3- بررسی ساختار فیزیکی تله (Building trap)
دوستان عزیز، به منظور مدل سازی قابلیت شکار مورچه ها، از چرخه رولت (Roulette wheel) استفاده می‌شود. در الگوریتم ALO، برای استفاده از اُپراتور چرخه رولت و همچنین برای انتخاب مورچه های شکارچی، داشتن اطلاعات مربوط به تناسب اندام آن ها، در طول بهینه سازی، مورد نیاز است. این مکانیسم، شانس بالایی به مورچه‌های مناسب تر برای شکار بهینه، می‌دهد.
4- فرآیند لغزش طعمه به سمت شکارچی (Sliding ants towards antlion)
همراهان گرامی، با مکانیسم هایی که تاکنون ارائه شده است؛ مورچه‌ها می‌توانند تله هایی متناسب با تناسب اندام خود بسازند و همواره باید به صورت تصادفی، حرکت کنند. با این حال، شکارچی هنگامی که متوجه می‌شود؛ شکار در داخل تله، به دام افتاده است؛ شن ها را به سمت بیرون از مرکز گودال پرتاب کرده و با این رفتارخود، طعمه به دام افتاده را که سعی در فرار دارد؛ به سمت پایین تله، می‌لغزاند. برای مدل‌سازی ریاضی این رفتار، شعاع کره (Hyper-sphere) راه رفتن تصادفی مورچه ها، به صورت تطبیقی (Adaptively) کاهش یافته و برای شبیه سازی آن، از معادلات زیر استفاده می‌گردد.
شکل زیر، برای شبیه سازی رفتار کاهشی با استفاده از دو فرمول بالا، آورده شده است. در واقع، این معادلات، شعاع بروز رسانی مورچه ها را کاهش داده و روند لغزش طعمه را در داخل چاله ها، تقلید می‌نمایند.
5- فرآیند هلاک شدن شکار و بازسازی گودال (Catching prey and re-building the pit)
در مرحله آخر الگوریتم بهینه سازی شیر مورچه، شکار زمانی است که طعمه توان خود را برای مبارزه از دست داده؛ به انتهای گودال رسیده و در آرواره مورچه گرفتار می‌شود. پس از آن، شکارچی، طعمه را به داخل ماسه کشیده و شروع به تغذیه کردن از آن می‌کند. برای تقلید از این فرآیند، فرض بر این است که صید طعمه، زمانی اتفاق می‌افتد که هر کدام از مورچه ها نسبت به مورچه‌های اطراف خود، تناسب اندام مناسب تری داشته و به داخل شن می‌روند. سپس یک مورچه باید موقعیت خود را نسبت به آخرین موقعیت مورچه شکار شده، بروز کند تا شانس خود را برای گرفتن طعمه جدید، افزایش دهد. برای این منظور، از معادله زیر استفاده کنید.
نکته قابل توجه، این است که معادله بالا، باید در هر تکرار اعمال شود تا وقوع پیاده روی‌های تصادفی در فضای جستجوی الگوریتم بهینه سازی، تضمین شود.
6- فرآیند نخبه گرایی (Elitism)
در طول این الگوریتم بهینه سازی، بهترین مورچه به دست آمده در هر تکرار، ذخیره شده و به عنوان نخبه در نظر گرفته می‌شود. چرا که نخبه گرایی یکی از ویژگی های مهم الگوریتم های تکاملی بوده و به آن ها اجازه می‌دهد تا بهترین راه حل (های) به دست آمده در هر مرحله از فرآیند بهینه سازی را حفظ کنند. از آنجایی که در این الگوریتم متاهیوریستیک، نخبه مناسب ترین مورچه است؛ باید بتواند بر حرکات همه مورچه ها در طول تکرار، تأثیر بگذارد. بنابراین، فرض بر این است که هر مورچه، به طور تصادفی در اطراف یک مورچه انتخاب شده؛ توسط چرخه رولت و نخبگان، به طور همزمان به صورت زیر، راه می رود.
کلام آخر در رابطه با الگوریتم بهینه سازی شیر مورچه
همراهان گرامی مجموعه پی استور، خسته نباشید. همان طور که ملاحظه کردید؛ رفتار شکار مورچه ها و گیر افتادن طعمه در تله آن ها، دو محور اصلی این الگوریتم بهینه سازی بود. با توجه به نتایج برتر ALO بر روی اکثر توابع آزمون تک وجهی و منحنی‌های همگرایی، می‌توان نتیجه گرفت که این الگوریتم متاهیوریستیک، از قدرت بهره برداری و نرخ همگرایی بالا سود می‌برد.
در نهایت، می‌توان این گونه نتیجه گرفت که علت اصلی سرعت بالای بهره برداری و همگرایی این الگوریتم بهینه سازی، به دلیل مکانیسم کوچک شدن مرز تطبیقی پیشنهادی و نخبه گرایی الگوریتم متاهیوریستیک، بوده و اکتشاف زیاد ALO را می‌توان از نتایج توابع تست چندوجهی و ترکیبی نتیجه گرفت که به دلیل مکانیسم های انتخاب تصادفی پیاده روی و چرخه رولت است. از این که تا انتهای این آموزش، با ما همراه بودید؛ سپاس گزاریم.
موفق باشید.