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

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

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

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

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

# צור אוכלוסייה התחלתית
# הערך את ההתאמה של כל פרט
# בחר את הפרטים המתאימים לזיווג
## צור דור חדש על ידי זיווג ומוטציה
# חזור על שלבים 2, 3 עד סיום

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

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

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

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

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

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

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

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

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

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

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

פונקציית הערכה (fitness) נותנת ציון לכל פרט. הציון עוזר לבחור מי יכול להיווצר שוב בדור הבא.

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

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

קיים סוג שבו יש כמה אוכלוסיות שעובדות יחד או מתחרות. כל אוכלוסייה משפיעה על ההערכה של האחרת.