משתני החלטה: מה בעצם האלגוריתם מחפש?

כשאנחנו אומרים שאלגוריתם "מחפש פתרון", נשאלת שאלה בסיסית:

מהו בכלל פתרון?

התשובה היא שבכל בעיית אופטימיזציה, פתרון הוא אוסף של ערכים שנבחרו עבור משתני החלטה (Decision Variables).

האלגוריתם לא מחפש מסלולים.

הוא לא מחפש רכבים.

הוא לא מחפש תלמידים.

הוא מחפש ערכים למשתנים.

מהו משתנה החלטה?

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

לדוגמה:

בתכנון הסעות תלמידים:

• לאיזה רכב משויך כל תלמיד.

• מה סדר האיסוף בכל רכב.

• באיזו שעה הרכב יוצא.

• האם להשתמש ברכב מסוים או לא.

אלו הן ההחלטות שהאלגוריתם צריך לקבל.

למה ייצוג הבעיה חשוב?

נניח שיש לנו 100 תלמידים.

אפשר לייצג את הבעיה כך:

לכל תלמיד נשמור את מספר הרכב שלו.

או כך:

לכל רכב נשמור רשימת תלמידים.

או כך:

נחזיק מטריצה שמייצגת מעבר בין נקודות.

שלושת הייצוגים מתארים בדיוק את אותה הבעיה.

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

דוגמה מבעיית הסוכן הנוסע

אפשר לייצג מסלול באמצעות רשימה:

A → B → C → D

ואפשר לייצג אותו באמצעות מטריצה:

From	To
A	B
B	C
C	D

הפתרון זהה.

הדרך לעבוד איתו שונה.

משתנים רציפים, שלמים ובינאריים

משתנה בינארי

יכול לקבל רק 0 או 1.

לדוגמה:

האם רכב מספר 5 מופעל?

1 = כן

0 = לא

משתנה שלם

מספר התלמידים ברכב.

0,1,2,3...

משתנה רציף

שעת יציאה.

07:15

07:16

07:17

ייצוג טוב הוא חצי מהפתרון

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

אותו אלגוריתם בדיוק,

עם ייצוג אחר של הבעיה,

יכול לעבוד פי עשרה מהר יותר.

ולפעמים אפילו למצוא פתרונות טובים יותר.

זו אחת הסיבות שבמערכות אופטימיזציה מסחריות, חלק גדול מהעבודה הוא בכלל לא בחירת האלגוריתם.

אלא בחירת משתני ההחלטה הנכונים.

מחשבה לסיום

רבים שואלים:

איזה אלגוריתם כדאי לבחור?

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

מה בעצם האלגוריתם אמור לבחור?

אם נגדיר את משתני ההחלטה בצורה נכונה,

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

ואם נגדיר אותם בצורה גרועה,

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