الگوریتم‌های ژنتیک یکی از انواع الگوریتم‌های تکاملی‌ میباشد که از علم زیست‌شناسی الهام گرفته شده است . الگوریتم ژنتیک که به‌عنوان یکی از روشهای تصادفی بهینه یابی شناخته شده و توسط جان هالند در سال ۱۹۶۷ ابداع شده‌است. کاربرد اصلی الگوریتم ژنتیک در کامپیوتر است ، اما روشهایی از ژنتیک در مهندسی صنایع، برنامه‌ریزی تولید، مدیریت تولید، مدیریت فناوری اطلاعات و مدیریت صنعتی نیز قابل استفاده است.

الگوریتم جستجو

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

  • جمعیت (Population) : مجموعه ای از پاسخ های ممکن
  • کروموزمدر الگوریتم ژنتیک هر کروموزوم یک راه حل و پاسخ ممکن برای مساله است . در واقع مجوعه ای از کروموزوم ها جمعیت را تشکیل میدهند . برای نمایش کروموزوم ها معمولا از رشته های دودویی و یا اعداد حقیقی استفاده میکنند . هر کروموزوم از تعدادی ژن تشکیل میشود . برای مثال در یک رشته دودویی هر بیت معادل یک ژن از کروموزوم می باشد

حال باید از بین جمعیت ، کروموزوم های خوب برای بقا و تکثیر باقی مانده و کروموزوم های نا مناسب از بین بروند . فقط به این نکته باید دقت کرد که میزان جمعیت ما ثایت باقی می ماند و گونه های نا مناسب حذف میشوند .مسائل پیش رو :

  1. طراحی ساختار کروموزوم
  2. ایجاد جمعیت اولیه
  3. روش انتخاب کروموزم ها
  4. نحوه مشخص کردن کیفیت کروموزوم ها (Fitness)
  5. معیار توقف الگوریتم

ساختار هر کروموزوم و جمعیت اولیه با توجه به شرایط اولیه مساله ایجاد میشوند و باید در کل الگوریتم شرایط مساله را حفظ کنند.

  • تابع تطابق یا برازندگی (Fitness Function) : تابع ارزیابی جمعیت است که به هر کروموزوم یک مقدار عددی نسبت میدهد که میزان توانمندی و شایستگی آن کروموزوم است . از بین کروموزوم های جمعیت ، بهترین ها با استفاده از یک تابع احتمال انتخاب شده و جمعیت جدید را تشکیل می دهند .تعدادی از این کروموزوم ها عینا مورد استفاده قرار میگیرند و تعدادی نیز برای آمیزش (Crossover) و جهش (Mutation) برای تولید فرزندان (Offspring) استفاده می شوند .
  • عملگر انتخاباین عملگر از بین کروموزوم های موجود با توجه به مقدار Fitness آنها بهترین ها را برای بقا و تولید مثل انتخاب میکند و جمعیت جدید را تشکیل میدهد . کرموزوم هایی که برازندگی بهتری دارند شانس بیشتری برای انتخاب دارند . مکانیزمهای زیادی برای انتخاب هستند که در اینجا فقط یکی از انها را تعریف میکنم
  • چرخه رولت : در این روش به نسبت برازندگی هر کروموزوم یک احتمال تجمعی به آن نسبت داده میشود و با این احتمال شانس انتخاب هر کروموزوم مشخص می شود .
  • عملگر آمیزشبر روی یک جفت کروموزوم کار میکند و یک جفت کروموزوم جدید به عنوان فرزند تولید می کند . نحوه قرار گیری فرزندان در جمعیت شیوه های متفاوتی دارد . مثلا میتوانند در همان لحظه جایگزین والدین خود شده و یا به جمعیت اضافه شده و وارد عملگر انتخاب شوند .
  • عملگر جهش : این عملگر بر روی تمام کروموزوم ها عمل میکند و به طور تصادفی با توجه به نرخ جهش که تعریف کردیم ژن هایی را انتخاب کرده و مقدار آنرا تغییر میدهد .

 

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

.