بخشی از مقاله
خلاصه
امروزه با پیشرفت علوم کامپیوتری و افزایش سرعت پردازش آنها، امکان استفاده از تحلیل های تکراری برای حل بسیاری از مسائل با گستردگی بیشتری دنبال می شود. روشهای بهینه یابی فراابتکاری از جمله روش های حل تکراری است که استفاده از فرآیندهای تکرار شونده برای رسیدن به پاسخ بهینه هر مسئله می کوشند. شاید مهمترین چالش در بهینه یابی خصوصا بهینه یابی توسط الگوریتم های فراابتکاری، انتخاب الگوریتم مناسب و تنظیم پارامترهای کنترلی آن باشد.
انتخاب هر الگوریتم به نوع مسئله، الگوریتم های در دسترس، ابزارهای محاسباتی و قیدهای مسئله وابسته است. در این مقاله با بررسی 7 الگوریتم بهینه یابی به بررسی نحوه عملکرد آنها در حل چهار مسئله آزمون پرداخته شده و به کمک شاخص های عملکردی مقایسه ای از کیفیت آنها ارایه شده است. نتایج تحلیل نشان می دهد که الگوریتم هایی که شاخص پراکندگی جمعیت در آنها با تکرار برنامه کاهش پیدا کرده اما به صفر نمی رسد، پاسخ های مناسب تری نسبت به سایر الگوریتم ها از خود نشان می دهند.
.1 مقدمه
بهینه یابی یکی از شاخه های ریاضیات است که روی دست یابی به مقدار خاصی - کمینه یا بیشینه - از یک یا چند تابع تمرکز دارد. به عبارت دیگر بهینه یابی از طریق قواعد مشخص به یافتن پاسخ پذیرفتی برای یک مسئله واقعی می پردازد. بهینه یابی در مسائل متنوعی مانند برنامه ریزی ریاضی، اقتصاد، علوم مدیریتی، تجارت، پزشکی، هوش مصنوعی، علوم مهندسی و ... کاربرد دارد. با پیشرفت تکنولوژی در کامپیوترها و افزایش سرعت پردازش آنها اجرای روش های بهینه یابی برای طراحی بهینه مسائل بزرگ مقیاس امکان پذیر شد و دسته بندی های مختلفی از روش های بهینه یابی توسعه یافت.
الگوریتم های بهینه یابی فراابتکاری که از جمله دسته روشهای بهینه یابی پرکاربرد در سال های اخیر به شمار می روند، اغلب از طبیعت الهام می گیرند و این نوع الگوریتم ها بسته به نوع منبع الهام به چند دسته تقسیم می شوند. دسته اصلی این الگوریتم ها از علوم زیست شناسی الهام گرفته اند و از حیوانات به عنوان یک مدل بهینه یابی استفاده می کنند. علوم منبع دیگری برای الهام در الگوریتم های بهینه یابی است. الگوریتم های این دسته عموما از علوم فیزیک و شیمی الهام می گیرند.
دسته الگوریتم های الهام گیرنده از هنر در بهینه یابی کلی بسیار موفقیت داشته اند. این دسته از خلاقیت موجود در رفتار هنرمندان مانند موسیقیدانان و معماران الهام می گیرد. رفتار اجتماعی از دیگر منابع الهام در بهینه یابی است که از رفتارهای اجتماعی برای حل مسائل بهینه یابی استفاده می کند. اگر چه منابع مختلفی در الگوریتم های فراابتکاری وجود دارد اما شباهت های زیادی در ساختار آنها به چشم می خورد.
در این مقاله به بررسی 7 الگوریتم بهینه یابی که دارای مشخصه های منحصر به فرد بوده و اغلب جزء الگوریتم های پایه در بهینه یابی به شمار می رود، پرداخته شده و به کمک شاخص های عملکردی کیفیت و سرعت همگرایی هر یک مورد بررسی قرار گرفته است. در ادامه ابتدا الگوریتم های مورد استفاده معرفی شده و پس از آن توابع آزمون و شاخص های عملکردی در ارزیابی الگوریتم ها بیان می گردد و در پایان مقایسه ای از رفتار و عملکرد هر الگوریتم برای دستیابی به پاسخ بهینه ارایه می گردد.
.2 الگوریتم های مورد استفاده
الگوریتم های مورد استفاده عموما از الگوریتم های پایه بهینه یابی بوده که از عملگر یا مشخصه منحصر به فردی در روند بهینه یابی استفاده نموده اند. از آنجایی که توانایی هر الگوریتم وابسته به عملگرهای آن می باشد، بنابراین این نحوه ی انتخاب می تواند هم سنجشی برای الگوریتم باشد هم سنجشی بر عملگر مورد استفاده در آن الگوریتم را ارایه دهد. در جدول 1 الگوریتم های مورد استفاده و ویژگی آنها ارایه شده است.
الگوریتم PSO از شبیه سازی رفتار اجتماعی الهام گرفته و ایده انتقال اطلاعات بین اعضا را به عنوان یک مزیت در رسیدن به بهترین پاسخ در نظر می گیرد PSO .[1] در بسیاری از مسائل واقعی جهان به کار گرفته شده است. الگوریتم استاندارد PSO با یک جمعیت که به طور تصادفی ایجاد شده است، آغاز می شود. هر ذره به طور هوشمندانه در فضای جستجو حرکت کرده و به دنبال بهترین نقطه که دارای بالاترین شایستگی است، می گردد.
نسخه اصلی PSO با استفاده از یک معادله سرعت برای هر ذره که بر اساس سرعت قبلی، راستای بهترین شخصی و بهترین کلی تعیین می شود، به موقعیت جدید هدایت می شود. در تولید این بردار ضرایب تصادفی در بردار های تفاضلی مربوط به بهترین شخصی و بهترین کلی ضرب می شوند تا فرآیند تصادفی بودن نیز در جستجو حفظ شود. علاوه بر ضرایب تصادفی ذکر شده، ضرایب از پیش تعیین شده ای در الگوریتم لحاظ می گردد که عملا باعث تغییر در اثر گذاری بخش بهترین شخصی و بهترین کلی می شود.
الگوریتم HS یک الگوریتم الهام گرفته از موسیقی است که بر پایه فرآیندهای خلاقانه یک موسیقیدان پایه گذاری شده است .[2] این الگوریتم بر روی مسائل مختلف مهندسی شامل طراحی سازه، طراحی شبکه توزیع آب، طراحی قابهای فولادی، مسائل مدیریت منابع آب و مهندسی خاک پیاده سازی شده است. در طی فرآیند بهینه یابی، هر بردار هارمونی از حافظه و بر اساس نرخ توجه به حافظه، نرخ تنظیم کوک و فرآیند تصادفی تولید می شود. پس از تولید بردار جدید در صورتی که برازندگی بیشتری نسبت به بدترین پاسخ موجود در حافظه داشته باشد، بردار جدید جایگزین آخرین بردار حافظه خواهد شد. تنظیم کوک بسیار شبیه به عملگر جهش در GA می باشد و فرآیند تصادفی نیز برای کشف نواحی جدید با شایستگی بیشتر کمک خواهد کرد.
در الگوریتم IC جمعیت به گروه های مختلف تحت انواع امپراتوری دسته بنده می شود و روند همگرایی به گونه ای است که ضعیف ترین عضو امپراتوری با کمترین توان به امپراتوری دیگر انتقال داده می شود. جمعیت موجود در هر امپراتوری با تمایل بیشتری به سمت رهبر امپراتوری حرکت می کنند که این موضوع باعث شده است تا فضای جستجو به محدوده های مختلف تقسیم شده و به نحو مطلوبی جستجو شود .[3]
مبنای الگوریتم TLBO برگرفته از نحوه انتقال آموزش از طریق معلم به دانش آموزان در یک کلاس و تاثیر آن بر روی دانش آموزان می باشد. روند همگرایی این روش در دو فاز معلم و دانش آموز انجام می شود. در فاز معلم، جمعیت با محوریت معلم که عضو شاخص مجموعه می باشد به سوی پاسخ بهینه پیش می رود و در فاز دانش آموز مجموعه دانش آموزان هستند که در روند همگرایی به یکدیگر کمک می کنند .[4]
در الگوریتم SOS با الهام از روند تعامل در اکوسیستم، منطقی تنظیم شده است که روند جستجوی پاسخ بهینه در سه فاز همبستگی، کمال گرایی و انگلی دنبال شده و جمعیت موجود در الگوریتم مجموعه فضای جستجو را به خوبی دنبال می کند و در عین حال سرعت را در دستیابی به پاسخ بهینه از دست نمی دهد .[5] اساس الگوریتم DE بر مبنای روابط برداری پایه ریزی شده است. این روش یک روش جستجوی تصادفی با رویکرد خودسازماندهی کننده است، همچنین در این روش نیازی به معادلات گرادیانی نیست. پاسخ DE به صورت یک بردار گزارش می شود و عملگرهایی مشابه جهش و پیوند در GA نیز در این روش قابل پیاده سازی است .[6]
الگوریتم GA روش بهینه یابی توانمند بر اساس مشخصه های ژنتیک و انتخاب طبیعی است .[7] در ابتدا عملگرهای پیوند، جهش و انتخاب در سیستم های هوشمند مطرح شد. این عملگر ها اساسا بخشهای ذاتی الگوریتم ژنتیک به شمار می روند. تاکنون تعداد زیادی از این نوع الگوریتم تهیه وتوسعه یافته است. یکی از مزایای اصلی GA عدم نیاز به روابط گرادیانی و انعطاف پذیر بودن آن در حل انواع مسائل بهینه یابی است. هر جمعیت در این الگوریتم بر اساس فرآیندهای تولید نسل به جمعیت جدید تبدیل شده و به این صورت فضای جستجو را برای یافتن پاسخ مناسب می پیماید. از معایب این روش می توان به اهمیت پارامترهای کنترلی، تعداد جمعیت و معیارهای عملگر انتخاب برای دستیابی به پاسخ مناسب اشاره کرد که در صورت عدم انتخاب مناسب آنها، فرآیند همگرایی به پاسخ مناسب با مشکل رو به رو می شود.
.3 ارزیابی الگوریتم ها
برای ارزیابی هر الگوریتم لازم است تا معیارهای سنجشی جهت بررسی کیفیت و سرعت همگرایی تعریف گردد. در این مقاله از شش شاخص زیر استفاده شده است:
. بهترین پاسخ
. میانگین پاسخ ها
. انحراف معیار پاسخ ها
. تغییرات بهترین پاسخ در طول اجرای برنامه
. تغییرات میانگین پاسخ ها در طول اجرای برنامه
. تغییرات شاخص پراکندگی جمعیت در طول اجرای برنامه [8] در این مقاله شاخص پراکندگی جمعیت مطابق رابطه - 1 - در نظر گرفته شده است.
