الگوریتم
ژنتیک
بدن هر موجود
زنده ای از سلول تشکیل یافته است و هر سلول هم از کروموزوم تشکیل یافته است
کروموزوم ها نیز از رشته های 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 می گردد.
پرداخت با کلیه کارتهای عضو شتاب امکان پذیر است.