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

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

אנלוגיה מעולם הנמלים[עריכת קוד מקור | עריכה]

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

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

  • Ant Colony Optimization (באנגלית)