به عنوان یک مهندس نرم افزار، توی کارم باید مسائل مختلف رو حل کنم. این مسائل میتونن هر چیزی باشن مثل توضیع متناسب بار روی دستگاه های سرویس دهنده، استخراج اطلاعات از داده ها، بهینه سازی مدل های مختلف و...
روش های مختلفی برای حل کردن مشکلات و مسائل وجود داره. ولی جذاب ترین و کاربردی ترین الگوریتم ها بنظر من، الگوریتم هایی هستند که از روی طبیعت ساخته شدند. طی سالیان اخیر الگوریتم های جذابی اختراع شدند که هر کدوم به نحوی از طبیعت الهام گرفته شدند، مثل شبکه های عصبی که از روی کارکرد سلول های عصبی ساخته شده، الگوریتم کلونی مورچگان، الگوریتم زنبور عسل و الگوریتم ژنتیک از روی رفتار طبیعی موجودات در طی زمان و تغییر در ژنتیکشون الهام گرفته شده. واقعا زیباست!
توی این مقاله من میخوام الگوریتم بهینه سازی ژنتیک یا Genetic Algorithm رو بررسی کنم که با تولید کروموزم های مختلف، جهش ژنتیکی و تولید مثل و انتخاب طبیعی به جواب بهینه ی مد نظر ما میرسه. من سال 2018 یک مقاله خیلی کوتاه آموزشی در این مورد نوشته بودم و تصمیم دارم اینبار به زبان فارسی و جزییات بیشتر اون رو بررسی کنم و امیدوار باشم بتونید ازش استفاده کنید و اندازه ی خودتون دنیا رو جای بهتری بکنید :)
این لینک مقاله قدیمی من در این مورد هست میتونید مطالعه کنید:
N-Queen with Genetic algorithm
در پایان این مقاله هم یک برنامه مینویسیم که به وسیله ی الگوریتم ژنتیک سعی کنه یک مسیر بهینه بین دو نقطه روی یک نقشه رو پیدا کنه. این Gif خروجی این برنامه هست:
سورس کد این مقاله:
https://github.com/pedramcode/genetic_article/
طی میلیون ها سال، موجودات مختلفی در کره ی خاکی ما زندگی کردن. در دل زمین، در عمق دریا و در کران آسمان. این موجودات جدای از گونه و نژادشون، همواره برای بقاء تلاش کردن. چون طبیعت یه قانون ساده داره: ضعیف ها از بین میرن!
تمام موجودات همیشه درحال تطابق با محیط اطراف خودشون بودند و هستند و خواهند بود. اون هایی که تونستند به بهینه ترین شکل ممکن با موجودات دیگه همزیستی کنند و مطابق با قوانین محیط اطرافشون رفتار کنن موندگار شدند و اونهایی که نتونستند منقرض شدند.
تمامی تجارب، خصوصیات فیزیکی و پروتکل های مورد نیاز برای بقاء نسل گونه های مختلف جانداران، داخل واحد های ذخیره سازی اطلاعات طبیعی تحت عنوان «ژنوم» ذخیره سازی میشن. به نسل های بعدی منتقل میشن و در طی زمان دچار تغییرات میشن.
این واحد های ذخیره سازی اطلاعات متشکل از ترکیبات پروتوئینی هستند که نحوه ی قرار گیری اونها کنار هم قابلیت ذخیره سازی داده های پیچیده و مورد نیاز برای زنده موندن رو به موجودات زنده میده.
ژنوم ها مثل هر سیستم ذخیره سازی Decentralized یا غیر متمرکز دیگه ای، نیاز به پروتوکلی دارن که صحت اطلاعات ذخیره شده رو تضمین بکنه. در واقع نیاز به الگوریتمی دارن که مطمعن بشن که همیشه دیتا ی درستی به نسل های بعدی منتقل میشه. اسامی مختلفی برای این الگوریتم توی ذهن من میاد. مثلا بی رحمی طبیعت، بکش یا کشته شو، قانون جنگل یا انتخاب طبیعی.
موجوداتی که دیتای کاملی ندارن، یا دیتا کافی برای بقاء توی طبیعت ندارن نمیتونن تولید مثل کنن. یا کشته میشن و یا جفت پیدا نمیکنن! طبیعت دست به هر کاری میزنه تا اون ها رو نابود کنه. اینطوری صحت اطلاعات ژنوم ها تضمین میشه!
پس همیشه بهترین ژن ها باهم تولید مثل میکنن و نسل های سالم تر با ژن های بهتر تولید میشن و اون گونه ی جانوری میتونه به بقای خودش ادامه بده.
ولی اینجا یک مشکلی هست؛ اگر قرار بود که همیشه بهترین ژن ها باهم تولید مثل کنند، ما شاهد هیچ تنوع جانداری نبودیم! ماهی ها همیشه توی آب میموندن و تبدیل میشدن به «بهترین ماهی ها»! اونها هیچ وقت تلاش نمیکردن به خشکی بیان و دو زیستان رو به وجود بیارن. یا زرافه ها همیشه دارای گردن های کوتاه بودند و هیچ وقت طبق محیطشون بهینه نمیشدند و در نهایت از بین میرفتند.
پس طبیعت نیاز به یک پروتکل بهتر داره تا بتونه علاوه بر تضمین صحت داده های ژنوم، اون ها رو همواره بهتر بکنه و موجودات پیشرفته تری بسازه.
این جا هست که طبیعت با یک حرکت ساده تونسته میلیون ها گونه جانوری رو تولید کنه و زیست بوم های پیچیده رو ساختار بده: جهش ژنتیکی
توی هر چند نسل، با یک احتمال کم، ژنوم ها دچار تغییرات ناگهانی ناچیز میشن. این تغییرات یا تغییرات مثبت هستند یا تغییرات منفی. اگر این تغییرات منفی باشن، طبیعت با قانون اول خودش اون ها رو پاکسازی میکنه! و اگر هم تغییرات سازنده ای باشن طبیعت اونها رو به نسل های بعدی منتقل میکنه.
مثلا توی نقطه ای تاریخ طبیعت یکسری از ماهی ها برای پیدا کردن غذا به سمت سواحل و دریاچه های کم عمق اومدن و در طی نسل های متمادی، باله های ماهی ها جاشون رو به پا دادن که راه رفتن توی قسمت های کم عمق رو ساده تر کنه و اینطوری گونه ی دوزیستان به وجود اومدن.
تا اینجا متوجه شدیم یکسری قوانین ساده توی طبیعت حکم فرماست که باعث میشه ژنوم ها بهینه تر و بهینه تر بشن:
حالا بیاید از دید یک مهندس نرم افزار به این قوانین وحشتناک نگاه کنیم و ازشون استفاده کنیم!
الگوریتم ژنتیک یک الگوریتم بهینه سازی هست. به این معنی که ما با این الگوریتم به یک جواب مطلق نمیرسیم. بلکه این الگوریتم تلاش میکنه که جواب های بهینه تر و بهینه تری تولید بکنه. مثلا فرض کنید ما میخوایم از تهران به مشهد بریم. شاید صدها یا هزاران مسیر مختلف وجود داره که ما میتونیم اون ها رو انتخاب کنیم و به مقصد بریم. نقطه مشترک تمامی این مسیر ها این هستند که همه ی اون ها درست هستند! ولی بهینه ترین مسیر ممکن کدوم مسیر هست؟ با درنظر گرفتن فاکتور های مختلف مثل میزان سوخت مصرف شده، زمان سپری شده، منابع مصرف شده میتونیم بهینه ترین مسیر رو ارزیابی کنیم.
شاید تا الان تونسته باشید یک ارتباطی بین قوانین طبیعت با الگوریتم بهینه سازی مد نظر ما پیدا کنید! بیاید بیشتر بررسی کنیم:
هر کدوم از مسیر های مختلف از تهران به مشهد یک کروموزم هستند (ژنوم های حاوی اطلاعات)
الگوریتم ما مثل طبیعت قانونی برای ارزیابی خوب بودن یا بد بودن اطلاعات داره. بیاید اسمشو بذاریم Evaluation Function یا تابع ارزیابی. مثلا تابع ارزیابی ما برای این مثال میتونه مسافت طی شده یا میزان منابع مصرف شده هر کروموزم (یا مسیر) باشه.
الگوریتم با تابع ارزیابی، ضعیف ترین و قوی ترین مسیر ها رو پیدا میکنه. مسیر های ضعیف نابود میشن. و مسیر های قوی میتونن باهم ترکیب بشن و مسیر های بهتر جدیدی تولید کنن.
و در نهایت برای اینکه مثل طبیعت رفتار کرده باشیم، هر از گاهی با یک احتمال کم مسیر ها رو دچار جهش ژنتیکی یا تغییرات کوچک میکنیم.
بعد از تکرار چند نسل از این مسیر ها، ما به جواب های بهینه و بهینه تر میرسم. و تمام! ما تونستیم یک الگوریتم تولید کنیم که با الهام از طبیعت بهترین مسیر رو از تهران به مشهد برای ما پیدا کنه!
حالا بیاید کد بزنیم! میخوایم برنامه ای بنویسیم که به کمک Genetic algorithm بهترین مسیر رو از تهران به مشهد برای ما پیدا کنه (البته که روی یک نقشه ی خیالی!)
من زبان پایتون رو برای پیاده سازی انتخاب کردم. این نکته رو هم بگم که این کد جنبه ی آموزشی داره و برای استفاده روی Production بهینه نیست و بهتره استفاده نشه!
شروع کنیم!
اولین مرحله این هست که ما پروژه رو متوجه بشیم. این پروژه قراره کوتاه ترین مسیر رو بین دو نقطه روی یک نقشه ی n x n پیدا کنه.
ما نیاز داریم که به الگوریتممون یکسری چیزارو معرفی کنیم:
وقتی الگوریتم این اطلاعات رو داشته باشه میتونه جواب های بهینه رو برامون تولید کنه.
اول اینکه کروموزم از چه چیزی تشکل میشه: از جهت ها. وقتی قراره روی یک نقشه حرکت کنیم ما میتونیم توی هر قدم به چهار جهت اصلی حرکت کنیم. بالا، پایین، چپ و راست. پس هر کدوم از این چهار جهت یک «ژن» برای کروموزم ما هستند.
مثلا اینها مثال هایی از کروموزم های مسئله ی ما هستند:
کروموزم های این مسئله طول مشخصی ندارن. چون نمیدونیم قراره با چند تا حرکت به مقصد برسیم.
بیاید ژن های مسئله رو داخل یک Enum تعریف کنیم.
حالا که ژن ها رو داریم میتونیم کروموزم رو تعریف کنیم.
کلاس Chromosome وقتی ساخته میشه، به تعداد تصادفی، ژن های تصادفی تولید میکنه. در واقع هر بار که یک کروموزم ساخته میشه میتونه حاوی ۵ تا ۱۰۰ ژن باشه که اون ژن ها هم تصادفی انتخاب میشن. دلیل این کار ساخت یک جمعیت اولیه یا Initial population هست. البته همینطور که میبینید Constructor این کلاس یک لیست میگیره از ژن ها. که اگه براش ارسال بشه دیگه ژن های رندوم تولید نمیکنه و به جاش با اون ژن های ارسالی کروموزم رو میسازه.
ما باید برای شروع کار الگوریتم این جمعیت رو براش تولید کنیم تا بتونه به وسیله این جمعیت، کار خودشو شروع بکنه.
توی پرانتز بگم که احساس کردم یه کلاس میتونه بهمون کمک بکنه. از اونجایی که ما با مختصات سر و کار داریم یک کلاس Vectorدو بعدی میتونه خیلی به کارمون بیاد:
تنها کاری که میکنه اینکه دو مقدار x و y رو داخل خودش ذخیره میکنه.
حالا میریم سراغ مهم ترین کلاسمون. کلاس طبیعت. کلاس دنیا یا همون کلاسی که قراره نقش طبیعت رو بازی کنه، کروموزم هارو ارزیابی کنه، جهش بده و تولید مثل کنه. اسم این کلاس رو میذاریم World.
این کلاس طول و عرض دنیای ما و همچنین نقطه ی مبدا و مقصد مارو نگهداری میکنه. بریم سراغ متد هایی که این کلاس داره. اولین متد یک متدی هست که ما میتونیم بهش کروموزم رو بدیم و برای ما ژن های کروموزم رو اجرا کنه و مختصات نهایی رو برگردونه. در واقع مثل اینکه یک آدم طبق دستوراتی که بهش میدیم (جهت های جغرافیایی) حرکت میکنه و در نهایت یه جا می ایسته. بعدا از این متد میتونیم برای ارزیابی کروموزم ها استفاده کنیم.
حالا میتونیم مهم ترین تابع این برنامه یعنی تابع ارزیابی کروموزم رو بنویسم. این تابع به هر کروموزوم یک امتیاز میده. این امتیاز بر اساس دو مبنا به دست میاد: فاصله ی مختصات نهایی کروموزم تا نقطه ی مد نظر ما روی نقشه و همچنین تعداد ژن های داخل کروموزم. چون هرچی ژن ها کمتر باشن یعنی ما با تعداد حرکت کمتری رسیدیم به مقصد.
من یک فرمول ساده برای این موضوع درنظر گرفتم. شما حتما میتونید به فرمول بهتری برسید!
امتیاز کروموزم = (فاصله مختصات نهایی تا مقصد * وزن پارامتر اول) + (تعداد ژن ها * وزن پارامتر دوم)
بنابر این هرچقدر که این امتیاز کمتر باشه اون کروموزوم بهتر هست. وزن پارامتر ها برای این هست که به الگوریتم میزان اهمیت اون پارامتر رو بگیم. مثلا برای ما رسیدن به مقصد مهم تر از تعداد حرکات هست.
متد بعدی متد ترکیب یا تولید مثل دو کروموزوم هست. توی این متد دو والد به عنوان ورودی ارسال میشه و اون دو والد دو کروموزوم جدید تولید میکنن. روش تولید هم ساده هست. دو نقطه روی هرکدوم انتخاب میشه، بعد از اون نقاط شکسته میشن و باهم ترکیب میشن.
متد بعدی نسبتا پیچیده هست. متد جهش ژنتیکی. من پنج روش برای جهش ژنتیکی پیاده سازی کردم. البته که این روش ها روش های مطلقی نیستن و صرفا به صورت ناگهانی به ذهن من رسیدن. مطمعنا روش های بهتری هم برای این کار وجود داره:
در هر بار جهش، یکی از این روش ها به صورت تصادفی انتخاب میشن.
و در نهایت هم متدی که تعیین بکنه که آیا کروموزوم به مقصد رسیده یا نه:
ما تا اینجا تمامی موارد مورد نیاز برای اجرای الگوریتم رو در اختیار داریم. پس قدم آخر اجرای الگوریتم هست!
همینطور که قبلا گفتم در ابتدا یک جمعیت اولیه در اختیار الگوریتم قرار میگیره. من ۱۰ کروموزوم رو برای الگوریتم تولید کردم. دنیایی که الگوریتم داخلش اجرا میشه یک دنیای کوچک ۵۰ در ۵۰ پیکسل هست که مبدا ما در مختصات [0 , 0] و مقصد ما در مختصات [49 , 49] قرار داره.
برنامه انقدر ادامه میده و نسل های جدید رو تولید میکنه تا به پاسخ بهینه برسه.
این نکته رو هم بگم که برای هر فرزند تازه متولد شده تنها ۳۰ درصد احتمال جهش وجود داره.
شما میتونید سورس این پروژه رو روی این ریپوزیتوری پیدا کنید:
https://github.com/pedramcode/genetic_article/
اگر هم سوالی در مورد این پروژه یا درکل الگوریتم ژنتیک دارید برام کامنت کنید و سعی میکنم پاسخ بدم.
