تعریف تابع هزینه در الگوریتم های بهینه سازی

مسئله :

یک جهانگرد می خواهد از شهر A به شهر B برود. بین این دو شهر، مسیرهای مختلفی وجود دارد که در هر مسیر باید از چند شهر عبور کند. طول جاده های مختلف نیز معلوم است و هدف این می باشد که جهانگرد کوتاهترین مسیر ممکن را برای رفتن از شهر A به شهر B طی کند.

شکل جواب ها :

جواب به صورت دنباله ای از اعداد است که هر عدد مربوط به شماره متناظر با یک شهر است (دقت کنید که منظور از شکل جواب، شکل کلی جواب مسئله به طور کلی است وگرنه هر الگوریتم بهینه سازی، جواب را تبدیل به شکلی می کند که بتواند روند بهینه سازی را برای مسئله اجرا نماید)

تعریف تابع هزینه :

در این مثال، تابع هزینه را می توان تنها به صورت یک جمع ساده در نظر گرفت. تنها کافی است که طول جاده های مختلف را که باید طی شوند با هم جمع بزنیم و عدد حاصل، برابر تابع هزینه مسئله می باشد. هر چقدر که این عدد کوچکتر باشد، جواب بهینه تر است. در واقع عبارت ((تابع هزینه)) نیز از همین مفهوم ناشی شده است، زیرا در زندگی عادی، معمولا سعی می شود که برای رسیدن به یک هدف خاص، کمترین ((هزینه)) ممکن پرداخت شود.

مسئله :

همان مسئله قبل، تنها با این تفاوت که جهانگرد علاوه بر این که دوست دارد با کمترین مسافت به شهر B برسد، همچنین می خواهد که از تعداد شهر بیشتری نیز عبور کند. منظور این است که اگر یک مسیر داریم که به طول 700 کیلومتر است و از 3 شهر می گذرد و همچنین مسیر دیگری به طول 800 کیلومتر وجود دارد که از 5 شهر می گذرد، جهانگرد مسیر عبوری از 5 شهر را انتخاب می کند و 100 کیلومتر اضافه برایش مهم نیست.

شکل جواب ها :

جواب به صورت دنباله ای از اعداد است که هر عدد مربوط به شماره متناظر با یک شهر است.

تعریف تابع هزینه :

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