بهینه ساز گرگ خاکستری Grey Wolf Optimizer
- نوع فایل : کتاب
- زبان : فارسی
- ناشر : الزویر Elsevier
- چاپ و سال / کشور: 2014
توضیحات
چاپ شده در مجله پیشرفت در نرم افزار مهندسی – Advances in Engineering Software
رشته های مرتبط مهندسی کامپیوتر، مهندسی نرم افزار، مهندسی الگوریتم ها و محاسبات
۱٫ مقدمه معرفی روش های بهینه سازی فرا ابتکاری در طی دو دهه اخیر محبوبیت و رواج بسیار زیادی را داشته است. در عین شگفتی، برخی از آن ها نظیر الگوریتم ژنتیکی (GA)(1)، بهینه سازی کلنی مورچه(ACO)(2) و بهینه سازی ازدحام ذرات(۳) نه تنها در میان دانشمندان علوم کامپیوتر، بلکه دانشمندان رشته های مختلف نسبتا شناخته شده می باشند. علاوه بر طیف وسیعی از کار های نظری، این روش های بهینه سازی در زمینه های مطالعاتی مختلف به کار گرفته شده اند. سوال مطرح شده این است که چرا الگوریتم های فرا ابتکاری گسترش چشمگیری داشته اند. پاسخ به این سوال را می توان در قالب چهار دلیل خلاصه سازی کرد: سادگی، انعطاف پذیری،مکانیسم عاری از مشتق گیری و اجتناب از نقطه بهینه محلی. اول، الگوریتم های فرا ابتکاری نسبتا ساده می باشند. آن ها عمدتا الهام گرفته از مفاهیم بسیار ساده می باشند. الهامات معمولا مربوط به پدیده های فیزیکی، رفتار های حیوانات یا مفاهیم تکاملی هستند. سادگی به دانشمندان رشته کامپیوتر امکان شبیه سازی مفاهیم طبیعی مختلف، پیشنهاد الگوریتم های فرا ابتکاری جدید، ترکیب دو یا چند الگوریتم فرا ابتکاری یا بهبود الگوریتم های فرا ابتکاری فعلی را می دهد. به علاوه، سادگی به دانشمندان دیگر امکان یادگیری سریع الگوریتم های فرا اکتشافی و به کار گیری آن ها را در حل مسائل خود می دهد. دوما، انعطاف پذیری اشاره به قابلیت کاربرد الگوریتم های فرا ابتکاری در مسائل مختلف بدون هر گونه تغییرات در ساختار الگوریتم دارد. الگوریتم های فرا ابتکاری به راحتی قابل کاربرد برای مسائل مختلف می باشند زیرا آن ها اغلب مسائل را به صورت جعبه سیاه فرض می کنند. به عبارت دیگر، تنها ورودی ها و خروجی های یک سیستم برای یک الگوریتم فرا ابتکاری مهم می باشند. بنا بر این، تنها چیزی که یک طراح نیاز دارد این است که بداند چگونه مسئله خود را برای الگوریتم های فرا ابتکاری ارایه کند. سوما، اکثریت الگوریتم های فرا ابتکاری، مکانیسم های عاری از مشتق گیری می باشند. بر عکس رویکرد های بهینه سازی مبتنی بر گرادیان،الگوریتم های فرا ابتکاری، مسائل را به طور تصادفی بهینه سازی می کنند. فرایند بهینه سازی با راه حل های تصادفی شروع می شوند و نیازی به محاسبه مشتق فضای جست و جو برای یافتن نقطه بهینه نیست. این ویژگی موجب شده است تا الگوریتم های فرا ابتکاری برای مسائل واقعی با اطلاعات اشتقاقی ناشناخته یا پر هزینه بسیار مناسب باشند. در نهایت، الگوریتم های فرا ابتکاری دارای قابلیت های برتری برای اجتناب از نقاط بهینه محلی در مقایسه با فنون بهینه سازی متعارف و سنتی می باشند. این ویژگی ناشی از ماهیت تصادفی الگوریتم های فرا ابتکاری است که به آن ها امکان اجتناب از رکود در راه حل های محلی و جست و جوی گسترده فضای کامل جست و جو را می دهد. فضای جست و جوی مسائل واقعی معمولا مجهول و بسیار پیچیده با تعداد زیادی نقطه بهینه محلی است از این روی الگوریتم های فرا ابتکاری، گزینه های خوبی برای بهینه سازی این مسائل واقعی چالش بر انگیز می باشند. قضیه (NFL) از نهار مجانی خبری نیست، در این لازم به ذکر می باشد. این قضیه به طور منطقی اثبات کرده است که هیچ الگوریتم ابتکاری برای حل همه مسائل بهینه سازی، بهترین نیست. به عبارت دیگر، یک الگوریتم فرا ابتکاری خاص ممکن است در یک مجموعه از مسائل، نتایج بسیار خوب و مفیدی را نشان دهد، ولی همین الگوریتم در یک مجموعه متفاوت از مسائل دیگر، عملکرد ضعیفی را به معرض نمایش بگذارد. پر واضح است که NFL موجب فعال تر شدن این زمینه مورد مطالعه شود که به نوبه خود منجر به بهبود رویکرد های فعلی و پیشنهاد الگوریتم های فرا ابتکاری جدید در هر سال می شود. این روش هم چنین به ما انگیزه توسعه یک الگوریتم فرا ابتکاری جدید با الهام گیری از گرگ های خاکستری را می دهد. به طور ملی، الگوریتم های فرا ابتکاری را می توان به دو دسته اصلی طبقه بندی کرد: مبتنی بر تک راه حل و مبتنی بر جمعیت. در دسته اول( برای مثال الگوریتم تبرید شبیه سازی شده(۵)، فرایند جست و جو با یک راه حل کاندید شروع می شود. این تک راه حل کاندید سپس در طول تکرار ها بهبود می یابد. با این حال، الگوریتم های فرا ابتکاری مبتنی بر جمعیت، بهینه سازی را با استفاده از مجموعه ای از راه حل ها( جمعیت) انجام می دهند. در این نمونه، فرایند جست و جو با یک جمعیت اولیه تصادفی شروع می شود( راه حل های چند گانه) و این جمعیت در طی یک دوره از تکرار ها بهبود می یابد. الگوریتم های فرا ابتکاری مبتنی بر جمعیت دارای برخی مزیت ها نسبت به الگوریتم های مبتنی بر تک راه حل می باشند: راه حل های چند گانه اطلاعاتی را در مورد فضای جست و جو به اشتراک می کذارند که منجر به جهش های نا گهانی به سمت یک بخش مفید از فضای جست و جو می شود. • راه حل های کاندید چند گانه به یک دیگر در اجتناب از راه حل های بهینه محلی کمک می کنند • الگوریتم های فرا ابتکاری مبتنی بر جمعیت به طور کلی دارای اکتشاف بیشتری در مقایسه با الگوریتم های مبتنی بر تک راه حل می باشند. یکی از شاخه های جالب الگوریتم های فرا ابتکاری مبانی بر جمعیت هوش ازدحامی(SI) است. مفاهیم هوش ازدحامی اولین بار در ۱۹۹۳(۶) پیشنهاد شد. بر اساس گفته بانبو و همکاران(۱)، SI، هوش جمعی براینده از گروه هایی از عوامل ساده می باشد. الهامات فنون هوش ازدحامی، عمدتا بر گرفته از کلنی های طبیعی، دسته های پرنده ها، گله های حیوانات و دسته های ماهیان می باشد. برخی از رایج ترین روش هی SI شامل ACO [2], PSO [3] و کلنی زنبور عسل(ABC)(7) می باشند. یک مرور منابع جامع از الگوریتم های SI در بخش بعدی ارایه می شود. برخی از مزیت های الگوریتم های هوش ازدحامی به شکل زیر می باشند: • الگوریتم های هوش ازدحامی اطلاعاتی را در مورد فضای جست و جو در روند تکرار حفظ می کنند در حالی که الگوریتم های تکاملی (EA)، اطلاعات نسل های قبلی را دور می اندازند. • الگوریتم های هوش ازدحامی اغلب از حافظه برای ذخیره بهترین راه حل بدست آمده تا کنون استفاده می کنند • الگوریتم های هوش ازدحامی معمولا دارای پارامتر های کم تری برای تعدیل می باشند • الگوریتم های هوش ازدحامی دارای عملگر ها یا اپراتور های کم تری در مقایسه با رویکرد های تکاملی(کراس آور، موتاسیون(جهش)، نخبه گرایی و از این قبیل موارد)دارد • پیاده سازی الگوریتم های هوش ازدحامی آسان است. صرف نظر از تفاوت های بین الگوریتم های فرا ابتکاری، یک خصوصیت مشترک، تقسیم فرایند جست و جو به دو مرحله: اکتشاف و بهره برداری است(۸-۱۲). مرحله اکتشاف، اشاره به فرایند تحقیق و بررسی مناطق مفید فضای جست و جو در مقیاس گسترده تا حد امکان دارد. یگ الگوریتم باید اپراتور های تصادفی برای جست و جوی تصادفی و کلی فضای جست و جو به منظور پشتیبانی از این مرحله داشته باشد. با این حال بهره برداری، اشاره به قابلیت جست و جوی محلی حول مناطق مناسب و مفید بدست آمده در مرحله اکتشاف دارد. یافتن یک تعادل مناسی بین این دو مرحله به دلیل ماهیت تصادفی الگوریتم های فرا ابتکاری یک وظیفه چالش بر انگیز محسوب می شود. مطالعه حاضر یک روش SI جدید را با الهام گیری از رفتار شکار و سلسله مراتب اجتماعی گله های گرگ خاکستری ارایه می کند. ادامه این مقاله به صورت زیر سازمان دهی شده است: در بخش ۲ مرور منابعی در خصوص فنون SI دیده می شود. بخش ۳ شرح کلی از الگوریتم پیشنهادی GWO در اختیار می گذارد. نتایج و بحث مربوط به توابع الگو، مسائل نیمه واقعی و کاربرد واقعی به ترتیب در بخش های ۴-۶ ارایه شده است. در نهایت، بخش ۷ شامل نتیجه گیری و پیشنهاداتی برای سمت و سوی مطالعات آینده است.
رشته های مرتبط مهندسی کامپیوتر، مهندسی نرم افزار، مهندسی الگوریتم ها و محاسبات
۱٫ مقدمه معرفی روش های بهینه سازی فرا ابتکاری در طی دو دهه اخیر محبوبیت و رواج بسیار زیادی را داشته است. در عین شگفتی، برخی از آن ها نظیر الگوریتم ژنتیکی (GA)(1)، بهینه سازی کلنی مورچه(ACO)(2) و بهینه سازی ازدحام ذرات(۳) نه تنها در میان دانشمندان علوم کامپیوتر، بلکه دانشمندان رشته های مختلف نسبتا شناخته شده می باشند. علاوه بر طیف وسیعی از کار های نظری، این روش های بهینه سازی در زمینه های مطالعاتی مختلف به کار گرفته شده اند. سوال مطرح شده این است که چرا الگوریتم های فرا ابتکاری گسترش چشمگیری داشته اند. پاسخ به این سوال را می توان در قالب چهار دلیل خلاصه سازی کرد: سادگی، انعطاف پذیری،مکانیسم عاری از مشتق گیری و اجتناب از نقطه بهینه محلی. اول، الگوریتم های فرا ابتکاری نسبتا ساده می باشند. آن ها عمدتا الهام گرفته از مفاهیم بسیار ساده می باشند. الهامات معمولا مربوط به پدیده های فیزیکی، رفتار های حیوانات یا مفاهیم تکاملی هستند. سادگی به دانشمندان رشته کامپیوتر امکان شبیه سازی مفاهیم طبیعی مختلف، پیشنهاد الگوریتم های فرا ابتکاری جدید، ترکیب دو یا چند الگوریتم فرا ابتکاری یا بهبود الگوریتم های فرا ابتکاری فعلی را می دهد. به علاوه، سادگی به دانشمندان دیگر امکان یادگیری سریع الگوریتم های فرا اکتشافی و به کار گیری آن ها را در حل مسائل خود می دهد. دوما، انعطاف پذیری اشاره به قابلیت کاربرد الگوریتم های فرا ابتکاری در مسائل مختلف بدون هر گونه تغییرات در ساختار الگوریتم دارد. الگوریتم های فرا ابتکاری به راحتی قابل کاربرد برای مسائل مختلف می باشند زیرا آن ها اغلب مسائل را به صورت جعبه سیاه فرض می کنند. به عبارت دیگر، تنها ورودی ها و خروجی های یک سیستم برای یک الگوریتم فرا ابتکاری مهم می باشند. بنا بر این، تنها چیزی که یک طراح نیاز دارد این است که بداند چگونه مسئله خود را برای الگوریتم های فرا ابتکاری ارایه کند. سوما، اکثریت الگوریتم های فرا ابتکاری، مکانیسم های عاری از مشتق گیری می باشند. بر عکس رویکرد های بهینه سازی مبتنی بر گرادیان،الگوریتم های فرا ابتکاری، مسائل را به طور تصادفی بهینه سازی می کنند. فرایند بهینه سازی با راه حل های تصادفی شروع می شوند و نیازی به محاسبه مشتق فضای جست و جو برای یافتن نقطه بهینه نیست. این ویژگی موجب شده است تا الگوریتم های فرا ابتکاری برای مسائل واقعی با اطلاعات اشتقاقی ناشناخته یا پر هزینه بسیار مناسب باشند. در نهایت، الگوریتم های فرا ابتکاری دارای قابلیت های برتری برای اجتناب از نقاط بهینه محلی در مقایسه با فنون بهینه سازی متعارف و سنتی می باشند. این ویژگی ناشی از ماهیت تصادفی الگوریتم های فرا ابتکاری است که به آن ها امکان اجتناب از رکود در راه حل های محلی و جست و جوی گسترده فضای کامل جست و جو را می دهد. فضای جست و جوی مسائل واقعی معمولا مجهول و بسیار پیچیده با تعداد زیادی نقطه بهینه محلی است از این روی الگوریتم های فرا ابتکاری، گزینه های خوبی برای بهینه سازی این مسائل واقعی چالش بر انگیز می باشند. قضیه (NFL) از نهار مجانی خبری نیست، در این لازم به ذکر می باشد. این قضیه به طور منطقی اثبات کرده است که هیچ الگوریتم ابتکاری برای حل همه مسائل بهینه سازی، بهترین نیست. به عبارت دیگر، یک الگوریتم فرا ابتکاری خاص ممکن است در یک مجموعه از مسائل، نتایج بسیار خوب و مفیدی را نشان دهد، ولی همین الگوریتم در یک مجموعه متفاوت از مسائل دیگر، عملکرد ضعیفی را به معرض نمایش بگذارد. پر واضح است که NFL موجب فعال تر شدن این زمینه مورد مطالعه شود که به نوبه خود منجر به بهبود رویکرد های فعلی و پیشنهاد الگوریتم های فرا ابتکاری جدید در هر سال می شود. این روش هم چنین به ما انگیزه توسعه یک الگوریتم فرا ابتکاری جدید با الهام گیری از گرگ های خاکستری را می دهد. به طور ملی، الگوریتم های فرا ابتکاری را می توان به دو دسته اصلی طبقه بندی کرد: مبتنی بر تک راه حل و مبتنی بر جمعیت. در دسته اول( برای مثال الگوریتم تبرید شبیه سازی شده(۵)، فرایند جست و جو با یک راه حل کاندید شروع می شود. این تک راه حل کاندید سپس در طول تکرار ها بهبود می یابد. با این حال، الگوریتم های فرا ابتکاری مبتنی بر جمعیت، بهینه سازی را با استفاده از مجموعه ای از راه حل ها( جمعیت) انجام می دهند. در این نمونه، فرایند جست و جو با یک جمعیت اولیه تصادفی شروع می شود( راه حل های چند گانه) و این جمعیت در طی یک دوره از تکرار ها بهبود می یابد. الگوریتم های فرا ابتکاری مبتنی بر جمعیت دارای برخی مزیت ها نسبت به الگوریتم های مبتنی بر تک راه حل می باشند: راه حل های چند گانه اطلاعاتی را در مورد فضای جست و جو به اشتراک می کذارند که منجر به جهش های نا گهانی به سمت یک بخش مفید از فضای جست و جو می شود. • راه حل های کاندید چند گانه به یک دیگر در اجتناب از راه حل های بهینه محلی کمک می کنند • الگوریتم های فرا ابتکاری مبتنی بر جمعیت به طور کلی دارای اکتشاف بیشتری در مقایسه با الگوریتم های مبتنی بر تک راه حل می باشند. یکی از شاخه های جالب الگوریتم های فرا ابتکاری مبانی بر جمعیت هوش ازدحامی(SI) است. مفاهیم هوش ازدحامی اولین بار در ۱۹۹۳(۶) پیشنهاد شد. بر اساس گفته بانبو و همکاران(۱)، SI، هوش جمعی براینده از گروه هایی از عوامل ساده می باشد. الهامات فنون هوش ازدحامی، عمدتا بر گرفته از کلنی های طبیعی، دسته های پرنده ها، گله های حیوانات و دسته های ماهیان می باشد. برخی از رایج ترین روش هی SI شامل ACO [2], PSO [3] و کلنی زنبور عسل(ABC)(7) می باشند. یک مرور منابع جامع از الگوریتم های SI در بخش بعدی ارایه می شود. برخی از مزیت های الگوریتم های هوش ازدحامی به شکل زیر می باشند: • الگوریتم های هوش ازدحامی اطلاعاتی را در مورد فضای جست و جو در روند تکرار حفظ می کنند در حالی که الگوریتم های تکاملی (EA)، اطلاعات نسل های قبلی را دور می اندازند. • الگوریتم های هوش ازدحامی اغلب از حافظه برای ذخیره بهترین راه حل بدست آمده تا کنون استفاده می کنند • الگوریتم های هوش ازدحامی معمولا دارای پارامتر های کم تری برای تعدیل می باشند • الگوریتم های هوش ازدحامی دارای عملگر ها یا اپراتور های کم تری در مقایسه با رویکرد های تکاملی(کراس آور، موتاسیون(جهش)، نخبه گرایی و از این قبیل موارد)دارد • پیاده سازی الگوریتم های هوش ازدحامی آسان است. صرف نظر از تفاوت های بین الگوریتم های فرا ابتکاری، یک خصوصیت مشترک، تقسیم فرایند جست و جو به دو مرحله: اکتشاف و بهره برداری است(۸-۱۲). مرحله اکتشاف، اشاره به فرایند تحقیق و بررسی مناطق مفید فضای جست و جو در مقیاس گسترده تا حد امکان دارد. یگ الگوریتم باید اپراتور های تصادفی برای جست و جوی تصادفی و کلی فضای جست و جو به منظور پشتیبانی از این مرحله داشته باشد. با این حال بهره برداری، اشاره به قابلیت جست و جوی محلی حول مناطق مناسب و مفید بدست آمده در مرحله اکتشاف دارد. یافتن یک تعادل مناسی بین این دو مرحله به دلیل ماهیت تصادفی الگوریتم های فرا ابتکاری یک وظیفه چالش بر انگیز محسوب می شود. مطالعه حاضر یک روش SI جدید را با الهام گیری از رفتار شکار و سلسله مراتب اجتماعی گله های گرگ خاکستری ارایه می کند. ادامه این مقاله به صورت زیر سازمان دهی شده است: در بخش ۲ مرور منابعی در خصوص فنون SI دیده می شود. بخش ۳ شرح کلی از الگوریتم پیشنهادی GWO در اختیار می گذارد. نتایج و بحث مربوط به توابع الگو، مسائل نیمه واقعی و کاربرد واقعی به ترتیب در بخش های ۴-۶ ارایه شده است. در نهایت، بخش ۷ شامل نتیجه گیری و پیشنهاداتی برای سمت و سوی مطالعات آینده است.
Description
۱٫ Introduction Meta-heuristic optimization techniques have become very popular over the last two decades. Surprisingly, some of them such as Genetic Algorithm (GA) [1], Ant Colony Optimization (ACO) [2], and Particle Swarm Optimization (PSO) [3] are fairly well-known among not only computer scientists but also scientists from different fields. In addition to the huge number of theoretical works, such optimization techniques have been applied in various fields of study. There is a question here as to why meta-heuristics have become remarkably common. The answer to this question can be summarized into four main reasons: simplicity, flexibility, derivation-free mechanism, and local optima avoidance. First, meta-heuristics are fairly simple. They have been mostly inspired by very simple concepts. The inspirations are typically related to physical phenomena, animals’ behaviors, or evolutionary concepts. The simplicity allows computer scientists to simulate different natural concepts, propose new meta-heuristics, hybridize two or more meta-heuristics, or improve the current meta-heuristics. Moreover, the simplicity assists other scientists to learn meta-heuristics quickly and apply them to their problems. Second, flexibility refers to the applicability of meta-heuristics to different problems without any special changes in the structure of the algorithm. Meta-heuristics are readily applicable to different problems since they mostly assume problems as black boxes. In other words, only the input(s) and output(s) of a system are important for a meta-heuristic. So, all a designer needs is to know how to represent his/her problem for metaheuristics. Third, the majority of meta-heuristics have derivation-free mechanisms. In contrast to gradient-based optimization approaches, meta-heuristics optimize problems stochastically. The optimization process starts with random solution(s), and there is no need to calculate the derivative of search spaces to find the optimum. This makes meta-heuristics highly suitable for real problems with expensive or unknown derivative information. Finally, meta-heuristics have superior abilities to avoid local optima compared to conventional optimization techniques. This is due to the stochastic nature of meta-heuristics which allow them to avoid stagnation in local solutions and search the entire search space extensively. The search space of real problems is usually unknown and very complex with a massive number of local optima, so meta-heuristics are good options for optimizing these challenging real problems. The No Free Lunch (NFL) theorem [4] is worth mentioning here. This theorem has logically proved that there is no meta-heuristic best suited for solving all optimization problems. In other words, a particular metaheuristic may show very promising results on a set of problems, but the same algorithm may show poor performance on a different set of problems. Obviously, NFL makes this field of study highly active which results in enhancing current approaches and proposing new meta-heuristics every year. This also motivates our attempts to develop a new meta-heuristic with inspiration from grey wolves. Generally speaking, meta-heuristics can be divided into two main classes: single-solution-based and population-based. In the former class (Simulated Annealing [5] for instance) the search process starts with one candidate solution. This single candidate solution is then improved over the course of iterations. Populationbased meta-heuristics, however, perform the optimization using a set of solutions (population). In this case the search process starts with a random initial population (multiple solutions), and this population is enhanced over the course of iterations. Population-based meta-heuristics have some advantages compared to single solutionbased algorithms: Multiple candidate solutions share information about the search space which results in sudden jumps toward the promising part of search space Multiple candidate solutions assist each other to avoid locally optimal solutions Population-based meta-heuristics generally have greater exploration compared to single solution-based algorithms One of the interesting branches of the population-based meta-heuristics is Swarm Intelligence (SI). The concepts of SI was first proposed in 1993 [6]. According to Bonabeau et al. [1], SI is “The emergent collective intelligence of groups of simple agents”. The inspirations of SI techniques originate mostly from natural colonies, flock, herds, and schools. Some of the most popular SI techniques are ACO [2], PSO [3], and Artificial Bee Colony (ABC) [7]. A comprehensive literature review of the SI algorithms is provided in the next section. Some of the advantages of SI algorithms are: SI algorithms preserve information about the search space over the course of iteration, whereas Evolutionary Algorithms (EA) discard the information of the previous generations SI algorithms often utilize memory to save the best solution obtained so far SI algorithms usually have fewer parameters to adjust SI algorithms have less operators compared to evolutionary approaches (crossover, mutation, elitism, and so on) SI algorithms are easy to implement Regardless of the differences between the meta-heuristics, a common feature is the division of the search process into two phases: exploration and exploitation [8-12]. The exploration phase refers to the process of investigating the promising area(s) of the search space as broadly as possible. An algorithm needs to have stochastic operators to randomly and globally search the search space in order to support this phase. However, exploitation refers to the local search capability around the promising regions obtained in the exploration phase. Finding a proper balance between these two phases is considered a challenging task due to the stochastic nature of meta-heuristics. This work proposes a new SI technique with inspiration from the social hierarchy and hunting behavior of grey wolf packs. The rest of the paper is organized as follows: Section 2 presents a literature review of SI techniques. Section 3 outlines the proposed GWO algorithm. The results and discussion of benchmark functions, semi-real problems, and a real application are presented in Section 4, Section 5, and Section 6, respectively. Finally, Section 7 concludes the work and suggests some directions for future studies
