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

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

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

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

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

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

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

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

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

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

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

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

[עריכה] קישורים חיצוניים

• אלגוריתמים גנטיים
• אלגוריתמים גנטיים בעזרת JAVA
• http://www.gp-field-guide.org.uk/