אלגוריתם אבולוציוני
אלגוריתם אבולוציוני (EA) הוא אלגוריתם מחשב המשחזר היבטים של האבולוציה הביולוגית במטרה לפתור בעיות "קשות", לפחות בקירוב, עבורן אין שיטות פתרון מדויקות או מספקות ידועות. אלגוריתמים אבולוציונים הם מטאהיוריסטיקות (אנ') ואלגוריתמים מבוססי אוכלוסייה בהשראה ביולוגית, והם חלק מחישוב אבולוציוני, שהוא בעצמו חלק מתחום האינטליגנציה החישובית. המנגנונים של האבולוציה הביולוגית שאלגוריתם אבולוציוני מחקה בעיקר הם: רבייה, מוטציה, רקומבינציה וברירה. פתרונות מועמדים לבעיית האופטימיזציה משחקים את התפקיד של פרטים באוכלוסייה, ופונקציית התאמה (fitness function) קובעת את איכות הפתרונות (ראו גם פונקציית הפסד). האבולוציה של האוכלוסייה מתרחשת לאחר יישום חוזר של האופרטורים הללו.
אלגוריתמים אבולוציוניים לרוב מבצעים היטב בקירוב פתרונות לכל סוגי הבעיות, משום שבאופן אידיאלי הם אינם מניחים דבר על נוף ההתאמה (fitness landscape) הבסיסי. טכניקות מתוך אלגוריתמים אבולוציוניים המיושמות למידול של האבולוציה הביולוגית מוגבלות בדרך כלל לחקר מיקרואבולוציה (תהליכים מיקרואבולוציוניים) ולתכנון מודלים המבוססים על תהליכים תאיים. ברוב היישומים המעשיים של EA, מורכבות חישובית היא גורם מגביל. למעשה, מורכבות חישובית זו נובעת מהערכת פונקציית ההתאמה. קירוב התאמה (fitness approximation) הוא אחד הפתרונות להתגברות על הקושי הזה. עם זאת, אלגוריתם אבולוציוני שנראה פשוט לעיתים יכול לפתור בעיות מורכבות; לכן, לעיתים אין קשר ישיר בין מורכבות האלגוריתם למורכבות הבעיה.
אלגוריתם גנטי הוא סוג ספציפי של אלגוריתם אבולוציוני, שמיישם בעיקר את רעיונות הרבייה, המוטציה והבחירה בהשראה מתוך גנטיקה ביולוגית.
קישורים חיצוניים
[עריכת קוד מקור | עריכה]
- אלעד דננברג, אלגוריתמים אבולוציונים, מדע גדול, בקטנה, 27/09/2018
