گل سرخ

حل مسئله کوله پشتی صفر و یک با استفاده از GA

شامل 5 مرحله است:

1 . Encoding :

یک انتخاب را بصورت یک رشته بیتی از 0 و1 بطول n (تعداد کالاهای موجود در مغازه) در نظر می گیریم. بیت iام برابر یک است اگر کالای iام انتخاب شود و در غیر اینصورت صفر است.

در این پیاده سازی جمعیت اولیه را برابر 20 در نظر می گیریم.

2 . :Mutation

با یک نرخ خاص که در اینجا 25 درصد انتخاب شده این عمل را انجام میدهیم:

5 رشته (5 رشته از 20 رشته همان 25 درصد میشود) را اتفاقی انتخاب کرده وبطور تصادفی محتوای دو بیت آنرا عوض می کنیم. در نتیجه 5 رشته به جمعیت اولیه اضافه می شود.

3 .Crossover:

با یک نرخ خاص که در اینجا 25 درصد انتخاب شده این عمل را انجام میدهیم:

5 رشته (5 رشته از 20 رشته همان 25 درصد میشود) را اتفاقی انتخاب کرده و جای نیمه راست و چپ آنرا عوض می کنیم. . در نتیجه 5 رشته به جمعیت اولیه اضافه می شود. و مجموع رشته ها 30 تا می شود.

4.Fitness function:

30 رشته بدست آمده از مرا حل قبل را با محاسبه تابع زیر برای هر کدام بصورت نزولی مرتب می کنیم:

Fitness =

bi= بیت iام رشته

Pi= سود مربوته

Wi=وزن مربوته

سپس 20 رشته اول را به عنوان جمعیت اولیه مرحله بعد در نظر می گیریم.

5.Termination:

حلقه بالا را 100 مرتبه تکرار می کنیم و سپس اولین رشته ای که مقداری کمتر از W داشته باشد را به عنوان جواب بر می گردانیم.