האבולוציה עובדת – גם במחשב

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

אבי בליזובסקי
לפני כשבועיים התקיימה בלונדון ועידה מדעית שבה השתתפו חוקרי מדעי המחשב מכל העולם העוסקים בתחום המכונה “מיחשוב אבולוציוני”. במסגרת כנס זה נערכת תחרות המעונה פרסי יומיס ( (HUMIES המדרג את התוכנות הטובות ביותר המפותחות בשיטה המחקה את האבולוציה שבטבע, במדד אחד בלבד – האם הן מנצחות באופן עקבי בני אדם בתחום שבו היא מתמחה. במקום השני ובפרס כספי של 3,000 דולר, זכתה עבודתם של פרופ' משה זיפר והדוקטורנט עמי האופטמן מהמחלקה למדעי המחשב באוניברסיטת בן גוריון בנגב שנשאה את הכותרת: “התפתחות אבולוציונית של מערכת חיפוש לבעית המט ב-N צעדים בשחמט.

בשיחה עם פרופ' משה זיפר הוא מסביר כי תחום האוגלוריתמים האבולוציוניים שבו עוסק הכינוס מדי שנה נולד כמו תחומים רבים במדעי המחשב בשנות החמישים והשישים ואולם עוד בשנות השמונים הוא היה תחום מחתרתי. “כיום מדובר בתחום פורח, הכינוסים הללו גדלים משנה לשנה – השנה השתתפו 650 חוקרים, מספר שנחשב למספר גבוה של משתתפים בכנסים העוסקים במדעי המחשב, ומשנת 2004 החלו מארגני הכנס בתחרות שנועדה לעודד פיתוח אלגוריתמים אבולוציוניים. ”

מהו אלגוריתם אבולוציוני?פרופ' זיפר: “תחום האלגוריתמים האבולוציוניים שואב את השראתו מהאבולוציה בטבע. נכון שתחומי הביולוגיה ומדעי המחשב מתקרבים, אך זה מתרחש בכיוון של שימוש בבסיסי נתונים לניתוח הגנום האנושי – תחום המכונה ביו אינפורמטיקה. אנחנו פועלים בכיוון ההפוך, מיישמים עיקרון ביולוגי על מדעי המחשב. יש עוד תחומים במדעי המחשב ששואבים את הרעיונות מהטבע, למשל רשתות נוירונים, אבל אנחנו פועלים על עקרון בסיסי יותר: האבולוציה בטבע מצאה פתרונות ודברים מורכבים שאני כאיש מדעי המחשב לא יכול לתכנן, המוח, רשת נוירונים, לב או שריר. בטבע אין מדובר בתכנון, כי האבולוציה הוא תהליך לא מכוון. אנחנו מפשטים את התהליך האבולוציוני, דארווין, כשכתב את ספרו מוצא המינים ב-1859 לא ידע כיצד התורשה עוברת מדור לדור, אבל הוא ראה את התוצאה של התהליכים הללו והתייחס אליהם כאל נתון. (בדיעבד התברר שכל התופעות הללו – הגנטיקה של מנדל, פרטי ה-DNA של ווטסון וקריק ופיענוח הגנום האנושי רק הוכיחו את נכונותה של תורת האבולוציה ולמעשה את האינטואיציה של דארווין א.ב.)

כיצד פועלת תוכנה אבולוציונית?
כדי שמערכת אבולוציונית תתפתח ותייצר פרטים מוצלחים אנו נדרשים לארבעה מרכיבים בסיסיים שהם אושיות המערכת:
• אוכלוסיה של פרטים
• יכולת לריבוי, הכרוכה בתורשה (אורגניזמים מתרבים בריבוי א-מיני או מיני ומורישים לצאצאים שלהם חלק מהתכונות).
• משאבים סופיים
• תחרות.
האבולוציה מתקיימת בין היתר בשל העובדה שאין מספיק מקום לכולם וכל היצורים בני אותו מין מתחרים על משאבים סופיים: מזון, טריטוריה, אוויר, בני זוג.. לאט לאט אלו שמתאימים יותר הם אלו שישרדו, יעמידו יותר צאצאים. הפרטים נהיים מותאמים יותר לסביבתם בגלל שינויים גנומיים. אני כאיש מדעי המחשב מבין שיש פה תהליך מעניין שברמה המופשטת שלו אני יכול לקחת את ארבעת התנאים, ליישם במחשב ולהריץ כאלגוריתם. ובמקום יצורים חיים, התוצרים שלה יהיו תוכנות מותאמות יותר לעשות את המוטל עליהן”

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

כיצד פיתחתם מערכת שפותרת בעיה בשחמט, ולמה דווקא שחמט?
בשנים האחרונות אני מתעסק הרבה במשחקים כי למרות שמשחקים נתפסים כמשהו קליל, מדובר בתחום רציני המשלב תבונה מלאכותית. במשחקים יש הרבה צדדים ויכולות שבני אדם משתמשים בהם ואשר אם נצליח להקנות למחשבים הם יבעבעו לתחומים אחרים של יישומים ומחקרים “רציניים” יותר המעניינים גם את החוקרים וגם את התעשיה. יש סוגים רבים של משחקים – משחקים אינטראקטיביים, משחקי לוח, דמויות, חידות. העתיקים ביותר הם משחקי הלוח מהסוג של דמקה, שחמט, שחמט סיני, גו, שש בש ועוד. האופטמן מגיע מרקע בפסיכולוגיה, ואנחנו יודעים הרבה דברים על הדרך שבה שחקני שחמט ברמה גבוהה משחקים. מאז שדיפ בלו – מחשב על של יבמ שתוכנן ברמת החומרה והתוכנה למשחק שחמט – ניצח את גארי קספרוב לפני 10 שנים, תוכנות השחמט התפתחו והיום יש תוכנות שמסוגלות לנצח רבי אמנים, כשהן מותקנות על מחשב נייד.
התוכנות הללו משתמשות בעץ משחק. המחשב אומר הנה המצב של הלוח כרגע מה היריב יכול לעשות. במהלך הראשון יש 40 אפשרויות ובמהלך השני כבר 1,600. אם עוברים על כל האפשרויות העץ גדל במהירות ומתפוצץ.. שחקן בשר ודם פוסל מראש את מרבית האפשרויות הללו. אחת הפונקציות של כל תוכנת שחמט טובה היא המנגננון לצמצום האפשרויות הללו. למשל להתעלם מאפשרויות שמובילות להפסד בטוח. ככל שתוכנת שחמט יותר טובה היא יודעת לחתוך יותר.

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

מסתבר שאנחנו טובים יותר. התוכנה שהתפתחה אבולוציונית יודעת לנבא מט בצורה יותר מהירה ומדויקת מקראפטי שהיא תוכנת על שנכתבה על ידי אדם היא עמדה בקריטריון של Human Competitive.

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

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

למאמר המדעי, באתר אוני' בן גוריון

לאתר התחרות