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

202-1-5171

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

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

איל ליס , 040170789

דוד סויסה , 040580003

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

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

תרגיל הגשה 1

שאלה 1

מחרוזת הביטים 000 שייכת לשמונת הסכמות הבאות:

א) ***

ב) 0**

ג) *0*

ד) **0

ה) 00*

ו) 0*0

ז) *00

ח) 000

שאלה 2

fitness:

שאלה 3

מימוש אלגוריתם גנטי :

Population size = 100.

Single-point crossover rate p_c=0.7.

Bitwise mutation rate p_m=0.001.

The goal is to maximize the function x*|tan(x)| .

Range = [0,256] radians.

Run the GA five times for 1000 generations.

הקוד: Question3.java

בתוכנית הנ"ל כל אינדיבידואל מיוצג ע"י bitstring באורך 10 ביטים, ועל כן ישנם 1024 אינדיבידואלים אפשריים בתחום [0,256] . הנקודות בתחום בקפיצות של 0.25.

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

גרף הפונקציה f(x)= x*|tan(x)| :

· חשוב לציין כי גרף זה מופיע ללא נקודה (11776666.62, 177.5) השייכת לגרף, לטובת תצוגה ברורה יותר.

· ניתן לראות כי הנקודה (11776666.62 , 177.5) היא נקודת המקסימום אך ישנן נקודות מקסימום מקומיות רבות.

· כמו כן הדגשנו בגרף את נקודות המקסימום שיצאו בתוכנית בחמשת ההרצות שנציג.

· בהרצה השנייה יצאה נקודת המקסימום (11776666.62 , 177.5) שלא מופיעה בגרף.

הרצה 1

Average	Best	Generation
1798.227999	7546.797615	0
2789.48464	7546.797615	1
4341.272422	12500.15789	2
12377.10317	12500.15789	200
12377.10317	12500.15789	400
12378.8475	12500.15789	600
12500.15789	12500.15789	800
12375.43174	12500.15789	999

נשים לב כי בהרצה זו ערך המקסימום שנקבע (12500.15789) לא הוגרל לאוכלוסיה בדור הראשון אלא נוצר באבולוציה בעקבות crossover & mutation והפך להיות דומיננטי באוכלוסיה.

הרצה 2

Average	Best	Generation
11658900	11776666.62	0
11658900	11776666.62	1
11305611	11776666.62	2
11541140	11776666.62	200
11541139	11776666.62	400
11776666	11776666.62	600
11658903	11776666.62	800
11658900	11776666.62	999

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

מכיוון שאינדיבידואל זה ( 11776666.62 , 177.5 ) בעל fitness גדול בהרבה משאר האוכלוסייה הוא מקבל הסתברות של p(i) = 0.98 ובכך משתלט במהירות על האוכלוסייה.

הרצה 3

Average	Best	Generation
20328.68	37749.07	0
35882.09	37749.07	1
37372.76	37749.07	2
37376.07	37749.07	200
36996.68	37749.07	400
37373.80	37749.07	600
36995.59	37749.07	800
37749.07	37749.07	999

בהרצה 3 ובהרצה 5 נמצאה אותה נקודת מקסימום (37749.07).

הרצה 4

Average	Best	Generation
7870.05	22499.84	0
17198.46	22499.84	1
20452.20	22499.84	2
22275.72	22499.84	200
22275.72	22499.84	400
22276.14	22499.84	600
22054.15	22499.84	800
22052.15	22499.84	999

הרצה 5

Average	Best	Generation
793.74	3846.94	0
975.87	3846.94	1
1704.48	37749.07	2
37371.95	37749.07	200
37749.07	37749.07	400
37372.35	37749.07	600
37001.82	37749.07	800
37374.82	37749.07	999

נשים לב כי בהרצה זו ערך המקסימום שנקבע (37749.07) לא הוגרל לאוכלוסיה בדור הראשון אלא נוצר באבולוציה בעקבות crossover & mutation והפך להיות דומיננטי באוכלוסיה.

בהרצה 3 ובהרצה 5 נמצאה אותה נקודת מקסימום.

מסקנות משאלה 3

• הפונקציה f(x)= x*|tan(x)| מכילה נקודות מקסימום מקומיות רבות. ישנן נקודות רבות שלא מוגרלות בדור הראשון ולא נוצרות באבולוציה בעקבות crossover & mutation ולכן בכל הרצה נקבל נקודת מקסימום מקומית שונה שאינה בהכרח נקודת המקסימום של התחום כולו.
• בכל הרצה יש נקודה מקסימאלית שמשתלטת על הדור והופכת להיות הדומיננטית כבר בדורות הראשונים (עד 3 דורות).
• הממוצע מתאזן לאחר כ- 15 דורות ומתקרב מאוד (מלמטה) לנקודת המקסימום שנמצאה בשל השתלטות של האינדיבידואל הגבוה על האוכלוסייה.
• אילו היינו מגדילים את גודל האוכלוסייה היינו מקבלים תוצאות גבוהות יותר לרוב כי היה סיכוי גדול יותר למצוא נקודות גבוהות יותר שיהפכו לדומיננטיות אך זמן ההרצה היה מתארך.
• עפ"י הנתונים ההסברות למוטציה היא 0.001Pm = כלומר בכל דור משתנה ביט אחד לאינדיבידואל אחד בממוצע (אוכלוסיה בגודל 100 שלכל ייצוג 10 ביטים). שינוי של Pm מ- 0.001 ל- 0.1 יוביל כמעט בכל הרצה לנקודת המקסימום בגרף (11776666.62) מכיוון שנתון זה משפיע על הכמות ה- mutation שמתבצעת וכך יש סיכוי גדול יותר להגיע לנקודה זו. ברגע שאינדיבידואל זה מופיע בדור מסוים באבולוציה הוא משתלט במהירות והופך לדומיננטי בגלל הסתברות גבוהה של p(i) = 0.98 שהוא מקבל.

שאלה 4

דרכים להרצה מהירה יותר של אלגוריתם גנטי:

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

· ניתן להריץ את האלגוריתם פחות דורות באבולוציה , וכך הוא יסתיים מהר יותר. במקרים מסוימים הרצה על מספר דורות קטן יותר לא תשפיע על התוצאות (כמו בשאלה 3, היה ניתן להפסיק את ההרצה כבר בדור ה 20 במקום ה- 100) ובמקרים מסוימים מספר דורות קטן לא יספיק על מנת להתכנס לפתרון דומיננטי וטוב.

· ניתן להריץ את האלגוריתם עם ייצוג קטן יותר וכך הוא ירוץ מהר יותר. הרצה עם ייצוג קטן תגרום לפחות חישובים ופחות מוטציות ועל כן תחסוך בזמן ריצה. גודל הייצוג משפיע על רמת הדיוק של האינדיבידואל אך גם על זמן הריצה של האלגוריתם. לדוגמא בשאלה 3 הייצוג היה מחרוזת באורך 10 ביטים.

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

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

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

• שינוי בערכי ההסתברויות Pm , Pc במהלך הריצה בהתאם לתוצאות הזמניות המתקבלות.
• הסתברות Pm נמוכה שתמנע תוצאות רנדומאליות שאינן מתכנסות לפתרון דומיננטי.
• שימוש בטכניקות crossover , mutation מתוחכמות יותר שנלמדו בהרצאה

שאלה 5

בניית אלגוריתם גנטי לבעיית הגנב 0/1. קיבולת מקסימאלית של תרמיל הגב = 625.

בתוכנית הנ"ל כל אינדיבידואל מיוצג ע"י bitstring באורך 50 ביטים (ביט עבור כל פריט אפשרי), ועל כן ישנם (50^2) אינדיבידואלים אפשריים.

הרצת האלגוריתם הגנטי במשך 500 דורות.

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

הקוד: Question5.java

הרצה a

Single-point crossover rate p_c=0.7

Bitwise mutation rate p_m=0.001

Average	Best	Generation
506.54	714	0
588.145	768	10
643.485	794	20
738.06	883	100
799.375	892	200
837.355	899	300
854.655	931	400
874.215	923	499

הרצה b

Single-point crossover rate p_c=0.4

Bitwise mutation rate p_m=0.001

Average	Best	Generation
506.045	701	0
615.195	790	10
651.92	813	20
764.825	858	100
799.825	885	200
831.275	904	300
829.3	911	400
832.4	908	499

הרצה c

Single-point crossover rate p_c=0.1

Bitwise mutation rate p_m=0.001

Average	Best	Generation
506.045	701	0
614.065	734	10
666.57	777	20
745.38	849	100
801.49	868	200
822.655	887	300
830.28	874	400
828.725	883	499

הרצה d

Single-point crossover rate p_c=0.7

Bitwise mutation rate p_m=0. 01

Average	Best	Generation
506.045	701	0
559.64	755	10
598.12	799	20
683.39	844	100
646.375	854	200
682.08	842	300
654.95	897	400
693.66	860	499

הרצה e

Single-point crossover rate p_c=0.7

Bitwise mutation rate p_m=0. 1

Average	Best	Generation
498.49	772	0
520.07	724	10
516.02	745	20
509.205	729	100
515.285	757	200
483.64	701	300
496.44	724	400
513.29	746	499

סיכום שאלה 5

מסקנות עבור ה- Best:

בניסוי 1 קיבלנו את התוצאות הטובות ביותר. החל מהדור ה- 300 ה- Best fitness מתייצב מעל ל- 900 וממשיך לעלות לאורך כל האבולוציה (מתכנס לפתרון), מה שמראה כי האבולוציה משפרת את האוכלוסייה.

התוצאה הגבוהה ביותר בניסוי זה ובכל הניסויים הופיעה בדור 476 והיא 940.

ניסוי 2 מציג תוצאות דומות אם כי מעט נמוכות מניסוי 1. ניסוי 3 עדין מציג Best fitness גבוה אם כי השונות נמוכה (גרף בקו ישר יחסית) בגלל פחות (Pc) crossover .

ניסוי 4 וניסוי 5 הם הנמוכים ביותר מכיוון שהשונות גבוהה מאוד (גרף עם רעשים) הנגרמת בגלל mutation (Pm) רבים שמונעים מהאוכלוסייה להתכנס לפתרון עם fitness גבוה.

ניסוי 5 שהוא הגרוע ביותר מציג תוצאות רנדומאליות לחלוטין.

מסקנות עבור ה- Average:

בניסוי 1,2,3 ה- Average מתקרב ל- Best ועולה באופן קבוע, מה שמראה כי האבולוציה משפרת את האוכלוסייה.

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

ניסוי 4 מראה שיפור רק בהתחלה ואח"כ האוכלוסייה לא משתפרת אלא נשארת באותו ממוצע הרחוק מ ה- Best עם שונות גבוהה (גרף עם רעשים).

ניסוי 5 שהוא הגרוע ביותר מציג תוצאות רנדומאליות לחלוטין עם שונות גבוהה (גרף עם רעשים) הנגרמת בגלל mutation (Pm) רבים שמונעים מהאוכלוסייה להתכנס לפתרון עם fitness גבוה מכיוון שאינדיבידואלים טובים מתקשים לשרוד בהסתברות mutation כזו.

מסקנות כלליות:

• אנחנו בחרנו להריץ את האלגוריתם שכתבנו על אוכלוסייה בגודל 200. חשוב להדגיש כי מניסויים שערכנו עם אוכלוסיות גדולות (500) וקטנות (100) יותר נובע בבירור כי האבולוציה עובדת טוב יותר עבור אוכלוסיות גדולות ומגיעה לתוצאות טובות יותר משמעותית אך זמן הריצה ארוך יותר.

• התוצאה הטובה ביותר שהצלחנו להגיע אליה הייתה 946 עם משקל 623 והתקבלה בדור 547 בניסוי. הממוצע בניסוי זה עבור האוכלוסייה בגודל 500 היה 890.626.

הייצוג בתוצאה זו הוא: 11111010110110011011111101110111110010111111111010 .

• בכדי להגיע למשקל מדויק של 625 שינינו את פונקצית ה- fitness כל שתעדיף משקל גבוה שאינו חורג מ- 625. ואכן אינדיבידואלים שונים הצליחו להגיע למשקל זה.

דוגמא לייצוג בעל משקל 625: 00111000001100110110111101000001010110101110110101 .

• בניסויים שערכנו בשאלה 3 ראינו כי כאשר אינדיבידואל הגיע ל- fitness גבוה הוא נשאר ה- best עד לסוף התוכנית, ואילו פה התוצאה ה- best משתנה ואף יכולה לקטון. הסיבה לכך היא שבשאלה 3 נקודות המקסימום המקומיות גדולות בהרבה ביחס לשאר האוכלוסייה ולכן מקבלות הסתברות p(i) גבוהה מאוד ב- selection. ואילו בשאלה זו אין שוני גדול בין האינדיבידואלים באוכלוסיה וההסתברות p(i) אינה שונה בהרבה בין האינדיבידואלים.

• במאמר שקראנו: "Evolutionary Algorithms", M. Tomassini נכתב כי המדדים הנפוצים לאלגוריתם גנטי הם Pc = 0.6 , Pm = 0.01 .

מהרצות שערכנו בבעיית הגנב 0/1 שלנו עם פרמטרים אלו עולה כי הפרמטרים מהניסוי הראשון (Pc = 0.7 , Pm = 0.001 ) טובים יותר לבעיה זו.

- סוף -