الگوریتم ژنتیک

الگوریتم‌های ژنتیک، به عنوان یکی از راه‌حل‌های یافتن جواب مسئله در بین روش‌های مرسوم در هوش مصنوعی مطرح است. در حقیقت بدین روش می توانیم در فضای حالت مسئله حرکتی سریع‌تر برای یافتن جواب‌های احتمالی داشته باشیم؛ یعنی می توانیم با عدم بسط دادن کلیه حالات، به جواب‌های مورد نظر برسیم.

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

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

کروموزوم

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

۱۰۱۱۰۱۱۰۱۰۰۰۰۱۰۱۰۱۱۱۱۱۱۱۰

‌یا

۱۲۶۴۱۹۶۳۵۲۴۷۸۹۲۳۴۵۵۵۴۸۲۱۶

‌

برای شروع فعالیت الگوریتم ژنتیک نیازمند جمعیتی از کروموزوم‌ها به صورت تصادفی هستیم. یعنی در ابتدا به عنوان قدم اول، تعدادی کروموزوم به صورت تصادفی ایجاد می کنیم. فرض کنید N کروموزوم و این N را جمعیت آغازین می‌نامیم.

در ادامه تابعی به نام تابع ارزش تشکیل می‌دهیم که این تابع به عنوان ورودی یک کرومزوم را دریافت می‌کند (یک جواب مسئله) و به عنوان خروجی عددی را مبتنی بر میزان بودن کرومزوم نسبت به جواب نهایی بر می‌گرداند. در حقیقت این تابع میزان خوب بودن جواب را مشخص می‌کند. برای همه نمونه‌های جمعیت مقدار تابع ارزش را حساب می‌کنیم.

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

بعد از انتخاب دو کرومزوم، اکنون نوبت به ترکیب می‌رسد. برای انجام عمل ترکیب، باید یک نقطه (نقطه شکست) در جفت کروموزوم خود را به صورت تصادفی انتخاب کنیم. هر کرومووزم را به دو پاره تقسیم می‌کنیم و در ادامه کمی جای هر پاره از هر کروموزوم را با دیگری عوض می‌کنیم. مانند شکل زیر

بدین ترتیب دو کرومزوم جدید تولید می‌شود (دو جواب جدید). راه دیگری نیز برای انجام عمل ترکیب وجود دارد و آن انتخاب چند نقطه شکست است. مثلاً به شکل زیر برای ۲ نقطه شکست توجه کنید

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

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

از شما دوستان عزیز که این مطلب آموزشی را دنبال نموده اید تشکر می کنیم و شما را دعوت میکنیم که برای فراگیری هوش مصنوعی مطالب ما را دنبال کنید.این مطالب برای افزایش دانش شما در سایت قرار داده شده و کمک زیادی در یادگیری شما در انجام پروژه هوش مصنوعی خواهد نمود.

فریلنسر هستم و مهارت انجام پروژه ای را دارم!

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

نحوه سفارش پروژه در سایت کافه پروژه :

اگر پروژه ای دارید که میخواهید آن را برون سپاری کنید کافی است در سایت کافه پروژه ثبت نام کنید و پروژه خود را ثبت نمایید.پروژه شما هر چه که باشد حتما مجری برای آن وجود دارد.جهت ثبت نام و ثبت سفارش پروژه خود برروی دکمه زیر کلیک نمایید.