یک مسئله عملی :

فرض کنید می خواهیم یک کلمه دیجیتالی ۳۲ بیتی داشته باشیم که تمام بیت های آن ۱ باشند. در این حالت ساختار ارگانیک ما همان کلمه دیجیتالی ۳۲ بیتی است. که برای تولید این ساختار ارگانیک روند الگوریتم ژنتیک که در بالا گفته شد را اعمال می کنیم.

۱-    ابتدا ۱۰۰ کلمه ۳۲ بیتی تصادفی تولید می کنیم (جمعیت اولیه)

۲-    تکرار فرآیند زیر :

۲-۱- تعداد ۱ ها را در کلمات شمارش کنید.

۲-۲- اگر در یکی از کلمات تمام بیت ها ۱ بود، از روند خارج شوید

۲-۳- ۱۰کلمه که بیشترین تعداد ۱ را دارند، جدا کنید و بقیه را حذف کنید.

۲-۴- از هر کلمه بخش (۲-۳) ، ۹ کلمه دیگر، بصورت زیر تولید کنید.

    ۲-۴-۱- یک کلمه از این ۹ کلمه را انتخاب کنید

    ۲-۴-۲- چند بیت را بصورت تصادفی انتخاب کنید و تغییر دهید.

۲-۵- حال دوباره تعداد ۱ ها را شمارش کنید و تا رسیدن به جواب این حلقه را تکرار نمائید.

توجه داشته باشید که با توجه به الگوریتم تولید نسل بعدی ضمانتی برای همگرائی و به جواب رسیدن این روش وجود ندارد.

 

حال این مسئله را علمی تر تکرار می کنیم:

۱-    ابتدا ۱۰۰ کلمه ۳۲ بیتی تصادفی تولید می کنیم (جمعیت اولیه)

۲-    تکرار فرآیند زیر :

۲-۱- تعداد ۱ ها را در کلمات شمارش کنید.

۲-۲- اگر در یکی از کلمات تمام بیت ها ۱ بود، از روند خارج شوید

۲-۳- ۱۰کلمه که بیشترین تعداد ۱ را دارند، جدا کنید و بقیه را حذف کنید.

۲-۴- از هر کلمه بخش (۲-۳) ، ۹ کلمه دیگر، بصورت زیر تولید کنید.

    ۲-۴-۱- یک کلمه از این ۹ کلمه را انتخاب کنید:

    ۲-۴-۲- نیمه اول این کلمه را با نیمه دوم بقیه کلمه ها ترکیب کنید و ۹ کلمه                  جدید تولید کنید.

۲-۵- حال دوباره تعداد ۱ ها را شمارش کنید و تا رسیدن به جواب این حلقه را تکرار نمائید.

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

۱-    نیمی از ژن ها(بیت ها) از یک کلمه و نیمی از کلمه دیگر:

 

۰۱۱۰ ۱۰۰۱ ۰۱۰۰ ۱۱۱۰ ۱۰۱۰ ۱۱۰۱ ۱۰۱۱ ۰۱۰۱           First word
۱۱۰۱ ۰۱۰۰ ۰۱۰۱ ۱۰۱۰ ۱۰۱۱ ۰۱۰۰ ۱۰۱۰ ۰۱۰۱           Second word
۰۱۱۰ ۱۰۰۱ ۰۱۰۰ ۱۱۱۰ ۱۰۱۱ ۰۱۰۰ ۱۰۱۰ ۰۱۰۱         NEW WORD

 

۲-     انتخاب ژن ها ( بیت ها ) بصورت تصادفی از دو کلمه و ترکیب آنها:

 

۰۱۱۰ ۱۰۰۱ ۰۱۰۰ ۱۱۱۰ ۱۰۱۰ ۱۱۰۱ ۱۰۱۱ ۰۱۰۱           First word
۱۱۰۱ ۰۱۰۰ ۰۱۰۱ ۱۰۱۰ ۱۰۱۱ ۰۱۰۰ ۱۰۱۰ ۰۱۰۱           Second word
۰۱۰۰ ۰۱۰۱ ۰۱۰۰ ۱۰۱۰ ۱۰۱۰ ۱۱۰۰ ۱۰۱۱ ۰۱۰۱           NEW WORD

 

۳-    ممکن است بجای انتخاب ژن ها در قسمت بالا، گروه های ژنی را از دو کلمه بصورت تصادفی انتخاب کنیم و کلمه جدید را بسازیم:

 

۰۱۱۰ ۱۰۰۱ ۰۱۰۰ ۱۱۱۰ ۱۰۱۰ ۱۱۰۱ ۱۰۱۱ ۰۱۰۱     First word
۱۱۰۱ ۰۱۰۰ ۰۱۰۱ ۱۰۱۰ ۱۰۱۱ ۰۱۰۰ ۱۰۱۰ ۰۱۰۱          Second word        
۱۱۰۱ ۱۰۰۱ ۰۱۰۱ ۱۰۱۰ ۱۰۱۰ ۱۱۰۱ ۱۰۱۰ ۰۱۰۱          NEW WORD

 

حال یک مثال واقعی تر را برسی می کنیم:

فرض کنید شما تعداد زیادی از زوج های مرتب دارید، مثلا (۱٫۰, ۴٫۱), (۳٫۱, ۹٫۵), (-۵٫۲, ۸٫۶), … و شما می خواهید یک چند جمله ای ( تا درجه ۵ ) را به این زوج ها نسبت دهید.
به عبارت دیگر شما می خواهید رابطه ای مانند
y = ax5 + bx4 + cx3 + dx2 +ex + f   بیابید که تطبیق خوبی با اطلاعات واقعی داشته باشد. برای این کار راه های معمولی وجود دارد مانند LSM(Least Square Method). در این روش مجموع ( actual(y)predicted (y) )2  برای تمام داده ها انجام می شود و کمترین مجموع به عنوان بهترین رابطه برای y انتخاب
می شود. حال اگر بخواهیم بجای استفاده از روش های معمول تطبیق منحنی از الگوریتم ژنتیک برای حل این مسئله استفاده کنیم.

ابتدا به بیان مسئله می پردازیم:

رابطه ما y = ax5 + bx4 + cx3 + dx2 +ex + f   است که ما باید  e ,d ,c ,b ,aوf  را بیابیم، پس این مجهولات همان ژن های ما خواهند بود. کروموزوم ها یا همان جواب های یک مسئله نیز یک ترکیب خاص از این ژن ها است، یعنی آرایه [ a b c d e f ]  .

روش ارزیابی شما برای هر آرایه بدین صورت خواهد بود:

 

برای هر زوج مرتب واقعی محاسبات زیر را انجام دهید.

ý = ax5 + bx4 + cx3 + dx2 +ex + f

٭ ý نشان دهنده مقدار تخمین زده شده برای y می باشد.

 

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

برای مثال اگر آرایه انتخاب شده به صورت [۰, ۰, ۰, ۲, ۳, ۵]  و داده های ما (۱, ۱۲)  و   (۲, ۲۲)  باشد، خواهیم داشت:

 

ý = ۰x5 + ۰x4 + ۰x3 + ۲x2 +۳x + 5 is 2 + 3 + 5 = 10 when x is 1

ý = ۰x5 + ۰x4 + ۰x3 + ۲x2 +۳x + 5 is 8 + 6 + 5 = 19 when x is 2

(۱۲ – ۱۰)۲ + (۲۲ – ۱۹)۲ = ۲۲ + ۳۲ = ۱۳

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

حال الگوریتم را بصورت زیر تعریف می کنیم:

۱-    ابتدا ۱۰۰ آرایه ۶تائی تولید می کنیم. (جمعیت اولیه)

۲-    ۵۰۰ مرتبه حلقه زیر را تکرار می کنیم:

۲-۱- برای تمام ۱۰۰ آرایه اولیه معیار مجموع را با تمام نقاط محاسبه می کنیم.

۲-۲- ۱۰ آرایه بهتر را براساس کوچکی معیار مجموع انتخاب می کنیم و سایر
آرایه ها را حذف می کنیم.

۲-۳- از هر آرایه باقی مانده، ۹ آرایه جدید به روش زیر تولید می کنیم:

۲-۳-۱- انتخاب بعضی ژن ها (متغیرها) از آرایه بصورت تصادفی.

۲-۳-۲- انتخاب عددی اعشاری بین ۰~۲ بصورت تصادفی.

۲-۳-۳- ضرب کردن المان های تصادفی از آرایه در اعداد اعشاری و تولید آرایه جدید.

۲-۴- محاسبه معیار مجموع برای تمام آرایه های جدید.

بعد از ۵۰۰ مرتبه بهترین آرایه ها را برای بهترین جواب خواهیم داشت.

همانند مثال کلمه دیجیتالی، در اینجا نیز می توانیم از روش های مختلفی برای تولید
آرایه های جدید استفاده کنیم:

یک روش همانند مثال قبلی ترکیب نیمه ای از یکی از یک آرایه با نیمه دیگر بقیه آرایه ها است.

 

    [ a, b, c, d, e, f ]

                                              [ a, b, c, d’, e’, f’ ]

 [ a’, b’, c’, d’, e’, f’ ]

یا انتخاب ژن ها بصورت تصادفی یا غیر تصادفی از دو کروموزوم و ترکیب آنها برای تولید کروموزوم های جدید.

 

    [ a, b, c, d, e, f ]

                                              [ a, b’, c, d’, e, f’ ]

 [ a’, b’, c’, d’, e’, f’ ]

 

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

    [ a, b, c, d, e, f ]

                                  [(a+a)/2, (b+b)/2, (c+c)/2, (d+d)/2, (e+e)/2, (f+f)/2]

 [ a’, b’, c’, d’, e’, f’ ]

 

با توجه به دو مثال بالا درمی یابیم که نحوه تولید نسل بعدی از نسل فعلی (Reproduction) از اهمیت زیادی برخوردار است، لذا در این بخش به این مسئله و جزئیات آن می پردازیم.

 

بهینه سازی مسئله

 

 

 

۸ یا ۱۶

تعداد جمعیت

population size

۰٫۲ ۰٫۴

نرخ جفت گیری

mutation rate

۰٫۵

نسبت جمعیتی بدون جفت گیری

fraction of population kept

۴

تعداد بیت هر ژن

number of bits

۱۲

تعداد بیت هر کروموزوم

total number of bits in a chormosome

 

 

[cost]=[mach]-1

 

 

weights chromosomes based upon position in list

 

 

crossover point

۴-۸

 

number of matings