שימוש באלגוריתם של האבקת פרחים משולב בשיטת למידה מאונכת ובמנגנון “אפקט השפמנון” לפתרון בעיות מיטוב כלליות

מילות מפתח: אלגוריתם של האבקת פרחים (  Flower Pollination Algorithm, FPA); למידה מאונכת (Orthogonal Learning, OL); מערך  מאונך (Orthogonal Array, OA);  מנגנון “אפקט השפמנון (Catfish Effect Mechanism); בעיות מיטוב כלליות (Global Optimization Problems);   OCFPA       

תקציר

FPA הוא שיטת מיטוב חדשנית המבוססת על התנהגויות של פרחים בשעת האבקתם. אולם יש חסרונות המגבילים את שימושה לפתרון בעיות הנדסיות, כגון נטייה להתכנסות מוקדמת  (Premature convergence)  ויכולת ניצול (exploitation) מוגבלת. אפשר לשפר את יכולת המיטוב של האלגוריתם, יש לשלב במפעיל (operator) ההאבקה המקומי שיטת למידה מאונכת (OL) המבוססת על תכנון ניסוי מאונך (OED). ה-OED יכול לנבא את הצירוף המיטבי של רמות הגורמים ע”י בניית קבוצת מבחן קטנה אך מייצגת על יסוד מערך מאונך. התכונות האלה של ה-OED מאפשרת ל-OL להפיק פתרון מבטיח מכמה מקורות של מידע נסיוני, המכוונים את האוכלוסייה לחפש פתרון בכיוון הגיוני אפשרי. כמו כן, היא מתמקדת באמצעות מנגנון “אפקט השפמנון”, על הפרטים הגרועים ביותר בתהליך האיטרציה. המנגנון הזה בוחן מידע חדש בעל ערך ושומר על מגוון עדיף של האוכלוסייה. תוצאות הניסוי בפונקציות הבחינה (benchmark functions) מוכיחות שהאלגוריתם משפר במידה ניכרת את ביצועי ה-FPA  המקורי וכושר התחרות שלו גדול מזה של כמה אלגוריתמים משוכללים.

1.    מבוא

המדע המודרני מציב אתגרים גדולים בפני שיטות המיטוב המקובלות, כי מאפייני בעיות המיטוב לא-רציפים, לא-לינאריים, מרובי משתנים בלתי תלויים (multivariate) או בלתי קמורים (nonconvex). האלגוריתמים  הנוכחיים של אינטליגנציית הנחיל (Swarm intelligence) הם דרכים יעילות לפתרון בעיות מיטוב מורכבות. רוב האלגוריתמים האלה פותחו כחיקוי של דפוסי חיפוש מזון או נדידה של בעלי חיים, או על יסוד תורת האבולוציה. כאלו הם

1.    האלגוריתם הגנטי (GA);

2.    מיטוב נחיל החלקיקים (PSO);

3.    האבולוציה הדיפרנציאלית (DE);    

4.    האלגוריתם של דילוג הצפרדע המבולבל (SFLA)

5.    מיטוב מבוסס על ביו-גיאוגרפיה (BBO)

6.    חיפוש קוקייה (CS);

7.    אלגוריתם של כינוס קריל (KH);

8.    המיטוב של זבוב הפירות (FFO);

9.    מיטוב בהשראת מסלול היונה (PIO)

10.          מיטוב בשיטת העשב הפולש (IWO)

11.          אלגוריתם העטלף (BA)

ה- FPAהוא אלגוריתם הוריסטי חדשני שנוצר בהשראת התנהגות הפרחים בשעת ההאבקה.  האבקת ה פרחים בטבע מתבצעת בשתי דרכים: האבקה עצמית והאבקה זרה. האבקה זרה מתבצעת בעזרת ציפורים וחרקים המעבירים אבקה לפרחים של צמחים רחוקים. האבקה עצמית מתבצעת בעזרת הרוח, אך ורק בין פרחים סמוכים של אותו צמח. לכן, ה-FPA נוצר באמצעות העתקת שיטת ההאבקה הזרה למאביקים כלליים ואת שיטת ההאבקה העצמית למאביקים מקומיים. האלגוריתם עורר עניין רב בזכות עקרונותיו הפשוטים, תנאיו המעטים וקלות הפעלתו.

אולם גם ה-FPA, כמו שאר האלגוריתמים של אינטליגנצית הנחיל, אינו מסוגל ליצור פשה מושלמת בין הניצול הכללי והמקומי. לכן הוצעו כמה שיטות להגברת יכולת החיפוש של ה-FPA. נאביל צירף את מנגנון ברירת השיבוט (Clone Selection mdechanism) למאביקים המקומיים כדי להגיע לפתרונות מדויקים יותר. הואנג ושות’ שילבו בין מפעילי המוטציה, ההכלאה, והבריכה הטבעית ב-DE כתחליף לשיטת העדכון המקורית של ההאבקה המקומית. ז’ו ושות’ פיתחו את מנגנון התנגדות העילית (Elite Opposition Mechanism), את שיטת התאמה-העצמית החמדנית (self-adaptive greedy strategy), ושיטת סבירות ההחלפה הדינמית  (dynamic switch probability) כדי לאזן בין החקירה (exploration) לניצול (exploitation). סולגאטרה וסינג ניתחו את השפעתן של שיטות המוטציה השונות על ביצועי ה-FPA המקורי. פונקציות המבחן הראו שלגרסאות האלה ביצועים מעולים.  כמו כן, FPA הפגין תוצאות טובות ביישומים הנדסיים נבחרים.  עבדלעזיז ושות’ נעזרו ב-FPA הבסיסי לפתרון בעיית החיסכון בייצור אנרגיה (ELD). וואנג ושות’ ערכו ניתוח אשכול באמצעות FPA המבוסס על האבקה באמצעות דבורה. ז’אנג ושות’ הציעו FPA של חיפוש כאוטי לחיזוי מהירות הרוח. שו ושות’ שילבו בין ה-FPA לתורת קבוצת הנקודה הטובה (Good point set theory) ולכללים ההיוריסטיים של דב (Deb) כדי לזהות פרמטרים באופטימיזציה של עיבוד שבבי (multipass turning). סאלגוטרה וסינג יישמו במקביל את אלגוריתם העטלף ואת ה-FPA  כדי לשלב בין מערכי האנטנה הקוויים (linear antenna arrays).

כידוע, FPA תקני פועל בשיטת הלמידה הדיפרנציאלית כדי לבצע חקירה כללית (global exploration) ולשכלל את הניצול. אולם דפוס ההתפתחות הפשוט הזה אינו יעיל בגלל כמה חסרונות: ראשית, התנהגות החיפוש האקראי כלפי הפרט הנוכחי חסרת מנגנון יעיל למניעת התכנסות מוקדמת. שנית, נוסחת העדכון פועלת על ווקטור הפתרון המלא במקום על כל מימד בנפרד, והתוצאה עלולה להיות נסיגה אחרי התקדמות ראשונית. הסיבה העיקרית לכך היא שלווקטורי פתרון שונים עשויים להיות רכיבים בעלי איכות שונה. לכן, רכיבים איכותיים עשויים לשפר את הפרט במימדים מסוימים, אבל רכיבים נחותים עלולים להביא להתנוונות במימדים אחרים.לאור זאת, ברור שהתנאים ההכרחיים לשיפור יכולת המיטוב הם השמירה על מגוון האוכלוסיה והניצול המשופר של מידע נסיוני.

ה-OED הוא כלי ניתוח אופייני של תכנית ניסוי שיכול לנבא בהצלחה את הצירוף המיטבי של רמות גורמים שונים באמצעות בחירת קבוצת מבחן קטנה יותר אך מייצגת. מידע בעל ערך עשוי להתקיים במימדים מסוימים של פתרונות אפשריים שונים. לכן, במחקר זה, פיתחנו שיטת OL בתכנית ניסוי מאונכת (OED) כדי להגיע לפתרון אפשרי מבטיח יותר מבין הפרט הנוכחי, הפרט הטוב ביותר, ופרט אקראי. כתוצאה מכך נשפר מאוד את מהירות הפתרון ואת דיוקו. אבל, למרות שה-OL יכול לייעל את המיטוב, האלגוריתם עדיין מוריד את המגוון. לכן הגברנו את גיוון האוכלוסייה באמצעות מנגנון “אפקט השפמנון” המחליף את המידע על בפרטים הגרועים ביותר במידע על מתחריהם. במהלך האיטרציה, הפרטים הגרועים ביותר מתקרבים לטובים ביותר, וברגע שהאלגוריתם מתחיל בהתכנסות המקומית, אפקט השפמנון עשוי להניע את אוכלוסיית המשנה הגרועה ביותר לחקור את מקומה החדש. כך נשמר מקוון האוכלוסייה. בקיצור, שילוב שיטת ה-OL ומנגנון אפקט השפמנון ב-FPA מבטיח את יציבות החיפוש ועשוי לשפר את הפתרון. תוצאות הניסויים הוכיחו שהאלגוריתם המוצע עדיף על ה-FPA המקורי ועל אלגוריתמים אבולוציוניים מתקדמים אחרים  שנבדקו בפונקציות מבחן.

בחלק 2 של המחקר מתוארות הבעיות של דגם המיטוב הכללי. חלק 3, מסביר בפרוטרוט את עקרונות ה-FPA. חלק 4, את ה-OL ואת מנגנון אפקט השפמנון; חלק 5, את תוצאות האלגוריתם המשולב של האבקת הפרחים ואפקט השפמנון (OCFPA). בחלק 6 מובא סיכום המסקנות.

2.    בעיות המיטוב הכללי

 בעיות הנדסיות רבות ניתן לראות כבעיות מיטוב כללי, שניתן לתאר כך:

כאשר SX היא הצורה הווקטורית של משתנה החלטה, D הוא מספר משתני ההחלטה,   f(SX)היא פונקציית המטרה, S מגדיר את מרחב החיפוש ל אלגוריתם המיטוב, _dɩ הוא הגבול התחתון (Lower) ו-u_d הוא הגבול העליון (Upper) של משתנה ההחלטה SX_d. בעיית מיטוב כללי דורשת לגלות את משתנה ההחלטה הטובה ביותר באמצעות הערך המרבי או המזערי של פונקציית המטרה.

3.אלגוריתם ההאבקה

FPA הוא אלגוריתם למיטוב כללי המבוסס על אוכלוסייה. יאנג ושות’ סיכמו את תהליך ההאבקה בארבעה כללים אידיאליים:  

1-   האבקה זרה באמצעות ציפורים וכדומה נחשבת להאבקה כללית שבה תנועת המאביקים אקראית על פי התפלגות לוי (levy flight).

2-    האבקה עצמית של פרחים קרובים נחשבת להאבקה מקומית.

3-   קביעות (constancy) הפרח נחשבת לשיעור ההתרבות, שהוא יחס הישר באותה רמה בין הפרחים המעורבים בהאבקה.

4-   האבקה כללית והאבקה מקומית מיושמות על בסיס סבירות מתחלפת.

מכלל 4 נובע ששני סוגי ההאבקה מתרחשים באקראי ובסבירות p. כלומר, אם ערך אקראי rand ב [0,1] קטן מ-p, תתקיים האבקה כללית, וכן ההיפך. תרשים הזרימה של FPA  מוצג באיור 1

4. OCFPA

4.1 תכנון הניסוי המאונך (OED)

ההנחה היא שהניסוי כולל F גורמים ולכל אחד מהם Q רמות. להשגת הצירוף הטוב ביותר של רמות בכל גורם, הערכנו בשיטה הישירה את כל הצירופים, Q^F במספר. אולם החישוב בשיטה זאת מסובך, בעיקר כששני המשתנים גדולים. אמנם בשיטת OED  ניתן להגיע לתוצאה במספר ניסויים קטן, אולם השיטה מופעלת על בסיס המערך המאונך (OA) וניתוח הגורמים (FA).

OA נוצר מטורים בסיסיים ולא-בסיסיים (nonbasic), כדוגמת משוואה 7. ממנה עולה כי יש כאן 6 גורמים (כמספר הטורים), לכל גורם 2 רמות (1 או 2), ו-8 צירופים (כמספר השורות):

אפשר להדגים את  השימוש ב OED בעזרת  המשוואה הבאה:

 R²= A²+ 2B²+3C²+4D². A, B, C, ו-D הם 4 גורמים, ולכל אחד מהם 2 רמות: A₁=2 ; B₁=8;  C₁=3 ; 1=₁D; A₂=5; B₂=3 C₂=5 ; D₂=7. תת-מערך של OA גם כן נחשב ל-OA, ולכן 4 הטורים הראשונים של L₈(2⁶) נבחרו הפעם כ-OA. בסך הכל התקבלו 8 צירופים של הרמות השונות של כל הגורמים ב-OA, והם מוצגים בטבלה 1. כולם נבדקו בעזרת נוסחת הפונקציה, ותוצאות ההערכה מוצגות בעמודה R_OA.

כאשר:

E_gk= ההשפעה הממוצעת של רמה k בגורם g;

R_i= תוצאות ההערכה של הצירוף i. כשהרמה k והגורם g, _igk=1ω. אם לא, _igk=0ω. בבעיות מיזעור, ככל ש E_gkקטן, רמה k  טובה יותר בגורם g. פעולתו של RA במקרה זה מוצגת בטבלה 2. ממנה אם בוחרים ברמה בעלת  E_gk קטן יותר, מגלים צירוף חדש: A1=2; B2=3; C1=3; D1=1, ב-FA, ותוצאות ההערכה R_FA טובות יותר מ-R_OA.

טבלה 2: ה-FA במקרה לדוגמה.

4.2 שיטת ה–OL

 למפעיל בהאבקה מקומית יש אפשרויות מוגבלות לחיפוש דיפרנצתיאלי. כדי לשפר את ביצועיו, מפעילים בשלב החיפוש המקומי את שית ה-OL המבוססת על ה-OED. זאת משום שעקרון ה-OED מאפשר ל-OL שילוב שיטתי ומושכל של מידע מועיל מפרטים שונים בכל מימד, והפעלה של פתרון איכותי שמכוון את האוכלוסייה לכיווני חיפוש מבטיחים.

לצורך מתן מידע מספיק לחיפוש, יש להפעיל את שיטת ה-OL על שלושה פרטים: ה-gbest  הנוכחי המספק מידע מתקדם להכוונה; ה- SX_i הנוכחי, ופרט שנחבר באקראי, SX_k. שני האחרונים רגילים לשתף זה את זה בנסיון החיפוש שלהם ולכך לגוון את המידע. כך יצרנו שיטת עדכון חדשנית ל- SX_i, על בסיס שיטת ה-OL, כמתואר בנוסחה הבאה:

בשיטת OL, מספר הגורם, F, תואם למספר המימדים בבעיה, D, ומספר הרמה Q של כל גורם שווה למספר הפריטים שנבחרו, כלומר 3. כשמפעילים את השיטה, הערך lv_di של רמה I (1=1,2,3) במימד d ניתן בנוסחה הבאה:

 מכאן נובע שנוצרים M פתרונות אפשריים לגורם C על סמך  L_M(3^D)של OA, כמתואר בנוסחה הבאה:

את הפתרונות האפשריים מעריכים באמצעות פונקצית מטרה מיוחדת, ומבצעים FA. שיטת OL פועלת על פי אלגוריתם 1:

01: קלט (Input)

02: מספר הגורמים (F=D) ומספר הרמות (D=3)

03: שלושה פרטים: SX_i, gbest, SX_k

04: פונקציית מטרה f(solution) לבעיות מיזעור (miminization) או השאה (maximization).

05: מספר הערכות הכשירות (Fitness Evaluations, FE)=0.

06: פלט (output)

07: תוצאות OL

08: התחל

09: בנה את ה-OA ע”פ F ו-Q.

10: חשב את המספר השלם הקטן ביותר  j  שיפתור את המשוואה

 (Q¹-1)(Q-1)=F, ואז הצב: M=Q^J

11 בנה L_M(3^D)  ב-OA על פי “אלגוריתם משופר  למיטוב של חיפוש קוקייה (Cuckoo search ) לבעיה של הערכת פרמטרים של מערכות כאוטיות”.

12 חשב את ערכה של כל רמה בכל מימד בעזרת פקודה 10.

13 לולאת  For: d=1:D

14

15 סוף לולאת For

16 צור ווקטור ל –M פתרונות  C₁,….C_m….C_M על בסיס L_M(3^D).

17 מצא את M הפתרונות לפי משוואה 11

18 הערך את M הפתרונות בעזרת פונקצית המטרה.

19 M התוצאות הן:  f(C1),…f(Cm),…f(C_M).

20 סכם את מספר הערכות הכשירות

21 Fes=Fes+M

22 בחר בפתרון הטוב ביותר ל  C_OA .

23

24 חשב את ההשפעה הממוצעת  E_dK בכל רמה k(1,2,3) של כל מימד d.

25 לולאת  For: d=1:D

26 מצא את אינדקס השורה בעלת אותה הרמה במימד d על פי OA.

27 חשב את הממוצע של תוצאות הכשירות על פי ווקטור האינדקס.

28

29

30

31 השווה בין E_d1, E_d2, ו- E_d3, ובחר ברמה המועילה ביותר k במימד d.

32 סוף לולאת For

33 בנה את  C_FA ע”י צירוף ערכי כל הרמות המועילות ביותר lv_dk

34 השווה בין C_OA ל-C_FA, ובחר את הטוב מביניהם לתוצאת OL.

35. סיים.

מפעולות 16 עד 25 עולה כי כל הפעלה של OL מגדילה את מספר הערכות הכשירות M. בבעיה בת 30 ממדים, למשל, כשמפעילים את שיטת OL על 3 פרטים, מספר הפתרונות שאפשר לקבל בשיטת ה-OA ושצריך להעירך בעזרת פונקציית המטרה הוא 3⁴=81. לכן, השימוש ב-OL יסבך את החישובים. כדי להקל את החישובים בכל איטרציה, יש להפעיל את ה-OL רק כשהפתרון הנוכחי, מספר i , נכלל בהאבקה המקומית והאינדקס i שווה למספר השלם האקראי u ששייך לקבוצה {1,…NP}. כך אפשר להגדיל את יכולת הניצול המקומית תוך הפחתת השימוש בחישובים.

4.3 מנגנון אפקט השפמנון

שמה של התופעה נובע ממנהגם של הדייגים להכניס שפמנון לבריכת סרדינים, כי השמפנון מאלץ את הסרדינים לשחות במרץ כדי להינצל מטריפה. התופעה הזאת שולבה בהצלחה ב-PSO.

המנגנון הזה מופעל משמש למניעת התכנסות מוקדמת של ה-FPA, בכך שהוא  מאלץ את הפרטים הגרועים ביותר לחקור אזורים חדשים ולהגיע לפתרונות אפשריים טובים יותר. העקרון שמאחוריו הוא שאם ערך הכשירות של הפתרון הטוב ביותר הנוכחי לא גדל אחרי כמה  איטרציות ברציפות, 10% הגרועים ביותר  מאוכלוסיית “הסרדינים”, WX, יוחלפו ב”שפמנונים”, CX. כאן, הפרט “השפמנוני” הוא פתרון מתחרה לפרט ה”סרדיני”, וניתן לחשבו בנוסחה הבאה:

כאשר i       הוא האינדקס של הפרטים ה”סרדיניים”. אלגוריתם 2 ממחיש את פעולתו של המנגנון:

01: קלט

02 מספר האוכלוסייה NP, מימדי האוכלוסייה D

03 מספר האיטרציה הנוכחית t, האוכלוסייה הנבדקת באיטרציה הנוכחית SX.

04 פונקציית המטרה f(solution) לבעיות מזעור או השאה.

05 וקטור אחסון f לכשירות ההיסטורית הטובה ביותר.

06 מספר איטרציות רצופות n.

07 פלט

08 הפרטים ה”שפמנוניים” CX.

09 התחל

10 לולאת  t>n  if

11 הפרט הטוב ביותר בכלל האוכלוסייה לא השתפר במשך n איטרציות רצופות

12  אם min(f(SX)-f best (t-n)==0

13 מיין את האוכלוסייה על פי הכשירות.

14 =sort(f(SX)[ sort_f, sort_ind].

15 בחר ב 10% הגרועים ביותר על פי sort_ind והגדר אותם כ WX.

16    WX=SX(sort_ind)0.9NP+1: NP),:)

17 צור את הפרטים “השפמנוניים”, בעזרת פקודה 12.

18 לולאתFor i= 1 עד למספר ה WX

19 לולאת  For d=1:D

20 CX_id=l_d+u_d-WX_id

21 סוף לולאת For

22 סוף לולאת For

23 חשב את ערכי הכשירות  f(CX_i)

24 סוף לולאת if

25 החלף את כל הפרטים הגרועים ביותר , WX, פרטים “שפמנוניים” CX.

26 סוף לולאת if

27 סיים.

 4.4. התהליך העיקרי ב-OCFPA.השיטה נוצרה כתוצאה משילוב שיטת ה-OL ומנגנון אפקט השפמנון ב-FPA המקורי. אלגוריתם 3 מדגים במלואה את פעולת הOCFPA:

01 קלט

02 SX של אבקת פרחים.

03 פונקצית המטרה f(SX) לבעיות מיזעור או השאה.

04 מספר האבקות (NP), מספר הערכות הכשירות (FE)

05 סבירות ההחלפה (p), גורם הצעד (γ).

06 פלט

07 האבקה הטובה ביותר בכלל (gbest).

08 התחל

09 הכניס מספר אקראי של אוכלוסיית האבקות.

10 לולאת For i= 1 עד NP.

11

12 חשב ואחסן את ערך הכשירות (SX_i)f.

13 סוף לולאת For

14 בחר באבקה בעלת ערך הכשירות הגבוה ביותר לאבקה הטובה ביותר הנוכחית.

15 (לא הגענו למספר המרבי של הערכות כשירות) while

16 שלוף מספר שלם אקראי מקבוצת {1,….NP}

17 לולאת For i= 1 עד NP.

18 לולאת אם  (if) p> מספר אקראי בטווח [0,1]

19 ערוך האבקה כללית.

20

21 אם לא

22 ערוך האבקה מקומית.

23 אם i~=u

24 שלוף ווקטור אקראי ξ מתחום ^D[0,1].

25 שלוף 2 מספרים שלמים אקראיים, j, ו-k, מקבוצת {1,….NP}

26

27 אם לא

28 צור את S ע”י הפעלת OL על פי אלגוריתם 1. 

29 סוף לולאת if

30 סוף לולאת if

31 חשב את ערך הכשירות (SX_i)f.

32 עדכן את  SX_i אם הפרט הנוכחי עדיף מקודמו.

33 סוף לולאת For.

34 גלה את האבקה בעלת הכשירות הטובה ביותר באוכלוסיה .

35 עדכן את gbest אם האבקה הטובה ביותר הנוכחית עדיפה מהאבקה הטובה ביותר הקודמת

36 הפעל את אפקט השמפנון ע”פ  אלגוריתם 2.

37 חזור לדור הבא עד שתנאי ההפסקה יתקיים.

38 סוף לולאת  while.

39 פלט gbest.

40 סיים. 

5. ניסויי אימות והשוואה

ניסינו את האלגוריתם שלנו על 14 פונקציות מבחן, וכל פרטיהן מצוינים   בטבלה 3. פונקציות 1 עד 7, למשל, הן אונימודליות ומשמשות בעיקר לבדיקת היעילות המיטבית, ואלו פונקציות 8 עד 4 הן מולטימודליות ומשמשות בעיקקר לבחינת האפשרות לחרוג מנקודות אופטימום מקומיות. הפרמטרים ל FPA ול-ODFPA הם =3γ ו p=0.8. מספר האיטרציות הרצופות n במנגנון אפקט השמפנון הוא 7. כדי להבטיח השוואה הוגנת, גודל האוכלוסייה נקבע כ-20 ומספר בדיקות הכשירות, כ-20,000. כל התוצאות הסטטיסטיות הושג ב-30 הפעלות נפרדות של האלגוריתמים. התוצאות הטובות ביותר כתובות באות עבה. הניסויים התבצעו במחשב אישי בעל יחידת עיבוד מרכזית של 3.2 ג’יגה-הרץ וזיכרון של 2.5 ג’יגה ביט, ומערכת הפעלה של Windows XP.

טבלה 3: פונקציות המבחן

5.1. השיפורים ב FPA לעומת OCFPA

 בטבלה 4 מוצגים תוצאות הניתוחים הסטטיסטיים לביצועי שני האלגוריתמים.  מהטבלה עולה ש-OCFPA עדיף מ-FPA בכל פונקציות המבחן. הוא הגיע לפתרונות טובים יותר של הפונקציות האונימודליות מס’ 1, 3, 5, ו-7, וגם בגילוי נקודות האופטימום הכלליות של הפונקציות המורכבות מס’ 2 ו-4 הצטיין יותר מ-FPA. מהתוצאות עולה כי  OCFPA  מצטיין ביכולת ניצול מצוינת וביעילות מיטבית. כמו כן, בפונקציות המולטימודליות מס’ 8 עד 14, במצבים של ריבוי נקו’ אופטימום מקומיות, OCFPA הגיע לפתרונות כלליים או כמעט כלליים ופתרונותיו היו מדויקים ואיתנים יותר מאלו של FPA. מכאן נובע ש FPA יכול למנוע התכנסות מקומית ולהגיע לפתרונות מדויקים יותר.  לסיכום, האלגוריתם שלנו מגיע מהר יותר לפתרונות מיטביים ועולה בדיוקו על ה-FPA הבסיסי.   

טבלה 4: השוואה בין ביצועי FPA ל-OCFPA, בבעיות של 30 מימדים.

5.2 השפעת ההבדלים בין השיטות על יכולת  החיפוש.

 שיטות ה-OL ו”מנגנון אפקט השפמנון” שימשו להגברת יכולת החיפוש של ה-FPA. בטבלה 5 אנו משווים בין ביצועיהם של  ה-FPA המבוסס על OL (OFPA), של ה-FPA המבוסס על אפקט השפמנון (CFPA), ושל ה-OFCPA על פי סטיות התקן שלהם.

 ב-13 פונקציות, חוץ מפונקציה  מס’ 4, OCFPA היה עדיף על OFPA. מהתוצאות עולה כי קלוש הסיכוי ששיטת OL תשפר את איכות הפתרון מהרגע שהאלגוריתם ננעל על נקודות אופטימום מקומיות, כי עיקר פעולתה של ה-OL היא שילוב בין חלקי מידע, והוא אינו יכול לחקור תחומים חדשים כדי למצוא מידע מועיל יותר. ב-10 פונקציות OCFPA היה עדיף מ-CFPA, ובפונקציות מס’ 6, 10, ו-11 ביצועיהם היו שווים. מכאן נובע שמנגנון אפקט השפמנון מסוגל להרחיב את תחום החיפוש כדי לגלות פתרונות אפשריים מבטיחים יותר.   

מנתוני הטבלה עולה שפעולת הגומלין בין שתי השיטות מועילה ל-OCFPA, בשל יכולתו של מנגנון אפקט השפמנון לבדוק תחומי חיפוש חדשים ולספק ל-OL פרטים רבי ערך, ובשל יכולתה של OL לנצל במלואו את המידע המועיל כדי להגיע לפתרונות מדויקים.

 טבלה 5: השוואת ביצועים בין OFPA, CFPA, ו-OCFPA, בבעיות של 30 מימדים.

5.3 השפעת גודל האוכלוסייה על יכולת החיפוש של שלושת האלגוריתמים.

השווינו בין יכולות החיפוש של OFPA, FPA, ו-OCFPA, בארבע ניסויים באוכלוסיות של 20, 50, 80 ו-100 פרטים, והתוצאות מפורטות בטבלה 6. מהתוצאות עולה שבפונקציות מס’ 1 עד 14, ביצועיו של OCFPA היו טובים משל FPA בכל ארבעת הניסויים. אולם רמת הדיוק של FPA ושל יורדת ככל שהאוכלוסייה גדלה. מכאן נובע שאוכלוסייה גדולה מדי מצריכה שימוש תדיר בהערכות כשירות ומונעת מהאלגוריתם להגיע לנקודת האופטימום הכללית. אך גם אוכלוסיה קטנה מדי עלולה לפגוע ביכולת החיפוש בגלל הירידה במגוון האוכלוסייה. לכן, בחירת אוכלוסיה בגודל המתאים חיונית לשיפור ההשפעה המיטבית. 

30 מימדים, 20,000 בדיקות כשירות

30 מימדים, 20,000 בדיקות כשירות

טבלה 6: השוואה בין ביצועי הלוגריתמים באוכלוסיות בגדלים שונים.

5.4 השפעת מספר המימדים על ביצועי  האלגוריתמים

ככל שהממדים רבים יותר, הבעיה מורכבת יותר, ולכן בדקנו את יכולות המיטוב של OCFPA על מספרי מימדים שונים: 10 מימדים ו10,000 מבחני כשירות; 50 מימדים ו-30,000 מבחני כשירות; 75 מימדים ו-45,000 מבחני כשירות; ו-100 מימדים ו-60,000 מבחני כשירות. בכל ארבעת המצבים הן FPA והן OCFPA  הגיעו לפתרון המיטבי 0 לפונקציה מס’ 6, אבל בכל שאר הפונקציות OCFPA הצטיין יותר. כמו כן, הוא הצטיין למדיי בדיוק ההתכנסות ובמהירות המיטבית. . מכאן נובע ששילוב שתי השיטות האלה שיפרה בהרבה את יכולת החיפוש של ה-FPA  גם בפתרון בעיות רבות מימדים.

טבלה 7: השוואת ביצועים במימדים שונים, באוכלוסיה של 20 פרטים.

5.4 השוואה לביצועי אלגוריתמים אבולוציוניים מתקדמים.

הוכחנו את עדיפותו של OCFPA גם על אלגוריתמים כגון CS, GSA, CMAES, OXDE, SGHS, ו-CLPSO. התוצאות מוצגות בטבלאות 8 ו-9. הדרגה חושבה על פי הממוצע וסטיית התקן. טבלה 8 משווה בין הביצועים בפונקציות המבחן האונימודליות.  OCFPA הפגין יכולת מיטוב כללית עדיפה מזאת של כל השאר בפונקציות מס’ 1, 2, 3, 5, 7, אולם היה נחות מ-CMAES ומ-OXDE. בפונקציה 6, כל האלגוריתמים הגיעו לפתרון המיטבי 0.

בטבלה 9 מוצגים הביצועים בפונקציות המולטימודאליות. בפונקציות מס’ 8, 9, ו-12, OCFPA הגיע לפתרונות המיטביים הכלליים והצטיין יותר מכל שאר האלגוריתמים. בפונקציה 10, OCFPA וגם CLPSO הגיעו לנקודת האופטימום הכללית 0, ועלו על כל שאר האלגוריתמים. בפונקציה 11  OCFPA הצטיין יותר משאר האלגוריתמים בחיפוש מדויק ובפתרונות איתנים. בפונקציות 13 ו-14,  CLPSO עלה  מעט על OCFPA, אם כי בפונקציה 13, CKPSO, OCFPA ו-OXDE הגיעו לאותה רמת דיוק, כמו גם CMAES  בפונקציה 14.

איורים 2 ו-3 מציגים את עקומות הביצועים של OCFPA ושל שאר האלגוריתמים בפונקציות שונות. גם מהם עולה ש OCFPA עולה על האלגוריתמים המשוכללים האלה בכל הנוגע למהירות הפיתרון והדיוק ברוב הפונקציות. 

איורים 4 ו-5 הם תרשימי קופסה-ושפם (box-and-whisker plot) של קבוצות הפתרונות המיטביים ב-30 נסיונות נפרדים לפונקציות האונימודליות 1, 2,5, ו-7, ולפונקציות המולטימודליות 8, 9, 10, ו-11. מהן עולה שלאלגוריתם שלנו היו פחות חריגות (outliers ) ופיזור נמוך יותר, מה שמעיד על יציבותו הרבה.

טבלה 8:  השוואת ביצועים בין OCFPA  לאלגוריתמים האבולוציוניים בפונקציות אונימודליות בבעיות של 30 מימדים.

טבלה 9: השוואת ביצועים של OCFPA  והאלגוריתמים האבולוציוניים בפונקציות מולטימודליות בבעיות של 30 מימדים

5.6 ניתוח סטטיסטי לא-פרמטרי

בעזרת מבחן הדרגות המסומנות של וילקוקסון, ערכנו השוואה מזווגת  (pairwise comparison) בין ביצועי האלגוריתמים כדי לגלות את עוצמת ההבדלים בתוצאות הסופיות, ביותר מ-30 נסיונות בלתי תלויים. התוצאות מוצגות בטבלה 10. קבענו את סף המובהקות ל-0.05, והשווינו אליו את ערכי p.  מהטבלה עולה  כי בהשוואה בין CS ל-OCFPA, בין GSA ל-OCFPA ובין SGHS ל-OFCPA, p היה קטן בהרבה מ-0.05 ב-13 פונקציות.          OXDE ו-CMAES הצטיינו יותר מ-OCFPA  רק בפונקציה מס’ 4. CLPSO הצטיין יותר מ-OCFPA רק בפונקציות מס’ 13 ו-14. לסיכום, ניתן לומר שהאלגוריתם שהצענו הפגין ביצועים עדיפים מאלה של האלגוריתמים האבולוציוניים המתקדמים.

ע: עדיפות ל-OCFPA

R⁺: סך הדרגות שבהן OCFPA עלה על האלגוריתם האחר;

R^–: סך הדרגות שבהן האלגוריתם האחר עלה על OCFPA;

ש: שוויון בביצועים;

לא: עדיפות לאלגוריתם האחר;

W:  מס’ הפעמים שבהם OCFPA  הצטיין יותר;

T: מס’ הפעמים שבהן היה שוויון בביצועים;

L: מס’ הפעמים שבהן האלגוריתם האחר הצטיין יותר.

 טבלה 10: ניתוח סטטיסטי של ביצועי האלגוריתמים בעזרת  מבחן הדרגה המסומנת של וילקוקסון.

6. מסקנות

פיתחנו גרסה חדשנית של FPA המסתייעת ב-OL וב-מנגנון אפקט השפמנון לפתרון בעיות מיטוב מורכבות. OCFPA  נעזר ב-OL כדי לשפר את יכולת החיפוש המקומי של הFPA הבסיסי באמצעות חילופי מידע מועיל בין וקטורי פתרון שונים בכל מימד של הבעיה. כמו כן, מנגנון אפקט השפמנון מסייע ל-FPA לחרוג מנקודות האופטימום המקומיות, ושפר את מרחב החיפוש של האוכלוסייה כדי לחקור אזורים מבטיחים יותר. שתי האסטרטגיות האלה מסייעות ל-OCFPA  להגיע לאיזון נכון בין יכולות החקירה והניצול. תוצאות הניסויים באמצעות פונקציות המבחן הוכיחו את יעילותו של האלגוריתם שהצענו ואת הצלחתו.

אמנם הצלחנו לשלב בהצלחה את ה-OL ב-OCFPA, אולם במחקרים עתידיים יש לבחון אפשרויות להרחבת השימוש ב-OL באמצעות הפעלתה על מקורות מקורות מידע שונים. כמו כן בכוונתו לנצל את ה-FPA  המבוסס על OL לפתרון בעיות הנדסיות בעולם הממשי, כגון זיהוי פרמטרים ובחירת מאפיינים (feature selection).