الگوریتم گرگ خاکستری GWO
در این قسمت به آموزش و توضیح الگوریتم گرگ خاکستری Grey Wolf Optimizer یا به اختصار GWO پرداخته شده است. این الگوریتم توسط سید علی میرجلیلی (Seyedali Mirjalili) در سال 2014 در مقاله Grey Wolf Optimizer در ژورنال Advances in Engineering Software پایگاه علمی Elsevier ارائه شده است. در ادامه به معرفی نحوه کارکرد و آموزش و فلوچارت این الگوریتم بهینه سازی پرداخته می شود.
الگوریتم گرگ خاکستری
الگوریتم گرگ خاکستری GWO یک الگوریتم متاهیورستیک است که از ساختار سلسله مراتبی hieratical و رفتار اجتماعی گرگ های خاکستری در هنگام شکار کردن الهام گرفته است. این الگوریتم مبتنی بر جمعیت بوده، فرآیند ساده ای دارد و به سادگی قابلیت تعمیم به مسائل با ابعاد بزرگ را دارد. گرگ های خاکستری به عنوان شکارچیان راس یا apex در نظر گرفته می شوند، که در بالای هرم زنجیره غذایی هستند. گرگهای خاکستری ترجیح می دهند در یک گروه (دسته) زندگی کنند، هر گروه به طور متوسط 5-12 عضو دارد. همه اعضای این گروه دارای سلسله مراتب تسلط اجتماعی بسیار دقیق هستند و وظایف خاصی دارند. در هر گله از گرگ ها برای شکار کردن ۴ درجه وجود دارد که مانند شکل زیر به صورت یک ساختار هرمی مدل می شود.
- گرگ های رهبر گروه alpha نامیده می شوند که می توانند مذکر یا مونث باشند. این گرگ ها بر گله تسلط دارند
- گرگ های beta: کمک به گرگ های alpha در فرایند تصمیم گیری بوده و همچنین مستعد انتخاب شدن به جای آن ها هستند.
- گرگ های delta: پایین تر از گرگ های beta و شامل گرگ های پیر، شکارچی ها و گرگ های مراقبت کننده از نوزادان
- گرگ های omega: پایین ترین مرتبه در هرم سلسله مراتب که کمترین حق را نسبت به بقیه اعضای گروه دارند. بعد از همه غذا می خورند و در فرایند تصمیم گیری مشارکتی ندارند.
روش شکار در گرگ های خاکستری
در توضیح و آموزش الگوریتم گرگ خاکستری می توان گفت این الگوریتم شامل ۳ مرحله اصلی است:
- مشاهده شکار، ردیابی و تعقیب آن (tracking and approaching)
- نزدیک شدن، احاطه کردن (حلقه زدن) به دور شکار و گمراه کردن آن تا زمانی که از حرکت باز بماند (Pursing and encircling)
- حمله به شکار (attacking)
در این مقاله ساختار سلسله مراتبی و رفتار اجتماعی گرگ ها در حین فرایند شکار به صورت ریاضی مدل شده و برای طراحی الگوریتمی برای بهینه سازی مورد استفاده قرار گرفته است.
بهینه سازی با استفاده از گرگ های alpha, beta و delta انجام می شود. یک گرگ به عنوان alpha هدایت کننده اصلی الگوریتم فرض می شود و یک گرگ beta و delta نیز مشارکت دارند و بقیه گرگ ها به عنوان دنبال کننده آن ها محسوب می شوند. گرگ های خاکستری توانایی تخمین موقعیت شکار را دارند. برای مدل سازی این فرایند مراحل زیر را ببینید: در جستجوی اولیه هیچ ایده ای در مورد موقعیت شکار نداریم. فرض می شود گرگ های alpha, beta, delta دانش اول بهتری در خصوص موقعیت شکار (نقطه بهینه جواب) دارند.
تشریح بهینه ساز گرگ خاکستری GWO
در بهینه ساز گرگ خاکستری GWO، مناسب ترین راه حل را به عنوان آلفا در نظر می گیریم ، و راه حل های دوم و سوم مناسب به ترتیب بتا و دلتا نامگذاری می شوند. بقیه راه حل ها امگا در نظر گرفته می شوند. در الگوریتم GWO ، شکار توسط ? ? و δ هدایت می شود. راه حل ? از این سه گرگ پیروی می کند.
وقتی شکار توسط گرگ ها احاطه شده و از حرکت بایستد حمله به رهبری گرگ alpha شروع می شود. مدل کردن این فرآیند با استفاده از کاهش بردار a انجام می شود. از آنجا که A برداری تصادفی در بازه [-2a,2a] است، با کاهش a، بردار ضرایب A هم کاهش می یابد. اگر |A|<1 باشد، گرگ alpha به شکار ( و بقیه گرگ ها) نزدیک می شود و اگر |A|>1 گرگ از شکار ( و بقیه گرگ ها) دور خواهد شد. الگوریتم گرگ خاکستری الزام دارد که تمام گرگ ها موقعت خود را برحسب موقعیت گرگ های alpha, beta, delta آپدیت کنند.
محاصره طعمه توسط گرگ های خاکستری
در طول شکار، گرگ های خاکستری طعمه را محاصره می کنند. مدل ریاضی رفتار محاصره در معادلات زیر ارائه شده است. که در روابط زیر t تکرار فعلی ، A و C بردارهای ضریب هستند ، Xp بردار موقعیت طعمه است و X بردار موقعیت گرگ خاکستری را نشان می دهد.
بردارهای A و C به شرح زیر محاسبه می شوند:
در روابط بالا متغیرa به طور خطی در طول تکرارها از 2 به 0 کاهش می یابند و r1 ، r2 بردارهای تصادفی در بازه [0 ، 1] هستند.
عملیات شکار معمولاً توسط آلفا هدایت می شود. گرگ های بتا و دلتا ممکن است گه گاه در شکار شرکت کنند. در مدل ریاضی رفتار شکار گرگهای خاکستری ، ما فرض کردیم که آلفا ، بتا و دلتا دانش بهتری در مورد موقعیت بالقوه طعمه دارند. سه راه حل اول بهترین ذخیره می شوند و عامل دیگر موظف است موقعیت های خود را مطابق با موقعیت بهترین عوامل جستجو مطابق با معادلات زیر به روز کند.
توضیح مرحله جستجو
مرحله جستجو پروسه ای دقیقا عکس فرایند حمله دارد: در هنگام جستجو گرگ ها از یکدیگر دور می شوند تا شکار را ردیابی کنند (|A|>1) در حالی ک.ه پس از ردیابی شکار، گرگ ها در فاز حمله به یکدیگر نزدیک می شوند (|A|<1). به این پروسه واگرایی در جستجو – همگرایی در حمله می گویند.
Exploration: |A|>1
Exploitation: |A|<1
نقش بردار C: بردار C به عنوان موانع موجود در طبیعت که نزدیک شدن گرگ ها به شکار را کند می کنند در نظر گرفته می شود. بردار C به شکار وزن داده و ان را برای گرگ ها غیر قابل دستیابی تر می کند. این بردار برخلاف a به صورت خطی از ۲ تا صفر کاهش نمی یابد.
ترتیب الگوریتم
- برازندگی کلیه جواب ها محاسبه شده و سه جواب برتر به عنوان alpha, beta, deltaتا پایان الگوریتم انتخاب می شوند.
- در هر تکرار سه جواب برتر (گرگ های alpha, beta, delta) قابلیت تخمین موقعیت شکار را داشته و این کار را در هر iteration با استفاده از رابطه زیر انجام می دهند:
- در هر تکرار بعد از تعیین موقعیت گرگ های alpha, beta, delta، آپدیت موقعیت بقیه جواب ها با تبعیت از آن ها انجام می شود.
- در هر تکرار بردار a (و به تبع آن A) و C آپدیت می شوند.
- در پایان تکرارها موقعیت گرگ alpha به عنوان نقطه بهینه معرفی می شود.
شبه کد الگوریتم گرگ خاکستری
فلوچارت الگوریتم گرگ خاکستری
با توجه به مطالب ذکر شده فلوچارت الگوریتم گرگ خاکستری را می توان بصورت زیر در نظر گرفت. این فلوچارت فقط با تعیین مقادیر بردارهای A و C کار خواهد کرد. توضیح این فلوچارت براحتی با مطالعه مراحل گفته شده در بالا بسیار ساده است.
نتیجه گیری
در این پست سعی شد نحوه کار الگوریتم گرگ خاکستری توضیح، تشریح و آموزش داده شود. این الگوریتم از سال 2016 یکی از الگوریتم های محبوب در زمینه بهینه سازی در بسیاری از تحقیقات بکار گرفته شده است. سایت پی استور با هدف آموزش این الگوریتم، فلوچارت الگوریتم را نیز ارائه کرده است. این الگوریتم توانایی خوبی در حل مسائل پیوسته دارد و مدام از این الگوریتم در مقالات بروز و معتبر دنیا نام برده می شود. امیدواریم از این آموزش استفاده لازم را برده باشید.
منابع
مطالب زیر را حتما مطالعه کنید
الگوریتم سنجاب پرنده — Squirrel Search Algorithm
الگوریتم جستجوی فراکتال تصادفی — Stochastic Fractal Search
تشریح جامع الگوریتم ممتیک — Memetic Algorithm
الگوریتم جستجوی هارمونی — Harmony Search
الگوریتم بهینه سازی شیر مورچه — The Ant Lion Optimizer
با سلام و احترام من دو الگوریتم در یک مقاله خوندم آیا از الگوریتم الگوریتم بهینه سازی سینوس کسینوس و یا گرگ خاکستری می توان برای مقاله مالی و برای شناسایی متغیرها استفاده کرد؟ و ارتباط آن با این مقاله ها چطوریه و چطور بیان میشه؟ اصلا ارتباط برقرار میشه؟ در الگوریتم گرگ خاکستری منظور از طعمه کیست محاصره چیست ؟
باسلام و عرض ادب خدمت استاد ارجمند.
بنده برنامه ای(که تابع هدف من محسوب میشه) در نرم متلب جهت “مدیریت تراکم در شبکه های توزیع” نوشتم و قصد دارم این برنامه رو با الگوریتم گرگ خاکستری(GWO) اجرا کنم.
سوال بنده این است:برنامه برای داشتن خروجی به یک مقدار اولیه نیاز دارد، حال این مقدار اولیه را در الگوریتم گرگ خاکستری چگونه باید تعریف کنم و یا اینکه الگوریتم، تابع هدف من را چگونه حل میکند و به من چه مقدار اوّلیه میدهد؟
ببینهایت سپاسگزارم از مطالب ارزشمندتون…
سلام و وقت بخیر
برنامه ای که به عنوان تابع هدف نوشتید حتماً دارای ورودی و خروجی است یعنی به ازای گرفتن ورودی های متفاوت بایستی خروجی متفاوتی ایجاد کنه مثلا در تابع y = x1 + x2 + 3 ورودی ها x1 و x2 هستند و خروجی y هست. حالا الگوریتم گرگ خاکستری با مقدار دهی همین ورودی ها در طی تکرار های مختلف کاری می کنه که اون خروجی y جواب بهتری بده.
در ابتدا مقدار اولیه ورودی ها به صورت کاملاً تصادفی در بین محدوده خاصی ایجاد میشه و رفته رفته با توجه به رفتار تابع هدف در ماگزیمم سازی یا مینیمم سازی این ورودی ها عدد های بهتری به خودشون می گیرن و خروجی بهتری رو تولید می کنند و در واقع در طی تکرار های مختلف به یک خروجی خوب همگرا می شوند.
در انتها اجرا یا حل کردن یک مسئله توسط الگوریتمی مانند گرگ خاکستری یعنی تعیین ورودی های اون برنامه یا مسئله بطوری که خروجی بهتر بشه.
سلام خسته نباشید امکان استفاده از الگوریتم گرگ خاکستری تو برنامه ریزی تولید هست یا نه؟
سلام و وقت بخیر
الگوریتم گرگ خاکستری یک الگوریتم بهینه سازی هست و اگر مسئله ای قابلیت بهینه سازی و شرایط مربوط به اون رو داشته باشه قطعاً می تونه با GWO بهینه سازی بشه. شما باید مسئله خودتون در برنامه ربزی تولید رو مد نظر داشته باشید و ببنید که آیا با روش های قطعی می تونید جواب رو به دست بیارید یانه؟ اگر نتوانستید باید ببینید بعد جواب مسئله اونقدر زیاد هست که نشه با روش های دستی اون رو به دست آور یا نه؟ اگر مسئله شما جزو چنین مسائلی باشه (مسائل NP-Hard) پس اون موقع می تونه با گرگ خاکستری جواب قابل قبولی براش بدست آورد.
واقعا ازتون ممنونم.بسیاااااار عالی بود
من اشتباها امتیاز کم دادم میخواستم عالی رو بزنم یعنی همه ستاره ها رو ولی دیدم نظرم ثبت شد.واقعا عالی هستید
با سلام به نظرتون برای ارائه کلاسی کدوم یک از این الگوریتم های فراابتکاری میتونه ارائه راحت تری داشته باشه؟! ممنون
سلام. الگوریتم مورچه و ژنتیک بسیار جذاب هستند و مخاطب رو جذب می‌کنند.
از لحاظ راحت بودن هم معمولاً الگوریتم گرگ خاکستری راحت تر می‌باشد.
از این الگوریتم برای حل مسئله فروشنده دوره گرد میشه استفاده کرد؟
بله مثلا میتونید با استفاده از الگوریتم گرگ خاکستری، مسئله فروشنده دوره گرد رو در متلب پیاده سازی کنید.
سلام وقت بخیر
شما به عنوان یک متخصص که تجربه کافی در حوزه آموزش و پیاده سازی الگوریتم های فراابتکاری دارید، از نظر شما کدام الگوریتم های فراابتکاری عملکرد بهتری در حل مساله فروشنده دوره گرد در تعداد شهر های بالا ۱۰۰ تا دارد به طوری که همه از یک نوع تابع شایستگی (fitness) استفاده کنند و در عملکرد اصلی الگوریتم تغییری داده نشود. ممنون میشم تجربه خودتان را بگید
با تشکر
سلام و عرض ادب
برای حل مسئله فروشنده دوره گرد یا همون TSP الگوریتم TS یا جستجوی ممنوعه Tabu Search بهترین کارکرد رو داره و چون روال کارش برای مسائل جایگشتی هست بهترین جواب رو برای tsp می تونه داشته باشه بعد اون الگوریتم کلونی مورچگان، ژنتیک و شبیه ساز حرارتی می تونه وجود داشته باشه ولی کارایی ts رو ندارن. بقیه الگوریتم هایی که ما با اونا سرو کار داریم ماهیت پیوسته دارند و برای حل مسائل پیوسته خوب هستند و خودتون می دونید که مسئله فروشنده دوره گرد جزو مسائل گسسته جایگشتی محسوب می شه.