الگوریتمهای ژنتیک یکی از انواع الگوریتمهای تکاملی میباشد که از علم زیستشناسی الهام گرفته شده است . الگوریتم ژنتیک که بهعنوان یکی از روشهای تصادفی بهینه یابی شناخته شده و توسط جان هالند در سال ۱۹۶۷ ابداع شدهاست. کاربرد اصلی الگوریتم ژنتیک در کامپیوتر است ، اما روشهایی از ژنتیک در مهندسی صنایع، برنامهریزی تولید، مدیریت تولید، مدیریت فناوری اطلاعات و مدیریت صنعتی نیز قابل استفاده است.
هنگامی که لغت تنازع بقا به کار می رود اغلب بار ارزشی منفی از آن به ذهن میرسد مثل قانون جنگل و یا حکم بقا برای قوی تر ها ...اما همیشه هم قوی تر ها برنده نبودند ، مثلا دایناسورها با وجود جثه بزرگ و قوی بقای نسل را واگذار کردند در حالی که موجوداتی بسیار ضعیف تر از آنها حیات خویش را ادامه دادند.
پس درست آن است که بگوییم طبیعت مناسب ترین ها را انتخاب میکند و نه صرفا قوی ترین ها . با کمی دقت در این الگوریتم میتوان دید که طبیعت با استفاده از یک روش ساده گونه های نا مناسب را به تدریج حذف و در مقابل گونه های مناسب و بهینه را بیشتر تکثیر میکند و دائما هر نسل را از لحاظ خصوصیت های مختلف ارتقا میبخشد.
در علوم کامپیوتر و ریاضیات الگوریتم جستجو الگوریتمی است که یک مساله را به عنوان ورودی میگیرد و پس از ارزیابی راه حل های ممکن یک راه حل برای آن مساله بر میگرداند . هنگامی که یک مساله را حل میکنیم بدنبال راه حل بهینه و یا به عبارتی بهترین پاسخ از بین پاسخ های ممکن هستیم .در الگوریتم ژنتیک با الهام از طبیعت ، هدف حل یک مساله جستجو و رسیدن به پاسخ بهینه است . برای این کار ابتدا باید با دو پارامتر زیر آشنایی پیدا کنیم:
حال باید از بین جمعیت ، کروموزوم های خوب برای بقا و تکثیر باقی مانده و کروموزوم های نا مناسب از بین بروند . فقط به این نکته باید دقت کرد که میزان جمعیت ما ثایت باقی می ماند و گونه های نا مناسب حذف میشوند .مسائل پیش رو :
ساختار هر کروموزوم و جمعیت اولیه با توجه به شرایط اولیه مساله ایجاد میشوند و باید در کل الگوریتم شرایط مساله را حفظ کنند.
در ادامه میخوام با یک مثال به توضیح بیتر این الگوریتم بپردازم :
صورت سوال : پیدا کردن مقدار بیشینه تابع زیر با دو متغیر (دو بعدی)
برای شروع کار باید تابع محاسبه 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 اجرا جوابهایی با دقت بالا ایجاد کردند .
زمان پاسخ گویی روز های شنبه الی چهارشنبه ساعت 9 الی 18
فقط به موضوعات مربوط به محصولات آموزشی و فروش پاسخ داده می شود