الگوریتم ژنتیک

[M!Zare 48037]

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

مختصراً گفته مي شود که الگوريتم ژنتيک (يا GA) يک تکنيک برنامه نويسي است که از تکامل ژنتيکي به عنوان يک الگوي حل مسئله استفاده مي کند.مسئله اي که بايد حل شود ورودي است و راه حلها طبق يک الگو کد گذاري مي شود و متريک که تابع fitness هم نام دارد هر راه حل کانديد را ارزيابي مي کندکه اکثر آنها به صورت تصادفي انتخاب مي شوند.

کلاً اين الگوريتم ها از بخش هاي زير تشکيل مي شوند :

تابع برازش - نمايش – انتخاب – تغيير

 

هنگامي كه لغت تنازع بقا به كار مي‌رود اغلب بار ارزشي منفي آن به ذهن مي‌آيد. شايد همزمان قانون جنگل به ذهن برسد و حكم بقاي قوي‌تر!

البته براي آنكه خيالتان راحت شود مي‌توانيد فكر كنيد كه هميشه هم قوي‌ترين‌ها برنده نبوده‌اند. مثلا دايناسورها با وجود جثه عظيم و قوي‌تر بودن در طي روندي كاملا طبيعي بازي بقا و ادامه نسل را واگذار كردند در حالي كه موجوداتي بسيار ضعيف‌تر از آنها حيات خويش را ادامه دادند. ظاهرا طبيعت بهترين‌ها را تنها بر اساس هيكل انتخاب نمي‌كند! در واقع درست‌تر آنست كه بگوييم طبيعت مناسب ترين‌ها (Fittest) را انتخاب مي‌كند نه بهترين‌ها.

قانون انتخاب طبيعي بدين صورت است كه تنها گونه‌هايي از يك جمعيت ادامه نسل مي‌دهند كه بهترين خصوصيات را داشته باشند و آنهايي كه اين خصوصيات را نداشته باشند به تدريج و در طي زمان از بين مي‌روند.

مثلا فرض كنيد گونه خاصي از افراد، هوش بسيار بيشتري از بقيه افراد يك جامعه يا كولوني دارند. در شرايط كاملا طبيعي اين افراد پيشرفت بهتري خواهند كرد و رفاه نسبتا بالاتري خواهند داشت و اين رفاه خود باعث طول عمر بيشتر و باروري بهتر خواهد بود(توجه كنيد شرايط طبيعيست نه در يك جامعه سطح بالا با ملاحظات امروزي يعني طول عمر بيشتر در اين جامعه نمونه با زاد و ولد بيشتر همراه است). حال اگر اين خصوصيت(هوش)ارثي باشد به طبع در نسل بعدي همان جامعه تعداد افراد باهوش به دليل زاد و ولد بيشتر اين‌گونه افراد بيشتر خواهد بود. اگر همين روند را ادامه دهيد خواهيد ديد كه در طي نسل‌هاي متوالي دائما جامعه نمونه ما باهوش و باهوش‌تر مي‌شود. بدين ترتيب يك مكانيزم ساده طبيعي توانسته است در طي چند نسل عملا افراد كم هوش را از جامعه حذف كند علاوه بر اينكه ميزان هوش متوسط جامعه نيز دائما در حال افزايش است(البته امكان داشت اگر داروين بي‌عرضگي افراد باهوش امروزي را مي‌ديد كمي در تئوري خود تجديد نظر مي‌كرد اما اين مسئله ديگريست!).

[M!Zare 48037]

بدين ترتيب مي‌توان ديد كه طبيعت با بهره‌گيري از يك روش بسيار ساده(حذف تدريجي گونه‌هاي نامناسب و درعين حال تكثير بالاتر گونه‌هاي بهينه) توانسته است دائما هر نسل را از لحاظ

خصوصيات مختلف ارتقا بخشد.

البته آنچه در بالا ذكر شد به تنهايي توصيف كننده آنچه واقعا در قالب تكامل در طبيعت اتفاق مي‌افتد نيست. بهينه‌سازي و تكامل تدريجي به خودي خود نمي‌تواند طبيعت را در دسترسي به

بهترين نمونه‌ها ياري دهد. اجازه دهيد تا اين مساله را با يك مثال شرح دهيم.

پس از اختراع اتومبيل به تدريج و در طي سال‌ها اتومبيل‌هاي بهتري با سرعت‌هاي بالاتر و قابليت‌هاي بيشتر نسبت به نمونه‌هاي اوليه توليد شدند. طبيعيست كه اين نمونه‌هاي متاخر حاصل

تلاش مهندسان طراح جهت بهينه‌سازي طراحي‌هاي قبلي بوده اند. اما دقت كنيد كه بهينه‌سازي يك اتومبيل تنها يك "اتومبيل بهتر" را نتيجه مي‌دهد.

اما آيا مي‌توان گفت اختراع هواپيما نتيجه همين تلاش بوده است؟ يا فرضا مي‌توان گفت فضا پيماها حاصل بهينه‌سازي طرح اوليه هواپيماها بوده‌اند؟

پاسخ اينست كه گرچه اختراع هواپيما قطعا تحت تاثير دستاورهاي صنعت اتومبيل بوده است اما به‌هيچ وجه نمي‌توان گفت كه هواپيما صرفا حاصل بهينه‌سازي اتومبيل و يا فضا پيما حاصل بهينه‌سازي هواپيماست. در طبيعت هم عينا همين روند حكم‌فرماست. گونه‌هاي متكامل‌تري وجود دارند كه نمي‌توان گفت صرفا حاصل تكامل تدريجي گونه قبلي هستند.

 

در اين ميان آنچه شايد بتواند تا حدودي ما را در فهم اين مساله ياري كند مفهوميست به نام : تصادف يا جهش.

به عبارتي طرح هواپيما نسبت به طرح اتومبيل يك جهش بود و نه يك حركت تدريجي. در طبيعت نيز به همين گونه‌است. در هر نسل جديد بعضي از خصوصيات به صورتي كاملا تصادفي تغيير مي‌يابند سپس بر اثر تكامل تدريجي كه پيشتر توضيح داديم در صورتي كه اين خصوصيت تصادفي شرايط طبيعت را ارضا كند حفظ مي‌شود در غير اين‌صورت به شكل اتوماتيك از چرخه طبيعت حذف مي‌گردد.

در واقع مي‌توان تكامل طبيعي را به اين‌صورت خلاصه كرد: جست‌وجوي كوركورانه(تصادف يا Blind Search)+ بقاي قوي‌تر.

[M!Zare 48037]

روش‌هاي كلاسيك رياضيات داراي دو اشكال اساسي هستند. اغلب اين روش‌ها نقطه بهينه محلي(Local Optima) را بعنوان نقطه بهينه كلي در نظر مي‌گيرند و نيز هر يك از اين روش‌ها تنها براي مساله خاصي كاربرد دارند. اين دو نكته را با مثال‌هاي ساده‌اي روشن مي‌كنيم.

به شكل زير توجه كنيد. اين منحني داراي دو نقطه ماكزيمم مي‌باشد. كه يكي از آنها تنها ماكزيمم محلي است. حال اگر از روش‌هاي بهينه‌سازي رياضي استفاده كنيم مجبوريم تا در يك بازه بسيار كوچك مقدار ماكزيمم تابع را بيابيم. مثلا از نقطه 1 شروع كنيم و تابع را ماكزيمم كنيم. بديهي است اگر از نقطه 1 شروع كنيم تنها به مقدار ماكزيمم محلي دست خواهيم يافت و الگوريتم ما پس از آن متوقف خواهد شد. اما در روش‌هاي هوشمند خاصه الگوريتم ژنتيك بدليل خصلت تصادفي آنها حتي اگر هم از نقطه 1 شروع كنيم باز ممكن است در ميان راه نقطه A به صورت تصادفي انتخاب شود كه در اين صورت ما شانس دست‌يابي به نقطه بهينه كلي (Global Optima) را خواهيم داشت.

در مورد نكته دوم بايد بگوييم كه روش‌هاي رياضي بهينه‌سازي اغلب منجر به يك فرمول يا دستورالعمل خاص براي حل هر مسئله مي‌شوند. در حالي كه روش‌هاي هوشمند دستورالعمل‌هايي هستند كه به صورت كلي مي‌توانند در حل هر مسئله‌اي به كار گرفته شوند. اين نكته را پس از آشنايي با خود الگوريتم بيشتر و بهتر خواهيد ديد.

[M!Zare 48037]

براي مثال اگر بخواهيم نوسانات قيمت نفت را با استفاده از عوامل خارجي وارزش رگرسيون خطي ساده مدل کنيم،اين فرمول را توليد خواهيم کرد:قيمت نفت در زمان t=ضريب 1 نرخ بهره در زمان t+ضريب 2 نرخ بيکاري در زمان t+ثابت 1 . سپس از يک معيار براي پيدا کردن بهترين مجموعه ضرايب و ثابت ها جهت مدل کردن قيمت نفت استفاده خواهيم کرد.در اين روش 2 نکته اساسي وجود دارد.اول اين روش خطي است و مسئله دوم اين است که ما به جاي اينکه در ميان "فضاي پارامترها"جستجو کنيم ،پارامترهاي مورد استفاده را مشخص کرده ايم.

با استفاده از الگوريتم هاي ژنتيک ما يک ابر فرمول يا طرح تنظيم مي کنيم که چيزي شبيه"قيمت نفت در زمان t تابعي از حداکثر 4 متغير است"را بيان مي کند. سپس داده هايي براي گروهي از متغيرهاي مختلف،شايد در حدود 20 متغير فراهم خواهيم کرد.سپس الگوريتم ژنتيک اجرا خواهد شد که بهترين تابع و متغيرها را مورد جستجو قرار مي دهد.روش کار الگوريتم ژنتيک به طور فريبنده اي ساده،خيلي قابل درک وبه طور قابل ملاحظه اي روشي است که ما معتقديم حيوانات آنگونه تکامل يافته اند.هر فرمولي که از طرح داده شده بالا تبعيت کند فردي از جمعيت فرمول هاي ممکن تلقي مي شود خيلي شبيه به اين که بگوييم جرج بوش فردي از جمعيت انسان هاي ممکن است.

متغير هايي که هر فرمول داده شده را مشخص مي کنند به عنوان يکسري از اعداد نشان داده شده اند که معادل دي ان اي آن فرد را تشکيل مي دهند.

موتور الگوريتم ژنتيک يک جمعيت آغاز از فرمول ايجاد مي کند.هر فرد در برابر مجموعه اي از داده ها ي مورد آزمايش قرار مي گيرند و مناسبترين آنها شايد 10 درصد از مناسبترين ها باقي مي مانند.بقيه کنار گذاشته مي شوند. مناسبترين افراد با هم جفتگيري (جابجايي عناصر دي ان اي)وتغيير(تغيير تصادفي عناصر دي ان اي) کرده اند.مشاهده مي شود که با گذشت از ميان تعدد ريادي از نسلها،الگوريتم ژنتيک به سمت ايجاد فرمول هايي که بيشتر دقيق هستند،ميل مي کنند.در حالي که شبکه هاي عصبي هم غير خطي و غير پارامتريک هستند،جذابيت زياد الگوريتم هاي ژنتيک اين است نتايج نهايي قابل ملاحظه ترند.فرمول نهايي براي کاربر انساني قابل مشاهده خواهد بود،و براي ارائه سطح اطمينان نتايج مي توان تکنيک هاي آماري متعارف رابر روي اين فرمول ها اعمال کرد.فناوري الگوريتم هاي ژنتيک همواره در حال بهبود استفبراي مثال با مطرح کردن معادله ويروس ها که در کنار فرمول ها وبراي نقض کردن فرمول ها ي ضعيف توليد مي شوندودر نتيجه جمعيت را کلاً قويتر مي سازند

[M!Zare 48037]

يک راه حل براي مسئله مورد نظر،با يک ليست از پارامترها نشان داده مي شود که به آنها کروموزوم يا ژنوم مي گويند.کروموزوم ها عموماً به صورت يک رشته ساده از داده ها نمايش داده مي شوند،البته انواع ساختمان داده هاي ديگر هم مي توانند مورد استفاده قرار گيرند.در ابتدا چندين مشخصه به صورت تصادفي براي ايجاد نسل اول توليد مي شوند. در طول هر نسل ،هر مشخصه ارزيابي مي شود وارزش تناسب(fitness) توسط تابع تناسب اندازه گيري مي شود.

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

براي هر فرد ،يک جفت والد انتخاب مي شود.انتخابها به گونه اي اند که مناسبترين عناصر انتخاب شوند تا حتي ضعيفترين عناصر هم شانس انتخاب داشته باشند تا از نزديک شدن به جواب محلي جلوگيري شود.چندين الگوي انتخاب وجود دارد: چرخ منگنه دار(رولت)،انتخاب مسابقه اي (Tournament) ،... .

معمولاً الگوريتم هاي ژنتيک يک عدد احتمال اتصال دارد که بين 0.6و1 است که احتمال به وجود آمدن فرزند را نشان مي دهد.ارگانيسم ها با اين احتمال با هم دوباره با هم ترکيب مي شوند.اتصال 2 کروموزوم فرزند ايجاد مي کند،که به نسل بعدي اضافه مي شوند.اين کارها انجام مي شوند تا اين که کانديدهاي مناسبي براي جواب،در نسل بعدي پيدا شوند. مرحله بعدي تغيير دادن فرزندان جديد است.الگوريتم هاي ژنتيک يک احتمال تغيير کوچک وثابت دارند که معمولاً درجه اي در حدود 0.01 يا کمتر دارد. بر اساس اين احتمال ،کروموزوم هاي فرزند به طور تصادفي تغيير مي کنند يا جهش مي يابند.مخصوصاً با جهش بيتها در کروموزوم ساختمان داده مان.

اين فرآيند باعث به وجود آمدن نسل جديدي از کروموزوم ها يي مي شود، که با نسل قبلي متفاوت است.کل فرآيند براي نسل بعدي هم تکرار مي شود،جفتها براي ترکيب انتخاب مي شوند،جمعيت نسل سوم به وجود مي آيندو... .

اين فرآيند تکرار مي شود تا اين که به آخرين مرحله برسيم.

شرايط خاتمه الگوريتم هاي ژنتيک عبارتند از:

• به تعداد ثابتي از نسل ها برسيم .
  
• بودجه اختصاص داده شده تمام شود(زمان محاسبه/پول).
  
• يک فرد(فرزند توليد شده) پيدا شود که مينيمم (کمترين)ملاک را برآورده کند.
  
• بيشترين درجه برازش فرزندان حاصل شود يا ديگر نتايج بهتري حاصل نشود.
  
• بازرسي دستي.
  
• ترکيبهاي بالا.
  

[M!Zare 48037]

ايده اصلي

در دهه هفتاد ميلادي دانشمندي از دانشگاه ميشيگان به نام جان هلند ايده استفاده از الگوريتم ژنتيك را در بهينه‌سازي‌هاي مهندسي مطرح كرد. ايده اساسي اين الگوريتم انتقال خصوصيات موروثي توسط ژن‌هاست. فرض كنيد مجموعه خصوصيات انسان توسط كروموزوم‌هاي او به نسل بعدي منتقل مي‌شوند. هر ژن در اين كروموزوم‌ها نماينده يك خصوصيت است. بعنوان مثال ژن 1 مي‌تواند رنگ چشم باشد ، ژن 2 طول قد، ژن 3 رنگ مو و الي آخر. حال اگر اين كروموزوم به تمامي، به نسل بعد انتقال يابد، تمامي خصوصيات نسل بعدي شبيه به خصوصيات نسل قبل خواهد بود. بديهيست كه در عمل چنين اتفاقي رخ نمي‌دهد. در واقع بصورت همزمان دو اتفاق براي كروموزوم‌ها مي‌افتد. اتفاق اول موتاسيون (Mutation) است. موتاسيون به اين صورت است كه بعضي ژن‌ها بصورت كاملا تصادفي تغيير مي‌كنند. البته تعداد اين گونه ژن‌ها بسيار كم مي‌باشد اما در هر حال اين تغيير تصادفي همانگونه كه پيشتر ديديم بسيار مهم است. مثلا ژن رنگ چشم مي‌تواند بصورت تصادفي باعث شود تا در نسل بعدي يك نفر داراي چشمان سبز باشد. در حالي كه تمامي نسل قبل داراي چشم قهوه‌اي بوده‌اند. علاوه بر موتاسيون اتفاق ديگري كه مي‌افتد و البته اين اتفاق به تعداد بسيار بيشتري نسبت به موتاسيون رخ مي‌دهد چسبيدن ابتداي يك كروموزوم به انتهاي يك كروموزوم ديگر است. اين مساله با نام Crossoverشناخته مي‌شود. اين همان چيزيست كه مثلا باعث مي‌شود تا فرزند تعدادي از خصوصيات پدر و تعدادي از خصوصيات مادر را با هم به ارث ببرد و از شبيه شدن تام فرزند به تنها يكي از والدين جلوگيري مي‌كند