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

مدرس: مسعود کاویانی

MasoudKaviani.ir

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

اگر دروسِ گذشته را خوانده باشید، متوجه می‌شوید که الگوریتم‌های فراابتکاری (Meta Heuristic)، به دنبال پیدا کردنِ یک راه‌حلِ بهینه در زمانی معقول می‌گشتند. در واقع این الگوریتم‌ها به جای این‌که تمامیِ حالات را جستجو کنند، با استفاده از روش‌های مختلفِ ابتکاری، با جستجو در قسمتی از حالات، به یک جوابِ معقول و خوب در زمانِ مناسب می‌رسیدند. الگوریتمِ ژنتیک هم یکی از این دسته از الگوریتم‌هاست که با الهام از ژنتیک موجوداتِ زنده، به دنبالِ پیدا کردنِ یک حالتِ بهینه در زمانِ معقول است.

اجازه بدهید ابتدا به بررسیِ ساختارِ پایه‌ی الگوریتم ژنتیک بپردازیم. الگوریتمِ ژنتیک شامل ۵ قسمت اصلی است. مقداردهی اولیه‌ی جمعیت، تابع برازش (Fitness Function)، انتخاب (Selection)، جابه‌جایی (Crossover) و جهش (Mutation). شکل زیر را نگاه کنید:

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

اجازه بدهید یک مثالِ کاربردی را با هم مرور کنیم. می‌خواهیم معادله‌ی ۴مجهولیِ زیر را با الگوریتمِ ژنتیک حل کنیم:

در واقع ما به دنبال یک راه‌حل می‌گردیم که متغیرهای a، b، c و d را با اعداد مناسب پر کند. اولین فاز تبدیلِ یک مسئله به حالتِ ژنتیکیِ آن است. اجازه بدهید این کار را مانندِ شکلِ زیر انجام دهیم:

در شکل بالا می‌بینید که هر کدام از متغیرها یک ژن شده‌اند و ترکیبِ متغیرها با ترتیبِ abcd، یک کروموزوم را تشکیل می‌دهد. حالا بایستی یک جمعیت درست کنیم. این جمعیت را به صورتِ دلخواه ۶ نفره در نظر می‌گیریم. پس نیاز به ۶ کروموزوم داریم. هر کدام از آن‌ها را با یک مقدار اولیه‌ی دلخواه پر می‌کنیم. چیزی مانندِ شکل زیر:

در شکل بالا فازِ مقداردهی اولیه را برای جمعیت انجام دادیم. حالا باید تابعِ برازش را ساخته و ارزشِ هر کروموزوم را با توجه به این تابع محاسبه کنیم. تابع برازش در این‌جا ساده است. مقادیرِ هر جمعیت را داخل فرمول می‌گذاریم و فرمول را حساب می‌کنیم. هر کروموزوم یک عدد به عنوان پاسخ پیدا می‌کند. هر چقدر این عدد به صفر (۰) نزدیک‌تر بود، یعنی این کروموزوم ژن‌های بهتری دارد (در واقع توانسته متغیرهای abcd را با تخمین بهتری پیش‌بینی کند). اجازه بدهید برای جمعیت بالا، ارزش هر کروموزوم را با توجه به ژن‌های آن به دست بیاوریم:

فرمول محاسبه برای به دست آوردن اعدادِ قرمز رنگ، همان فرمولِ معاله‌ی اول بوده است. همان‌طور که می‌بینید، کروموزوم شماره‌ی ۴، ارزش بیشتری دارد. زیرا به صفر (۰) که همان جوابِ معادله است، نزدیک‌ترست.

حال به مرحله‌ی انتخاب می‌رسیم. گفتیم که در الگوریتم ژنتیک، به دنبال انتخابِ اصلح هستیم. پس آن کروموزومی که ارزش بیشتری دارد، بایستی احتمالِ انتخاب بالاتری هم داشته باشد. در واقع مانندِ این است که انسان‌های باهوش‌تر، بیشتر اجازه‌ی تولید مثل دارند. مثلاً در مثالِ بالا کروموزوم شماره‌ی ۴ بایستی با احتمالِ بیشتر نسبت به کروموزوم ۵ انتخاب شود، زیرا ژن‌های بهتری دارد (در واقع اعدادِ متغیرهای abcd را بهتر انتخاب کرده بود). اجازه بدهید ۶ کروموزوم جدید را با نسبتِ احتمالِ انتخاب برای این کروموزوم‌ها تولید کنیم:

در شکلِ بالا، با توجه به احتمالِ انتخاب‌ها، یک سری کروموزوم جدید انتخاب شد (مثلا کروموزوم ۴ شانس بیشتری برای انتخاب داشت). همان‌طور که می‌بینید به ترتیب کروموزوم‌های ۲ – ۳ – ۱ – ۶ – ۳ – ۴ انتخاب شد و این‌ها را جایگزین کروموزوم‌های قبلی کردیم. یعنی مثلاً در این‌جا کروموزوم ۲ انتخاب شده و جایگزین کروموزوم ۱ می‌شود. مشاهده می‌کنید که کروموزوم شماره‌ی ۵ اصلاً انتخاب نشد و در واقع از بین رفت.

حالا موقع ازدواج رسیده است. به صورت تصادفی زوج‌ها را با هم انتخاب می‌کنیم. برای مثال در شکل زیر مشاهده می‌کنید که کروموزوم‌های ۱ – ۴ – ۵ با هم ازدواج می‌کنند و کروموزوم‌های ۲ – ۳ – ۶ مجرد باقی می‌مانند (یعنی تغییری نمی‌کنند). کروموز‌های ازدواج کرده باید نسل بعدی را جایگزین خود کنند. در تولیدِ نسلِ بعدی کروموزوم‌ها با همدیگر عملیات جابه‌جایی (Crossover) ژنی را انجام داده و نتیجه را به جای ژن‌های خود قرار می‌دهند. البته این عملیات نیاز به یک نقطه‌ی جابه‌جایی (Crossover Point) دارد که مشخص می‌کند از کدام ژن به بعد (برای هر عمل Crossover) بایستی جابه‌جایی صورت پذیرد. این نقطه‌ی جابه‌جایی نیز به صورت تصادفی برای هر زوج انتخاب می‌شود. عملیات Crossover و نتیجه‌ی آن را در شکل زیر مشاهده می‌کنید:

اجازه بدهید حاصل Crossover بر روی کروموزوم ۱ و ۴ را با هم مرور کنیم. این دو کروموزوم با هم ازدواج کرده و در نقطه‌ی ۱ جابه‌جاییِ ژنی را انجام می‌دهند. یعنی قسمت سمت چپ از کروموزوم ۱ انتخاب شده و بعد از آن (قسمت راست) از کروموزوم ۴ انتخاب می‌شود. به این صورت ژن‌ها در کروموزوم جابه‌جا شده و نتیجه‌ی حاصل به جای کروموزوم ۱ قرار می‌گیرد. برای کروموزوم‌های ۴ و ۵ همین اتفاق با نقاط جابه‌جایی مختلف می‌افتد.

عملیات آخری که باید انجام شود، عملیات جهش (Mutation) است. این عملیات باعث تغییر تصادفی در ژن‌ها می‌شود. تعداد ژن‌هایی که باید جهش کنند یک عدد است که می‌توانیم برای سیستم تعیین کنیم. برای مثال می‌گوییم ۱۰درصد ژن‌ها بایستی تغییر کنند. الگوریتم به صورت تصادفی ۱۰درصد از ژن‌ها را انتخاب کرده و آن‌ها را به صورتِ تصادفی تغییر می‌دهد. در این مثال، ما ۲۴ژن داریم، پس بایستی ۱۰درصدِ آن‌ها یعنی ۲ژن را جهش دهیم. به صورتِ تصادفی به ترتیب ژن ۴ از کروموزوم ۳ و ژنِ ۲ از کروموزوم ۵ را با اعدادی تصادفی (مثلا بین ۰ تا ۳۰) جابه‌جا می‌کنیم. نتیجه چیزی شبیه به شکل زیر می‌شود:

این آخرین مرحله‌ی الگوریتمِ ژنتیک برای تولید یک نسل جدید است. در شکلِ بالا یک جمعیتِ جدید ۶تایی ایجاد شده است، که ژن‌های آن نسبت به ژن‌های نسلِ قبلیِ خود تغییر کرده است. حال اجازه دهید، ارزشِ این نسل را با توجه به فرمولِ اولیه دوباره محاسبه کنیم. در شکل زیر تابع برازش (Fitness Function) را دوباره برای نسل جدید استفاده می‌کنیم (با استفاده از همان فرمولِ اول):

همان‌طور که می‌بینید، به صورت میانگین، اکثر کروموزوم‌ها، نسبت به نسل قبلیِ خود بهتر شده است. پس در کل نتیجه می‌گیریم که این نسل از نسلِ قبلیِ خود بهتر شده است. الان یک نسل جدید ساخته شد. نسلی که بهتر از نسلِ قبلیِ خود توانسته متغیرهای abcd را تخمین بزند. دوباره این نسلِ جدید باید تحت همین فرآیند قرار گیرد تا نسلِ بعدی را بسازد. این کار آنقدر بایستی تکرار شود تا نسل‌های بعدی تغییرِ خاصی نسبت به نسل قبلی با توجه به خروجیِ تابع برازش (Fitness Function) پیدا نکند. برای مثال اگر همین فرآیند‌های بالا را به اندازه‌ی ۵۰ دورِ دیگر تکرار کنیم نتیجه مانند زیر می‌شود:

همان‌طور که مشاهده می‌کنید، الگوریتمِ ژنتیک توانست اعداد مناسب را با ساخت ۵۰ نسل بسازد. این کار با بهبود مستمر هر نسل و انجام عملیات مختلف صورت گرفت.

در واقع الگوریتم ژنتیک با انجام عملیاتِ جابه‌جایی (Crossover)، جهش (Mutation) و دادن احتمالِ انتخاب بیشتر به کروموزوم‌هایی که ژن‌های بهتری دارند، نسل‌ها و کروموزوم‌های بهینه‌تری را تولید کند تا در نهایت به یک جواب خوب (بدون گشتن و امتحان کردنِ تمامیِ حالت‌ها) برسد.