الگوریتم
ژنتیک
بدن هر موجود
زنده ای از سلول تشکیل یافته است و هر سلول هم از کروموزوم تشکیل یافته است
کروموزوم ها نیز از رشته های DNA تشکیل یافته
اند. به هر بلوک DNA یک ژن می گویند. و هر ژن نیز از یک پروتئین
خاص و منحصر به فرد تشکیل یافته است. به مجموعهای از ژن ها یک ژنم (GENOME) می گویند.
از اصطلاحاتی که از مباحث زیست شناسی به مبحث الگوریتم ژنتیک (GE) وارد شده است و باید به آتها اشاره کرد می توان به موارد زیر
اشاره نمود.
1-
تولید مثل(crossover) که به تولید یک کروموزوم جدید توسط ترکیب ژن های والدین می گویند.
2-
جهش یا تغییر ناگهانی(mutation): به تغییرات ایجاد شده در DNA میگویند
3-
صحت و درستی(fitness): برای یک موجود زنده به صورت موفقیت آن موجود در ایجاد حیات و
تشکیل خود می گویند. البته ممکن است در نگاه اول مطالب بالا کمی نامفهوم به نظر
برسد. اما در ادامه به توضیح بیشتر آنها و همچنین نوع کاربرد آنها در الگوریتم
ژنتیک اشاره خواهد شد (1) .
1-1-1-کلیات الگوریتم ژنتیک (4)
الگوريتم هاي
ژنتيك روش قدرتمندي را براي توسعه اكتشافي مسائل بهينه سازي تركيبي مقياس بزرگ
فراهم آورده است . انگيزه اصلي مطرح كردن الگوريتم ژنتيك مي تواند اين گونه عنوان
شودكه «تكامل تدريجي» به شكل قابل ملاحظه اي در توسعه انواع وگونه هاي پيچيده از
طريق مكانيزم هاي نسبتاً ساده تكميلي نمود يافته است . حال سوال اساسي اين است :
پذيرش كدام ايده از تئوري تكامل تدريجي مي تواند به ما در حل مسائل اين قلمرو كمك
كند ؟ اين سوال با توجه به غناي پديده تكامل تدريجي جوابهاي متفاوتي دارد. هالند و
دي جانگ (1975) از نخستين كساني هستندكه با معرفي مفهوم الگوريتم ژنتيك به عنوان
يك تكنيك جستجوي عمومي كه از تكامل تدريجي بيولوژیك در قالب بقاي افراد اصلح و
مبادله ساختارمند و تصادفي اطلاعات الگوبرداري مي كند درصدد پاسخگويي به اين سوال
برآمدند.
يك الگوريتم
ژنتيك مسئله را به صورت مجموعه اي از رشته ها كه شامل ذرات ريزهستند كد گذاري مي
كند ، سپس براي تحريك فرايند تكامل تدريجي ،تغييراتي را بر روي رشته ها ا عمال مي‌دارد.
در مقايسه با الگوريتم هاي جستجوي محلي ، در جستجوي عمومي كه تنها يك راه حل قابل
قبول وجود دارد ، الگوريتم هاي ژنتيك جامعه اي از افراد را در نظر مي‌گيرند . كار
با مجموعه اي از افراد، امكان مطالعه ساختارها و ويژگيهاي اصلي افراد متفاوت را كه
منجر به شناسايي و كشف راه حلهاي كارآمد تر مي شود، فراهم مي‌سازد . در طي مطالعه
، الگوريتم ژنتيك رشته هاي متناسب با ارزش را برمي گزيند و آن دسته از رشته هايي
را كه تنــاسب كمتري با جمعيت مورد بررسي دارند حذف مي‌كنند .
هر کدام افراد
جمیعت که تقریبهای از جواب نهایی می باشند به صورت رشته هایی از حروف یا ارغام
کدگذاری می شوند این رشته ها را کروموزوم می نامند. متداول ترین حالت نمایش با
ارقام صفر و یک است. حالتهای دیگر استفاده از سه رقم، اعداد حقیقی و اعداد صحیح هم
مورد استفاده قرار می گیرند. برای مثال یک کروموزوم با دو متغییر a
,b با ساختار شکل 1-1 نمایش داده می شود.
100111100010000100111
شکل 1-1- نمایش یک کروموزوم
با ارقام صفر و یک
متغییر a
با ده خانه اول سمت راست و b با یازده
خانه باقیمانده نمایش داده شده است. این می تواند به علت سطح دقت و یا محدوده
متغییر تصمیم گیری باشد.
مقادیرموجود
بر روی کروموزوم ها به تنهایی معنی خاص ندارند بلکه باید از حالت کد شده خارج شوند
تا به عنوان متغییرهای تصمیم گیری دارای معنی و نتیجه باشند باید توجه داشت که
فرآیند جستجو بر روی اطلاعات کد شده انجام می گیرد مگر در صورتی که از ژن هایی با
مقادیر حقیقی شود. بعد از اینکه کروموزوم ها از حالت کدگذاری شده خارج شدند می
توان کارایی یا برازش هر فرد از جمیعت را محاسبه کرد. برازش مقیاس نسبی است که
شایستگی افراد برای تولید نسل بعد را نشان می دهد. در طبیعت برازش معادل توانایی
فرد برای بقا می باشد. تابع هدف در تعیین برازش افراد نقش تعیین کننده دارد.
در هنگام
تکثیر به کمک اطلاعات اولیه ای که از تابع هدف
به دست می آید. برازش هر فرد مشخص می گردد. از این مقادیر در فرآیند انتخاب
استفاده می شود تا آنرا به سمت انتخاب افراد مناسب سوق دهد. هر
چه برازش فرد نیبت به جمیعت بالاتر باشد احتمل بیشتری دارد که انتخاب شود. هر چه
برازش نسبی آن کمتر باشد احتما انتخاب آن
برای تولید نسل بعد ی کمتر می شود(4).
وقتی که برازش تمام افراد جمیعت مشخص شد. هر کدام با احتمالی که متناسب با
میزان برازش آنهاست می توانند برای تولید نسل بعد انتخاب شوند. عمل تکثیر در
الگوریتم ژنتیک برای رد و بدل اطلاعات ژنتیکی بین یک جفت یا تعداد بیشتری از افراد
به کار می رود. ساده ترین نوع تکثیر تقاطع یک نقطه است دو رشته شکل را در
نظر بگیرید اگر یک عدد صحیح از یک تا تعداد ارقام رشته منهای یک انتخاب شود و
اطلاعات دو رشته را در دو طرف
این دو نقطه عوض کنید دو رشته جدید به
وجود می آیند که آنها را فرزند می نامیم به عنوان مثال اگر عدد شش را برای دو رشته
شکل انتخاب کنیم نتیجه تقاطع یک نقطه ای
به صورت شکل1-2 در می آید.
11100100011101
10010110101101
شکل 1-2-a دو کرموزوم قبل
از تقاطع (والدین)
11100110101101
10010100011101
شکل 1-2-b دو کروموزوم بعد از تقاطع (فرزندان)
این عملگر
الزاما بر تمامی رشته های یک جمیعت اعمل نمی شود بلکه برای اعمال آن بر یک جفت
رشته یک احتمال نسبت داده می شود. بعد از این مرحله با احتمال جدید عملگر جهش بر
روی رشته های تولید شده اعمال می گردد. در جهش ، هر فرد به تنهایی با توجه به
قوانیین احتما می تواند تغییر کند.
در نمایش
دودویی رشته ها، جهش به معنای تغییر مقدار یکی از خانه های رشته از صفر به یک و یا
از یک به صفر می باشد. به عنوان مثال جهش در هفتمین خانه اولین فرزند تولید شده در
مثال قبل منجر به ایجاد رشته شکل 1-3 می گردد.