כאשר האלגוריתמים מספקים: מהפכת הבינה המלאכותית בלוגיסטיקה

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

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

תוכנה זו, הנקראת פותר תכנות ליניארי מעורב-שלמים (MILP), מפצלת בעיית אופטימיזציה מסיבית לחתיכות קטנות יותר ומשתמשת באלגוריתמים גנריים כדי לנסות ולמצוא את הפתרון הטוב ביותר. עם זאת, הפותר עשוי לקחת שעות – או אפילו ימים – להגיע לפתרון.

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

האצת פתרונות עם למידת מכונה

חוקרים מ-MIT ו-ETH ציריך השתמשו בלמידת מכונה כדי להאיץ דברים.

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

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

הטכניקה החדשה הזו האיצה את פותרי ה-MILP בין 30 ל-70 אחוז, ללא כל נפילה דיוק. אפשר להשתמש בשיטה זו כדי להשיג פתרון אופטימלי מהר יותר או, לבעיות מורכבות במיוחד, פתרון טוב יותר בפרק זמן נסבל.

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

"לפעמים, בתחום כמו אופטימיזציה, נפוץ מאוד שאנשים חושבים על פתרונות כאל למידת מכונה גרידא או כקלאסית גרידא. אני מאמינה נחרצת שאנחנו רוצים להשיג את הטוב משני העולמות, וזהו מופע ממש חזק של הגישה ההיברידית הזו", אומרת הסופרת הבכירה קאתי וו, עוזרת פרופסור לפיתוח קריירה של גילברט וו. ווינסלו בהנדסה אזרחית וסביבתית ( CEE), וחבר במעבדה למערכות מידע והחלטות (LIDS) ובמכון לנתונים, מערכות וחברה (IDSS).

וו כתב את המאמר עם הכותבים המובילים בשיתוף Sirui Li, סטודנט לתואר שני ב-IDSS, ו-Wenbin Ouyang, סטודנט לתואר שני ב-CEE; כמו גם מקס פאולוס, סטודנט לתואר שני ב-ETH ציריך. המחקר יוצג בכנס על מערכות עיבוד מידע עצבי.

קשה לפתור

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

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

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

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

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

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

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

כיווץ מרחב הפתרונות

היא ושותפי הפעולה שלה פיתחו מנגנון סינון שמצמצם את מרחב החיפוש המפריד הזה מיותר מ-130,000 שילובים פוטנציאליים לכ-20 אפשרויות. מנגנון הסינון הזה נשען על העיקרון של הפחתת התשואות השוליות, שאומר שהיתרון הרב ביותר יגיע מקבוצה קטנה של אלגוריתמים, והוספת אלגוריתמים נוספים לא תביא לשיפור נוסף.

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

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

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

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

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

מחקר זה נתמך, בחלקו, על ידי Mathworks, הקרן הלאומית למדע (NSF), ה MIT Amazon Science Hub, וועדת התמיכה במחקר של MIT.