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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

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

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

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

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

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

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

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

הערכות[עריכת קוד מקור | עריכה]

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

שימושים[עריכת קוד מקור | עריכה]

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

בראייה מתמטית, אלגוריתם גנטי מאפשר למצוא נקודות קיצון של פונקציה \ 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).

קישורים חיצוניים[עריכת קוד מקור | עריכה]