אלגוריתמים אבולוציונים
27/09/2018
מהנדסים תמיד השתמשו בכלים מתמטיים כדי לתכנן ולבנות דברים. אחד השימושים המשמעותיים ביותר למתמטיקה שמהנדס עושה הוא האופטימיזציה (מיטוב בעברית) [1]. מהנדס אוירונאוטיקה למשל, יתאר את כח העילוי במשוואות, וכדי ליצור כנף יעילה יותר - יחפש פתרון אופטימלי (מיטבי) לאותן משוואות, כזה שיוביל, נגיד, לגרר מינימאלי. פתרון הוא אוסף של ערכים מספריים שמקיים את המשוואות. כך למשל, אורך, רוחב ופרופיל חתך של כנף, מהווים פתרון של משוואות העילוי והגרר. בדרך כלל, יש יותר מפתרון אחד למשוואות (במקרים רבים יש מספר אינסופי של פתרונות), והמהנדס יחפש את הטוב מביניהם. הקשר בין הערכים המספריים המתארים את צורת הכנף לגרר ניתן לתיאור על ידי פונקציה, ותהליך המיטוב הוא למעשה חיפוש הנקודה הכי גבוהה (או נמוכה) של הפונקציה. בדוגמה לעיל למשל, נחפש את צורת הכנף שנותנת את הגרר הנמוך ביותר. כשאתם שומעים על רכב חדש בעל ביצועים טובים יותר, או על מכונת כביסה יעילה יותר, מאחורי כל אלה נמצאים מהנדסים שהשקיעו מאמץ לשיפור המוצר ולמציאת פתרון טוב יותר למשוואות. אחד הכלים המתמטיים לאופטימיזציה הוא אלגוריתמים אבולוציונים [2].
במקום לנסות לחפש פתרון אופטימלי על ידי חקר המשוואות, אלגוריתמים אבולוציוניים משתמשים במודל ששואב השראה מתורת האבולוציה. את עקרון פעולת האלגוריתם ניתן לתאר בקווים כלליים כך: תארו לכם אוכלוסיה של ג'ירפות חייזריות. כל לילה תוקפים אריות מפלצתיים את העדר ואוכלים את הג'ירפות הנמוכות. ביום הג'ירפות ששרדו את הלילה מתרבות, וחוזר חלילה. תינוק ג'ירף יהיה לרוב בעל גובה דומה להוריו. אבל מדי פעם, כשג'ירף תינוק נולד, הגנים שלו עוברים מוטציה וגובהו שונה מזה של הוריו. ככל שהג'ירף גבוה יותר, כך הסיכוי שלו לשרוד גדול יותר. כמו כן, זוג ג'ירפות גבוה יוליד תינוק גבוה.
אלגוריתם אבולוציוני עובד בצורה דומה. האוכלוסיה היא לא של ג'ירפות חייזריות, אלא של פתרונות מתמטיים. בכל צעד, האלגוריתם "יזרוק" את הפתרונות הפחות טובים, ימחק אותם מהזיכרון והם יעלמו כמו ג'ירפות נמוכות שהאריות טרפו. חלק מהפתרונות יבחרו לרביה - בדרך כלל המוצלחים יותר. משני פתרונות ש"יזדווגו" יווצר פתרון חדש שיהיה קרוב לפתרונות המקוריים. לפעמים, בהסתברות מסויימת, יוכנס שינוי קל (מוטציה) בפתרון החדש.
המודל שתואר כאן רק מזכיר במקצת את המודל שפתחו ביולוגים לתיאור הברירה הטבעית. אפשר לחשוב עליו כעל מודל מפושט, בסיסי, אולי אפילו ילדותי של האבולוציה. הדבר המדהים הוא, שאפילו המודל הבסיסי הזה עובד! המעגל הזה, של השמדת פתרונות פחות טובים, בחירת הורים ויצירת צאצאים חוזר על עצמו. היות שהפתרונות הפחות טובים נזנחים והיותר טובים מתרבים, האוכלוסיה תתקרב עם הזמן לאופטימום - הפתרון הכי טוב. היווצרות מוטציות תבטיח שהחיפוש לא ייתכנס מהר מדי לפתרון שהוא טוב - אבל לא הכי טוב (מינימום או מקסימום מקומיים).
דוגמה לאופטימיזציה בעזרת אלגוריתם אבולוציוני ניתן לראות בסרטון המלווה. בסרטון נתונה פונקציה דו-ממדית שהגרף שלה מקבל צורה של אוכף. הפונקציה מוגדרת על כל זוג מספרים x ו- y, זאת אומרת שלא משנה איזה זוג מספרים נבחר ל x ו - y, המשוואה של הפונקציה תתאים להם ערך שלישי. בדוגמה של מהנדס האוירונאוטיקה, זוג המספרים (פתרון) הם האורך והרוחב של הכנף. הערך של הפונקציה הוא הגרר, שאותו רוצים כמובן להפחית ככל שאפשר. x=3 ו- y=2 למשל, הם פתרון של המשוואה, כלומר כנף באורך 3 ורוחב 2.
בדוגמה שבסרטון, פתרון נחשב יותר טוב ככל שהערך שהפונקציה מחזירה עבורו יותר קטן. אף שקשה לראות זאת, לפונקציה שבדוגמה יש מינימום והוא נמצא בנקודה (x=1,y=1). הנקודות הורודות בסרטון הן הפתרונות האפשריים. כמו עם הג'ירפות, פתרונות שהם לא נמוכים מספיק לא ישרדו. פתרונות טובים נבחרים להתרבות, ולפעמים יש מוטציות. האלגוריתם לא "יודע" איך נראית הפונקציה. הוא פשוט מייצר פתרונות ובודק מה הערך שהם מקבלים. הפתרונות מתקרבים לנקודת המינימום, בזכות האלגוריתם. (למיטיבי לכת, ניתן למצוא הסבר מעמיק יותר בסוף הטקסט.)
עכשיו, תארו לכם ש x ו- y לא מתארים אורך ורוחב של כנף מטוס, אלא מספרים שמייצגים קוטר של גלגל אופניים ומרחק בין הגלגלים, ושהפונקציה היא פונקציה מסובכת שמתארת צריכת אנרגיה של רוכב בטור דה פראנס. כשהמחשב פותר את המשוואה, הוא למעשה מייצר הדמייה של אלפי זוגות אופניים שונים, ובודק כמה הן טובים.
כמות הפתרונות שתיבחר להשמדה או לרביה, כמו גם סוג הרביה וה"קידוד הגנטי" של הפתרון, הם שמבדילים בין סוגי האלגוריתמים השונים. במשפחת האלגוריתמים האבולוציוניים ניתן למצוא את האסטרטגיה האבולוציונית [3], אלגוריתם גנטי [4], תכנות גנטי ועוד [5]. לעיתים קרובות, המשוואות שמהנדסים מנסים למטב מאוד מסובכות וקשות לפתרון. לפעמים המהנדסים אפילו לא יודעים מה המשוואה והם מקבלים ערכים לפתרונות על ידי ניסוי. כאן בא לידי ביטוי היתרון הגדול של אלגוריתמים אבולוציונים: אין צורך להתעמק במשוואות בשביל למצוא פתרון מיטבי. לא ניתן להוכיח שהאלגוריתמים האלה ימצאו את הפתרון הכי טוב, אבל מבחינה פרקטית הם עושים עבודה טובה מאוד. החיסרון הגדול של האלגוריתמים האלה, הוא שנדרש כח חישוב גדול מאוד בשביל להעריך איזה פתרון טוב ואיזה פחות, ולכן זמן החישוב כשמשתמשים באלגוריתמים כאלה הוא בדרך כלל גבוה מאוד.
אז מתי כדאי להשתמש באלגוריתמים האלה? איזה דרך פתרון היא המיטבית? אולי צריך לעשות גם לשאלות האלה מיטוב, ואולי נענה עליהן בקרוב.
לקריאה נוספת ומקורות:
הפונקציה בדוגמה היא פונקציית רוזברוק: f = (a-x)2+b(y-x2)2. פונקציות מהסוג הזה נראות כמו אוכף, שבמרכזו "עמק". למצוא את העמק הנמוך זה די קל, אבל בתוך העמק מתחבאת נקודת מינימום גלובאלית שקשה למצוא. בסרטון שלנו בחרנו a=1 ו b=100. האלגוריתם שנבחר לפתרון הוא אלגוריתם גנטי [4].
[1] - Parkinson, A.R., Balling, R. and Hedengren, J.D., 2013. Optimization methods for engineering design. Brigham Young University, 5., http://flowlab.groups.et.byu.net/me575/textbook/optimization_book.pdf
[2] - Back, T., 1996. Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms. Oxford university press.
[3] - Beyer, HG. & Schwefel, HP. Natural Computing (2002) 1: 3. https://doi.org/10.1023/A:1015059928466
[4] - Holland, John H. “Genetic Algorithms.” Scientific American, vol. 267, no. 1, 1992, pp. 66–73. JSTOR, JSTOR, www.jstor.org/stable/24939139.
[5] - Weise, T., 2009. Global optimization algorithms-theory and application. Self-published, 2.
מרצה במחלקה להנדסת מכונות, במכללה האקדמית להנדסה בראודה בכרמיאל. אלעד דוקטור למערכות אוטונומיות ורובוטיקה, חוקר בינה מלאכותית ואופטימיזציה.
