بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
طراحي بهينه سيستم فازي با الگوريتم ژنتيک مرتب سازي نامغلوب دو
خلاصه
با توجه به وجود مسائل چند هدفه در زندگي واقعي، مسئله بهينه سازي چند هدفه مورد توجه بسياري از پژوهشگران قرار گرفته است . در بهينه سازي چند هدفه ، مجموعه اي از راه حل هاي مختلف به دست مي آيد که مجموعه بهينه پارتو ناميده مي شود. يکي از روش هايي که در ٢٠ سال اخير تحقيقات زيادي را به خود جلب کرده است ، استفاده از الگوريتم هاي تکاملي است که مي توانند مجموعه بهينه پارتو را در يک اجرا به دست آورند.
انعطاف پذيري سيستم هاي فازي باعث مي شود تا آن ها در دامنه گسترده اي از مسائل قابل اجرا شوند. از بين آن ها مسائل با چندين هدف متضاد براي محققين جالب تر است . در اين نوع از مسائل هيچ راه حلي وجود ندارد که به طور همزمان همه اهداف را بهينه کند. اين مسائل با استفاده از الگوريتم هاي تکاملي چند هدفه به طراحي سيستم هاي فازي ميپردازند. در اين مقاله قصد داريم تا به بهينه سازي سيستم فازي با استفاده از الگوريتم ژنتيک مرتب سازي نامغلوب دو بپردازيم . در اين روش پيشنهادي سيستم فازي دقيق تر و با خطاي کمتري نسبت به روش الگوريتم ژنتيک ساده خواهيم داشت .
کلمات کليدي: الگوريتم ژنتيک مرتب سازي نامغلوب دو، سيستم فازي
.1 مقدمه
الگوريتم هاي تکاملي با موفقيت براي حل مسائل با دو تابع هدف يا بيشتر در طول ٢٠ سال اخير استفاده شده اند. اين حوزه "بهينه سازي چند هدفه تکاملي " ناميده مي شود و از زمينه هاي تحقيقاتي بسيار فعال است که مورد توجه بسياري از محققان قرار گرفته است . در اولين رويکرد عملي براي بهينه سازي چندهدفه با استفاده از الگوريتم تکاملي، VEEA توسط Schaffer ارائه شد. همچنين انواع ديگري از الگوريتم هاي تکاملي وجود داشتند که تلاش ميکردند تا چندين جواب نامغلوب را توليد کنند. هيچ يک از اين الگوريتم ها به طور مستقيم از تعريف واقعي بهينگي پارتو استفاده نمي کنند. مفهوم پارتو بر اساس تخصيص شايستگي، اولين بار توسط Goldberg در ١٩٨٩ ارائه شد و به اين معني است که براي تمام افراد نامغلوب در جمعيت احتمال يکسان براي توليد مثل اختصاص مي دهد. Fonseca و Fleming در ١٩٩٣ الگوريتم ژنتيک چندهدفه (MOGA) را ارائه دادند. در ١٩٩٤ Horn et al با استفاده از روش انتخاب تورنمنت مبتني بر پارتو مغلوب شده NPGA را معرفي کرد.
Srinivas و Deb در سال ١٩٩٥ الگوريتم NSGA را ارائه دادند که بر اساس رتبه بندي پارتو نسخه Goldberg مي باشد. الگوريتم NSGA II در سال ٢٠٠٢ توسط Deb و Goel معرفي شد.[١]
امروزه الگوريتم هاي تکاملي جايگزين بسيار مناسبي براي حل مسائل جستجوي پيچيده مثل بهينه سازي چندهدفه يا سراسري هستند.[٢] هرچند که مدل هاي تصميم گيري تک هدفه براي برخي مسائل تصميم گيري، کارآمد و موثر هستند ولي در بسياري از زمينه ها، تصميم گيري ها بر اساس بررسي چند هدف صورت مي گيرد که به آن ها بهينه سازي چندهدفه مي گويند. بهينه سازي چندهدفه يکي از زمينه هاي بسيار فعال و پرکاربرد تحقيقاتي در ميان مباحث بهينه سازي است و در شاخه هاي مختلف علوم پايه ، مهندسي و اقتصاد، روز به روز بيشتر مطرح مي شوند.
طراحي خودکار سيستم هاي فازي مي تواند به عنوان يک مسئله جستجو يا بهينه سازي در نظر گرفته شود. الگوريتم هاي تکاملي و الگوريتم هاي ژنتيک اين کار را انجام مي دهند و راه حل هاي نزديک به بهينه را بدون داشتن توصيف دقيق از مسئله پيدا مي کنند. بنابراين آن ها مي توانند به آساني دانش قبلي را در مدل بگنجانند. بهينه سازي چند هدفه منجر به توليد مجموعه اي از مدل هاي فازي با سطوح تبادل متفاوت بين چند هدف به جاي يک هدف ميشوند.
سپس ، تصميم گيرنده مي تواند با توجه به نيازهايش مناسبترين مدل را انتخاب کند.[٣]
٢. الگوريتم ژنتيک مرتب سازي نامغلوب دو
الگوريتم ژنتيک مرتب سازي نامغلوب ١، الگوريتم ژنتيک نامغلوب معروف براي بهينه سازي چند هدفه است . اين الگوريتم ، الگوريتم تاثير گذاري است اما به خاطرپيچيدگي محاسباتي، عدم نخبه گرايي و به دليل انتخاب مقدار پارامتر بهينه براي پارامتر اشتراکي δshare مورد انتقاد قرار گرفته است . نسخه توسعه يافته اين الگوريتم يعني الگوريتم ژنتيک مرتب سازي نامغلوب ٢، الگوريتم مرتب سازي بهتري دارد، نخبه گراست و به هيچ پارامتراشتراکي نياز ندارد تا از قبل مشخص شود. جمعيت مطابق معمول مقداردهي مي شود. جمعيت بر اساس عدم غلبه در هر جبهه مرتب مي شود. اولين جبهه ، مجموعه نامغلوب در جمعيت فعلي است و جبهه دوم تنها به وسيله جبهه اول مغلوب مي شود و جبهه ها ادامه دارد. براي هر فرد در هر جبهه ، رتبه بر اساس جبهه اي که متعلق به آن است ، مي باشد. افراد جبهه اول مقدار برازندگي يک و افراد جبهه دوم مقدار برازندگي دو دارند و غيره .
علاوه بر مقدار برازندگي يک پارامتر جديد به نام فاصله ازدحامي براي هر فرد محاسبه مي شود. فاصله ازدحامي ٢ معيار نزديکي هر فرد به همسايگانش است . والدين ، از جمعيت با استفاده از انتخاب تورنمنت بر اساس رتبه و فاصله ازدحامي انتخاب مي شوند. هر فرد که رتبه کمتري نسبت به ديگري دارد يا اگر فاصله ازدحامي بهتري از ديگري داشته باشد، انتخاب مي شود. سپس جمعيت انتخاب شده ، فرزندان را از عملگرهاي تقاطع ٣ و جهش 4 توليد مي کند. جمعيت که از جمعيت فعلي و فرزندان تشکيل شده است ، بر اساس عدم غلبه دوباره مرتب مي شود و تنها N تا از بهترين افراد انتخاب ميشوند که N اندازه جمعيت است . انتخاب بر اساس رتبه و فاصله ازدحامي روي جبهه فعلي است . فاصله ازدحامي تنها اگر رتبه براي هر دو فرد مشابه باشند، مقايسه مي شوند. شکل ١ شماي کلي از اين الگوريتم را نمايش مي دهد.
شکل ١ : شماي کلي الگوريتم ژنتيک مرتب سازي نامغلوب دو[٤]
٣. منطق فازي
منطق فازي براي اولين بار در سال ١٩٦٥ توسط لطفي زاده استاد ايراني الاصل دانشگاه برکلي کاليفرنيا بنا نهاده شد. منطق فازي نگرشي چند ارزشي به وقايع و رويدادها دارد در واقع منطق فازي بر اساس تئوري مجموعه هاي فازي بنا نهاده شد که در آن مجموعه فازي به عنوان مجموعه اي در نظر گرفته مي شود که داراي مرز غيرقطعي و نامشخص است و هر عضو داراي درجه عضويت نسبي است .[٥]
سيستم هاي فازي، "سيستم هاي مبتني بر دانش يا قواعد" هستند. قلب يک سيستم فازي يک پايگاه دانش بوده که از قواعد اگر - آنگاه فازي
تشکيل شده است . يک قاعده اگر ـ آنگاه فازي، يک عبارت اگر ـ آنگاه است که بعضي کلمات آن به وسيله توابع تعلق پيوسته مشخص شده اند.
در کتب و مقالات معمولاً از سه نوع سيستم فازي صحبت به ميان مي آيد:
١) سيستم هاي فازي خالص
٢) سيستم هاي فازي تاکاگي-سوگنو و کانگ
٣) سيستم هاي با فازي ساز و غيرفازي ساز
مشکل اصلي در رابطه با سيستم هاي فازي خالص اين است که ورودي ها و خروجي هاي آن مجموعه هاي فازي مي باشند (واژه هايي در زبان طبيعي). در حالي که در سيستم هاي مهندسي، ورودي ها و خروجي ها متغيرهايي با مقادير حقيقي مي باشند. براي حل اين مشکل ، تاکاگي-سوگنو و کانگ نوع ديگري از سيستم هاي فازي معرفي کرده اند که ورودي ها و خروجي هاي آن متغيرهايي با مقادير واقعي هستند. سيستم تاکاگي- سوگنو به جاي استفاده از قواعدي به صورت عبارت توصيفي با مقادير زباني در سيستم هاي فازي خالص ، از يک رابطه رياضي ساده براي بخش آنگاه قاعده فازي استفاده مي کند. اين تغيير، ترکيب قواعد فازي را ساده تر مي سازد اما بخش آنگاه قاعده ، يک فرمول رياضي بوده و بنابراين چهارچوبي را براي نمايش دانش بشري فراهم نمي کند و اين سيستم امکان اعمال اصول مختلف منطق فازي را فراهم نمي کند و در نتيجه انعطاف پذيري سيستم هاي فازي در اين ساختار وجود ندارد. براي رفع اين مشکل از سيستم هاي فازي با فازي سازها و غير فازي سازها استفاده مي کنيم . ساختار کلي اين نوع سيستم ها در شکل ٢ نمايش داده شده است .
شکل ٢ : ساختار کلي از سيستم هاي فازي با فازي ساز و غير فازي ساز[٦]
دو روش براي مدل سازي سيستم هاي فازي با فازي ساز و غيرفازي ساز وجود دارد: روش ممداني [٧] و روش تاکاگي- سوگنو - کانگ که به طورخلاصه روش سوگنو١ ناميده مي شود. تفاوت اين دو روش در قسمت "نتيجه " ديده مي شود که در روش ممداني، نتيجه يک قضيه و در روش تاکاگي سوگنو تابعي خطي مي باشد.
٤. الگوريتم پيشنهادي
قبل از طراحي بهينه سيستم فازي با الگوريتم ژنتيک مرتب سازي نامغلوب دو، سيستم سينيماتيک معکوس ٢ را که سيستم فازي مورد استفاده است ، معرفي ميکنيم . به منظور درک سيستم سينيماتيک معکوس فرض کنيد که يک ربات همانند شکل ٣ با دو بازوي متحرک به طول L2.L1 داشته باشيم که در مختصات x,y ساکن ميباشد و موتور حرکتي بازوي اول آن در نقطه (٠,٠) قرار دارد. اين ربات براي اينکه به نقطه (x,y) برسد، مطابق شکل بايد يک بار بازوي به طول L1 را با زاويه حرکت دهد و سپس بازوي به طول L2 را با زاويه حرکت دهد تا به شي موردنظر دستيابي پيدا کند. ما با داشتن L و مي توانيم به راحتي به موقعيت شي پي ببريم که به اين فرايند سينماتيک مستقيم مي گويند.
شکل ٣: ربات با دو بازو به طول l2 , l1
در اين روش براي به دست آوردن مختصات انتهايي به صورت زير عمل مي کنيم :
اما اگر مختصات موقعيت شي موردنظر را داشته باشيم و از ربات بخواهيم تا به سمت آن شي برود، آنگاه يافتن زواياي مشکل است و يافتن راه حل دقيق با افزايش تعداد مفاصل ربات مشکل مي شود. اين روش همان سينماتيک معکوس است که در اين صورت طبق زير عمل مي کنيم :
١. ابتدا تعدادي زاويه توليد مي کنيم و طبق سيستم سينماتيک مستقيم اين زوايا را به عنوان ورودي به سيستم داده و تعدادي موقعيت به دست مي آوريم . شکل ٤ اين حالت را نمايش مي دهد.
شکل ٤ : سينماتيک مستقيم
٢. حال براي حل سينماتيک معکوس ، (x,y) را به عنوان ورودي سيستم درنظر گرفته و به دنبال سيستم سينماتيک معکوس مي گرديم که بتواند با توجه مسير داده شده ، تخميني از را بدون استفاده از هيچ عبارت رياضي به ما بدهد. شکل ٥ سينماتيک معکوس را نشان مي دهد.
حال پس از درک سيستم فازي مورد نظر مراحل الگوريتم پيشنهادي را به صورت زير توضيح مي دهيم .
٤-١- تنظيم پارامترها
در اين الگوريتم دو دسته پارامتر وجود دارد. دسته اول پارامترهاي مربوط به الگوريتم ژنتيک مرتب سازي نامغلوب دو است و دسته دوم مربوط به سيستم فازي ميباشد. پارامترهاي الگوريتم ژنتيک مرتب سازي نامغلوب دو شامل اندازه جمعيت ، شرط پايان الگوريتم ، درصد ترکيب و درصد جهش مي باشد .
پارامترهاي مربوط به سيستم فازي شامل تعداد قوانين ، تعداد ورودي ها، تعداد خروجي ها و ضريب هر قانون ميباشد. تنظيم اين پارامترها وابسته به سيستم فازي موردنظر مي باشد و بسته به آن مقدار اين پارامترها نيز تغيير مي کند.
٤-٢- توليد داده هاي آموزشي
براي توليد داده ورودي، مطابق مطالب ارائه شده در مورد سينماتيک معکوس ، ابتدا طبق سينماتيک مستقيم عمل مي کنيم تا تعدادي x و y پيدا کنيم . براي اين منظور فرض مي کنيم که رباتي مانند شکل ٣ داريم . در اين صورت در بازه (٠,٩٠) و с در بازه (٠,١٨٠) قرار دارد و با فرض اينکه طول بازوي اول برابر شش و طول بازوي دوم برابر با ١٠ باشد، مقدار x,y مطابق فرمول ١ و ٢ به دست آمده و به عنوان داده ورودي است .در اين الگوريتم به جاي اينکه کل داده ها را به عنوان ورودي در نظر بگيريم ، نيمي از داده ها را به عنوان داده آموزشي و نيمي از آن را به عنوان داده تست در نظر ميگيريم .
٤-٣- توليد سيستم فازي خام
براي توليد سيستم فازي پايه ، با استفاده از داده هاي ورودي و خروجي آموزشي توليد شده ، سيستم فازي سينماتيک معکوس توليد مي کنيم که براي توليد اين سيستم فازي از تابع genfisموجود در متلب استفاده مي کنيم . ما در اين الگوريتم از سيستم فازي ممداني استفاده ميکنيم .
در اين قسمت پس از آماده شدن سيستم فازي، براي بهينه کردن اين سيستم فازي از الگوريتم ژنتيک مرتب سازي نامغلوب دو استفاده مي کنيم .
