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

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

دی ۸, ۱۳۹۷ 0 By mitra1--javid

ر گرفته ميشوند که کروموزوم۷۰ ناميده ميشود. در واقع هر كروموزوم رشتهاي است كه حاوي اطلاعات مربوط به جواب مسئله ميباشد. به مجموعهاي از اين كروموزومها كه نشاندهنده يك مجموعه جواب مسئله ميباشند جمعيت۷۱ اطلاق ميشود. هر كروموزوم شامل تعدادي ژن۷۲ ميباشد كه هر يك از اين ژنها نشان دهنده يك ويژگي خاص از جواب مسئله مي باشند. هر ژن بسته به نوع کدگذاري۷۳ و دقت مورد نظر از تعدادي بيت يا آلل۷۴ تشكيل ميشود. در شکل (‏۲-۹) ساختار يك كرموزوم نمايش داده شده است كه از ۴ ژن تشكيل شده است و هر يك از اين ژنها نيز شامل ۴ بيت ميباشند ‏[۴۵].

شکل (‏۲-۹): نمايش ژن‌ها در يك كروموزوم

به طور کلي فلوچارت مربوط به بهينه سازي با روش الگوريتم ژنتيک به صورت شکل (۱۰-۲) مي‌باشد.

شکل (‏۲-۱۰): فلوچارت الگوريتم ژنتيك
با توجه به اين فلوچارت الگوريتم ژنتيك با يک جمعيت اوليه آغاز مي شود يعني در ابتداي کار يک سري جواب يا راه حل براي مسئله وجود دارد که به منظور رسيدن به جواب بهينه بايد اصلاح شوند. اين جمعيت اوليه در ابتداي امر به صورت کاملاً تصادفي تعيين ميشود. مرحله بعدي ارزيابي کروموزومها ميباشد يعني هر يک از اين جوابها به چه ميزان نسبت به هم ارجحيت دارند و يا اينکه به جوابهاي بهينه نزديکتر هستند. براي اين کار از تابع برازندگي۷۵ استفاده ميشود که به آن تابع هزينه۷۶ نيز گفته ميشود. برازندگي يك عضو در الگوريتم ژنتيك مساوي با مقداري است كه تابع برازندگي به آن نسبت ميدهد. براي تعيين ميزان برازندگي، كروموزومها بايد ديكد (رمزگشايي) شوند. تعيين ميزان برازندگي شاخصي براي ارزيابي نحوه عملکرد افراد در فضاي جستجو ميباشد بدين معني كه برازندگي هر يك از افراد جمعيت نشان دهنده ميزان مطلوبيت آن فرد نسبت به بقيه افراد و نزديكي آن به جواب نهايي مسئله ميباشد.
براي ارزيابي برازندگي افراد در مسائل مختلف بهينهسازي با توجه به نوع مسئله دو روش مختلف وجود دارد. در مسايل ساده ميتوان توابع رياضي مشخصي را بيان كرد تا بتوان از طريق آنها برازندگي افراد جمعيت را تعيين نمود اما در برخي از مسايل پيچيده نميتوان رابطه رياضي خاصي ارايه داد و بايد از روشهاي عددي براي تعيين برازندگي استفاده كرد. سپس شرط پايان الگوريتم وجود دارد.
در عمل چندين گزينه براي شرط پايان الگوريتم ژنتيک وجود دارد که اين شروط بايد به گونهاي تعيين شوند که وقتي الگوريتم به جواب بهينه کلي رسيد آن را متوقف نمايد. در هر صورت همواره مشخص است که جمعيت اوليه نميتواند جواب بهينه مسئله باشد بنابراين مراحل انتخاب۷۷ و تقاطع۷۸ و جهش۷۹ نيز بايد اجرا شوند. در واقع اينها هر يک عملگرهايي هستند که به کمک آنها نسل جديد كروموزومها از روي نسل قبلي به وجود ميآيند. مجموعه اين عمليات را ميتوان عمليات توليد نسل جديد۸۰ ناميد. پس از توليد نسل جديد بايد دوباره ميزان برازندگي کروموزومهاي آن ارزيابي شوند و كنترل شود كه آيا جواب بهينه مسئله بدست آمده يا خير؟. اين فرآيند تا جايي بايد تکرار شود که الگوريتم جمعيت اوليه را به جمعيت بهينهاي سوق دهد که جواب بهينه کلي مسئله را شامل شود.
تا اينجا شرح مختصري از الگوريتم ژنتيك ارايه شد در ادامه کدگذاري ، انتخاب ، توليد مثل و جهش و انواع آنها در الگوريتم ژنتيك شرح داده شدهاند.
كدگذاري
الگوريتم ژنتيك به جاي كار بر روي پارامترها يا متغيرهاي يك مسئله، با شكل كد شده آنها سر و كار دارد. در واقع با کدگذاري، فضاي طراحي يا فضاي جستجو به فضاي استانداردي تبديل ميشود که ميتوان عملگرهاي الگوريتم ژنتيك را به نحو مناسبي روي آن پياده کرد. روشهاي متنوعي براي كدگذاري وجود دارد. انتخاب روش مناسب به مسئله مورد بررسي بستگي دارد. در ادامه چند نمونه از روشهاي كدگذاري مورد استفاده در الگوريتم ژنتيك شرح داده شده اند.
كدگذاري دو دويي
اين نوع کدگذاري سادهترين و در عين حال متداولترين روش کدگذاري دادههاي ورودي الگوريتم ژنتيک ميباشد. مطابق شکل (‏۲-۱۱)، در اين روش دادههاي ورودي به صورت رشتهاي از اعداد صفر و يک وارد الگوريتم ميشوند. هر بيت در رشته ميتواند نمايانگر يكي از مشخههاي جواب مسئله باشد بنابراين هر رشته يك جواب براي مسئله مورد بررسي ميباشد ولي لزوماً بهترين جواب نيست. طول رشته بستگي به دقت جواب دارد. معمولاً به الگوريتمهايي که با اين روش کدگذاري ميشوند الگوريتمهاي ژنتيک دودويي نيز گفته ميشود ‏[۴۶].

۱ ۱ ۱ ۰ ۰ ۰ ۱ ۰
كروموزوم ۱
۰ ۱ ۱ ۱ ۱ ۰ ۱ ۱
كروموزوم ۲
شکل (‏۲-۱۱): كدگذاري باينري

كدگذاري جايگشتي۸۱
در اين روش از اعداد صحيح براي انجام عمليات کدگذاري استفاده ميشود. اين روش كدگذاري براي مواقعي كه برازندگي يك عضو وابسته به موقعيت ژن‌ها روي كروموزوم باشد مانند مسايل مرتبسازي، مفيد مي‌باشد. براي اين گونه مسايل براي جلوگيري از يكسان شدن كروموزومها بعد از اعمال تقاطع و جهش بايد اصلاحاتي در اين عملگرها صورت گيرد. اين روش کدگذاري در شکل (‏۲-۱۲) نمايش داده شده است.

مطلب مشابه :  منبع پایان نامه ارشد دربارهويروس، بيماري، نيوكاسل، (نمودار3-

۱ ۵ ۳ ۲ ۶ ۴ ۷ ۹ ۸
كروموزوم A
8 5 6 7 2 3 1 4 9
كروموزوم B
شکل (‏۲-۱۲): كدگذاري جايگشتي

كدگذاري مقداري۸۲
در اين روش کروموزومها به صورت رشتهاي از مقادير کدگذاري ميشوند که اين مقادير ميتوانند هر چيز مرتبط با دادههاي ورودي مسئله مانند اعداد اعشاري ، عبارات منطقي و يا حروف الفبا و غيره باشند (شکل (‏۲-۱۳)). اين
روش براي برخي مسايل خاص مناسب است و اغلب لازم ميباشد تا عملگرهاي بازتركيب و جهش متناسب با مسئله تعريف شوند.

۱٫۲۳۲۴ ۵٫۳۲۴۳ ۰٫۴۵۵۶ ۲٫۳۲۹۳ ۲٫۴۵۴۵
كروموزوم A
ABDJEFIFJDHDIERJFDLDFLFEGT
كروموزوم B
(back), (right), (left), (forward), (left)
كروموزوم C
شکل (‏۲-۱۳): كدگذاري مقداري

انتخاب
انتخاب، فرايند گزينش دو والد از جمعيت جهت انجام تقاطع ميباشد. در انتخاب، اعضايي که برازندگي۸۳ بالاتري دارند انتخاب ميشوند به اين اميد كه فرزندان آنها بعد از تقاطع ميزان برازندگي بيشتري داشته باشند. كروموزومهاي انتخاب شده از جمعيت اوليه والديني هستند كه در توليد مثل شركت ميكنند. در شکل (‏۲-۱۴) به صورت ساده نحوه انجام انتخاب نشان داده شده است.

شکل (‏۲-۱۴): نحوه انجام انتخاب

در انتخاب، كروموزومها به صورت تصادفي و بر اساس تابع برازندگي انتخاب ميشوند. هرچه ميزان برازندگي يك عضو در جمعيت بيشتر باشد شانس انتخاب بيشتري دارد. براي انتخاب كروموزومها روشهاي مختلفي وجود دارد. در ادامه چند روش پركاربرد انتخاب شرح داده شده است ‏[۴۶].
روش چرخ گردان۸۴
اين روش يکي از متداول ترين روشهاي انتخاب ميباشد. در اين روش احتمال انتخاب هر عضو متناسب با مقدار برازندگي آن عضو ميباشد. روش چرخ گردان را ميتوان به اين صورت بيان نمود: ارزش هر عضو برابر با ميزان برازندگي آن عضو تقسيم بر ميزان برازندگي كل جمعيت ميباشد. به هر عضو يك قطاعي از چرخ اختصاص داده ميشود كه اندازه آن قطاع متناسب با ارزش آن عضو مي‌باشد. چرخ N بار ميچرخد كه N برابر تعداد اعضاي نسل بعد ميباشد. براي انجام عمل انتخاب، عددي تصادفي بين صفر و مجموع برازندگيها انتخاب ميشود و کروموزومي که عدد تصادفي انتخاب شده، در محدوده آن بر روي محيط دايره واقع شده باشد براي عمل توليد مثل انتخاب ميشود.
از لحاظ عملكردي روش چرخ گردان يك روش انتخاب نسبتاً متوسط ميباشد زيرا هيچ ضمانتي براي انتخاب اعضاي با برازندگي بالا وجود ندارد و فقط احتمال انتخاب آنها نسبت به بقيه اعضا بيشتر ميباشد.

شکل (‏۲-۱۵): روش انتخاب چرخ گردان

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

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

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

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

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

شکل (‏۲-۱۶): تقاطع تكنقطهاي

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

شکل (‏۲-۱۷): تقاطع دونقطهاي

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

شکل (‏۲-۱۸): تقاطع يكنواخت

جهش۹۲
بعد از تقاطع، كرموزوم ها در معرض جهش قرار ميگيرند. جهش پديدهاي است که در الگوريتم ژنتيک به تغيير ناگهاني ژن گفته ميشود. اين عملگر اميد احياي کروموزوم هاي خوبي را که در مراحل انتخاب يا توليد مثل حذف شدهاند ، زنده ميکند و نيز تضمين مينمايد که جستجو در تمام فضاي طراحي صورت ميپذيرد. جهش از گير افتاندن الگوريتم در نقاط بهينه محلي جلوگيري ميكند و نيز تنوع ژنتيكي را در جمعيت حفظ ميكند. نحوه اعمال عملگر جهش به طور کامل وابسته به نوع کدگذاري مسئله ميباشد. براي کدگذاري دودويي جهش ميتواند شامل تغيير مقدار هر ژن از صفر به يک و يا از يک به صفر با يك احتمال كوچك باشد ‏[۴۶].
وارون كردن۹۳
وارون كردن شامل تغيير دادن يك ژن از ۰ به ۱ و ۱ به ۰ بر اساس يك كرموزوم جهش تصادفي ميباشد. شکل (‏۲-۱۹) مفهوم وارون كردن را بيان ميكند. يك والد در نظر گرفته ميشود و يك كروموزوم جهش به صورت تصادفي ايجاد ميشود. براي هر عدد ۱ موجود در كروموزوم جهش، ژن موجود در والد تغيير ميكند (از ۱ به ۰ و از ۰ به ۱) و كروموزوم فرزند توليد ميشود. در مثال ارايه شده در شکل (‏۲-۱۹) در سه نقطه از كروموزوم جهش، عدد ۱ ظاهر شده است بنابراين در نقاط متناظر آن در كروموزوم والد تغيير صورت گرفته است.

شکل (‏۲-۱۹): جهش flipping

تبادل۹۴
دو نقطه در كروموزوم به صورت تصادفي انتخاب ميشوند و مقادير آن ها با يكديگر تعويض ميشوند. در شکل (‏۲-۲۰) اين روش تقاطع نشان داده شده است.

شکل (‏۲-۲۰): جهش به روش تبادل

معكوس كردن۹۵
دو نقطه در كروموزوم به صورت تصادفي