ژنتیک الگوریتم
نام پروژه: ژنتیک الگوریتم
نوع پروژه: ریاضی
درجه سختی: دشوار
هدف پروژه: هدف این پروژه آشنا نمودن شما با الگوریتم ژنتیک برای بهینه سازی مسائل می باشد.
خلاصه پروژه: در این پروژه ابتدا شما را با ایده اولیه الگوریتم ژنتیک آشنا می کنیم، سپس از آن برای حل یک مثال استفاده خواهید نمود و در نهایت یک برنامه کامپیوتری برای بهینه سازی از طریق الگوریتم ژنتیک تولید خواهید نمود.
پیش نیاز: مطالعه پروژه بهینه سازی
وسائل مورد نیاز: قلم و کاغذ
1- تعریف مسئله دانش آموز پر کار:
در ابتدا یک مسئله ی بهینه سازی را که قید هم دارد، «تعریف» می کنیم. تعریف یک مسئله یعنی این که تعیین کنیم: «متغیر های مسئله چه هستند؟ قید مسئله چیست؟ هدف چیست؟» و هدف را به صورت تابعی از متغیر ها بنویسیم، که به آن «تابع هدف» می گوییم. مسئله ی تعیین کردن بهترین راه برای رفت و آمد از خانه به مدرسه را به صورت زیر می توان تعریف کرد:
یک دانش آموز می خواهد از خانه به مدرسه برود و بعد باز گردد، اما او تعداد مشخصی کار، مثلاً 1-n کار دیگر هم در این بین دارد، یعنی باید به 1-n جا سر بزند. بدین ترتیب دانش آموز باید از خانه خارج شود، با در نظر گرفتن مدرسه به n جای مشخص شهر برود و سر انجام به خانه باز گردد. مکان جغرافیایی خانه، مدرسه و نقاط دیگر مشخص است. بنا بر این این دانش آموز از خانه خارج می شود و از تمام n نقطه می گذرد، و البته مقداری از وقت خود را در مدرسه خواهد بود، مسئله این است که کوتاه ترین مسیر برای عبور از همه ی نقاط چیست؟
برای راحتی نام این مسئله را «مسئله دانش آموز پر کار» می گذاریم. مثلاً به شکل زیر توجه کنید؛ دانش آموز می خواهد از خانه (محل 0) به مدرسه (محل 1) برود، یک کتاب را هم می خواهد به کتابخانه ی محله (محل 2) پس بدهد، با هم کلاسی ها می خواهد یک سری هم به پارک (محل 3) بزند، یک خط کش هم می خواهد از لوازم التحریری (محل 4) بخرد، یک نامه پست (محل 5) کند و البته برای خانه از بقالی سر کوچه (محل 6) چیز هایی بخرد. فعلاً فرض می کنیم که فرقی نمی کند که این کار ها بعد یا قبل از مدرسه انجام شود:
یعنی دانش آموز از خانه به نقطه ی 4 حرکت می کند، آن گاه به ترتیب، به مکان های 3، 6، 5 و 1 می رود و سپس به خانه بر می گردد. شکل بالا در واقع یک «جواب ممکن» مسئله است. ما قصد داریم که بهترین جواب را از میان جواب های ممکن به دست بیاوریم.
1-2- قید مسئله:
مسئله ی «دانش آموز پر کار» بسیار شبیه به مسئله ی «فروشنده ی دوره گرد» است. در زیر شرح داده شده است: در منطقه ای که n شهر وجود دارد، و بین همه ی شهر ها جاده وجود دارد و فاصله ی هر دو شهر مشخص است، فروشنده ای دوره گرد قصد دارد محصولات خود را در تمام این n شهر عرضه کند و به فروش برساند. به این منظور قصد دارد از یک شهر حرکت خود را آغاز کرده و از تمام این شهر ها بگذرد و به شهر اول باز گردد، به طوری که از هیچ شهری دو بار عبور نکند. حال مسئله این است که کوتاه ترین مسیر ممکن کدام است؟
اگر گفتید که فرق این دو مسئله چیست؟
مسئله ی دانش آموز پر کار در واقع یک «قید» دارد، در حالی که مسئله ی فروشنده ی دوره گرد قید ندارد، قید مسئله ی اول این است که نقطه ی شروع و پایان حرکت دانش آموز معلوم است. یعنی اگر به شکل 2 نگاه کنید، می بینید که مرحله ی اول و آخر جواب همه ی جواب های ممکن نقطه ی 0 یا همان خانه است، که با رنگ دیگر نشان داده شده است.
1-3- تابع هدف:
تابع هدف در واقع طول مسیر حرکت است که می خواهیم «کمینه ی» آن را پیدا کنیم. برای محاسبه ی طول مسیر انتخاب شده، باید روی مسیر از خانه شروع به حرکت کرد و فاصله ی هر دو مکان متوالی را با استفاده از رابطه فاصله دو نقطه در مختصات دکارتی به دست آورد و همه را با هم جمع کرد.
2- آشنایی با الگوریتم ژنتیک و چند اصطلاح:
الگوریتم ژنتیک یکی از روش های راهنمونی است که از نظریه ی تکامل زیستی الهام گرفته شده است و بر این پایه استوار است که موجودات در طبیعت، همواره به سمت بهتر و متکامل تر شدن پیش می روند. در ابتدا لازم است کلماتی را که در این روش به کار می روند، تعریف کنیم:
- ژن: پروتئینی است که یکی از ویژگی های یک موجود را در بر دارد، مثلاً رنگ چشم.
- کروموزوم: به مجموعه ی ژن های موجود در یک سلول موجود زنده کروموزوم گفته می شود که تمام ویژگی های وراثتی آن موجود را در بر می گیرد. تمام سلول های یک موجود زنده، دارای کروموزوم های دقیقاً مشابه می باشند.
- تولید مثل: یکی از توانایی های حیاتی موجودات زنده است. به وجود آمدن موجود جدیدی به وسیله دو موجود نر و ماده به طوری که موجود جدید (فرزند) برخی از خواص را از پدر و برخی را از مادر به ارث می برد.
- ترکیب ژنتیکی: عملیات شکسته شدن دو کروموزوم و تولید یک یا چند کروموزوم جدید را ترکیب ژنتیکی می گویند.
- جهش ژنتیکی: عبارت است از تغییری کوچک و جزئی در یک کروموزوم در ترکیب ژنتیکی به دلیل عوامل محیطی.
- شانس بقا: میزان مطابقت یک موجود با محیط زیست را می رساند.
2-1: ایده ی الگوریتم ژنتیک:
در این قسمت ایده ی این روش به طور کلی توضیح داده می شود و در بخش بعدی آن را برای مسئله ی دانش آموز پر کار به کار می گیریم.
در ابتدای کار، تعدادی موجود با ژن های تصادفی به وجود می آوریم که احتمالاً موجودات ضعیفی خواهند بود. در میان آن ها، موجوداتی که از همه ضعیف تر هستند، به دلایلی (از جمله از بین رفتن توسط موجودات کمی قوی تر و یا عوامل محیط از بین خواهند رفت و سایر موجودات با انجام عمل تولید مثل، نسل بعد را به وجود خواهند آورد. از آن جایی که معمولاً موجودات قوی تر (یعنی دارای شانس بقای بیشتر) تولید نسل بعد را انجام می دهند، پس نسل جدید کمی بهتر از نسل قبل خواهد بود. همچنین احتمال وقوع جهش ژنتیکی در هنگام تولید مثل و ایجاد فرزندی که تفاوت های زیادی با پدر و مادر وجود دارد. در صورتی که این موجود، ضعیف و ناقص الخلقه باشد، از بین خواهند رفت و در صورت قوی بودن، تولید مثل خواهد کرد و نوع خود را گسترش خواهد داد.
باز در میان نسل جدید به وجود آمده، همین اتفاق می افتد و به همین ترتیب موجودات قوی تر و قوی تر می شوند. بنا بر این فلو چارت الگوریتم به صورت زیر قابل ترسیم است:
3- استفاده از الگوریتم ژنتیک برای حل مسئله ی دانش آموز پر کار:برای مثال، مسئله را برای 6 مکانی که در بخش قبل تعریف کرد یم، حل می کنیم. یعنی باید مراحل الگوریتم را برای مسئله ای که داریم پیاده سازی کنیم.
ساختار کروموزوم هر فرد:
کروموزوم هر فرد، آرایه ای به طول 6 است و در هر خانه آن عددی بین 1 تا 6 قرار دارد و هیچ عددی دو بار تکرار نمی شود. البته دو خانه هم در ابتدا و انتها برای نشان دادن این که دانش آموز از خانه شروع می کند و سر انجام به خانه بر می گردد، وجود دارد.
کروموزوم بالا یعنی دانش آموز از خانه خارج می شود و ابتدا به مکان 4 می رود، آن گاه به ترتیب، به مکان های 3، 6، 2، 1 و 5 رفته و سپس به خانه بر می گردد.
یک راه حل پیشنهادی برای ترکیب ژنتیکی:
می خواهیم از ترکیب ژنتیکی کروموزوم های 1 و 2، دو فرزند حاصل شود. برای تشکیل کروموزوم فرزند اول، نیمه ی اول کروموزوم 1 را در نیمه ی اول کروموزوم فرزند اول قرار می دهیم و برای تشکیل نیمه دوم، از ابتدای کروموزوم دوم شروع می کنیم و هر خانه ای را که عدد درون آن، در نیمه ی اول کروموزوم فرزند نیامده بود، به نیمه ی دوم کروموزوم فرزند اضافه می کنیم و مثل همین کار را برای ساخت کروموزوم فرزند دوم انجام می دهیم. یعنی نیمه ی اول کروموزوم 2 را در نیمه ی اول کروموزوم فرزند دوم قرار می دهیم و...
توجه کنید که در این فرایند و همین طور در مورد فرایند های بعدی، دو خانه ی اول و آخر کروموزوم که نماینده ی نقطه ی شروع و پایان حرکت هستند، به هیچ وجه تغییر نمی کنند و هر بلایی که سر کروموزوم می آید، تنها برای خانه های میانی است. در واقع با این روش، قید مسئله را اعمال می کنیم.
جهش ژنتیکی می تواند به این صورت باشد که جای دو تا از خانه های کروموزوم فرد به صورت تصادفی با هم عوض شود.
شانس بقا = یک تقسیم بر طول مسیر انتخاب شده
برای محاسبه ی طول مسیر انتخاب شده، باید روی مسیر از مکان شماره ی 0 شروع به حرکت کرد و فاصله ی هر دو مکان متوالی را با استفاده از رابطه ی فاصله دو نقطه در مختصات دکارتی به دست آورد و همه را با هم جمع نمود. دقت کنید که باید فاصله ی بین مکان 0 با خانه ی اول کروموزوم و همین طور فاصله ی خانه ی آخر کروموزوم با مکان 0 را هم حساب کرد.
یک راه حل پیشنهادی برای انتخاب اصلح:
پس از محاسبه ی شانس بقای هر فرد (کروموزوم)، برای تولید نسل آینده، باید والدین اصلح (دارای شانس بقای بیشتر) انتخاب شوند. برای تولید هر فرزند، دو نفر از نسل های قبل انتخاب می کنیم به طوری که هر چه شانس بقای فرد بیشتر باشد، احتمال انتخاب او نیز بیشتر شود.
فرض کنید که یک جمعیت 5 نفره داریم که شانس بقای آن ها بصورت زیر است:
این وضعیت را می توان به صورت زیر در جدول زیر نمایش داد که در آن 3 خانه به فرد اول، 7 خانه به فرد دوم و... اختصاص داده شده است. حال اگر عددی تصادفی بین 1 تا 17 (مجموع شانس های بقا در این مثال) انداخته شود و عدد درون آرایه ی مربوط به آن خوانده شود، یک فرد برای شرکت در تولید نسل بعد انتخاب می شود. مسلماً هر چه شانس بقای فرد بیشتر باشد، خانه های بیشتری از جدول را به خود اختصاص خواهد داد، پس احتمال انتخاب او نیز بیشتر خواهد شد. اگر هم یک کروموزوم بیش از یک بار انتخاب شود، اشکالی ندارد. چون وجود چند نمونه از یک کروموزوم قوی تر، به بهتر شدن نسل بعدی کمک می کند.
4- برنامه ی رایانه ای برای حل مسئله ی دانش آموز پر کار:
حالا می توانیم شروع کنیم به نوشتن برنامه ی حل مسئله ی دانش آموز پر کار به روش الگوریتم ژنتیک، «شبه کد» برنامه ای که باید بنویسید در زیر آمده است و بعد از آن هم متغیر ها و توابع اصلی تعریف شده اند. برای بیشتر شدن وضوح شبه کد، متغیر ها و توابع با رنگ های متفاوت نشان داده شده اند. برای مشاهده ی آن فایل مورد نظر را دانلود کنید
دانلود متغیر ها و توابعتکلیف: برنامه کامل تولید شده را برای ما ارسال کنید
منابع مطالعه: کتب ژنتیک الگوریتم بهینه سازی مهندسی – موسی حسینی- نشر گوتنبرگ
