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

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

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

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

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

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

הולנד ניסה בעצם לייבא תכונות אלה של אדפטיביות לתוך מערכות ממוחשבות.

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

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

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

קל לזכור את העיקרון המנחה את האבולוציה בכלל ואת האלגוריתם הגנטי בפרט באופן הבא:

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

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

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)\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).

אלגוריתמים קו-אבולוציוניים[עריכת קוד מקור | עריכה]

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

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