صفحه قبلی – صفحه بعدی

تابع تطابق

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

  • محاسبه تابع تناسب باید به اندازه کافی سریع باشد.
  • باید بصورت کمی اندازه گیری کند که یک راه حل معین به چه اندازه مناسب است یا اینکه از طریق راه حل داده شده چگونه می توان راه حلهای مناسبی تولید کرد.

در بعضی موارد، ممکن است به دلیل پیچیدگی ذاتی مساله محاسبه تابع تناسب به طور مستقیم  ممکن نباشد. در چنین مواردی، تابع تناسب را با توجه به نیازهای مساله انجام می دهیم.
تصویر زیر محاسبات تابع تناسب را برای راه حل مساله کوله پشتی صفر و یک (0/1 Knapsack) نشان می دهد. این یک تابع تناسب ساده است که فقط مقادیر سود اقلام انتخاب شده را جمع آوری می کند (که دارای 1 هستند)  و این کار را به ترتیب از چپ به راست انجام می دهد تا کوله پشتی پر شود.
Binary Representation

صفحه قبلی – صفحه بعدی

پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *