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

תרגיל מס' 1

מגישים:  יאיר פילד 33612557

אורי לוביץ' 31387293

דוגמאות קוד מצויינות (או לחילופין – הקוד שלנו) ניתן למצוא בקיצורים הבאים:

ass1_files\Main.java

ass1_files\GA.java

ass1_files\Organism.java

ass1_files\ExcelWriter.java

ass1_files\jxl.jar

שאלה 1

הוכח: כל מחרוזת באורך L, הינה פרט אחד מתוך 2^L סכימות.

הוכחה באינדוקציה על L.

נסמן H(T), קבוצת הסכמות שמחרוזת T שייכת אליהם.

בסיס: L=1, תהי T מחרוזת באורך 1, ובה"כ T="1", אזי H(T) = {"1", "*"}.

נניח נכונות האינדוקציה עבור מחרוזות באורך k<L. ונוכיח עבור L.

תהי T מחרוזת כלשהי באורך L, בה"כ התו האחרון בה הינו "1", ומכאן נובע:  T = S"1", עם S מחרוזת באורך L-1. לפי הנחת האינדוקציה, |H(S)| = 2^L-1.

ומכאן נובע:

מ.ש.ל.

שאלה 2

שאלה 3

מסקנות:

1. הבעיה קלה, וההתכנסות לאופטימום הינה מאוד מהירה, ללא קשר חד לסט הפרמטרים (לדוגמא, בהסתברות של 50% הביט הMSB-, הינו 1, וכבר בדור G0, כמחצית מהאוכלסיה מייצגים מספרים בחצי העליון של תחום ה-Fitness, וכן הלאה, כך שבאוכלוסיה של 100 פרטים לפני תחילת האבולוציה כ-10 מהם נמצאים בעשיריון העליון של תחום ה-Fitness).
2. ניתן לשים לב שריצות עם פרמטר Pm גבוה יוצרות תהליך חיפוש עם מאפיינים סוכסטים, אשר מקשים על ההתכנסות , בעיקר של הממוצע.
3. לגבי גרף ה-Best Fit, ולגבי פרמטר Pc, לא ניתן להסיק מסקנות ברורות.

שאלה 4

מסקנות:

1. בבעיה הזו לא ניכרים הבדלים אקוטיים בהחלפת הייצוג מ- Binary ל- Gray.
2. ניתן לומר באופן כללי שיש שיפור מסויים בהתכנסות ה- Average Fitness בייצוג Gray, אולם הבדלים אלו יכולים להיות במסגרת סטיית מדגם.
3. לסיכום, לא נראה שבבעיה זו ייצוג בקוד Gray הצליח לשפר את פעולת אופרטור המוטציה, לפחות לא באופן ניכר לעין.

שאלה 5

"יש לי רק דבר אחד לומר לכם בשם כולם... <פאוזה>

 היה ..... נחמד, נחמד, היה ממש נחמד... "