الگوریتم گرگ خاکستری: پیاده سازی، فرمول و کاربرد

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

1- الگوریتم بهینه سازی گرگ خاکستری چیست؟

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

• تحلیل آماری

الگوریتم گرگ خاکستری از چه چیزی الهام گرفته است؟

الهام‌بخش این الگوریتم رفتار گرگ خاکستری است که طعمه‌های بزرگ را در دسته شکار می‌کند و به همکاری بین گرگ‌ها تکیه می‌کند. این رفتار دو جنبه جالب دارد:

• سلسله مراتب اجتماعی
• مکانیزم شکار

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

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

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

مورو Muro و همکاران استراتژی شکار دسته گرگ را شرح می دهد و شامل موارد زیر است:

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

تعریف و فرمول الگوریتم گرگ خاکستری

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

بیشتر منطق از معادلات زیر پیروی می کند:

که در آن t نشان دهنده تکرار جاری است، بردار A و بردار C بردارهای ضریب هستند، بردار Xp بردار موقعیت طعمه و بردار X موقعیت گرگ است. بردارهای A و B برابر هستند با:

که در آن اجزای بردار a به صورت خطی از 2 به 0 از طریق تکرار کاهش می‌یابند و بردارهای تصادفی r1 و r2 با مقادیر [0,1] محاسبه شده‌اند. برای هر گرگ در هر تکرار. بردار A مبادله بین اکتشاف و بهره برداری را کنترل می کند در حالی که بردار C همیشه درجاتی از تصادفی بودن را اضافه می کند. این امر ضروری است زیرا عوامل ما می توانند در بهینه محلی گیر کنند و بیشتر فراابتکاری ها راهی برای اجتناب از آن دارند.

از آنجایی که ما موقعیت واقعی راه حل بهینه را نمی دانیم، بردار Xp به 3 بهترین راه حل بستگی دارد و فرمول های به روز رسانی هر یک از عوامل (wolfs) عبارتند از:

که در آن بردار X موقعیت فعلی عامل و بردار X(t+1) موقعیت به روز شده است. فرمول بالا نشان می دهد که موقعیت گرگ مطابق با بهترین سه گرگ از تکرار قبلی به روز می شود. توجه داشته باشید که دقیقاً برابر با میانگین سه بهترین گرگ نخواهد بود، اما به دلیل بردار C، یک جابجایی تصادفی کوچک اضافه می‌کند. این منطقی است زیرا، از یک طرف، ما می خواهیم که عوامل ما توسط بهترین افراد هدایت شوند و از طرف دیگر، ما نمی خواهیم در بهینه محلی گیر کنیم.

در نهایت، شبه کد الگوریتم گرگ خاکستری GWO برابر است با:

توجه داشته باشید که پیچیدگی زمانی الگوریتم به تعداد تکرارها، عوامل و اندازه بردارها بستگی دارد، اما به طور کلی می‌توانیم پیچیدگی زمانی را به صورت O(k . n) تقریب بزنیم، که در آن k تعداد تکرار ها و n تعداد عوامل است.

مثال الگوریتم گرگ خاکستری

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

علاوه بر این، اگر موقعیت گرگ‌های امگا را طبق فرمول‌های توضیح داده شده در بخش قبل به‌روزرسانی کنیم، می‌توانیم رفتار عوامل را در تصویر زیر (سمت راست) مشاهده کنیم. توجه داشته باشید که متغیر a که مبادله بین اکتشاف و بهره برداری را کنترل می کند، روی مقدار 2 تنظیم شده است. این به این معنی است که ما اکتشاف بیش از حد را ترجیح می دهیم:

ثانیاً، تصویر بعدی رفتار دسته گرگ را نشان می دهد که متغیر a روی مقدار 1 تنظیم شده است.

در نهایت، در تصویر زیر، متغیر a برابر با 0 است. به این معنی است که فرآیند بهینه سازی در پایان است و امیدواریم به دنبال بهترین سه گرگ به سمت راه حل بهینه همگرا شویم. ما می‌توانیم ببینیم که چگونه گرگ‌های امگا بین بهترین سه گرگ جمع می‌شوند، در حدود نقطه‌ای که از نظر هندسی مرکز بین عوامل آلفا، بتا و دلتا را نشان می‌دهد:

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

کاربردهای الگوریتم گرگ خاکستری

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

تنظیم فراپارامتر

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

به عنوان مثال، با استفاده از GWO می‌توانیم فراپارامترهای Gradient Boosting را بهینه کنیم. در آن صورت، می‌توانیم بردار موقعیت را به‌گونه‌ای بسازیم که هر یک از مؤلفه‌های برداری برای یک مقدار دارای یک فراپارامتر خاص باشد. به عنوان مثال، X = (نرخ یادگیری، تعداد درختان، حداکثر عمق). پارامترها اصلاً نباید مقدار عددی داشته باشند زیرا ما همیشه می توانیم معیارهای خود را برای محاسبه فاصله بین عامل ها تعریف کنیم.

• هوش مصنوعی

انتخاب ویژگی

یکی دیگر از کاربردهای GWO که به یادگیری ماشین نیز مربوط می شود، انتخاب ویژگی است. این الگوریتم با ساخت مجموعه‌ای از ویژگی‌های ممکن و اصلاح مکرر این ویژگی‌ها بر اساس برخی معیارهای عملکرد تا زمانی که راه‌حل مورد نظر پیدا شود، کار می‌کند.

این رویکرد از نظر پیچیدگی زمانی بسیار ارزان‌تر است، زیرا پیچیدگی برای انتخاب بهترین زیرمجموعه ویژگی‌ها به طور تصاعدی با هر متغیر اضافی افزایش می‌یابد. این به این دلیل است که تعداد کل زیر مجموعه های یک مجموعه با n عنصر 2 به توان n است. یعنی اگر 30 ویژگی مختلف به عنوان ورودی در الگوریتم یادگیری ماشین داشته باشیم، در نتیجه تعداد زیر مجموعه های ممکن از 30 ویژگی 2 به توان 30=1.073.741.824 می شود!

بنابراین، نمایش 30 ویژگی به عنوان یک بردار باینری با اندازه 30 امکان پذیرتر خواهد بود (هر بیت یک ویژگی خاص است، 1 نشان می دهد که ویژگی گنجانده شده است و 0 وجود ندارد). آن بردار باینری موقعیت عامل را نشان می دهد و می تواند به راحتی توسط GWO یا هر فراابتکاری دیگر استفاده شود.

کاربردهای دیگر

علاوه بر مثال‌های بالا، GWO با موفقیت در حل مشکلات مختلفی مانند:

• مشکل فروشنده دوره گرد (TSP)
• مشکل حداقل درخت پوشا
• سیستم های معادلات غیر خطی
• مشکل پخش بار و موارد دیگر

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