اصول الگوريتم ژنتيک

کد گذاری3

  قبل از اين که يک الگوريتم ژنتيک براي يک مسئله اجرا شود، بايد روشی را براي کد کردن کوروموزوم ها به زبان کامپيوتر به کار ببریم .اين مرحله به اين مفهوم است که ما بايد با ارائه يک شبيه سازی و جايگذاری را , برای کليه جوا های ممکن، داریم.

کدگذاری دودویی

  عمومي ترين روش وآشناترين نوع کدگذاري در GA ، همان روش کدگذاري دودویی است، زیرا در تحقيقات اوليه GA اين روش مورد استفاده قرار گرفت که روش بسيار ساده ای است.

  در روش کد گذاري دودویی همه ي کورموزم ها با رشته هايي که شامل بيت هايي از 1-0 است کد مي شوند .

اغلب اين روش کدگذاري براي اکثر مسائل طبيعي نيست و بعد از CrossOver[4] و جهش[5]  بايد تغييراتي درآن به وجود آورد.

شکل 5.2 : مثالی از کروموزوم ها به روش کدگذاری دودویی

کدگذاری مقادیر

  شيوه ي کدگذاری مقادیر را در مواردی بکار می بریم که مسئله دارای مقادیر پيچيده اي است، مانند اعداد صحيح که استفاده از کد گذاري باينري در اين حالت بسيار دشوار است .

شکل 6.2: مثالی از کروموزوم ها با استفاده از روش کدگذاری مقادیر

 کدگذاری مقادیر روش خوبي براي کدگذاري مسئله هاي خاص است، ولي با اين وجود براي اينگونه کد گذاري اغلب بايد شيوه هاي توسعه يافته ي جديدي در Crossover و جهش به کار برد .                               

کدگذاری درختی

  کدگذاری درختی اساساً براي استنتاج برنامه يا بيان طرح برنامه هاي الگوريتم ژنتیک مورد استفاده قرار می گیرد. درکدگذاري درختي هر کروموزم يک درخت براي  توابع يا دستورات در زبان برنامه نويسي مانند شکل زير است.       

شکل 7.2 : مثالی از کروموزوم ها به روش کدگذاری درختی

کد گذاري درختي براي استنتاج برنامه ها يا هر راهبردی که بتواند به صورت درخت کدگذاري شود بسيار مفيد است. زبان برنامه نويسيLISP  اغلب بدين منظور به کار ميرود.  بنابراين Crossover و جهش را مي توان به سادگي با اين روش انجام داد.

   ارزیابی2

   ما در اين مرحله با معرفی يک معيار و اندازه به بهتر بودن يا نبودن هر جواب ممکن از جمعيت اوليه پی می بريم. يعنی اينکه اين معيار به ما مي گويد که مثلا جواب x واقع در جمعيت اوليه  (First Population)چقدر خوب است .

  اين معيار می تواند با نسبت دادن يک عدد به هر جواب ممکن ميزان خوب بودن آن جواب را بيان کند. مثلا اگر داشته باشيم f(b)=5 f(a)=3  و اين بدان معنی است که عضو bدر جمعيت اوليه بهتر از a  است يا مقدار Fitness بالاتری نسبت به a دارد.

 انتخاب

همان طور که در طرح کلي الگوريتم ژنتيک مطرح گشت ابتدا کروموزوم ها انتخاب مي شوند تا والدين نسل بعد باشند و فرآيند هاي CrossOver روي آن ها انجام گيرد، حال يک سوال اساسي مطرح است که اين انتخاب والدين چگونه وبر چه معياري استوار است؟ با توجه به نظريه تکاملي داروين، بهترين ها ژن ها براي تواليد نسل هاي آينده زنده مي مانند.

روش هاي مختلفي براي انتخاب موجود است، به طور مثال:

 (roulette wheel selection , Boltzman selection, tournament selection , rank selection, steady state selection )

چند روش مهم در اينجا توضيح داده مي شود .

انتخاب گردونه دوار

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

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

فرايند انتخاب شدن بالا را مي توان  با الگوريتم زير عملياتي کرد.

1 _ [SUM] : ابتدا مجموع همه مقادیر تناسب هاي کوروموزوم هاي يک نسل را حساب مي کنيم.

2 _ [SELECT] : از فاصله ي (0,S) به صورت رندوم يک عدد را مثل r انتخاب مي کنيم.

3 _ [LOOP] :  برو به نسل و تناسب را از 0 جمع کن، هنگامي که جمع s بزرگتر از r است بايست و برگرد به کورموزومي که روي آن بودي.

 البته واضح است که مرحله اول براي هر نسل يک بار اجرا مي شود .

انتخاب رتبه ای

 روش انتخاب قبلي که توضيح داده شد روش خوبي است ولي در حالتي که اختلاف ارزش هاي تناسب در کروموزوم ها زياد باشد دچار مشکل مي شود مثلاً اگر ارزش بهترين کورموزوم 90% باشد مجموع کوروموزوم هاي ديگر، شانس بسیار کمتري براي انتخاب شدن دارند .

در شيوه  انتخاب رتبه ای به اين صورت عمل مي کنيم که ابتدا جمعيت يا نسل را مرتب مي کنيم سپس به هر کورموزوم با توجه به مقدار تناسب آن عددي اختصاص مي دهيم، مثلا بدترين کروموزوم 1، کورموزوم ماقبل بدتري 2  و الي آخر، تا اينکه به بهترين کورموزوم N را نسبت مي دهيم (N تعداد کورموزوم هاي نسل) .

در تصاوير زیر به وضوح، چگونگي تغييرات نمودار، از شيوه ي ارزش گذاري با تناسب به روش عدددهي مشاهده می کنيد .

انتخاب حالت استوار

اين شیوه، روش خاصی براي انتخاب والدين نيست و ايده آل اصلي اين روش براي انتخاب جمعيت يا نسل جديد حفظ بخش بزرگی از کروموزوم ها براي نسل جديد است. روش انتخاب حالت استوار در الگوریتم ژنتیک، به این صورت عمل مي کند که در همه توليدها تعداد معدودی کورموزوم خوب (با تناسب بالا) برای تولید فرزندان جدید انتخاب مي شوند، سپس تعدادي از کوروموزوم هاي بعدی (باتناسب  پايين ) حذف شده و به جاي آنها فرزندان جديد جايگذاري مي شود،  و نسل جديد به وجود آمده براي توليد جديد حفظ مي گردد .

 نخبه گزینی

  بهترین‌های هر نسل با توجه به درجه تناسبشان مستقیماً به نسل بعدی منتقل می‌شوند. این كار برای آن است كه مطمئن باشیم بهترین پاسخ ما در نسل بعدی نسبت به نسل قبل بدتر نشود.

  عملگرهای تغییر

در الگوريتم ژنتيک برای بوجود آوردن يک نسل جديد( يا يک سری کروموزوم جديد( از جوابها ما يک سری از تغييرات را روی جواب های انتخاب شده  (Selected) يا کروموزوم ها اعمال می کنيم به اين سری از تغييرات اعمال عملگر  می گوييم.

حال عملگرهای ما در اين تغييرات دو عملگر Crossover و Mutation می باشد.

عملگر Crossover

  هدف از CrossOver تولید فرزندان از دو والد است، در طی این فرایند بعضی از ژن‌های دو والد با هم عوض می‌شوند، این عملگر در کروموزوم های باينري با انتخاب يک مکان تصادفي در کروموزوم ها  ,تغيير را آغاز مي کند. بخش اول ژن هاي پدر و بخش دوم ژنهاي مادر با هم ترکيب مي شوند(و بالعکس) تا دو فرزند توليد شوند.  و تضمینی نیست كه درجه‌ی تناسب(امتیاز) فرزندان بهتر از والدین باشد. در واقع هدف از CrossOver، فقط تغییر دادن جواب ها و حركت در فضای جستجو است.