محدوده کاري الگوريتم ژنتيک بسيار وسيع مي باشد و هر روز با پيشرفت روزافزون علوم و تکنولوژي استفاده از اين روش در بهينه سازي و حل مسائل بسيار گسترش يافته است. الگوريتم ژنتيک يکي از زير مجموعه هاي محاسبات تکامل يافته مي باشد که رابطه مستقيمي با مبحث هوش مصنوعي دارد در واقع الگوريتم ژنتيک يکي از زير مجموعه هاي هوش مصنوعي مي باشد. الگوريتم ژنتيک را ميتوان يک روش جستجوي کلي ناميد که از قوانين تکامل بيولوژيک طبيعي تقليد ميکند .الگوريتم ژنتيک بر روي يکسري از جوابهاي مساله به اميد بدست آوردن جوابهاي بهتر قانون بقاي بهترين را اعمال مي کند. درهر نسل به کمک فرآيند انتخابي متناسب با ارزش جوابها و توليد مثل جواب-هاي انتخاب شده به کمک عملگرهايي که از ژنتيک طبيعي تقليد شده اند ,تقريبهاي بهتري از جواب نهايي بدست مي آيد. اين فرايند باعث ميشود که نسلهاي جديد با شرايط مساله سازگارتر باشد.
ساختار الگوريتمهاي ژنتيكي
به طور كلي, الگوريتمهاي ژنتيكي از اجزاء زير تشكيل ميشوند:
كروموزوم Chromosome
در الگوريتمهاي ژنتيكي, هر كروموزوم نشان دهنده يك نقطه در فضاي جستجو و يك راه حل ممكن براي مسئله مورد نظر است. خود كروموزومها (راه حلها) از تعداد ثابتي ژن (متغير) تشكيل ميشوند. براي نمايش كروموزومها, معمولاً از كدگذاريهاي دودويي (رشته هاي بيتي) استفاده ميشود.
جمعيت Population
مجموعهاي از كروموزومها يك جمعيت را تشكيل ميدهند. با تاثير عملگرهاي ژنتيكي بر روي هر جمعيت, جمعيت جديدي با همان تعداد كروموزوم تشكيل ميشود.
تابع برازندگي Fitness Function
به منظور حل هر مسئله با استفاده از الگوريتمهاي ژنتيكي, ابتدا بايد يك تابع برازندگي براي آن مسئله ابداع شود. براي هر كروموزوم, اين تابع عددي غير منفي را برميگرداند كه نشان دهنده شايستگي يا توانايي فردي آن كروموزوم است.
عملگرهاي الگوریتم ژنتيك
در الگوريتمهاي ژنتيكي, در طي مرحله توليد مثل Reproduction ازعملگرهاي ژنتيكي استفاده ميشود. با تاثير اين عملگرها بر روي يك جمعيت, نسل Generation بعدي آن جمعيت توليد ميشود. عملگرهاي انتخاب Selection , آميزش Crossover و جهش Mutation معمولاً بيشترين كاربرد را در الگوريتمهاي ژنتيكي دارند.
عملگر انتخاب (Selection ):
اين عملگر از بين كروموزومهاي موجود در يك جمعيت, تعدادي كروموزوم را براي توليد مثل انتخاب ميكند. كروموزومهاي برازنده تر شانس بيشتري دارند تا براي توليد مثل انتخاب شوند.
روش های انتخاب :
Elitist Selection (انتخاب نخبگان)
مناسب‌ترین عضو هر اجتماع انتخاب می‌شود. با توجه به مقدار شایستگی که از تابع ارزیاب دریافت کرده است.
نمونه برداري به روش چرخ رولت
در اين روش, به هر فرد قطعه اي از يك چرخ رولت مدور اختصاص داده ميشود. اندازه اين قطعه متناسب با برازندگي آن فرد است. چرخ N بار چرخانده ميشود كه N تعداد افراد در جمعيت است. در هر چرخش, فرد زير نشانگر چرخ انتخاب ميشود و در مخزن والدين نسل بعد قرار ميگيرد. اين روش ميتواند به صورت زير پياده سازي شود:
- نرخ انتظار كل افراد جمعيت را جمع كنيد و حاصل آن را T بناميد.
- مراحل زير را N بار تكرار كنيد:
يك عدد تصادفي r بين 0 و T انتخاب كنيد.
در ميان افراد جمعيت بگرديد و نرخهاي انتظار( مقدار شایستگی) آنها را با هم جمع كنيد تا اين كه مجموع بزرگتر يا مساوي r شود. فردي كه نرخ انتظارش باعث بيشتر شدن جمع از اين حد ميشود, به عنوان فرد برگزيده انتخاب ميشود.
Tournament Selection (انتخاب تورنومنت) :
یک زیر مجموعه از صفات یک جامعه انتخاب می‌شوند و اعضای آن مجموعه با هم رقابت می‌کنند و سرانجام فقط یک صفت از هر زیر‌گروه برای تولید انتخاب می‌شوند.
عملگر آميزش (Crossover ):
در جریان عمل تلفیق به صورت اتفاقی بخشهایی از کروموزوم ها با یکدیگر تعویض می شوند. این موضوع باعث می شود که فرزندان ترکیبی از خصوصیات والدین خود را به همراه داشته باشند و دقیقاً مشابه یکی از والدین نباشند.
هدف تولید فرزند جدید می باشد به این امید که خصوصیات خوب دو موجود در فرزندشان جمع شده و یک موجود بهتری را تولید کند.
روش کار به صورت زیر است:
بصورت تصادفی یک نقطه از کروموزوم را انتخاب می کنیم
ژن های مابعد آن نقطه از کروموزوم ها را جابجا می کنیم
تلفیق تک نقطه ای (Single Point Crossover)
اگر عملیات تلفیق را در یک نقطه انجام دهیم به آن تلفیق تک نقطه ای می گویند.
تلفیق بدين صورت انجام مي گيرد که حاصل ترکيب کروموزومهاي پدر و مادر مي باشد. روش توليد مثل نيز بدين صورت است که ابتدا بصورت تصادفي ,نقطه اي که قرار است توليد مثل از آنجا آغاز گردد ,انتخاب مي گردد. سپس اعداد بعد از آن به ترتيب از بيت هاي کروموزومهاي پدر و مادر قرار مي گيرد که در شکل زير نيز نشان داده شده است.
در شکل بالا کروموزومهاي 1 و2 در نقش والدين هستند. و حاصل توليد مثل آنها در رشته هائي بنام Offspring ذخيره شده است.دقت شود که علامت “|” مربوط به نقطه شروع توليد مثل مي باشد و در رشته هاي Offspring اعدادي که بعد از نقطه شروع توليد مثل قرار مي گيرند مربوط به کروموزومهاي مربوط به خود مي باشند. بطوريکه اعداد بعد از نقطه شروع مربوط به Offspring1 مربوط به اعداد بعد از نقطه شروع مربوط به کروموزوم 1 و اعداد بعد از نقطه شروع توليد مثل مربوط به Offspring2 مربوط به اعداد بعد از نقطه شروع توليد مثل مربوط به کروموزوم 2 مي باشند
روش ادغام دو نقطه ای Two-point CrossOver :
در این روش دو مکان را به صورت تصادفی انتخاب کرده و مقادیر بین این دو نقطه را جابجا می کنیم.
تلفیق نقطه ای (Multipoint Crossover) :
می توانیم این عملیات را در چند نقطه انجام دهیم ، که به آن بازترکیبی چند نقطه ای می گویند
تلفیق جامع (Uniform Crossover) :
اگر تمام نقاط کروموزوم را بعنوان نقاط بازترکیبی انتخاب کنیم به آن بازترکیبی جامع می گوئیم. مثال)
عملگر جهش (Mutation ):
پس از اتمام عمل آميزش, عملگر جهش بر روي كروموزومها اثر داده ميشود. اين عملگر يك ژن از يك كروموزوم را به طور تصادفي انتخاب نموده و سپس محتواي آن ژن را تغيير ميدهد. اگر ژن از جنس اعداد دودويي باشد, آن را به وارونش تبديل ميكند و چنانچه متعلق به يك مجموعه باشد, مقدار يا عنصر ديگري از آن مجموعه را به جاي آن ژن قرار ميدهد. در شكل زیر چگونگي جهش يافتن پنجمين ژن يك كروموزوم نشان داده شده است.
پس از اتمام عمل جهش, كروموزومهاي توليد شده به عنوان نسل جديد شناخته شده و براي دور بعد اجراي الگوريتم ارسال ميشوند.
قبل از اين كه يك الگوريتم ژنتيكي بتواند اجرا شود, ابتدا بايد كدگذاري (يا نمايش) مناسبي براي مسئله مورد نظر پيدا شود. معمولي ترين شيوه نمايش کروموزومها در الگوريتم ژنتيک به شکل رشته هاي دودويي است. هر متغير تصميم گيري به صورت دودويي در آمده و سپس با کنار هم قرار گرفتن اين متغيرها کروموزوم ايجاد ميشود . گرچه اين روش گسترده ترين شيوه کدگذاري است اما شيوه هاي ديگري مثل نمايش با اعداد حقيقي در حال گسترش هستند. همچنين يك تابع برازندگي نيز بايد ابداع شود تا به هر راه حل كدگذاري شده ارزشي را نسبت دهد. در طي اجرا, والدين براي توليد مثل انتخاب ميشوند و با استفاده از عملگرهاي آميزش و جهش با هم تركيب ميشوند تا فرزندان جديدي توليد كنند. اين فرآيند چندين بار تكرار ميشود تا نسل بعدي جمعيت توليد شود. سپس اين جمعيت بررسي ميشود و در صورتي كه ضوابط همگرايي رآورده شوند, فرآيند فوق خاتمه مي يابد.
پیش نیاز :
در ادامه آموزش الگوریتم های بهینه سازی ، فیلم آموزشی الگوریتم ژنتیک برای دانش پذیران گرامی تهیه شده است. پیش نیاز این فیلم آموزشی، آموزش بهینه سازی می باشد. لذا به دانش پذیران گرامی توصیه می شود ابتدا فیلم آموزشی بهینه سازی را مشاهده کنند و سپس فیلم آموزشی الگوریتم ژنتیک را ببینند.
.
.
مدت زمان : 104 دقیقه
حجم فایل ها : 154 مگابایت
.
.
نتیجه سالها تجربه :
این فیلم آموزشی نتیجه سالها کدنویسی و کار با الگوریتم ژنتیک در پروژه های مختلف می باشد و هزینه ای که شما برای تهیه آن می پردازید در برابر سالها تجربه ای که صرف تهیه این فیلم آموزشی شده بسیار ناچیز است.
.
تصویرهایی از محیط این فیلم آموزشی :
گنجینه فیلم های آموزشی فارسی الگوریتم های بهینه سازی تکاملی-هوش مصنوعی
| ردیف | عنوان | مدت زمان | لینک |
|---|---|---|---|
| 1 | فیلم آموزش فارسی الگوریتم تکامل گرامری Grammatical Evolution | 35 دقیقه | لینک دریافت (کلیک کنید) |
| 2 | فیلم آموزشی فارسی الگوریتم بازی تکاملی Evolutionary Game Algorithm | 35 دقیقه | لینک دریافت (کلیک کنید) |
| 3 | فیلم آموزش فارسی الگوریتم جستجوی فاخته cuckoo search | 100 دقیقه | لینک دریافت (کلیک کنید) |
| 4 | فیلم آموزش فارسی بررسی قیود در مسائل بهینه سازی مقید | 34 دقیقه | لینک دریافت (کلیک کنید) |
| 5 | فیلم آموزش فارسی الگوریتم دسته ماهی مصنوعی | 30 دقیقه | لینک دریافت (کلیک کنید) |
| 6 | فیلم آموزش فارسی الگوریتم کلونی زنبور عسل | 65 دقیقه | لینک دریافت (کلیک کنید) |
| 7 | فیلم آموزش فارسی بهینه سازی مبتنی بر جغرافیای زیستی | 30 دقیقه | لینک دریافت (کلیک کنید) |
| 8 | فیلم آموزش فارسی الگوریتم ژنتیک در متلب | 190 دقیقه | لینک دریافت (کلیک کنید) |