הרעיון: אוכלוסיית-פתרונות שמתפתחת לאורך דורות
אלגוריתם אבולוציוני הוא שיטת-אופטימיזציה שמחפשת פתרון טוב לבעיה לא באמצעות נוסחה מדויקת, אלא בחיקוי מנגנון האבולוציה הביולוגית. הוא מתחיל מאוכלוסייה של פתרונות-מועמדים אקראיים, מודד כל אחד מהם באמצעות "פונקציית-כשירות" (Fitness Function) שקובעת עד כמה הוא טוב, ובוחר את המועמדים הטובים-ביותר להולדת "הדור" הבא — דרך הכלאה (Crossover) בין שני מועמדים ומוטציה אקראית קטנה. התהליך חוזר על עצמו דורות רבים, כשבכל דור הפתרונות משתפרים בממוצע, בלי שאף אחד תכנת במפורש איך לפתור את הבעיה.
שורשים בשנות ה-60–70: הולנד, רכנברג ושוופל
כמה זרמים עצמאיים התפתחו במקביל. ג'ון הולנד מאוניברסיטת מישיגן, שהחל בעבודתו על אוטומטים תאיים, ניסח בתחילת שנות ה-70 את "האלגוריתם הגנטי" (Genetic Algorithm) — הזרם הפופולרי ביותר עד היום — והרחיב אותו בספרו "Adaptation in Natural and Artificial Systems" מ-1975. במקביל, בגרמניה, נתקלו אינגו רכנברג, הנס-פאול שוופל ופיטר בינרט, שלושה סטודנטים במכון להנדסת-זרימה באוניברסיטה הטכנית של ברלין, ב-1964, בבעיית-עיצוב אווירודינמית שקשה היה לפתור בנוסחה סגורה — צורת-פיה במנהרת-רוח. רכנברג הציע לנסות שינויים אקראיים בפרמטרי-הצורה, בעקבות מוטציות בטבע, ומכאן צמחו "אסטרטגיות-האבולוציה" (Evolution Strategies) — במקור לבעיות-אופטימיזציה הנדסיות-מספריות, לא לייצוג בינארי כמו אצל הולנד.
מה מבדיל בין המשפחות
האלגוריתם הגנטי המקורי של הולנד עבד על ייצוגים דיסקרטיים (למשל מחרוזות-ביט), עם הכלאה כמנגנון-מרכזי ובחירה מבוססת-הסתברות-יחסית-לכשירות. אסטרטגיות-האבולוציה מתמקדות בעיקר במוטציה על משתנים רציפים, עם "בררה דטרמיניסטית" — נשמרים תמיד המועמדים הטובים-ביותר בפועל, לא לפי הסתברות — ולעיתים גם גודל-הצעד של המוטציה עצמו מתפתח יחד עם הפתרון. תכנות גנטי (Genetic Programming), זרם שלישי שפרסם ג'ון קוזה בספרו-היסוד מ-1992, מיישם את אותו היגיון-בררה, אך על עצים-חישוביים שלמים — התפתחות של תוכניות-מחשב ממש, לא רק פרמטרים.
למה שיטה כזו, ולא ירידת-גרדיאנט
אלגוריתם אבולוציוני אינו זקוק לדעת שום דבר על המבנה הפנימי של הבעיה — לא נגזרת, לא רציפות, ולא אפילו נוסחה סגורה. די לו בכך שאפשר להעריך כל מועמד ולקבל ציון-כשירות. זה הופך אותו לשימושי דווקא כשירידת-גרדיאנט, שדורשת נגזרות חלקות, נתקעת — למשל כשפונקציית-המטרה אינה רציפה, כשיש הרבה מינימה מקומיים, או כשמחפשים בו-זמנית כמה פרמטרים ממינים שונים לגמרי (מספרים, מבנה, כללים בדידים) שאי-אפשר לגזור אותם יחד. המחיר הוא סיכון של "התכנסות-מוקדמת": כל האוכלוסייה מתכנסת סביב פתרון בינוני יחסית ומאבדת גיוון, לפני שהספיקה לחקור אזורים טובים יותר במרחב-החיפוש — ולכן שמירה על גיוון באוכלוסייה היא שיקול-תכנון מרכזי בכל יישום מעשי.
שימוש מודרני: אימון רשתות-נוירונים בלי גרדיאנט בכלל
ב-2017 פרסמו חוקרי OpenAI מאמר שהראה שאסטרטגיות-אבולוציה יכולות לשמש חלופה ניתנת-להרחבה לשיטות למידת-חיזוק מבוססות-גרדיאנט: במקום לחשב נגזרות בהתפשטות-לאחור, הן מדגמות אלפי הפרעות-מוטציה אקראיות במקביל על פני מחשבים רבים, ובוחרות את הכיוון שהשתפר בממוצע. הגישה פתרה משימת-בקרה תלת-ממדית מורכבת בפחות מעשר דקות באמצעות 1,440 ליבות-מעבד שרצו במקביל — הדגמה לכך ששיטות אבולוציוניות עדיין תחרותיות, גם מול הכלים המתקדמים ביותר של הלמידה העמוקה.
עיצוב-משותף ברובוטיקה: לא רק פרמטר אחד
יתרון מעשי נוסף של אלגוריתם אבולוציוני הוא היכולת לחפש בו-זמנית כמה סוגי-פרמטרים שונים לגמרי בתוך אוכלוסייה אחת. הדגמה מוקדמת ומשפיעה היא מאמרם של הוד ליפסון וג'ורדן פולק, שפורסם ב-2000 בכתב-העת Nature: רובוטים פשוטים הורכבו מרכיבי-יסוד (מוטות, מפעילים ונוירונים מלאכותיים), האבולוציה בחרה בסימולציה את מבני-הגוף והבקרים המשולבים שזזו הכי טוב, ואז יוצרו בפועל במדפסת-ייצור-מהיר. אותו היגיון-בסיס משמש היום ברובוטיקה רכה, שבה חוקרים מתכננים יחד את צורת-הגוף, את סוג-החומר ואת חוקי-הבקרה של רובוט, שלושתם בבת-אחת, במקום לתכנן כל רכיב בנפרד ואז לחבר ביניהם.