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

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

אופטימיזצית הנחיל (באנגלית: 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=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

כאשר:

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

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]