חיפוש פיתרון לבעית הסוכן הנוסע ע"י אלגוריתם מערכת הנמלים

מוסד לימוד
מקצוע
מילות מפתח , , , , , ,
שנת הגשה 2002
מספר מילים 2968
מספר מקורות 3

תקציר העבודה

תוכן עניינים
מבוא. 2
תיאור מערכת הנמלים. 4
תיאור האלגוריתם המיושם. 7
תיאור התוכנית שכתבנו 9
ניסויים, תוצאות ומסקנות.. 12
בביליוגרפיה. 17
מבוא
מערכת הנמלים (Ant System) הינה היוריסטיקה מבוזרת לפתרון בעיות אופטימיזציה קומבינטוריות קשות. ההשראה למערכת הנמלים נבעה מהתבוננות בנמלים חיות, אשר ביכולתן למצוא את המסלול הקצר ביותר מהקן שלהן אל מקור המזון.
תופעה מעניינת היא שחיות כמעט עוורות כמו נמלים יכולות למצוא את הנתיב הקצר ביותר מהקן למקור המזון וחזרה. מחקרים בנושא העלו כי האמצעי בעזרתו מתקשרות הנמלים זו עם זו הוא כימי: הפרשות פרומונים. נמלה שנעה במרחב מסמנת את דרכה לשאר הנמלים ע"י שביל של פרומונים שהיא משאירה על הקרקע. בעוד שנמלה מבודדת נעה באקראיות, נמלה שנתקלה בשביל מסומן תזהה זאת ותחליט בסבירות גבוהה, לעקוב אחר שביל זה, ולחזק אותו בהפרשותיה היא.
צורת התנהגות זו מביאה לכך שככל שמספר רב יותר של נמלים עוקבות אחר אותו שביל, הוא נהיה יותר מושך בעיני שאר הנמלים. כלומר, הסיכויים של נמלה לבחור נתיב גדל ככל שיותר נמלים בחרו את אותו הנתיב קודם לכן.
לפרומונים תכונה חשובה נוספת, והיא שהם מתאדים לאחר שעבר פרק זמן מסויים.
תכונה זו היא שעוזרת לנמלים לאתר את המסלול הקצר ביותר: נניח שישנם שני מסלולים אפשריים מקן הנמלים אל מקור המזון, אחד קצר ואחד ארוך יותר. לנמלים הראשונות שיוצאות מהקן אותם סיכויים לבחור בין המסלולים, אך אלה שילכו לאורך השביל הקצר יגיעו מהר יותר למזון. במילים אחרות, יותר נמלים ליחידת זמן ילכו לאורך המסלול הקצר. הפרשת הפרומונים מתאדה ככל שעובר הזמן, אך מכיוון שכמות הנמלים ליחידת זמן גדולה יותר לאורך מסלול הקצר כך כמות הפרומונים ליחידת זמן גדולה יותר, ולכן יותר ויותר נמלים יבחרו במסלול זה.
  התנהגות זו מובילה לכך שמסלולים עם רמת עקבות גבוהה יותר הם המסלולים הקצרים יותר.
כדי להדגים את דרך פעולתה של מערכת הנמלים, ננסה לפתור את בעיית הסוכן-הנוסע,  Traveling Salesman Provlem  (TSP).
בבעיה זו מעוניין סוכן למצוא את המסלול הסגור הקצר ביותר שעובר דרך n ערים, מבלי לבקר באותה עיר פעמיים.