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

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

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

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

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

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

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

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

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

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

מקורות:

[1] תורת הגרפים

[2] גרף מגדלי האנוי

[3] אלגוריתמים אבולוציונים

[4] אופטימיזצית קן נמלים

[5] אופטימיזציה עם נמלים אמיתיות