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

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

אופטימיזציית הגחלילית (באנגלית: Firefly optimization) היא שיטה מטה-היוריסטית מתחום הבינה המלאכותית לאופטימיזציה של פונקציות המקבלת את השראתה מהתנהגותן של גחליליות בטבע. השיטה הוצעה על ידי קסין שי יאנג בשנת 2008, והיא שימושית בתחומים רבים, לרבות בעיבוד תמונה, תזמון תהליכים, ניתוח מבני של חלבונים, קינימטיקה הפוכה ועוד. סיבוכיות האלגוריתם היא , כאשר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t} הוא מספר האיטרציות שמבצע האלגוריתם.

הקדמה

בעיית אופטימיזציה

שגיאה ביצירת תמונה ממוזערת:
גחלילית מזן Photuris lucicrescens
קובץ:Postscript-viewer-shaded.png ערך מורחב – אופטימיזציה (מתמטיקה)

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

הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \begin{align} & \text{optimize} && f(x) \\ & \text{subject to} && \mathbf{x\in S} \\ \end{align} }

כאשר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \text{S}} היא קבוצת הפתרונות האפשריים לבעיה. הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s} הוא פתרון לבעיה אם ורק אם מתקיים הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s\in S} וגם הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f(x)\leq f(s)} לכל הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x\in S} .

הגחליליות בטבע

קובץ:Postscript-viewer-shaded.png ערך מורחב – גחליליות

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

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

האלגוריתם

תיאור

בהינתן מספר איטרציות מרבי הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t_{max}} , ניתן לתאר את האלגוריתם בצורה הכללית הבאה:

  1. אתחל אוכלוסייה אקראית הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x_1,...,x_n} של גחליליות על פני פונקציית מטרה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f(x)} ב- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle d} ממדים, כאשר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f(x_i)} היא עוצמת ההארה של גחלילית הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x_i} .
  2. לכל זוג גחליליות הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x_i, x_j} , אם גחלילית הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x_i} בהירה יותר מגחלילית הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x_j} , הזז את גחלילית הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x_j} לכיוון גחלילית הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x_i} על פי משוואת התנועה: כאשר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t} מייצג נקודה בזמן, הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ x_i, x_j} הן מיקום הגחליליות הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle i,j} בהתאמה, הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \alpha_t } הוא מקדם אקראיות ו- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{\epsilon}_t } הוא וקטור מספרים אקראיים המתפלגים נורמלית בזמן הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t} . אחרת, הזז את הגחלילית הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x_j} באופן אקראי.
  3. עדכן את תאורת הגחליליות ואת מידת המשיכה בין הגחליליות ע"פ המיקומים והמרחקים החדשים שהתקבלו.
  4. חזור על שלבים (2) ו- (3) למשך הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t_{max}} פעמים. בסיום, הגחלילית המוארת ביותר היא קירוב לפתרון הבעיה.

בבעיות למציאת מקסימום, יתקיים הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle I \propto f(\mathbf{x})} ובבעיות למציאת מינימום יתקיים הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle I \propto f^{-1}(x)} .

פסאודו - קוד

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

רקע תאורטי

מודל מתמטי

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

  1. כל גחלילית נמשכת לגחליליות אחרות, ללא קשר למינן.
  2. מידת המשיכה של גחלילית הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a} כלפי גחלילית היא ביחס ישר למידת ההארה של גחלילית הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b} (אנלוגיה להתנהגותן הטבעית של הגחליליות).
  3. עוצמת האור שגחלילית הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a} קולטת מגחלילית הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b} היא ביחס הפוך למרחק בין גחלילית הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a} לבין גחלילית הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b} (אנלוגיה לחוק ריבוע המרחק ההופכי, לפיו עוצמת האור נחלשת ביחס ריבועי הפוך למרחק ממקור האור).
  4. עוצמת ההארה של הגחלילית נקבעת ע"פ ערכה של פונקציית המטרה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f(x)} .

על פי תכונות (2) ו- (3), ניתן לגזור את משוואת המשיכה בין שתי גחליליות, כפונקציה מעריכית של המרחק ביניהן: הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \beta = \beta_0e^{-\gamma r^2}} כאשר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \beta_0} הוא קבוע, הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \gamma} הוא מקדם התפשטות האור באוויר, הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \beta} היא עוצמת המשיכה בין שתי גחליליות ו- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle r} הוא המרחק הגאומטרי בין שתי הגחליליות. תנועתה של גחלילית מושפעת מגחלילית בהירה יותר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle j} באופן הבא:

כאשר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t} מייצג נקודה בזמן, הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ x_i, x_j} הן מיקום הגחליליות הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle i,j} בהתאמה, הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \alpha_t } הוא מקדם אקראיות ו- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{\epsilon}_t } הוא וקטור מספרים אקראיים המתפלגים נורמלית בזמן הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t} . עבור הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \beta_0=0} מתקבלת תנועה אקראית פשוטה, ועבור הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \gamma=0} מתקבלת משוואת תנועת חלקיקים של אופטימיזציית הנחיל.

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

במקרים רבים, אלגוריתם הגחליליות יעיל יותר מאלגוריתמים רבים אחרים מתחום בינת הנחיל. סיבה עיקרית לכך היא תופעת החלוקה האוטומטית. האלגוריתם מבוסס על כך שאטרקטיביות של פתרון פוחתת עם עליית המרחק, ולכן, נוצר מצב שבו האוכלוסייה מופרדת באופן אוטומטי לתתי-קבוצות, כאשר כל תת-קבוצה מרוכזת סביב אופטימום מקומי שונה. עבור אוכלוסייה הגדולה מאד ממספר מוקדי האופטימום המקומיים, חלוקה זו מאפשרת למצוא את כל המוקדים המקומיים בו-זמנית. מבחינה מתמטית, הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {\sqrt{\gamma}}^{-1} } מאפיין את המרחק הממוצע בין שתי קבוצות גחליליות סמוכות. מכאן, כל אוכלוסייה נחלקת לתתי קבוצות סמוכות בעלות מרחק ממוצע קבוע. עובדה זו מאפשרת התמודדות עם בעיות שאינן לינאריות.

גרף של פונקציה 4-קוטבית

קל לזהות את תופעת החלוקה האוטומטית בהרצת האלגוריתם על הפונקציה התלת-מימדית הבאה:

הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f(x,y)=e^{-x^{2}-y^{2}}({\left | x \right |}+{\left | y \right |})}

לפונקציה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f(x,y)} ישנן ארבע נקודות מקסימום הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (\pm 0.5 , \pm 0.5)} . האלגוריתם מאפשר את מציאת הקטבים על ידי הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 25} גחליליות ו- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 20} איטרציות. הסכימה הבאה מתארת את מיקומן האקראי של הגחליליות (כנקודות) בתחילתה של ריצת האלגוריתם (משמאל) ואת מיקומן בסיום ריצת האלגוריתם:

גרף של פונקציית רוזנברוק עבור n=2.

התמקדות כנגד התרחבות

רעיון כללי

שני המרכיבים העיקריים בכל שיטה מטה-היוריסטית הם התמקדות והתרחבות.

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

אלגוריתם המחלק את פעולתו להתמקדות והתרחבות נקרא אלגוריתם חיפוש-לסירוגין. רמות ההתמקדות וההתרחבות של האלגוריתם, וכמו כן מידת האיזון בין שני המרכיבים, נקבעות על ידי מידת האקראיות וערכי הפרמטרים. יעילותו ודיוקו של האלגוריתם תלוי ביחס ההתמקדות-התרחבות הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Q} :

הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Q=\frac{\tau_a}{\tau_b}}

כאשר הפענוח נכשל (שגיאת המרה. השרת ("https://en.wikipedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle \tau _{a}} ו- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \tau_b} הם פרקי הזמן המנוצלים לתהליך ההתמקדות ולתהליך ההתרחבות, בהתאמה.

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

חשיבותו של יחס התמקדות-התרחבות מוביל לפיתוח המודל התאורטי הבא, עבור המקרים הדו-ממדיים והתלת-ממדיים: אלגוריתם חיפוש המתמקד במרחב פתרונות קטן בעל רדיוס הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a} הנמצא במרחב פתרונות שרדיוסו הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b} , כאשר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a\ll b} , ניתן למידול על ידי תהליך דיפוזיבי איטי המתואר על ידי מערכת המשוואות הסטוכסטיות הדיפרנציאליות הבאות:

הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left\{\begin{matrix} D\nabla_r^2t_1+\frac{1}{2 \pi \tau_a } \int_{0}^{2 \pi}\left [ t_2(r)-t_1(r) \right ]d \theta +1 =0 \\ \\ u\nabla_rt_2(r)-\frac{1}{\tau_b }\left [ r_2(r)-t_1(r) \right ] + 1 =0 \end{matrix}\right.}

כאשר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle D} הוא קבוע הדיפוזיה, הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \tau_a} ו- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \tau_b} הם תוחלות הזמן שנוצלו לתהליך ההתמקדות ולתהליך ההתרחבות, בהתאמה, הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t_1} ו- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t_2} הם תוחלות זמני ההגעה למטרה בתהליך ההתמקדות ובתהליך ההתרחבות, בהתאמה, ו- הוא קצב החיפוש הממוצע. תחת ההנחה שקצב החיפוש הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle u } זהה בכל הצעדים, פרק הזמן המינימלי הדרוש לכל אחד מהשלבים הוא:

הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \tau_{a}^{\mathrm{min}}\approx \frac{D}{2u^2}\cdot \frac{\ln^2\frac{b}{a}}{2\ln\frac{b}{a}-1} \quad \quad \tau_{b}^{\mathrm{min}}\approx \frac{a}{u}\sqrt{\ln\frac{b}{a}-\frac{1}{2}}}

כאשר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle u\rightarrow \infty } , מתקבל יחס ההתמקדות-התרחבות האופטימלי:

הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (1) \quad Q_{\mathrm{optimal}}=\frac{\tau_a}{\tau_b^2} \approx \frac{D}{a^2}\frac{1}{\left [ 2- \frac{1}{\ln{\frac{b}{a}}} \right ]^2} }

התוצאות לעיל קבילות עבור המקרה הדו-מימדי, ושלא קיימות תוצאות כלליות עבור יותר מ-3 ממדים.

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

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

הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle D\approx \frac {s^2} {2}}

כאשר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle D} הוא קבוע הדיפוזיה ו-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s} הוא אורך הצעד של המהלך בכל איטרציה. במקרה שבו הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b / a\rightarrow \infty } נקבל מתוצאה (1):

הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Q_{\mathrm{optimal}}=\frac{\tau_a}{\tau_b^2}\approx \frac{1}{8}}

מכאן ניתן להסיק שבמקרה זה, יש להשקיע זמן רב יותר בשלב ההתרחבות מאשר בשלב ההתמקדות.

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

גרף של גל הרמוני העומד על דיסק

נדגים את חישוב יחס ההתמקדות-התרחבות במקרה של פונקציית גל-עומד:

הפענוח נכשל (שגיאת המרה. השרת ("https://en.wikipedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle f(x)=1+\left\{\exp \left[-\sum _{i=1}^{d}\left({\frac {x_{i}}{\beta }}\right)^{10}\right]-2\exp \left[-\sum _{i=1}^{d}\left(x_{i}-\pi \right)^{2}\right]\right\}\cdot \prod _{i=1}^{d}\cos ^{2}x_{i}}

פונקציה זו מאופיינת במספר גדול של נקודות קיצון מקומיות, ובעלת מינימום גלובלית יחידה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f_{\mathrm {min}}=0} בנקודה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (\pi,\pi,\dots,\pi)} בתחום הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle -20\leq x_i \leq 20} כאשר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle i=1,2, \dots ,d} ו- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \beta = 15} . נקבע ש- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \alpha = \pi/2} , ומכיוון ש- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b=20} , נובע ש- , ועבור הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle d=2} נקבל:

הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Q_{\mathrm {optimal}} \approx \frac{1}{2\left [ 2-\ln\left ( \frac{b}{a} \right ) \right ]^2} \approx 0.19}

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

הטבלה הבאה מתארת רצף של חמישה ניסויים, בהם מופעל אלגוריתם הגחליליות למציאת מינימום עבור פונקציית גל-עומד, כאשר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n=15} , הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t=1000} , הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x \in [-20,20]^n} , הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \beta = 15} ו- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Q} משתנה.

השוואה של ביצועי אלגוריתם הגחליליות מול האלגוריתם של בניצ'ו אטאל, עבור מספר ממדים משתנה.
הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Q} הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 0.4} הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 0.3} הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 0.2} הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 0.1} הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 0.05}
תוצאה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 9.4e-11} הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 9.4e-11} הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 9.4e-11} הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 9.4e-11} הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 9.4e-11}

קל להבחין שהתוצאה המדויקת ביותר מתקבלת כאשר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Q=0.2} - הבחנה אמפירית המתלכדת עם הטענה התאורטית.

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

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

הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac{\tau_a}{\tau_b^2} \sim O\left ( \frac{D}{a^2} \right ) \quad \quad \tau_m \sim O\left ( \frac{b}{u}\left ( \frac{b}{a} \right )^{d-1} \right )}

כאשר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \tau_m} הוא זמן החיפוש הכולל הממוצע. הודגם אמפירית כי בממדים גבוהים, אלגוריתם הגחליליות יעיל בהרבה מן האלגוריתם הנ"ל, אך לא נמצא מודל תאורטי המסביר את תוצאות הניסוי.

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

מקדם האקראיות הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \alpha_t } מווסת את מידת האקראיות של מהלכי הגחליליות. כיוון שהפחתה הדרגתית של מידת האקראיות תאפשר מניעה של התכנסות לאופטימום מקומי, התכנסות מהירה תתקבל עבור הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \alpha_t=a_0 \delta^t}

כאשר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \delta\in[0,1]} ו- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_0} הוא מקדם אקראיות התחלתי. סימולציות מראות שהתכנסות יעילה במיוחד מתקבלת עבור הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \gamma=1/\sqrt{L}} , הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n\in[25,40] } , הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_0=0.01L } , כאשר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle L} הוא סדר הגודל הממוצע של פתרונות הבעיה.

סיבוכיות זמן

סיבוכיות האלגוריתם היא הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle O(n^{2}t)} , כאשר הוא מספר האיטרציות ו- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n} הוא מספר הגחליליות. עבור הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n} גדול יחסית, ניתן להחליף את הלולאה הכפולה בלולאה יחידה, ולמיין את מידת המשיכה של הגחליליות באמצעות אלגוריתם מיון השוואתי. במקרה זה, סיבוכיות האלגוריתם היא הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle O(nt\log{n})} . בשני המקרים, הסיבוכיות לינארית ב- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t} .

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

להלן מספר האיטרציות שנדרשו לפתרון בעיות אופטימיזציה עבור שלוש פונקציות מרכזיות, בטווח נתון, וכתלות במספר הממדים של הפונקציה (הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n} ).

פונקציית ספירה (Sphere function)

גרף של פונקציית ספירה עבור n=2.

הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \textrm{Sphere}(\boldsymbol{x}) = \sum_{i=1}^{n} x_{i}^{2} \quad\quad [-100,100]^n}

הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n} מינימום מקסימום
15 6239 6440
30 6202 6452
60 6149 6398

פונקציית אקליי (Ackley function)

גרף של פונקציית אקליי עבור n=2.

הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \textrm{Ackley}(\boldsymbol{x}) =-20 \exp \left [ -\frac{1}{5}\sqrt{\frac{1}{n}\sum_{i=1}^{n}{x_{i}^{2}}} \right ]- \exp \left [ \frac{1}{n} \sum_{i=1}^{n}{\cos (2\pi x_i)} \right]+20+e\quad\quad [-30,30]^n}

הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n}

מינימום

מקסימום

15 1720 2176
30 1568 1805
60 1402 1862

פונקציית רוזנברוק

גרף של פונקציית רוזנברוק עבור n=2.

הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \textrm{Rosenbrock}(\boldsymbol{x}) = \sum_{i=1}^{n-1} \left[ 100 \left(x_{i+1} - x_{i}^{2}\right)^{2} + \left(x_{i} - 1\right)^{2}\right]\quad\quad [-30,30]^n}

מינימום

מקסימום

15 2497 2938
30 2531 2653
60 2471 2574

שימושים עיקריים

ראו גם

לקריאה נוספת

  1. Yang, X. S. (2008). Nature-Inspired Metaheuristic Algorithms. Frome: Luniver Press. ISBN 1-905986-10-6
  2. Yang, X. S. (2009). "Firefly algorithms for multimodal optimization". Stochastic Algorithms: Foundations and Applications, SAGA 2009. Lecture Notes in Computer Sciences 5792. pp. 169–178. arXiv:1003.1466.

קישורים חיצוניים