אלגוריתמים אבולוציוניים וחיים מלאכותיים

202-1-5171

 

מרצה: פרופ' משה זיפר

בודק תרגילים: יונתן שיכל

 

איל ליס ,    040170789

דוד סויסה , 040580003

הנדסת תוכנה, שנה ד'

 

תאריך הגשה: 17-12-2006

 

תרגיל הגשה 3 - Genetic Programming

 

 

 

 

 

 

שאלה 1 – Evolving Sorting Networks            הקוד: evolution-ex3.scm

 

 

הקוד והדו"ח נכתבו עפ"י המאמר של   John R. Koza וחבריו:

"Evolving Sorting Networks using Genetic Programming and Rapidly Reconfigurable Field-Programmable Gate Arrays"

 

 

הקוד שכתבנו דומה במידה רבה לתרשים הזרימה של  Genetic Programming  שלמדנו בכיתה:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


נסביר את תרשים הזרימה בכלל ואת הקוד שכתבנו בפרט:

 

סט הפונקציות - { Compare-Exchange , progn2, progn3, progn4 }. המתודה בקוד המבצעת את הפונקציה Compare-Exchange נקראת  compare&swap! . שאר הפונקציות מוגדרות במתודה functions. המתודה בקוד הסופרת את מספר הפעולות Compare-Exchange נקראת  count-compare-exchange .

 

סט הטרמינלים - { 0,…,15, nop }.  המתודה בקוד המגדירה את סט הטרמינלים נקראת  terminals .

 

יצירת דור אפס – האוכלוסיה היא אוסף של 1000 עצים, כך שכל עץ מייצג תוכנית scheme. האוכלוסיה הראשונית נבנית באופן אקראי כלומר עבור כל צומת בעץ יש החלטה רנדומלית לגבי תוכנו ולכן העצים הנוצרים אינם בהכרח מלאים.

האוכלוסיה הראשונית מוגבלת לעצים עד עומק 5 בלבד. הסיבה לכך היא שלא נרצה ליצור עצים ענקיים ולא נרצה שזמן יצירת הדור ההתחלתי יהיה ארוך מאוד. אם בענף מסוים הגענו לעומק 5, אז העלים יהיו ((nop או Compare-Exchange בלבד בענף זה.

חשוב להדגיש כי העצים מוגבלים בעומקם בדור האפס בלבד. באבולוציה עצים אלו יעברו crossover & mutation  שיגדילו ויקטינו את גודלם ועומקם, כפי שנסביר בהמשך.

המתודה בקוד היוצרת את הדור האפס נקראת   generation0.

 

:Selection  selection tournament עם קבוצות בגודל 10% מגודל האוכלוסיה.

המתודה בקוד מבצעת את ה- selection נקראת  tournament.

 

חישוב ה- Fitness: לצורך חישוב ה-  fitnessאנו מגרילים בכל חישוב מספר וקטורים (50, 500, או 1000) בינאריים רנדומליים באורך 16 מתוך 65,536 האפשרויות ואותם מנסים למיין בעזרת העץ הנבדק. סדר ההחלפות שמבצע המיון הוא לפי סדר העלים במעבר DFS על העץ. ה- fitness הוא סכום של מספר הפעמים שהמיון לא הצליח ועוד שבר בתחום [ 0 , 0.99 ] המציין את נירמול של מספר ה- Compare-Exchange שיש בעץ. עבור 60 Compare-Exchange (המספר האופטימלי עפ"י המיון של Green) ערך השבר הוא אפס וככל שמספר ה- Compare-Exchange מתרחק מ- 60 (יותר או פחות) כך השבר גדל. עבור 32 Compare-Exchange ומטה או 100 Compare-Exchange ומעלה השבר יהיה מקסימלי =  0.99 . המתודה בקוד המבצעת את הנירמול נקראת make-normal .

הסיבה להוספת השבר היא שאנו רוצים לצ'פר עצים בעלי מספר Compare-Exchange הקרוב לאופטימום (60). ולכן ערך ה- fitness המקסימלי עבור 50 וקטורי בדיקה הוא 50.99, והמינימלי (ה- fitness הטוב ביותר – שאליו נשאף) הוא אפס עבור כל מספר של וקטורי בדיקה.

חישוב ה- fitness אצלנו שונה במעט מהחישוב של Koza. השבר ב- fitness  במאמרו של Koza המציין את מספר ה-  Compare-Exchange שיש בעץ מחושב ע"י מספר ה- Compare-Exchange שיש בעץ כפול 0.01. כמו כן Koza מונה רק את 65 ה- Compare-Exchange הראשונים בעץ, כלומר ערך השבר אצלו יכול להגיע עד 0.65 בלבד.

הסיבה לכך שנתנו ניקוד שונה (בשבר) למספר ה-Compare-Exchange  שיש בעץ היא שאנו מתחשבים גם בעצים המכילים יותר מ- 65 Compare-Exchange בתקווה שיוכלו להשתפר באבולוציה.

בנוסף, לא רצינו לצ'פר עצים עם מעט מאוד Compare-Exchange מכיוון שעצים אלו לא יצליחו למיין אבל ישתלטו על האוכולסיה בדורות הראשונים אם נצ'פר אותם.

המתודה בקוד המחשבת את ה- Fitness לעץ נקראת מין הסתם  fitness .

 

הערה לגבי בניית העצים וחישוב ה- Fitness: כמו Koza במאמרו, גם אנחנו הגדרנו באופן קבוע את 32 ה- Compare-Exchange הראשונים, הקבועים לכל העצים בכל ההרצות. בחישוב ה- fitness אנו קודם כל ממינים את וקטור הבדיקה עם 32 ה- Compare-Exchange הקבועים לפני שממינים אותו בעזרת העץ. מכאן שהעץ האופטימלי יכיל בעצם 32 Compare-Exchange קבועים ועוד 28 Compare-Exchange שפותחו ב- GP. בדו"ח אנחנו מתייחסים לעץ כאילו הוא מכיל את כל ה- Compare-Exchange כולל המלאכותיים שלא פותחו ב- GP.

המתודה בקוד הממיינת תחילה את וקטור הבדיקה בעזרת 32 הפעולות הקבועות נקראת  run-prefix! .

 

Crossover: Subtree Exchange. נבחר תת-עץ רנדומלי (שהשורש שלו הוא פונקציה או (nop מכל הורה ונחליף תתי עצים אלו. יש לשים לב כי פעולה זו יכולה לשנות את גודל העצים הצאצאים.

 

שיפור איכות העצים: מהרצות רבות שביצענו הבחנו כי בעץ נוצרות פעולות Compare-Exchange רבות עם אותם מספרים, לדוגמא (Compare-Exchange 5 10) חוזר על עצמו 8 פעמים בעץ כלשהו.

הדבר פוגע ביעילות העץ מכיוון שיש פעולות Compare-Exchange רבות שלא משפיעות כלל על העץ אך באות על חשבון פעולות אחרות שעשויות לתרום.

לכן בכל פעם שמתבצע crossover אנו מבצעים שיפור לעצים הצאצאים. אנו עוברים על הצאצאים ומגדלים פעולות Compare-Exchange אחרות (עם מספרים אחרים) במקום הפעולות החוזרות.

חשוב להדגיש ששיפור זה מתבצע רק אחרי crossover, ובהחלט יתכנו עדין עצים עם פעולות Compare-Exchange זהות בעקבות Mutation.

המתודה בקוד המבצעת את השיפור נקראת  remove-duplications .

 

Mutation: Subtree Mutation. נבחר צומת כלשהי בעץ (פונקציה או טרמינל) באופן רנדומלי, נזרוק את תת העץ היוצא מצומת זו ונגדל מצומת זו תת-עץ חדש שעומקו 5 לכל היותר. יש לשים לב כי פעולה זו יכולה לשנות את גודל העץ.

 

פרמטרים לריצה עפ"י המאמר של  Koza:

POPULATION SIZE = 1000;

Pc = 0.89;   // for Crossover

Pm = 0.01;   // for Mutation

Pr = 0.1;   // for Reproduction

 

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

בנוסף רצינו לראות האם ההרצה יכולה למצוא עץ עם פחות פעולות Compare-Exchange ממה שכבר מצאה.

 

 

 

הוראות הרצה:

 

הקוד שכתבנו נכתב בשפת scheme. עדיף להריץ את הקוד ב- MzScheme ולא ב- DrScheme  מהסיבה ש- MzScheme מהיר הרבה יותר.

בכדי להריץ ב- MzScheme יש לכתוב את הפקודה  (load "evolution-ex3.scm")  ולאחר מכן את הפקודה  (go n)  כאשר n הוא מספר הדורות, לדוגמא  (go 200).

 

התוכנית מוציאה 2 קבצי פלט של נתונים: קובץ txt  המכיל את הנתונים: מס' דור, fitness עבור העץ הטוב ביותר בדור, מספר Compare-Exchange בעץ הטוב ביותר בדור והעץ עצמו.

                                                             קובץ csv המכיל את הנתונים: מס' דור, fitness עבור העץ הטוב ביותר בדור, fitness ממוצע לכל העצים בדור ומספר Compare-Exchange בעץ הטוב ביותר בדור.

המתודה בקוד מייצרת את שני קבצי הפלט וכותבת לתוכם נקראת print-fitness.

 

הסיבה לכך שהקוד נכתב בשפת scheme היא שהעץ המייצג תוכנית ב- GP הוא עץ LISP / scheme. ב- scheme העץ (התוכנית) ניתן להרצה ע"י eval וכך ניתן לשערך עצים בקלות.

בנוסף, ב- scheme ההתעסקות עם עצים נוחה וקלה מאוד בהשוואה לשפות אחרות מכיוון שמבנה הנתונים עבור עץ ב- scheme הוא רשימה של רשימות.

המתודה בקוד המבצעת את שיערוך העץ נקראת  run-func! .

 

 

תוצאות:

 

א) עבור הרצה של אוכלוסיה בגודל 1000 למשך 200 דורות עם 50 וקטורי בדיקה הצלחנו להגיע לעץ שהכיל 60  Compare-Exchange וקיבל fitness = 0   כלומר מיין את כל 50 וקטורי הבדיקה.

            העץ התקבל בדור 70:

 (prog3

 (prog2 (nop) (compare&swap! 10 12))

 (prog3 (prog4 (prog4 (nop) (nop) (prog4 (compare&swap! 8 15) (compare&swap! 14 13) (nop) (compare&swap! 5 1)) (compare&swap! 9 3))

               (prog3 (prog4 (prog4 (compare&swap! 12 6) (nop) (nop) (prog2 (nop) (nop))) (prog3 (nop) (nop) (nop)) (nop) (nop)) (compare&swap! 10 9) (compare&swap! 12 1))

               (nop)

               (prog2 (compare&swap! 3 14) (nop)))

        (nop)

        (prog4

         (prog2 (prog3 (compare&swap! 4 11) (compare&swap! 1 10) (nop)) (prog3 (compare&swap! 5 12) (compare&swap! 6 9) (nop)))

         (prog3

          (prog4 (compare&swap! 4 10)

                 (prog3 (prog4 (prog4 (compare&swap! 5 14) (compare&swap! 6 15) (compare&swap! 9 10) (nop)) (compare&swap! 10 8) (nop) (nop))

                        (prog2 (compare&swap! 7 14) (prog4 (nop) (prog2 (nop) (nop)) (nop) (nop)))

                        (nop))

                 (prog3

                  (prog4

                   (prog4 (nop) (nop) (nop) (nop))

                   (prog3

                    (prog4 (prog4 (nop) (prog3 (prog2 (nop) (compare&swap! 8 3)) (nop) (nop)) (nop) (nop))

                           (prog4 (prog4 (nop)

                                         (prog3 (prog2 (nop) (nop))

                                                (nop)

                                                (prog4

                                                 (prog4 (prog3 (nop) (prog4 (compare&swap! 7 12) (compare&swap! 4 3) (nop) (nop)) (prog2 (nop) (compare&swap! 1 5))) (nop) (nop) (nop))

                                                 (prog3 (nop) (prog2 (prog2 (nop) (nop)) (prog4 (nop) (nop) (nop) (nop))) (nop))

                                                 (nop)

                                                 (nop)))

                                         (nop)

                                         (nop))

                                  (nop)

                                  (nop)

                                  (nop))

                           (nop)

                           (nop))

                    (nop)

                    (nop))

                   (nop)

                   (nop))

                  (nop)

                  (nop))

                 (prog2 (nop) (nop)))

          (prog2 (nop) (nop))

          (nop))

         (prog4 (nop) (prog2 (compare&swap! 8 9) (nop)) (compare&swap! 6 8) (prog3 (nop) (prog3 (nop) (compare&swap! 3 10) (prog2 (nop) (nop))) (nop)))

         (prog2 (nop) (prog3 (nop) (compare&swap! 2 6) (prog2 (compare&swap! 6 7) (prog2 (nop) (nop)))))))

 (nop))

 

 

ייצוג של 60 ה- Compare-Exchange בגרף (32 ה- Compare-Exchange הראשונים הם המלאכותיים ומופיעים בגרף באדום ו- 28 הנותרים התפתחו ב- GP ומופיעים בסגול):

 

 

 

הגרף עבור הרצה של אוכלוסיה בגודל 1000 למשך 200 דורות עם 50 וקטורי בדיקה (ה- fitness המקסימלי במקרה זה הוא 50.99):           

תוצאות ניסוי A בקובץ Excel

תוצאות ניסוי A בקובץ טקסט עם העץ הטוב ביותר בכל דור

 

 

 

·        בבדיקת עץ זה עבור כל 65,536 המקרים האפשריים התגלו 8838 מיקרים שלא מוינו, כלומר 13.5% מסך כל המקרים האפשריים.

המתודה בקוד הבודקת את העץ על כל 65,536 המקרים האפשריים נקראת  slow-fitness .

 

 

 

ב) עבור הרצה של אוכלוסיה בגודל 1000 למשך 500 דורות עם 500 וקטורי בדיקה הצלחנו להגיע לעץ שהכיל 62  Compare-Exchange וקיבל fitness = 0.099   כלומר מיין את כל 500 וקטורי הבדיקה.

            העץ התקבל בדור 196:

(prog4 (nop)

       (prog4 (nop) (prog3 (compare&swap! 2 1) (compare&swap! 7 12) (compare&swap! 1 7)) (prog3 (nop) (nop) (nop)) (nop))

       (prog4 (prog4 (nop) (nop) (nop) (nop)) (prog3 (nop) (nop) (compare&swap! 7 5)) (nop) (nop))

       (prog4 (prog4 (prog2 (prog3 (nop)

                                   (prog4 (prog4 (prog2 (nop) (nop)) (prog2 (prog2 (nop) (nop)) (nop)) (prog2 (prog2 (nop) (nop)) (nop)) (prog3 (nop) (nop) (nop))) (prog3 (nop) (nop) (prog3 (nop) (nop) (nop))) (nop) (nop))

                                   (nop))

                            (prog2 (nop) (nop)))

                     (nop)

                     (nop)

                     (compare&swap! 9 8))

              (prog2 (prog4 (prog4 (prog4 (nop) (nop) (nop) (nop)) (nop) (compare&swap! 3 9) (nop))

                            (prog4 (nop) (nop) (nop) (compare&swap! 8 10))

                            (compare&swap! 6 8)

                            (prog3 (nop)

                                   (nop)

                                   (prog4 (prog4 (prog4 (nop) (nop) (nop) (prog2 (prog3 (compare&swap! 7 9) (nop) (nop)) (prog3 (nop) (nop) (nop))))

                                                 (prog3 (prog3 (nop)

                                                               (prog4 (nop)

                                                                      (nop)

                                                                      (compare&swap! 8 5)

                                                                      (prog4 (compare&swap! 9 14)

                                                                             (prog4 (prog2 (nop) (nop)) (nop) (prog2 (prog2 (nop) (nop)) (nop)) (prog2 (prog2 (nop) (nop)) (nop)))

                                                                             (nop)

                                                                             (compare&swap! 8 9)))

                                                               (nop))

                                                        (prog2 (prog3 (nop) (nop) (nop)) (compare&swap! 5 10))

                                                        (prog4 (compare&swap! 11 14)

                                                               (compare&swap! 11 13)

                                                               (compare&swap! 9 11)

                                                               (prog4 (nop)

                                                                      (compare&swap! 5 9)

                                                                      (nop)

                                                                      (prog3 (prog4 (nop) (nop) (nop) (prog2 (prog3 (nop) (nop) (nop)) (prog2 (nop) (nop))))

                                                                             (nop)

                                                                             (prog4 (nop)

                                                                                    (nop)

                                                                                    (nop)

                                                                                    (prog3 (prog4 (nop) (nop) (nop) (prog2 (prog3 (nop) (nop) (nop)) (prog2 (nop) (nop))))

                                                                                           (nop)

                                                                                           (prog3 (compare&swap! 12 13) (prog2 (prog3 (nop) (nop) (nop)) (nop)) (nop))))))))

                                                 (prog4 (nop) (nop) (nop) (compare&swap! 6 7))

                                                 (nop))

                                          (prog4 (nop)

                                                 (nop)

                                                 (prog3 (nop) (prog4 (prog4 (compare&swap! 3 2) (nop) (prog2 (prog2 (nop) (nop)) (nop)) (nop)) (prog4 (nop) (nop) (nop) (nop)) (nop) (nop)) (nop))

                                                 (prog3 (prog2 (nop)

                                                               (prog4 (nop)

                                                                      (nop)

                                                                      (prog3 (nop)

                                                                             (prog4

                                                                              (prog4 (prog2 (nop) (nop)) (nop) (prog2 (prog2 (nop) (nop)) (nop)) (prog3 (nop) (nop) (nop)))

                                                                              (prog3 (nop)

                                                                                     (prog4 (prog4 (prog2 (nop) (nop)) (nop) (prog2 (prog2 (nop) (nop)) (nop)) (prog2 (prog2 (nop) (nop)) (nop)))

                                                                                            (prog4 (nop) (nop) (nop) (nop))

                                                                                            (nop)

                                                                                            (nop))

                                                                                     (nop))

                                                                              (nop)

                                                                              (nop))

                                                                             (nop))

                                                                      (compare&swap! 2 4)))

                                                        (nop)

                                                        (compare&swap! 8 7)))

                                          (prog2 (nop) (nop))

                                          (prog3 (prog3 (prog2 (compare&swap! 10 11) (nop)) (compare&swap! 1 4) (nop)) (nop) (compare&swap! 5 8)))))

                     (prog2 (compare&swap! 9 10) (compare&swap! 7 8)))

              (nop)

              (prog2 (prog4 (nop) (nop) (prog2 (prog3 (nop) (nop) (nop)) (nop)) (compare&swap! 4 6))

                     (prog3 (prog3 (prog4 (nop) (nop) (nop) (prog3 (nop) (nop) (prog3 (prog2 (nop) (nop)) (prog3 (nop) (nop) (compare&swap! 1 3)) (nop))))

                                   (compare&swap! 5 6)

                                   (prog2 (nop) (prog4 (nop) (nop) (nop) (nop))))

                            (nop)

                            (nop)))))

 

ייצוג של 62 ה- Compare-Exchange בגרף (32 ה- Compare-Exchange הראשונים הם המלאכותיים ומופיעים בגרף באדום ו- 30 הנותרים התפתחו ב- GP ומופיעים בסגול):

 

 

 

 

הגרף עבור הרצה של אוכלוסיה בגודל 1000 למשך 500 דורות עם 500 וקטורי בדיקה (ה- fitness המקסימלי במקרה זה הוא 500.99):         

תוצאות ניסוי B בקובץ Excel

תוצאות ניסוי B בקובץ טקסט עם העץ הטוב ביותר בכל דור

 

 

·        בבדיקת עץ זה עבור כל 65,536 המקרים האפשריים התגלו 788 מיקרים שלא מוינו, כלומר 1.2% מסך כל המקרים האפשריים.

·        באותה הרצה, בדור 493 התקבל עץ שעבורו התגלו רק 636 מיקרים שלא מוינו, כלומר 0.97% מסך כל המקרים האפשריים (!!!).

 

 

 

ג) עבור הרצה של אוכלוסיה בגודל 1000 למשך 500 דורות עם 1000 וקטורי בדיקה הצלחנו להגיע לעץ שהכיל 70  Compare-Exchange וקיבל fitness = 0.2475   כלומר מיין את כל 1000 וקטורי הבדיקה.

            העץ התקבל בדור 401:

(prog4 (prog2

        (prog3 (prog2 (compare&swap! 7 1)

                      (prog4 (prog2 (prog3 (prog2 (nop) (compare&swap! 10 12)) (prog3 (compare&swap! 2 7) (nop) (nop)) (compare&swap! 3 12)) (prog3 (nop) (prog4 (nop) (prog2 (nop) (nop)) (nop) (nop)) (prog3 (nop) (nop) (nop))))

                             (nop)

                             (compare&swap! 15 10)

                             (prog2 (nop)

                                    (prog4 (nop)

                                           (prog2 (prog3

                                                   (nop)

                                                   (prog4 (prog2 (nop) (prog3 (nop) (nop) (prog3 (nop) (nop) (nop)))) (compare&swap! 3 5) (nop) (compare&swap! 3 7))

                                                   (prog4 (nop)

                                                          (prog3 (compare&swap! 5 9)

                                                                 (prog4 (prog3

                                                                         (prog4 (nop) (compare&swap! 15 5) (nop) (nop))

                                                                         (prog4 (prog4 (nop)

                                                                                       (prog3 (nop)

                                                                                              (prog3 (nop) (prog3 (prog3 (nop) (nop) (nop)) (nop) (nop)) (nop))

                                                                                              (prog3 (nop) (prog4 (nop) (nop) (nop) (prog4 (prog2 (nop) (compare&swap! 2 4)) (prog2 (nop) (nop)) (nop) (nop))) (nop)))

                                                                                       (nop)

                                                                                       (prog3 (nop) (compare&swap! 12 13) (nop)))

                                                                                (prog2 (compare&swap! 8 4) (nop))

                                                                                (nop)

                                                                                (nop))

                                                                         (compare&swap! 9 12))

                                                                        (nop)

                                                                        (nop)

                                                                        (nop))

                                                                 (nop))

                                                          (compare&swap! 1 5)

                                                          (compare&swap! 5 15)))

                                                  (prog3 (prog2

                                                          (prog3 (prog3

                                                                  (nop)

                                                                  (nop)

                                                                  (prog3 (prog3 (nop) (prog3 (prog2 (nop) (nop)) (prog2 (nop) (nop)) (nop)) (nop))

                                                                         (nop)

                                                                         (nop)))

                                                                 (nop)

                                                                 (prog3 (prog3 (nop) (nop) (nop)) (nop) (nop)))

                                                          (compare&swap! 11 15))

                                                         (prog3 (prog3 (prog2 (nop) (nop)) (prog2 (nop) (nop)) (nop)) (prog3 (prog2 (nop) (nop)) (nop) (nop)) (nop))

                                                         (nop)))

                                           (prog3 (nop)

                                                  (prog2 (prog4

                                                          (prog3 (nop)

                                                                 (prog3 (prog3

                                                                         (nop)

                                                                         (prog3 (nop)

                                                                                (nop) (prog3 (prog2 (nop) (nop)) (prog4 (nop) (nop) (nop) (prog4 (prog3 (nop) (nop) (nop)) (nop) (nop) (nop))) (nop)))

                                                                         (nop))

                                                                        (nop)

                                                                        (nop))

                                                                 (prog2 (nop) (nop)))

                                                          (prog4 (nop) (compare&swap! 7 5) (prog4 (nop) (nop) (nop) (nop)) (nop))

                                                          (nop)

                                                          (prog2 (prog4 (nop) (compare&swap! 9 14) (nop) (nop)) (prog3 (nop) (nop) (nop))))

                                                         (compare&swap! 6 1))

                                                  (prog2 (compare&swap! 1 8) (nop)))

                                           (nop)))))

               (prog4 (nop)

                      (prog3 (prog4 (prog3 (nop) (prog3 (prog2 (nop) (nop)) (prog2 (nop) (nop)) (nop)) (nop)) (prog2 (compare&swap! 4 7) (nop)) (nop) (nop))

                             (nop)

                             (prog3 (nop) (compare&swap! 7 6) (prog3 (nop) (nop) (nop))))

                      (prog3 (prog2

                              (nop)

                              (compare&swap! 5 7))

                             (nop)

                             (prog3 (prog4 (prog3 (nop) (nop) (nop))

                                           (nop)

                                           (prog2 (prog3 (prog2 (nop) (nop)) (nop) (nop))

                                                  (prog3 (prog2 (prog3 (nop) (nop) (prog3 (compare&swap! 11 14) (prog4 (nop) (nop) (nop) (prog4 (compare&swap! 11 12) (nop) (nop) (nop))) (nop))) (nop)) (nop) (nop)))

                                           (prog3 (prog3 (nop) (nop) (nop)) (prog4 (nop) (nop) (nop) (nop)) (nop)))

                                    (nop)

                                    (nop)))

                      (nop))

               (nop))

        (prog3 (nop) (nop) (prog3 (prog2 (compare&swap! 6 7) (nop)) (nop) (nop))))

       (nop)

       (nop)

       (prog2 (nop)

              (prog4 (prog2 (nop) (prog3 (nop) (nop) (nop)))

                     (prog2 (prog3 (nop)

                                   (prog4 (nop)

                                          (prog3 (prog3 (nop) (nop) (nop)) (nop) (nop))

                                          (nop)

                                          (prog4 (compare&swap! 13 14) (nop) (nop) (prog3 (nop) (nop) (nop))))

                                   (prog4 (prog3 (nop) (nop) (prog3 (nop) (nop) (nop)))

                                          (prog3 (nop)

                                                 (nop)

                                                 (prog3 (prog2 (nop) (nop)) (prog4 (nop) (nop) (nop) (prog4 (prog3 (nop) (nop) (nop)) (nop) (nop) (nop))) (nop)))

                                          (prog4 (nop) (nop) (nop) (prog4 (nop) (nop) (nop) (nop)))

                                          (compare&swap! 8 9)))

                            (nop))

                     (prog3 (prog3 (nop) (nop) (prog2 (compare&swap! 3 4) (nop)))

                            (prog2 (prog4

                                    (nop)

                                    (nop)

                                    (prog3 (nop)

                                           (prog4 (nop)

                                                  (nop)

                                                  (prog3 (nop)

                                                         (prog3 (prog2 (compare&swap! 7 8) (nop)) (prog2 (nop) (nop)) (nop))

                                                         (nop))

                                                  (nop))

                                           (nop))

                                    (prog3 (nop)

                                           (prog2 (prog4 (nop)

                                                         (prog4 (nop) (nop) (prog3 (nop) (prog4 (prog3 (nop) (prog2 (nop) (nop)) (prog4 (nop) (nop) (compare&swap! 9 11) (nop))) (compare&swap! 4 6) (nop) (nop)) (nop)) (nop))

                                                         (prog3 (nop) (prog4

                                                                       (prog3 (prog3 (nop) (nop) (prog3 (prog3 (nop) (nop) (nop)) (nop) (nop))) (nop) (prog3 (prog3 (nop) (nop) (nop)) (nop) (nop)))

                                                                       (nop)

                                                                       (prog3 (nop) (prog3 (compare&swap! 4 5) (nop) (prog2 (prog2 (compare&swap! 14 11) (nop)) (prog2 (nop) (nop)))) (nop))

                                                                       (nop))

                                                                (prog2 (nop) (nop)))

                                                         (nop))

                                                  (prog4 (nop)

                                                         (nop)

                                                         (prog4 (nop) (nop) (compare&swap! 13 12) (compare&swap! 11 13))

                                                         (prog3 (nop) (prog4 (nop) (nop) (prog3 (nop) (prog3 (prog2 (nop) (nop)) (prog2 (nop) (nop)) (nop)) (nop)) (nop)) (prog3 (nop) (nop) (nop)))))

                                           (prog2 (prog3 (nop) (nop) (nop)) (nop))))

                                   (prog3 (nop)

                                          (prog2 (prog4 (nop) (nop) (nop) (prog3 (nop) (prog2 (nop) (prog4 (nop) (nop) (compare&swap! 10 14) (nop))) (nop))) (nop))

                                          (prog3 (prog4 (nop) (nop) (nop) (nop))

                                                 (nop)

                                                 (prog3 (compare&swap! 10 11) (prog3 (prog4 (nop) (nop) (nop) (nop)) (nop) (prog3 (nop) (prog4 (nop) (nop) (nop) (nop)) (nop))) (nop)))))

                            (prog2 (nop) (nop)))

                     (nop))))

 

 

הגרף עבור הרצה של אוכלוסיה בגודל 1000 למשך 500 דורות עם 1000 וקטורי בדיקה (ה- fitness המקסימלי במקרה זה הוא 1000.99):      

תוצאות ניסוי C בקובץ Excel

תוצאות ניסוי C בקובץ טקסט עם העץ הטוב ביותר בכל דור

 

 

·        בבדיקת עץ זה עבור כל 65,536 המקרים האפשריים התגלו רק 220 מיקרים שלא מוינו, כלומר 0.34% מסך כל המקרים האפשריים (!!!).

 

 

 

ניתוח התוצאות ומסקנות:

 

כמו כן קיימות ההשפעות הרגילות של גודל האוכלוסיה ומספר הדורות.

 

חישוב ה- fitness אצלנו יעיל יותר מכיוון שאנו מתחשבים גם בעצים המכילים יותר מ- 65 Compare-Exchange בתקווה שיוכלו להשתפר באבולוציה.

בנוסף, לא רצינו לצ'פר עצים עם מעט מאוד Compare-Exchange מכיוון שעצים אלו לא יצליחו למיין אבל ישתלטו על האוכולסיה בדורות הראשונים אם נצ'פר אותם.

בחישוב של Koza הדורות הראשונים באבולוציה מתקשים להתפתח מכיוון שהם מעדיפים כמה שפחות פעולות Compare-Exchange כי הם מקבלים fitness נמוך יותר.

 

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

 

(Pc = 0.89, Pm = 0.01, Pr = 0.1).

 

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

 

בהרצה השנייה התוכנית הצליחה למיין את וקטורי הבדיקה כבר בדור 67 עם עץ בעל 72 פעולות Compare-Exchange, אך רק בדור 196 התקבל העץ בעל מספר פעולות Compare-Exchange המינימלי להרצה זו (62).

גם בהרצה השלישית התוכנית הצליחה למיין את וקטורי הבדיקה כבר בדור 83 עם עץ בעל 89 פעולות Compare-Exchange, אך רק בדור 401 התקבל העץ בעל מספר פעולות Compare-Exchange המינימלי להרצה זו (70).

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

 

ניתן לראות כי בהרצה הראשונה גודל הסט היה 50. בבדיקת העץ הטוב ביותר בהרצה עבור כל 65,536 המקרים האפשריים התגלו 8838 מיקרים שלא מוינו, כלומר 13.5% מסך כל המקרים האפשריים.

בהרצה השנייה גודל הסט היה 500. בבדיקת העץ הטוב ביותר בהרצה עבור כל 65,536 המקרים האפשריים התגלו 788 מיקרים שלא מוינו, כלומר 1.2% מסך כל המקרים האפשריים.

באותה הרצה, בדור מתקדם יותר (493) התקבל עץ שעבורו התגלו רק 636 מיקרים שלא מוינו, כלומר 0.97% מסך כל המקרים האפשריים.

בהרצה השלישית גודל הסט היה 1000. בבדיקת העץ הטוב ביותר בהרצה עבור כל 65,536 המקרים האפשריים התגלו רק 220 מיקרים שלא מוינו, כלומר 0.34% מסך כל המקרים האפשריים.

 

            מכאן נובע כי ככל שסט וקטורי הבדיקה גדול יותר כך האלגוריתם מכליל טוב יותר עבור כל 65,536 המקרים האפשריים.

            גם עבור סטים בגודל 500 התוכנית מייצרת עץ מיון בעל מספר פעולות Compare-Exchange טוב (62) ואחוז טוב למיון מוצלח (99.03%).

כפי שכבר הזכרנו, הגדלת סט וקטורי הבדיקה מגדיל את זמן הריצה וגם מעלה את מספר פעולות ה- Compare-Exchange (60, 62, 70 בעץ הכי טוב לפי ההרצות בהתאמה) מכיוון שהעץ נדרש לבצע יותר מיונים בכדי לקבל fitness נמוך יותר, וככל שיש יותר וקטורים נבדקים – האלגוריתם זקוק ליותר פעולות Compare-Exchange.

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

 

עם סט וקטורי בדיקה בגודל 50 הגענו ל- 60 פעולות בעץ (אופטימלי).

עם סט וקטורי בדיקה בגודל 500 הגענו ל- 62 פעולות בעץ (קרוב מאוד לאופטימום).

עם סט וקטורי בדיקה בגודל 1000 הגענו ל- 70 פעולות בעץ (די רחוק מהאופטימום אבל ממיין טוב).

 

 

לפי התוצאות שהצגנו והשיפור בין הניסויים השונים שערכנו, נראה כי עם כוח חישוב גדול יותר והגדלת הדורות וסט וקטורי הבדיקה ניתן להגיע בעזרת התוכנית שלנו לתוצאה האופטימלית – עץ בעל 60 פעולות Compare-Exchange שימיין באופן מוחלט את כל 65,536 המקרים האפשריים.

 

 

 

 

 

 

- סוף -