الگوریتم ژنتیک ، (GA | Genetic Algorithms)، خانواده‌ای از «مدل‌های محاسباتی»
(Computational Models) است که از مفهوم «تکامل» (Evolution) الهام گرفته شده‌اند.
این دسته از الگوریتم‌ها، «جواب‌های محتمل» (Potential Solutions) یا «جواب‌های کاندید»
(Candidate Solutions) و یا «فرضیه‌های محتمل» (Possible Hypothesis) برای یک مسأله خاص
را در یک ساختار داده‌ای «کروموزوم مانند» (Chromosome-like) کدبندی می‌کنند. الگوریتم ژنتیک
از طریق اعمال «عملگرهای بازترکیب» (Recombination Operators) روی ساختارهای داده‌ای
کروموزوم مانند، اطلاعات حیاتی ذخیره شده در این ساختارهای داده‌ای را حفظ می‌کند.
در بسیاری از موارد، ازالگوریتم ژنتیک ، به عنوان الگوریتم‌های «بهینه‌ساز تابع» (Function Optimizer)
یاد می‌شود؛ یعنی، الگوریتم‌هایی که برای بهینه‌سازی «توابع هدف» (Objective Functions) مسائل مختلف
به کار می‌روند. البته، گستره کاربردهایی که از الگوریتم ژنتیک، برای حل مسئله در دامنه کاربردی خود استفاده می‌کنند، بسیار وسیع است.
پیاده‌سازی الگوریتم ژنتیک، معمولا با تولید جمعیتی از کروموزوم‌ها (جمعیت اولیه از کروموزوم‌ها در
الگوریتم‌های ژنتیک، معمولا تصادفی تولید می‌شود و مقید به حد بالا و پایین متغیرهای مسأله هستند) آغاز می‌شود.
در مرحله بعد، ساختارهای داده‌ای تولید شده (کروموزوم‌ها) «ارزیابی» (Evaluate) می‌شوند و کروموزوم‌هایی که
به شکل بهتری می‌توانند «جواب بهینه» (Optimal Solution) مسأله مورد نظر (هدف) را نمایش دهند،
شانس بیشتری برای «تولید مثل» (Reproduction) نسبت به جواب‌های ضعیف‌تر پیدا می‌کنند.
به عبارت دیگر، فرصت‌های تولید مثل بیشتری به این دسته از کروموزوم‌ها اختصاص داده می‌شود.
میزان «خوب بودن» (Goodness) یک جواب، معمولا نسبت به جمعیت جواب‌های کاندید فعلی سنجیده می‌شود.
مقدمه
بسیاری از اختراعات بشری از طبیعت الهام گرفته شده‌اند. «شبکه‌های عصبی مصنوعی»
(ANN | Artificial Neural Network) نمونه بارز چنین ابداعاتی هستند. یکی دیگر از چنین ابداعاتی،
توسعه ایده الگوریتم ژنتیک ، است. الگوریتم‌های ژنتیک، با «شبیه‌سازی» (Simulating) فرایند تکامل
در طبیعت، با هدف یافتن بهترین جواب ممکن برای یک مسأله، به جستجو در «فضای جواب‌های کاندید»
(Candidate Solution Space) می‌پردازند. در فرایند جستجو برای یافتن جواب بهینه، ابتدا مجموعه
یا جمعیتی از جواب‌های ابتدایی تولید می‌شود. سپس، در «نسل‌های» (Generations) متوالی، مجموعه‌ای
از جواب‌های تغییر یافته تولید می‌شوند (در هر نسل از الگوریتم ژنتیک، تغییرات خاصی در ژن‌های کروموزوم‌های
تشکیل دهنده جمعیت ایجاد می‌شود). جواب‌های اولیه معمولا به شکلی تغییر می‌کنند که در هر نسل،
جمعیت جواب‌ها به سمت جواب بهینه «همگرا» (Converge) می‌شوند.
این شاخه از حوزه «هوش مصنوعی» (Artificial Intelligence)، بر پایه مکانیزم تکامل موجودات زنده
و تولید گونه‌های موفق‌تر و برازنده‌تر در طبیعت الهام گرفته شده است. به عبارت دیگر، ایده اصلی
انتخاب طبیعی
در طبیعت، موجوداتی که ویژگی‌های برازنده‌تری نسبت به دیگر گونه‌ها دارند،
برای مدت بیشتری به بقاء در طبیعت ادامه می‌دهند. چنین ویژگی‌ای، این امکان را در
اختیار برازنده‌ترین موجودات زنده قرار می‌دهد تا بر اساس مواد ژنتیکی خود، اقدام به تولید مثل کنند.
بنابراین، پس از یک دوره زمانی بلند مدت، جمعیت موجودات زنده به سمتی تکامل پیدا خواهد کرد
که در آن، غالب موجودات بسیاری از ویژگی‌های ارثی خود را از «ژن‌های» (Genes) موجودات برتر
و تعداد کمی از ویژگی‌های خود را از ژن‌های موجودات «رده پایین» (Inferior) با ژنها یا ویژگی‌های نامرغوب به ارث خواهند برد.
به بیان ساده‌تر، موجودات برازنده‌تر زنده می‌مانند و موجودات نامناسب از بین می‌روند. به این فرایند و
نیروی شگفت‌انگیز طبیعی، «انتخاب طبیعی» (Natural Selection) گفته می‌شود. نکته مهم در مورد
انتخاب طبیعی و اثبات درست بودن این اصل این است که تحقیقات دانشمندان در مورد «توضیحات مولکولی
از تکامل» (Molecular Explanation of Evolution) نشان داده است که گونه‌های مختلف موجودات زنده،
خود را با شرایط محیطی تطبیق نمی‌دهند، بلکه صرفا موجودات برازنده‌تر به بقاء خود ادامه می‌دهند.
با توجه به اهمیت روش‌های بهینه‌سازی هوشمند و الگوریتم‌های تکاملی، «فرادرس» اقدام به انتشار فیلم آموزش
تئوری و عملی الگوریتم ژنتیک در قالب آموزشی ۱۴ ساعت و ۲۳ دقیقه‌ای کرده که در ادامه متن به آن اشاره شده است.
تکامل شبیه‌سازی شده
برای شبیه‌سازی فرایند انتخاب طبیعی توسط سیستم‌های کامپیوتری و حل مسأله با استفاده
از الگوریتم‌های الهام گرفته شده از انتخاب طبیعی، ابتدا باید مدل‌های نمایشی جهت مدل‌سازی متغیرهای مسأله تعریف شوند:
- نمایشی از یک «موجودیت» (Individual) در هر نقطه از فضای جستجوی مسأله در طول فرایند
- جستجو برای یافتن جواب بهینه: برای چنین کاری، مفهوم «نسل‌های» (Generation) متوالی از
- موجودیت‌ها مطرح می‌شود. هر موجودیت یک ساختار داده‌ای خواهد بود که «ساختار ژنتیکی»
- (Genetic Structure) یک جواب یا فرضیه محتمل/کاندید را نمایش می‌دهد. همانند یک کروموزوم،
- ساختار ژنتیکی یک موجودیت توسط الفبایی ثابت و محدود توصیف خواهد شد. به عنوان نمونه، الگوریتم
- ژنتیک از الفبای مبتنی بر رشته‌های «باینری» (Binary)، «مقادیر صحیح» (Integer Values) یا «مقادیر
- حقیقی» (Real Values) به عنوان تفسیری از جواب‌های محتمل برای یک مسأله خاص استفاده می‌کند.
به عنوان نمونه، مسأله «فروشنده دورهگرد» (Travelling Salesman) یا TSP را در نظر بگیرید. مسأله
فروشنده دور‌گرد، مسأله پیدا کردن مسیر بهینه برای پیمایش مثلا 10 شهر است. فروشنده می‌تواند مسیر
پیمایشی خود را از هر شهری شروع کند. بنابراین، جواب‌های این مسأله «جایگشتی» (Permutation) از شهرهای پیمایش شده خواهد بود
فرهنگ لغات الگوریتم ژنتیک
در ادامه، برخی از اصطلاحات و واژگان کلیدی در توصیف فرایندهای موجود در الگوریتم
ژنتیک نمایش داده شده است. نکته مهم در مورد فرهنگ لغات الگوریتم ژنتیک این است
که اصطلاحات و واژگان کلیدی مترادف و معادل یکدیگر، در زمینه‌های موضوعی
مرتبط با الگوریتم ژنتیک، غالبا به جای یکدیگر مورد استفاده قرار می‌گیرند.
عملگرهای الگوریتم ژنتیک
عملیات بهینه‌سازی در الگوریتم ژنتیک، با یک تولید جمعیت اولیه از «رشته‌های تصادفی»
(Random Strings) آغاز می‌شود (این رشته‌ها معادل کروموزوم‌ها یا موجودیت‌ها یا جواب‌های
کاندید مسأله هستند). رشته‌های تصادفی، طراحی مسأله یا به عبارت دیگر،
«متغیرهای تصمیم» (Decision Variables) مرتبط با یک مسأله را نمایش می‌دهند.
سپس، جمعیت اولیه تحت تأثیر سه دسته عملگر اصلی در الگوریتم ژنتیک قرار می‌گیرند
تا جمعیت جدیدی از نقاط در فضای جواب مسأله تولید شود؛ جمعیت جدید، متشکل از
کروموزوم‌ها یا موجودیت‌ها یا جواب‌های جدید خواهد بود. عملگرهای اصلی الگوریتم
ژنتیک عبارتند از: عملگر تولید مثل، عملگر ترکیب یا آمیزش و عملگر جهش.
همانطور که پیش از این نیز اشاره شد، الگوریتم ژنتیک را می‌توان به عنوان مکانیزمی جهت
بیشینه‌سازی تابع هدف در نظر گرفت. این کار، از طریق از طریق ارزیابی کروموزوم‌ها یا بردارهای
جواب انجام می‌شود. هدف عملگرهای اصلی در الگوریتم ژنتیک، انتخاب، ترکیب و تغییر بردارهای
متناظر با جواب‌هایی است که در نسل کنونی، بهترین جواب برای مسأله بهینه‌سازی محسوب می‌شوند.
از این طریق، جمعیت جدیدی از کروموزوم‌ها یا بردارهای جواب تولید خواهد شد.
کاربردهای الگوریتم ژنتیک
در صورتی که بتوانید جواب‌های کاندید یک مسأله را در قالب کروموزوم‌ها کدبندی کنید،
به راحتی خواهید توانست از الگوریتم ژنتیک برای حل مسأله و مقایسه عملکرد (برازندگی) نسبی
جواب‌های بهینه حاصل شده استفاده کنید. نمایش دقیق و مؤثر از متغیرهای مسأله و پیاده‌سازی
ساز و کارهای با معنی برای ارزیابی برازندگی جواب‌های کاندید،
مهم‌ترین عوامل در موفقیت در کاربردهای تولید شده از الگوریتم ژنتیک است.
نقطه قوت الگوریتم ژنتیک، در سادگی و ظرافت آنها به عنوان یک الگوریتم جستجوی قدرتمند
و قدرت آنها در کشف سریع جواب‌های خوب برای مسائل سخت و «با ابعاد بالا»
(High Dimensional) نهفته است. الگوریتم ژنتیک زمانی می‌توانند مفید و مؤثر واقع شود که:
- فضای جستجوی مسأله بزرگ، پیچیده و دارای ساختار بندی ضعیف باشد.
- دانش دامنه نایاب باشد و یا دانش خبره، جهت محدود کردن فضای جستجو، به سختی کدبندی شود.
- هیچ‌گونه تحلیل ریاضی در دسترس نباشد.
- روش‌های جستجوی سنتی با شکست مواجه شوند.
از الگوریتم‌های ژنتیک، جهت حل مسأله و مدل‌سازی استفاده می‌شود. امروزه،
از الگوریتم‌های ژنتیک و مشتقات آن، در دامنه وسیعی از مسائل علمی و مهندسی
استفاده می‌شود. مهم‌ترین کاربردهای الگوریتم ژنتیک عبارتند از:
- بهینه‌سازی:
- «برنامه‌نویسی خودکار» (Automatic Programming)
- «یادگیری ماشین» (Machine Learning):
- مدل‌های «سیستم ایمنی» (Immune Systems):
- مدل‌های اقتصادی:
کدهای پیاده‌سازی الگوریتم ژنتیک در زبان‌های برنامه‌نویسی مختلف
در این بخش، کدهای پیاده‌سازی الگوریتم ژنتیک برای مدل‌سازی و حل «الگوریتم راسو» (Weasel algorithm)
نمایش داده شده است. هدف این الگوریتم این است که نشان دهد تغییرات تصادفی در ژنها و ترکیب آنها
با یک مکانیزم انتخاب غیر تصادفی، منجر به تولید نتایجی متفاوت و بهتر از
شانس خالص در فرایندهای تکاملی خواهد شد. مشخصات این مسأله به شکل زیر است:
- جمعیت اولیه: یک آرایه 28 عنصری متشکل از الفبای ABCDEFGHIJKLMNOPQRSTUVWXYZ.
- هدف نهایی: تبدیل رشته ورودی یا جمعیت اولیه به رشته METHINKS IT IS LIKE A WEASEL.
- تابع برازندگی: تابعی که شباهت آرگومان ورودی را به رشته نهایی یا هدف نهایی مشخص می‌کند.
- عملگرهای تکاملی (پیاده‌سازی عملگر انتخاب و جهش ضروری است، ولی پیاده‌سازی عملگر ترکیب اختیاری است)
جمع‌بندی
الگوریتم‌های ژنتیک، به راحتی در دامنه وسیعی از مسائل، از جمله مسائل بهینه‌سازی نظیر
«مسأله فروشنده دورهگرد» (Travelling Salesman Problem) و مسائل مرتبط با «برنامه‌ریزی»
(Scheduling)، می‌توانند مورد استفاده قرار بگیرند. نتایج حاصل از الگوریتم ژنتیک برای برخی از
مسائل ممکن است بسیار خوب و برای برخی دیگر از مسائل، ممکن است بسیار ضعیف باشد.
اگر تنها از عملگر جهش در الگوریتم ژنتیک استفاده شود، الگوریتم بسیار کند می‌شود. استفاده
از عملگر ترکیب، سبب سرعت بخشیدن به فرایند همگرایی در الگوریتم ژنتیک خواهد شد.
مشکل بهینه محلی در الگوریتم ژنتیک بسیار شایع است. در حالتی که الگوریتم در بهینه محلی قرار بگیرد،
استفاده از عملگر جهش سبب می‌شود تا جواب‌های بدتری نسبت به بهینه محلی تولید شود. با این حال،
برای فرار از دام بهینه محلی می‌توان از عملگر ترکیب استفاده کرد. البته، از آنجایی که جهش یک فرایند
کاملا تصادفی است، این امکان نیز وجود دارد که جهش‌های بزرگی در کروموزوم‌ها ایجاد شوند و آن کروموزوم‌ها
یا جواب‌های کاندید از بهینه محلی خارج شوند.
در آینده، ممکن است شاهد توسعه الگوریتم‌های تکاملی باشید که برای حل مسائل خاص مورد استفاده قرار بگیرند.
این امر، نقض اصول پیاده‌سازی الگوریتم ژنتیک است که با هدف استفاده همه منظوره و بدون در نظر گرفتن دامنه مسائل
قابل حل، توسعه داده شده‌اند. با این حال، چنین گرایشی در توسعه الگوریتم‌های
تکاملی ممکن است منجر به تولید سیستم‌های تکاملی به مراتب قوی‌تر شود.
