پایان نامه درباره ، -، كروموزوم، کروموزومهاي، الگوريتم‏هاي، ژنتيكي، عملگرهاي، دودويي

استفاده می‌کند.
الگوریتم ژنتیک که به ‌عنوان یکی از روشهای تصادفی بهینهیابی شناخته شده، توسط جان هالند در سال ۱۹۶۷ ابداع شده ‌است. بعدها این روش با تلاشهای گلدبرگ 1989، مکان خویش را یافته و امروزه نیز بواسطه تواناییهای خویش، جای مناسبی در میان دیگر روشها دارد. الگوریتمهای ژنتیک معمولاً به عنوان یک شبیه‌ساز کامپیوتر که در آن جمعیت یک نمونه انتزاعی (کروموزومها) از نامزدهای راه‌حل یک مسأله بهینه‌سازی به راه حل بهتری منجر شود، پیاده‌سازی می‌شوند. به طور سنتی راه‌حلها به شکل رشته‌هایی از ۰ و ۱ بودند، اما امروزه به گونه‌های دیگری هم پیاده‌سازی شده‌اند. فرضیه با جمعیتی کاملاً تصادفی منحصربفرد آغاز می‌شود و در نسلها ادامه می‌یابد. در هر نسل گنجایش تمام جمعیت ارزیابی می‌شود، چندین فرد منحصر در فرایندی تصادفی از نسل جاری انتخاب می‌شوند (بر اساس شایستگیها) و برای شکل دادن نسل جدید، اصلاح می‌شوند (کسر یا دوباره ترکیب می‌شوند) و در تکرار بعدی الگوریتم به نسل جاری تبدیل می‌شود.
3-2-2-2-2. ساختار الگوریتم ژنتیکكروموزوم
در الگوريتم‏هاي ژنتيكي، هر كروموزوم نشان دهنده يك نقطه در فضاي جستجو و يك راه‏حل ممكن براي مسئله مورد نظر است. خود كروموزوم‏ها (راه حل‏ها) از تعداد ثابتي ژن (متغير) تشكيل مي‏شوند. براي نمايش كروموزوم‏ها، معمولاً از كدگذاري‏هاي دودويي (رشته‏هاي بيتي) استفاده مي‏شود.
جمعيت
مجموعه‏اي از كروموزوم‏ها يك جمعيت را تشكيل مي‏دهند. با تاثير عملگرهاي ژنتيكي بر روي هر جمعيت، جمعيت جديدي با همان تعداد كروموزوم تشكيل مي‏شود.
تابع برازندگي
به منظور حل هر مسئله با استفاده از الگوريتم‏هاي ژنتيكي، ابتدا بايد يك تابع برازندگي براي آن مسئله ابداع شود. براي هر كروموزوم، اين تابع عددي غير منفي را برمي‏گرداند كه نشان دهنده شايستگي يا توانايي فردي آن كروموزوم است.
3-2-2-2-3. عملگرهاي الگوریتم ژنتيكدر الگوريتم‏هاي ژنتيكي، در طي مرحله توليد مثل ازعملگرهاي ژنتيكي استفاده مي‏شود. با تاثير اين عملگرها بر روي يك جمعيت، نسل بعدي آن جمعيت توليد مي‏شود. عملگرهاي انتخاب ، آميزش و جهش معمولاً بيشترين كاربرد را در الگوريتم‏هاي ژنتيكي دارند.
عملگر انتخاب (Selection)
اين عملگر از بين كروموزوم‏هاي موجود در يك جمعيت، تعدادي كروموزوم را براي توليد مثل انتخاب مي‏كند. كروموزوم‏هاي برازنده‏تر شانس بيشتري دارند تا براي توليد مثل انتخاب شوند.
روش های انتخاب :
انتخاب نخبگان (Elitist Selection)
مناسب‌ترین عضو هر اجتماع انتخاب می‌شود. با توجه به مقدار شایستگی که از تابع ارزیاب دریافت کرده است.
نمونه‏برداري به روش چرخ رولت
در اين روش، به هر فرد قطعه‏اي از يك چرخ رولت مدور اختصاص داده مي‏شود. اندازه اين قطعه متناسب با برازندگي آن فرد است. چرخ N بار چرخانده مي‏شود كه N تعداد افراد در جمعيت است. در هر چرخش، فرد زير نشانگر چرخ انتخاب مي‏شود و در مخزن والدين نسل بعد قرار مي‏گيرد. اين روش مي‏تواند به صورت زير پياده‏سازي شود:
نرخ انتظار كل افراد جمعيت را جمع كنيد و حاصل آن را T بناميد.
مراحل زير را N بار تكرار كنيد:
يك عدد تصادفي r بين 0 و T انتخاب كنيد.
4216401227455در ميان افراد جمعيت بگرديد و نرخ‏هاي انتظار( مقدار شایستگی) آنها را با هم جمع كنيد تا اين كه مجموع بزرگتر يا مساوي r شود. فردي كه نرخ انتظارش باعث بيشتر شدن جمع از اين حد مي‏شود، به عنوان فرد برگزيده انتخاب مي‏شود.
11703052149475شکل (2) – نحوه ارزیابی شایستگی در چرخ رولت
00شکل (2) – نحوه ارزیابی شایستگی در چرخ رولت

انتخاب تورنومنت (Tournament Selection)
یک زیر مجموعه از صفات یک جامعه انتخاب می‌شوند و اعضای آن مجموعه با هم رقابت می‌کنند و سرانجام فقط یک صفت از هر زیر‌گروه برای تولید انتخاب می‌شوند.
عملگر آميزش (Crossover)
در جریان عمل تلفیق به صورت اتفاقی بخشهایی از کروموزومها با یکدیگر تعویض می شوند. این موضوع باعث میشود که فرزندان ترکیبی از خصوصیات والدین خود را به همراه داشته باشند و دقیقاً مشابه یکی از والدین نباشند. هدف تولید فرزند جدید میباشد به این امید که خصوصیات خوب دو موجود در فرزندشان جمع شده و یک موجود بهتری را تولید کند.
روش کار به صورت زیر است:
بصورت تصادفی یک نقطه از کروموزوم را انتخاب میکنیم
ژن های مابعد آن نقطه از کروموزومها را جابجا میکنیم
تلفیق تک نقطه ای (Single Point Crossover)
9664701854835اگر عملیات تلفیق را در یک نقطه انجام دهیم به آن تلفیق تک نقطهای می گویند. تلفیق بدين صورت انجام ميگيرد که حاصل ترکيب کروموزومهاي پدر و مادر ميباشد. روش توليد مثل نيز بدين صورت است که ابتدا بصورت تصادفي، نقطهاي که قرار است توليد مثل از آنجا آغاز گردد، انتخاب ميگردد. سپس اعداد بعد از آن به ترتيب از بيتهاي کروموزومهاي پدر و مادر قرار ميگيرد که در شکل زير نيز نشان داده شده است.
11569701767840شکل (3) – یک نمونه تلفیق (آمیزش)
00شکل (3) – یک نمونه تلفیق (آمیزش)

در شکل بالا کروموزومهاي 1 و2 در نقش والدين هستند و حاصل توليد مثل آنها در رشتههائي بنام Offspring ذخيره شده است. دقت شود که علامت “|” مربوط به نقطه شروع توليد مثل ميباشد و در رشتههاي Offspring اعدادي که بعد از نقطه شروع توليد مثل قرار ميگيرند مربوط به کروموزومهاي مربوط به خود مي باشند. بطوريکه اعداد بعد از نقطه شروع مربوط به Offspring1 مربوط به اعداد بعد از نقطه شروع مربوط به کرومکوزوم 1 و اعداد بعد از نقطه شروع توليد مثل مربوط به Offspring2 مربوط به اعداد بعد از نقطه شروع توليد مثل مربوط به کروموزوم 2 ميباشند
روش ادغام دو نقطه ای(Two-point CrossOver)
در این روش دو مکان را به صورت تصادفی انتخاب کرده و مقادیر بین این دو نقطه را جابجا می کنیم.
12903201190625شکل (4) – یک نمونه تلفیق دو نقطه ای
00شکل (4) – یک نمونه تلفیق دو نقطه ای
52070-123825
تلفیق نقطه ای (Multipoint Crossover)
میتوانیم این عملیات را در چند نقطه انجام دهیم ، که به آن بازترکیبی چند نقطهای میگویند
.تلفیق جامع (Uniform Crossover)
11645901459865شکل (5) – یک نمونه تلفیق جامع
00شکل (5) – یک نمونه تلفیق جامع
276225833120 اگر تمام نقاط کروموزوم را بعنوان نقاط بازترکیبی انتخاب کنیم به آن بازترکیبی جامع میگوئیم.
عملگر جهش (Mutation)
پس از اتمام عمل آميزش، عملگر جهش بر روي كروموزوم‏ها اثر داده مي‏شود. اين عملگر يك ژن از يك كروموزوم را به طور تصادفي انتخاب نموده و سپس محتواي آن ژن را تغيير مي‏دهد. اگر ژن از جنس اعداد دودويي باشد، آن را به وارونش تبديل مي‏كند و چنانچه متعلق به يك مجموعه باشد، مقدار يا عنصر ديگري از آن مجموعه را به جاي آن ژن قرار مي‏دهد. در شكل (6) چگونگي جهش يافتن پنجمين ژن يك كروموزوم نشان داده شده است.
پس از اتمام عمل جهش، كروموزوم‏هاي توليد شده به عنوان نسل جديد شناخته شده و براي دور بعد اجراي الگوريتم ارسال مي‏شوند.
124968016510جهش
1 0 1 0 0 0 1 1 1 0
1 0 1 0 1 0 1 1 1 0
محل جهش
00جهش
1 0 1 0 0 0 1 1 1 0
1 0 1 0 1 0 1 1 1 0
محل جهش

131889591440شکل (6) – یک کروموزوم قبل و بعد از اعمال عملگر جهش
00شکل (6) – یک کروموزوم قبل و بعد از اعمال عملگر جهش

3-2-2-2-4. روند کلی الگوریتم ژنتیکقبل از اين كه يك الگوريتم ژنتيكي بتواند اجرا شود، ابتدا بايد كدگذاري (يا نمايش) مناسبي براي مسئله مورد نظر پيدا شود. معموليترين شيوه نمايش کروموزومها در الگوريتم ژنتيک به شکل رشتههاي دودويي است. هر متغير تصميمگيري به صورت دودويي درآمده و سپس با کنار هم قرار گرفتن اين متغيرها کروموزوم ايجاد ميشود .گرچه اين روش گستردهترين شيوه کدگذاري است اما شيوههاي ديگري مثل نمايش با اعداد حقيقي در حال گسترش هستند. همچنين يك تابع برازندگي نيز بايد ابداع شود تا به هر راه‏حل كدگذاري شده ارزشي را نسبت دهد. در طي اجرا، والدين براي توليدمثل انتخاب مي‏شوند و با استفاده از عملگرهاي آميزش و جهش با هم تركيب مي‏شوند تا فرزندان جديدي توليد كنند. اين فرآيند چندين بار تكرار مي‏شود تا نسل بعدي جمعيت توليد شود. سپس اين جمعيت بررسي مي‏شود و در صورتي كه ضوابط همگرايي برآورده شوند، فرآيند فوق خاتمه مي‏يابد.
147129557150شکل (7) – روند کلی الگوریتم ژنتیک
00شکل (7) – روند کلی الگوریتم ژنتیک
185420-238125
1308105080جمعيت اوليه
ارزيابی جوابها
آيا جواب مورد نظر حاصل شده؟
پايان
انتخاب
تلفیق
بله
جهش
T=T+1
T=0
خير
شروع
00جمعيت اوليه
ارزيابی جوابها
آيا جواب مورد نظر حاصل شده؟
پايان
انتخاب
تلفیق
بله
جهش
T=T+1
T=0
خير
شروع

11664951255395شکل (8) – روند کلی الگوریتم ژنتیک
00شکل (8) – روند کلی الگوریتم ژنتیک

3-2-2-2-5. شرط پايان الگوريتمچون که الگوریتم های ژنتیک بر پایه تولید و تست می باشند، جواب مساله مشخص نیست و نمی دانیم که کدامیک از جواب های تولید شده جواب بهینه است تا شرط خاتمه را پیدا شدن جواب در جمعیت تعریف کنیم. به همین دلیل، معیارهای

متن کامل پایان نامه ها در سایت sabzfile.com

About: admin