אלגוריתם גנטי
מתודולוגיה

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