الگوریتم ژنتیک
محدوده کاري الگوريتم ژنتيک بسيار وسيع مي باشد و هر روز با پيشرفت روزافزون علوم و تکنولوژي استفاده از اين روش در بهينه سازي و حل مسائل بسيار گسترش يافته است. الگوريتم ژنتيک يکي از زير مجموعه هاي محاسبات تکامل يافته مي باشد که رابطه مستقيمي با مبحث هوش مصنوعي دارد در واقع الگوريتم ژنتيک يکي از زير مجموعه هاي هوش مصنوعي مي باشد. الگوريتم ژنتيک را ميتوان يک روش جستجوي کلي ناميد که از قوانين تکامل بيولوژيک طبيعي تقليد ميکند .الگوريتم ژنتيک برروي يکسري از جوابهاي مساله به اميد بدست آوردن جوابهاي بهتر قانون بقاي بهترين را اعمال مي کند. در هر نسل به کمک فرآيند انتخابي متناسب با ارزش جوابها و توليد مثل جواب-هاي انتخاب شده به کمک عملگرهايي که از ژنتيک طبيعي تقليد شدهاند ,تقريبهاي بهتري از جواب نهايي بدست ميآيد. اين فرايند باعث ميشود که نسلهاي جديد با شرايط مساله سازگارتر باشد .
2- تاریخچه
حساب تکاملي ,براي اولين بار در سال 1960 توسط آقاي ريچنبرگ ارائه شد که تحقيق وي در مورد استراتژي تکامل بود.بعدها نظريه او توسط محققان زيادي مورد بررسي قرار گرفت تا اينکه الگوريتم ژنتيک (GA ) توسط جان هولند(John Holland ) و در سال 1975 در دانشگاه ميشيگان ,ارائه شد.
در سال 1992 نيز جان کوزا (John Koza ) از الگوريتم ژنتيک (GA ) براي حل و بهينه سازي مسائل مهندسي پيشرفته استفاده کرد و توانست براي اولين بار روند الگوريتم ژنتيک (GA ) را به زبان کامپيوتر در آورد و براي آن يک زبان برنامه نويسي ابداع کندکه به اين روش برنامه نويسي ,برنامه نويسي ژنتيک ( GP ) گويند و نرم افزاري که توسط وي ابداع گرديد به نرم افزار LISP مشهور است که هم اکنون نيز اين نرم افزار کاربرد زيادي در حل و بهينه سازي مسائل مهندسي پيدا کرده است .
2-1 تاريخچه بيولوژيکي
بدن هر موجود زنده اي از سلول تشکيل يافته است و هر سلول هم از کروموزوم تشکيل يافته است.کروموزومها نيز از رشته هاي DNA تشکيل يافته اند.کروموزومها هم از ژن تشکيل يافته اند.و به هر بلوک DNA يک ژن مي گويند و هر ژن نيز از يک پروتئين خاص ومنحصر به فرد تشکيل يافته است.و به مجموعه از ژنها يک ژنوم (Genome ) مي گويند.
3- ساختار الگوريتم‌هاي ژنتيكي
به طور كلي, الگوريتم‌هاي ژنتيكي از اجزاء زير تشكيل ميشوند:
3-1 كروموزوم[1]
در الگوريتم‌هاي ژنتيكي, هر كروموزوم نشان دهنده يك نقطه در فضاي جستجو و يك راهحل ممكن براي مسئله مورد نظر است. خود كروموزومها (راه حلها) از تعداد ثابتي ژن[2] (متغير) تشكيل ميشوند. براي نمايش كروموزومها, معمولاً از كدگذاريهاي دودويي (رشتههاي بيتي) استفاده ميشود.
3-2 جمعيت[3]
مجموعهاي از كروموزومها يك جمعيت را تشكيل ميدهند. با تاثير عملگرهاي ژنتيكي بر روي هر جمعيت, جمعيت جديدي با همان تعداد كروموزوم تشكيل ميشود.
3-3 تابع برازندگي[4]
به منظور حل هر مسئله با استفاده از الگوريتم‌هاي ژنتيكي, ابتدا بايد يك تابع برازندگي براي آن مسئله ابداع شود. براي هر كروموزوم, اين تابع عددي غير منفي را برميگرداند كه نشان دهنده شايستگي يا توانايي فردي آن كروموزوم است.
3-4 عملگرهاي الگوریتم ژنتيك
در الگوريتم‌هاي ژنتيكي, در طي مرحله توليد مثل[5] ازعملگرهاي ژنتيكي استفاده ميشود. با تاثير اين عملگرها بر روي يك جمعيت, نسل[6] بعدي آن جمعيت توليد ميشود. عملگرهاي انتخاب[7] , آميزش[8] و جهش[9] معمولاً بيشترين كاربرد را در الگوريتم‌هاي ژنتيكي دارند.
3-4-1 عملگر انتخاب (Selection ):
اين عملگر از بين كروموزومهاي موجود در يك جمعيت, تعدادي كروموزوم را براي توليد مثل انتخاب ميكند. كروموزومهاي برازندهتر شانس بيشتري دارند تا براي توليد مثل انتخاب شوند.
روش های انتخاب :
- : Elitist Selection (انتخاب نخبگان)
o مناسب‌ترین عضو هر اجتماع انتخاب میشود. با توجه به مقدار شایستگی که از تابع ارزیاب دریافت کرده است.
- نمونهبرداري به روش چرخ رولت
در اين روش, به هر فرد قطعهاي از يك چرخ رولت مدور اختصاص داده ميشود. اندازه اين قطعه متناسب با برازندگي آن فرد است. چرخ N بار چرخانده ميشود كه N تعداد افراد در جمعيت است. در هر چرخش, فرد زير نشانگر چرخ انتخاب ميشود و در مخزن والدين نسل بعد قرار ميگيرد. اين روش ميتواند به صورت زير پيادهسازي شود:
1- نرخ انتظار كل افراد جمعيت را جمع كنيد و حاصل آن را T بناميد.
2- مراحل زير را N بار تكرار كنيد:
يك عدد تصادفي r بين 0 و T انتخاب كنيد.
در ميان افراد جمعيت بگرديد و نرخهاي انتظار( مقدار شایستگی) آنها را با هم جمع كنيد تا اين كه مجموع بزرگتر يا مساوي r شود. فردي كه نرخ انتظارش باعث بيشتر شدن جمع از اين حد ميشود, به عنوان فرد برگزيده انتخاب ميشود.
- Tournament Selection (انتخاب تورنومنت) :
یک زیر مجموعه از صفات یک جامعه انتخاب می‌شوند و اعضای آن مجموعه با هم رقابت می‌کنند و سرانجام فقط یک صفت از هر زیر‌گروه برای تولید انتخاب می‌شوند.
3-4-1 عملگر آميزش (Crossover ):
در جریان عمل تلفیق به صورت اتفاقی بخشهایی از کروموزوم ها با یکدیگر تعویض می شوند. این موضوع باعث می شود که فرزندان ترکیبی از خصوصیات والدین خود را به همراه داشته باشند و دقیقاً مشابه یکی از والدین نباشند.
هدف تولید فرزند جدید می باشد به این امید که خصوصیات خوب دو موجود در فرزندشان جمع شده و یک موجود بهتری را تولید کند.
روش کار به صورت زیر است:
بصورت تصادفی یک نقطه از کروموزوم را انتخاب می کنیم
ژن های مابعد آن نقطه از کروموزوم ها را جابجا می کنیم
- تلفیق تک نقطه ای (Single Point Crossover)
اگر عملیات تلفیق را در یک نقطه انجام دهیم به آن تلفیق تک نقطه ای می گویند.
تلفیق بدين صورت انجام مي گيرد که حاصل ترکيب کروموزومهاي پدر و مادر مي باشد.روش توليد مثل نيز بدين صورت است که ابتدا بصورت تصادفي ,نقطه اي که قرار است توليد مثل از آنجا آغاز گردد ,انتخاب مي گردد.سپس اعداد بعد از آن به ترتيب از بيت هاي کروموزومهاي پدر و مادر قرار مي گيرد که در شکل زير نيز نشان داده شده است.
شکل 3 یک نمونه تلفیق (آمیزش)
در شکل بالا کروموزومهاي 1 و2 در نقش والدين هستند. و حاصل توليد مثل آنها در رشته هائي بنام Offspring ذخيره شده است.دقت شود که علامت “|” مربوط به نقطه شروع توليد مثل مي باشد و در رشته هاي Offspring اعدادي که بعد از نقطه شروع توليد مثل قرار مي گيرند مربوط به کروموزومهاي مربوط به خود مي باشند.بطوريکه اععدار بعد از نقطه شروع مربوط به Offspring1 مربوط به اعداد بعد از نقطه شروع مربوط به کرومکوزوم 1 و اعداد بعد از نقطه شروع توليد مثل مربوط به Offspring2 مربوط به اعداد بعد از نقطه شروع توليد مثل مربوط به کروموزوم 2 مي باشند
- روش ادغام دو نقطه ای((Two-point CrossOver :
در این روش دو مکان را به صورت تصادفی انتخاب کرده و مقادیر بین این دو نقطه را جابجا می کنیم.
- تلفیق نقطه ای (Multipoint Crossover) :
می توانیم این عملیات را در چند نقطه انجام دهیم ، که به آن بازترکیبی چند نقطه ای می گویند
- .تلفیق جامع (Uniform Crossover) :
اگر تمام نقاط کروموزوم را بعنوان نقاط بازترکیبی انتخاب کنیم به آن بازترکیبی جامع می گوئیم. مثال)
3-4-3.عملگر جهش (Mutation ):
پس از اتمام عمل آميزش, عملگر جهش بر روي كروموزومها اثر داده ميشود. اين عملگر يك ژن از يك كروموزوم را به طور تصادفي انتخاب نموده و سپس محتواي آن ژن را تغيير مي‌دهد. اگر ژن از جنس اعداد دودويي باشد, آن را به وارونش تبديل ميكند و چنانچه متعلق به يك مجموعه باشد, مقدار يا عنصر ديگري از آن مجموعه را به جاي آن ژن قرار مي‌دهد. در شكل 2 چگونگي جهش يافتن پنجمين ژن يك كروموزوم نشان داده شده است.
پس از اتمام عمل جهش, كروموزومهاي توليد شده به عنوان نسل جديد شناخته شده و براي دور بعد اجراي الگوريتم ارسال ميشوند.
4- روند كلي الگوريتم‌هاي ژنتيكي
قبل از اين كه يك الگوريتم ژنتيكي بتواند اجرا شود, ابتدا بايد كدگذاري (يا نمايش) مناسبي براي مسئله مورد نظر پيدا شود. معمولي ترين شيوه نمايش کروموزومها در الگوريتم ژنتيک به شکل رشته هاي دودويياست. هر متغير تصميم گيري به صورت دودويي در آمده و سپس با کنار هم قرار گرفتن اين متغيرها کروموزوم ايجاد ميشود .گرچه اين روش گسترده ترين شيوه کدگذاري است اما شيوه هاي ديگري مثل نمايش با اعداد حقيقي در حال گسترش هستند.همچنين يك تابع برازندگي نيز بايد ابداع شود تا به هر راه حل كدگذاري شده ارزشي را نسبت دهد. در طي اجرا, والدين براي توليد مثل انتخاب ميشوند و با استفاده از عملگرهاي آميزش و جهش با هم تركيب ميشوند تا فرزندان جديدي توليد كنند. اين فرآيند چندين بار تكرار ميشود تا نسل بعدي جمعيت توليد شود. سپس اين جمعيت بررسي ميشود و در صورتي كه ضوابط همگرايي رآورده شوند, فرآيند فوق خاتمه مييابد.
شکل 5 کد برنامه مجازي الگوريتم ژنتيک ساده و فلوچارت آن
5- روند کلي بهينه سازي و حل مسائل در الگوريتم ژنتيک :
5-1 شروع(Start ) : توليد تصادفي يک جمعيت(Population ) که شامل تعداد زيادي کروموزم(روشهاي حل مسئله است) مي باشد.
5-2-صحت و درستي(Fitness ): ارزيابي صحت براي تابع f(x) به ازائ هر کروموزوم x درجمعيت.
شکل 6 نحوه ارزیابی تابع شایستگی در چرخ رولت
5-3-ايجاد يک جمعيت جديد(New Population ):توليد يک جمعيت جديد با انجام تمامي زير گروههاي زير تا آنکه يک جمعيت جديد ايجاد گردد.
5-3-1 : انتخاب(Selection ):انتخاب کروموزومهاي پدر و مادر از جمعيت قبلي با توجه به صحت و درستي آن (Fitness ).بطوريکه هر چه Fitnees بهتر باشد (دقت جواب در همگرائي بيشتر باشد) شانس بيشتري براي انتخاب دارد.
5-3-2 :توليد مثل(Crossover ):انجام زادو ولد و ايجاد يک نسل جديد.
5-3-3 :جهش(Mutation ):مشخص شدن مکان فرزند توليد شده در کروموزوم
5-3-4 :پذيرش(Accepting ): جا دادن فرزند جديد در داخل جمعيت.
5-4-جايگزيني(Replace ):جايگزيني جمعيت جديد به حاي جمعيت قبلي و مورد استفاده قرار دادن جمعيت جديد در مراحل بعدي الگوريتم
5-5-امتحان: (Test ): اگر شرائط مطلوب در حل مسئله ارضا شد اعلام ميکنيم که به بهترين جواب رسيده ايم و از الگوريتم خارج مي شويم در غير اين صورت به مرحله 2 يعني Fitneess ميرويم و دوباره همين روند را تکرار مي کنيم.
6- شرط پايان الگوريتم
چون که الگوریتم های ژنتیک بر پایه تولید و تست می باشند، جواب مساله مشخص نیست و نمی دانیم که کدامیک از جواب های تولید شده جواب بهینه است تا شرط خاتمه را پیدا شدن جواب در جمعیت تعریف کنیم. به همین دلیل، معیارهای دیگری را برای شرط خاتمه در نظر میگیریم:
- تعداد مشخصی نسل: میتوانیم شرط خاتمه را مثلاً 100 دور چرخش حلقه اصلی برنامه قرار دهیم.
- عدم بهبود در بهترین شایستگی جمعیت در طی چند نسل متوالی
- بهترین شایستگی جمعیت تا یک زمان خاصی تغییری نکند.
ü شرایط دیگری نیز میتوانیم تعریف کنیم و همچنین میتوانیم ترکیبی از موارد فوق را به عنوان شرط خاتمه به کار ببندیم.
يک مثال ساده:
ما يک مربع 3*3 داريم که مي خواهيم اعدادي بين 1تا15 را در اين مربع قرار دهيم به طوري که جمع اعداد در هر سطرو ستون برابر 24 شود.
ابن مسئله تا حدودي پيچيده است.ممکن است يک انسان بتواند آن را در مدت زماني مشخص حل کند ولي هيچ گاه يک کامپيوتر نخواهد توانست آن رادر مدت زمان کوتاهي با استفاده از اعداد تصادفي حل کند. ولي الگوريتم ژنتيک مي تواند اين مشکل را حل کند.
نسل اول
اولين گام ايجاد کردن يک نسل ابتدايي براي شروع کار است که شامل تعدادي ژنوم تصادفي است.اين ژنوم ها به صورت باينري(0و1) نشان داده مي شوند. حالا مثال مان:
اول يکسري عدد به صورت تصادفي توليد مي شوند. هر ژنوم يا کروموزوم شامل اطلاعاتي براي هر 9 جاي خالي است .چون اين اعداد مقادير بين 0تا15 دارند مي توان آنها را با 4 بيت يا ژن داده نمايش داد. پس هر ژنوم شامل 36 بيت است.
يک نمونه ژنوم مي تواند به شکل زير باشد:
Bits (Genes) 0110 1100 1111 1011 0100 1010 0111 0101 1110
Values(Traits) 6 12 15 11 4 10 7 5 14
حالابايد به هر ژنوم در مجموعه يک عدد تناسب(Fitness) بنابر تاثير آن در حل مسئله نسبت داد.فرآيند وروش محاسبه اين عدد براي هر مسئله فرق مي کند.انتخاب الگوي مناسب براي مسئله مشکلترين و حساسترين بخش در حل مسئله ژنتيک است.دراين مثال ما اعداد را در مکان هايشان جايگذاري مي کنيم و بررسي مي کنيم که چقدر با جواب اصلي فاصله دارند.
مقادير معادل عبارتند از 33و25و26و24و21و39.واضح است که اين مقادير مسئله را حل نمي کنند.پس بايد مقادير تناسب را براي اين ژنوم محاسبه کرد.براي اين کار ابتدا فاصله هرمجموع را از24 محاسبه کرده،سپس معکوس مجموع تفاصل آنها را محاسبه مي کنيم .
بنابراين درجه تناسب براي اين ژنوم تقريباً برابر 0.033 است.هرچقدر که اعداد ما به جواب نزديکتر باشند عدد تناسب بزرگتر خواهد شد.اما اگر مخرج ما برابر 0شود چه اتفاقي مي افتد؟ دراين صورت همه اعداد ما برابر 24 شده اند وما به جواب رسيده ايم.
نسل بعدي: دو ژنوم (کروموزوم) به طور تصادفي براي توليد نسل بعدي انتخاب مي شوند. اين اصلي ترين بخش الگوريتم ژنتيک است که از 3 مرحله تشکيل شده:
1-انتخاب
دو ژنوم به طور تصادفي از نسل قبل انتخاب مي شوند.اين ژنوم ها داراي اعداد تناسب بزرگتري هستند و بعضي صفات آنها به نسل بعدي منتقل مي شوند. اين بدين معني است که عدد تناسب در حال افزايش خواهد بود.
بهترين روش براي تابع انتخاب(Fitness) در اين مسئله روشي به نام رولت(Roulette) است.اول يک عدد تصادفي بين 0 وعدد تناسب نسل قبلي انتخاب مي شود. تابع انتخاب به صورت زير خواهد بود:
RouletteSelection(){ float ball = rand_float_between(0.0, total_fitness); float slice = 0.0; for each genome in population { slice += genome.fitness;//مقدار شایستگی هر ژنوم( کروموزوم) با ژنوم های بعدی جمع میشود if slice > ball return genome; }}
2- تلفیق(Crossover)
حالا دو ژنوم بخشي از ژنهايشان را براي ايجاد نسل بعدي اهدا مي کنند. اگر آنها تغيير پيدا نکنند همانطور بي تغيير به نسل بعدي منتقل خواهند شد.درجهCrossover نشان دهنده اين است که هر چند وقت يکبار ژنوم ها تغيير پيدا خواهند کرد و اين عدد بايد در حدود 65-85% باشد.
عملگر تغيير در ژنوم هاي باينري مثال ما با انتخاب يک مکان تصادفي در ژنوم براي تغيير آغاز مي شود. بخش اول ژنهاي پدر و بخش دوم ژنهاي مادر با هم ترکيب مي شوند(و بالعکس) تا2 فرزند توليد شوند. در زيريک عمل تغيير را مي بينيم.
Before Crossing
Father 011110010011 001011011000111011010000
Mother 010100111110 010101111101000100010010
After Crossing
Child1 011110010011 010101111101000100010010
Child2 010100111110 001011011000111011010000
3- جهش(Mutation)
قبل از اين که ژنوم ها در نسل بعدي قرار بگيرند،احتمال دارد دچار جهش يا تغيير ناگهاني شوند شوند.جهش يک تغيير ناگهاني در ژن است.در ژنهاي باينري اين تغيير به معناي تغيير يک بيت از 0به 1 يا از 1 به 0 است. درجه جهش نشان دهنده احتمال بروز جهش در يک ژن است و تغريباً بين 1-5% براي ژنهاي باينري و 5-20%براي ژنهاي عددي است.
این روند تا تولید نسل های متعددی ادامه می یابد تا در نهایت به جواب برسیم.
7- برخي از كاربرد الگوريتم‌هاي ژنتيكي
توپولوژي هاي شبکه هاي کامپيوتي توزيع شده.
بهينه سازي ساختار ملکولي شِميايي (شيمي)
مهندسي برق براي ساخت آنتنهاي Crooked-Wire Genetic Antenna
مهندسي نرم افزار
بازي هاي کامپيوتري
مهندسي مواد
مهندسي سيستم
رباتيک(Robotics)
تشخيص الگوو استخراج داده(Data mining)
حل مسئله فروشنده دوره گرد
آموزش شبکه هاي عصبي مصنوعي
ياددهي رفتار به رباتها با GA .
يادگيري قوانين فازي با استفاده از الگويتم هاي ژنتيک.
8- نتيجه گيري
الگوريتم‌هاي ژنتيك الگوريتم‌هايي هستند كه داراي قدرت بسيار زيادي در يافتن جواب مسئله هستند، اما بايد توجه داشت كه شايد بتوان كاربرد اصلي اين الگوريتم ها را در مسائلي در نظر گرفت كه داراي فضاي حالت بسيار بزرگ هستند و عملاً بررسي همه حالت‌ها براي انسان در زمان‌هاي نرمال (در حد عمر بشر) ممكن نيست. از طرفي بايد توجه داشت كه حتماً بين حالات مختلف مسئله بايد داراي پيوستگي مناسب و منطقي باشيم. در نهايت الگوريتم‌هاي ژنتيك اين امكان را به ما مي‌دهد كه داراي حركتي سريع در فضاي مسئله به سوي هدف باشيم. به گونه‌اي كه مي‌توانيم تصور كنيم كه در فضاي حالات مسئله به سوي جواب مشغول پرواز هستيم.
[1] Chromosome
[2] Gene
[3] Population
[4] Fitness Function
[5] Reproduction
[6] Generation
[7] Selection
[8] Crossover
[9] Mutation