Genetic Algorithm
الگوریتم‌های ژنتیک: تکنیک جستجو در علم رایانه برای یافتن راه‌حل تقریبی برای بهینه‌سازی مدل، ریاضی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتم‌های تکاملی است که از تکنیک‌های زیست‌شناسی فرگشتی مانند وراثت، جهش زیست‌شناسی و اصول انتخابی داروین برای یافتن فرمول بهینه جهت پیش‌بینی یا تطبیق الگو استفاده می‌شود. الگوریتم‌های ژنتیک اغلب گزینه خوبی برای تکنیک‌های پیش‌بینی بر مبنای رگرسیون هستند. در مدل‌سازی الگوریتم ژنتیک یک تکنیک برنامه‌نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده می‌کند. مسئله‌ای که باید حل شود دارای ورودی‌هایی می‌باشد که طی یک فرایند الگوبرداری شده از تکامل ژنتیکی به راه‌حل‌ها تبدیل می‌شود سپس راه حل‌ها به عنوان کاندیداها توسط تابع برازش یا تابع برازندگی (Fitness Function) مورد ارزیابی قرار می‌گیرند و چنانچه شرط خروج مسئله فراهم شده باشد الگوریتم خاتمه می‌یابد. به‌طور کلی یک الگوریتم مبتنی بر تکرار است که اغلب بخش‌های آن به صورت فرایندهای تصادفی انتخاب می‌شوند که این الگوریتم‌ها از بخش‌های تابع برازش، نمایش، انتخاب و تغییر تشکیل می‌شوند.
هنگامی که لغت تنازع بقا به کار می‌رود اغلب بار ارزشی منفی آن به ذهن می‌آید. شاید هم‌زمان قانون جنگل به ذهن برسد و حکم بقای قوی‌ترها!
البته همیشه هم قوی‌ترین‌ها برنده نبوده‌اند؛ مثلاً دایناسورها با وجود جثه عظیم و قویتر بودن در طی روندی کاملاً طبیعی بازیِ بقا و ادامه نسل را واگذار کردند در حالی که موجوداتی بسیار ضعیف‌تر از آن‌ها حیات خویش را ادامه دادند. ظاهراً طبیعت، بهترین‌ها را تنها بر اساس هیکل انتخاب نمی‌کند! در واقع درست‌تر آنست که بگوییم طبیعت مناسبترینها (Fittest) را انتخاب می‌کند.
قانون انتخاب طبیعی بدین صورت است که تنها گونه‌هایی از یک جمعیت ادامه نسل می‌دهند که بهترین خصوصیات را داشته باشند و آن‌هایی که این خصوصیات را نداشته باشند به تدریج و در طی زمان از بین می‌روند.
الگوریتم‌های ژنتیک یکی از الگوریتم‌های جستجوی تصادفی است که ایده آن برگرفته از طبیعت می‌باشد. الگوریتم‌های ژنتیک برای روش‌های کلاسیک بهینه‌سازی در حل مسائل خطی، محدب و برخی مشکلات مشابه بسیار موفق بوده‌اند ولی الگوریتم‌های ژنتیک برای حل مسائل گسسته و غیر خطی بسیار کاراتر می‌باشند. به عنوان مثال می‌توان به مسئله فروشنده دوره‌گرد اشاره کرد. در طبیعت از ترکیب کروموزوم‌های بهتر، نسل‌های بهتری پدید می‌آیند. در این بین گاهی اوقات جهش‌هایی نیز در کروموزوم‌ها روی می‌دهد که ممکن است باعث بهتر شدن نسل بعدی شوند. الگوریتم ژنتیک نیز با استفاده از این ایده اقدام به حل مسائل می‌کند.
روند استفاده از الگوریتم‌های ژنتیک به صورت زیر می‌باشد:
الف) معرفی جواب‌های مسئله به عنوان کروموزوم
ب) معرفی تابع برازندگی (فیت نس)
ج) جمع‌آوری اولین جمعیت
د) معرفی عملگرهای انتخاب
ه) معرفی عملگرهای تولید مثل
در الگوریتم‌های ژنتیک ابتدا به‌طور تصادفی یا الگوریتمیک، چندین جواب برای مسئله تولید می‌کنیم. این مجموعه جواب را جمعیت اولیه می‌نامیم. هر جواب را یک کروموزوم می‌نامیم. سپس با استفاده از عملگرهای الگوریتم ژنتیک پس از انتخاب کروموزوم‌های بهتر، کروموزوم‌ها را باهم ترکیب کرده و جهشی در آن‌ها ایجاد می‌کنیم. در نهایت نیز جمعیت فعلی را با جمعیت جدیدی که از ترکیب و جهش در کروموزوم‌ها حاصل می‌شود، ترکیب می‌کنیم.
مثلاً فرض کنید گونه خاصی از افراد، هوش بیشتری از بقیه افرادِ یک جامعه یا کولونی دارند. در شرایط کاملاً طبیعی، این افراد پیشرفت بهتری خواهند کرد و رفاه نسبتاً بالاتری خواهند داشت و این رفاه، خود باعث طول عمر بیشتر و باروری بهتر خواهد بود (توجه کنید شرایط، طبیعیست نه در یک جامعه سطح بالا با ملاحظات امروزی؛ یعنی طول عمر بیشتر در این جامعه نمونه با زاد و ولد بیشتر همراه است). حال اگر این خصوصیت (هوش) ارثی باشد بالطبع در نسل بعدی همان جامعه تعداد افراد باهوش به دلیل زاد و ولد بیشترِ این‌گونه افراد، بیشتر خواهد بود. اگر همین روند را ادامه دهید خواهید دید که در طی نسل‌های متوالی دائماً جامعه نمونه ما باهوش و باهوش‌تر می‌شود. بدین ترتیب یک مکانیزم ساده طبیعی توانسته‌است در طی چند نسل عملاً افراد کم هوش را از جامعه حذف کند علاوه بر اینکه میزان هوش متوسط جامعه نیز دائماً در حال افزایش است.
بدین ترتیب می‌توان دید که طبیعت با بهره‌گیری از یک روش بسیار ساده (حذف تدریجی گونه‌های نامناسب و در عین حال تکثیر بالاتر گونه‌های بهینه)، توانسته‌است دائماً هر نسل را از لحاظ خصوصیات مختلف ارتقاء بخشد.
البته آنچه در بالا ذکر شد به تنهایی توصیف‌کننده آنچه واقعاً در قالب تکامل در طبیعت اتفاق می‌افتد نیست. بهینه‌سازی و تکامل تدریجی به خودی خود نمی‌تواند طبیعت را در دسترسی به بهترین نمونه‌ها یاری دهد. اجازه دهید تا این مسئله را با یک مثال شرح دهیم:
پس از اختراع اتومبیل به تدریج و در طی سال‌ها اتومبیل‌های بهتری با سرعت‌های بالاتر و قابلیت‌های بیشتر نسبت به نمونه‌های اولیه تولید شدند. طبیعیست که این نمونه‌های متأخر حاصل تلاش مهندسان طراح جهت بهینه‌سازی طراحی‌های قبلی بوده‌اند. اما دقت کنید که بهینه‌سازی یک اتومبیل، تنها یک «اتومبیل بهتر» را نتیجه می‌دهد.
حال ببینیم که رابطه تکامل طبیعی با روش‌های هوش مصنوعی چیست. هدف اصلی روش‌های هوشمندِ به کار گرفته شده در هوش مصنوعی، یافتن پاسخ بهینه مسائل مهندسی است. به عنوان مثال اینکه چگونه یک موتور را طراحی کنیم تا بهترین بازدهی را داشته باشد یا چگونه بازوهای یک ربات را متحرک کنیم تا کوتاه‌ترین مسیر را تا مقصد طی کند (دقت کنید که در صورت وجود مانع یافتن کوتاه‌ترین مسیر دیگر به سادگی کشیدن یک خط راست بین مبدأ و مقصد نیست) همگی مسائل بهینه‌سازی هستند.
روش‌های کلاسیک ریاضیات دارای دو اشکال اساسی هستند. اغلب این روش‌ها نقطه بهینه محلی (Local Optima) را به عنوان نقطه بهینه کلی در نظر می‌گیرند و نیز هر یک از این روش‌ها تنها برای مسئله خاصی کاربرد دارند.
در مورد نکته دوم باید بگوییم که روش‌های ریاضی بهینه‌سازی اغلب منجر به یک فرمول یا دستورالعمل خاص برای حل هر مسئله می‌شوند. در حالی که روش‌های هوشمند دستورالعمل‌هایی هستند که به صورت کلی می‌توانند در حل هر مسئله‌ای به کار گرفته شوند. این نکته را پس از آشنایی با خود الگوریتم بیشتر و بهتر خواهید دید.
نحوه عملکرد الگوریتم ژنتیک روش کار الگوریتم ژنتیک به‌طور فریبنده‌ای ساده، قابل درک و به‌طور قابل ملاحظه‌ای روشی است که ما معتقدیم حیوانات آنگونه تکامل یافته‌اند. هر فرمولی که از طرح داده شده بالا تبعیت کند فردی از جمعیت فرمول‌های ممکن تلقی می‌شود. الگوریتم ژنتیک در انسان متغیرهایی که هر فرمول داده‌شده را مشخص می‌کنند به عنوان یکسری از اعداد نشان داده‌شده‌اند که معادل DNA آن فرد را تشکیل می‌دهند. موتور الگوریتم ژنتیک یک جمعیت اولیه این‌گونه است که هر فرد در برابر مجموعه‌ای از داده‌ها مورد آزمایش قرار می‌گیرد و مناسبترین آن‌ها باقی می‌مانند؛ بقیه کنار گذاشته می‌شوند. مناسبترین افراد با هم جفتگیری (جابجایی عناصر DNA) و (تغییر تصادفی عناصر DNA) کرده و مشاهده می‌شود که با گذشت از میان تعداد زیادی از نسل‌ها، الگوریتم ژنتیک به سمت ایجاد فرمول‌هایی که دقیقتر هستند، میل می‌کنند. در فرمول نهایی برای کاربر انسانی قابل مشاهده خواهد بوده و برای ارائه سطح اطمینان نتایج می‌توان تکنیک‌های آماری متعارف را بر روی این فرمول‌ها اعمال کرد که در نتیجه جمعیت را کلاً قویتر می‌سازند. الگوریتم ژنتیک درمدل سازی مختصراً گفته می‌شود که الگوریتم ژنتیک یک تکنیک برنامه‌نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده می‌کند. مسئله‌ای که باید حل شود دارای ورودی‌هایی می‌باشد که طی یک فرایند الگو برداری شده از تکامل ژنتیکی به راه حل‌ها تبدیل سپس راه حل‌ها به عنوان کاندید توسط تابع ارزیاب (fitness function) مورد ارزیابی قرار گرفته و چنانچه شرط خروج مسئله فراهم باشد الگوریتم خاتمه می‌یابد. در هر نسل، مناسبترینها انتخاب می‌شوند نه بهترین‌ها. یک راه‌حل برای مسئله مورد نظر، با یک لیست از پارامترها نشان داده می‌شود که به آن‌ها کروموزوم یا ژنوم می‌گویند. کروموزوم‌ها عموماً به صورت یک رشته ساده از داده‌ها نمایش داده می‌شوند، البته انواع ساختمان داده‌های دیگر هم می‌توانند مورد استفاده قرار گیرند. در ابتدا چندین مشخصه به صورت تصادفی برای ایجاد نسل اول تولید می‌شوند. در طول هر نسل، هر مشخصه ارزیابی می‌شود و ارزش تناسب (fitness) توسط تابع تناسب اندازه‌گیری می‌شود.
گام بعدی ایجاد دومین نسل از جامعه است که بر پایه فرایندهای انتخاب، تولید از روی مشخصه‌های انتخاب شده با عملگرهای ژنتیکی است: اتصال کروموزوم‌ها به سر یکدیگر و تغییر.
برای هر فرد، یک جفت والد انتخاب می‌شود. انتخاب‌ها به گونه‌ای‌اند که مناسبترین عناصر انتخاب شوند تا حتی ضعیفترین عناصر هم شانس انتخاب داشته باشند تا از نزدیک شدن به جواب محلی جلوگیری شود. چندین الگوی انتخاب وجود دارد: چرخ منگنه‌دار (رولت)، انتخاب مسابقه‌ای (Tournament) ،... .
معمولاً الگوریتم‌های ژنتیک یک عدد احتمال اتصال دارد که بین ۰٫۶ و ۱ است که احتمال به وجود آمدن فرزند را نشان می‌دهد. ارگانیسم‌ها با این احتمال دوباره با هم ترکیب می‌شوند. اتصال ۲ کروموزوم فرزند ایجاد می‌کند، که به نسل بعدی اضافه می‌شوند. این کارها انجام می‌شوند تا این که کاندیدهای مناسبی برای جواب، در نسل بعدی پیدا شوند. مرحله بعدی تغییر دادن فرزندان جدید است. الگوریتم‌های ژنتیک یک احتمال تغییر کوچک و ثابت دارند که معمولاً درجه‌ای در حدود ۰٫۰۱ یا کمتر دارد. بر اساس این احتمال، کروموزوم‌های فرزند به‌طور تصادفی تغییر می‌کنند یا جهش می‌یابند، مخصوصاً با جهش بیت‌ها در کروموزوم ساختمان داده‌مان.
این فرایند باعث به وجود آمدن نسل جدیدی از کروموزوم‌هایی می‌شود، که با نسل قبلی متفاوت است. کل فرایند برای نسل بعدی هم تکرار می‌شود، جفت‌ها برای ترکیب انتخاب می‌شوند، جمعیت نسل سوم به وجود می‌آیند و … این فرایند تکرار می‌شود تا این که به آخرین مرحله برسیم.
شرایط خاتمه الگوریتم‌های ژنتیک عبارتند از:
به تعداد ثابتی از نسل‌ها برسیم.
بودجه اختصاص داده‌شده تمام شود (زمان محاسبه/پول).
یک فرد (فرزند تولید شده) پیدا شود که مینیمم (کمترین) ملاک را برآورده کند.
بیشترین درجه برازش فرزندان حاصل شود یا دیگر نتایج بهتری حاصل نشود.
بازرسی دستی.
ترکیب‌های بالا.
روش‌های نمایش
قبل از این که یک الگوریتم ژنتیک برای یک مسئله اجرا شود، یک روش برای کد کردن ژنوم‌ها به زبان کامپیوتر باید به کار رود. یکی از روش‌های معمول کد کردن به صورت رشته‌های باینری است: رشته‌های ۰ و ۱. یک راه حل مشابه دیگر کد کردن راه حل‌ها در آرایه‌ای از اعداد صحیح یا اعداد اعشاری است. سومین روش برای نمایش صفات در یک GA یک رشته از حروف است، که هر حرف دوباره نمایش دهنده یک خصوصیت از راه حل است. خاصیت هر سه روش این است که آن‌ها تعریف سازنده‌ای را که تغییرات تصادفی در آن‌ها ایجاد می‌کنند را آسان می‌کنند: ۰ را به ۱ و برعکس، اضافه یا کم کردن ارزش یک عدد یا تبدیل یک به صفر یا برعکس. یک روش دیگر که توسط John Koza توسعه یافت، برنامه‌نویسی ژنتیک است؛ که برنامه‌ها را به عنوان شاخه‌های داده در ساختار درخت نشان می‌دهد. در این روش تغییرات تصادفی می‌توانند با عوض کردن عملگرها یا تغییر دادن ارزش یک گره داده شده در درخت، یا عوض کردن یک زیر درخت با دیگری به وجود آیند.
