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

אופטימיזציית הנחיל (באנגלית: Particle Swarm Optimization, או בקיצור PSO) היא שיטת אופטימיזציה המבוססת על התנהגות חברתית של נחילים ולהקות בטבע תחת ההבחנה שכל פרט בלהקה מבסס את תנועתו על פי מידע או זיכרון שיש ברשותו לגבי נקודות עניין במרחב ועל פי מיקומם של חברים אחרים בלהקה. שיטה זו הוצגה לראשונה על ידי קנדי ואברהרט בשנת 1995 ושוכללה על ידי שיי (Shi) ב-1998. אופטימיזציית הנחיל היא שיטת אופטימיזציה מטה-היוריסטית, דהיינו לא נסמכת על תכונה כלשהי של הבעיה לפתרון אלא מספקת מנגנון כללי למציאת אופטימום לוקאלי של פונקציית שיערוך נתונה $f(x)$.

אלגוריתם בסיסי

1. אתחול אוכלוסיית הנחיל $x_{1},...,x_{n}$ (מרחב הפתרונות הפוטנציאלים) לערכים אקראיים במרחב החיפוש.
2. לכל פרט $x_{i}$ באוכלוסייה נקבע את $best_{i}=x_{i}$ ואת מהירותו ההתחלתית $v_{i}=0$.
3. נקבע את $gbest$ כפתרון בעל הערך הטוב ביותר של פונקציית השיערוך $f(x)$ מתוך $x_{1},...,x_{n}$.
4. כל עוד לא התקבל תנאי עצירה נבצע:
   1. נסיט כל פרט על פי המידע הלוקאלי שלו לגבי הפתרון הטוב ביותר והפתרון הגלובאלי הטוב ביותר: $v_{i}=W*v_{i}+c_{1}*U(0,1)*(best_{i}-x_{i})+c_{2}*U(0,1)*(gbest-x_{i});x_{i}=x_{i}+v_{i}$
   2. נעדכן עבור כל פרט את הפתרון הלוקאלי הטוב ביותר: $best_{i}=argmax_{x_{i},best_{i}}\{f(x)\}$
   3. נעדכן את הפתרון הגלובאלי הטוב ביותר שיש בנמצא: $gbest=argmax_{best_{1},...,best_{n}}\{f(x)\}$
5. החזר את $gbest$

כאשר: W הוא מקדם השולט ברמת הexploration לעומת exploitation, ככל ש W קרוב ל-1 כך הנחיל נוטה להמשיך לחפש ולא להתכנס לפתרון, וככל ש W קרוב ל0 הנחיל נוטה להיכנס לפתרון ולא לחפש פתרונות טובים יותר - נהוג להגדיר את W בין 0.4 ל-0.9 כאשר אנו מקטינים את W לאורך הזמן וביחס למספר האיטרציות הכולל.

• $U(0,1)$ היא פונקציה המחזירה וקטור במימד הפתרון שרכיביו נבחרים בהתפלגות אחידה מהקטע $(0,1)$.
• $c_{1},c_{2}$ הם קבועים שמווסתים את מידת הנטייה של הפתרונות בין פתרונות עצמיים מיטביים ופתרון גלובאלי מיטבי ברמת הנחיל. לרוב ניתן לקבוע $c_{1}\approx 2,c_{2}\approx 2$.

ראו גם

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

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

מדיה וקבצים בנושא אופטימיזציית הנחיל בוויקישיתוף

• מידע על אופטימיזציית הנחיל. (באנגלית)
• בינת הנחיל (אורכב 22.01.2020 בארכיון Wayback Machine) - מאמר במגזין גליליאו