بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
الگوريتم جهش ترکيبي قورباغه ي فازي تطبيقي
الگوريتم جهش ترکيبي قورباغه يک الگوريتم متاهيورستيک بر اساس انتقال خصوصيات ميباشد. الگوريتم هاي متاهيوريستيک نمـيتواننـد بـه طور قطعي به جواب بهينه همگرا شوند. يکي از روشهاي حل اين مشکل ، استفاده از روشهايي ترکيبي مانند منطق فازي است . در اين مقاله روشي ترکيبي با استفاده از منطق فازي ارائه شده است که الگوريتم جهش ترکيبي قورباغه ي فازي تطبيقي ناميده ميشـود. در ايـن الگـوريتم ، بـروز رساني مکان هر قورباغه به کمک منطق فازي انجام ميشود. براي اثبات برتري سرعت ، دقت و قـدرت همگرايـي روش پيشـنهادي نسـبت بـه الگوريتم پايه از توابع محک استاندارد استفاده شده است و نتايج حاصل بيانگر برتري روش پيشنهادي نسبت به آن است .
کليد واژه - الگوريتم جهش ترکيبي قورباغه ، منطق فازي، الگوريتم جهش ترکيبي قورباغه فازي تطبيقي
١- مقدمه
الگوريتم جهش ترکيبي قورباغه (SFLA1) در سال ٢٠٠٣ توسـطusuff و Lansey بيان شد. هدف اصلي از بيـان ايـن الگـوريتم ، حل مسائل پيچيده ي بهينه سازي بدون استفاده از روابط رياضي بود [١] , [٢]. SFLA ترکيبي ازمزيت هاي دو الگـوريتم MA2 وPSO3 است . اين الگوريتم از زندگي گروهي قورباغه ها و رفتار آن - ها هنگام جست و جوي غذا الهـام گرفتـه شـده اسـت . در روش مفروض مکان هر قورباغه بيانگر جوابي از مسئله ميباشد. در ايـن روش جمعيت اوليه به چند گروه مجزا تقسيم ميشود که تعـداد قورباغه هاي موجود در همه ي گروه ها با هم برابر است . بر اسـاس اين تقسيم بندي دو نوع تکنيک جستجو در اين الگـوريتم وجـود دارد، تکنيک اول که تکنيک جستجوي محلي است و بر اساس آن قورباغه ها در هر گروه با تبـادل اطلاعـات موقعيـت خـود را جـاي بهترين قورباغه براي رسيدن به غذا بهبود ميدهند و تکنيک دوم مربوط به تبادل اطلاعات بين گروه ها ميباشد، که بر اسـاس آن ، بعد از هر جستجوي محلي در گروه ها، اطلاعات بدست آمده بـين گروه ها با هم مقايسه ميشود. در هر گروه موقعيت بدترين قورباغه توسط بهترين قورباغه در همان گروه بهبود پيدا ميکند. بـه ايـن صورت که اگر قورباغه در موقعيت جديد داراي برازندگي بهتـري نسبت به موقعيت قبلي باشد، جايگزين آن ميشود. در صـورتيکه جواب بهبود پيدا نکـرد، بـا کمـک بهتـرين قورباغـه ي سراسـري موقعيت آن بهبود پيدا ميکند. در غير اين صورت ، مکان فعلـي قورباغه با يک موقعيت جديد تصادفي جايگزين ميشود.
الگوريتم هاي متاهيوريستيک نميتوانند به طور قطعي به جـواب بهينه همگرا شوند[١٣]. همچنـين SFLA اولـين بـار بـراي حـل مسائل گسسته پيشنهاد شد[١٢]. براي حـل مسـائل پيوسـته بـا اسـتفاده از SFLA، بايـد تغييراتـي در جهـش قورباغـه هـا بـراي رسيدن به مکان بعدي اعمال شود. در SFLA اصلي ايـن جهـش در مجموعه نقاط گسسته محاسبه مـيشـود[١١]. در ايـن مقالـه ابتدا تغييرات لازم روي جهش قورباغه ها براي پيوسته کـردن آن صورت گرفته است ، سپس روشي ترکيبـي بـا اسـتفاده از منطـق فازي ارائه شده است که الگوريتم جهش ترکيبـي قورباغـه فـازي تطبيقي ناميده ميشود. در اين الگوريتم ، بروز رسـاني مکـان هـر قورباغه به کمک منطق فازي انجام ميشود . اين استراتژي مطرح شده الگوريتم جهش ترکيبـي قورباغـه فـازي تطبيقـي-Fuzzy ) (SFLA نام گذاري ميشود.
بخش هاي بعدي اين مقاله به اين صورت سازماندهي شـده اسـت ، در بخش دوم کارهـاي مـرتبط مطـرح مـيشـود. دربخـش سـومSFLA استاندارد مورد بحث قرار گرفته اسـت . در بخـش چهـارم روش پيشنهادي مطرح ميشـود. در بخـش پـنجم آزمـايش هـاي انجام گرفته ارائه ميشود و در نهايت در بخش ششم نتيجه گيري بيان خواهد شد.
٢- کارهاي مرتبط
همانطور که اشاره شد اين الگوريتم ترکيبي از دو الگـوريتم MAو PSO است . براي بهبود در عملکرد PSO، اين الگوريتم با ديگـر روشهاي هوشمند ترکيب شده است [٤],[٣]. براي نمونه در [٥]با الگوريتم هاي تکاملي و در [٦] با منطق فازي ترکيب شده است .در [٨] يـک نمونـه از PSO بـا عنـوان FPSO ارائـه شـده اسـت .
موقعيت ذرات در اين مدل از PSO به صورت فـازي تعيـين مـي- شود به اين صورت که براي هر ذره با توجه به مکـاني کـه در آن قرار دارد پارامتري با عنوان درجـه عضـويت در نظـر گرفتـه مـي شود. در [٩] نيز از منطـق فـازي در نمونـه اي ديگـر از PSO بـا عنوان FATPSO استفاده شده است . ورودي هاي سيستم فـازي در اين مدل عبارت اند از بهترين شايستگي حاصل و بردار سرعت نظير آن . خروجي هاي سيستم فـازي در ايـن مـدل دو پـارامتر آستانه هسـتند کـه مکـان و سـرعت ذرات در فضـاي جسـتجو را کنترل ميکنند. در [٧] نيز يک سيستم فـازي جهـت بهبـود در عملکرد PSO ارائه شده است . که ورودي هاي اين سيستم فـازي عبارت اند از فاصله بين بهترين ذره ي سراسري و بهترين تجربـه هر ذره و تعداد نسل هايي که در آن بهينه ترين برازنـدگي بـدون تغيير است . همچنين خروجي هاي اين سيستم ضرايب W و C١و C2 اند که به ترتيب ضريب اجتماعي و پارامترهاي شـناختي و اجتماعي مي باشند.
٣- الگوريتم جهش ترکيبي قورباغه
هدف اصلي SFLA ، حل مسائل پيچيـده ي بهينـه سـازي بـدون استفاده از روابط رياضي است [١]. اين الگـوريتم کـه از طبيعـت الهام گرفته شده اسـت از دو قسـمت جسـتجوي محلـي و تبـادل اطلاعات به صورت سراسري تشکيل شـده اسـت . ايـن الگـوريتم طي عمليات ممتيک با گذشت زمان تکامل پيدا ميکند. در ايـن الگوريتم ، meme ها کوچکترين واحد جامعـه و تبـادل اطلاعـاتي
هستند، که توسط قورباغه ها حمل ميشوند. memeهـا در SFLA
معادل ژن ها در الگوريتم ژنتيک هسـتند امـا تکامـل خـود را بـر اساس تبادل اطلاعات بدست ميآورد . جمعيت اوليه بـه چنـدين گروه ٤ که هر کدام به نوبه ي خود شامل يک زيرگروه ٥ مـيباشـند تقسيم ميشود. عمليات تکاملي در زيرگروه ها انجام ميشود. گـام حرکتي براي بهبـود حرکـت يـک قورباغـه يـا بهتـرين مکـان درزيرگروه يا در بين کل جمعيت است .
شکل ١ :نحوه ي تشکيل memplexها
الگوريتم اصلي SFLA در ٦ مرحله ي اصلي انجام مي شـود. ايـن مراحل عبارت اند از:
١- توليد جمعيت اوليه بصورت تصادفي. پس از توليد جمعيـت اوليه بايستي جمعيت از بهترين جواب تـا بـدترين جـواب مرتـب شود.
٢-مشخص کردن اعضاي گـروه هـا. اگـر قورباغـه ي jام در کـل جمعيت را به صورت Fj و گروه iام را با mi نشان دهيم ، آنگـاه اعضاي گروه iام را به صـورتيکه در معادلـه ي (١) تعريـف شـده است ، مشخص ميکنيم :
٣- در مرحله ي بعدي فرايند ساختن و تکامل زيرگـروه هـا انجـام ميشود. براي شروع عمليات جست و جوي محلـي هـر گـروه بـه عنوان يک جامعه ي مستقل عمل مـيکنـد. هـر زيرگـروه شـامل
قورباغه است ، که بـر اسـاس توزيـع هندسـي کـه بـه صورت معادله (٢) تعريف ميشود از گروه اصلي بدست ميآيد.
بر اسـاس معادلـه ي (٢) قورباغـه اي کـه برازنـدگي بـالاتري دارد احتمال انتخاب بالاتري براي عضويت در زيرگروه خواهـد داشـت .
هر قورباغه در هر زيرگروه با يادگيري از وضعيت بهترين قورباغه - ي زيرگروه ، يا بهترين قورباغه در جمعيت ، به سمت مکان بهينـه حرکت ميکند. بهترين و بدترين مکان قورباغه ها در هر زيرگـروه را به ترتيب با، نشان ميدهيم .
بدترين قورباغه درهر زيرگروه بـر اسـاس گـام مشـخص شـده در معادله ي (٣) مکان خود را بهبود ميبخشد.
در معادله ي حداکثر گـام حرکـت مجـاز، kشـماره ي تکرار يا نسل وr1 يک عدد تصادفي در بازه ي صفر تا ١ ميباشند.همچنين در معادله ي (٣)، به ترتيب بـراي گـام هـاي منفي و مثبت محاسبه ميشوند.بنابراين ، مکان بدترين قورباغه ، براساس معادله ي (٤) بدست مي- آيد.
در صورتيکه جواب بهبود پيدا نکرد روابط (٣ و ٤) را تکـرار مـي- کنيم با اين تفاوت که در حالت جديد بجاي xB در روابط فوقxg که موقعيت بهترين قورباغه در کل جمعيت است را قرار مـي دهيم . اگر با اعمال اين تغيير باز هم در جواب بهبـودي حاصـل نشد، يک جواب بصورت تصـادفي توليـد کـرده و آن را جـايگزين
xw ميکنيم . به خاطر اينکه همه ي درايه هاي بـردار x اعـداد صحيح هستند، پس از هر بار اعمال روابط (٣ و ٤) بايستي جـواب حاصله را گرد کنيم .
٤- مرحله ي ٣ را براي تعدادي تکرار که از قبل مشـخص شـده ادامه ميدهيم .
٥ - در اين مرحله پس از بهبود موقعييت قورباغـه هـا، جمعيـت جديد را از بهترين جواب تا بدترين جواب مرتب ميکنيم .
٦- در صورتيکه شـرط پايـان الگـوريتم بـرآورده شـده باشـد از الگوريتم بيرون ميآييم در غير اين صورت به مرحله ي ٢ باز مـي گرديم و ساير مراحل را تکرار ميکنيم .
٤- استراتژي پيشنهادي FSFLA
در اين مقاله با معرفي ضـريب اجتمـاعي در SFLA و اسـتفاده از منطق فازي براي تطبيق پذيري آن در حين تکامل سعي در بـالا بردن دقت و فرار از بهينه ي محلي داريم . با توجـه بـه اينکـه بـا گذشت زمان و در حين تکامل شرايط و برازندگي قورباغـه هـا در
حال تغيير است ، بنابراين ضريب اجتماعي براي حفظ کـارايياش نيازمند به روزرساني است . اين ايده ميتواند در نحوه ي عملکـرد قورباغه ها جهت عمليات جستجو٦ و استخراج ٧ موثر باشد. به اين صورت که در ابتدا جستجو انجام شود و کل محيط بررسي شـود و در ادامه با عمل استخراج اطلاعات مفيد از آنچه جستجو شـده است جمع آوري شود. هـدف از ارائـه ايـن طـرح ايجـاد پويـايي و افـزايش قابليـت تطبيـق در حـين تکامـل در SFLA مـي باشـد.
سيسـتم فـازي مـورد اسـتفاه در اينجـا داراي دو ورودي و يـک فلوچارت الگوريتم پيشنهادي در شکل ٢ آمده است .
خروجي است . ورودي هاي اين سيستم متغيرهايي براي ارزيـابي کارايي SFLA مي باشـند و خروجـي آن ضـريب اجتمـاعي و يـا تغيير ضريب اجتماعي مي باشد. وروديهاي سيستم فازي نزديکي بدترين قورباغه به بهترين قورباغه ي محلي و يا سراسـري ( d) و بهترين ارزيابي کارايي فعلي (NCBPE٨) و خروجـي آن تغييـرات ضريب اجتماعي تعريف ميشود.
با توجه به اينکه مسائل مختلف بهينه سازي داراي محدوده ي مختلفي از مقادير ارزيابي کارايي ميباشند، بنابراين NCBPEبايد به فرمت نرمالي تبديل شود تا بتواند براي يک رنج وسيع و نامحدودي از مسائل بهينه سازي مورد استفاده قرار گيرد. با در نظر گرفتن اين فرض که در مسائل بهينه سازي هدف يافتن مينيمم سراسري و حل مسئله مينيمم سازي است ، NCBPEتوسط معادله ي (٣) نرمال ميشود.در معادله ي (٣) ، CBPEminو CBPEmax به ترتيب بهترين و بدترين جوابهايي هستند که تا کنون بدست آمده اند . معادلات (٥,٤) نيز نحوه ي محاسبه ي ميزان نزديکي بدترين قورباغه به بهترين قورباغه ي محلي و يا سراسري را ارزيابي مي کند.
شکل ٢. فلوچارت الگوريتم FSFLA
چون C ضريب شـتاب بـراي افـزايش جسـتجوي محلـي حـول بهترين محلي و يـا سراسـري اسـت ، بنـابراين کـاهش آن باعـث افزايش جستجوي سراسري و افزايش آن باعث افزايش جستجوي محلي ميشود[١٤]. در نتيجه در اين تابع ، C نموداري صـعودي خواهد بود تا رفته رفته از ميزان جستجوي سراسري کـم شـده و جسـتجوي محلـي افـزايش يابـد . بـه عبـارتي در ابتـدا عمـل exploitation انجام دهد و کل محيط را خوب جستجو کند و در ادامه exploration کند و اطلاعات لازم را از آنچه جستجو کـرده است استخراج کند. قوانين ارائه شده در جدول ١ نيز بر اين اصل استوار است . مقادير متغير اين سيسـتم فـازي بـا مجموعـه هـاي فازي low و medium و high تعريف ميشـوند. نحـوه ي تنظـيم اين قوانين به اين شکل است که هر اندازه که d کم و NCBPE کم باشد C بزرگتر گرفته شود. دليل آن نيز ايـن اسـت کـه dکم نشان دهنده ي نزديکي بدترين قورباغه به بهتـرين قورباغـه ي محلي و يا سراسري است و NCBPE کم نيز بيانگر اين است کـه جواب حاصل کارايي لازم را دارد بنابراين لازم نيست از مـوقعيتي که در آن قرار گرفته دور شود پس C بايد بزرگ انتخـاب شـود.
براي مثال قانون اول d کم و NCBPE نيز کم است و اين نشان دهنده ي اين است که قورباغه در شرايط خوبي است بنابراين C
