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

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

چکیده

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

فلسفه اصلی

الگوریتم ژنتیک به وسیله گلدبرگ که از تئوری تکامل داروین الهام گرفته شده است توسعه یافته است. باقی ماندن یک کروموزوم بستگی به قانون "افراد شایسته تر زنده بمانند" دارد. داروین همچنین اظهار داشت که بقای یک کروموزوم می تواند از طریق تولید مثل، تقاطع و جهش انجام شود.

مثال عددی

فرض کنید تساوی a+2b+3c+4d=30 وجود داشته باشد با استفاده از الگوریتم ژنتیک مقادیر a,b,c,d را به گونه ای یافت شود که تساوی برقرار باشد. در ابتدا باید تابع هدف فرمول بندی شود. که در این مثال هدف مینیم کردن تابع f(x)=a+2b+3c+4d-30 می باشد. چون چهار متغیر در معادله وجود دارد می توان کروموزوم را به شکل 1 ایجاد کرد.  

شکل 1: تشکیل کروموزوم برای معادله ریاضی f(x) با چهار متغیر

مرحله 1: مقداردهی اولیه:

برای مثال تعداد کروموزوم ها برای جمعیت اولیه 6 تعریف می شود. سپس مقادیر ژن های a,b,c,d به طور تصادفی برای 6 کروموزوم تولید می شود.

Chromosome[1] = [a;b;c;d] = [12;05;23;08]

Chromosome[2] = [a;b;c;d] = [02;21;18;03]

Chromosome[3] = [a;b;c;d] = [10;04;13;14]

Chromosome[4] = [a;b;c;d] = [20;01;10;06]

Chromosome[5] = [a;b;c;d] = [01;04;13;19]

Chromosome[6] = [a;b;c;d] = [20;05;17;01]

مرحله دوم: ارزیابی

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

abcd

F_obj[1] = Abs(( 12 + 2*05 + 3*23 + 4*08 ) - 30)

= Abs((12 + 10 + 69 + 32 ) - 30)

= Abs(123 - 30)

= 93

F_obj[2] = Abs((02 + 2*21 + 3*18 + 4*03) - 30)

= Abs((02 + 42 + 54 + 12) - 30)

= Abs(110 - 30)

= 80

F_obj[3] = Abs((10 + 2*04 + 3*13 + 4*14) - 30)

= Abs((10 + 08 + 39 + 56) - 30)

= Abs(113 - 30)

= 83

F_obj[4] = Abs((20 + 2*01 + 3*10 + 4*06) - 30)

= Abs((20 + 02 + 30 + 24) - 30)

= Abs(76 - 30)

= 46

F_obj[5] = Abs((01 + 2*04 + 3*13 + 4*19) - 30)

= Abs((01 + 08 + 39 + 76) - 30)

= Abs(124 - 30)

= 94

F_obj[6] = Abs((20 + 2*05 + 3*17 + 4*01) - 30)

= Abs((20 + 10 + 51 + 04) - 30)

= Abs(85 - 30)

= 55

مرحله سوم: انتخاب

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

Fitness[1] = 1 / (1+F_obj[1])

= 1 / 94

= 0.0106

Fitness[2] = 1 / (1+F_obj[2])

= 1 / 81

= 0.0123

Fitness[3] = 1 / (1+F_obj[3])

= 1 / 84

= 0.0119

Fitness[4] = 1 / (1+F_obj[4])

= 1 / 47

= 0.0213

Fitness[5] = 1 / (1+F_obj[5])

= 1 / 95

= 0.0105

Fitness[6] = 1 / (1+F_obj[6])

= 1 / 56

= 0.0179

Total = 0.0106 + 0.0123 + 0.0119 + 0.0213 + 0.0105 + 0.0179

= 0.0845

فرمول احتمال هر کروموزوم به صورت P[i] = Fitness[i] / Total می باشد.

P[1] = 0.0106 / 0.0845

= 0.1254

P[2] = 0.0123 / 0.0845

= 0.1456

P[3] = 0.0119 / 0.0845

= 0.1408

P[4] = 0.0213 / 0.0845

= 0.2521

P[5] = 0.0105 / 0.0845

= 0.1243

P[6] = 0.0179 / 0.0845

= 0.2118

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

C[1] = 0.1254

C[2] = 0.1254 + 0.1456

= 0.2710

C[3] = 0.1254 + 0.1456 + 0.1408

= 0.4118

C[4] = 0.1254 + 0.1456 + 0.1408 + 0.2521

= 0.6639

C[5] = 0.1254 + 0.1456 + 0.1408 + 0.2521 + 0.1243

= 0.7882

C[6] = 0.1254 + 0.1456 + 0.1408 + 0.2521 + 0.1243 + 0.2118

= 1.0

پس از احتمال تجمعی فرآیند تعداد تصادفی R در بازه 0 تا 1 به صورت زیر بدست می آید.

R[1] = 0.201

R[2] = 0.284

R[3] = 0.099

R[4] = 0.822

R[5] = 0.398

R[6] = 0.501

اگر مقدار تصادفی R[1] بزرگتر از C[1] و کوچکتر از C[2] باشد کروموزوم 2 به عنوان یک کروموزوم در جمعیت جدید برای نسل بعدی انتخاب می شود.

NewChromosome[1] = Chromosome[2]

NewChromosome[2] = Chromosome[3]

NewChromosome[3] = Chromosome[1]

NewChromosome[4] = Chromosome[6]

NewChromosome[5] = Chromosome[3]

NewChromosome[6] = Chromosome[4]

کروموزوم ها در جمعیت جدید به شکل زیر می باشد:

Chromosome[1] = [02;21;18;03]

Chromosome[2] = [10;04;13;14]

Chromosome[3] = [12;05;23;08]

Chromosome[4] = [20;05;17;01]

Chromosome[5] = [10;04;13;14]

Chromosome[6] = [20;01;10;06]

مرحله چهارم: تقاطع

در این مثال، از تقاطع تک نقطه ای استفاده شده است. نقطه تقاطع به صورت تصادفی انتخاب می شود. پدر بعدی برای جفت شدن برای تولید فرزند به طور تصادفی انتخاب می شود و تعداد کروموزوم های جفت شده با استفاده از پارامتر crossover_rate (ρc) کنترل می شود.شبه کد فرآیند تقاطع به شکل ذیل می باشد:

begin

k← 0;

while(k<population) do

R[k] = random(0-1);

if(R[k]< ρc) then

select Chromosome[k] as parent;

end;

k = k + 1;

end;

end

کروموزوم K به عنوان پدر انتخاب می شود اگر R[k]<ρc باشد. با فرض اینکه نرخ تقاطع 25% باشد آنگاه تعداد k کروموزوم برای تقاطع انتخاب می شود اگر مقدار تصادفی تولید شده برای k کروموزوم کمتر از 0.25 باشد. این فرآیند به صورت زیر می باشد. در ابتدا مقدار تصادفی R به تعداد جمعیت تولید می شود .

R[1] = 0.191

R[2] = 0.259

R[3] = 0.760

R[4] = 0.006

R[5] = 0.159

R[6] = 0.340

برای مقدار تصادفی R بالا، کروموزوم های Chromosome[1], Chromosome[4] و Chromosome[5] برای تقاطع انتخاب می شوند.

Chromosome[1] >< Chromosome[4]

Chromosome[4] >< Chromosome[5]

Chromosome[5] >< Chromosome[1]

بعد از انتخاب کروموزوم ها، فرآیند بعدی مشخص کردن موقعیت نقطه تقاطع می باشد. این کار با تولید مقدار تصادفی بین 1 تا طول کروموزوم منهای یک انجام می شود. به عبارت دیگر مقدار تصادفی تولید شده برای این مثال باید بین 1 تا 3 باشد. بعد از بدست آمدن نقطه تقاطع، کروموزوم های والد از روی نقطه تقاطع برش می خورند و ژن ها با یکدیگر جابه جا می شوند. برای مثال سه مقدار تصادفی بدست آمده است بنابراین:

C[1] = 1

C[2] = 1

C[3] = 2

خواهد بود. بنابراین برای تقاطع های یک ، دو و سه ، به ترتیب شماره ژن 1 ،1و 2برای برش انتخاب می شوند.

Chromosome[1] = Chromosome[1] >< Chromosome[4]

= [02;21;18;03] >< [20;05;17;01]

= [02;05;17;01]

Chromosome[4] = Chromosome[4] >< Chromosome[5]

= [20;05;17;01] >< [10;04;13;14]

= [20;04;13;14]

Chromosome[5] = Chromosome[5] >< Chromosome[1]

= [10;04;13;14] >< [02;21;18;03]

= [10;04;18;03]

بنابراین جمعیت کروموزوم ها پس از یکبار تقاطع به صورت زیر می باشد:

Chromosome[1] = [02;05;17;01]

Chromosome[2] = [10;04;13;14]

Chromosome[3] = [12;05;23;08]

Chromosome[4] = [20;04;13;14]

Chromosome[5] = [10;04;18;03]

Chromosome[6] = [20;01;10;06]

مرحله 5: جهش:

تعداد کروموزوم هایی که در یک جمعیت جهش پیدا می کنند با پارامتر  mutation_rate مشخص می شوند. فرآیند جهش با جابه جایی ژن در موقعیت تصادفی با یک مقدار جدید انجام می شود. این فرآیند در ابتدا با طول کل ژن ها در جمعیت محاسبه شود. در این مثال:

Total_gen = number_of_gen_in_Chromosome * number of population

= 4 * 6

= 24

فرآیند چهش به وسیله تولید عدد صحیح تصادفی بین 1 تا تعداد ژن ها (1 تا 24) انجام می شود. اگر مقدار تولید شده تصادفی کمتر از مقدار نرخ جهش (mutation_rate(ρm) باشد این موقعیت ژن نگه داشته می شود. با فرض اینکه ρm=10% باشد انتظار می رود که 10 % از ژن های کل جمعیت جهش یابند.

number of mutations = 0.1 * 24

= 2.4

≈ 2

فرض کنید مقدار تصادفی تولید شده برابر 12 و 18 باشد. بنابراین کروموزوم 3 ژن شماره چهارش و کروموزوم 5 شماره دو آن نیاز به جهش می باشد. مقدار ژن های انتخاب شده برای جهش با مقدار تصادفی بین 0 تا 30 جایگزین می شوند. فرض کنید دو عدد تصادفی بدست آمده بین 0 تا 30 به ترتیب 2 و 5 باشد بنابراین کروموزوم ها به صورت زیر تغییر پیدا خواهند کرد :

Chromosome[1] = [02;05;17;01]

Chromosome[2] = [10;04;13;14]

Chromosome[3] = [12;05;23;02]

Chromosome[4] = [20;04;13;14]

Chromosome[5] = [10;05;18;03]

Chromosome[6] = [20;01;10;06]

فرآیند جهش نشان دهنده به پایان رسیدن یک تکرار یا یک نسل ار الگوریتم ژنتیک می باشد. حال می توان تابع هدف را پس از یک نسل ارزیابی نمود:

Chromosome[1] = [02;05;17;01]

F_obj[1] = Abs(( 02 + 2*05 + 3*17 + 4*01 ) - 30)

= Abs((2 + 10 + 51 + 4 ) - 30)

= Abs(67 - 30)

= 37

Chromosome[2] = [10;04;13;14]

F_obj[2] = Abs(( 10 + 2*04 + 3*13 + 4*14 ) - 30)

= Abs((10 + 8 + 33 + 56 ) - 30)

= Abs(107 - 30)

= 77

Chromosome[3] = [12;05;23;02]

F_obj[3] = Abs(( 12 + 2*05 + 3*23 + 4*02 ) - 30)

= Abs((12 + 10 + 69 + 8 ) - 30)

= Abs(87 - 30)

= 47

Chromosome[4] = [20;04;13;14]

F_obj[4] = Abs(( 20 + 2*04 + 3*13 + 4*14 ) - 30)

= Abs((20 + 8 + 39 + 56 ) - 30)

= Abs(123 - 30)

= 93

Chromosome[5] = [10;05;18;03]

F_obj[5] = Abs(( 10 + 2*05 + 3*18 + 4*03 ) - 30)

= Abs((10 + 10 + 54 + 12 ) - 30)

= Abs(86 - 30)

= 56

Chromosome[6] = [20;01;10;06]

F_obj[6] = Abs(( 20 + 2*01 + 3*10 + 4*06 ) - 30)

= Abs((20 + 2 + 30 + 24 ) - 30)

= Abs(76 - 30)

= 46

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

Chromosome[1] = [02;05;17;01]

Chromosome[2] = [10;04;13;14]

Chromosome[3] = [12;05;23;02]

Chromosome[4] = [20;04;13;14]

Chromosome[5] = [10;05;18;03]

Chromosome[6] = [20;01;10;06]

که برای تکرارهای بعدی عملیات ارزیابی، انتخاب، تقاطع و جهش روی این کروموزوم ها انجام می شود. تعداد تکرار وابسته به مقدار تعیین شده قبلی می باشد. برای مثال مسئله بعد از 50 بار تکرار و تولید نسل بهترین کروموزوم بدست آمده است:

Chromosome = [07; 05; 03; 01]

بنابراین: a = 7, b = 5, c = 3, d = 1

 a + 2b + 3c + 4d = 30

اگر این مقادیر در معادله قرار گیرد داریم:

7 + (2 * 5) + (3 * 3) + (4 * 1) = 30

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

[1]: http://cdn.persiangig.com/download/2wctetN12Z/1_GA.pdf/dl.