מי הם ה"שכנים" של הפתרון שלך? Neighborhood Search

אם מרחב הפתרונות הוא מפה ענקית של כל הפתרונות האפשריים, אז השאלה הבאה היא:

איך בכלל זזים בתוך המפה הזאת?

התשובה נמצאת במושג שנקרא Neighborhood Search.

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

מהו Neighbor?

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

לדוגמה, נניח שיש לנו מסלול:

A → B → C → D → E

אפשר ליצור שכן על ידי החלפת שתי נקודות:

A → C → B → D → E

או על ידי העברת נקודה למיקום אחר:

A → B → D → C → E

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

שכנים בעולם האמיתי

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

• העברת תלמיד אחד מרכב לרכב אחר

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

• איחוד שני מסלולים

• פיצול מסלול קיים

• שינוי סדר האיסוף בתוך מסלול

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

למה שכנים כל כך חשובים?

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

יכול להיות שנצליח להשתפר קצת.

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

כלומר:

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

שכונה קטנה או שכונה גדולה?

לכל בחירה יש מחיר.

שכונה קטנה

יתרונות:

• מהירה לבדיקה

• מעט אפשרויות

חסרונות:

• קל להיתקע

שכונה גדולה

יתרונות:

• מאפשרת קפיצות משמעותיות

• מקטינה סיכוי להיתקע

חסרונות:

• דורשת יותר חישובים

לא חייבים לבחור רק סוג אחד -Neighborhood Search

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

לדוגמה:

80% מהזמן:

• החלפת תלמיד אחד

15% מהזמן:

• החלפת קבוצות תלמידים

5% מהזמן:

• איחוד מסלולים שלמים

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

מה אפשר ללמוד מזה?

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

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

אילו שינויים אנחנו בכלל מרשים לעצמנו לבצע?

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

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

מחשבה לסיום

אם מרחב הפתרונות הוא מפה,

אז השכנים הם הכבישים שמחברים בין הנקודות.

ואם אין כביש שמוביל למקום טוב יותר,

כנראה שלעולם לא נגיע אליו.