ناب لرنینگ |
بزرگترین بانک اطلاعاتی پروژه های دانشجویی 
الگوریتم ژنتیک
از سال ١٩۶٠ تقلید از موجودات زنده برای استفاده در الگوریتم‌های قدرتمند برای مسایل الگوریتم ژنتیک مورد توجه قرار گرفت که تکنیک‌های محاسبه تکاملی نام گرفتند در واقع می‌توان گفت الگوریتم ژنتیک یک تکنیک برنامه نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مساله استفاده می‌کند. هنگامی که لغت تنازع بقا به کار می‌رود اغلب بار ارزشی منفی آن به ذهن می‌آید. شاید هم‌زمان قانون جنگل به ذهن برسد و حکم بقای قوی‌تر! البته برای آن که خیالتان راحت شود می‌توانید فکر کنید که همیشه هم قویترینها برنده نبوده‌اند؛ مثلا دایناسورها با وجود جثه عظیم در طی روندی کاملا طبیعی بازی بقا را واگذار کرده‌اند در حالی که موجوداتی بسیار ضعیف‌تر از آن‌ها حیات خویش را ادامه داده‌اند. ظاهراً طبیعت بهترین‌ها را تنها بر اساس هیکل انتخاب نمی‌کند! در واقع درستتر است بگوییم طبیعت مناسبترین‌ها (fittest) را انتخاب می‌کند نه قویترینها. قانون انتخاب طبیعی بدین صورت است که تنها گونه‌هایی از یک جمعیت ادامه نسل می‌دهند که بهترین خصوصیات را داشته باشند و آن‌هایی که این خصوصیات را نداشته باشند به تدریج ودر طی زمان از بین می‌روند. مثلاً فرض کنید گونه خاصی از افراد هوش بسیار بیشتری از بقیه افراد یک جامعه دارند. در شرایط کاملاً طبیعی این افراد پیشرفت بهتری خواهند کرد و این رفاه خود باعث طول عمر بیشتر و باروری بهتر خواهد بود. حال اگر این خصوصیت (هوش) ارثی باشد به طبع در نسل بعدی همان جامعه تعداد افراد باهوش به دلیل زاد و ولد بیشتر این گونه افراد بیشتر خواهد بود. اگر همین روند را ادامه دهید که طی نسل‌های متوالی دائما جامعه نمونه ما باهوش¬تر می‌شود. بدین‌ترتیب یک مکانیسم کاملاً ساده طبیعی توانسته است در طی چند نسل عملاً افراد کم هوش را از جامعه حذف کنند علاوه بر این که میزان هوش متوسط جامعه نیز دائماً در حال افزایش است. بدین ترتیب می‌توان دید که با بهره‌گیری از یک روش بسیار ساده (حذف تدریجی گونه‌های نامناسب و در عین حال تکثیر بالاتر گونه‌های بهینه) توانسته است دائماً هر نسل را از لحاظ خصوصیات مختلف ارتقا بخشد. البته این روش به تنهایی برای رسیدن به تکامل کافی نیست (حداقل در مورد آنچه در طبیعت وجود دارد) وجود فرآیندی به نام جهش (Mutation) نیز لازم است. در واقع می‌توان تکامل طبیعی را به این صورت خلاصه کرد:
جستجوی تصادفی + بقای مناسب‌تر
روش‌های کلاسیک ریاضیات دارای دو اشکال اساسی هستند:
اغلب این روش‌ها نقطه بهینه محلی (Local optimal) را بعنوان نقطه بهینه محلی در نظر می‌گیرند.
هر یک از این روش‌ها تنها برای مساله خاصی کاربرد دارد؛ مثلا تقسیم‌بندی‌هایی مانند برنامه ریزی خطی و غیر خطی داریم و برای حل هر یک روش خاصی داریم. اگر با مساله جدیدی روبرو شویم که از قبل الگوریتمی برای آن نداریم باید برای آن روش حل طراحی کنیم. این منحنی دارای چند نقطه ماکزیمم میباشد؛ که یکی از آن‌ها تنها ماکزیمم مطلق است. حال اگر از روش‌های بهینه‌سازی ریاضی استفاده کنیم مجبوریم تا در یک بازه بسیار کوچک مقدار ماکزیمم تابع را بیابیم. به محض رسیدن به اولین نقطه بهینه الگوریتم متوقف می‌شود. حال آن‌‌که نمی‌دانیم نقطه بهینه موضعی است یا مطلق؛ اما در روش‌های هوشمندی چون الگوریتم ژنتیک به دلیل خصلت تصادفی، احتتمال انتخاب هیچ نقطه‌ای صفر نیست یعنی همواره ما شانس انتخاب نقطه بهینه مطلق را داریم و این شانس با روند اجرای الگوریتم افزایش می‌یابد. در مورد نکته دوم باید بگوییم که روش‌های ریاضی بهینه‌سازی اغلب منجر به یک فرمول یا دستورالعمل خاص برای حل هر مساله می‌شوند. در حالی که روش‌های هوشمند دستورالعمل‌هایی هستند که به صورت کلی می‌توانند در هر مساله‌ای به کار گرفته شوند. این نکته را پس از آشنایی با خود الگوریتم بیشتر و بهتر خواهد دید.
کروموزوم و ژن
در جهان اطراف ما همه ارگانیزم‌های حیاتی از ساختارهای قانون‌مندی تشکیل شده‌اند. ساختارهایی که از سوی آفریدگار هستی در بطن موجودات قرار داده شده است. همه این ارگانیزم‌ها از بلوک‌های پایه‌ای از زندگی به نام سلول به وجود آمده‌اند. قوانین مزبور در قالب ژن‌ها به صورت کد شده در هر ارگانیزم وجود دارند. از به هم وصل شدن این ژن‌ها رشته‌هایی طولانی به نام کروموزوم تولید می‌شوند. هر ژن نمایانگر یکی از خصوصیات آن ارگانیزم است؛ مانند رنگ چشم یا رنگ مو و البته هر ژن می‌تواند دارای مقادیر مختلفی باشد. مثلا رنگ چشم می‌تواند دارای مقادیری متناظر با مشکی، قهوه‌ای و … باشد. هنگامی که دو ارگانیزم به تولید مثل می‌پردازند، در حقیقت ژن‌های خود را با یکدیگر ترکیب می‌کنند. بدین‌صورت که ارگانیزم تولید شده که آن را کروموزوم می‌نامیم، دارای نیمی از ژن‌های یک والد و نیمی دیگر از والد دیگری است. این عمل را ترکیب می‌نامیم. گاهی اوقات بعضی از ژن‌ها دارای جهش می‌شوند. این جهش تغییری در ساختار کروموزوم ایجاد نمی‌کند، اما با توجه به این که مقدار جدیدی به ژن تخصیص می‌یابد، موجب بروز خصوصیت جدیدی می‌شود.
واژگان الگوریتم ژنتیک
کروموزوم: رشته یا ارایه ای از بیت‌ها است که شکل رمز شده جواب محتمل مساله میباشد.
فنوتایپ: هر کروموزوم متناظر با مجموعه جوابی برای مساله است. مجموعه متناظر با هر کروموزوم را یک فنوتایپ می‌گویند.
بیت: مجموعه ای از کروموزوم‌ها را جمعیت می‌گویند. الگوریتم ژنتیک با جمعیتی از کروموزوم‌ها کار می‌کند.
جمعیت: مجموعه‌ای از کروموزوم‌ها را جمعیت می‌گویند. الگوریتم ژنتیک با جمعیتی از کروموزوم‌ها کار می‌کند.
نسل: هر تکرار از الگوریتم ژنتیک را یک نسل می‌گویند.
تابع برازندگی: تابعی است که مقادیر متغیرهای مساله در آن قرار می‌گیرند و مطلوبیت هر جواب را مشخص می‌کند. معمولا خود تابع هدف است.
از الگوریتم ژنتیک در مسایل جستجو و بهینه‌سازی استفاده می‌شود. ابتدا یک نسل اولیه ایجاد می‌گردد (بصورت تصادفی) که در واقع کروموزوم‌های اولیه هستند. هر یک از این کروموزوم‌ها جوابی برای مساله هستند اما جواب اصلی که ما به دنبال آن هستیم نیستند. سپس پدیده جهش با احتمال خیلی کم ممکن است رخ دهد. در نهایت کروموزوم‌ها از نظر امتیاز رتبه‌بندی می‌گردند، این امتیاز دهی معمولا بر اساس مقدار تابع هدف است. برخی کروموزوم‌ها با هم ترکیب شده و نسل بعد را بوجود می‌آورند، احتمال انتخاب کروموزوم‌های باامتیاز بالاتر، بیشتر است اما در عین حال احتمال انتخاب شدن برای تمام کروموزوم‌ها حتی کروموزوم‌های با کم‌ترین امتیاز وجود دارد. با نسل جدید بوجود آمده این مراحل را تکرار می‌کنیم تا به جوالب مطلق برسیم.
الف: عملگر تقاطع یا ترکیب (Crossover)
ب: عملگر جهش (Mutation)
ج: تابع برازش (Fitness)
د: مکانیزم انتخاب (Selection)
