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

מתוך המכלול, האנציקלופדיה היהודית
(הופנה מהדף אופטימיזצית הנחיל)
קפיצה לניווט קפיצה לחיפוש

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

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

  1. אתחל את אוכלוסיית הנחיל הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x_1,...,x_n} (מרחב הפתרונות הפוטנציאלים) לערכים אקראיים במרחב החיפוש.
  2. לכל פרט באוכלוסייה קבע את הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle best_i=x_i} ואת מהירותו ההתחלתית הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v_i=0} .
  3. קבע את הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle gbest} כפתרון בעל הערך הטוב ביותר של פונקציית השיערוך הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f(x)} מתוך הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x_1,...,x_n} .
  4. כל עוד לא התקבל תנאי עצירה בצע:
    1. הסט כל פרט על פי המידע הלוקאלי שלו לגבי הפתרון הטוב ביותר והפתרון הגלובאלי הטוב ביותר: הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 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. עדכן עבור כל פרט את הפתרון הלוקאלי הטוב ביותר: הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle best_i=argmax_{x_i,best_i}\{f(x)\}}
    3. עדכן את הפתרון הגלובאלי הטוב ביותר שיש בנמצא: הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle gbest=argmax_{best_1,...,best_n}\{f(x)\}}
  5. החזר את

כאשר:

  • הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle U(0,1)} היא פונקציה המחזירה וקטור במימד הפתרון שרכיביו נבחרים בהתפלגות אחידה מהקטע הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (0,1)} .
  • הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_1,c_2} הם קבועים שמווסתים את מידת הנטייה של הפתרונות בין פתרונות עצמיים מיטביים ופתרון גלובאלי מיטבי ברמת הנחיל. לרוב ניתן לקבוע הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_1 \approx 2, c_2 \approx 2} .

ראו גם

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

ויקישיתוף ראו מדיה וקבצים בנושא זה בוויקישיתוף.

סמל המכלול גמרא 2.PNG
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0