اشکال در (Roulette Wheel (GA

[TheMatrix]

سلام دوستان.
من تازه با GA یا همون الگوریتم ژنتیک آشنا شدم و دیدم واقعا چیز محشریه.
من یه برنامه ی ساده با استفاده از GA نوشتم که یه رشته ای رو پیدا میکنه. روش من برای انتخاب Roulette Wheel یا همون چرخ گردان هستش ولی من وقتی برنامه رو اجرا میکنم بعد از گذشت حتی 1000000 بار تکامل, هیچ کدوم از رشته ها اصلا به رشته ی هدف نزدیک نشدند.
من یه چنتا کانتر و متغیر به برنامم اضافه کردم و دیدم مقدار تولید مثل یا cross-over در کروموزم های با برازندگی بالاتر با مقدار تولید مثل در برازندگی های پایین مساوی است, و این بدین معنی است که قسمت انتخاب طبیعی یا همون تابع select درست کار نمیکنه.
این اون تابعی ه که من برای انتخاب نوشتم:

int select()
{
int SUM=0,N=0,TSUM=0;
for(int i=0; i<population_size; i++)
SUM=SUM+score[i];
N=random(0,SUM);
for(int i=0; i<population_size; i++)
{
TSUM=TSUM+score[i];
if(TSUM>=N)
return i;
}
return -1;
}

توجه کنید آرایه ی score در اینجا برازندگی رشته ها را در بر دارد.
سورس خود برنامه رو هم میزارم.(سورس به زبان سلیس ++C)
ممنون میشم کمکم کنید.

[Alireza_Salehi]

1. معیار توقف چیست؟ (while(1 معنی نمیده!
2. چرا تعداد جمعیت ثابت است و offspring ها مستقیما بر روی جمعیت نسل قبل قرار می گیرند؟
3. معیار شما برای محاسبه fitness چیست؟ اگر تعداد کاراکتر های مشابه معیار بوده چرا با fitness با مقدار 6 (که از تعداد کاراکتر ها هم بیشتر است!!!) همچنان الگوریتم ادامه پیدا می کند؟
4. mutation کجاست؟
5. مسئله Word Matching با رشته های طولانی تر از این (18 کاراکتر) با حدود 23 تکرار (230 کرومزوم) همگرا می شود!

الگوریتم ژنتیک در تصویر زیر نشان داده شده است، با کد خودتون مقایسه کنید(منبع (http://eu.wiley.com/WileyCDA/WileyTitle/productCd-0471127418.html)).

[TheMatrix]

1. معیار توقف چیست؟ (while(1 معنی نمیده!
2. چرا تعداد جمعیت ثابت است و offspring ها مستقیما بر روی جمعیت نسل قبل قرار می گیرند؟
3. معیار شما برای محاسبه fitness چیست؟ اگر تعداد کاراکتر های مشابه معیار بوده چرا با fitness با مقدار 6 (که از تعداد کاراکتر ها هم بیشتر است!!!) همچنان الگوریتم ادامه پیدا می کند؟
4. mutation کجاست؟
5. مسئله Word Matching با رشته های طولانی تر از این (18 کاراکتر) با حدود 23 تکرار (230 کرومزوم) همگرا می شود!

الگوریتم ژنتیک در تصویر زیر نشان داده شده است، با کد خودتون مقایسه کنید(منبع (http://eu.wiley.com/WileyCDA/WileyTitle/productCd-0471127418.html)).

مگه تعداد جمعیت نباید ثابت باشه؟

[Alireza_Salehi]

بله ولی این که در مرحله Selection از کجا انتخاب شوند مهم است.

مثلا 10 کرومزوم داریم و از طریق Crossover نیز 6 کروکزوم جدید و از طریق mutation هم 3 کروکزوم جدید تولید می شوند.
حالا دو روش داریم :
1. از بین این 19 تا کرومزوم، 10 کرومزوم انتخاب شوند.
2. تنها از بین کرومزوم های جدید و کرومزوم های تکامل نیافته، 10 کرومزوم انتخاب شوند. (روش شما)

به نظر من اولی بهتر عمل می کند.

[TheMatrix]

از راهنمایی شما ممنونم.
ولی بازم یه سوال داشم:
هدف ما از جهش, ایجاد کروموزم های تکی جدید است یا هدف, تغییر کروموزم های جدید(فرزندان) است؟

در ضمن, با استفاده از راهنمایی های مفید شما من برنامه را بازنویسی کردم که کار هم میکند, منتهی یه مشکل کوچیک داره اونم اینه که تعداد جمعیت اولیه نمیتونه فرد باشه.

ممنون میشم مشکلات برناممو بگید.

[Alireza_Salehi]

هدف از جهش (mutation) ایجاد کرومزوم های تکی جدید است. برای مثال اگر 10 کرومزوم داشته باشیم و 6 تای آنها در crossover شرکت کرده باشند 4 تای دیگر می توانند در mutation شرکت کنند.
و این که چند تا کرومزوم در crossover و چند تا در mutation شرکت کنند تجربی است، نرخ های مختلف را تست کنید. (البته نرخ mutation معمولا کم در نظر گرفته می شود)

به طور کلی در الگوریتم ژنتیک عملگر های موجود جهت اجتناب از ماکزیمم محلی (local optima) هستند و در واقع عملگری مانند جهش فضای جستجو را جهت انتخاب هایی بهتر گسترده تر می کند.