פונקציית המטרה: איך מלמדים מחשב מהו פתרון טוב?

בכל בעיית אופטימיזציה יש שאלה אחת בסיסית:

איך המחשב יודע האם פתרון אחד טוב יותר מפתרון אחר?

התשובה היא פונקציית המטרה (Objective Function).

אפשר לחשוב עליה כעל מערכת הניקוד של הבעיה.

היא לא אומרת למחשב כיצד למצוא פתרון.

היא רק אומרת לו:

מבין שני פתרונות חוקיים – איזה מהם עדיף.

דוגמה פשוטה

נניח שיש לנו בעיית משלוחים.

פתרון א':

• 5 רכבים

• 1,000 ק"מ נסיעה

פתרון ב':

• 4 רכבים

• 1,100 ק"מ נסיעה

איזה פתרון טוב יותר?

אין תשובה אחת נכונה.

זה תלוי במה שחשוב לעסק.

אם רכב נוסף עולה הרבה כסף,

אולי עדיף פתרון ב'.

אם דלק הוא הגורם המשמעותי,

אולי עדיף פתרון א'.

פונקציית מטרה בסיסית

אפשר להגדיר:

עלות = מספר רכבים × 1000 + קילומטרים

פתרון א'

5×1000 + 1000 = 6000

פתרון ב'

4×1000 + 1100 = 5100

לפי פונקציה זו,

פתרון ב' עדיף.

בעולם האמיתי יש יותר ממטרה אחת

בתכנון הסעות תלמידים למשל, נרצה לעיתים:

• למזער מספר רכבים

• למזער זמן נסיעה

• למנוע תלמידים בודדים ברכב

• להעדיף נהגים קבועים

• לאזן עומס בין נהגים

• לצמצם זמני המתנה

חלק מהמטרות אפילו מתנגשות.

אז איך משלבים מטרות?

משקלים

דוגמה:

עלות =1000×רכבים +10×דקות נסיעה +500×חריגה מקיבולת

כעת האלגוריתם מקבל ציון יחיד לכל פתרון.

סדרי עדיפויות

לפעמים לא רוצים פשרה.

לדוגמה:

1. אסור לחרוג מקיבולת

2. אחר כך לצמצם רכבים

3. אחר כך לצמצם מרחק

גישה זו נקראת לעיתים Lexicographic Optimization.

פונקציית מטרה גרועה = אופטימיזציה גרועה

נניח שמישהו ממזער רק מרחק.

המערכת עלולה להשתמש ב־100 רכבים.

אם ממזערים רק רכבים,

התלמידים עלולים לבלות שעה וחצי בנסיעה.

המחשב לא מבין מה "נכון".

הוא רק ממקסם או ממזער את מה שביקשנו ממנו.

מחשבה לסיום

רבים חושבים שהאתגר באופטימיזציה הוא לבחור את האלגוריתם הנכון.

אבל לעיתים קרובות,

החלק הקשה ביותר הוא דווקא להחליט

מה בכלל נחשב לפתרון טוב?

אלגוריתם מצוין עם פונקציית מטרה גרועה,

ימצא במהירות את הפתרון הלא נכון.