دانلود مقاله الگوریتم ژنتیک و میزان سازگاری


Widget not in any sidebars

infeasible
Coding Space
Solution Space
encoding
یکی از روش های معمول نمایش به صورت رشته ای باینری است:رشته های 0و1.یک روش حل دیگر کد کردن راه حل ها در آرایه ای از اعداد صحیح یا اعشاری است،که دوباره هر جایگاه یک جنبه از ویژگی ها را نشان می دهد.این راه حل در مقایسه با قبلی پیچیده تر و مشکل تر است.سومین روش برای نمایش صفات در یک GA،یک رشته از حروف است،که هر حرف دوباره نمایش دهنده یک خصوصیت از راه حل است.
خاصیت تمام این روش ها این است که آنها تعریف سازنده ایی را که تغییرات تصادفی در آنها ایجادمی کنند را آسان می کند:0 را به 1 و برعکس،اضافه یا کم کردن ارزش یک عدد یا تبدیل یک حرف به حرف دیگر.
به طور کلی روش نمایش به دامنه مسئله بستگی دارد.
مثال هایی از روش نمایش عبارتند از:
-دوتایی {1و0}
-سه تایی{2و1و0}
-چهارتایی{3و2و1و0}
-عدد صحیح {…و12و11و…و3و2و1}
-حقیقی {…و126،4و591،1و854،2}
2-3-2مراحل الگوریتم ژنتیک25
2-3-3 ایجاد جمعیت اولیه
اولین مرحله بعد از تعیین تکنیکی که برای تبدیل هر جواب به یک کروموزوم بکار می رود ایجاد یک جمعیت اولیه از کروموزوم هاست.در این مرحله جواب اولیه معمولاً بصورت تصادفی تولید می شود.البته در بعضی موارد با توجه به نوع مسئله و برای بالا بردن سرعت همگرایی الگوریتم از روش های ابتکاری نیز استفاده گردیده است.به هر حال عمومی ترین و فرآگیرترین روش،استفاده از یک رویکرد تصادفی است.
2-3-4 ارزیابی جواب های هر نسل
در این مرحله با معرفی یک معیار یا اندازه به بهتر بودن یا نبودن هر جواب ممکن از جمعیت موجود پی می بریم.یعنی این که این معیار به ما می گوید که مثلاً جواب X واقع در جمعیت اولیه چقدر خوب است.
تابعی که بر اساس آن میزان سازگاری کروموزوم ها با محیط ارزیابی می شود تابع برازندگی نام دارد.در برخی موارد به این تابع،تابع ارزیابی هم گفته می شود.با استفاده از این تابع هر کروموزوم رمزگشایی شده و به آن یک مقدار برازندگی نسبت داده می شود.به عنوان مثال در مسئله فروشنده دوره گرد این تابع می تواند بیانگر کل فاصله تور باشد.
2-3-5روش های انتخاب
روش های مختلفی برای الگوریتم های ژنتیک وجود دارند که می توان برای انتخاب کروموزوم ها از آنها استفاده کرد.اما روش های لیست شده در ذیل از معمول ترین روش ها هستند.
2-3-5-1انتخاب تصادفی
با استفاده از یک تابع تصادفی دو کروموزوم انتخاب می شود.به عنوان مثال می توان دو عدد تصادفی را در بازه یک و تعداد کروموزوم ها تولید و کروموزوم های مربوط به آن دو عدد را به عنوان والد انتخاب کرد.
2-3-5-2 انتخاب بر اساس چرخ رولت
در این روش ابتدا برای هر کروموزوم از جمعیت مقدار شایستگی آن محاسبه می شود.مجموع شایستگی ها را حساب کرده سپس یک عدد را به طور تصادفی بین صفر و مجموع شایستگی ها انتخابمی شود.ودر ضمن کروموزوم های بهتر انتخاب بیشتری دارند و شانس انتخاب هر کروموزوم متناسب با میزان برازندگی آن کروموزوم است.با این شیوه احتمال انتخاب با میزان شایستگی نسبت مستقیم دارد.
2-3-6 رتبه بندی
کروموزوم ها بر حسب شایستگی مرتب می شوند و برنامه به ترتیب انتخاب را انجام می دهد.