پایان نامه با کلید واژگان الگوريتم، مي‌شود.، تغيير

مرحله انتخاب يك عضو و برگزيده مي‌شود و روند آنقدر تكرار مي‌شود تا به اندازه كافي، جفت براي تشكيل نسل بعد انتخاب گردد. اين روش انتخاب را مي‌توان به صورت زير بيان كرد:
برداي مانند V در نظر بگيريد:
M تعداد عناصر بردار است اگر تعداد اعضاي مجموعه N باشد، هر عضو i= 1,…N داراي تطابقي مانند مي‌باشد. هر عضو i به نسبت ، بار در v تكرار مي‌شود. هر چه بيشتر باشد، عضو مكان‌هاي بيشتري را به خود اختصاص مي‌د‌هد. بعد از تشكيل بردار v يك مقدار تصادفي انتخاب مي‌شود. اين مقدار به مكاني در بردار اشاره مي‌كند كه آن مكان خود معرّف عضوي از اعضاي جمعيت است، به عنوان مثال اگر جمعيتي با N=4 داشته باشيم و تطابق اعضا عبارت باشد از:
مقدار مجموع تطابق‌ها عبارت است از:
بردار v را برداري با 60 عنصر در نظر مي‌گيريم. اين بردار به صورت زير پر مي‌شود. به عضو 1، 10 مكان، به عضو 2، 10 مكان، به عضو 3، 15مکان و به عضو 4، 25 مكان اختصاص مي‌يابد.
حالا r بين 1 تا 60 به تصادف انتخاب مي‌شود. فرض كنيد r=32 نتيجه مي‌شود:
پس عضو 3 انتخاب مي شود.
7-2-1-5-3) ترکيب
در طبيعت بقاي نسل يکي از مهمترين فاکتورهاست و تنها عملگر ممکن براي اين امر آميزش است. در الگوريتم‌هاي ژنتيکي نيز آميزش وجود دارد. آميزش با تعويض ژن‌ها، بين دو کروموزوم انجام مي‌گردد و هر کدام از کروموزوم‌ها خصوصياتي از خود را به فرزندان انتقال مي‌دهند. بديهي است کروموزوم‌هايي که داراي برازندگي بيشتري هستند شانس بيشتري براي آميزش دارند.
مهمترين عملگر در الگوريتم ژنتيک، عملگر ترکيب است. ترکيب، فرآيندي است که در آن نسل قديمي کروموزوم‌ها با يکديگر مخلوط و ترکيب مي‌شوند تا نسل تازه‌اي از کروموزوم‌ها بوجود بيايد.
جفت‌هايي که در قسمت انتخاب، به عنوان والد در نظر گرفته شدند، در اين قسمت ژن‌هايشان را با هم مبادله مي‌کنند و اعضايي جديد بوجود مي‌آورند.
نکته مهم اين جاست که ترکيب اعضا با تطابق بالا باعث بوجود آمدن اعضايي مي‌شود که از تطابق ميانگين، تطابق بيشتري دارند. ترکيب در الگوريتم ژنتيک باعث از بين رفتن پراکندگي يا تنوع ژنتيکي جمعيت مي‌شود، زيرا اجازه مي‌دهد ژن‌هاي خوب يکديگر را بيايند.
انواع روش‌هاي ترکيب:
جابجايي دودويي73
جابه‌جايي حقيقي74
ترکيب تک‌نقطه‌اي
ترکيب دو نقطه‌اي.
ترکيب n نقطه‌اي
ترکيب يکنواخت
ترکيب حسابي
ترتيب
چرخه
محدب و …
جابه‌جايي دودوئي
روش‌هاي معمول جابجايي تک نقطه75، دو نقطه76 و جابجايي يکنواخت77 مي‌باشد. ساده‌ترين جابجا کردن، جابجايي تک نقطه‌اي است. در جابجايي تک نقطه‌اي، ابتدا جفت کروموزوم والد (رشته دودوئي) در نقطه مناسبي در طول رشته بريده شده و سپس قسمت‌هايي از نقطه برش، با هم عوض مي‌شوند، بدين ترتيب دو کروموزوم جديد به دست مي‌آيد که هر نقطه از آن ژن‌هايي را از کروموزوم‌هاي الد به ارث مي‌برند.
براي جابجايي چند نقطه‌اي78 ، m موقعيت جابجا شدن، که نقطه جابجايي و طول کروموزوم مي‌باشد را به صورت تصادفي و بدون تکرار انتخاب مي‌کنيم، سپس جهت ايجاد فرزندي جديد بيت‌هاي بين نقاط مشخص شده در والدين با هم عوض مي‌شوند. فلسفه انجام جابجايي اين است که قسمت‌هايي از کروموزوم که بيان کننده سهم بسزايي در عملکرد بهتر يک عضو خاص هستند ممکن است در زير رشته‌هاي همسايه يافت نشوند.
در كد گذاري حقيقي كه كروموزوم‌ها به صورت برداري از اعداد حقيقي مي‌باشند روش‌هاي زيادي براي عملگر جابه‌جايي حقيقي ارائه شده كه اكثر آنها در دو دسته زير خلاصه مي‌شود:
جابه‌جايي عمومي
جابه‌جايي محاسباتي
8-2-1-5-3) جهش79
جهش باعث جستجو در فضاهاي دست نخورده مسأله مي‌شود مي‌توان استنباط كرد كه مهمترين وظيفه جهش اجتناب از همگرايي به بهينه محلّي است.
در الگوريتم ژنتيك نيز بعد از اينكه يك عضو در جمعيت جديد به وجود آمد، هر ژن آن با احتمال جهش80 ، جهش مي‌يابد. در جهش ممكن است ژني از مجموعه ژن‌هاي جمعيت حذف شود يا ژني كه تا حال در جمعيت وجود نداشته است به آن اضافه شود. جهش يك ژن به معناي تغيير آن ژن است و وابسته به نوع كدگذاري، روش‌هاي متفاوت جهش استفاده مي‌شود.
اگر مرحله جهش صورت نگيرد، فرزندان بلافاصله بعد از ترکيب و بدون هيچ تغييري بوجود مي‌آيند (يا مستقيماً نسخه برداري مي‌شوند که در نتيجه عمل ترکيب هم صورت نگرفته است). اگر تغيير صورت بگيرد، يک يا بيش از يک قسمت از کروموزوم تغيير مي‌کند. اگر احتمال تغيير 100% باشد، يعني همه کروموزوم‌هاي تغيير کرده‌اند و اگر 0% باشد، هيچ تغيير نکرده است.
به طور کلي جهش از قرار گرفتن الگوريتم ژنتيک در اکسترمم‌هاي محلي جلوگيري مي‌کند. جهش نبايد زياد صورت بگيرد زيرا در اين صورت الگوريتم ژنتيک به جستوي کاملا تصادفي تبديل خواهد شد.
همانطور كه گفته شد، هر عضو، وابسته به احتمال جهش، جهش مي‌يابد. احتمال جهش() مقداري است كه توسط كاربر تعيين مي‌شود. در الگوريتم استاندارد ژنتيك بنا به دلايلي مقدار اين پارامتر، بسيار كوچك، مثل يا حتي در نظر گرفته مي‌شود. اما از آنجا كه كمتر از شكل استاندارد اين الگوريتم استفاده مي‌شود، به عنوان يك پيشنهاد مي‌توان را به صورت زير تخمين زد:
كه N تعداد ژن‌هاي كروموزوم است.
در هر حال بين 0 و 1 است و معمولاً عددي كوچك انتخاب مي‌شود در فرزندي كه بوجود آمده است (توسط تركيب)، به ترتيب مقداري تصادفي بين 0 و 1 به هر ژن اختصاص مي‌يابد. اگر اين مقدار اختصاص داده شده از كمتر باشد، ژن جهش مي‌يابد و اگر بيشتر باشد ژن تغيير نمي‌كند. نرخ بالاي جهش، باعث تنوع و پراكندگي ژنتيكي در جمعيت مي‌شود كه اين پراكنندگي ممكن است همگرايي را به تأخير بيندازد. به همين دليل پيشنهاد مي‌شود براي جمعيت‌هاي بزرگ يا در نسل‌هاي آخر از هاي كوچكتر و براي جمعيت‌هاي كوچك يا در نسل‌هاي ابتدايي از هاي بزرگتر استفاده شود.
انواع جهش عبارتند از:
جهش باينري81
جهش حقيقي82
وارونه سازي بيت
تغيير ترتيب قرارگيري
وارون سازي
تغيير مقدار
1-8-2-1-5-3) جهش باينري:
در الگوريتم ژنتيك با كد گذاري باينري، اين عملگر اغلب با توليد تصادفي يكي از اعداد 0 و1 جايگزيني آن به جاي بيت مورد نظر صورت مي‌گيرد، اما در برخي كاربردهاي ژنتيك عمل جهش دودوئي در يك بيت با متمم ساختن آن بيت انجام مي‌شود. به اين صورت كه اگر بيت مورد نظر 0 بوده به بيت 1 و بر عكس تبديل خواهد شد، كه آزمايش‌ها نشان داده شده است كه روش دوم مناسبتر است.
شکل 3-1 : جهش باينري در کروموزوم
2-8-2-1-5-3) جهش حقيقي
در كدگذاري حقيقي، عملگر جهش باعث توليد تصادفي يك مقدار جديد در يك موقعيت خاص در كروموزوم مي‌شود، در نتيج? اين تغييراتِ تصادفي در جمعيت كروموزوم‌ها، نواحي بيشتري از فضاي كاوش بررسي شده و از همگرايي بي‌موقع (ناگهاني محلّي) الگوريتم جلوگيري مي‌شود.
يك مثال از عملگر جهش حقيقي، جهش تصادفي يا يكنواخت مي‌باشد. با اين فرض كه يك كروموزوم و يك ژني باشد كه تحت عمل جهش قرار مي‌گيرد آنگاه يك مقدار انتخابي تصادفي جديد از محدوده مي باشد كه بجاي ژن در كروموزوم جديد جايگذاري خواهد شد.
مثال ديگري براي اين روش عملگر جهش مرزي كه در آن يكي از ژن‌هاي كروموزوم به طور تصادفي با حد پايين يا بالاي محدوده آن ژن جايگزين مي‌شود يا
3-8-2-1-5-3) وارونه سازي بيت
از اين نوع جهش هنگامي استفاده مي‌شود که کد گذاري، کد گذاري باينري باشد. در اينجا بيتي که شرايط جهش را دارد اگر 0 باشد به 1 و اگر 1 باشد به 0 تغيير مي‌دهد. به عنوان نمونه اگر در شکل ژن چهارم شرايط جهش را داشته باشد به صورت نشان داده شده، جهش مي‌يابد.
شکل 3-2 : وارونه سازي بيت
4-8-2-1-5-3) تغيير ترتيب قرارگيري
از اين نوع جهش مخصوصاً در الگوريتم‌هايي استفاده مي‌شود که کد گذاري بر اساس مقدار باشد البته در ديگر کد گذاري‌ها مثل کد گذاري باينري هم مي‌توان اين جهش را بکار برد. در اين جهش، محل قرارگيري دو ژني که مي‌خواهد جهش بيابند در کروموزوم تعويض مي‌شود.
شکل 3-3 : تغيير ترتيب قرارگيري
5-8-2-1-5-3) وارون سازي
اين عمل در طبيعت بسيار رخ مي‌دهد ولي در الگوريتم‌هاي ژنتيکي به ندرت استفاده مي‌شود و دليل آن ايجاد تخريب زياد است. اين عملگر کروموزوم را معکوس مي‌کند.
شکل 3-4: وارون سازي
6-8-2-1-5-3) تغيير مقدار
اين نوع جهش را نمي‌توان براي کدگذاري باينري يا کدگذاري‌هاي مشابه که امکان تغيير ژن‌ها وجود ندارد، به کار برد. در اين جهش به ژني که شرايط جهش را دارد مقداري اضافه يا کم مي‌شود. اضافه شدن و کم شدن مي‌تواند به تصادف انتخاب شود يا الگوريتم مقيد به استفاده از يکي از اين دو عمل باشد.
مقداري که به ژن افزوده يا از آن کاسته مي‌شود، وابسته به محدوده مقدار ژن است و باز مي‌تواند به تصادف انتخاب شود يا براي الگوريتم تعريف شود. بديهي است مقدارهاي بزرگ پراکندگي ژنتيکي را افزايش مي‌دهند. اين جهش خصوصاً براي کدگذاري‌هايي که در آنها، ژن‌ها به صورت اعداد حقيقي هستند مناسب است.
3-1-5-3) شرايط خاتمه براي الگوريتم ژنتيک
براي اينکه تشخيص دهيم چه موقع الگوريتم از اجرا متوقف شود، از شيوه‌هاي مختلفي مي‌توان استفاده کرد. به عنوان نمونه مي‌توان همگرا شدن کل جمعيت را در نظر گرفت و يا اينکه فاصله ارزيابي (برازندگي) بهترين فرد جمعيت از متوسط ارزيابي‌ها (برازندگي‌ها) را در نظر گرفت که در اين حالت بايد از حد مشخصي کوچکتر باشد، يا مقدار تابع هدف از حد مشخصي بيشتر باشد يا مي‌توان تعداد نسل‌هاي مشخصي را به عنوان محک اختتام در نظر گرفت:
1- به دست آوردن جواب نهايي مورد نظر بعد از چند تکرار کم و قابل قبول بودن جواب به ازاي خطاي خاص.
2- اگر با پيشروي الگوريتم هيچ نوع بهبودي مشاهده نشد خواه الگوريتم جواب دلخواه را پيدا کرده باشد و يا اينکه در مينيمم محلي گير کرده باشد.
3- اگر مقدار ميانگين تابع هدف به ازاي تعدادي تکرار به مقدار خاصي رسيده باشد.
4- الگوريتم به تعداد ثابتي از نسل‌ها رسيده باشد.
5- بيشترين درجه برازش فرزندان حاصل شود يا ديگر نتايج بهتري حاصل نشود.
6- بازرسي دستي.
7- ترکيب‌هايي از روش هاي بالا.
2-5-3) الگوريتم رقابت استعماري (ICA)
همانند ساير روش‌هاي بهينه‌سازي تکاملي، کار اين الگوريتم نيز با تعدادي جمعيت اوليه شروع مي‌شود. بطور خلاصه در اين الگوريتم، هر عنصر جمعيت، يک کشور ناميده مي‌شود. کشور‌ها به دو دسته مستعمره و استعمار‌گر تقسيم مي‌شوند. هر استعمارگر، بسته به قدرت خود، تعدادي از کشور‌هاي مستعمره را به سلطه خود درآورده و آن‌ها را کنترل مي‌کند. سياست جذب و رقابت استعماري، هسته اصلي اين الگوريتم را تشکيل مي‌دهند[1],[10].
1-2-5-3) شکل دهي امپراطوري‌هاي اوليه
همانطور که قبلا گفته شد، در بهينه‌سازي، هدف يافتن يک جواب بهينه بر حسب متغير‌هاي مسئله، است. ما يک آرايه از متغير‌هاي مسئله را که بايد بهينه‌ شوند، ايجاد مي‌کنيم. در الگوريتم ژنتيک اين آرايه، کروموزوم ناميده مي‌شود. در اينجا نيز آن را يک کشور مي‌ناميم. در يک مسئله‌ي بهينه‌سازي بعدي، يک کشور، يک آرايه‌ي است. اين آرايه به صورت زير تعريف مي‌شود.
مقادير متغيره‌ها در يک کشور، به صورت اعداد اعشاري نمايش داده مي‌شوند. از ديدگاه تاريخي‌ـ‌فرهنگي، اجزاي تشکيل دهنده يک کشور را مي‌توان ويژگي هاي اجتماعي- سياسي آن کشور، همچون فرهنگ، زبان، ساختار اقتصادي و ساير ويژگي‌ها در نظر گرفت. شکل 3-3 اين مسئله را به خوبي نشان مي‌دهد. مطابق اين شکل متغيرهاي مجهول تابع هزينه که ما در طي فرايند بهينه‌سازي به دنبال آنها مي‌گرديم، در نگاه اجتماعي‌ـ‌سياسي ويژگي‌هاي تاريخي و

Author: y7oozita

پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *