איך מפרקים בעיה ענקית לבעיות קטנות - Clustering

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

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

לחלק את הבעיה לקבוצות קטנות יותר, ולפתור כל קבוצה בנפרד.

לגישה הזו קוראים Clustering.

מהו Cluster?

קלאסטר Cluster הוא אוסף של פריטים שדומים זה לזה או קשורים זה לזה בדרך כלשהי.

לדוגמה, בתכנון מסלולי הסעות תלמידים, אפשר לקבץ תלמידים לפי:

• אזור מגורים

• מוסד לימודים

• שעות התחלה וסיום

• מאפייני הסעה מיוחדים

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

למה זה עוזר?

נניח שיש לנו 1,000 תלמידים.

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

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

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

Clustering לא משפר את הפתרון עצמו.

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

האם חלוקה לקבוצות פוגעת באופטימליות?

כן.

וזו אחת הפשרות המרכזיות בתחום.

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

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

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

סוגי Clustering נפוצים

גיאוגרפי

קיבוץ לפי קרבה פיזית.

מתאים למשלוחים, הסעות וטכנאים.

לפי אילוצים

קיבוץ לפי מאפיינים משותפים:

• מוסד לימודים

• סוג רכב

• חלון זמן

• נהג קבוע

דינמי

במקום לקבוע קבוצות פעם אחת,

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

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

קלסטרינג Clustering בעולם האמיתי

בפועל, מערכות רבות משתמשות ב־Clustering כשלב ראשון.

לדוגמה:

1. מחלקים תלמידים לקבוצות.

2. יוצרים מסלולים ראשוניים.

3. מאחדים מסלולים במידת הצורך.

4. מפעילים Local Search או Metaheuristics לשיפור נוסף.

כלומר:

Clustering אינו פתרון.

הוא כלי לארגון הבעיה.

מחשבה לסיום

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

לפעמים הדרך להגיע לתוצאה טובה יותר היא דווקא להתחיל בלפרק את הבעיה.

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