הצגת המקור של הדף "אופטימיזציית הנחיל"

'''אופטימיזציית הנחיל''' (באנגלית: Particle Swarm Optimization, או בקיצור PSO) היא שיטת [[אופטימיזציה (מתמטיקה)|אופטימיזציה]] המבוססת על התנהגות חברתית של [[נחיל]]ים{{אנ|Flocking (behavior)}} ולהקות בטבע תחת ההבחנה שכל פרט בלהקה מבסס את תנועתו על פי מידע או זיכרון שיש ברשותו לגבי נקודות עניין במרחב ועל פי מיקומם של חברים אחרים בלהקה. שיטה זו הוצגה לראשונה על ידי קנדי ואברהרט בשנת 1995 ושוכללה על ידי שיי (Shi) ב-1998. אופטימיזציית הנחיל היא שיטת אופטימיזציה מטה-[[היוריסטיקה|היוריסטית]], דהיינו לא נסמכת על תכונה כלשהי של הבעיה לפתרון אלא מספקת מנגנון כללי למציאת [[אופטימום | אופטימום לוקאלי]] של [[פונקציה | פונקציית]]  שיערוך נתונה <math>f(x)</math>.

==אלגוריתם בסיסי==
# אתחול אוכלוסיית הנחיל <math>x_1,...,x_n</math> (מרחב הפתרונות הפוטנציאלים) לערכים [[מספר אקראי|אקראיים]] במרחב החיפוש.
# לכל פרט <math>x_i</math> באוכלוסייה נקבע את <math>best_i=x_i</math> ואת מהירותו ההתחלתית <math>v_i=0</math>.
# נקבע את <math>gbest</math> כפתרון בעל הערך הטוב ביותר של פונקציית השיערוך <math>f(x)</math> מתוך <math>x_1,...,x_n</math>.
# כל עוד לא התקבל [[תנאי עצירה]] נבצע:
## נסיט כל פרט על פי המידע הלוקאלי שלו לגבי הפתרון הטוב ביותר והפתרון הגלובאלי הטוב ביותר: <math>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</math>
## נעדכן עבור כל פרט את הפתרון הלוקאלי הטוב ביותר: <math>best_i=argmax_{x_i,best_i}\{f(x)\}</math>
## נעדכן את הפתרון הגלובאלי הטוב ביותר שיש בנמצא: <math>gbest=argmax_{best_1,...,best_n}\{f(x)\}</math>
#החזר את <math>gbest</math>

כאשר:
W הוא מקדם השולט ברמת הexploration לעומת exploitation, ככל ש W קרוב ל-1 כך הנחיל נוטה להמשיך לחפש ולא להתכנס לפתרון, וככל ש W קרוב ל0 הנחיל נוטה להיכנס לפתרון ולא לחפש פתרונות טובים יותר - נהוג להגדיר את W בין 0.4 ל-0.9 כאשר אנו מקטינים את W לאורך הזמן וביחס למספר האיטרציות הכולל.
* <math>U(0,1)</math> היא פונקציה המחזירה [[מרחב וקטורי|וקטור]] במימד הפתרון שרכיביו נבחרים ב[[התפלגות אחידה רציפה|התפלגות אחידה]] מהקטע <math>(0,1)</math>.
*<math>c_1,c_2</math> הם קבועים שמווסתים את מידת הנטייה של הפתרונות בין פתרונות עצמיים מיטביים ופתרון גלובאלי מיטבי ברמת הנחיל. לרוב ניתן לקבוע <math>c_1 \approx 2, c_2 \approx 2</math>.

==ראו גם==
*[[אופטימיזציית קן הנמלים]]

==קישורים חיצוניים==
{{ויקישיתוף בשורה}}
* [http://www.swarmintelligence.org מידע] על אופטימיזציית הנחיל. {{אנגלית}}
* [http://galileo.allmag.co.il/page/679 בינת הנחיל] {{Webarchive|url=https://web.archive.org/web/20200122144944/https://allmag.co.il/ |date=2020-01-22 }} - מאמר במגזין [[גליליאו (כתב עת)|גליליאו]]

[[קטגוריה:אופטימיזציה רציפה]]
[[קטגוריה:אקולוגיה]]