برای خیلی از افراد این سوال نسبتاً غیردقیق پیش آمده که از میان انبوهی الگوریتم بهینه سازی فرا ابتکاری (Metaheuristic) نظیر الگوریتم ژنتیک، تراکم ذرات (پرندگان)، قورباغه جهنده، کلونی مورچه، قطرات هوشمند آب و … کدام یک از بقیه بهتر و کارآمدتر است؟ پاسخ کوتاه و دقیق این است که هیچ کدام!

در سال 1997 دو نفر به نامهای دیوید ولپرت و ویلیام مک ردی قضیه ریاضی جالبی را به نام قضیۀ ناهار مفت نداریم (No Free Lunch-NFL) مطرح کردند. این قضیه به زبان ساده می گوید که میانگین کارآیی هر دو الگوریتم بهینه سازی دلخواه روی تمام مسائل ممکن مقدار یکسانی است. به عبارت دیگر اگر تمام مسائل بهینه سازی ممکن (که تعدادشان بیشمار است) را با هر دو الگوریتم بهینه سازی دلخواهی حل کنیم و کارآیی دو الگوریتم را با شاخص مناسبی اندازه گیری کرده و سپس میانگین گیری نماییم به عدد یکسانی خواهیم رسید!

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

نتایج یکی از دقیق ترین و علمی ترین مطالعات به منظور مقایسه کارآیی الگوریتم های بهینه سازی فراابتکاری (و به احتمال زیاد بهترین آنها تا به امروز) در سال 2011 در [1] منتشر شده است. در این مقاله 25 مسالۀ بهینه سازی دشوار و متنوع با تعداد متغیرهای نسبتاً زیاد توسط 9 الگوریتم بهینه سازی مختلف حل شده و بر اساس نتایج به دست آمده، کارآیی آنها با استفاده از تست ها آماری غیرپارامتری با هم مقایسه شده است (این تست ها وقتی مفید و ضروری هستند که از نوع توزیع آماری متغیرهای تصادفی بی خبر هستیم). الگوریتم های مورد مقایسه نیز عبارتند از PSO، IPOP-CMA-ES، CHC، SSGA، SS-BLX، SS-Arit، DE-Bin، DE-Exp و SaDE (احتمالاً اسم بیشتر این الگوریتم ها را نشنیده اید، اگرچه بیشترشان خیلی کارآمدتر از الگوریتم های محبوب در جامعه علمی ایران هستند!) جزئیات این مقاله، کاملاً تخصصی بوده و درک عمیق آن مستلزم داشتن دانش کافی در زمینه تست های آماری است. دو تا از جداول مقایسه ای به عنوان نمونه در زیر آورده شده اند.

توجه کنید که هر جدول در واقع به یک سوال پاسخ می دهد و چون سوالات متفاوتی را می توان پرسید، جداول متعددی نیز برای پاسخ دهی به آنها مورد نیاز است (مثلاً می توان پرسید که کارآمدترین الگوریتم در میان این 9 تا کدام است، یا پرسید که از میان PSO و SaDE کدام یک عملکرد بهتری دارد). نکتۀ جالب توجه و تا حدی دور از انتظار این است که در اکثر مقایسه ها، ورژن هایی از الگوریتم تکامل تفاضلی (Differential Evolution-DE) نظیر SaDE و DE-Exp برنده می شوند و نکته تاسف آور هم اینکه این الگوریتم ها در جامعه علمی ایران کمتر شناخته شده هستند و به ندرت مورد استفاده قرار می گیرند. نتیجه اینکه از الگوریتم DE که جزو الگوریتم های تکاملی است غافل نشوید!

برای دیدن لینک مرجع [1] با بیش از 3000 ارجاع اینجا را کلیک کنید.

برای دیدن لینک مقالۀ نهار مفت نداریم اینجا را کلیک کنید.

نوشته شده توسط دکتر فرشاد مریخ بیات