אלגוריתם גנטי

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

היסטוריה

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

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

מתודולוגיה

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

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

ייצוג בינארי של שני כרומוזומים

1101111000011110

1101100100110110

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

במודל תכנותי זה יוצרים קהילה של פרטים אשר מאופיינים בכרומוזומים, ומעבירים אותם "תהליך אבולוציוני". האלגוריתם עוסק במעבר בין אוכלוסייה של כרומוזומים (רצף של סיביות 0 ו-1 ) לרצף חדש של סיביות ("אוכלוסייה חדשה") על ידי שימוש בבחירה הטבעית ואופרטורים כמו crossover. לאחר יצירת קהילת הפרטים הראשונה, מדרגים כל פרט על מנת למצוא את הפרטים הטובים ביותר. לאחר מכן, עורכים מיזוג (זיווג) בין פרטים אלה על מנת ליצור קהילה חדשה, טובה במקצת מקודמתה, ומעבירים אותה את אותו התהליך. ההנחה כאן היא שמיזוג בין שני פתרונות טובים לבעיה עשוי להניב פתרון טוב יותר. כמו בגנטיקה ביולוגית, שני הורים בעלי סט גנים טובים יוצרים צאצא שגם הוא עליון מבחינה גנטית. לאחר מספר חזרות על הפעולה, הפרטים ישתפרו דרמטית ויציגו את הפתרון הטוב ביותר, או פתרון טוב באופן יחסי לבעיה הנתונה.

בכתיבת אלגוריתם גנטי יש לממש:

• זיווג (Crossover) של שני פרטים שמחזיר שני צאצאים או יותר. הצאצאים נושאים מטען גנטי שהוא שילוב של הפרטים שזווגו. פועל על גנים נבחרים מהכרומוזומים של ההורים ויוצר צאצא חדש. הדרך הפשוטה ביותר לביצוע היא לבחור באופן אקראי נקודה לזיווג, להעתיק את כל הביטים שלפני הנקודה מהורה אחד ולהעתיק את כל הביטים שאחרי הנקודה מההורה השני. אם crossover לא מבוצע, הצאצא יהיה העתק מושלם של ההורים. הפעולה מבוצעת במטרה להכיל את החלקים הטובים של הכרומוזומים הישנים ולכן הכרומוזומים החדשים יהיו טובים יותר. למרות זאת, חשוב להשאיר חלק של האוכלוסייה הישנה לדור הבא.
• מוטציה (Mutation) על פרט בודד שמשנה את התכונות שלו. המטרה היא לבצע שינוי בהעתקות שנוצרו על ידי הזיווג, זאת כדי למנוע חזרה של חלקים שלמים במחרוזת הביטים. אם לא נבצע את פעולת המוטציה הצאצא ייווצר מידית לאחר פעולת הזיווג או שיועתק ישר מההורים ללא כל שינוי. כאשר מבצעים מוטציה חלק אחד או יותר מהכרומוזומים משתנים. מוטציות מתרחשות לרוב בהסתברות נמוכה כלשהי (בין 0.1% ל-0.01%) וזאת מכיוון שאם ההסתברות תהיה גבוהה האלגוריתם הגנטי יהפוך לאלגוריתם של חיפוש אקראי (האלגוריתם יצא משליטה).
• שיערוך (Evaluation) בו בוחרים את הפרטים שישתתפו בתהליך הזיווג לפי רמת התאמה, בעזרת "פונקציית כשירות" (fitness function). לפונקציית השערוך יש מרכיבים רבים שיכולים להחליש או לחזק את ביצועי האלגוריתם הגנטי. ביצועי האלגוריתם הגנטי רגיש מאוד לטכניקה של תהליך הנרמול, כך למשל אם נדרוש שיפור יתר - הדבר יכול להוביל לקבלת חומר גנטי אלטרנטיבי באוכלוסייה ויקדם שליטה של צאצא יחיד. במקרה כזה, לפעולת ה-crossover אין השפעה והאלגוריתם מרכז את מירב החיפושים אחר הפתרון הנדרש סביב הכרומוזום הטוב האחרון שמצא. לעומת זאת, אם תהליך הנרמול לא יפעל כראוי האלגוריתם ייכשל במציאת פתרון בזמן סביר וקרוב לוודאי שפתרונות טובים מקרב האוכלוסייה יאבדו. מאפיין חשוב נוסף של פונקציית השערוך הוא החוזק והחולשה של האלגוריתם הגנטי. ביישום האלגוריתם בדרך כלל לוקחים ערך יחיד שחוזר על ידי פונקציית השערוך ומשתמש בערך כדי לקבוע התאמה יעילה. בקביעת פונקציית השערוך יש להתייחס לאילוצים של היישומים כדי לפסול צאצאים שייתכן ואינם חוקיים.

אלגוריתם (פסאודו-קוד)

1. צור אוכלוסייה התחלתית
2. הערך את ההתאמה של כל פרט באוכלוסייה
3. בחר את הפרטים המתאימים ביותר לזיווג
   1. צור דור חדש של פרטים על ידי זיווג ומוטציה של הדור הקודם
4. חזור על שלבים 2–3 עד סיום הסימולציה

מוטציות

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

הערכות

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

שימושים

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

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

אקולוגיה- נעשה שימוש באלגוריתמיקה גנטית לשם הגעה למודלים של תופעות אקולוגיות.

ניסוח מתמטי

בראייה מתמטית, אלגוריתם גנטי מאפשר למצוא נקודות קיצון של פונקציה $\ f$ ב-n משתנים.

תהי $\ f:\mathbb {R} ^{n}\rightarrow \mathbb {R}$ פונקציית הכשירות, בה רוצים למצוא נקודות קיצון גלובליות, אזי:

• $\ {\vec {x}}=(x_{1},\dots ,x_{n})\in \mathbb {R} ^{n}$ הוא פרט במודל ואיבר בתחום של הפונקציה
• $x_{1},\dots ,x_{n}$ הם "כרומוזומים".
• $f({\vec {x}})\in \mathbb {R}$ הוא השיערוך של פרט ${\vec {x}}$.
• זיווג הוא לקיחת ${\vec {x}}=(x_{1},\dots ,x_{n}),{\vec {y}}=(y_{1},\dots ,y_{n})\in \mathbb {R} ^{n}$ פרטים בתחום והחזרת ${\vec {z}}\in \mathbb {R} ^{n}$ שמורכב מהכרומוזומים של x ו-y. דוגמה ב-$\mathbb {R} ^{4}$: זיווג של ${\vec {x}}=(x_{1},x_{2},x_{3},x_{4}),{\vec {y}}=(y_{1},y_{2},y_{3},y_{4})$ יכול להיות ${\vec {z}}=(y_{1},x_{2},x_{3},y_{4})$.
• מוטציה משנה חלק מהכרומוזומים $x_{1},\dots ,x_{n}$ של פרט ${\vec {x}}=(x_{1},\dots ,x_{n})$.

אלגוריתמים קו-אבולוציוניים

אלגוריתמים קו-אבולוציוניים (Co-evolutionary Algorithms) הם תת-משפחה של אלגוריתמים גנטיים שבם פונקציית הכשירות נקבעת על פי יחס בין אוכלוסיות ולא אבסולוטית, קרי, טיב פתרון מאוכלוסיית פתרונות אחת נקבע ביחס כלשהו לאינטראקציה שלו עם קבוצת פתרונות של אוכלוסייה אחרת שמשתתפת באלגוריתם. היחס המדובר יכול להיות שיתופי (כל אוכלוסייה מייצגת חלק מן הפתרון הכולל לבעיה) או תחרותי (כל אוכלוסייה מיצגת חלק אחר של הבעיה, או מתחרה על פתרונות לבעיה).

לקריאה נוספת

• • Holland, John (1992). Adaptation in Natural and Artificial Systems. Cambridge, MA: MIT Press. ISBN 978-0262581110.

קישורים חיצוניים

• אלגוריתמים גנטיים
• http://www.gp-field-guide.org.uk/
• אלגוריתם גנטי, באתר אנציקלופדיה בריטניקה (באנגלית)
• אלגוריתמים גנטיים, דף שער בספרייה הלאומית