האבולוציה לפי אלגוריתם ה- Cellular Programming של זיפר, מתאפיינת בכך שהיא מקומית (Local), הן ביחס לפעולות האופרטורים, הן ביחס

ינואר ‏2004

מגישים: אורי לוביץ' 31387293

יאיר פילד 33612557

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

תרגיל מס' 5 ואחרון

מטרת התרגיל:

מימוש האלגוריתם האבולוציוני של זיפר cellular programming algorithm ,

לפתרון בעיית ה- Synchronization (מצב בינארי, חד ממדי, רדיוס = 1).

בתרגיל הזה ניסינו לבדוק רעיון מסוים לגבי אלגוריתם ה- Cellular Programming של זיפר. בתוך כך, גם ענינו על הנדרש בתרגיל.

מה הרעיון?

האבולוציה לפי אלגוריתם ה- Cellular Programming של זיפר, מתאפיינת בכך שהיא מקומית
(Local), הן ביחס לפעולות האופרטורים האבולוציוניים, הן ביחס לקביעת ה- Fitness.

אנו מבחינים בכך שה"חישוב" שמבצעת האבולוציה לפי אלגוריתם זה, דומה לחישוב תאי (Cellular Computing).

כלומר, אם נסתכל על פרק הזמן באלגוריתם שבין שני עדכונים עוקבים של ה- Fitness של אורגניזם (תא) מסוים כאל יחידת זמן אחת (Time step), אזי יש לנו תאים (כמספר התאים ב-CA של הבעיה המקורית) המשוכנים במרחב (במקרה הרלוונטי בשורה), ואשר בכל זמן i (לאחר i Time steps), כל תא נמצא באחד ממספר סופי של מצבים, כאשר "מצב" כולל את ה- Genome וה- Fitness של אורגניזם.

ובמעבר לזמן i+1 מתעדכנים כל אחד מהתאים, תאורטית באופן מקבילי, בהתאם לפונקצית מעבר התלויה במצבם של התאים בשכונה לוקלית של התא, פונקצית המעבר במקרה הזה היא יוניפורמית לכל התאים, אבל היא לא דטרמיניסטית (בגלל שזו כוללת פעולות בהסתברויות מסוימות, וזאת להבדיל מהדוגמאות שראינו בכתה של פונקצית מעבר דטרמיניסטית, שניתנת לתיאור ע"י טבלת מעברים).

היתרון האפשרי בכך שהאבולוציה שנעשית על ה- CA היא בעצמה חישוב תאי, הנו (לפחות) שגם אותה ניתן לממש ע"י מודל תאי. לצורך העניין, ע"י הרחבת ההגדרות של כל תא ב- CA, כלומר תוך שימוש באותו מודל תאי של הבעיה המקורית שעליה אמורה האבולוציה לעבוד, וללא כל צורך במנגנון נוסף (על ה- CA) לצורך ביצוע פעולות החישוב הגלובליות שמתבצעות באלגוריתמים אבולוציוניים רגילים (Selection מתוך כל האוכלוסייה).

משבצת גנרית באלגוריתם של זיפר, הנה אופן חישוב ה- Fitness של כל תא.

בבעיית ה- Synchronization, ניתן באופן כללי להוסיף כגורם בחישוב ה- Fitness של תא מסוים, את השאלה "האם מצב התא ב- Time step האחרון הנו כשל מצב רוב התאים בזמן זה?". נראה שהוספת גורם זה תעזור לאבולוציה, אולם אז נדרשת פעולה גלובלית בחישוב ה- Fitness, וזה עומד בניגוד לרעיון הראשון שאנחנו מנסים להעביר, לפיו האבולוציה לפי האלגוריתם של זיפר, יכולה להתבצע במודל של חישוב תאי לכל דבר ועניין.

הרעיון השני הוא -

אם "החישוב האבולוציוני" לפי האלגוריתם של זיפר הנו חישוב תאי, עם אלמנט גלובלי משמעותי (שהרי פונקצית המטרה של האבולוציה, הנה Fitness כלשהו של האוכלוסייה כולה, ולא של קבוצות או פרטים בה), אזי אופטימיזציה הנכונה לחישוב תאי עם אלמנט גלובלי משמעותי, יכולה לעבוד גם על האלגוריתם האבולוציוני עצמו, ללא תלות בשימוש באופטימיזציה גם לגבי ה- CA עצמו (בקשר לבעיה המקורית).

אופטימיזציה כזו, שלמדנו, הייתה הכללת מסגרת ה"סביבה" הלוקלית של תא, מסביבת רדיוס R קבוע מן התא, אל סביבת C_N(1,d_i) באופן כללי.

אנחנו נסינו לבדוק את השפעת הרחבת הסביבה הלוקלית של אורגניזם באבולוציה, מסביבת רדיוס לסביבת C_N(1,d) (d קבוע), על האבולוציה, כאשר אנחנו משאירים את הבעיה המקורית של ה- CA, היא בעיית ה- Synchronization (החד ממדית), עם סביבת הרדיוס, עם R=1, וכמובן תוך שימוש בפעולות לוקאליות בלבד בחישוב ה- Fitness. במקרה זה הסביבה הרלוונטית לחישוב ה- Fitness שונה מהסביבה הרלוונטית לפעולות האופרטורים האבולוציוניים, אולם גם היא לוקלית.

חישוב ה- Fitness:

נניח שבזמן j, מחשבים את ה- Fitness של האורגניזם-תא i. נסמן תא (i,j).

אזי ערך ה- Fitness של האורגניזם נקבע לפי "שכונה" של ארבע התאים, ושווה למספר התאים ב"שכונה", שמתאימים למצב ה"שכונה" כפי שהיה לו הסינכרוניזציה הייתה מלאה בשלושת פרקי הזמן האחרונים, ומצב כל התאים בזמן האחרון j היה מצב התא (i,j). "השכונה" הרלוונטית לתא (i,j) הנה שני התאים הסמוכים (i-1,i+1) בזמן j, והתא i בזמנים j-1,j-2.

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

	x
	x
x	y	x

באיור:

למעלה - התאים בשכונה של y, בנוסף ל- y עצמו, מסומנים ב- x.

אם הקונפיגורציה האמצעית הנה הסופית, אזי ה- Fitness

של המשבצת האנלוגית ל- y, מחושב ביחס להתאמת

השכונה (ה- xים) עם הקונפיגורציה התחתונה, ושווה ל- 2.

	1
	1
0	0	1

	0
	1
0	0	0

הרחבת הסביבה הלוקלית לאופרטורים האבולוציונים:

לאחר שחשבנו Fitness של אורגניזם, מבצעים את אותם השלבים באלגוריתם של זיפר, אלא שמאגר האורגניזמים שמהם מתבצע ה- Selection עבור תא מסוים בנוסף אליו (התאים שמחושבים לטובת מציאת ה- “Fitter neighbors”, אשר האחרונים מהווים את המאגר לפעולות ה- Crossover וה-Mutation), הנו סביבת התאים C_N(1,d), עם d קבוע.

שאר הפרמטרים:

No. Generations 150

C (No. test-cases inputs) 50

M (No. time-steps for each initial input) 2 * No. Cells

Pc 0.8

Pm 0.001

ונדגיש שוב, הרצת ה- CA עצמו נעשתה עם סביבת הרדיוס הטריוויאלית R=1, כדי לבודד את המרכיב של האופטימיזציה מסוג זה (שינוי הסביבות הלוקליות) על האבולוציה.

ביצענו הרצות עבור CA-ים עם 100,200 ו- 300 תאים, ועבור כל אחד מהמקרים הרצנו עם פרמטר d שונה, הכולל לפחות את d=1 (סביבת רדיוס, R=1), ו- d=2.

כמדד להצלחה של CA, חישבנו AvgFit = ה- Fitness הממוצע לתא, לאורך 50 ההרצות עם input אקראי, מנורמל ל- [0,1].

גרפים של AvgFit vs Generations , בכל אחד מן המקרים האמורים:

בכל הנתונים הבאים ההפרדה הינה לפי קונפיגורציות C_N(1,d), עם ערכי d שונים, בממוצע על-פני 5 הרצות נפרדות.

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

בהקשר זה נוסיף כי יתכן והרצות עם ערך Pm גבוה יותר, יכולות היו (אולי) להתגבר על מקרים כאלו.

דיאגרמות Genome(transition table)-time:

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

100 תאים: משמאל לימין R=1, (1,2), (1,4)

300 תאים: משמאל לימין R=1, (1,2), (1,4)

הערה: ניתן לראות כי האבולוציה מסלקת (מהר מאוד) את כל הגנומים "האדומים". כאשר מנסים לנתח תופעה זו מבינים כי גנומים אלו מייצגים טבלאות מעבר אשר מכילות את המעבר של: "111" עובר ל-1. ברור לכל שכלל זה הינו קטסטרופאלי עבור בעיית ה-Synchronization.

מספר דיאגרמות Space-time מוצלחות:

כמה דוגמאות ריצה.

100 Cells with Evolution Radius=1 200 Cells with Evolution C_N(1,d) when d=2

300 Cells with Evolution C_N(1,d) when d=1,2,4

d=4 d=2 d=1

תוצאות:

קצב ההתכנסות ו-Scaling – ניתן לראות בבירור, כי בכל שלושת המקרים, האבולוציה של קונפיגורציה (1,1), שהיא למעשה סביבת רדיוס 1, התכנסה באופן בולט לעין לאט יותר.
במקרים של 200, ו- 300 תאים ההבדלים בין קונפיגורציה זו לשאר ניכרים עוד יותר, מה גם שניתן להבחין בהם בין קונפיגורציה (1,2), שהינה בעצם סביבת רדיוס = 2, לבין קונפיגורציות עם d > 2 (התכנסות מהירה יותר). זה המקום להדגיש שאנו מצפים להבדלים הללו, אולם אין הדבר מעיד שקצב ההתכנסות אמור לעלות עם המשך עליית הערך של d, כיוון שכפי שראינו בכתה, אנו מצפים לקשר ישר בין קצב ההתכנסות ל- ACD (ולא ל- d). לגבי ה- Scaling, אם נבחן את המערכת ביחס ליניארי בין מס' הדורות למס' התאים (נבדוק את התוצאות עבור מס' דורות השווה למחצית ממס' התאים), אנו נבחין כי ה- AvgFitness נשמר, וזאת גם עבור סביבת רדיוס 1, כלומר יש לנו Scaling טוב, אבל כנראה שהבעיה הזו קלה מידי בכדי להסיק מסקנות משמעותיות לגבי ה- Scaling של האופטימיזציה.

סיכום ודיון:

אנו מסבירים מדוע האלגוריתם האבולוציוני של זיפר הנו בעצם חישוב תאי, אם לא מבצעים פעולות גלובליות בקביעת ה- Fitness.
מכאן שניתן למדל את ה"חישוב האבולוציוני" ע"י הרחבה בלבד של מודל האוטומט התאי, ללא שימוש בפעולות גלובאליות. במודל המורחב לכל תא תהיה יותר מפונקציונאליות אחת, ובמקרה הספציפי: במקום סוג (Type) אחד של מצב, יש לנו שניים, האחד כפי שהיה קודם (במקרה שלנו 0 או 1), עם אותה טבלת מעברים ולפי אותו שעון, והשני מצב ה- Genome-Fitness, המשתנה לפי פונקצית מעבר אחרת, לפי סביבה לוקלית אחרת, בהתאם לפרקי זמן ארוכים יותר לפי אותו שעון.
בנוסף לכך, אנחנו מראים שלפחות אופטימיזציה אחת הנכונה ל- CA אשר פותר בעיה עם אלמנט גלובלי משמעותי, נכונה גם עבור ה"חישוב האבולוציוני".

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

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

כמו-כן, יתכן שניתן יהיה לראות הבדל משמעותי יותר שעושה האופטימיזציה שבדקנו, במקרה שה- CA שעובר אבולוציה פותר בעיה מורכבת יותר מ- Synchronization.

בניית מודל ו/או סימולציה לאוטומט תאי, עם ההרחבות שהצגנו, שבו התא גם עובר את האבולוציה בעצמו, ובנוסף, באופן כללי יותר, מודל שבו לכל תא יש פונקציונאליות מרובה. נניח, האם ניתן ליישם CA אשר בו לכל תא יש פונקציונאליות מרובה, לפיה ביחידות זמן שונות, התא משנה מצב בהתאם לפונקציות מעבר שונות וכו', ובכך ה- CA מבצע מספר חשובים שונים במקביל (כלומר, לאו דווקא להוסיף כפונקציונליות את ה"חישוב האבולוציוני").

לסיום, נציין כי גם התהליך האבולוציוני הביולוגי, הגם שהוא פועל על האוכלוסייה ככללה, הכלים העומדים לרשותו הנם לוקליים בעיקרם, למשל, יצירת גנוטיפ חדש משני גנוטיפים בדור קודם (המקבילה לאופרטור ה- Crossover), נעשית פעמים רבות מתוך מאגרים לוקאליים, גם "המאבק ההישרדותי" (שבבסיס ה- Selection) הנו לוקאלי, וכד' (לדוגמא, באבולוציה של צמח שמצוי בחבל ארץ גדול ההכלאות נעשות בין צמחים בנישות קטנות יותר, גם אם יש חפיפה בניהן).

קוד (Java):