الگوریتم ژنتیک چیست؟ الگوریتم ژنتیک یک روش جستجوی ابتکاری و بهینه شده است که از نظریه انتخاب طبیعی چارلز داروین الهام گرفته شده است. این الگوریتم در واقع بیانگر تئوری انتخاب طبیعی است؛ جایی که در آن مناسب‌ترین افراد برای ادامه نسل و تولید فرزندان انتخاب می‌شوند. در این مقاله از تریتا به طور مختصر در مورد الگوریتم ژنتیک صحبت می‌کنیم.
انتخاب طبیعی چارلز داروین
تئوری انتخاب طبیعی برای اولین بار توسط چارلز داروین در کتاب خاستگاه گونه‌ها (On the Origin of Species) مطرح شد این نظریه دو اصل اساسی و مهم دارد :
- زندگی تمام گونه‌های روی کره زمین به هم وابسته است و به هم ارتباط دارد.
- تنوع زیستی که در بین گونه‌ها وجود دارد محصول تغییر جمعیت به وسیله انتخاب طبیعی است جایی که بعضی ویژگی‌ها و خصوصیات سازگاری بیش‌تری با محیط دارند به نسل‌های بعد منتقل می‌شوند. بعضی افراد این تئوری را «بقای گارترین گونه‌ها» می‌نامند.
ایده انتخاب طبیعی در الگوریتم ژنتیک چیست؟
عملکرد انتخاب طبیعت با انتخاب بهترین افراد از یک جمعیت آغاز می‌شود این افراد فرزندانی را تولید می‌کنند که ویژگی‌های والد خود را به ارث می‌برند و به نسل‌های بعدی انتقال می‌دهند. اگر والدین سازگاری بهتری داشته باشند فرزندان آن‌ها از والد خود بهتر و سازگارتر خواهند شد و حتی شانس بیش‌تری برای بقا خواهند داشت. این فرآیند به صورت مداوم تکرار خواهد شد و در آخر نسلی به وجود خواهد آمد که بیش‌ترین سازگاری را با محیط خواهد داشت. طبیعت همیشه یک منبع بسیار مهم برای گرفتن ایده‌ها و الهام بخش برای حل بسیاری از مشکلات ماست. الگوریتم ژنتیک یکی از همین ایده‌هایی است که بشر از دل طبیعت استخراج کرده است.
نحوه انجام الگوریتم ژنتیک چیست؟
ما مجموعه‌ای از راه حل‌ها و ایده‌ها برای حل مشکلات را در نظر می‌گیریم ایده‌ها و راه حل‌ها با یکدیگر ترکیب می‌شوند و در بعضی موارد جهش می‌یابند و فرزندان جدید (راه حل‌های جدید) تولید می‌کنند و این فرایند در طی نسل‌های مختلف دائما تکرار می‌شود و به هر فرد یا راه حل یک امتیاز اختصاص داده می‌شود. در آخر راه حل‌های بهتر و بهینه‌تر که امتیاز بیش‌تری دریافت کردند شانس بیش‌تری برای انتخاب شدن توسط طبیعت دارند.
الگوریتم ژنتیک به مراتب سریع‌تر و موثر‌تر از روش‌های سنتی است همچنین این روش به جای یک راه حل واحد مجموعه‌ای از راه حل‌ها را در اختیار ما قرار می‌دهد. اما مانند هر روش و الگوریتم دیگری الگوریتم ژنتیک نیز یک سری محدودیت‌هایی دارد از جمله اینکه این الگوریتم برای همه مشکلات مناسب نیست مخصوصا برای مسائل ساده و با پارامترهای محدود این روش توصیه نمی‌شود. سازگاری هر عضو از جمعیت باید به طور مداوم اندازه‌گیری شود و این اندازه گیری حجم زیادی از محاسبات را می‌طلبد. اگر این الگوریتم به درستی به کار گرفته نشود ممکن است که جواب‌های یک مسئله همگرا نشوند.
مراحل الگوریتم ژنتیک چیست؟
این الگوریتم می‌تواند در مسائل مربوط به جستجو استفاده شود؛ ما تعدادی از راه حل‌ها برای یک مشکل را در نظر می‌گیریم و بهترین آن‌ها را از این بین انتخاب می‌کنیم. پنج فاز و مرحله برای الگوریتم ژنتیک در نظر گرفته می‌شود:
- جمعیت اولیه
- عملگر سازگاری
- انتخاب
- ترکیب
- و جهش
جمعیت اولیه (Initial population)
فرایند الگوریتم ژنتیک چیست؟ این فرایند با مجموعه‌ای از افراد و راه حل‌ها آغاز می‌شود که ما آن‌ها را جمعیت (population) می‌نامیم هر فرد از این جمعیت یک راه حل برای مشکلی است که ما می‌خواهیم آن را حل کنیم. در مورد جمعیت در الگوریتم ژنتیک باید چند نکته را در نظر داشت:
- تنوع بین جمعیت باید حفظ شود و از همگرایی زودرس جواب‌ها به یک جواب واحد خودداری شود (این کار توسط عمل‌گر‌های جهش صورت می‌گیرد)
- اندازه جمعیت نباید از یک میزانی فراتر برود چراکه این کار سبب کندی عملکرد الگوریتم ژنتیک می‌شود همچنین اندازه جمعیت نباید آنقدر کوچک باشد که نتوان دو والد موثر را از بین این جمعیت انتخاب کرد بنابراین یک اندازه بهینه برای جمعیت نیاز است که برای تعیین این اندازه نیاز به سعی و خطا دارد.
- هر فرد این جمعیت به وسیله‌ی مجموعه‌ای از پارامترها توصیف و طبقه بندی می‌شود که ما به هر یک از این پارامترها ژن (Genes) می‌گوییم.
- این ژن‌ها به هم می‌پیوندند و تولید یک رشته به نام کروموزوم (Chromosome) می‌کنند که تمام ویژگی‌های راه حل ما را ارائه می‌دهد.
- در الگوریتم ژنتیک ژن‌های هر راه حل به وسیله یک حرف الفبایی ارائه می‌شوند که این رشته‌ها معمولا به صورت صحیح یا اعشاری بیان می‌شوند که مهم‌ترین آن‌ها ارائه با سیستم دودویی (binary) است.
عملگر سازگاری (Fitness function)
عملگر سازگاری مشخص می‌کند که هر فرد این جامعه به چه میزان قابلیت سازگاری با محیط را دارد (توانایی هر فرد برای رقابت با دیگر افراد جامعه)، ما با این کار به هر یک از افراد این جامعه امتیازی را اختصاص می‌دهیم و احتمال اینکه یک فرد از جامعه برای ادامه نسل انتخاب شود به این امتیاز که بر اساس سازگاری به آن اختصاص داده می‌شود بستگی دارد. عملگر سازگاری باید دو ویژگی مهم را که در ادامه به آن‌ها اشاره می‌شود، داشته باشد:
- این عملگر باید به اندازه کافی برای انجام محاسبات سریع باشد.
- همچنین باید بتواند به صورت کمی میزان سازگاری راه حل‌های اولیه و همچنین راه حل‌های به وجود آمده از ترکیب دو راه حل والد را به داشته باشد.
انتخاب (Selection)
انتخاب فرآیند گزینش والد‌های مناسبی است که بتوانند با هم ترکیب شوند و نسل‌های بعدی را به وجود آورد. در این مرحله ما بهترین و سازگارترین افراد جامعه را انتخاب می‌کنیم و به آن‌ها اجازه می‌دهیم که ژن‌های خود را به نسل بعد انتقال دهند. دو جفت از این جمعیت برحسب بیش‌ترین سازگاری انتخاب می‌شوند که ما آن‌ها را والد می‌نامیم. افراد با بالاترین سازگاری شانس بیش‌تری برای انتخاب شدن و ادامه نسل دارند.
ترکیب (Crossover)
ترکیب مهم‌ترین و اساسی‌ترین فاز و مرحله الگوریتم ژنتیک است. هر کدام از این جفت والدها با هم ترکیب می‌شوند و فرزند جدید به وجود می‌آورند نقطه بازترکیب به صورت تصادفی در داخل ژن‌ها انتخاب می‌شود. فرزندان با انتقال جابه‌جایی ژن‌های والد و انتقال یک ژن از والد اول به والد دوم و برعکس به وجود می‌آیند. این جابجایی از ابتدای ژن‌ها تا نقطه بازترکیب به صورت متناظر صورت می‌گیرد و فرزندان جدید به جمعیت اضافه می‌شوند.
جهش (Mutation)
پس از شکل گیری فرزندان بعضی از ژن‌های آن‌ها دچار جهش می‌شوند که احتمال تصادفی بودن این جهش کم است. هدف اصلی جهش نگه داشتن تنوع و تمایز میان جمعیت و جلوگیری از همگرا شدن زودهنگام جمعیت به یک نوع خاص است.
خاتمه الگوریتم و نکات پایانی
الگوریتم زمانی خاتمه می‌یابد که جمعیت به یک نمونه و یک راه حل خاص همگرا شده باشد. یعنی در واقع فرزندان تفاوت چشم‌گیری با والدین خود نداشته باشند. در این صورت می‌توان گفت که الگوریتم ژنتیک مجموعه‌ای از راه حل‌ها را برای مشکل ما فراهم آورده است.
- هر جمعیت یک اندازه معین و خاصی دارد و زمانی که نسل جدید شکل می‌گیرد آن‌هایی که کم‌ترین سازگاری را دارند از بین می‌روند و فضایی را برای فرزندان جدید به وجود می‌آورند.
- این توالی مراحل و فازها تکرار می‌شود تا افرادی را به وجود بیاورد که از نسل قبل خود بهتر و سازگارتر باشند.
بسیار عالی وروشن توضیح دادید ممنون