تابع برازش در الگوریتم ژنتیک – Fitness Function

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

قبل از اینکه بخواهیم مطالب مونو ادامه بدیم یک نگاهی می ندازیم به چرخه الگوریتم ژنتیک تا ببینیم کجا هستیم.

چرخه الگوریتم ژنتیک

همون طور که توی شکل بالا مشخصه ما تا حالا فقط قسمت اول چرخه که ایجاد جمعیت اولیه است رو بررسی کردیم. خوب بریم سراغ بخش دوم یعنی ارزیابی جواب‌ها.
همانطور که گفتیم هر کروموزوم توی الگوریتم ژنتیک یعنی یک جواب حالا ما باید یک معیار داشته باشیم تا بتونیم این جواب‌ها رو بررسی کنیم کدوم یک از کروموزوم ها خوبه کدوم یک از کروموزوم ها خوب نیست. به عبارت دیگر می خواهیم مشخص کنیم جواب (کروموزوم ) تا چه اندازه‌ای خوب است.
برای اینکه بتونیم خوب یا بد بودن جواب رو تعیین کنیم از یک مفهوم کمک می گیریم به عنوان تابع برازش (fitness function). نکته مهم در مورد تابع برازش در الگوریتم ژنتیک این است که خروجی الگوریتم ژنتیک بسیار به این تابع وابسته است. اگر تابع میزان خوب بودن جواب رو نتواند به درستی نشان دهد مسلما الگوریتم ما جواب اشتباه می دهد. به هیمن خاطر باید در تعیین تابع برازش بسیار دقیق باشیم. در مطالب بعدی نمونه های مختلفی از تابع برازش رو توی مسائل مختلف بررسی میکنیم. اگر مفهوم چندان برای شما قابل درک نیست نگران نباشید، مفصل در موردش صحبت خواهیم کرد.

این تابع برازش مثل هر تابع دیگه ای یک ورودی داره و یک خروجی. توی شکل زیر مشخصه:

ورودی تابع برازش در الگوریتم ژنتیک: کروموزوم (یا همون جواب)
خروجی تابع برازش در الگوریتم ژنتیک: میزان خوب بودن کروموزوم (یا همون میزان خوب بودن جواب)

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

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