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

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

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

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

כאשר:

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