بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
الگوریتم رقابت استعماری فازی :FICA
چکیده - الگوریتم رقابت استعماری علیرغم موفقیتهایش در حل مسائل بهینه سازی، هنوز مشکل افتادن مکرر در مینیمم های محلی و پائین بودن سرعت همگرایی را در حل برخی مسائل بهینه سازی دارد. در این مقاله با ارائه ی نسخه ی فازی این الگوریتم، سعی شده است تا چالش های فوق حلی شوند. در آزمایشات از توابع مرسوم Rastrigin GrieWangk ، Ackley, Sphere و ROSenbrock بعنوان مسائل بهینهسازی استفاده شده است. نتایج حاصل از آزمایشات، کارایی و سرعت همگرایی بالای الگوریتم پیشنهادی را تایید می کنند.
۱- مقدمه
طیف وسیعی از مسائلی علوم مختلف رامی توان بصورت یک مسالے بهینه سازی مدل کرد. بنابراین یافتن جواب برای مسائل بهینه سازی اهمیت بسزایی در تمام شاخههای علمی به خصوصی رشته های مهندسی دارد. بطور کلی روشی های حل مسائل بهینه سازی را میتوان به دو دسته کلاسیک و مکاشفه ای تقسیم کرد. روشهای کلاسیک، مبتنی بر تحلیلی ریاضی تابع و در بیشتر موارد مشتق گیری می باشند. روشهای مکاشفه ای، روشهایی برای حل کلاس بسیار رایج و متداولی از مسائل می باشند. این روشها بدون استفاده از درک عمیقی از ساختار مساله، سعی در یافتن جواب دارند. به عبارت دیگر، مساله برای الگوریتم همانند جعبه سیاه است. برخی از این روش ها شامل الگوریتم ژنتیک || ۵ ، آنیلینگ شبیه - سازی شده [۵)، بهینهسازی ذرات " ||۶ ، بهینهسازی کولونی مورچگان" [۷، بالا رفتن از کوه [۷}، الگوریتم مونت کارلو و ... می باشند.
الگوریتم رقابت استعماری، یکی از روشهای مکاشفه ای برای حل مسائل بهینه سازی است که نسبت به PSO و الگوریتم ژنتیک در مسائل با ابعاد بالا
همگرایی مطلوبی از خود نشان داده است || ۱ ||. در سالهای اخیر تحقیقات زیادی بر روی بهبود ICA و افزایش کارایی آن در حل مسائل بهینه سازی صورت گرفته است. در سال ۲۰۱۰، A. Kaveh و S. Talatahari با اضافه کردن بردار تصادفی عمود بر بردار بین مستعمره و استعمارگر در گام جذب عملکرد الگوریتم را بهبود بخشیدند ||۲]. در سال ۲۰۱۱، S. Talatahari و همکارانش با اضافه کردن توابع آشوب به جای توابع تصادفی همگرایی آن را افزایش دادند ||۳}. علیرغم کارهای بسیار خوبی که در زمینه بهبود الگوریتم رقابت استعماری انجام شده است، هنوز مشکلات زیر به عنوان چالشهای اساسی مطرح است: الف) افتادن در بهینه های محلی ب) سرعت همگرایی پایین در برخی مسائل ج) افزایش بیش از حد پیچیدگی محاسباتی با افزایش ابعاد تابع د) کاهش سرعت بهبود هزینه با افزایش زمان در این مقاله برای حل چالشی های فوق، نسخه ی فازی رقابت استعماری (FICA) ارائه شده است. با بکار بردن نسخه ی فازی، هریک از مستعمرهها مستعمره ی تمام استعمارگرها با یک درجه عضویت می باشند. جهت حرکت مستعمره ها در جهت بردار حاصل از برآیند وزن دار بردارهای استعمارگرها و متناسب با تابع عضویت است. در روش فازی چون هر مستعمره به همه ی استعمارگرها متناسب با قدرتشان وابسته است و همچنین بدلیل این که در روش فازی در هر دوره ی زمانی، چندین استعمارگر ضعیفتر ممکن است با مستعمرههای قوی تر تعویض شود؛ بنابراین میزان بی نظمی مسیری که مستعمره ها در این روش طی می کنند، بالاتر است. در نتیجه، احتمال افتادن در بهینه ی محلی کاهش مییابد. همچنین در این روش، همواره جهت حرکت مستعمره ها به سمت برآیند حاصل از تمام نقاط بهینه ی شناخته شده است؛ اینکار میزان همگرایی را به میزان زیادی افزایش می دهد. در FICA، با افزایش زمان هیج امپراتوری حذف نمی گردد؛ بلکه همه ی امپراطوری ها به
سمت یک امپراطوری بهینه حرکت می کنند و در نهایت به یک امپراطوری که همان جواب بهینه است، همگرا می شوند. الگوریتم پیشنهادی بر روی توابع . Rosenbrocky Sphere Rastrigin Griewangk Ackley's تست شده است. نتایج حاصل از نظر سرعت همگرایی و کمینه ساختن هزینه، کارائی الگوریتم پیشنهادی را تایید می کنند.
۲- رقابت استعماری فازی (FICA)
در این بخشی ایده ی کلی الگوریتم FICA و جزئیات هریک از بخش -های ان تشریح شده است.
۱-۲ استراتژی الگوریتم رقابت استعماری فازی
الگوریتم رقابت استعماری بر این عقیده استوار بود که هر مستعمرهای مطلقاً دارای یک استعمارگر بوده و رفتهرفته همه ی امپراتوری ها متلاشی شده و در نهایت یک استعمارگر غالب در جهان باقی خواهد ماند. البته این عقیده در جهان گذشته که ارتباطات رشد آن چنانی نکرده بود تا حدودی برقرار بود. ولی امروزه با رشد شگفتآور فناوری ها و تبدیل شدن دنیا به دهکده ی جهانی، برای اجرای سیاست همسان سازی و مطیع سازی کشورهای ضعیفتر، دیگر نیازی نیست که کشورهای قدرتمند تسلط نظامی و سیاسی بر آن کشورها داشته باشند. بلکه کشورهای قدرتمند با در دست داشتن ابزار مختلف مانند ماهواره ، اینترنت و... به طور گسترده می توانند به تمامی کشورهای جهان تاثیر گذاشته و سیاستهای همسان سازی خود را که به مقاصد مختلفی انجام می شود، اجرا کنند. عقیده ی بالا به ما می گوید که همه ی استعمارگرها به اندازه ی نی در کشورهای ضعیف تر تسلط داشته و سیاست همسان سازی را در آنها اجرا می کنند. همچنین تعداد استعمارگرها کمتر نمی شود؛ بلکه هر کشوری که در توسعه پیشی گیرد، می تواند جای کشورهای قدرتمند قبلی را بگیرد. نکته ی دیگری که باید به آن توجه شود، این است که به مرور زمان همه ی کشورها حتی آنها که خودشان به کشورهای ضعیف تر اعمال نفوذ میکنند، شبیه به کشوری می شوند که از همه قدرتمندتر است. در پیادهسازی منطق فازی، پس از این که مستعمرهها و استعمارگرها انتخاب شدند، بوسیله ی عملگر جذب و تحت یک روش مسیریابی فازی، مستعمره ها یک جهت حرکتی برای خود در نظر گرفته و به سمت آن جهتها حرکت می کنند. سپس مشابه الگوریتم ژنتیک || ۴ || و با روش انتخاب اصلح، کشورهایی که بهترین مشخصه ی بهینگی را دارند را به عنوان استعمارگر و بقیه به عنوان مستعمره در می گیریم. به عبارت دیگر، در هر مرحله
استعمارگرهای ضعیف جای خود را با مستعمره های قوی عوض می کنند. سپس اپراتور انقلاب به مستعمرهها اعمال می شود. در نهایت حلقه ی تغییر و بهبود در فضای جستجو تا جایی ادامه مییابد که فاصله ی بین استعمارگرها از یک حد آستانه کمتر شود.
۲-۲ نحوه ی پیادهسازی منطق فازی در ICA
حالی برای پیاده سازی منطق فازی در الگوریتم استعماری هر استعمارگر را به عنوان یک مجموعه ی فازی و مستعمرههای موجود را به عنوان اعضای آن مجموعه ها (استعمارگرها) که با توابع عضویت مشخصی به هریک از استعمارگرها مرتبط هستند، در نظر گرفته می شود. استعمارگرها در هر مرحله از الگوریتم بر اساسی سیاست انتخاب اصلح انتخاب می شوند. در آزمایشات انتخاب حدود ۲ درصد از کشورها به عنوان استعمارگر نتایج مطلوبی به همراه داشته است.
بطور دقیقی تر، فرض کنید کشورهای استعمارگر و کشورهای مستعمره باشند. میزان تعلق مستعمره ی به استعمارگر با تابع عضویت بیان میشود. این تابع طبق رابطه ی زیر محاسبه میشود:
که در آن قدرت نرمالی شده استعمارگر است که طبق رابطه زیر محاسبه میگردد:
در واقع این تابع عضویت، درجه عضویت یک مستعمره به یک استعمارگر را متناسب با قدرت نسبی آن استعمارگر در مقایسه با سایر استعمارگرها و میزان فاصله ی مستعمره از آن تعریف می کند. آزمایشات نشان میدهد تاثیر دادن فاصله در این تابع عضویت، از همگرایی نارس جلوگیری می کند. بر اساس این مفروضات گام جذب طبق رابطه زیر صورت میگیرد:
در اینجا یک تابع تصادفی با توزیع یکنواخت می باشد. شکل(۱) به صورت هندسی نحوه ی حرکت مستعمرهها به سمت استعمارگرها را نشان می دهد.
دلیل اعمال طول بردارها یا به عبارتی میزان فاصله ی هر استعمارگر از مستعمره، جلوگیری از همگرایی زودرس الگوریتم می باشد. همگرایی زودرس در اکثر مواقع وقتی بوجود می آید که بیشتر مستعمره ها بجای جستجوی نقاط
مختلف و متفاوت فقط حول بهینه ترین نقاط شناخته شده نوسان کرده و درنهایت دور یک بهینه ی محلی جمع شوند.
مشابه ICA، در اینجا هم برای افزایش ناحیه ی جستجو یک انحراف زاویه ای برابر به بردار بدست آمده از برآیند بردارهای مربوط به استعمارگرها می دهیم. پارامتری است که محدوده ی انحراف زاویه ای را کنترل می کند.
در اینجا هم مشابه ICA برای جلوگیری از افتادن در مینیمم محلی از اپراتور انقلاب استفاده می شود. در FICA استفاده از روش انتخاب تصادفی مستعمره مورد استفاده در ICA در عمل نتایج خوبی ندارد. به همین خاطر به جای انتخاب تصادفی مستعمره ها، ضعیف ترین مستعمره ها در هر مرحله انتخاب شده و موقعیت تصادفی جدیدی برای آنها در نظر گرفته می شود.
۳-۲ جایگزینی استعمارگرها
در ICA اگر یک مستعمره دارای هزینه ی کمتری نسبت به استعمارگر خود شود، جای مستعمره و استعمارگر عوض می شود. شکل (۲) به این مطلب اشاره می کند.
حال تصور کنید که در یک مرحله به تعداد m مستعمره همزمان به مقداری بهینه تر از استعمارگر خود دست پیدا کنند، در این صورت فقط آن مستعمره که به بهینهترین هزینه دست پیدا کرده شانس استعمارگر شدن را دارد و 1-m مستعمره بهینه بعدی در زمان های بعدی ممکن است از بین بروند.
همچنین یک امپراتوری قدرتمند ممکن است mمستعمره داشته باشد که از n استعمارگر ضعیفتر خارجی قویتر باشند؛ در این حالت آن m مستعمره ممکن است به خاطر اعمال اپراتور انقلاب از بین رفته و استعمارگرهای ضعیفتر همچنان باقی بمانند.
در FICA برای حل این مشکل از روشی مشابه انتخاب اصلح در الگوریتم ژنتیک در هر مرحله استفاده شده است. به این صورت که در گام جایگزینی که در هر مرحله تکرار می شود، استعمارگرهای ضعیف عزل شده و مستعمره هایی که قوی تر از آن ها هستند، جای آنها را می گیرند. شکل(۳)
