מינימום מקומי ומינימום גלובלי – איך אלגוריתמים נתקעים בדרך לפתרון טוב יותר

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

אפשר להסיק שהגענו לפסגה.

אבל האם זו באמת הפסגה הגבוהה ביותר באזור?

לא בהכרח.

זהו בדיוק הרעיון של מינימום מקומי ו-מינימום גלובלי.

מהו מינימום גלובלי?

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

אם מדובר בתכנון מסלולים, זהו המסלול בעל העלות הנמוכה ביותר מבין כל המסלולים האפשריים.

אם מדובר בשיבוץ עובדים, זהו השיבוץ בעל העלות המינימלית מתוך כל האפשרויות.

זהו היעד האולטימטיבי של תהליך האופטימיזציה.

מהו מינימום מקומי?

מינימום מקומי הוא פתרון שנראה מצוין בהשוואה לפתרונות הקרובים אליו.

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

לדוגמה:

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

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

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

למה זה קורה?

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

הוא דומה יותר לנוף הררי.

יש בו:

• עמקים רדודים

• עמקים עמוקים

• גבעות

• רכסים

• מבויים סתומים

אלגוריתם של Local Search נע במורד ההר.

ברגע שאין יותר ירידה אפשרית, הוא נעצר.

מבחינתו הוא הגיע ליעד.

אבל בפועל הוא רק הגיע לעמק הקרוב ביותר.

איך בורחים ממינימום מקומי?

יש כמה שיטות נפוצות.

קפיצות גדולות

במקום להזיז תלמיד אחד,

מזיזים קבוצה שלמה.

קבלת פתרונות גרועים זמנית

לפעמים כדאי להסכים לעלות על גבעה קטנה,

כדי להגיע לעמק עמוק יותר בהמשך.

זו בדיוק הגישה של Simulated Annealing.

זיכרון של צעדים קודמים

אם כבר ביקרנו בפתרון מסוים,

אין טעם לחזור אליו שוב.

זו הגישה של Tabu Search.

התחלה מחדש

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

מבצעים מספר ריצות שונות,

ובוחרים את הפתרון הטוב ביותר שהתקבל.

למה זה חשוב?

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

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

אבל בפועל,

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

הבנת ההבדל הזה היא אחת מנקודות המפנה החשובות ביותר בלימוד אופטימיזציה.

מחשבה לסיום

כאשר אלגוריתם נתקע,

זה לא תמיד אומר שהוא נכשל.

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

המטרה של אופטימיזציה אינה רק לרדת במדרון.

היא לדעת מתי צריך דווקא לטפס קצת, כדי להגיע לעמק עמוק יותר.