הקדמה
אבולוציה ביולוגית היא תהליך כ״כ מוצלח עד שגרם להתפתחות של יצורים חד תאיים לכדי יצורים מורכבים כמו בני אדם. מה יקרה אם נשתמש באבולוציה על מנת לבנות בינה מלאכותית ? זאת השאלה שהובילה להתפתחות התחום במדעי המחשב שנקרא אלגוריתמים אבולוציוניים, זוהי משפחה של אלגוריתמי בינה מלאכותית המבוססים על רעיונות השאובים מאבולוציה בטבע על מנת לפתור בעיות.
מטרה
המטרה של אסטרטגיה אבולוציונית דומה לזו של למידה חיזוקית (Reinforcement Learning) ובאופן מדויק יותר לזו של Q-Learning. המטרה היא, בהינתן עולם וסוכן למצוא את המדיניות (Policy) שעל פיה הסוכן צריך לפעול כדי להצליח בצורה הטובה ביותר לעמוד ביעדים שניתנו לו. הסוכן יכול להיות למשל שחקן במשחק מחשב ,רובוט שמנקה את הבית או טייס של מטוס קרב והיעדים יכולים להיות לנצח במשחק בציון גבוהה ככל הניתן, לנקות את הבית כמה שיותר מהר בלי לפספס אף חלק או להפיל כמה שיותר מטוסי אוייב. כדי להבין את הכוונה ב״מדיניות״ אפשר לחשוב על מודל כזה:
המדיניות היא בעצם הדרך שבה הסוכן יקבל החלטה לבצע פעולה כלשהי בהינתן מצב מסויים.
אז איך זה עובד?
מכיוון שאנחנו מדברים על מדעי המחשב אי אפשר בלי קצת וקטורים ומטריצות. אם נתאר את המצב של העולם שלנו כוקטור ואת המדיניות בתור מטריצה אז תוצאת המכפלה בניהם תהיה וקטור של הסתברויות עבור כל אחת מהפעולות האפשריות.
כמובן שזוהי הפשטה של הרעיון אבל נוכל להשתמש בה כדי להבין את דרך הפעולה של האסטרטגיה האבולוציונית. האלגוריתם מבוסס ביסודו על הרעיון של מוטציה וברירה טבעית, כך שבתהליך איטרטיבי (בלולאה) ניצור מוטציות ונבחר את הטובות ביותר. בכל שלב נייצר אוכלוסיה ,האוכלוסיה תהיה מורכבת מקבוצה גדולה של עותקים של המדיניות כאשר לכל אחד מהם נבצע מוטציה אקראית .ניתן לכל צאצא באוכלוסיה לפעול בעולם ולאחר מכן נתבונן בביצועים שלו. נאסוף את הצאצאים שמביאים את התוצאות הטובות ביותר במה שנקרא מטא-אוכלוסיה ונבצע איחוד שלהם כך שנקבל נקודת מוצא חדשה או ״אב״ עבור האוכלוסיה שבשלב הבא בלולאה, כך נחזור שוב ושוב עד שנקבל מדיניות טובה.
קצת יותר פרטים
עכשיו כשהבנו באופן בסיסי איך עובד האלגוריתם נתאר אותו בצורה קצת יותר מתמטית (אם לא בא לכם אפשר לקפוץ ישר לחלק הבא). נסמן ב -θ את המדיניות, F תהיה הפונקציה שמעריכה את ביצועי המדיניות על העולם, λ מייצגת את גודל האוכלוסיה ו -μ מייצגת את גודל המטא-אוכלוסיה. נאתחל את המדיניות בערכים רנדומליים ובכל שלב המוטציה תהיה הוספת דגימה אקראית מהסתברות נורמלית כפול גודל צעד הלימוד שנסמנו σ (ניתן לחשוב עליו כ Learning Rate). על מנת לחשב את מדיניות הבסיס החדשה עבור האיטרציה הבאה נבצע ממוצע משוכלל של μ הצאצאים הטובים ביותר, צעד זה מתבצע ע״י שימוש בפרמטר wi שהוא סקלר המתפקד כמעיין נרמול. נכפיל את הממוצע בצעד הלימוד σ ונחבר זאת למדיניות הבסיס של הצעד הנוכחי. כעת יש בידינו את כל החלקים הדרושים ע״מ להבין את האלגוריתם המלא:
https://arxiv.org/pdf/1802.08842.pdf
למה זה טוב?
לאסטרטגיה אבולוציונית יש שתי יתרונות בולטים על פני שיטות קלאסיות של למידה חיזוקית.
1 – האלגוריתם אינו מוטה כמעט להשפעות המתכנת כך שיש לו חופש גדול יותר להתפתח.
2 – האלגוריתם ניתן להרצה בצורה מקבילה באופן פשוט מאוד ולכן חוסך זמן רב בלימוד בהינתן כוח חישוב רב מספיק. למען האמת בכל שלב בלולאה אין קשר בין הצאצאים בכלל ולכן כל אחד מהם יכול לפעול במקביל בצורה שאינה קשורה לאחרים ורק בסיום הזמן המוקצה לשלב בלולאה יאוחדו התוצאות שלהם ויווצרו צאצאים חדשים.
לכן הגורם היחד שמשפיע על גודל האוכלוסיה הוא כמות המשאבים.
דוגמא לביצועי האלגוריתם ניתן לראות בוידאו הבא:
בוידאו רואים שחקן של משחק המחשב Qbert שאומן למשך 5 שעות בלבד בשימוש באוכלוסיה בגודל 400 ופיתח שיטת משחק מעניינת מאוד .ראשית ניתן לראות ב 6:24 שהשחקן קופץ ממקום למקום ומחכה שהיריב יזוז לכיוונו כדי שיוכל לנצח במשחק כלומר השחקן למד ״להטעות״ את היריב .ולאחר מכן ב 6:27 ניתן לראות באג שהשחקן גילה במשחק שלא היה ידוע עד כה שמאפשר לשחקן לקבל אינסוף נקודות במשחק.
קישורים
חלק מהכתבה מבוססת על המאמר הזה כמו כן ניתן למצוא מימוש שלי הכולל הרחבה לאלגוריתם זה בפרויקט שלי בגיטהאב.
