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

תרגיל מס' 2

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

אורי לוביץ' 31387293

בדומה לפעם קודמת, דוגמאות קוד ניתן למצוא בקיצורים הבאים:

ExcelWriter.java - appears in all

jxl.jar - appears in all

GA.java - from Q1 and Q2

Organism.java - from Q1 and Q2

Main.java - from Q1 and Q2

GA.java - from NQueen

Organism.java - from NQueen

Main.java - from NQueen

GA.java - from TSP

Organism.java - from TSP

Main.java - from TSP

שאלה 1

מסקנות:

1. כל שלושת שיטות ה-Selection, הראו התכנסות מהירה של ה-Best Organism לכיוון האופטימום ונבדלו בקצב ההתכנסות, וכן בתנודתיות של ה-Average Fitness.
2. ניתן למיינם מהטוב ביותר (משמאל לימין): Tournament > Rank > FitnessPorp.
3. הסיבה לכך נובעת מהתפלגות פונק' ה-Fitness. לרוב ה-Organismים ישנם ערכי fitness קרובים זה לזה (וההבדל היחסי ביניהם הינו קטן), וה- Tournament מביאה לידי ביטוי משמעותי יותר הבדלי fitness קטנים יותר.
4. הערה - חסרונות של שימוש בשיטת ה- Tournament (אם קיימים...), לא יראו במקרה זה, שכן הבעייה קלה מידי.
5. בשאלה זו, כמו גם בשאר השאלות, אם לא ציינו אחרת, השתמשנו בערכים Pm=0.05, Pc=0.7.

שאלה 2 – The Card Problem

פרמטרים:

ייצוג: בחרנו בייצוג הפשוט והטריוואלי של מחרוזת ביטים שבה הביט במקום ה-i מייצג את מס' הערימה בה נמצא הקלף ה-i (0=ערימת החיבור, 1=ערימת הכפל).

Fitness: הרכבנו פונקציה כמכפלת שתי פונקציות שונות, אחת לכל ערימה (שתיהן מנורמלות בתחום [0,1])

Fitness יחסי לסכום האיברים בערימה 0- פונקצית פרבולה עם שורשים ב-0, וב-72, וכן נק' מקסימום ב-36 ( (Fit1 = iSum*(72.0-iSum)/(36*36.0 )

Fitness יחסי למכפלת האיברים בערימה 1– הרכבנו שתי פונקציות, אחת ליניארית עבור ערכים הקטנים מ-360, והשניה שורש של ההופכי עבור הערכים הגדולים מ-360.

(dFit2 = (iProduct <= 360) ? iProduct/360.0 : Math.pow(( 360 /iProduct ),0.5 )

המטרה היתה להתמודד עם קצב עליית פרמטר המכפלה מחד, ולאפשר עליה של הפרמטר גם מעט מעל 360 (מבלי להוריד את ערך ה-Fitness לאפס de-facto)

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

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

וסלחנות גרמה לתנודתיות ראנדומית ומנעה התכנסות)

את הבעיה הזו פתרנו ע"י Elitism של 10% מהאוכלוסיה.

הרצות עם Elitism: תוצאה סופית (ממוצע על-פני 100 הרצות) - 359.26 ; 35.2

שאלה 3 – The N-Queen Problem

ייצוג: הייצוג המוצא: רצף של Integers, ובו המספר j במקום ה-i מייצג העמדה של מלכה (אדומה) בעמודה ה-i והשורה ה-j.

Fitness: מספר זוגות המלכות המאיימות אחת על השניה.

Selection: Fitness Proportionate + Elitism

Mutation: Swap בין שני איברים ראנדומים.

CrossOver: עבור כל אחד משני ה"הורים" נמצא את הרצף הארוך ביותר של איברים סמוכים אשר אין ביניהם קונפליקטים ב"רמה העמוקה ביותר" (הסבר עוד מעט).

נבנה את הגנוטיפ ע"י שרשור הרצף המדובר של הורה א' עם שאר האיברים לפי סדר הופעתם בהורה ב' (החל מתחילת הרצף המדובר של הורה ב').

רמה עמוקה ביותר ללא קונפליקטים, מהי? נשים לב כי בייצוג שהשתמשנו, מלכה באינדקס (=עמודה)i ובשורה j, "מאיימת" על מלכה באינדקס

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

של 1. בדומה, נגדיר רמות עמוקות יותר.

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

אבל עד פרמטר N=100 שבדקנו, זמני הריצה הכוללים היו קצרים. מנגד, בדקנו גם עבור N=200, ונדרשנו לכ- 3 שעות.

תצוגת הלוח עבור הפתרונות עם פרמטר N=50, N=20 בהתאמה.

ולמי שממש מעוניין פתרון לבעיה עבור N=200 N=200 (לקח כמה שעות, אבל נמצא בכל 3 ההרצות, לאחר 1800, 2700 ו 3600 דורות).

"Rook takes queen, Bishop takes queen, Pawn takes queen, Everybody takes queen. Gangbang!!!"

(the mad history of the world I)

שאלה 4 - TSP

ייצוג: Path

Fitness: חסם עליון שבחרנו (מס' הערים * הצלע הארוכה ביותר) פחות אורך המסלול – מנורמל בתחום [0,1]

Selection: Tournament (בין חמישה) + Elitism (10%)

Mutation: 2 Point swap, (Pm=0.1)

Crossover: OX (לוקחים תת-מסלול מהורה אחד ומשלימים לפי סדר ההופעה בהורה שני), (Pc=0.7)

השפן: Local Improvement הלוקח כל אחד ממועמדים לדור החדש (לאחר הפעלת האופרטורים האחרים), משכפל אותו 5 פעמים, כאשר לכל שכפול מבצעים אופטימיזציה

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

האופטימיצזיה מסתמכת על העובדה כי בפתרון לבעיית TSP, בהנתן תת-מסלול בפתרון - v(1)àv(2)à…v(k)àv(k+1), אזי זהו המסלול הקצר

ביותר היוצר מ v(1), מסיים ב v(k+1), ועובר דרך כל הקדקדים v(2) עד v(k) (וכולם מופיעים בו פעם אחת בלבד).

השיפור המקומי שלנו בוחר קדקד v(1) באקראי, ומוצא את המסלול הקצר ביותר ממנו אל v(5), תוך מעבר בשלושת הקדקדים שבינהם.

בסה"כ מדובר בבחירת המסלול הטוב מבין 6 אופציות (=3!).

מסלולים הכי קצרים (באורך כולל 1243):

Path: [0, 1, 2, 22, 21, 20, 5, 8, 23, 7, 14, 13, 4, 12, 3, 15, 19, 6, 10, 11, 16, 18, 17, 9]

Path: [0, 2, 22, 21, 20, 5, 8, 23, 7, 14, 1, 13, 4, 12, 3, 15, 19, 6, 10, 11, 16, 18, 17, 9]

(סדר הערים כמופיע בטבלה, כאשר ת"א הינה 0)

 "הוא הגיע אל הארץ בדרכים עקלקלות, הוא היה סוכן חשאי לא רצה להתגלות..."