איך משפרים פתרון בלי להתחיל הכול מחדש - Local Search

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

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

מהו Local Search?

הרעיון פשוט מאוד:

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

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

אם כן – מאמצים אותו.

אם לא – מנסים שינוי אחר.

דוגמה פשוטה

נניח שיש לנו מסלול:

A → B → C → D → E

אפשר לבצע שינוי קטן:

A → C → B → D → E

כעת מחשבים מחדש את העלות הכוללת.

אם המסלול החדש קצר יותר, נשמור אותו.

אם הוא גרוע יותר, נחזור למסלול הקודם.

ואז נמשיך לנסות שינויים נוספים.

מהו "שכן"?

ב־Local Search כל פתרון מוקף בפתרונות דומים.

לפתרונות האלו קוראים Neighbors.

לדוגמה:

• החלפת שתי נקודות במסלול.

• העברת לקוח מרכב אחד לאחר.

• החלפת קבוצת תלמידים בין שני רכבים.

• שינוי סדר העצירות.

כל פעולה כזו מייצרת שכן חדש.

למה זה עובד?

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

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

כך ניתן להגיע לפתרונות טובים מאוד בזמן קצר.

הבעיה הגדולה

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

לדוגמה:

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

האלגוריתם נעצר.

אבל האם באמת מצאנו את הפתרון הטוב ביותר?

לא בהכרח.

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

לתופעה הזו קוראים מינימום מקומי.

אז מה עושים?

יש כמה דרכים להתמודד עם הבעיה:

• לבצע שינויים גדולים יותר.

• לאפשר לעיתים מעבר לפתרון גרוע יותר.

• לזכור אילו פתרונות כבר נבדקו.

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

שיטות אלו שייכות לעולם ה־Metaheuristics, עליו דיברנו במאמר הקודם.

איפה משתמשים ב־Local Search?

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

• תכנון משלוחים

• הסעות תלמידים

• שיבוץ נהגים

• הקצאת משימות

• תכנון ייצור

• ניהול מחסנים

• תכנון סבבי שירות לטכנאים

מחשבה לסיום

שיטת Local Search מלמד אותנו עיקרון חשוב:

לא תמיד צריך להתחיל מחדש כדי להגיע לתוצאה טובה יותר.

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

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

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