Evolutionary Computation and Artificial Life

Exercise 5 –Answers

מגישות:

עינב ביטון 040893133

יסמין מגידיש 060639150

Solving the Synchronization and the Density problems using Cellular Programming Algorithm

בתרגיל זה פתרנו את בעיית ה Synchronization ואת בעיית ה Density באמצעות Cellular Programming.

בעיית הסינכרוניזציה: האוטומט התאי צריך להגיע למצב שבו כל שורה מורכבת מצבע אחד וצבע שורה כלשהי שונה מבצעי השורות הצמודות אליה.

בעיית הצפיפות: האוטומט התאי צריך להגיע למצב שבו כל שורה מורכבת מצב יחיד הזהה לצבע השורות הצמודות אליה.

כל הקוד נכתב ב JAVA.

אלגוריתם ה Cellular Programming מומש לפי Moshe Sipper's Cellular Programming Algorithm.

The parameters used in our solution:

Configuration runs’ number - Density: configurationCounter = 20,000

Configuration runs’ number - Synchronization: configurationCounter = 400,000

Rule Table evolution interval: C = 300

Running Cellular Automata: M = 2 * Cellular_Atomata_Size

Genome representation:

הגנום במקרה של Cellular Automata הוא האוטומט התאי - מערך של תאים, חד מימדי ומעגלי. האוטומט התאי אינו יוני פורמי, כלומר לכל תא יש RT משלו. האוטומט התאי הינו בנארי, כלומר ה value של כל תא הוא 0 או 1. גודל הגנום הינו 29, 49 כמתבקש.

Rule Table Representation (for each cell):

ע"פ הנתון בשאלה r=1 ולכן גודל הסביבה של כל תא באוטומט התאי הינו 2r+1 = 3. ומכאן שגודל ה Rule Table(RT) הוא 2 ^ (2r+1) = 8 טבלה תלת מימדית 2X2X2 כאשר המימד הראשון מיצג את השכן השמאלי, האמצעי את התא הנוכחי והשלישי מייצג את השכן הימני. למשל עבור 001 – מיקום זה ב RT - m_ruleTable[0][0][1]מייצג את החוק המתאים למצב 001 ומכיל את הערך אליו יעבור התא.

Initialization:

אתחול ה RT – הגרלת החוקים באופן אקראי לערכי 0 או 1.

אתחול ערך התאים בכל דור של האלגוריתם – ע"פ שיטת ה Bias הגרלת מספר רנדומאלי ובהסתברות אותו מספר שהוגרל מוגרלים ערכי התאים.

Fitness method:

ע"פ המתואר באלגוריתם – כל C=300, RT evolution time interval מחשבים את ה fitness הממוצע לכל התאים. בכל איטרציה מתוך ה-300 כל תא נבחן - אם הוא עומד בתנאים מוסיפים לו ניקוד אחרת ערכו נותר ללא שינוי. שיטת חלוקת הניקוד היא פרטית לבעיה איתה התמודד האוטומט התאי, ומפורטת כדלהלן:

Ø Density Problem –

לאחר ריצה של runCA (ריצה של M = 2 * Cellular_Automata_Size) מעריכים כל תא באופן הבא – אם ערכו הנוכחי של התא סווג להיות הערך המצופה של בעיית ה Density אזי ערך ה fitness שלו עלה ב 1, אחרת נותר ללא שינויי. ומכאן שערך ה - fitness של תא יחיד הוא בטווח של .0-300 ערך ה- Densityנקבע ע"י הערך השולט (0/1) באוכלוסיה האקראית שהגרלנו באותה איטרציה.

Ø Synchronization Problem –

לאחר ריצה של runCA (ריצה של M = 2 * Cellular_Automata_Size) מעריכים כל תא באופן הבא – נניח כי אנו מחשבים את ערך ה fitness בזמן T, אזי:

If cell.value(T) == cell.value (T-2)

fitness++

מקבל 1+ אם ערכו שווה לערכו לפני 2 איטרציות

If cell.value (T) != cell.value (T-1)

fitness++

מקבל 1+ אם ערכו לא שווה לערכו מאיטרציה הקודמת

If cell.value (T) == cell.rigth.value (T)

fitness++

מקבל 1+ אם ערכו שווה לשכנו הימני

If cellValue(T) == cell.left.value (T)

fitness++

מקבל 1+ אם ערכו שווה לשכנו השמאלי

כלומר ערך fitness של תא יחיד הוא בטווח של 0 – 300*4.

Crossover:

Rule Table Crossover method:

ע"פ המתואר באלגוריתם –

לכל תא מחשבים את ה Fitter neighbors שלו (ערך ה fitness שלהם גבוה יותר משלו).

אם ה fitter neighbors == 0 נשאר ללא שינוי.

אם מספר ה fitter neighbors == 1 אז מבצעים החלפה בינו לבין השכן הטוב.

אחרת אם fitter neighbors == 2 (אין אפשרות ליותר r=1) מבצעים crossover כדלהלן: הגרלת מספר רנדומאלי, בטווח 0-8, המציין את מספר החוקים שיועתקו משכן-הורה אחד, והשאר יועתקו מהשכן-הורה השני. הRT החדש שנוצר הוא הצאצא החדש.

Mutation rate: 0.01

Rule Table Mutation method:

בחירת מיקום בטבלה [0,7], חוק, באופן רנדומאלי והפיכת ערכו. בעת ביצוע mutation אנו בוודאות משנים את ערכו של אחד מהחוקים שב Rule table.

Experiments plots for Density Problem

The results for Cellular Automata, size = 29

Run #1: Best Fitness: 0.943333 in generation: 191700

Run #2: Best Fitness: 0.87 in generation: 91500

Run #3: Best Fitness: 0.91 in generation: 399900

Run no. 1:

Rule Table vector:

232 232 232 232 232 232 232 232 232 232 232 232 232 232 224 224 224 224 224 224 224 224 224 224 224 232 232 232 232

Run no. 2:

Rule Table vector:

234 234 234 234 200 200 200 200 200 200 200 200 200 200 232 232 232 232 232 232 232 232 232 232 232 232 234 234 234

Run no. 3:

Rule Table vector:

184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184

The results for Cellular Automata, size = 49

Run #1: Best Fitness: 0.93 in generation: 290400

Run #2: Best Fitness: 0.863333 in generation: 79800

Run #3: Best Fitness: 0.86 in generation: 21900

Run no. 1:

Rule Table vector:

184 184 184 184 184 184 184 184 184 188 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 232 232 232 232 232 232 232 232 232 232 232 184 184 184 184 184 184 184

Run no. 2:

Rule Table vector:

226 226 226 226 226 226 226 226 226 226 226 226 226 226 226 226 226 234 234 234 170 170 170 170 170 232 232 232 232 232 232 232 232 232 232 232 232 232 232 232 232 232 232 232 232 232 226 226 226

Run no. 3:

Rule Table vector:

95 95 95 95 95 95 95 95 95 95 127 127 127 127 127 127 127 127 127 127 127 127 127 127 127 127 127 127 127 127 127 127 127 127 127 127 127 127 127 127 127 127 127 127 127 127 95 95 95

Experiments plots for Synchronization Problem

The results for Cellular Automata, size = 29

Got the first a Perfect Fitness in generation number:

Run #1: 6300

Run #2: 8100

Run #3: 8400

Run no. 1:

Rule Table vector:

117 117 117 117 117 117 117 117 117 117 117 117 117 119 119 119 115 113 3 3 3 3 3 7 3 3 11 3 21

Run no. 2:

Rule Table vector:

81 81 81 17 17 17 87 87 87 19 83 83 83 83 83 83 83 83 119 119 119 115 83 81 81 83 83 83 83

Run no. 3:

Rule Table vector:

83 83 83 83 83 83 83 83 83 83 83 83 63 63 63 63 63 63 63 63 63 63 63 63 63 55 55 55 55

The results for Cellular Automata, size = 49

Got the first a Perfect Fitness in generation number:

Run #1: 18900

Run #2: 16500

Run #3: 8700

Run no. 1:

Rule Table vector:

35 35 35 35 35 35 3 3 3 3 3 3 3 3 3 3 3 11 3 3 3 3 3 3 39 39 39 39 39 39 39 39 37 39 55 39 39 39 167 39 39 39 35 35 35 35 35 35 35

Run no. 2:

Rule Table vector:

39 103 39 39 39 39 39 103 39 39 39 39 39 39 39 39 39 39 39 39 103 39 39 35 35 39 39 39 39 53 53 53 53 53 53 53 53 53 53 53 53 63 31 31 31 63 63 63 31

Run no. 3:

Rule Table vector:

85 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 23 53 85 53 53 21 21 21 51 59 59 59 59 59 59 59 43 59 43 11 11 27 11 11 3 3 21 21 21 21 21 21 21

לעיון מפורט בתוצאות כל הריצות הנ"ל לחץ כאן

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

Improvements/Tricks:

v Density problem – אין.

v Synchronization problem – ע"פ המתואר לעיל, חישוב ה fitness מאפשר לכל תא להגיע לערך בטווח 0-4, מאחר שלכל תא מתבצעת בדיקת הסנכרון מול שכניו הסמוכים, ימני ושמאלי, ערכו ב time step–1 וערכו time step-2. מניסויים שערכנו ראינו כי האבולוציה מגיעה לתוצאות הטובות ביותר ובדורות מוקדמים יותר כאשר חישוב ה fitness נעשה במתכונת הנ"ל.

Conclusions:

v את בעיית הצפיפות לא הצלחנו לפתור בצורה מושלמת.התוצאה המקסימאלית שקיבלנו הינה 94%.

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

v ניתן לראות, הן בבעיית הסינכרוניזציה והן בבעיית הצפיפות, כי בדורות הראשונים ערך ה fitness מאוד נמוך, שואף ל 0. אך האבולוציה תוך מספר קטן של דורות מקפיצה את ערך ה fitness וישנה עלייה תלולה בערך ה fitness. לאורך ריצת האלגוריתם יש קפיצות בערך ה fitness בשל ה crossover, המתבצע כל 300 דורות (ללא הסתברות כלשהי), וה mutation המתבצע כל 300 דורות בהסתברות נמוכה. לאחר כל ירידה חדה בערך הfitness ניתן לראות כי האבולוציה "מתקנת" את הנזק במהירות וערך ה fitness עולה משמעותית.

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

o בבעיית הסינכרוניזציה הגענו להתכנסות בתחום של 20,000 דורות, לעומת בעיית הצפיפות – אותה הרצנו 400,000 דורות ע"מ להגיע לתוצאה טובה.

o בבעיית הסינכרוניזציה אנו מגיעים ל Perfect Fitness (=1) לאחר מספר דורות קטן יחסית. הדבר בא לידי ביטוי בגרפים לעיל. לעומת זאת, בבעיית הצפיפות אין אנו מגיעים ל Perfect Fitness. עבור CA with size = 29קבלנו fitness מקסימאלי של 0.94. עבור CA with size = 49קבלנו fitness מקסימאלי של 0.93.

o ניתן לראות כי בגרפים של Fitness vs. Time הגרפים של בעיית הצפיפות רועשים יותר מהגרפים של בעיית הסינכרוניזציה. הדבר נובע מחוסר היציבות של פתרון בעיית הצפיפות.

v ניתן לראות כי בגרף של ה Rule Table בתחילה ישנו מגוון רחב של חוקים, אך במהלך הריצה הגרף מתכנס למספר חוקים דומיננטיים, החוקים "הטובים". ההתכנסות לחוקים הדומיננטיים אינה באי סדר. החוקים מופיעים ברצף, ובכך שומרים על חוזקם ומשתלטים. בשתי הבעיות נראה כי האוטומט התאי, הלא יוניפורמי, מתייצב על מספר מצומצם של חוקים שולטים.

v הן בבעיית הסינכרוניזציה והן בבעיית הצפיפות, עבור CA with size = 29 האלגוריתם מתכנס במהירות יותר מאשר עבור CA with size = 49. הדבר בא לידי ביטוי בדורות הראשונים. אך במהלך הריצה של האלגוריתם לא ניתן להסיק מסקנות לגבי התוצאות וקצב התקדמותו לקראת פתרון טוב יותר על בסיס גודל ה CA.

Implementation:

All the implemented code