الگوریتم ژنتیک
الگوریتم‌های ژنتیک، به عنوان یکی از راه‌حل‌های یافتن جواب مسئله در بین روش‌های مرسوم در هوش مصنوعی مطرح است. در حقیقت بدین روش می توانیم در فضای حالت مسئله حرکتی سریع‌تر برای یافتن جواب‌های احتمالی داشته باشیم؛ یعنی می توانیم با عدم بسط دادن کلیه حالات، به جواب‌های مورد نظر برسیم.
در جهان اطراف ما همه ارگانیزم‌های حیاتی از ساختارهای قانونمندی تشکیل شده‌اند. ساختارهایی که از سوی آفریدگار هستی در بطن مخلوقات قرار داده شده است. همه این ارگانیزم‌ها از بلوک‌های پایه‌ای از زندگی به نام سلول تشکیل به وجود آمده‌اند. قوانین مزبور در قالب ژن‌ها به صورت کد شده در هر ارگانیزم وجود دارند. از به هم وصل شدن این ژن‌ها، رشته‌هایی طولانی به نام کروموزوم تولید می‌شود. هر ژن نمایانگر یکی از خصوصیات آن ارگانیزم است.
مانند رنگ چشم یا رنگ مو و البته هر ژن می‌تواند دارای مقادیر مختلفی باشد. مثلاً در رابطه با رنگ چشم می‌توانیم دارای مقادیری متناظر با مشکی، قهوه‌ای و آبی و سبز و… باشیم. هنگامی که دو ارگانیزم به تولید مثل می‌پردازند، در حقیقت ژن‌های خود را با یکدیگر ترکیب می‌کنند. بدین صورت که ارگانیزم تولید شده که در این متن از این بعد آن را نوزاد می‌نامیم، دارای نیمی از ژن‌های یک والد و نیم دیگر از والد دیگری است. این عمل را ترکیب می‌نامیم. گاهی اوقات بعضی از ژن‌ها دارای جهش می‌شوند. این جهش تغییری در ساختار کروموزوم ایجاد نمی‌کند، اما با توجه به این‌که مقدار جدیدی به یک ژن تخصیص می‌یابد، موجب بروز خصوصیت جدیدی می‌شود. از این اتفاق با نام جهش یاد می‌کنیم.
برای استفاده از الگوریتم ژنتیک در برنامه‌هایتان ابتدا باید راهی بیابید تا حالات جواب مسئله خود را به صورت کد شده در قالب رشته‌ای از اعداد صحیح یا در فرم کلاسیک‌تر آن به صورت رشته‌ای از بیت‌ها نمایش دهید (هر رشته از بیت‌ها معادل یک کروموزوم یا یک ارگانیزم طبیعی است و هدف این است که به ارگانیزم بهتری، یعنی کرومزوم بهتری دست پیدا کنیم). بدین ترتیب جواب‌های شما به یکی از اشکال زیر خواهد بود.
۱۰۱۱۰۱۱۰۱۰۰۰۰۱۰۱۰۱۱۱۱۱۱۱۰
یا
۱۲۶۴۱۹۶۳۵۲۴۷۸۹۲۳۴۵۵۵۴۸۲۱۶
برای شروع فعالیت الگوریتم ژنتیک نیازمند جمعیتی از کروموزوم‌ها به صورت تصادفی هستیم. یعنی در ابتدا به عنوان قدم اول، تعدادی کروموزوم به صورت تصادفی ایجاد می کنیم. فرض کنید N کروموزوم و این N را جمعیت آغازین می‌نامیم.
در ادامه تابعی به نام تابع ارزش تشکیل می‌دهیم که این تابع به عنوان ورودی یک کرومزوم را دریافت می‌کند (یک جواب مسئله) و به عنوان خروجی عددی را مبتنی بر میزان بودن کرومزوم نسبت به جواب نهایی بر می‌گرداند. در حقیقت این تابع میزان خوب بودن جواب را مشخص می‌کند. برای همه نمونه‌های جمعیت مقدار تابع ارزش را حساب می‌کنیم.
در ادامه به صورت تصادفی دو نمونه از کرومزوم‌ها را انتخاب می‌کنیم. باید توجه داشته باشیم که سیستم به گونه‌ای طراحی شود که شانس انتخاب هر کرومزوم متناسب با مقدار تابع ارزش آن کروموزوم باشد. یعنی اگر کرومزومی دارای مقدار تابع ارزشی بهتری بود، شانس انتخاب شدن آن بیشتر باشد (بدین وسیله سعی می‌کنیم بیشتر روی پاسخ‌های بهتر مسئله پردازش انجام دهیم) این عمل دقیقاً معادل انتخاب طبیعت در داستان ماست (موجودات قوی‌تر شانس بیشتری برای بقا دارند).
بعد از انتخاب دو کرومزوم، اکنون نوبت به ترکیب می‌رسد. برای انجام عمل ترکیب، باید یک نقطه (نقطه شکست) در جفت کروموزوم خود را به صورت تصادفی انتخاب کنیم. هر کرومووزم را به دو پاره تقسیم می‌کنیم و در ادامه کمی جای هر پاره از هر کروموزوم را با دیگری عوض می‌کنیم. مانند شکل زیر:
شکسته شدن کروموزوم ها
بدین ترتیب دو کرومزوم جدید تولید می‌شود (دو جواب جدید). راه دیگری نیز برای انجام عمل ترکیب وجود دارد و آن انتخاب چند نقطه شکست است. مثلاً به شکل زیر برای ۲ نقطه شکست توجه کنید.
در هر حال ما باید یک روش را انتخاب کنیم و در طول پروژه عمل ترکیب خود را مبتنی بر آن روش انجام دهیم. بعد از انجام عملیات انتخاب و ترکیب، نوبت به عمل جهش ژن‌ها می‌رسد. عمل جهش باید با احتمال پایین رخ دهد. یعنیدر اکثر مواقع نباید دارای جهش باشیم، اما احتمال آن نیز نباید صفر باشد. بنابراین اگر کرومزوم به دست آمده از عملگر ترکیب دچار جهش شود، باید یکی از بیت‌های آن که متناظر با ژن‌های آن هستند، به صورت تصادفی انتخاب شود و سپس مقدار آن تغییر کند. اگر بخواهیم این موضوع را به صورت کلاسیک نشان دهیم، به صورت زیر خواهد بود:
نتیجه نهایی
