אינטליגנציית נחיל (Swarm Intelligence)

חכמה בלי מנהל

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

לפי ויקיפדיה, את הצירוף טבעו ג'ררדו בני וג'ינג וואנג ב-1989, בהקשר של מערכות רובוטיות תאיות; המאמר שלהם, "Swarm Intelligence in Cellular Robotic Systems", ראה אור בקובץ מאמרים ב-1993. ויקיפדיה גם משרטטת את הגבול מול ערך שכן באתר: יישום עקרונות הנחיל על רובוטים נקרא רובוטיקת נחיל, ואילו אינטליגנציית נחיל היא משפחת האלגוריתמים הכללית יותר. הערך הזה עוסק ברעיון ובאלגוריתמים שנולדו ממנו. הרובוטים עצמם, מנחילי Kilobot ועד הוויכוח על נחילים צבאיים, מתוארים בערך רובוטיקת נחיל.

ארבע תכונות ושלושה יתרונות

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

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

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

נמלים, פרומונים וגשר כפול

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

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

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

מנמלים אמיתיות לנמלים מלאכותיות

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

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

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

ציפורים מדומות ונחיל של חלקיקים

ענף שני נולד מתנועה של להקות. ב-1986 בנה קרייג ריינולדס מודל ממוחשב של תנועה מתואמת של להקות עופות ודגים, וקרא ליצורים המדומים boids. במודל הבסיסי כל אחד מהם פועל לפי שלושה כללי היגוי בלבד: הפרדה, כלומר להתרחק משכנים צפופים מדי; יישור, כלומר לנווט לכיוון הממוצע של השכנים; ולכידות, כלומר לנוע לעבר המיקום הממוצע שלהם. הוא מגיב רק לשכנים שבטווח קטן סביבו ומתעלם מכל השאר. בניסויים המוקדמים נוספו גם הימנעות ממכשולים ותנועה לעבר מטרה. ב-1987 הוצגו בכנס SIGGRAPH גם מאמר על המודל וגם סרט קצר שנעשה בעזרתו, "Stanley and Stella in: Breaking the Ice". לפי ריינולדס, מאז היו למודל יישומים רבים בהנפשה, והראשון שבהם היה "באטמן חוזר" מ-1992: נחילי העטלפים ולהקות הפינגווינים שבו נוצרו בגרסאות מותאמות של התוכנה המקורית.

ב-1995 הציגו ג'יימס קנדי וראסל אברהארט את אופטימיזציית נחיל החלקיקים (Particle Swarm Optimization). לפי Scholarpedia, היא שאבה השראה מסימולציות של להקות, כמו זו של ריינולדס, וגם ממחקר בפסיכולוגיה חברתית: את תנועת החלקיקים אפשר לראות כמודל של אנשים שמתאימים את דעותיהם לאלה של הסובבים אותם. כל "חלקיק" הוא פתרון אפשרי לבעיה, והוא זוכר את המקום הטוב ביותר שמצא. בכל צעד המהירות שלו היא שקלול של שלושה רכיבים: המהירות הקודמת, משיכה אל המקום הטוב ביותר שמצא בעצמו, ומשיכה אל המקום הטוב ביותר שמצאו שכניו. היישום המעשי הראשון של השיטה, שדווח יחד עם האלגוריתם עצמו, היה אימון רשתות נוירונים.

ביקורת: יותר מדי מטפורות

ההצלחה של הנמלים והציפורים הולידה גל חיקויים. לפי ויקיפדיה, אלגוריתמים אבולוציוניים, אופטימיזציית נחיל חלקיקים, אבולוציה דיפרנציאלית ואופטימיזציית מושבת נמלים שולטים בתחום השיטות בהשראת הטבע, אבל מאז פורסמו שיטות "חדשות" רבות בהשראת זאבים, עטלפים, גחליליות, דבורים ובעלי חיים נוספים. ב-2013 פרסם קנת סורנסן מאמר בשם "Metaheuristics—the metaphor exposed". הוא כתב על "צונאמי של ממש" של שיטות כאלה, רובן מבוססות על מטפורה של תהליך טבעי או אנושי, וטען שהכיוון הזה "מאיים להרחיק" את התחום מקפדנות מדעית. לפי ויקיפדיה, כתב העת Journal of Heuristics עדכן בעקבות זאת את מדיניותו, והודיע שיימנע מלפרסם מאמרים שעוטפים רעיונות ישנים במטפורה חדשה.

יש גם בלבול שמות. OpenAI פרסמה מסגרת קוד בשם Swarm, שהיא עצמה תיארה כ"ניסיונית וחינוכית". לפי התיעוד שלה, היא מתמקדת בתיאום בין סוכני AI, שכל אחד מהם יכול להעביר את השיחה לסוכן אחר; ולפי דף המאגר, היא הוחלפה בינתיים ב-OpenAI Agents SDK. המגמה הזאת מתוארת בערך על המעבר למערכות רב-סוכניות.