الگوریتم ژنتیک (1)

http://www.ai-junkie.com/ga/intro/gat1.html

ابتدا ، یک درس زیست شناسی

هر ارگانیزمی از یک مجموعه قواعد پیروی می کند مانند یک طرح اولیه که توضیح می دهدچگونه این ارگانیزم از بلوکهای سازنده بسیار کوچک تشکیل شده است. این قواعد بصورت رمز در ژنهای یک ارگانیزم اسکه به نوبه خود با رشته های طویلی بنام کروموزم با یکدیگر مرتبط هستند. هر ژن بیانگر یک ویژگی ارگانیزم است مانند رنگ چشم یا رنگ مو و دارای  تنظیمات متعددی می باشد. برای مثال، تنظیمات برای یک ژن رنگ مو ممکن است بور، مشکی یا قهوه ای مایل به قرمز باشد. این ژنها و تنظیماتشان معمولا» بعنوان نژادمانه(یا سنخ ارثی) (genotype)نامیده می شوند. تجلی فیزیکی نژادمانه –خود ارگانیزم- رخ مانه (یا سنخ پدیداری) (phenotype) نامیده می شود.

هنگامی که دو ارگانیزم عمل جنسی می کنند ژنهایشان را به اشتراک می گذارند. فرزند منتجه ممکن است در نهایت نیمی از ژنهایش  از یک والد و نیمی دیگر از والد دیگرش باشد. این فرایند بازترکیب  (recombination) نامیده می شود.  دربسیاری موارد ژن ممکن است جهش (mutate) کند. معمولا» این ژن تغییر یافته بر تکامل رخ مانه تاثیری نمی گذارد بلکه دربسیاری موارد خود را در ارگانیزم بصورت یک ویژگی کاملا» جدید نشان می دهد.

زندگی روی زمین بتدریج از طریق فرایندهای انتخاب طبیعی ، بازترکیب و جهش، گسترش یافت تا باقی بماند. برای به تصویر کشاندن اینکه این فرایندها چگونه با هم کار می کنند تا دامنه متنوعی از گیاهان و جانورانی را تولید کند که سیاره مان را با آنها شریکیم بگذارید داستان کوتاهی را بگویم…

زمانی گونه ای از موجودات بنام دادزن ها (Hooters) زندگی می کردند. دادزن ها کلا» درمحدوده تاریکی از یک سامانه غاری وسیع که عمیقا» درون یک رشته کوه نهان شده بتدریج تکامل یافتند. آنها زندگی ساده ای را گذرانده اند، اطراف دیواره های غار مرطوب را احساس و بو می کشیدند تا جلبکی را که بسیار دوست داشتند بخورند، بین صخره ها لجنهایی از خود ترشح می کردند و در زمان جفتگیری، مشتاقانه به داد زدنهای سایر دادزن ها گوش می دادند. در این غارها هیچ شکارچی نبود که از دادزنها تغذیه کند؛ فقط دادزن ها و جلبکها بودند و گاهگاهی تنبل(slug) دوست داشتنی، بنابراین هیچگاه چیزی نبود که دادزن ها از آن بترسند(باستثنای گاهگاهی یک دادزن بداخلاق)و یک رود زیرزمینی از این سامانه غاری می گذشت و بطور مداوم آب ، قطر قطره از این سفره آبی به پایین چکه می کرد و مواد مغذی تازه ای همراه خود می آورد که سبب رشد جلبکها می شد . بهمین جهت همیشه مواد فراوانی برای خوردن و نوشیدن در دسترس بود. بهر حال، گرچه دادزن ها می توانستند احساس کنند و بشنوند در تاریکی قیرگون غارها هیچگاه نیازی به چشم نداشتند و بهمین دلیل کاملا» کور بودند. با وجود این  کوری آنها هیچگاه مایه نگرانیشان نبودو آنها اوقات خود را به خوشی درجویدن و داد زدن در تاریکی سپری می کردند.

تا اینکه یک روززمین لرزه ای سبب فروپاشی بخشی از سامانه غاری شد و برای نخستین بار در چندین هزار سال دادزن ها گرمی نور خورشید را بر پوستشان و نرمی و جهش خزه ها را زیر پایشان حس کردند . چند دادزن جسور خزه را مزه مزه کردند و دریافتند که خوردن خزه حتی بهتر ازجلبک غاری است.»اووووه!» آنها با دهانهای پر از خزه داد زدند و فورا» توسط عقابهای غارتگری که به آنجا پرواز کرده بودند ببینند اینهمه هیاهو برای چیست خورده شدند.

برای مدتی بنظر می رسید که دادزن ها تا حد انقراض نوعشان ممکن است شکار شوند، زیرا گرچه دادزن ها به خوردن خزه علاقه داشتند هیچگاه نمی توانستند بفهمند آیا عقابی بالای سرشان پرواز می کند یا نه. نه تنها این، آنها حتی نمی توانستند بفهمند که آیا زیر یک صخره پنهانند یا حتی با حسگرهایشان بفهمند این صخره  بقدر کافی پایین هست تا در دسترس باشد. هر روز دادزن های زیادی تلوتلو خوران از غارها بدنبال بوی شیرین خزه در بینی هایشان بیرون می آمدند تا بسرعت توسط عقابها ربوده و خورده شوند. وضعیت آنها واقعا» ترسناک بنظر می رسید.

خوشبختانه طی سالها، جمعیت دادزن ها در پناه غارها تا حد بیشماری رشد کرده بود و بقدر کافی از آنها برای جفتگیری باقی ماند- بالاخره، یک عقاب فقط می تواند تا حد معینی بخورد. یک روز، یک سری جوجه از دادزن ها متولد شد که در یک ژن سلولهای پوست جهش یافته شریک بودند. این ژن بخصوص  مسبب گسترش سلولهای پوستی بر پیشانی آنها بود. نوزادان دادزن درحین رشد، وقتی که این سولهای پوستی شان با دستورالعمل ژن تغییر یافته رشد کرد، اندکی به نور حساس شدند. هر نوزاد جدید دادزن کی توانست حس کند آیا چیزی جلوی نوری را که به پیشانیش می رسید گرفته یا نه. هنگامی که این نوزادان کوچک دادزن رشد کردند و دادزن های بالغی شدند و برای خوردن خزه  جرات می کردند زیر نور بروند می توانستند بفهمند آیا چیزی بالای سرشان بسرعت پایین می آید یا نه. بنابراین این دادزن ها شانس کمی بهتری برای بقا نسبت به عموزاده های کاملا» کورشان داشتند. و از آنجا که شانس بقای بهتری داشتند تولید مثل بیشتری کردند و بهمین دلیل ژن سلول پوستی حساس به نور را به نوزادان خود منتقل ساختند. و بعد ازمدت کوتاهی جمعیت این گونه، تحت تسلط داد زن هایی در آمد که این مزیت کوچک را داشتند.

حالا چندین هزار نسل در آینده را بررسی کنیم. اگراین فرایند را طی چندین و چند سال عمومیت دهید که بسیاری از تغییرات (mutations) کوچکی را که در ژن سلول پوستی روی داده است در بربگیرد می توان بسادگی فرایندی را مجسم نمود که یک سلول پوستی حساس به نور به انبوهی از سلولهای حساس به نور تبدیل شده و آنگاه سلولهای درونی این انبوهه ممکن است طوری تغییر کرده باشد که بصورت یک ناحیه بشکل عدسی های کوچک سخت شده است. که می تواند به گردا<ری نور و متمرکز سازی آن درون یک مکان کمک کند. خیالبافی در مورد تغییری که سبب شود دو ناحیه گردآوری نور بوجود آید زیاد مشکل نیست که سرانجام به دادزن ها دید دو چشمی بخشد. این یک مزیت بزرگ نسبت به عموزاده های یک چشمشان خواه بود زیرا دادزن ها حالا قادر به تشخیص دقیق فواصل هستند و میدان دید وسیعتری دارند.

همانطور که می بینید این فرایندهای انتخاب طبیعی -بقای شایستگان- و جهش ژن نقش بسیار قدرتمندی در تکامل تدریجی یک ارگانیزم بازی می کنند. اما چگونه بازترکیب در طرح نقشه چیزها گنجانده می شود؟ برای نشان دادن آن ناچارم درباره دادزن های دیگری بگویم…

در حدود همان زمان که دادزن ها با سلولهای پوستی حساس به نوردر میان خزه ها با شادی جست و خیز می کردند و عقابها را دست می انداختند، یکسری جوجه دیگر از دادزن ها متولد شده بودند که در یک ژن جهش یافته شریک بودندکه بر دادزدن آنها تاثیر می گذاشت. این جهش سبب شد که عضو دادزدن آنها کمی بزرگتر از عموزاده هایشان باشد و چون این عضو بزرگتر بود آنها حالا می توانستند در مسافت بزرگتری داد بزنند. معلوم شد که این در جمعیت بسرعت کاهنده دادزن ها مفید است زیرا دادزن های با عضو داد زدن بزرگترمی توانستند برای یافتن جفتهای بالقوه که دورتر بودند بلند تر داد بزنند. نه تنها آن ، بله  دادزن های ماده شروع کردند تا نرهای دادزن با عضو دادزدن بزرگتر را تا حدی ترجیح بدهند. سرانجام این رقابت این شد که دادزن هایی که از موهبت عضو دادزدن بلندتر برخوردار بودند شانس بهتری برای جفتگیری داشتند تا دادزن هایی که در دادزدن اینقدر خوب نبودند. طی مدت زمانی، دادزن های با عضو دادزدن بزرگتر در جمعیت بیشتر شدند.

تا اینکه یک روزیک دادزن ماده با ژن سلولهای پوستی حساس به نور با یک دادزن نر با ژن تولید کننده عضو دادزدن عظیم ملاقات کرد. آنها عاشق شدند و مدت کوتاهی بعد یکسری جوجه دوست داشتنی بدنیا آمدند. حالا، از آنجا که کروموزمهای نوزادان بازترکیبی از کروموزمهای هر دو والد بود، برخی از جوجه ها هر دو ژن خاص را داشتند و وقتی بالغ شدند نه تنها سلولهای پوستی حساس به نور را داشتند بلکه عضو دادزدن عظیمی هم داشتند! این جوجه های جدید در پرهیز از عقابها و تولید مثل بینهایت خوب بودند بنابراین فراین تکامل تدریجی آنها را مورد لطف قرار داد و یکبار دیگراین نوع بهبود یافته جدید از دادزن ها در جمعیت تسلط یافت.

و بهمین ترتیب و بهمین ترتیب ….

الگوریتم های ژنتیک روشی برای حل مسایل است از طریق تقلید از همین فرایندهایی که مادر طبیعت بکارمی گیرد. این الگوریتم ها همین ترکیب انتخاب ،بازترکیب و جهش را بکار می برند تا حل یک مساله را بتدریج تکامل دهند. جالب است نه؟

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

پیش از آنکه از الگوریتم ژنتیک برای حل یک مساله استفاده کنید، باید راهی بیابید که هر حل بالقوه مساله را به رمز (encode)در آورد. این می تواند یک رشته از اعداد حقیقی باشد، همانطور که در بیشترموارد هست، یک رشته بیت دودویی. از این پس از این رشته بیت بعنوان کروموزم نام می بریم.یک کروموزم ممکن است چنین بنظر برسد:

10010101110101001010011101101110111111101

(اگر هیچ یک از اینها در حال حاضر برای شما مفهومی ندارد نگران نشوید، بزودی همه چیز روشن می شود. حالا کاملا» آسوده مطلب را دنبال کنید.)

در ابتدا یکبار اجرای یک الگوریتم ژنتیک، جمعیت تصادفی  بزرگی از کروموزوم ایجاد می شود. هر یک، وقتی رمزگشایی می شوند راه حل متفاوتی برای مساله   ارائه می دهند.اگر N کروموزم در جمعیت اولیه باشندآنگاه گامهای زیر تکرار می شود تا وقتی که یک راه حل پیدا شود

  • هر کروموزم را تست کنید  تا مشخص شود چقدر برای حل مساله خوب است و مطابق با آن یک امتیازشایستگی می گیرد. امتیاز شایستگی، معیاری از میزان شایستگی آن کروموزم برای حل مساله مورد نظرمی باشد. 
  • دو عضو از جمعیت  فعلی انتخاب کنید. شانس انتخاب شدن متناسب با شایستگی کروموزمها است. انتخاب چرخ رولت(Roulette wheel) شیوه ای است که معمولا» مورد استفاده قرار می گیرد.
  • بسته به  نرخ تحول، بیتها را از هر کروموزم را در هر نقطه ای که بطور تصادفی انتخاب شده است انتقال دهید.
  • میان بیتهای کروموزم منتخب بروید و بسته به نرخ جهش معکوس کنید.
  • گامهای 2،3،4 را تا وقتی که جمعیت جدیدی به تعداد N ایجاد شود تکرار کنید.

درباره انتخاب چرخ رولت

این روشی برای انتخاب اعضا از جمعیت کروموزمها بطریقی است که متناسب با شایستگی آنها باشد. این روش تضمین نمی کند که  شایسته ترین عضو به نسل بعدی می رود، فقط چون این عضو شانس خوبی برای این کار دارد. بلکه به این شکل عملی می شود:

تصور کنید که کل امتیاز شایستگی جمعیت توسط یک نمودار کلوچه ای (Pie Chart) یا چرخ رولت نشان داده می شود. حالا شما برشی از چرخ را به  هر عضو جمعیت تخصیص می دهید. اندازه برش متناسب با امتیاز شایستگی کروموزم می باشد یعنی هر چه عضوشایسته تر باشد برش بزرگتری از کلوچه را می گیرد. حالا، برای انتخاب یک کروموزم تمام کاری که باید انجام دهید چرخش توپ است و گرفتن کروموزم در نقطه ای است که می ایستد.

نرخ تعویض چیست؟

این نرخ بسادگی، شانسی است که دو کروموزم بیتهایشان را با هم مبادله کنند. مقدار خوب برای این نرخ 0/7 می باشد. تعویض توسط انتخاب یک ژن تصادفی همراه با طول کروموزم و مبادله همه ژنها بعد از آن نقطه انجام می شود.  

برای مثال: برای دو کروموزم مفروض

10001001110010010

01010001001000011

یک بیت تصادفی همراه با طول، مثلا» در موقعیت 9، انتخاب کنیدو تمام بیتها را بعد از آن نقطه مبادله کنید. بنابراین خواهد شد:

10001001101000011

01010001010010010

نرخ جهش چیست؟

این شانسی است که یک بیت درون یک کروموزم معکوس شود(صفر  بشود یک ، یک بشود صفر). این نرخ برای ژنهای رمزنگاری شده دو دویی معمولا» بسیار کم است، مثلا» 0/001.

بنابراین هر وقت کروموزمی از جمعیت انتخاب می شود، الگوریتم ابتدا کنترل می کند تا ببیند آیا تعویض باید بکار رود و آنگاه الگوریتم به تعداد طول هر کروموزمی که سبب جهش بیتها می شود تکرار می شود البته در مواردی که قابلیت اجرای آن هست.

از تئوری تا عمل

برای اینکه این تئوری را بخوبی یاد بگیرید مثال ساده ای را بررسی می کنیم:

با فرض داشتن ارقام صفر تا نه و عملگرهای +، − ، × و ÷ ، دنباله ای را بیابید که بیانگر عدد هدف باشد. این عملگرها را می توان از چپ به راست همانطور که می خوانید بکار برد.

بنابراین با فرض اینکه عدد هدف 23 باشد، دنباله 2+1÷4×6+5می تواند یک راه حل ممکن باشد.

اگر 5/75 عدد منتخب باشد آنگاه 5−7×9 +2÷ 5 می تواند یک راه حل ممکن باشد.

لطفا» پیش از ادامه،مطمئن شوید که این مساله را فهمیده اید. استفاده از این مساله گرچه بنظر دستکاری شده است بدلیل سادگی درک آن است.

گام1: رمزنگاری

ابتدا نیازمند رمزنگاری کی راه حل ممکن بصورت رشته ای از بیتها… کروموزوم هستیم. خوب چطور این کار را می کنیم؟ ابتدا باید تمامی کاراکترهای مختلف موجود برای این راه حل را باید ارائه دهیم… یعنی ارقام صفر تا نه و عملگرهای +، − ، × و ÷ . این یک ژن را بیان می کند. هر کروموزم از چندین ژن تشکیل شده است.

چهار بیت برای نشان دادن دامنه کاراکترهای مورد استفاده لازم است:

صفر: 0000

یک: 0001

دو:0010

سه: 0011

چهار: 0100

پنج:1010

شش:0110

هفت: 0111

هشت:1000

نه:1001

+:1010

−:1011

×:1100

÷:1101

موارد بالا ، ژنهای مختلف لازم برای رمزنگاری مساله را نشان می دهد همانطور که تشریح شد. ژنهای ممکن 1110و 1111  بدون استفاده باقی می مانند و در صورت مواجهه ، الگوریتم آنها را نادیده می گیرد.

بنابراین حالا می توانید ببینید که راه حلی که در بالا برای 23ذکر شد،2+1÷4×6+5 با چهار ژن ارائه می شود مانند:

0110 1010 0101 1100 0100 1101 0010 1010 0001

 6        +        5        *        4         /        2        +       1

این ژنها همه با یکدیگر رشته ای را می سازند که کروموزم را تشکیل می دهد:

 011010100101110001001101001010100001

کوتاه درباره رمزنگاری

از آنجا که این الگوریتم با آرایشهای تصادفی بیتها سرو کار دارد اغلب به رشته ای نظیر این برمی خورد.

 011010100101110001001101001010100001

که پس از رمز گشایی ، این سه بیت بیانگر

0010 0010 1010 1110 1011 0111 0010

2        2        +        n/a     –        7        2

 که در متن این مساله بی معنا است! بنابراین ، در زمان رمزگشایی، الگوریتم هر ژنی را که با الگوی مورد انتظار:

عدد -> عملگر -> عدد -> عملگر

تطابق نداشته باشد نادیده می گیرد.. و بهمین ترتیب. پس با این فرض، کرومزووم بی معنای بالا چنین خوانده ( و تست) می شود.

 2+7

گام 2: تصمیم گیری بر سر مناسب ترین تابع

این می تواند مشکلترین بخش الگوریتم در یافتن راه حل باشد و واقعا» بستگی به مساله ای دارد کهدر تلاش برای حلش هستید ولی ایده کلی این است که هر چه کروموزم به حل مساله نزدیکتر باشد امتیاز برازش بیشتری را بگیرد. با توجه به پروژه ساده ای که در اینجا تشریح می کنیم، یک امتیاز برازش که تخصیص می یابد بطور معکوس متناسب با اختلاف بین حل و مقداری است که کروموزوم رمز گشایی شده ارائه می دهد.

اگر فرض کنیم عدد هدف برای باقیمانده این خود آموز 42 باشد، کروموزمی که در بالا مطرح شد

011010100101110001001101001010100001

امتیاز برازش  (23−42)÷1  یا 19÷1 دارد.

همانطور که مشخص است اگر مساله حل شود، یک تقسیم بر صفر یا خطای صفر رخ می دهد زیرا برازش  (42−42)÷1 می شود. بهر حال این مساله ای نیست چون ما آنچه را که می خواستیم بدست آوردیم… یک راه حل. بنابراین می توان برای این امر یک تست انجام داد و الگوریتم را مطابق با آن متوقف کرد.

گام 3: انجام عملی الگوریتم

ابتدا این خودآموز را دوباره مطالعه کنید. اگر احساس کردید الگوریتم را بخوبی درک کرده اید که این مساله را حل کنید توصیه می کنیم که خودتان الگوریتم ژنتیک را رمزنگاری کنید. از این بهتر راهی برای یادگیری نیست.

پاسخی بگذارید

در پایین مشخصات خود را پر کنید یا برای ورود روی شمایل‌ها کلیک نمایید:

نشان‌وارهٔ وردپرس.کام

شما در حال بیان دیدگاه با حساب کاربری WordPress.com خود هستید. بیرون رفتن /  تغییر دادن )

عکس گوگل

شما در حال بیان دیدگاه با حساب کاربری Google خود هستید. بیرون رفتن /  تغییر دادن )

تصویر توییتر

شما در حال بیان دیدگاه با حساب کاربری Twitter خود هستید. بیرون رفتن /  تغییر دادن )

عکس فیسبوک

شما در حال بیان دیدگاه با حساب کاربری Facebook خود هستید. بیرون رفتن /  تغییر دادن )

درحال اتصال به %s