משתמש:Anna1007/אופטימיזציה מבוססת תבונת נמלים

התנהגות נמלים כהשראה לבעיות מטה-היוריסטיות

במדעי מחשב וחקר ביצועים, אופטימיזציה מבוססת תבונת נמלים (ACO, Ant colony optimization) הינה טכניקה הסתברותית למציאת פתרון לבעיות חישוביות אשר מוצאת את הנתיבים הקצרים ביותר באמצעות תורת הגרפים. אלגוריתם זה הינו חלק ממשפחת אלגוריתמים מבוססי תבונת נמלים, בשיטות מבוססות תבונת נחיל (PSO, Particle swarm optimization), ומהווה חלק מאופטימיזציה מטה-היוריסטית (metaheuristic).
השיטה הוצעה על ידי Marco Dorigo בשנת 1992 כחלק מעבודת הדוקטורט שלו , מטרתו של האלגוריתם הראשון היתה לחפש את הנתיב האופטימאלי בגרף המבוסס על התנהגות של נמלים המחפשות נתיב בין המושבה שלהם למקור המזון. הרעיון המקורי התחיל מניסיון למצוא פתרון לבעיות מספריות, שהתבסס על התנהגות של נמלים.

סקירה

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

פתרון האלגוריתם

התכנסות

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

אלגוריתם בסיסי

  procedure ACO_MetaHeuristic
    while(not_termination)
       generateSolutions()
       daemonActions()
       pheromoneUpdate()
    end while
  end procedure

בחירת צמתים

נמלה היא סוכן חישובי פשוט באלגוריתם מבוסס תבונת נמלים. בצורה איטרטיבית, הנמלה בונה פתרון לבעיה. בכל איטרציה של המודל, כל מהלכי הנמלה במעבר ממקום $x$ למקום $y$ הינם חלק מהפתרון השלם. לפיכך, כל נמלה K מחשבת סט $A_{k}(x)$ של מצבים אפשריים בהתאם למצב בו נמצאת בכל איטרציה, ומתקדמת לצעד הבא לפי חישוב הסתברותי. לנמלה K, ההסתברות $p_{xy}^{k}$ לנוע ממקום X למקום Y תלוי בשני ערכים: "האטרקטיביות" $\eta _{xy}$ של המהלך המחושבת על ידי רמת הכדאיות ו"רמת הנתיב" $\tau _{xy}$ המעיד על רמת המיומנות של המהלך. בסיום השוטטות של הנמלה, רמת הנתיב מתעדכנת בהתאם לסיווג הנמלה, נתיב טוב מקבל משוב חיובי ונתיב לא טוב מקבל משוב שלילי.

באופן כללי, ההסתברות למעבר מנקודה $x$ ל $y$ של נמלה $K$ היא:

$p_{xy}^{k}={\frac {(\tau _{xy}^{\alpha })(\eta _{xy}^{\beta })}{\sum _{y\in \mathrm {allowed} _{y}}(\tau _{xy}^{\alpha })(\eta _{xy}^{\beta })}}$

כאשר:
$\tau _{xy}$ , הוא כמות הפרומון שהופרשה במעבר מנקודה $x$ לנקודה $y$.
0 ≤ $\alpha$, הוא פרמטר השולט בהשפעה על $\tau _{xy}$.
$\eta _{xy}$, הוא כדאיות המעבר מ $x$ ל $y$.
$\beta$ ≥ 1, הוא פרמטר השולט בהשפעה על $\eta _{xy}$.
ה- $\tau _{xy}$ וה- $\eta _{xy}$ מציגים את האטרקטיביות ורמת הנתיב למעבר בין הנקודות האפשריות.

עדכון הפרומון

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

$\tau _{xy}\leftarrow (1-\rho )\tau _{xy}+\sum _{k}\Delta \tau _{xy}^{k}$

כאשר:
$\tau _{xy}$, הוא כמות הפרומון שהופרשה במעבר מנקודה $x$ לנקודה $y$.
$\rho$, הוא מקדם אידוי הפרומון.
$\Delta \tau _{xy}^{k}$, הוא כמות הפרומון שהופרש על ידי הנמלה $k$.
בדומה לבעיית הסוכן הנוסע (TSP) על ידי:

$\Delta \tau _{xy}^{k}={\begin{cases}Q/L_{k}&{\mbox{if ant }}k{\mbox{ uses curve }}xy{\mbox{ in its tour}}\\0&{\mbox{otherwise}}\end{cases}}$

כאשר:
$L_{k}$, הוא עלות הסיור של נמלה $k$.
$Q$, הוא קבוע.

יישומים

אלגוריתמי אופטימיזציה מבוסס תבונת נמלים, יושמו לבעיות אופטימיזציה קומבינטריות רבות, החל מבעיות ריבועיות ועד לניתוב כלי רכב. בנוסף, יושמו לבעיות דינאמיות, בעיות אקראיות ויישומים מקביליים. יישום זה מאפשר פתרון כמעט אופטימאלי לבעיית הסוכן הנוסע. לאלגוריתם קיים יתרון על פני הגישות Simulated Annealing ו Genetic Algorithm עם בעיות דומות, כאשר הגרף עשוי להיות דינאמי. אלגוריתם אופטימיזציה מבוסס תבונת נמלים ניתן להפעיל באופן רציף ומסתגל לשינויים בזמן אמת (כמו למשל ניתובי רשת ומערכת תחבורה עירונית).
האלגוריתם הראשון נקרא מערכת נמלים ( Ant System ) ומטרתו היתה לפתור את בעיית הסוכן הנוסע במטרה למצוא את הנתיב הקצר ביותר למסלול נסיעה בין ערים. האלגוריתם הכללי יחסית פשוט ומתבסס על סדרה של נמלים, בכל שלב על הנמלה לבחור את הצעד הבא שלה בהתאם לחוקים הבאים:

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

קושי בהבחנה

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

יתרונות האלגוריתם

1. מאפשר לפתור בעיות NP (מחלקת סיבוכיות) בזמן סביר.
2. מכוון חיפוש רנדומלי- מאפשר איזון בין סריקות חדשות לידע הקיים.
3. נותן משוב חיובי עבור פתרונות טובים, ונותן משוב שלילי עבור פתרונות לא יעילים.
4. פתרון מתכנס.
5. אופטימאלי גם במקרה והפתרון לא נכון לחלוטין.
6. לא כל נמלה חייבת להשלים פתרון מדויק.

חסרונות האלגוריתם

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

קישורים חיצוניים

• Ant Colony Optimization Home Page
• AntSim - Simulation of Ant Colony Algorithms
• MIDACO-Solver General purpose optimization software based on ant colony optimization (Matlab, Excel, C/C++, Fortran and Python)
• Ant Farm Simulator