اصول و مبانی الگوریتم ژنتیک:

  • Coding or Representation:

بیان رشته های راه حل با تمام پارامترها

  • Fitness Function:

برای انتخاب والدین و درنهایت انتخاب جواب نهائی بکار گرفته می شود

  • Reproduction:

چگونگی تولید نسل بعدی است، که به دو روش زیر انجام می شود:

۳-۱- Crossover

۳-۲- Mutation

۴- Convergence

بیان کننده میزان همگرائی و زمان رسیدن به جواب نهائی است.

 

CODING:

برای بیان مسئله به زبان ریاضی باید تمام ویژگی های مسئله را بصورت پارامترهای جداگانه بیابیم. در الگوریتم ژنتیک این پارامترها هریک یک ژن می باشند که باید این ژن ها را کنار یکدیگر قرار داد تا کروموزوم ها تشکیل شوند. کروموزوم ها در واقع همان جواب های پیش بینی شده برای مسئله هستند که باید میزان نزدیکی آنها بررسی شده و از بهترین آنها کروموزوم ها یا همان نسل بعدی تولید شود. برای بیان پارامترها (ژن ها) از انواع نمادها می توان استفاده کرد، مانند حروف الفبا، اعداد و … . اما استفاده از الفبای باینری (۰,۱) برای بیان پارامترها کاربرد بیشتری دارد. در بیان یک مسئله، تعداد پارامترها برای مشخص کردن جواب از اهمیت زیادی برخوردار است و می تواند دقت و زمان رسیدن به جواب را تا حد زیادی تحت تاثیر قرار دهد.

-۴-۳-۱-        جمعیت‌ اولیه‌

            الگوریتم‌ ژنتیک‌ در مرحله اول به‌ کمک‌ یک‌ جمعیت‌ اولیه‌، یک‌ جست‌ و جوی‌ فراگیر را آغاز می‌کند. اندازه‌ی‌ جمعیت‌ به‌ ویژگی‌های پرسش‌ بهینه‌یابی‌ بستگی‌ دارد. دقت‌ پاسخ‌ به‌ طول‌ کروموزوم‌ها وابسته‌ است‌، بنابراین‌ طول‌ کروموزوم‌ها را باید به‌ دقت‌ برگزید. تعداد کروموزوم‌های‌ جمعیت‌ را نیز باید به‌ دقت‌ برگزید، زیرا جمعیت‌ بزرگ‌ زمان‌ رسیدن‌ به‌پاسخ‌ را می‌افزاید.

برای‌ تولید جمعیت‌ اولیه‌، از اعداد‌ تصادفی‌ استفاده‌ می‌شود. اگر rand عددی‌ در بازه ‌[۱  ۰] باشد، گرد شده‌ی‌ آن‌ یا ۰ است‌ یا ۱، پس‌ هر ژن‌ را می‌توان‌ این‌ گونه‌ ایجاد کرد.

(۳-۴)

اگر با تعداد لازم‌ از این‌ ژن‌ها یک‌ جمعیت‌ ایجاد شود، جمعیت‌ آغازین‌ به‌ دست‌ می‌آید.

اگر هدف‌ این‌ باشد که‌ مقدار متغیر  با  رقم‌ اعشار پیدا شود، باید تعداد ژن‌های‌ مربوط‌به‌ آن‌ را طوری‌ پیدا کنیم‌ که‌ در رابطه‌ی‌ زیر صدق‌ کند:

(۳-۵)

 

که‌ در آن‌،  تعداد ژن‌های‌ مربوط‌ به‌ متغیر  است‌. و در نهایت‌ تعداد نهایی‌ ژن‌های‌ مربوط‌ به‌ هرکروموزم‌ به‌ صورت‌ زیر بدست‌ می‌آید.

(۳-۶)

 

 

۳-۴-۳-۲-     نگاشت‌ از فضای‌ کروموزوم‌ها به‌ فضای‌ پاسخ‌

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

کروموزوم‌ها اندازه‌های‌ به‌ رمز درآمده‌ی‌ متغیرهای‌ مسئله‌ بهینه‌یابی‌ هستند. همان‌‌گونه‌ که‌ دیده‌ شد، هر کروموزوم‌ از n عدد‌ کروموزوم‌ تک‌‌ژنی‌ ساخته‌ شده‌ است‌. تکه‌ کروموزوم‌ شماره‌ی‌  اندازه‌ی‌ به‌ رمز درآمده‌ی‌ متغیر  است‌. هر کدام‌ از این‌ تکه کروموزوم‌ها عددی‌ در مبنای‌ دو هستند که‌ با تبدیل‌شان‌ از مبنای‌ دو به‌ مبنای‌ ده‌ به‌ دست‌ می‏آید که‌ در بازه‌ی‌ زیر قرار دارد.

(۳-۷)

 

زیرا کوچکترین‌ و بزرگ‌ترین‌ عددهایی‌ که‌ از تبدیل‌ یک‌ عدد دو دویی‌ به‌ یک‌ عدد دهدهی‌ ایجاد می‌شوند، هنگامی‌ به‌ دست‌ می‌آیند که‌ اجزای‌ عدد دودویی‌ به‌ ترتیب‌، همگی‌ ۰ و همگی‌ ۱باشند.

کوچکترین‌ عدد

بزرگترین‌ عدد

اکنون‌ از تبدیل‌ این‌ n عدد‌ کروموزوم‌ از مبنای‌ دو به‌ مبنای‌ ده‌، N عدد  به‌ دست‌ آمده‌ است،‌ که‌ در هر بازه‌  قرار دارند. این‌ n عدد با یک نگاشت‌ به‌ بازه‌های‌ زیر نگاشته‌ می‌شوند.

 

 

برای‌ آنکه‌ توزیع‌ عددها یکنواخت‌ باشد. این‌ نگاشت‌، خطی‌ در نظر گرفته‌ می‌شود]۱۴[.

(۳-۸)

 

بدین‌ ترتیب‌، با تبدیل‌ هر کدام‌ از کروموزوم‌ها از مبنای‌ دو به‌ مبنای‌ ده‌ و نگاشت‌ آنها، مقداری‌ برای‌ هر کدام‌ از متغیرهای‌ مسئله‌ بهینه‌یابی‌ به‌ دست‌ می‌آید. از آنجا که‌ جمعیت‌ آغازین‌ M کروموزوم‌ داشت‌، M دسته‌ مقدار برای‌ متغیرهای‌ مسئله‌ بهینه‌یابی‌ به‌ دست‌ می‌آید.

 

۳-۴-۳-۳-     برازندگی[۱]‌ کروموزوم‌ها

            همانگونه‌ که‌ دیده‌ شد M دسته‌ مقدار برای‌ متغیرهای‌ مسئله‌ بهینه‌یابی‌ به‌ دست‌ آمد. این‌مقادیر، که‌ هیچ‌ دانشی‌ از برازندگی‌ و شایستگی‌ خود به‌ دست‌ نمی‌دهند، M مقدار برای‌ تابع‌هدف‌  به‌ دست‌ می‌دهند، که‌ آنها را برازندگی‌ کروموزوم‌ها می‌نامند.

 

از آنجا که‌ هدف‌، یافتن‌ بیشینه‌ی‌ تابع‌ هدف‌  است‌، هر کدام‌ از این‌ M دسته‌ مقدار که‌ مقدار بزرگتری‌ برای‌  به‌ دست‌ می‌دهد, برازنده‌تر است‌. همان‌ طور که‌ برازندگی‌ هر فرد، میزان‌ احتمال ‌بقای‌ او در طبیعت‌ را مشخص‌ می‌کند. مقدار برازندگی‌ هر کروموزوم‌ نیز، میزان‌ احتمال‌ حضور آن‌در جمعیت‌ بعدی‌ را تعیین‌ می‌کند.

 

۳-۴-۳-۴-     الگوریتم‌های گزینش‌

            در انتخاب نسل بعد چندین روش وجود دارد که سه روش مهم آن عبارت است از]۱۲[:

۱-      انتخاب بهترین‌ها به صورت قطعی

۲-      انتخاب بر اساس مکانیزم چرخ رولت یا گردون

۳-      انتخاب بر اساس مسابقه

۳-۴-۳-۴-۱- انتخاب قطعی[۲]

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

 

۳-۴-۳-۴-۲- مکانیزم چرخ گردان۱

            انتخاب براساس چرخ گردان تصادفی است و برای اعضای بد جمعیت نیز شانسی برای انتخاب شدن در نظر می‌گیرد. در این مکانیزم‌، یک‌ دسته‌ از کروموزوم‌ها براساس‌ برازندگی‌ خود و نیز به ‌کمک‌ اعداد تصادفی‌، از جمعیت‌ پیشین‌ خود برگزیده‌ می‌شوند. شکل‌ ۳-۳، گردونه‌ی‌ بخت یا چرخ گردان‌ را نمایش‌ می‌دهد. هر کروموزوم‌ درصدی‌ از سطح‌ این‌ گردونه‌ را، که ‌با برازندگی‌ آن‌ نسبت‌ مستقیم‌ دارد، می‌پوشاند. این‌ درصد سطح‌ برای‌ هر کدام‌ از کروموزوم‌ها، احتمال‌ گزینش‌ آن‌ کروموزوم‌ نامیده‌ می‌شود و برابر است‌ با

(۳-۹)

 

 

اکنون‌ گردونه‌ای‌ هست‌ که‌ بر روی‌ آن‌ M کروموزوم‌ با درصد سطح‌های‌  نشسته‌اند. یک ‌پیکان‌ در کنار این‌ گردونه‌ در نظر گرفته‌ می‌شود و گردونه‌ را می‌چرخانیم‌. گردونه‌ می‌چرخد تا زمانیکه‌ متوقف‌ شود. سطحی‌ که‌ روبروی‌ این‌ پیکان‌ می‌ایستد، کروموزوم‌ برگزیده‌ را نشان‌می‌دهد. با M بار چرخاندن‌ گردونه‌، M کروموزوم‌ برگزیده‌ می‌شوند، بدین‌ ترتیب‌، فرآیند گزینش ‌پایان‌ می‌پذیرد و یک‌ جمعیت‌ نوین‌ به‌ دست‌ می‌آید. کروموزوم‌های‌ این‌ جمعیت‌ نوین‌ را والدین‌می‌نامند.

شکل‌۳-۳٫ گزینش‌ به‌ کمک‌ گردونه‌ی‌ بخت‌

 

 

 

۳-۴-۳-۴-۳- انتخاب بر اساس مسابقه۱

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

 

 

 

REPRODUCTION: تولید مثل

Reproduction یا همان تولید نسل بعدی در حالت کلی به دو روش انجام می شود:

 

  • Crossover پیوند

در این روش از هر دو والد، دو فرزند تولید خواهد شد، یا به عبارت کلی از n والد، n فرزند تولید خواهد شد. در روش Crossover این احتمال وجود دارد که کروموزوم های والدین بدون هیچ تغییر و بهینه سازی به فرزندان منتقل شوند، و یا کروموزوم های والدین بصورت تصادفی با یکدیگر ترکیب شده و در فرزندان ظاهر شوند. در حالت کلی احتمال وقوع Crossover ، ۰٫۶~۱٫۰ است.

روش Crossover نیز به چند طریق انجام می شود:

۱-۱- Single point crossover :

در این روش یک نقطه را بصورت تصادفی در رشته های ژنی (کروموزوم) والدین انتخاب
می کنیم و از این نقطه ها، کروموزوم ها را به دو قسمت تقسیم می کنیم و سپس این دو قسمت را در دو کروموزوم جابجا می کنیم تا دو فرزند(کروموزوم) جدید داشته باشیم.

 

 

 

Randomly chosen position

 

 

 

Parents:                    ۱۰۱۰۰۰۱۱۱۰                   ۰۰۱۱۰۱۰۰۱۰

 

 

 

Offspring:                ۱۰۱۰۰۱۰۰۱۰                   ۰۰۱۱۰۰۱۱۱۰

 

نحوه انجام Single point crossover در رشته ژن های بیتی

Single point crossover در دو کروموزوم والد

 

 

۱-۲- Two point crossover (Multi point crossover) :

این روش همانند Single point crossover است، با این تفاوت که بجای یک نقطه دو یا چند نقطه بصورت تصادفی انتخاب می شوند و کروموزوم های والد از این نقاط به چند قسمت تقسیم می شوند. ویژگی این نوع crossover این است که برای فرزندان، شکل های بیشتری از ترکیب قسمت های مختلف کروموزوم های والد وجود دارد. یکی دیگر از ویژگی های این نوع crossover این است که در تولید کروموزوم های جدید، ژن های ابتدا(head) و انتها (tail) دست نخورده باقی می مانند.

 

Randomly  chosen   position

 

 

 

Parents:                     ۱۰۱۰۰۰۱۱۱۰                       ۰۰۱۱۰۱۰۰۱۰

 

 

 

 

Offspring:                  ۰۱۰۱۰۱۰۰۱۰             ۰۰۱۱۰۰۱۱۱۰

 

نحوه انجام Two point crossover در رشته ژن های بیتی

Two point crossover در دو کروموزوم والد

 

۱-۳- Uniform crossover :

در این روش یک ماسک، که دقیقا به اندازه طول رشته ژنی است، به روشی تصادفی تولید
می شود. این ماسک مشخص می کند که کدام ژن ها از کروموزوم اول و کدام ژن ها از کروموزوم دوم برای تولید فرزند اول استفاده می شوند و همچنین فرزند دوم نیز بر همین اساس و فقط برعکس فرزند اول خواهد بود. مزیت این روش نسبت به Single point crossover این است که در این روش، امکان بوجود آمدن ویژگی های جدید وجود دارد، برعکس Single point crossover که تنها ویژگی های قبلی با هم ترکیب می شدند و ویژگی جدیدی بوجود نمی امد. همچنین ویژگی های مناسب نیز در راه حل (کروموزوم) تا حدی حفظ خواهد شد. در واقع Uniform crossover یک مصالحه بین این دو ویژگی است.

 

Mask:                       ۰۱۱۰۰۱۱۰۰۰                     (Randomly generated)

Parents:                    ۱۰۱۰۰۰۱۱۱۰           ۰۰۱۱۰۱۰۰۱۰

 

Offspring:                ۰۰۱۱۰۰۱۰۱۰               ۱۰۱۰۰۱۰۱۱۰

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

Uniform crossover در دو کروموزوم والد

 

 

مشکلات Crossover:

بسته به نوع CODING و بیان مسئله، یک Crossover ساده می تواند شانس تولید کروموزوم های غیر مجاز را افزایش دهد. البته با استفاده از روش Uniform Crossover بهینه شده
می توان تا حد زیادی از این مشکلات جلوگیری کرد.

 

  • Mutation جهش

در این روش از هر والد یک فرزند بوجود خواهد آمد. در این روش امکان بوجود آمدن
ویژگی های بیشتر از روش Crossover است. در روش Crossover فقط ترکیب ژن ها عوض
می شود درحالی که در روش Mutation ژن های جدیدی بوجود می آیند.

 

Mutation در یک کروموزوم والد

 

استراتژی انتخاب والدین:

  • همیشه بهترین ها را برای تولید نسل بعد حفظ کنید
  • نخبه گرائی : اعضاء ضعیف تر را حذف کنید
  • احتمال انتخاب افراد برای بقاء و تولید نسل، با میزان تطبیق آنها با تابع تطبیق نسبت عکس دارد.

تابع تطبیق یک مسئله مهم در انتخاب والدین است. بطوریکه اگر این تابع بسیار قوی باشد، جواب های بسیار دقیقی خواهیم داشت و اگر این تابع ضعیف باشد و تمام شرایط را درنظر گرفته نباشد، یا به جواب نمی رسیم یا اگر هم برسیم، جواب های ما دقیق نخواهند بود.

-۴-۴- شرط همگرایی الگوریتم ژنتیک

            شرایط مختلفی را می‌توان معیار همگرایی الگوریتم مورد استفاده قرار داد. در بعضی تحقیقات تکرار هشتاد درصد اعضای جمعیت جاری در نسل جدید، به عنوان شرط پایانی محاسبات الگوریتم منظور شده است]۱۲[. در بعضی تحقیقات دیگر تکرار متوالی یک مقدار خاص به عنوان تابع هدف، شرط همگرایی الگوریتم است. معمولاً شرط‌ پایانی‌ را تعداد نسل‌ها یا بیشینه‌ی ‌موجود در جمعیت‌ در نظر می‌گیرند]۸[.

۱- Fitness

۱- Deterministic Selection