دانلود پایان نامه

۱۰۰|۱۰۱|۱۱ A*: 100|100|11
Chromosome B: 011|100|01 B*: 011|101|01
روش ادغام چند نقطه ای (Multi point Cross over): در این روش دو کروموزوم والد از چند نقطه به منظور انجام عمل ادغام دچار شکست می شوند. در این روش ممکن است تعداد مکانها زوج ویا فرد باشند.
روش ادغام یک نواخت(Uniform Cross Over): این روش توسعه یافته روش چند نقطه ایست در این روش هر بیت براساس یک احتمال ۵۰ درصدی از والدهایش جدا شده و جابه جا می شوند.
Chromosome A: 10110011 A*:10011010
Chromosome B: 00011010 B*: 00110011

در مثال بالا ژنهای سوم و هشتم جابه جا شدند. روش ادغام دو بعدی: در این روش چند زیر رشته به هم متصل شده ویک رشته را پدید می آورند. مثلا در مثال زیر دو زیر رشته به هم متصل شده و یک رشته را پدید آورده اند.
String 1: 1011 +1001
String 1: 0101 +1110
در حالت دو بعدی رشته ها را به صورت ماتریس نشان دهده وبا پیدا کردن دو موقعیت تصادفی رشته ها ادغام می شوند.
نرخ ادغام(Croos Over Rate)
این نرخ همان احتمال ادغام است که با نشان می دهند. این نرخ بیان می کند که چه نسبتی ار جفت ها در هم ادغام می شوند. هر چه این نرخ(احتمال) بیشتر باشد بیانگرآن است که تعداد بیشتری از کروموزوم ها وارد استخر جمعیت (Mating poll) می شود. اگر این نرخ خیلی زیاد شود باعث می شود که فرصت تطابق از بین برود و همچنین اگر خیلی کوچک شود تعداد فرزندان تولید شده کوچک خواهد بود. برای جمعیت با اندازه۳۰تا۲۰۰ نرخ معمولا عددی بین ۰.۵تا۱ را به خود می گیرد.
توجه داشته باشید که نرخ ادغام یک پارامتر کنترلی است که بسته به نوع مسئله برنامه نویس می تواند مقادیر مختلفی را برای آن در نظر بگیرد اما معمولا این نرخ راحدود۸۰% در نظر می گیرند.
۳-عملگر جهش(Mutation):
در سیر تکاملی طبیعی، جهش یک فرایند تصادفی است که در آن محتوای یک ژن با ژن دیگر جهت تولید یک ساختار ژنتیکی جدید جایگزین می گردد . در الگوریتم ژنتیک ، جهش به طور تصادفی با احتمال کم(معمولاً‌بین ۰۰۱/۰ و ۰۱/۰ ) انجام شده و عناصر را در کروموزوم تغییر می دهد . نقش جهش اغلب به عنوان تضمینی است برای آنکه احتمال جستجو در رشته هرگز صفرنگردد. (لاورسون و آرویز ۱۹۸۷) عملگر جهش روی تک تک بیت های کروموزوم انجام می گیرد . عمل جهش یک ژن شامل تبدیل عدد صفر به یک وبالعکس می باشد.این اتفاق براساس یک احتمال کوچک اتفاق می افتد.دراین روش یک عدد تصادفی بین صفر تا یک تولید شده اگر عدد تصادفی تولید شده از کوچکتر باشد مقدار خروجی را درست(True) وگرنه مقدار خروجی راغلط بر می گرداند. اگر برای هر بیت مقدارخروجی درست باشد بیت تغییر می کند و گرنه بیت بدون تغییر باقی می ماند.بیت های یک رشته به صورت مستقل جهش پیدا می کنند.
از عملگر جهش به منظور بازیابی اطلاعات از دست رفته استفاده می شود. فرض کنید که مقدار بیت های یک جمعیت در یک محدوده خاص برابر صفر شده است در حالی که جواب بهینه نیاز به یک عدد یک برای یک بیت به خصوص دارد.
واضح است که عملگر ادغام قادر به تولید چنین فرزندی نیست بنا براین در این حالت باید از عملگر جهش استفاده نمود. به مثال زیر دقت کنید. همه بیت ها سمت چپ رشته ها برابر صفر است. اگر در جواب بهینه لازم باشد بیت سمت چپ عدد یک باشد آنگاه عملگر ادغام هرگز قادر به تولید چنین جوابی نیست بنا براین باید از عملگر جهش استفاده نمود.
۰۱۱۰۱۰۱۱
۰۰۱۱۱۱۰۱
۰۱۱۱۱۰۱۰ ۱۱۱۰۰۱۱
۰۰۰۱۰۰۱۱
این عمل برای جلوگیری ازهمگرایی سریع وکمک به الگوریتم جستجو برای فرار از به دام افتادن در مقادیر موضعی (بهینه محلی)مفید است.همچنین این عمل برای حفظ حالت متفاوت بودن ومتمایز بودن رشته ها به کار می رود و موجب گسترش فضای جستجو می شود.
نرخ جهش(Mutation Rate):
همان احتمال جهش یااست این عدد معمولا برای یک جمعیت با اندازه ۳۰تا۲۰۰ عضئ بین۰۰.۱تا ۰.۵ خواهد بود.نکته مهمی که باید در اینجا اشاره نمودآن است که هر چه میزان نرخ جهش افزایش یابد الگوریتم به سمت تصادفی شدن پیش می رود برای جلوگیری از این امر معمولا این نرخ را کوچک( حدود۳%) در نظر می گیرند.
یکی ازپارامتر های کنترلی الگوریتمQAPتعیین تعداد ژنهای جهش است. با توجه به این که با افزایش نرخ جهش الگوریتم به سمت یک الگوریتم تصادفی پیش می رود می توان نتیجه گرفت که تعدادژنهای تعیین شده برای جهش نباید خیلی زیاد شود.
الف- جهش یکنواخت : این عملگر که توسط میکالویچ ارائه شده یک ژن از کروموزوم به صورت تصادفی انتخاب شده و مقدار آن به مقدار تصادفی دیگری تغییر می یابد ، یعنی یک عدد تصادفی دربازه که L طول کروموزوم می باشد انتخاب شده و ژن موجود در آن مکان از کروموزوم تغییر می کند به عنوان مثال :
P : 0 1 0 0 1 0 1 1 0
اگر یک کروموزوم و عدد تصادفی ایجاد شده ۵ باشد بنابراین کروموزوم م موجود در محل ۵ عوض می شود یعنی یک تبدیل به صفر شده در نتیجه به صورت زیر در می آید .
C : 0 1 0 0 0 0 1 1 0
ب) جابجایی : در این روش دو ژن به صورت تصادفی انتخاب شده و با یکدیگر تعویض می شوند مثلاً اگر دو عدد تصادفی ۳ و ۶ باشند داریم .
P: 3 4 7 5 2 8 1 6
C: 3 4 8 5 2 7 1 6
ج- جهش وارونگی : در این روش ابتدا دو عدد تصادفی را بین که L طول کروموزوم می باشد انتخاب کرده و کروموزوم به سه بخش تقسیم می شود حال قسمت وسط بر عکس می گردد مثلاًٌ فرض کنید .
P : 4 3 / 5 7 1 / 6 2 8
و دو عدد تصادفی ۲ و ۵ به صورت زیر در می آید .
C :4 3 / 1 7 5 / 6 2 8
۳- تابع برازندگی : برای تشخیص کروموزوم مناسب تر در فرآیند انتخاب می بایست از یک شاخص جهت ارزیابی کروموزوم ها استفاده نمود در مورد مسائل بهینه سازی توابع معمولاً این شاخص همان مقدار تابع هدف مساله می باشد یعنی هر کروموزوم تبدیل به یک جواب متناظر شد و در تابع هدف قرار می گیرد آنگاه مقدار تابع هدف برای هر جواب بهتر باشد کروموزوم متناظر با آن جواب مناسب تر خواهد بود . اما در مورد بعضی مسائل که پیچیده تر هستند می بایست اقدام به تعریف تابع بر ارزش نمود.
۴- مکانیسم انتخاب : مکانیسم انتخاب به چگونگی انتخاب کروموزوم ها از فضای نمونه گیری مربوط می شود و دارای سه رویکرد ذیل می باشد :
* نمونه گیری تصادفی
* نمونه گیری قطعی
* نمونه گیری مختط
* روش های انتخاب به این گونه است :
* روش چرخه رولت(Roulette Wheel)
* روش مسابقه(Tournament )
* روش رتبه بندی(Rank)
* روش حالت پایدار(Steady State )
۱) روش چرخه رولت(Roulette Wheel):دراین روش به هررشته با توجه به تابع برازندگی آن(Fitness)تخصیص می یابد.F(وسپس با توجه به این مقدار تخصیص داده شده احتمال انتخاب هر رشته را محاسبه نموده ودست به انتخاب رشته والد می زنیم.(حاصل جمع این احتمال ها باید برابر یک شود)احتمال رشته انتخابیi ام برابر است با

n اندازه جمعیت است. برای مثال فرض کنید۸ رشته داریم. درجدول۲-۲ مقدارتابع برازندگی و احتمال محاسبه شده برای این ۸ رشته آمده است.
جدول ۲-۲ محاسبه احتمال در چرخه رولت
P
Fitness (F)
Population NO
۰.۶
۱.۲
۱
۰.۱۳
۲.۵
۲
۰.۱۷
۳.۲
۳
۰.۴
۰.۸
۴
۰.۲۷
۵.۳
۵
۰.۱
۰.۲
۶
۱۰/۰
۹/۱
۷
۰.۲۲
۴.۲
۸

در ادامه می توان هر کدام از این درصد های احتمال رابر روی یک چرخه رولت نمایش دادآن گاه مقدار مناسب برای انتخاب پس ازn بار(دراینجا۸ بار) چرخیدن این چرخ به دست می اید.

شکل ۲-۳ چرخه رولت
۲) روش مسابقه(Tournament): در روش رولت گاهی با مشکلاتی از قبیل کندی درهمگرایی ویا همگرایی ناگهانی مواجه می شویم. بنابراین گاهی برای غلبه براین مشکلات از این روش استفاده می نماییم. دراین روش یک زیر مجموعه کوچکی از رشته(کروموزوم ها) به صورت تصادفی انتخاب شده وسپس از میان این رشته ها با توجه به تابع برازندگی (Fitness)دست به انتخاب والد ها می زنیم.
برای مثال قبل ابتدا به صورت تصادفی رشته های ۱و۵ انتخاب شده وسپس با توجه به مقدار برازندگی ۵انتخاب می شود. این روش انتخاب را می توان در جدول۲-۳ خلاصه نمود.دراین مثال۵ بار دست به انتخاب والد زدیم.
جدول ۲-۳ محاسبات روش مسابقه
والد برنده شده با توجه به تابع برازندگی
موارد انتخاب شده تصادفی
۵
۵و۱
۸
۸و۳
۲
۲و۴
۵
۳و۵
۱
۱و۶

این عملکرد نسبت به چرخه رولت بهتر است به همین دلیل در جمعیت های بسیار بزرگ به عنوان بهترین روش انتخاب می شود.(در حل مسئلهQAPنیز ما تقریبا از این روش استفاده نمودیم.)
۳) روش رتبه بندی((Rank: در روش چرخه رولت اگر مقدار تابع برازندگی کروموزوم ها خیلی با هم تفاوت داشته باشد به مشکل بر میخوریم. برای نمونه اگر یک کروموزوم۹۰%ازمجموع برازندگی کروموزوم ها را به خود اختصاص دهد دراین صورت احتمالی برابر با ۹۰%گرفته وبیشتر مواقع به عنوان کروموزوم والد انتخاب می شود وعامل تصادفی سازی که یکی ازویژگی های روش های متاهیوریستیک و ازجملهGAاست رابه شدت محدود می کند. برای غلبه براین مشکل از روش رتبه بندی استفاده می نماییم. دراین روش کروموزوم ها به ترتیب صعودی تابع برازندگیشان رتبه بندی شده وسپس با توجه با این رتبه ها احتمال هرکروموزوم محاسبه شده ودست به انتخاب می زنیم.
مثال مربوط به چرخه رولت با استفاده از این روش به صورت زیر در می آید. احتمال هر کروموزوم ازتقسیم رتبه آن کروموزوم بر مجموع رتبه کروموزوم ها به دست می آید.
جدول ۲-۴ محاسبات روش رتبه بندی
P
Rank
Fitness (F)
Population No
۰.۸
۳
۱.۲
۱
۰.۱۴
۵
۲.۵
۲
۰.۱۷
۶
۳.۲
۳
۰.۰۶
۲
۰.۸
۴
۰.۲۲
۸
۵.۳
۵
۰.۰۳
۱
۰.۲
۶
۰.۱۱
۴
۱.۹
۷
۰.۱۹
۷
۴.۲
۸

شکل ۲-۴ چرخه رولت در روش رتبه بندی
همان طور که ازشکل می توان دریافت اشکال این روش آن است که به آهستگی همگرا(Slow Convergence)می شود.زیرادراین روش بهترین کروموزوم ها با سایر کروموزوم ها تفاوت چندانی ندارند.
علاوه برروش بالا که اشاره شد روش دیگری نیز برای تغییر مقدارتفاوت تابع برازندگی دو کروموزوم وجود دارد وآن استفاده از جذر مقدار تابع برازندگی به جای خود تابع برازندگی است.
۴) روش حالت پایدار(Steady State):این روش متدخاصی برای انتخاب ندارد واساس آن براین اصل استوار است که کروموزوم های نامناسب حذف شده

دسته‌ها: No category

دیدگاهتان را بنویسید