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

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

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

1. אתחול אוכלוסיית הנחיל ${\displaystyle x_{1},...,x_{n}}$ (מרחב הפתרונות הפוטנציאלים) לערכים אקראיים במרחב החיפוש.
2. לכל פרט ${\displaystyle x_{i}}$ באוכלוסייה נקבע את ${\displaystyle best_{i}=x_{i}}$ ואת מהירותו ההתחלתית ${\displaystyle v_{i}=0}$.
3. נקבע את ${\displaystyle gbest}$ כפתרון בעל הערך הטוב ביותר של פונקציית השיערוך ${\displaystyle f(x)}$ מתוך ${\displaystyle x_{1},...,x_{n}}$.
4. כל עוד לא התקבל תנאי עצירה נבצע:
   1. נסיט כל פרט על פי המידע הלוקאלי שלו לגבי הפתרון הטוב ביותר והפתרון הגלובאלי הטוב ביותר: ${\displaystyle 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. נעדכן עבור כל פרט את הפתרון הלוקאלי הטוב ביותר: ${\displaystyle best_{i}=argmax_{x_{i},best_{i}}\{f(x)\}}$
   3. נעדכן את הפתרון הגלובאלי הטוב ביותר שיש בנמצא: ${\displaystyle gbest=argmax_{best_{1},...,best_{n}}\{f(x)\}}$
5. החזר את ${\displaystyle gbest}$

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

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

ראו גם

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

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

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

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