כשכללי האצבע כבר לא מספיקים - Metaheuristics

במאמר הקודם הכרנו את מושג ה־Heuristic – שיטה חכמה למציאת פתרון טוב בזמן סביר.

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

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

כאן נכנסות לתמונה ה־Metaheuristics.

מהי Metaheuristic?

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

אז Metaheuristic היא:

אסטרטגיה לניהול תהליך החיפוש עצמו.

במילים אחרות:

היא לא אומרת איזה פתרון לבחור.

היא אומרת:

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

דוגמה פשוטה

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

גישה היוריסטית פשוטה תהיה:

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

אבל גישת Metaheuristic תהיה:

• לבדוק מספר אזורים.

• להשוות בין אפשרויות.

• לחזור אחורה אם צריך.

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

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

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

למה בכלל צריך Metaheuristics?

בבעיות מורכבות יש תופעה נפוצה:

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

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

המערכת "נתקעת".

לנקודה הזו קוראים לעיתים:

מינימום מקומי.

הפתרון נראה טוב.

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

איך Metaheuristics עוזרות?

במקום להתקדם רק בכיוון אחד,

הן מאפשרות:

• לחקור אזורים חדשים.

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

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

• להימנע מחזרה על אותן טעויות.

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

דוגמאות מפורסמות

שיטת Simulated Annealing

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

• המטרה היא לצאת ממלכודות מקומיות ולהמשיך לחפש.

שיטת Tabu Search

• שיטה ששומרת זיכרון של מהלכים קודמים.

• כך נמנעת חזרה לאותם פתרונות שוב ושוב.

שיטת Genetic Algorithms

• שיטה בהשראת האבולוציה.

• מספר פתרונות "מתחרים" זה בזה, משתלבים ומשתפרים לאורך זמן.

האם Metaheuristics מבטיחות פתרון מושלם?

לא.

וזה בדיוק הרעיון.

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

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

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

איפה משתמשים בזה?

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

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

• שיבוץ עובדים.

• תכנון ייצור.

• ניהול שרשרת אספקה.

• תכנון הסעות.

• הקצאת משאבים.

• מערכות תפעוליות מורכבות.

מחשבה לסיום

היוריסטיקה מלמדת אותנו איך לקבל החלטה טובה.

מטא-היוריסטיקה (Metaheuristic) מלמדת אותנו איך לחפש החלטות טובות.

זה אולי נשמע כמו הבדל קטן.

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

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