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

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

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

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

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

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

 procedure ACO_MetaHeuristic
 while(not_termination)
 generateSolutions()
 daemonActions()
 pheromoneUpdate()
 end while
 end procedure

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

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