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

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

[עריכה] מתודולוגיה

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

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

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

[עריכה] אלגוריתם (פסאודו-קוד)

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

[עריכה] מוטציות

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

[עריכה] הערכות

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

[עריכה] שימושים

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

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

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

$\ \vec{x}=(x_1,\dots,x_n)\isin \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)$ .