# כשהמתכנתים פגשו את דארווין

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

- Canonical: https://www.hayadan.org.il/evolutionary_programming_020808
- Author: ד"ר רועי צזנה
- Published: 2008-08-02T00:10:56+03:00
- Modified: 2008-08-01T12:58:42+03:00
- Sections: אוניברסיטת בן גוריון, טכנולוגית מיחשוב, מחקר ופיתוח בישראל
- Topics: אלגוריתמים ממוחשבים, מיחשוב גנטי, תכנות אבולוציוני

## Article

פרופסור משה זיפר מבן-גוריון יחד עם תלמידו אסף גלזר, זכו במקום השלישי בתחרות לתכנות אבולוציוני. השניים פיתחו אלגוריתם המאתר פגמים בפרוסות סיליקון דקות ביעילות העולה על זו של מהנדס מומחה לפני שבוע אירע אירוע יוצא דופן : מאות חוקרים למדעי המחשב הגיעו לכנס באטלנטה, שתו בירות ודיברו זה עם זה על אבולוציה, אבולוציה ועוד אבולוציה. אולי זה בעצם לא מפתיע, בהתחשב בכך שתופעה זו חוזרת על עצמה מדי שנה במסגרת כנס GECCO למיחשוב גנטי ואבולוציוני. גולת הכותרת של הכינוס היא התחרות השנתית, בה מחוייבים המשתתפים להציג אלגוריתמים שתוכננו על סמך עקרונות אבולוציוניים ולהוכיח כי הם מוצלחים יותר במשימתם מבני אדם. לישראל יש ייצוג טוב בתחרות, בדמותו של משה זיפר, פרופסור למדעי המחשב באוניברסיטת בן-גוריון. זיפר זכה במקום השלישי ב- 2005, במקום השני ב- 2007, והשנה הגיע למקום השלישי שוב, בשיתוף פעולה עם תלמידו אסף גלזר. השניים יצרו אלגוריתם שהצליח לאתר פגמים בפרוסות סיליקון דקות ביעילות העולה על זו של מהנדס מומחה. פעולה זו, שבוצעה עד עתה על-ידי בני-אדם בלבד, יכולה לחסוך מאות מליוני דולרים לחברות השבבים הגדולות. אם לשפוט לפי הדרך בה הדברים נעשים בטכניון, הרי שכאשר מתכנתים רוצים לתכנן אלגוריתמים הם יושבים בקבוצה, מזמינים כמה פיצות, חושבים על מה שצריך לעשות ואיך אפשר לעשות אותו ואז מוציאים את זה לפועל. בתכנות הגנטי, לעומת זאת, מעורבות המתכנת עקיפה יותר. הוא קובע רק את המטרה הסופית ואת הסינון שיעברו האלגוריתמים בדרך אליה. "הרעיון הבסיסי הוא להשתמש באבולוציה כהשראה לבניית אלגוריתם." מסביר פרופסור זיפר. "האבולוציה בטבע היא תהליך מאד חזק, שיכול לייצר דברים שאנחנו לא יודעים לייצר בדרכים אחרות. אז אנחנו מעתיקים את הדגם האבולוציוני לתוך המחשב." התכנות הגנטי מתחיל בקבוצה גדולה של אלגוריתמים שונים במקצת זה מזה, שעושים פעולה דומה ברמה נמוכה מאד של הצלחה. המחשב מריץ את האלגוריתמים, מזהה אלו מהם הגיעו לתוצאות הטובות ביותר, ובוחר אותם בתהליך של ברירה מלאכותית (המקבילה הממוחשבת לברירה הטבעית), להוות את הבסיס לדור הבא של האלגוריתמים. האלגוריתמים בנויים כך שהם יכולים להחליף ביניהם חלקים מהקוד, ויש מקום גם ל- 'מוטציות' אקראיות בכל מעבר מדור לדור. כתוצאה, הדור הבא של האלגוריתמים בכל שלב יהיה שונה באופן מהותי מהדור הקודם. כאשר חוזרים על תהליך השינוי והניפוי פעמים רבות, מקבלים אלגוריתמים המבצעים את הפעולה המבוקשת ברמה גבוהה מאד של הצלחה – למרות שיד אדם לא היתה מעורבת בתהליך התכנות. בחלק מהמקרים גם החוקרים עצמם אינם מצליחים להבין כיצד האלגוריתם פועל ומדוע. "אתה עובר מדור לדור, ע"י תהליך שבו אתה בורר את היותר מתאימים על פי הקריטריון שקבעת. אתה עושה רקומבינציה ביניהם ותהליך של מוטציה, כמו בטבע, ואז יש דורות ההולכים ונעשים טובים יותר, החיים בתוך המחשב ומהווים פתרונות אפשריים לבעיה שאתה רוצה לפתור. יש כאן את כל המרכיבים של אבולוציה דרוויניסטית בטבע." אומר זיפר, ומוסיף כי, "אתה מתחיל עם אוכלוסיה שהיא די רעה ועם הזמן מגיע לאוכלוסיה שהיא יותר טובה מהתוצאות שהשיגו המומחים בתחום, שהם המהנדסים שיודעים להסתכל על דפקטים בסיליקון ולהגדיר אותם." האלגוריתם שתכננו החוקרים מסוגל להחליף את בני-האדם המחפשים אחר פגמים בפרוסות סיליקון המשמשות ליצירת שבבי מחשבים. עקב הדרישה לכח-אדם אנושי, תחום זה היווה עד עתה צוואר-בקבוק בתעשיית יצור השבבים. האלגוריתם שפותח מסוגל לאתר ולקטלג פגמים במהירות גדולה יותר ובדיוק רב יותר ממהנדסים אנושיים המתמחים באותה משימה. התכנות האבולוציוני מלמד אותנו על כוחה של האבולוציה במציאת פתרונות יעילים למגוון רחב של בעיות, אך הוא אינו פשוט כפי שהוא נראה במבט ראשון. מסגרת הניסוי הבסיסית אכן קלה להבנה, אך כדי להתאים את האלגוריתם ולהגיע לפתרונות טובים יש צורך להבין את תחום החישובים האבולוציוניים על בוריו, ולשלב את הידע עם הבנה מעשית בבעיה שמנסים לפתור. "אחת המכשלות העומדות בפני אלגוריתמים אילו היא כח המיחשוב הגדול הנדרש (אחרי הכל, לאבולוציה הדרוויניסטית נדרשת פלנטה שלמה)," מוסיף זיפר, אך קובע כי, "...השיפור המתמשך ביכולות של המחשבים המודרניים הולך ופותח דלתות חדשות בפני חוקרים בתחום. תחום האלגוריתמים האבולוציוניים הולך ומתפתח משנה לשנה. כבר עתה הם מסוגלים לפתור בעיות קשות, בעוקפם כל דרך פתרון אחרת."