پایان نامه ها

دانلود پایان نامه با موضوع الگوريتم، كروموزوم، جمعيت

بقيه اعضا بيشتر ميباشد.

شکل (‏215): روش انتخاب چرخ گردان

روش رتبه بندي85
در روش چرخ گردان اگر برازندگي يک کروموزوم از بقيه کروموزوم هاي آن نسل خيلي بيشتر باشد بخش زيادي از محيط چرخ را به خود اختصاص ميدهد و در نتيجه احتمال بسيار بالايي جهت انتخاب شدن خواهد داشت و اگر آن کروموزوم نقطه بهينه محلي باشد آن گاه الگوريتم با سرعت نسبتاً زيادي به سمت آن نقطه بهينه محلي همگرا ميشود. در روش رتبهبندي ابتدا جمعيت هر نسل رتبه بندي ميشود و اين رتبهبندي از کمترين برازندگي آغاز ميشود به طوري كه کروموزوم با بدترين برازندگي رتبه يک و به همين ترتيب مورد بعدي دو و الي آخر رتبه بندي صورت ميگيرد و در واقع برازندگي هر كروموزوم برابر با رتبه آن كروموزوم ميباشد. سرعت همگرايي در اين روش پايين است.

روش مسابقه اي86
در اين روش يک زير مجموعه کوچک از کروموزومها که معمولاً دو يا سه تا از آنها ميباشند، به صورت تصادفي از جمعيت آن نسل انتخاب ميشوند و بين آنها جهت برگزيده شدن به عنوان کروموزوم والد رقابت صورت ميگيرد. در اين ميان کروموزومي که از برازندگي بهتري برخوردار باشد انتخاب خواهد شد. رقابت تا زمان پر شدن استخر توليد مثل87 ادامه مييابد. اين روش در مواردي که جمعيت نسل زياد باشد به عنوان بهترين روش توصيه مي شود. البته اين روش نيزداراي ضعفهايي است که جهت پوشاندن آنها از مفاهيم ديگري مانند نخبهگزيني88 براي بقاي بهترين افراد هر جمعيت براي همگرا شدن الگوريتم به جواب بهينه استفاده ميشود.

نخبه گزيني
بهترين كروموزوم هر نسل يا چند كروموزوم بهتر هر نسل در نسل بعدي تكرار ميشوند. چنين كروموزومهايي در صورتي كه براي توليد مثل انتخاب نشوند ممكن است از دست بروند يا اينكه توسط عملگرهاي تقاطع يا جهش دچار آسيب شوند. نخبهگزيني عملكرد الگوريتم ژنتيك را تا حدود زيادي بهبود ميبخشد.
توليد مثل89
الگوريتم پس از انتخاب يك جمعيت اوليه وارد مرحله توليد مثل (تقاطع90) مي‌شود. پس از اتمام مرحله انتخاب، جمعيتي از رشتههاي با برازندگي بالا وجود خواهد داشت. عمل انتخاب مجموعهاي از بهترين رشتهها را فراهم ميكند ولي رشتهي (كروموزوم) جديدي به وجود نميآورد. اين عملگر بر اساس فرايند تركيب كروموزومها در طول توليد مثل در موجودات زنده شبيهسازي شده است. توسط عملگر تقاطع دو والد با يكديگر تركيب شده و دو فرزند ايجاد ميكنند كه هر يك از اين فرزندان بخشي از خصوصيات خود را از كروموزوم پدر و بخشي ديگر را از كزوموزوم مادر به ارث بردهاند ‏[46].

تقاطع تك نقطهاي
در اين روش يک نقطه تصادفي در دو کروموزوم والد انتخاب ميشود. از اين نقطه والدين به دو بخش شكسته ميشوند و با تعويض بخشهاي بعد از نقطه شکستگي دو کروموزوم جديد توليد ميشود كه کروموزومهاي نسل بعد يا فرزندان ميباشند. در شکل (‏216) نحوه انجام اين تقاطع تك نقطهاي نشان داده شده است.

شکل (‏216): تقاطع تكنقطهاي

تقاطع دو نقطهاي
در اين روش كروموزومهاي والد در دو نقطه تصادفي در طول آنها شكسته ميشوند و بخش موجود بين اين دو نقطه، بين دو والد مبادله ميشود. در شکل (‏217) روش تقاطع دونقطهاي نمايش داده شده است.

شکل (‏217): تقاطع دونقطهاي

در تقاطع تك نقطهاي هر كروموزوم والد از يك نقطه شكسته شده و دو نيمه به وجود آمده با هم ادغام ميشوند تا فرزندان را به وجود آورند. در صورتي كه هر دو نيمه يك كروموزوم والد داراي اطلاعات ژنتيكي خوبي باشند هيچ يك از دو فرزند به وجود آمده به طور كامل از اين اطلاعات ژنتيكي بهره نخواهند برد. در اين حالت با استفاده از تركيب دو نقطهاي مي توان اين مشكل را برطرف نمود. اين مشكل در مورد ساير موقعيتهاي روي كروموزوم نيز صدق ميكند. با استفاده از تقاطع چند نقطهاي ميتوان اين عيب را رفع نمود.
تقاطع چند نقطهاي
هنگامي که طول کروموزومها بزرگ باشد تقاطع تک نقطهاي نميتواند به خوبي به جستجوي فضاي طراحي بپردازد . به همين دليل از روش تقاطع چند نقطهاي استفاده ميشود . در اين روش چند نقطه به صورت تصادفي روي كروموزومهاي والد انتخاب ميشوند و ژنهاي کروموزومها در ميان اين نقاط انتخاب شده به صورت يک در ميان جابجا خواهند شد.
تقاطع يكنواخت
اين روش حالت توسعه يافتهي تقاطع چند نقطهاي است. در اين روش براي ايجاد کروموزوم فرزند، کروموزومي تصافي به طول برابر با کروموزومهاي والد توليد ميشود به اين كروموزوم تصادفي ماسك91 گفته ميشود. در هر بيت از ماسك اگر عدد يك ظاهر شود ژن از والد اول در فرزند اول كپي ميشود و هر جايي از ماسك كه عدد صفر ظاهر شود ژن از والد دوم در فرزند اول كپي ميشود. در مورد فرزند دوم اين قضيه برعكس ميباشد يعني عدد يك در ماسك به اين معني است كه فرزند دوم ويژگي خود را از والد دوم ميگيرد و در صورتي كه عدد صفر ظاهر شود ويژگي خود را از والد اول ميگيرد. در شکل (‏218) نحوه انجام تقاطع يكنواخت نشان داده شده است.

مطلب مشابه :  منابع پایان نامه ارشد با موضوعارتکاب جرم، قانون مجازات، معاونت در جرم

شکل (‏218): تقاطع يكنواخت

جهش92
بعد از تقاطع، كرموزوم ها در معرض جهش قرار ميگيرند. جهش پديدهاي است که در الگوريتم ژنتيک به تغيير ناگهاني ژن گفته ميشود. اين عملگر اميد احياي کروموزوم هاي خوبي را که در مراحل انتخاب يا توليد مثل حذف شدهاند ، زنده ميکند و نيز تضمين مينمايد که جستجو در تمام فضاي طراحي صورت ميپذيرد. جهش از گير افتاندن الگوريتم در نقاط بهي
نه محلي جلوگيري ميكند و نيز تنوع ژنتيكي را در جمعيت حفظ ميكند. نحوه اعمال عملگر جهش به طور کامل وابسته به نوع کدگذاري مسئله ميباشد. براي کدگذاري دودويي جهش ميتواند شامل تغيير مقدار هر ژن از صفر به يک و يا از يک به صفر با يك احتمال كوچك باشد ‏[46].
وارون كردن93
وارون كردن شامل تغيير دادن يك ژن از 0 به 1 و 1 به 0 بر اساس يك كرموزوم جهش تصادفي ميباشد. شکل (‏219) مفهوم وارون كردن را بيان ميكند. يك والد در نظر گرفته ميشود و يك كروموزوم جهش به صورت تصادفي ايجاد ميشود. براي هر عدد 1 موجود در كروموزوم جهش، ژن موجود در والد تغيير ميكند (از 1 به 0 و از 0 به 1) و كروموزوم فرزند توليد ميشود. در مثال ارايه شده در شکل (‏219) در سه نقطه از كروموزوم جهش، عدد 1 ظاهر شده است بنابراين در نقاط متناظر آن در كروموزوم والد تغيير صورت گرفته است.

شکل (‏219): جهش flipping

تبادل94
دو نقطه در كروموزوم به صورت تصادفي انتخاب ميشوند و مقادير آن ها با يكديگر تعويض ميشوند. در شکل (‏220) این روش تقاطع نشان داده شده است.

شکل (‏220): جهش به روش تبادل

معكوس كردن95
دو نقطه در كروموزوم به صورت تصادفي انتخاب ميشوند و مقادير آنها و مقادير ژنهاي بين آنها عكس ميشوند. در شکل (‏221) در كروموزوم والد بيتهاي اول و چهارم از سمت راست به تصادف جهت جهش انتخاب شدهاند بنابراين طبق اين روش مقادير بيت‌هاي بين آنها يعني بيت دوم و سوم تغيير خواهند كرد.

1 0 1 1 0 1 0 1
Parent
1 0 1 1 1 0 1 0
Child
شکل (‏221): جهش به روش عكس كردن

تابع هدف96 و تابع برازندگي
تابع برازندگي با اعمال تغيير مناسب بر روي تابع هدف يعني تابعي كه قرار است بهينه شود بدست مي‌آيد. اين تابع هر رشته را با يك مقدار عددي ارزيابي مي‌كند كه كيفيت آن را مشخص مي‌كند. تابع هدف براي فراهم آوردن مقياسي از عملكرد كروموزومها در بازه مسئله به كار ميرود. در يك مسئله كمينهسازي، كروموزومهايي بيشترين برازندگي را خواهند داشت كه كمترين مقدار را در ارتباط با تابع هدف مسئله داشته باشند.
به عنوان مثال براي بيان برازندگي ميتوان از روش پيشنهاد شده توسط بيكر97 نام برد كه از توليد تعداد بسيار زياد فرزند توسط يك كروموزوم در نسل بعد و نيز همگرا شدن سريع الگوريتم ژنتيك جلوگيري ميكند. در اين روش برازندگي كروموزومها بر اساس رتبه آنها در جمعيت تعيين مي‌شود. يك متغير SP به عنوان باياس يا فشار به سمت بهترين كروموزوم انتخاب ميشود و برازندگي كروموزومها به صورت زير محاسبه ميشود:
(‏26)

مطلب مشابه :  پایان نامه درموردمواد مخدر، انقلاب اسلامی، مجازات اعدام، مبارزه با مواد مخدر

F(x_i )=2-SP+2(SP-1)(x_i-1)/(N-1)

كه در آن x_i موقعيت يك كروموزوم در يك جمعيت مرتب شده ميباشد. براي مثال براي اندازه جمعيت N=40 و فشار انتخابي SP=1.1، برازندگي كروموزومها در بازه [1.1-0.9] خواهد بود. بهترين عضو جمعيت مقدار برازندگي 1.1 و بدترين عضو جمعيت مقدار برازندگي 0.9 را خواهند داشت ‏[46].
پارامترهاي الگوريتم ژنتيك
علاوه بر عملگرهاي ذكر شده در بالا، يك الگوريتم ژنتيک داراي يک سري پارامترهايي است که انتخاب مقدار مناسب آنها موجب رسيدن الگوريتم به يک جواب مناسب و يا تغيير در سرعت اجراي الگوريتم ميشود. اين پارامترها شامل نوع الگوريتم ژنتيک، اندازه جمعيت اوليه، نرخ توليد مثل، نرخ جهش و شرط پايان يافتن الگوريتم ميباشند.
ميزان جمعيت اوليه تاثير بسيار زيادي در نحوه رسيدن به جواب مسئله و روند اجرايي الگوريتم دارد. همچنين مقدار مناسب جمعيت اوليه خود متاثر از ميزان بزرگي فضاي طراحي ميباشد و از طرفي ديگر ميزان اين پارامتر ميتواند ديد کلي براي تعيين مقادير نرخ توليد مثل و جهش را ايجاد كند. يک جمعيت اوليه کوچک باعث سرعت همگرايي بالاتري براي الگوريتم ميشود و ارزيابي سريعتر برازندگي کروموزومهاي يک نسل را در پي دارد اما ميتواند موجب رسيدن به يک نقطه بهينه محلي در بهينهسازي شود در واقع کاهش دقت جواب نهايي را در پي خواهد داشت.
احتمال تقاطع (Pc) نشان ميدهد که چند درصد از جمعيت نسل بعدي از طريق تقاطع ايجاد شوند. در صورتي كه هيچ گونه تقاطعي صورت نگيرد فرزندان دقيقاً شبيه والدين خود خواهند بود. تقاطع به اين اميد انجام ميشود كه كروموزومهاي نسل بعد بخشهاي خوب كروموزومهاي نسل قديمي را خواهند گرفت تا فرزندان بهتري ايجاد شود. مقدار زياد براي اين پارامتر موجب ميشود که الگوريتم ديرتر به يک نقطه همگرا شود و زمان اجراي برنامه را افزايش ميدهد و از طرفي امکان اينکه اين نقطه يک نقطه بهينه محلي باشد نيز وجود دارد.
احتمال جهش (Pm) تعيين ميكند كه در هر كروموزوم چه تعدادي از بيتها دچار جهش شوند. اگر هيچ گونه جهشي صورت نگيرد فرزندان بعد از عمليات تقاطع بدون تغيير وارد نسل جديد ميشوند. اما در صورتي كه جهش صورت گيرد قسمتهايي از كروموزوم تغيير خواهد كرد. احتمال جهش مقداري كوچك ميباشد (در حدود 0.5%). در صورتي كه جهش صورت گيرد يك يا چند بيت از كروموزوم دچار تغيير (جهش) خواهد شد. بايد توجه داشت كه نبايد اين مقدار خيلي زياد در نظر گرفته شود زيرا در اين صورت الگوريتم ژنتيك تبديل به يك جستجوگر تصادفي ساده ميگردد و از سرعت آن به نحو قابل توجهي كاسته ميشود. اگرچه اين عمل باعث ميشود که فضاي طراحي مسئله به خوبي جستجو شود. عملگر جهش و نرخ آن ابزار الگوريتم ژنتيک براي گريز از نقطه بهينه محلي ميباشند تا اينکه الگوريتم بتواند به نقطه بهينه کلي مسئله برسد و اين يكي از مزاياي الگوريتم ژنتيک در براب
ر روشهاي سنتي جستجو ميباشد. به عنوان مثال مسئلهاي را در نظر بگيريد كه فضاي جواب آن مطابق شکل (‏222) باشد. در چنين مواقعي اگر ميزان پارامترهاي نرخ جهش و نرخ تقاطع مناسب در نظر گرفته نشوند رسيدن به جواب بهينه كلي عملاً غيرممكن بوده يا اينكه الگوريتم بسيار دير به جواب بهينه كلي همگرا خواهد شد.

شکل (‏222): نقاط بهينه محلي و کلي در يک فضاي طراحي

پارامتر ديگر شرط پايان الگوريتم ژنتيک ميباشد. براي اينکه الگوريتم ژنتيک متوقف شود بايد مشخص شود که الگوريتم به نقطه بهينه کلي رسيده است. دو روش رايج براي پايان دادن به الگوريتم وجود دارد. يکي اينکه تعداد نسلهاي توليد شده به يک ميزان خاصي برسد که در روند بهبود نقطه بهينه در نسلها، هيچ تغييري در ايجاد نقطه بهينه جديد ديده نشود و ديگر اينکه درصد معيني از کروموزومهاي جمعيت يک نسل مشابه يکديگر شده

دیدگاهتان را بنویسید