تابع بهینگی
الگوریتم ژنتیک نیز مانند الگوریتم های متاهیوریستیک با گذر از حالتی به حالت دیگر در فضای
حالت مسئله به تدریج خود را به نقطه بهینگی سراسری مسئله نزدیک می کند. همچنین گذر
از حالتی به حالت دیگر بر اساس هزینه هر حالت انجام می پذیرد. در روش های جستجوی
متاهیوریستیک تخمین هزینه هر حالت با ستفاده از تابع هزینه انجام می گیرد. به عنوان
مثال هزینه حالت در مسئله 8 وزیر برابر است تعداد گاردهایی که وزیرها به همدیگر می
دهند. در الگوریتم ژنتیک نیز می توان مستقیما از تابع هزینه برای تخمین بهینگی یک
حالت استفاده کنیم . اما در برخی مسائل بهتر است که با کمی تغییر در تابع هزینه ،
بهینگی یک حالت را به
|
|
شکل عددی بین صفر و 1 نشان دهیم. به عنوان مثال در مسئله 8 وزیر می دانیم که حداکثر
تعداد گاردها زمانی اتفاق می افتد که وزیر ها در یک سطر ، در یک ستون و یا بر روی
یک قطر از صفحه شطرنج قرار گرفته باشند. در چنین حالتی حداکثر تعداد گاردها برابر
با 28 عدد خواهد بود. و در حالت کلی برای مسئله n وزیر حداکثر تعداد گاردها برابر
با 2/( N * N-1) خواهد بود. ما نیز از این مقدار استفاده کرده و با
استفاده از رابطه زیر میزان بهینگی یک حالتی از مسئله N وزیر مانند S را محاسبه می
کنیم :
|
Fitness(S) = Objective(S) / Guards
Guards = N * (N-1) / 2
|
ابا استفاده از فرمول بالا میزان بهینگی هر حالت در مسئله N وزیر عددی بین 0 و 1
خواهد بود. حال ممکن است این سوا مطرح شود که از تابع بهینگی به چه منظوری در
الگوریتم ژنتیک استفاده می شود؟ برای جواب دادن به این سوال یکبار دیگر به نظریه
دارین مراجعه می کنیم . بر اساس نظزیه داروین نسل هایی که از ویژگی های و خصوصیات
برتری نسبت به نسل های دیگر برخوردارند شانس بیشتری نیز برای بقا و تکثیر خواهند
داشت. در واقع تابع بهینگی میزان برتر بودن یک حالت نسبت به حالت دیگر را تخمین می
زند و موجب می شود که هنگام تکثیر، حالت هایی به نسل بعدی منتقل یابند که از بهینگی
بیشتری برخوردار هستند. همانند آنچه در نحوه نمایش کروموزوم ها مطرح کردیم ، در
اینجا نیز نحوه محاسبه میزان بهینگی در مسائل مختلف به شکل های گوناگونی انجام می
پذیرد.
|
|