Artificial Intelligence - هوش مصنوعی - حل مسئله کوله پشتي به روش هاي مختلف

Artificial Intelligence - هوش مصنوعی (http://artificial.ir/intelligence/)

- حل مسائل معروف هوش مصنوعي (http://artificial.ir/intelligence/forum102.html)

- - حل مسئله کوله پشتي به روش هاي مختلف (http://artificial.ir/intelligence/thread620.html)

حل مسئله کوله پشتي به روش هاي مختلف

دوستان بياييد مسئله کوله پشتي را با روش هاي مختلف با هم حل کنيم:rolleyes:
حل مسئله با روش هايي مثل:
الگوريتم ژنتيک
الگوريتم عقبگرد
و غيره

مسئله کوله پشتی چیست؟
فرض کنید که جهانگردی می خواهدکوله پشتی خود را با انتخاب حالتهای ممکن از بین وسائل گوناگونی که بیشترین راحتی را برایش فراهم می سازند پر کند. این مسئله می تواند با شماره گذاری این وسائل از 1 تا n و تعریف برداری از متغیرهای دودویی(Binary) (j = 1,2,…n) بصورت ریاضی فرمول بندی شود. به این معنی که: اگر شیء j ام انتخاب شود در غیر اینصورت وقتی میزان راحتی باشد که وسیله j ا م فراهم می آورد و وزن آن و c اندازه کوله پشتی باشد. مسئله ما انتخاب برداری از بین بردارهای دودویی x است،که محدودیت را بر آورده کند. بطوریکه تابع هدف ماکزیمم مقدار خود را بگیرد به عنوان نمونه ای از مسائلی که می توانند بصورت مساله کوله پشتی فرمول بندی شوند، مسئله زیر را در نظر بگیرید: فرض کنید که شما مایل به سرمایه گذاری همه یا قسمتی ازسرمایه تان باشید. اگر مبلغی که برای سرمایه گذاری در نظر گرفتید c دلار باشد و n مورد برای سرمایه گذاری ممکن باشد ، اجازه دهیدکه سود حاصل از سرمایه گذاری j ام و مقدار دلارهایی باشد که آن سرمایه گذاری لازم دارد . بدین ترتیب جواب بهینه مسئله کوله پشتی که تعریف کردیم به ما این امکان را می دهدکه بهترین حالت ممکن را از بین حالتهای مختلف سرمایه گذاری انتخاب کنیم. در این رابطه باید روشی برای حل این مسئله پیدا کرد . یک روش ابتدایی که در نگاه اول توجه ما را به خود جلب می کند ، عبارت از برنامه نویسی برای کامپیوتر به منظور امتحان کردن تمامی بردارهای دودویی ممکن x است، تا از بین بردارهایی که محدودیت مسئله را ارضاء می کنند بهترین را انتخاب کند. متاسفانه تعداد چنین بردارهایی است.بطوریکه یک کامپیوتر فرضی که می تواند یک بیلیون بردار را در یک ثانیه امتحان کند؛برای n = 60 بیش از 30 سال وقت لازم دارد و بیش از 60 سال برای n = 61 و دهها قرن برای n = 65 والی اخر. با این وجود ،با استفاده از الگوریتمهایی خاص می توان در بسیاری موارد مسئله ای با n = 100 000 را در عرض چند ثانیه روی یک کامپیوترکوچک حل کرد

در لينک زير برنامه کوله پشتي را که از طريق الگوريتم ژنتيک حل شده (در متلب )
دانلود کنيد:

دانلود کد حل مسئله کوله پشتی توسط الگوریتم ژنتیک

در ضمن مطالعه مقالات (انگليسي) زير هم براي حل اين مسئله با الگوريتم ژنتيک بسيار مفيد است:;)

مسئله کوله پشتی صفر و یک

در این مسئله مجمو عه ای از قطعات داریم که هر یک دارای وزن و ارزش معین است.

- اوزان و ارزش ها اعداد مثبتی هستند.

- دزدی درنظر دارد قطعاتی که می دزدد درون یک کوله پشتی قرار دهد و اگر وزن کل قطعات قرار داده شده در آن کوله پشتی از یک عدد صحیح مثبتW فراتر رود، کوله پشتی پاره می شود.:)

الگوریتم عقبگرد برای مسئله کوله پشتی صفر و یک

كد:

   void knapsack ( index i ,

 int profit , int weight)

 {

 if ( weight ≤ W &&  profit > maxprofit ) {

 maxprofit = profit ;

 numbest = i ;

 bestset = include;

 }

  if ( promising (i)) {

 include [ i + 1 ] = “yes”;

 knapsack ( i + 1, profit + p [ i + 1] , weight +

 w [ i +1 ]);

 include [ i +1] = “ no”;

 knapsachk ( i +1 , profit , weight );

 }

 }

 bool promising ( index i )

 {

  index j , k ;

 

 int totweight ;

 float bound;

 if ( weight ≥ W)

  return  false ;

 {

 j = i +1 ;

 bound = profit ;

 totweight = weight ;

  while ( j <= n && totweight + w[j] <= W) {

 totweight = totweight + W [j];

 

  bound = bound + p[j];

 j++;

 }

 k = j;

 if ( k <= n)

 bound = bound + (W – totweight) * p [k]/w[k];

  return bound > max profit ;

 }

 }

مقایسه الگوریتم برنامه نویسی پویا و الگوریتم عقبگرد برای مسئله کوله پشتی صفر و یک

- تعداد عناصری که توسط الگوریتم برنامه نویسی پویا برای مسئله کوله پشتی صفر و یک محاسبه می شود دربدترین حالت به O (minimum (2ⁿ , nW)) تعلق دارد.

- در بدترین حالت ، الگوریتم عقبگرد (ⁿ 2)θ گره را چک می کند.

- الگوریتم عقبگرد معمولا کارایی بیشتری نسبت به الگوریتم برنامه نویسی پویا دارد.

- هوروویتز و شانی ، روش تقسیم و حل را با روش برنامه نویسی پویا ترکیب کرده الگوریتمی برای مسئله کوله پشتی صفر و یک بسط داده اند که دربدترین حالت به O(2^n/2)
تعلق دارد.

سورس کد کوله پشتی به روش 0 و 1

كد:

# include

# include

using namespace std;

void bi(int t[],int n){

for(int i=0; n!=0;i++){

t[i]=n%2;

n/=2;

}



}

int main()

{

int n,i,s,sum,b=-1;

cout<<"enter number of gold pocket :"; 

cin>>n;

cout<<"enter sum:";

cin>>s;

int temp[10]={0},a[10];

for( i=0;i

cin>>a[i];

for(int j=1;j

bi(temp,j);

sum=0;

for(int k=0;k

if(temp[k]!=0)

sum+=a[k];}

if (sum==s){

for(int k=0;k

if (temp[k]==1)

cout<<<" ";

b=1;

cout<



}

if (b==-1)

cout<<"there is not such set"<

return 0;

}

يک الگوریتم داینامیک برای حل مسئله کوله پشتی

كد:

Dynamic-0-1-knapsack (v, w, n, W)



FOR w = 0 TO W

DO c[0, w] = 0

FOR i=1 to n

DO c[i, 0] = 0

FOR w=1 TO W

DO IFf wi ≤ w

THEN IF vi + c[i-1, w-wi]

THEN c[i, w] = vi + c[i-1, w-wi]

ELSE c[i, w] = c[i-1, w]

ELSE

c[i, w] = c[i-1,w]

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

كد:

Algorithm greedy_knapsock(p,w,m,x,n)

//object ordered so that (P[i]/W[i])>(P[i+1]/W[i+1])

m=0

cu=m //remaning capacity

for i=1 to n

if w[i]>cu then exit

x[i]=1

cu=cu-w[i]

next i

if i<=n then x[i]=cu/w[i]

end

سورس کد کوله پشتی در سی

كد:

void Knapsack(){

int a[n, w], c[n], v[n], n, w, i, c;

for(c = 0; c <= w; c++){

a[0, c] = 0;

}

for(i = 1, i <= n; i++){

a[i, 0] = 0;

for(c = 1; c <= w; c++){

if(c[i] <= c){

if(v[i] + a[i-1, c-c[i]] > a[i-1, c])

a[i, c] = v[i] + c[i-1, c-c[i]];

else

a[i, c] = a[i-1, c];

}

else

a[i, c] = a[i-1, c];

}

}

}

اين مقاله هم در زمينه حل مساله کوله پشتي چندبعدي با استفاده از اتوماتاهاي يادگير است:)

الگوریتم گریدی برای مساله کوله پشتی با مطلب

سريعترين راه براي يافتن يك جواب تقريبي KP استفاده از اين واقعيت است كه جواب آزاد سازي پيوسته مسئله فقط داراي يك متغير اعشاري است. الگوریتم گریدی از این مطلب برای حل مساله کوله پشتی استفاده می نماید. می توان ثابت کرد که جواب بدست آمده بطور متوسط نزدیک به جواب بهینه است.
برنامه الگوريتم گريدي برای مساله کوله پشتی با مقادیر ۰ و ۱ به زبان مطلب و بصورت پنجره فعال بصورت زیر است.
فرض می شود اشیا براساس نسبت وزنی مرتب شده اند

كد:

n=input('n = ');

c=input('c = ');

d=1:n;

p=input('(pj) = ');

w=input('(wj) = ');

 

bn=0;

for bb=1:n-1;

    if (p(bb)/w(bb))<(p(bb+1)/w(bb+1))

        bn=1;

        break;

    end

end

if bn>0

    ERROR=' The items not sorted correct  TRY AGAIN '

    break;

end

 

cc=c;

s=0;

jj=1;

for j=1:n

    if w(j)>cc

        d(j)=0;

    else

        d(j)=1;

        cc=cc-w(j);

        s=s+p(j);

    end

    if p(j)>p(jj)

        jj=j;

    end

end

if p(j)>s

    s=p(jj);

    for j=1:n

        d(j)=0;

    end

    d(jj)=1;

end

x=d

zq=s

لطفا" اگر امكان داشته باشه مسئله كوله پشتي رو به زبان #c برام بفرستين

مسئله كوله پشتي به زبان #c

نقل قول:

نوشته اصلي بوسيله ziaye (پست 14606)

لطفا" اگر امكان داشته باشه مسئله كوله پشتي رو به زبان #c برام بفرستين

از وبلاگي که دوستمون معرفي کردن ضميمه کردم(hadiabc)

سلام میشه حل مسئله کوله پشتی رو با الگوریتم رقابت استعماری بذارید؟ممنون.

سلام بازم ازتون كمك مي خواستم استادم ازم يه موضوع مرتبط با كلوني مورچه ها خواسته البته با كد متلب مثلا واسه مسيريابي شبكه هاي كامپيوتري كه با استفاده از كلوني مورچه ها حل ميشه كد متلب مي خواد كه اجرا بشه.
لطفا كدشو واسم بفرستين.
ممنون

نقل قول:

نوشته اصلي بوسيله سارافيروزه (پست 21319)

سلام دوست عزیز
برای گرفتن کد اجرایی به لینک زیر یه سر بزن:1:
http://artificial.ir/intelligence/thread351.html

سلام
سال نو رو به تمام دوستان تبریک میگم
من کد حل مسئله کوله پشتی صفر و یک رو با الگوریتم pso در متلب رو لازم دارم.
کسی از دوستان متخصص میتونه کمک کنه
یه سوال : حل این مسئله با الگوریتم ژنتیک بهینه تر یا pso
mer30

چرا تو همه ی این الگوریتم ها ، تعداد هر شئ یکی فرض شده ؟
ضمنا جای الگوریتم حل این مسئله به روش جست و جوی عمیق شونده ی تکراری (ids) خالیه...

نقل قول:

نوشته اصلي بوسيله Reyhane (پست 1982)

سلام
من روش حل مسئله کوله پشتی رو با الگوریتم های موازی با hypercube میخوام! لطفا راهنمایی کنید... ممنون:63:

سلام اگه یه لطف کنید برام کتاب طراحی الگوریتم دکتر نقیب زاده رو به ایمیل زیر ارسال کنید ممنون میشم
real_enriq@yahoo.com

سلام

حل مسئله کوله پشتی با الگوریتم تپه نوردی میخاستم!!

ممنون میشم اینم در کنار بقیه الگوریتما قرار بدین!

مطالب جالب و مفيد بود
متشكرم:67:

نقل قول:

نوشته اصلي بوسيله hadiabc (پست 7458)

سلام
در این وبلاگ
پرو‍‍‍‍‍ژه طراحي الگوريتم و هوش مصنوعي

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

کوله پشتی صفرویک

سلام
دوستان کسی پروژه پیاده سازی الگوریتم های حریصانه و پویا برای کوله پشتی صفر و یک رو اگه با سی شارپ لطفا ضمیمه کنه + مقایسه پیچیدگی زمانی این دو روش

سلام خواهش می کنم اگر کسی میتونه کد الگوریتم ژنتیک این مسٔله رو توضیح بده بد جوری نیاز دارم ممنون

دوستان میشه بگید الگوریتم حل این سوال چی هست؟
In the 0-1 Multiple Knapsack Problem (MKP) a set of n items and a set of m knapsacks (with m n)
are given. With each item j (j = 1; : : : ; n) are associated a prot pj 2 Z+ and a weight wj (we assume
wj 2 Z+). A capacity ci 2 Z+ is associated with each knapsack i (i = 1; : : : ;m). The goal is to select
is to select m disjoint subsets of items so that the total prot of the selected items is maximum and
each subset can be assigned to a dierent knapsack whose capacity is no less than the total weight of
the items in the subset.

Develop a heuristic algorithm based on the Lagrangian relaxation of constraints

باسلام لطفا" مقاله در مورد الگوریتم های فرا ابتکاری که در اون مثال کوله پشتی را از روش مورچگان وجستجوی ممنوع وژنتیک حل شده باشه برام ایمیل کنید تا24 ساعت آینده.باتشکر

سلام
لطفا کد الگوریتم کوله پشتی و 8 وزیر با شبکه هاپفیلددرمتلب

تعریف سوال
شما یک کوله پشتی دارید که حجم ثابتی دارد. همچنین تعدادی وسیله نیز دارید که حجم هر کدام را به شما داده اند. می‌خواهید تعدادی از این وسیله‌ها را در کوله پشتی بریزید به طوری که بیشترین حجم ممکن از کوله پشتی اشغال شود. (فرض کنید شکل وسایل طوری است که فضای بی‌استفاده بین آن‌ها باقی نمی‌ماند.)

الگوریتم
این مسئله یکی از پایه‌ای‌ترین مسائل برنامه‌ریزی پویا است و صورت‌های مختلفی دارد که در انتها به آن‌ها و ایده‌ی اثبات‌شان اشاره می‌شود.
برای حل مدل ساده‌ی سوال، یک آرایه دوبعدی به نام dd به ابعاد(n+1)×(W+1)(n+1)×(W+1) را در نظر بگیرید که در آن nn تعداد وسایل مختلفی که می‌توانیم در کوله‌پشتی بگذاریم وWW حجم کوله‌پشتی است.
مقدارdi,jdi,j برابر یک است اگر و تنها اگر بتوان فقط با استفاده از ii وسیله‌ی اول، دقیقا حجم jj از کوله‌پشتی را پر کرد. یعنی یک زیرمجموعه‌ از ii عضو اول وجود دارد که مجموع وزن‌شان jj است. در غیر اینصورت، مقدارش برابر صفر است.
جواب مسئله بزرگترین اندیس jj است که dn,jdn,j برابر یک باشد.
مقداردهی اولیه: با استفاده از ۰۰ وسیله‌ی اول (استفاده نکردن از وسایل) فقط می‌توان حجم ۰۰ را تولید کرد (کوله‌پشتی خالی) پس تمام خانه‌های به صورت d0,jd0,j برابر صفر اند به جز d0,0d0,0 که برابر ۱۱ است.
به روز رسانی: برای به دست آوردن di,jdi,j دو حالت وجود دارد این که خود وسیله‌ی ii ام در کوله‌پشتی نباشد که در این صورت باید برای این که مقدار یک شود، مقدار di−1,jdi−1,j برابر ۱۱ باشد. حالت دیگر این است که خود وسیله در کوله پشتی باشد. پس در این حالت مقدار در صورتی یک می‌شود که (مقدار حجم وسیله‌ی ii ام را aiai بگیریم) di−۱,j−aidi−۱,j−ai با فرض j≥aij≥ai برابر یک باشد.
شبه کد:

d = {0}
d[0][0] = 1

for i from 1 to n
for j from 0 to W
d[i][j] = d[i-1][j]
if j >= a[i] and d[i-1][j-a[i]] == 1
d[i][j] = 1
اگر دقت کنید می‌بینید احتیاج خاصی به نگه داشتن یک آرایه‌ی دوبعدی نداریم چون برای محاسبه‌ی هر ستون، فقط به ستون قبلی احتیاج داریم و فقط باید ۲ ستون را نگه‌داریم. اما حتی می‌توانیم از این هم جلوتر برویم و فقط یک ستون داشته باشیم. اما در اینجا باید حواس‌مان باشد که اشتباه زیر را انجام ندهیم.
شبه کد با آرایه‌ی یک بعدی (اشتباه):

d = {0}
d[0] = 1

for i from 1 to n
for j from 0 to W
if j >= a[i] and d[j-a[i]] == 1
d[j] = 1
کد بالا یک مشکل دارد. به نظرتان مشکلش چیست؟
فرض کنید در فقط یک وسیله داریم مثلا با حجم ۲ واحد و حجم کوله‌پشتی برابر ۴ است. پس فقط می‌توان ۲ واحد از کوله‌پشتی را پر کرد. اما اگر شبه کد بالا را برای آن اجرا کنید، می‌بینید که مقدار d4d4 برابر یک است. چون با استفاده از وسیله‌ی اول که حجم دو واحد داشت، مقدار d2d2 را یک کردیم، اما بعد از این متوقف نشدیم بلکه چون مقدار d2d2 برابر یک بود، مقدار d4d4 را نیز برابر یک قرار دادیم. پس انگار بیش از یک وسیله با حجم دو داشتیم. در واقع این کد جواب مسئله‌ی دیگری به نام خرد کردن پول است که در آن به تعداد نامتناهی از هر کدام از وسایل داریم.
حال بیایید سعی کنیم مشکل کد بالا را حل کنیم. مشکل این بود که اول با استفاده از وسیله‌ی اول (یا بقیه‌ی وسایل) مقدار خانه‌های پایین جدول را به روز رسانی کردیم و سپس دوباره با استفاده از همان وسیله، مقادیر خانه‌های بالاتر را نیز به روز رسانی کردیم. چطور می‌شود اگر خانه‌ها را به ترتیب دیگری پیمایش کنیم تا این مشکل پیش نیاید؟ حجم وسایل که نمی‌تواند منفی باشد. پس اگر بالا به پایین آرایه را به روز رسانی کنیم، این مشکل پیش نمی‌آید. خودتان هم کمی فکر کنید که چرا این روش درست است.
بر همین اساس کد را تغییر می‌دهیم. شبه کد با آرایه‌ی یک بعدی (درست):

d = {0}
d[0] = 1

for i from 1 to n
for j from W to 0
if j >= a[i] and d[j-a[i]]
d[j] = 1
پیچیدگی‌ الگوریتم
پیچیدگی زمانی که در تمام حالت‌ها از O(n×W)O(n×W) است. مقدار حافظه‌ی مورد نیاز نیز O(W)O(W) است.

ساخت سايت

پیاده سازی الگوریتم ۸ وزیر با استفاده از الگوریتم ژنتیک
طراحی وب سايت
راهکاری که برای حل یک مسئله با الگوریتم ژنتیک استفاده می شود تکامل می یابد. الگوریتم ژنتیک مثل هر الگوریتم بهینه سازی دیگر با تعریف متغیرهای بهینه سازی آغاز می شود و مانند الگوریتم های بهنیه سازی دیگر نیز خاتمه می یابد یعنی با تست همگرایی.

یک الگوریتم GA دارای پارامترهای زیر است:

: Fitnessتابعی برای ارزیابی یک فرضیه که مقداری عددی به هر فرضیه نسبت میدهد
: Fitness_threshold مقدار آستانه که شرط پایان را معین میکند
: population تعداد فرضیه هائی که باید در جمعیت در نظر گرفته شوند
: crossover rate در صدی از جمعیت که در هر مرحله توسط الگوریتم crossover جایگزین میشوند
:mutation rate نرخ mutation
الگوریتم GA به صورت زیر کار می کند:

: Initializeجمعیت را با تعداد population فرضیه بطور تصادفی مقدار دهی اولیه کنید.
: Evaluateبرای هر فرضیه h در population مقدار تابع Fitness(h) را محاسبه نمائید.
تا زمانیکه[maxh Fitness(h)] < Fitness_threshold یک جمعیت جدید ایجاد کنید.
فرضیه ای که دارای بیشترین مقدار Fitness است را برگردانید.
روش های مختلف crossover:

Single-point crossover

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

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

اپراتورهای ژنتیکی Mutation :

اپراتور mutation برای بوجود آوردن فرزند فقط از یک والد استفاده میکند. اینکار با انجام تغییرات کوچکی در رشته اولیه بوقوع میپیوندد.
با استفاده از یک توزیع یکنواخت یک بیت بصورت تصادفی اتنخاب و مقدار آن تغییر پیدا میکند.
معمولا mutation بعد از انجام crossover اعمال میشود.

تابع fitness معیاری برای رتبه بندی فرضیه هاست که کمک میکند تا فرضیه های برتر برای نسل بعدی جمعیت انتخاب شوند. نحوه انتخاب این تابع بسته به کاربر مورد نظر دارد

در روش معرفی شده در الگوریتم ساده GA احتمال انتخاب یک فرضیه برای استفاده در جمعیت بعدی بستگی به نسبت fitness آن به fitness بقیه اعضا دارد. این روش Roulette Wheel selectionنامیده میشود.

روش جستجوی GA با روشهای دیگر مثل شبکه های عصبی تفاوت دارد:

در شبکه عصبی روش Gradient descent بصورت هموار از فرضیه ای به فرضیه مشابه دیگری حرکت میکند در حالیکه GA ممکن است بصورت ناگهانی فرضیه والد را با فرزندی جایگزین نماید که تفاوت اساسی با والد آن داشته باشد.از اینرو احتمال گیر افتادن GA در مینیمم محلی کاهش می یابد. با این وجود GA با مشکل دیگری روبروست که crowding نامیده میشود crowding پدیده ای است که در آن عضوی که سازگاری بسیاربیشتری از بقیه افراد جمعیت دارد بطور مرتب تولید نسل کرده و با تولید اعضای مشابه درصد عمده ای از جمعیت را اشغال میکند. راه حل رفع مشکل Crowdingاستفاده از ranking برای انتخاب نمونه ها است، با اختصاص رتبه به فرضیه ای که بسیار بهتر از بقیه عمل میکند.

مسئله ۸ وزیر:

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

تعریف توابع و متغیرها
تولید جمعیت اولیه
دیکد کردن کروموزوم ها
پیدا کردن هزینه برای هر کروموزوم
انتخاب جفت ها
جفت گیری
میوتیشن
بررسی همگرایی
خاتمه یا بازگشت به مرحله دیکد کردن کروموزوم ها
ژن عددی از ۰ تا n-1 است در ۸ وزیر n برابر با ۸ است بنابراین ژن عددی از ۰ تا ۷ می شود و کروموزوم آرایه ای از ژن هاست. که می تواند پاسخ مسئله باشد.

جمعیت هر نسل می تواند تعداد کروموزوم ها را تعیین کند.

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

برای پیدا کردن هزینه مربوط به هر کروموزوم یک تابع هزینه تعریف می شود. نتیجه تابع هزینه یک cost value است که در نهایت میانگین cost valueهای هر نسل به نتیجه مطلوب نزدیک می شود.

کروموزوم هایی که فیتنس بالاتری (هزینه پایین تر) دارند برای تولید نسل بعدی استفاده می شوند.

در فرایند cross over فرزندان توسط والدین تولید می شوند که ترکیب آنها شامل ترکیب ژن های آنهاست. اگر نسل جدید حاوی کروموزومی باشد که نزدیک یا برابر با نتایج مطلوب باشد آنگاه مسئله حل شده است. در غیر اینصورت فرایند قبلی در نسل جدید هم پیاده سازی می شود مانند فرایندی که برای والدین آنها اتفاق افتاد. تا زمانی که به راه حل مناسب برسیم این روال ادامه دارد.

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

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

فانکش استفاده از میوتیشن برای نسل فعلی:

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

همان طور که گفته شد ژن عددی از ۰ تا ۷ است که به معنی شماره سطری است که وزیر در آن قرار گرفته است. موقعیت ژن در یک کروموزوم به معنی شماره ستون قرار گیری وزیر است. مشخص کردن مکان قرار گیری هر وزیر را باید حتما در هر سطر و ستون مشخص کرد.

کروموزوم نیز مجموعه ای از ۸ ژن است. و این طور فرض می شود که هیچ ژنی در یک کروموزوم دوبار تکرار نشود. برای مثال اگر کروموزوم ما ۰|۱|۴|۲|۳|۶|۷|۵ باشد یعنی ۸ وزیر در خانه های زیر از ماتریس قرار گرفته اند.

(۰,۰), (۱,۱), (۲,۴), (۳,۲), (۴,۳), (۵,۶), (۶,۷), (۷,۵)

در اینجا میوتیشن با swap کردن ژنی که باید mutate شود با یک ژن تصادفی (به جز ژنی که می خواهیم میوتیشن را روی آن انجام دهیم) از همان کروموزوم انجام می شود.

در crossover ژن ها از کروموزوم های دو والدین با احتمال ۰٫۵ گرفته می شود. یک ژن از یکی از والدین گرفت می شود و به کروموزوم فرزند اضافه می شود. ژنی که تولید می شود در پرنت دیگر پاک می شود. این مرحله انقدر ادامه می یابد تا کروموزوم های پدر و مادر هر دو، خالی شود و فرزند آنها همه ژن ها را داشته باشد.

تابع فیتنس: زمانی که دو وزیر طوری قرار بگیرند که یکدیگر را تهدید کنند یعنی در یک سطر، ستون یا قطر مشابه باشند. از آنجایی که کروموزوم ها ژن های تکراری ندارند بنابراین این اطمینان وجود دارد که هیچ دو وزیری در یک ستون قرار نمی گیرند. پس تنها باید برخوردهای قطری را بررسی و محاسبه کرد. بنابراین ماکزیمم تعداد برخوردها می تواند ۲۸ باشد. تابع فیتنس مقدارش هر چه بیشتر باشد بهتر است بنابراین اگر یک راه حل ۰ برخورد (تهدید دو وزیر) داشته باشد فیتنس آن ۲۸ است که با تفریق مقدار برخوردهایی که در حالت فعلی رخ می دهند از ۲۸ به دست می آید.

در کد c# مورد استفاده :

class GeneticAlgo: کلاسی است که مسئولیت همه عملیات الگوریتم ژنتیک را بر عهده دارد.

class FitnessComparator: یک کلاس مقایسه کننده است که کروموزوم ها را با fitness value مرتب می کند تا جمعیت نهایی را در جدول نشان دهد. بیشترین فیتنس در بالای جدول قرار می گیرد و کمترین آنها در پایین جدول.

struct Chromosome: ساختاری است که کروموزومی که حاوی ژنهااست، فیتنس و مجموع میانگین فیتنس ها را نشان می دهد.

class MainFrame: این کلاس موظف به کنترل اینترفیس کاربر و ایجاد جمعیت اولیه به منظور انتقال آن به الگوریتم ژنتیک است.

class Board: این کلاس گرافیک و عملیات صفحه شطرنج را بر عهده دارد.

متغیر private const int MAX_FIT = ۲۸ بیشترین مقدار فیتنس را دارد.

توابع:

private List<chromosome> GetInitialPopulation(int population)

{

List<chromosome> initPop = new List<chromosome>();

GeneticAlgo RandomGen = new GeneticAlgo();

for (int i = 0; i < population; i++)

{

List<int> genes = new List<int>(new int[] {0, 1, 2, 3, 4, 5, 6, 7});

Chromosome chromosome = new Chromosome();

chromosome.genes = new int[8];

for (int j = 0; j < 8; j++)

{

int geneIndex = (int)(RandomGen.GetRandomVal

(۰,genes.Count-1)+0.5);//randomly select a gene

chromosome.genes[j] = genes[geneIndex];

genes.RemoveAt(geneIndex);//remove selected gene

}

initPop.Add(chromosome);

}

return initPop;

}

سلام من نیاز به حل مسعله tsp با الگوریتم چرخه اب دارم اگه کمکم کنید ممنون میشم