אלגוריתם גנטי הוא אלגוריתם חיפוש יוריסטי אדפטיבי בהשראת 'תורת האבולוציה של דרווין בטבע' .' הוא משמש לפתרון בעיות אופטימיזציה בלמידת מכונה. זהו אחד האלגוריתמים החשובים שכן הוא עוזר לפתור בעיות מורכבות שייקח זמן רב לפתור.
אלגוריתמים גנטיים נמצאים בשימוש נרחב ביישומים שונים בעולם האמיתי, למשל, עיצוב מעגלים אלקטרוניים, שבירת קוד, עיבוד תמונה ויצירתיות מלאכותית.
בנושא זה, נסביר בפירוט את האלגוריתם הגנטי, כולל מינוחים בסיסיים המשמשים באלגוריתם גנטי, כיצד הוא פועל, יתרונות ומגבלות של אלגוריתם גנטי וכו'.
c++ מחרוזת מפוצלת
מהו אלגוריתם גנטי?
לפני שנבין את האלגוריתם הגנטי, בואו נבין תחילה טרמינולוגיות בסיסיות כדי להבין טוב יותר את האלגוריתם הזה:
לאחר חישוב הכושר של כל קיים באוכלוסיה, נעשה תהליך בחירה כדי לקבוע מי מהאינדיבידואליות באוכלוסייה יזכה להתרבות ולייצר את הזרע שיהווה את הדור הבא.
סוגי סגנונות בחירה זמינים
אז, עכשיו אנחנו יכולים להגדיר אלגוריתם גנטי בתור אלגוריתם חיפוש היוריסטי לפתרון בעיות אופטימיזציה. זוהי תת-קבוצה של אלגוריתמים אבולוציוניים, המשמשת במחשוב. אלגוריתם גנטי משתמש במושגי ברירה גנטית וטבעית כדי לפתור בעיות אופטימיזציה.
איך עובד אלגוריתם גנטי?
האלגוריתם הגנטי עובד על מחזור הדורות האבולוציוני כדי לייצר פתרונות באיכות גבוהה. אלגוריתמים אלה משתמשים בפעולות שונות שמשפרות או מחליפות את האוכלוסייה כדי לתת פתרון התאמה משופר.
זה בעצם כולל חמישה שלבים כדי לפתור את בעיות האופטימיזציה המורכבות, הניתנות להלן:
1. אתחול
תהליך של אלגוריתם גנטי מתחיל ביצירת מערך הפרטים, הנקרא אוכלוסיה. כאן כל אדם הוא הפתרון לבעיה הנתונה. אדם מכיל או מאופיין על ידי קבוצה של פרמטרים הנקראים גנים. גנים משולבים למחרוזת ומייצרים כרומוזומים, וזה הפתרון לבעיה. אחת הטכניקות הפופולריות ביותר לאתחול היא השימוש במחרוזות בינאריות אקראיות.
2. משימת כושר
פונקציית כושר משמשת כדי לקבוע עד כמה אדם בכושר? המשמעות היא היכולת של אדם להתחרות עם אנשים אחרים. בכל איטרציה, אנשים מוערכים על סמך תפקוד הכושר שלהם. פונקציית הכושר מספקת ציון כושר לכל אדם. ציון זה קובע עוד יותר את ההסתברות להיבחר לרבייה. ככל שציון הכושר הגבוה, כך הסיכויים להיבחר לרבייה גבוהים יותר.
3. בחירה
שלב הבחירה כולל בחירה של פרטים לרבייה של צאצאים. כל הפרטים שנבחרו מסודרים אז בזוג של שניים כדי להגביר את הרבייה. ואז הפרטים האלה מעבירים את הגנים שלהם לדור הבא.
ישנם שלושה סוגים של שיטות בחירה זמינות, שהן:
- בחירת גלגל רולטה
- בחירת טורניר
- בחירה מבוססת דירוג
4. רבייה
לאחר תהליך הבחירה, יצירת ילד מתרחשת בשלב ההתרבות. בשלב זה, האלגוריתם הגנטי משתמש בשני אופרטורים של וריאציות המוחלים על אוכלוסיית ההורים. שני המפעילים המעורבים בשלב ההעתקה מובאים להלן:
- הצלבה נקודה אחת
- קרוסאובר שתי נקודות
- קרוסאובר לייב
- הצלבה של אלגוריתמים בירושה
הגנים של ההורים מוחלפים ביניהם עד לנקודת ההצלבה. הצאצאים החדשים הללו מתווספים לאוכלוסיה. תהליך זה נקרא גם קרוסאובר. סוגי סגנונות קרוסאובר זמינים:
מפעיל המוטציה מחדיר גנים אקראיים לצאצאים (ילד חדש) כדי לשמור על הגיוון באוכלוסייה. ניתן לעשות זאת על ידי היפוך חלקים בכרומוזומים.
מוטציה מסייעת בפתרון סוגיית ההתכנסות המוקדמת ומגבירה את הגיוון. התמונה למטה מציגה את תהליך המוטציה:
סוגי סגנונות מוטציות זמינים,
5. סיום
לאחר שלב ההעתקה מוחל קריטריון עצירה כבסיס לסיום. האלגוריתם מסתיים לאחר הגעה לפתרון כושר הסף. היא תזהה את הפתרון הסופי כפתרון הטוב ביותר באוכלוסייה.
זרימת עבודה כללית של אלגוריתם גנטי פשוט
יתרונות האלגוריתם הגנטי
- היכולות המקבילות של אלגוריתמים גנטיים הן הטובות ביותר.
- זה עוזר באופטימיזציה של בעיות שונות כמו פונקציות בדידות, בעיות מרובות אובייקטיביות ופונקציות רציפות.
- הוא נותן מענה לבעיה המשתפרת עם הזמן.
- אלגוריתם גנטי אינו זקוק למידע נגזר.
מגבלות של אלגוריתמים גנטיים
- אלגוריתמים גנטיים אינם אלגוריתמים יעילים לפתרון בעיות פשוטות.
- זה לא מבטיח את איכות הפתרון הסופי לבעיה.
- חישוב חוזר של ערכי כושר עשוי ליצור כמה אתגרים חישוביים.
ההבדל בין אלגוריתמים גנטיים לאלגוריתמים מסורתיים
- מרחב חיפוש הוא האוסף של כל הפתרונות האפשריים לבעיה. באלגוריתם המסורתי נשמרת רק קבוצה אחת של פתרונות, בעוד שבאלגוריתם גנטי ניתן להשתמש במספר קבוצות של פתרונות במרחב החיפוש.
- אלגוריתמים מסורתיים זקוקים למידע נוסף על מנת לבצע חיפוש, ואילו אלגוריתמים גנטיים זקוקים רק לפונקציה אובייקטיבית אחת כדי לחשב את כושרו של אדם.
- אלגוריתמים מסורתיים אינם יכולים לעבוד במקביל, ואילו אלגוריתמים גנטיים יכולים לעבוד במקביל (חישוב הכושר של האינדיבידואליות אינו תלוי).
- הבדל אחד גדול באלגוריתמים גנטיים הוא שבמקום לפעול ישירות על תוצאות המחפשים, אלגוריתמים תורשתיים פועלים על ייצוגים (או עיבוד) שלהם, המכונה לעתים קרובות ככרומוזומים.
- אחד ההבדלים הגדולים בין אלגוריתם מסורתי לאלגוריתם גנטי הוא שהוא אינו פועל ישירות על פתרונות מועמדים.
- אלגוריתמים מסורתיים יכולים ליצור רק תוצאה אחת בסופו של דבר, ואילו אלגוריתמים גנטיים יכולים ליצור מספר תוצאות אופטימליות מדורות שונים.
- אין סיכוי גבוה יותר שהאלגוריתם המסורתי יניב תוצאות אופטימליות, בעוד שאלגוריתמים גנטיים אינם מבטיחים יצירת תוצאות גלובליות אופטימליות, אך גם קיימת אפשרות גדולה לקבל את התוצאה האופטימלית לבעיה שכן הוא משתמש באופרטורים גנטיים כמו Crossover ומוטציה.
- אלגוריתמים מסורתיים הם דטרמיניסטיים באופיים, ואילו אלגוריתמים גנטיים הם הסתברותיים וסטוכסטיים באופיים.