الگوریتم ژنتیک چیست؟ معرفی Genetic Algorithm به زبان ساده

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

دوره های شبکه، برنامه نویسی، مجازی سازی، امنیت، نفوذ و ... با برترین های ایران

الگوریتم طبیعت برای بقا چیست؟

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

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

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

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

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

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

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

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

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


معرفی الگوریتم ژنتیک - قسمت اول


در ادامه میخوام با یک مثال به توضیح بیتر این الگوریتم بپردازم :

صورت سوال : پیدا کردن مقدار بیشینه تابع زیر با دو متغیر (دو بعدی)

معرفی الگوریتم ژنتیک - قسمت دوم

برای شروع کار باید تابع محاسبه Fitness ( برازندگی ) را مشخص کنیم که در اینجا همان تابع صورت سوال میباشد . چرا که هدف بیشینه سازی این تابع میشد و مقدار آن مشخص کننده جواب مساله است .مرحله بعد مشخص کردن تعداد بیتهای مورد نیاز برای ساختن کروموزوم هاست . از فرمول زیر تعدا بیتها برای یک متغیر مشخص میشود و در نهایت طول کروموزوم برابر است با حاصل این فرمول ضرب در ابعاد مساله :

bitOfPerX=((max-min))*10000;
bitOfPerX=ceil(log2(bitOfPerX));
bitNum=bitOfPerX*n;

max و min : حد بالا و پایین شرایط مساله هستند .10000 : دقت مساله را مشخص میکند . (تا چهار رقم اعشار) یعنی برای هر متغیر به 17 بیت نیاز است و در مجموع برای ایجاد یک کروموزوم دو متغیره به 34 بیت . حال باید جمعیت اولیه را ایجاد کنیم . برای این کار از اعداد Random استفاده میکنیم :

v=round(unifrnd(0,1,[10 bitNum]));

ماتریس جمعیت ما است که با این دستور یک ماتریس 34*10 ایجاد شده . یعنی 10 کروموزوم 34 بیتی v خب تا اینجا مراحل اولیه انجام شده حالا باید کروموزوم ها برای انتخاب ، آمیزش و جهش وارد حلقه اصلی برنامه شوند . میزان اجرای الوریتم یک امر تجربی است من برای این برنامه الگوریتم را هزار بار اجرا کردم . حال باید مقادیر reeal این متغیر ها را پیدا کنیم برای این کار از فرمول زیر استفاده میکنیم :

vx= min + decimal(substring) * ( max-min)/(2^bitNum-1)

مقدار متغیر ها برای مرحله اول :

معرفی الگوریتم ژنتیک - قسمت دوم

بعد از محاسبه x ها باید مقدار برازندگی هر یک را مشخص کنیم . یعنی با ازای هر کروموزوم که شامل دو متغیر است مقدار تابع را مشخص میکنیم

13.1888- 12.1669- 8.8400- 15.3479- 7.6979- 12.2653- 11.6437- 6.5262- 11.3858- 12.4907-

در مقاله قبلی برای انتخاب چرخه رولت را معرفی کردیم اما اینجا از روشی به نام Tournament Selection استفاده میکنیم . به این شکل که دو کروموزوم به تصادف انتخاب شده و یکی از آنها برای مرحله بعد انتخاب میشود . با شروع برنامه جمعیت اولیه 10 میباشد و از بین این ده تا ده کروموزوم انتخاب میشود اما در مراحل بعدی که فرزندان به جمعیت اضافه میشوند انتخاب از بین کروموزوم های بیشتری صورت میگردد و 10 تا انتخاب میشوند .

بعد از انتخاب 10 کروموزوم نوبت Crossover است . برای این کار یک نرخ آمیزش انتخاب میکنیم . مثلا در این مثال من 0.35 را انتخاب کردم و به ازای هر کروموزوم یک عدد تصادفی بین 0 و 1 تولید میکنیم اگر عدد کوچکتر از نرخ آمیزش بود کروموزوم برای آمیزش انتخاب میشود .

در نهایت از هر زوج والد انتخاب شده دو فرزند تولید شده و به جمعیت اضافه میشوند .برای آمیزش روشهای مختلفی وجود دارد در اینجا از Uniform Crossover استفاده کردیم به این شکل که یک بردار تصادفی با اعداد صفر و یک به اندازه طول کروموزوم ایجاد کرده (Crossover Mask) و هر بیتی از این بردار که صفر بود جای بیتهای متناظر آن در والدین با هم جابجا میشوند . به مثال زیر توجه کنید :

معرفی الگوریتم ژنتیک - قسمت دوم

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

در این مثال مجموعا 340 = 34*10 بیت (ژن) داریم و باید 340 عدد تصادفی تولید کنیم . مثلا اگر عدد تصادفی بیت 12 شد 0.02 باید مقدار بیت 12 را معکوس کنیم .بعد از جهش دوباره به اول حلقه برگشته . یعنی محاسبه x و سپس برازندگی و بعد انتخاب و چون تعدادی فرزند به جمعیت اضافه شده صدرصد انتخاب در بین بیش از ده کروموزوم صورت میگیرد . در نهایت برای 5بار اجرای مستقل و 1000بار اجرای الگوریتم جوابها به این شکل شد :

معرفی الگوریتم ژنتیک - قسمت دوم

همانطور که میبینیم هر 5 اجرا جوابهایی با دقت بالا ایجاد کردند .


نظرات