אופטימיזציית הגחלילית

אופטימיזציית הגחלילית (באנגלית: Firefly optimization) היא שיטה מטה-היוריסטית מתחום הבינה המלאכותית לאופטימיזציה של פונקציות המקבלת את השראתה מהתנהגותן של גחליליות בטבע. השיטה הוצעה על ידי קסין שי יאנג בשנת 2008, והיא שימושית בתחומים רבים, לרבות בעיבוד תמונה, תזמון תהליכים, ניתוח מבני של חלבונים, קינימטיקה הפוכה ועוד. סיבוכיות האלגוריתם היא , כאשר  הוא מספר האיטרציות שמבצע האלגוריתם.

פסאודו - קוד

Begin
Generate a random population of n fireflies x_1, x_2, ..., x_n
While (t < MaxGeneration) 
update distances
update lights intensities
update attractiveness
for i = 1 : n 
for j = 1 : n 
if (I_j > I_i), 
move firefly i to j
end if 
end for j
end for i
set s as the firefly with the optimal light intensity. 
end while 
return s as solution 
end

חלוקה אוטומטית

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

מציאת יחס התמקדות-התרחבות אופטימלי

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

דוגמה - מציאת יחס התמקדות-התרחבות אופטימלי של הילוך איזוטרופי

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

הכללה לממדים גבוהים

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

קביעת הפרמטרים

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

סיבוכיות זמן

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

הערכת ביצועים

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