אופטימיזציית קן הנמלים

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

אנלוגיה מעולם הנמלים

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