לפני מספר חודשים סיפרנו לכם על אלגוריתמים אבולוציונים לאופטימיזציה. נזכיר, שאלה שיטות ששואבות השראה מהטבע, ועל ידי ביצוע ברירה, הכלאה ומוטציה בערכים מספריים, הן מוצאות את הערכים המיטביים לבעיה. החוזק הגדול של האלגוריתמים האלה הוא בעובדה שאין צורך להבין את הבעיה לעומק. אם אנחנו מסוגלים לחשב את הערכים על ידי ניסוי או סימולציה, אפשר להפעיל את השיטות האלה ובדרך כלל נקבל תשובה לא רעה בכלל.
בשנות השמונים של המאה העשרים, תחום המחקר של האלגוריתמים האלה פרח. חדשות לבקרים התפרסם מחקר על שיטה אבולוציונית חדשה שפותרת בעיות מהר יותר מזו הקודמת. האלגוריתמים נבדלו בדרך שבה הם מבצעים את הברירה, שיטות קידוד שונות לערכי המשתנים בבעיה וכולי. מבחינה תיאורתית, בעיה כללית יכולה לקחת אינסוף זמן, אבל מבחינה פרקטית הרבה מאוד מקרים פרטיים ניתן לפתור מהר והתחרות היתה מי מצליח למצוא את הגביע הקדוש: אלגוריתם שיפתור את מירב הבעיות האלה בזמן הקצר ביותר.
אבל אז, בשנת 1997, המתמטיקאים דייוויד וולפרט ווויליאם מקרדי פוצצו את המסיבה. הם פרסמו מאמר ובו הוכחה של משפט מתמטי שמראה שאין ולא תהיה שיטה אחת שהיא הכי טובה, כל עוד אין לנו מידע פנימי על הבעיה [2]. כלומר, אם אלגוריתם א' פותר את בעיה 1 מאוד מהר, ניתן בוודאות למצוא בעיה 2 שבה הוא יהיה מאוד איטי. הם קראו למשפט "אין ארוחות חינם".
כדי למצוא פתרון לבעיה בצורה יעילה אנחנו צריכים לשלם בצורת ידע. כלומר, כדי שהאלגוריתם שלנו יהיה מהיר, אנחנו צריכים מידע על הבעיה אותה אנחנו מנסים לפתור, והאלגוריתם שלנו צריך להיות בנוי בהתאם למידע הזה. וולפרט ומקרדי הראו שאם ניקח אלגוריתם מסוים, נפתור איתו את כל הבעיות שבעולם ונבדוק כמה זמן בממוצע לקח לו לפתור, אז המהירות הממוצעת של כל האלגוריתמים תהיה זהה. כולם אותו דבר! לכן לא יכול להיות אלגוריתם אחד הכי מהיר, כי כשמסתכלים על פתרון כל הבעיות כל האלגוריתמים מהירים באותה מידה.
הדוגמה שניתנה לקוחה מתחום המסעדנות: הבעיה שלנו מקבילה למציאת הארוחה הזולה ביותר. השיטה (האלגוריתם) היא מסעדה עם תפריט, שבו לכל מנה (בעיה) יש מחיר שהוא הזמן שלוקח לאלגוריתם לפתור את הבעיה. יש אינסוף מסעדות עם אותו התפריט, וההבדל ביניהן הוא במחירי המנות. אם לא אכפת לנו איזו מנה נאכל, אז גם לא משנה איזו מסעדה נבחר, משום שהמחיר הממוצע יהיה זהה. אדם צמחוני שהולך למסעדה עם אוכל בשר שמנסה למצוא את המנה הבשרית הזולה ביותר, עלול לשלם מחיר גבוה יותר מהממוצע. כלומר, אם המטרה שלנו היא לעשות אופטימיזציה למנה צמחונית, אבל נשתמש אוכל בשר שטוב בלמצוא מנות בשריות זולות, יהיה לנו מאוד קשה למצוא פתרון טוב.
אין אלגוריתם שהוא הכי טוב לכל הבעיות, כמו שאין מסעדה שזולה יותר לכל המנות. כדי לאכול את המנה הזולה ביותר, אנחנו צריכים ידע על המנה אותה נבחר (צמחונית או בשרית) ועל המחיר שאותה מסעדה תגבה על המנה. לכן, אין גביע קדוש של אופטימיזציה, ואין ארוחות חינם.
התוצאה העיקרית של המאמר של וולפרט ומקרידי היה לשנות את הכיוון שבו התקדם המחקר, לא רק באלגוריתמים אבולוציוניים אלא באופטימיזציה בכלל. חוקרים התחילו לחפש דרכים בהן ניתן לאפיין בעיות ולהתאים להן את האלגוריתמים המהירים ולהפך - איך לכתוב בעיות כך שיתאימו טוב יותר לכלים שיש בידינו.
בנושא אלגוריתמים אבולוציוניים במיוחד, התחיל להתפתח תחום המטא אלגוריתמים, או אלגוריתמי-על. התאמה של אלגוריתם אופטימיזציה לבעיה על ידי שימוש באלגוריתמים אבולוציוניים.
אבל גם כאן, כמו באלגוריתמים רגילים, אין ארוחות חינם.
 
מקורות ולקריאה נוספת:
[1] - על אלגוריתמים אבולוציוניים באתר מדע גדול, בקטנה
[2] - Wolpert, D.H., Macready, W.G. (1997), "No Free Lunch Theorems for Optimization," IEEE Transactions on Evolutionary Computation 1, 67.