رفتن به مطلب

کد الگوریتم ژنتیک بهمراه توضیح


ارسال های توصیه شده

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

که در ابتدا توضیحات الگوریتم ژنتیک آورده شده است

برای بدست آوردن تعداد خطا از الگوریتم طبقه بند نزدیک ترین همسایه استفاده کرده ایم.الگوریتم ژنتیک

 

گلدبرگ در سال ١٩٨٩ قواعد الگوريتم ژنتيك را ارائه نمود و در سال ١٩٩٠ همگرایي الگوريتم ژنتيك ثابت شد. الگوريتم هاي ژنتيك، هيوريستيك هاي جستجو و الگوريتم هاي بهينه سازي ای هستند كه به طور موازي اجرا مي شوند و بوسيله اصل داروين از انتخاب طبيعي و تكثير ژنتيكي الهام گرفته شده اند. به عبارت ديگر اين الگوريتم ها، تكنيك هاي بهينه سازي بر اساس انتخاب و تركيب مجدد راه حل هاي اميد بخش مي باشند. در الگوريتم هاي ژنتيك سنتي، راه حل ها به عنوان رشته هاي باينري 0 و 1 نمايش داده مي شوند. چارچوب الگوريتم ژنتيك در شکل1 نشان داده شده است.

 

تصویر یک

شكل1. چارچوب الگوريتم ژنتيك

tw58fz5m61253j61ae3m.png

 

تصویر دوم

شکل2. عملگرهای ژنتیک

r69gu53t0tml43yjvzr.png

 

در گام اول جمعیت اولیه تولید می شود. قبل از هرچیز مقادیر کروموزوم ها که وزن دهی ویژگی ها هستند، بطور تصادفی مقداردهی اولیه می شوند. ابتدا باید ساختار کروموزوم را که به فرم رشته های باینری است طراحی کنیم. همانطور که در شکل3 نشان داده شده، طول هر کروموزوم n بیت است.

تصویر سوم

شکل3. ساختار ژن

 

q9ytdypugytimxllq0cm.png

 

بعد از تولید جمعیت اولیه، سیستم با استفاده از پارامترهای موجود در کروموزوم ها، الگوریتم KNN را اجرا می کند و عملکرد هر کروموزوم توسط تابع ارزیابی در الگوریتم ژنتیک محاسبه می شود. هدف اصلی ما پیدا کردن پارامترهای بهینه و یا نزدیک به بهینه ای است که دقیق ترین راه حل را تولید کند. تابع ارزیابی را به صورت زیر تعریف می کنیم.

 

[TABLE=align: left]

[TR]

[TD][/TD]

[/TR]

[TR]

[TD][/TD]

[TD][/TD]

[/TR]

[/TABLE]

cost=error

 

که Error خطای دسته بندی است.

در گام آخر، با استفاده از عملگرهای ژنتیک نسل جدیدی تولید می شود. با توجه به مقدار تابع ارزیابی برای هر کروموزوم، کروموزوم هایی با ارزش بالاتر انتخاب شده و برای تولید جمعیت جدید از عملگر های Crossover و Mutationاستفاده می کنند.

عملگر آميزش (Crossover ):

در جریان عمل تلفیق به صورت اتفاقی بخشهایی از کروموزوم ها با یکدیگر تعویض می شوند. این موضوع باعث می شود که فرزندان ترکیبی از خصوصیات والدین خود را به همراه داشته باشند و دقیقاً مشابه یکی از والدین نباشند. [5]

هدف تولید فرزند جدید می باشد به این امید که خصوصیات خوب دو موجود در فرزندشان جمع شده و یک موجود بهتری را تولید کند.

روش کار به صورت زیر است:

بصورت تصادفی یک نقطه از کروموزوم را انتخاب می کنیم

ژن های مابعد آن نقطه از کروموزوم ها را جابجا می کنیم

 

  • تلفیق تک نقطه ای (Single Point Crossover)

اگر عملیات تلفیق را در یک نقطه انجام دهیم به آن تلفیق تک نقطه ای می گویند.

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

تصویر چهارم

شکل 4 یک نمونه تلفیق (آمیزش)

301lyk21crpwujz7badg.jpg

 

در شکل بالا کروموزومهاي 1 و2 در نقش والدين هستند. و حاصل توليد مثل آنها در رشته هائي بنام Offspring ذخيره شده است.دقت شود که علامت "|" مربوط به نقطه شروع توليد مثل مي باشد و در رشته هاي Offspring اعدادي که بعد از نقطه شروع توليد مثل قرار مي گيرند مربوط به کروموزومهاي مربوط به خود مي باشند.بطوريکه اععدار بعد از نقطه شروع مربوط به Offspring1 مربوط به اعداد بعد از نقطه شروع مربوط به کرومکوزوم 1 و اعداد بعد از نقطه شروع توليد مثل مربوط به Offspring2 مربوط به اعداد بعد از نقطه شروع توليد مثل مربوط به کروموزوم 2 مي باشند

 

  • روش ادغام دو نقطه ای((Two-point CrossOver :

در این روش دو مکان را به صورت تصادفی انتخاب کرده و مقادیر بین این دو نقطه را جابجا می کنیم.

تصویر پنجم

dahu47kzmpse7dfsl4at.jpg

 

شکل 5 یک نمونه تلفیق (آمیزش)

 

  • تلفیق نقطه ای (Multipoint Crossover) :

می توانیم این عملیات را در چند نقطه انجام دهیم ، که به آن بازترکیبی چند نقطه ای می گویند

 

  • .تلفیق جامع (Uniform Crossover) :

اگر تمام نقاط کروموزوم را بعنوان نقاط بازترکیبی انتخاب کنیم به آن بازترکیبی جامع می گوئیم.

عملگر جهش (Mutation ):

پس از اتمام عمل آميزش, عملگر جهش بر روي كروموزوم‏ها اثر داده مي‏شود. اين عملگر يك ژن از يك كروموزوم را به طور تصادفي انتخاب نموده و سپس محتواي آن ژن را تغيير مي‏دهد. اگر ژن از جنس اعداد دودويي باشد, آن را به وارونش تبديل مي‏كند و چنانچه متعلق به يك مجموعه باشد, مقدار يا عنصر ديگري از آن مجموعه را به جاي آن ژن قرار مي‏دهد. در شكل 6 چگونگي جهش يافتن پنجمين ژن يك كروموزوم نشان داده شده است. [5]

پس از اتمام عمل جهش, كروموزوم‏هاي توليد شده به عنوان نسل جديد شناخته شده و براي دور بعد اجراي الگوريتم ارسال مي‏شوند.

 

[TABLE=align: left]

[TR]

[TD][/TD]

[/TR]

[TR]

[TD][/TD]

[TD=align: center][/TD]

[/TR]

[/TABLE]

تصویر ششم

6lyvck1tojzql5bkaidm.png

 

 

 

 

 

 

 

 

 

 

 

در این کد ما از single crossover و جهش را هم فقط در یک بیت انجام داده ایم.......

دیتا بیس مورد استفاده pima از دیتا بیس های UCI

برای مشاهده این محتوا لطفاً ثبت نام کنید یا وارد شوید.

برای مشاهده این محتوا لطفاً ثبت نام کنید یا وارد شوید.

لینک به دیدگاه

البته نا گفته نماند که در این کد بنده از الگوریتم ژنتیک برای وزن دهی استفاده کرده ام............

نحوهی وزن دهی به ویژگی ها به این صورت است که ما برای هر ویژگی 14 بیت در نظر می گیریم . حال برای محاسبه وزن، دسیمال این چهارده بیت را بدست آورده و بر (دو به توان 14) منهای یک تقسیم می کنیم. و این می شود وزن آن ویژگی ......

دوستان می توانند برای انتخاب ویژگی نیز از الگوریتم ژنتیک استفاده کنند......

لینک به دیدگاه
  • 2 سال بعد...

به گفتگو بپیوندید

هم اکنون می توانید مطلب خود را ارسال نمایید و بعداً ثبت نام کنید. اگر حساب کاربری دارید، برای ارسال با حساب کاربری خود اکنون وارد شوید .

مهمان
ارسال پاسخ به این موضوع ...

×   شما در حال چسباندن محتوایی با قالب بندی هستید.   حذف قالب بندی

  تنها استفاده از 75 اموجی مجاز می باشد.

×   لینک شما به صورت اتوماتیک جای گذاری شد.   نمایش به صورت لینک

×   محتوای قبلی شما بازگردانی شد.   پاک کردن محتوای ویرایشگر

×   شما مستقیما نمی توانید تصویر خود را قرار دهید. یا آن را اینجا بارگذاری کنید یا از یک URL قرار دهید.

×
×
  • اضافه کردن...