נמלים שכללו את שיטות הניווט שלהן למציאת אוכל. כיום אנו יודעים להשתמש בשיטות שלהן כדי לפתור בעיות מתמטיות וחישוביות סבוכות
נמלים הן יצורים קטנים ומופלאים. בילדותי נהגתי לעצור ולהתבונן בנמלים שעות ארוכות, ובהמשך השתמשתי בהן בעבודת המאסטר שלי במדעי המחשב. מה הקשר, תשאלו? תמצאו אותו בפתגם המוכר שכתב שלמה המלך בספר משלי (ו, ו-ז): לֵךְ-אֶל-נְמָלָה עָצֵל רְאֵה דְרָכֶיהָ וַחֲכָם. אֲשֶׁר אֵין לָהּ קָצִין שֹׁטֵר וּמֹשֵׁל". המשפט הזה מתאר במדויק את הפוטנציאל האלגוריתמי שזיהה מרקו דוריגו בעבודת הדוקטורט שלו במדעי המחשב. מאז זכתה השיטה שפיתח להצלחה רבה בתחום האופטימיזציה ההסתברותית.
לֵךְ-אֶל-נְמָלָה עָצֵל
נמלה היא חרק ממשפחת הדבוראים (הכוללת גם דבורים וצרעות), שהתפתח מהצרעות לפני כ-140 מיליון שנה. יש יותר מ-10,000 מינים של נמלים, והן מהוות מעל 15 אחוז מהמסה הכוללת של חיות יבשתיות בכדור הארץ.
אחת הסיבות להצלחתן הגדולה של הנמלים היא שיתוף הפעולה בין הפרטים, שמשרתים מטרה גדולה מזאת של כל אחד מהם בנפרד – טובת הקן. מכיוון שאנו מתמקדים באלגוריתם שמחקה את התנהגותן של הנמלים, לא נתייחס לשאלה הביולוגית-פילוסופית המורכבת – האם הנמלים באמת מעדיפות את טובת הקן על טובתן העצמית, או שפעולותיהן רק נראות לנו כך. אפשר להתייחס לקן נמלים כמעין ישות בפני עצמה, מוח אחד בעל גופים רבים. לעיתים קוראים לתופעה הזאת "מולטי-אורגניזם".
ה"קן" מסוגל לעשות דברים מופלאים, הרבה מעבר ליכולות של נמלה אחת. הוא מדגים בכך את תופעת "חוכמת הנחיל", שבה כל פרט בקבוצה מסוימת תורם חלק קטן, ונהנה מיכולותיו של המולטי-אורגניזם שאליו הוא שייך. דוגמא נוספת לכך היא להקת דגים. אחת ההשערות לסיבה לכך שהדגים שוחים יחד, היא שהלהקה מסוגלת לזהות טורף המגיע ממגוון זוויות, בשעה שדג בודד מוגבל לטווח הראייה הפרטי שלו. ברגע שהלהקה מזהה טורף, המידע עובר במהירות בין פרטיה, וכך הם נהנים מטווח ראייה מועצם.
רְאֵה דְרָכֶיהָ וַחֲכָם
אנו נתמקד באספקט אחד של חוכמתו של קן הנמלים: מציאת אוכל. כולנו יודעים, לצערנו, שנמלים יודעות למצוא בקלות את הדרך אל האוכל שהשארנו בחוץ. ולא רק זה – בדרך כלל נראה אותן הולכות במסלול שהוא, אם לא הקצר והיעיל ביותר, לפחות קרוב מאוד לכך. אך איך הן מוצאות את הדרך הזאת כל כך מהר? האם הן מדברות זו עם זו ומוסרות את המידע הנחוץ? ואולי יש להן חוש ריח טוב במיוחד?
מתברר שהתשובה אכן קשורה לריח, אך מעט יותר מורכבת. בשנת 1959 פיתח הזואולוג הצרפתי פייר-פול גראסה (Grassé) תיאורייה שניסתה להסביר את התנהגותם של טרמיטים על בסיס תקשורת בלתי ישירה באמצעות הסביבה. טרמיטים הם אמנם מסדרת חרקים אחרת ואינם קרובים אבולוציונית במיוחד לנמלים, אך גם הן מתקשרות בדרך עקיפות על ידי הסביבה.
מתברר שנמלים משאירות על השביל שבו הן הולכות פרומונים, כלומר חומרים כימיים שמעוררים תגובה אצל חברותיהן הנמלים. כשנמלה נתקלת במקרה באוכל, היא תחזור לקן ותשאיר פרומונים בדרכה. ככל שהאוכל קרוב יותר, יותר נמלים יספיקו להגיע אליו ולחזור, אפילו אם הן הולכות באופן אקראי לגמרי. וכך, ככל שעובר הזמן יצטברו על הדרך לאוכל יותר ויותר פרומונים, שיהפכו אותה לדרך ברירת המחדל שלהן. כשנמלה מריחה כמות חזקה של פרומונים, היא תעקוב אחרי הריח וכך תמצא את האוכל, ובתוך זאת תחזק אף יותר את הפרומונים הנמצאים על הדרך.
שמה של התיאוריה שפיתח גראסה הוא סטיגמרגיה (Stigmergy), מושג שמשלב שתי מילים ביוונית: סטיגמה (סימן) ואֵרגוֹן (עבודה או פעולה). כלומר מדובר באות כימי על הקרקע שמוביל את הנמלים לפעולה.
נמלים משאירות פרומונים על השביל שבו הן הולכות. אדם מתבונן בנמלה על עלה עשב | Science Photo Library
אֲשֶׁר אֵין לָהּ קָצִין שֹׁטֵר וּמֹשֵׁל
ראינו אם כן שלנמלים יש דרך מיוחדת למצוא את הפתרון הטוב ביותר, או לפחות הטוב ביותר מתוך קבוצת פתרונות קרובים לבעיה שמעסיקה אותן: מציאת הדרך הקצרה ביותר אל האוכל. עם זאת, לפי המודל הזה הנמלים אינן מתקשרות בינן לבין עצמן באופן ישיר, אלא רק בעקיפין, על ידי הרחת הפרומונים שהושארו על הדרך. כלומר הן מוצאות את הפתרון הזה ללא הדרכה וללא הכוונה מלמעלה.
בנוסף, נמלה שמצאה מסלול מוצלח לא יודעת את זה בהכרח, ולא מסמנת אותו בצורה שונה מנמלה שמצאה מסלול לא מוצלח. האופטימיזציה מגיעה מעבודה קהילתית ואקראית למחצה, המתכנסת בסופו של דבר למסלול מוצלח למדי.
בעיית הסוכן הנוסע
כעת, נעשה מעבר חד לבעיה אנושית שקשורה למציאת דרכים קצרות: בעיית הסוכן הנוסע, אחת הבעיות הקלאסיות הנחקרות במדעי המחשב. בבעיה זו, לסוכן שעובר מדלת לדלת יש משימה - הוא צריך לעבור במספר נתון של ערים ולנסות למכור את מרכולתו, בלי לעבור בשום עיר יותר מפעם אחת. יש לו מפה ובה המרחקים בין כל עיר לעיר, והוא צריך לבחור את המסלול הקצר ביותר שיעבור בכולן.
הבעיה הזאת קלה כשיש שלוש או ארבע ערים, אך ככל שמספר הערים במסלול עולה, מספר המסלולים האפשריים מזנק במהירות. מספר האפשרויות למסלול שיעבור ב-15 ערים שונות, למשל, הוא יותר ממיליארד מיליון – מספר של 15 ספרות ויותר!
הבעיה הזאת היא חלק מקבוצת בעיות מתמטיות שנקראות בעיות NPC, ונחשבת לאחת הבעיות הבסיסיות ביותר במדעי המחשב. דוריגו מצא דרך לפתור אותה באמצעות נמלים מלאכותיות. כדי להבין את זה, דמיינו סוכן דמוי נמלה עם חליפה ומגבעת. הסוכן-נמלה צריך לבחור את העיר הבאה בכל צעד, ולבקר בכל עיר פעם אחת בדיוק.
בסימולציה של דוריגו, בכל סיבוב יוצאת לדרך קבוצה של סוכני נמלים. ככל שהעיר רחוקה יותר, הסיכוי שסוכן יבחר אותה קטן יותר. עם זאת, ככל שיש יותר פרומונים על הדרך בין שתי ערים, הסיכוי שהסוכן-נמלה יבחר בעיר הזאת גדל. צורת הפקת הפרומונים שונה מעט מזאת של הנמלים, שכן לסוכנים ממוחשבים יש יתרון – הם יודעים מה אורך המסלול שהם עשו, והאורך משפיע על הפרומונים שהם משאירים.
לאחר שהגיע לעיר האחרונה, הסוכן מפקיד פרומונים על כל צעד מהדרך שעבר, כך ככל שהמסלול היה קצר יותר הוא יפקיד יותר פרומונים בכל צעד מהדרך. בכל "סיבוב" כמה סוכנים עובדים במקביל, ובסופו הפרומונים מתאדים מעט (כמו שקורה בטבע) וערכם קטן. כך יוצא שככל שמשתמשים פחות במסלול מסוים, הסיכוי שישתמשו בו בעתיד נמוך יותר, ולהפך.
דוריגו אמנם פיתח את האלגוריתם שלו כדי לפתור את בעיית הסוכן הנוסע, אך האלגוריתם עצמו הוא כללי, ואפשר ליישם אותו לבעיות רבות, כל עוד אפשר לייצג אותן כמעבר בין נקודות על גרף. מאז עבודתו של דוריגו, חוקרים השתמשו בשיטת האופטימיזציה שפיתח במספר רב של תחומים, ביניהם עיבוד תמונה, קטגוריזציה, כריית מידע ואפילו שימושים בתחום הביוכימיה, כמו בעיית קיפול החלבונים.
סרטון על אלגוריתם "אופטימיזציית קן הנמלים":
