בתחום הבינה המלאכותית, אלגוריתם אבולוציוני (EA) הוא תת-קבוצה של חישובי אוכלוסייה הכוללים המבוססים על אופטימיזציה מטהאוריסטית. EA משתמשת במנגנונים בהשראת התפתחות ביולוגית כמו רבייה, מוטציה, ריקומבינציה וברירה. הפתרון המועמד בבעיית אלגוריתמי האופטימיזציה האבולוציונית ממלא את תפקידם של פרטים באוכלוסייה. וגם פונקציית הכושר קובעת את איכות התשובות.
אלגוריתמים אבולוציוניים בדרך כלל מעריכים היטב פתרונות לכל סוגי הבעיות. כי באופן אידיאלי הם לא מניחים שום הנחות לגבי נוף הכושר הבסיסי. שיטות המשמשות למידול אבולוציוני ואלגוריתמים גנטיים מוגבלות בדרך כלל למחקרים של תהליכים מיקרו אבולוציוניים ומודלים לתכנון המבוססים על שלבים תאיים. ברוב יישומי ה-EA האמיתיים, מורכבות חישובית היא גורם אוסר.
למעשהבעיה זו קשורה להערכת תפקוד כושר. קירוב כושר הוא פתרון אחד להתגבר על הקושי הזה. עם זאת, EA פשוט לכאורה יכול לפתור בעיות מורכבות לעתים קרובות. לכן, לא יכול להיות קשר ישיר בין מורכבות הרצף לבעיה. פרטים נוספים ניתן למצוא בספרים "אלגוריתמים אבולוציוניים".
יישום
שלב ראשון הוא יצירת אוכלוסיה ראשונית של פרטים באופן אקראי.
שלב שני הוא להעריך את ההתאמה של כל אדם בקבוצה זו (מגבלת זמן, היערכות מספקת וכו').
שלב שלישי - חזור על שלבי ההתחדשות הבאים עד להשלמתם:
- בחר את האנשים המתאימים ביותר לגידול (הורים).
- הבא אנשים חדשים שעברו את האלגוריתם האבולוציוני באמצעות הצלבה ומוטציה כדי להביא צאצאים.
- הערכת הכושר האישי של אנשים חדשים.
- החלף בהם את האוכלוסייה הפחות מתאימה.
Types
אלגוריתם גנטי הוא רצף אבולוציוני, הסוג הפופולרי ביותר של יועץ מומחה. מחפשים פתרון לבעיה בצורה של מחרוזות של מספרים (באופן מסורתי, אם כי הייצוגים הטובים ביותר הם בדרך כלל אלו המשקפים יותר את הבעיה הנפתרת) על ידי יישום אופרטורים כגון רקומבינציה ומוטציה (לעיתים אחד, במקרים מסוימים שניהם). סוג זה של יועץ מומחה משמש לעתים קרובות בבעיות אופטימיזציה. שם נוסף לכך הוא fetura (מלטינית עבור "לידה"):
- תכנות גנטי. הוא מציג פתרונות כקודי מחשב, והתאמתם נקבעת על פי יכולתם לבצע משימות חישוביות.
- תכנות אבולוציוני. דומה לאלגוריתם הגנטי האבולוציוני, אבל המבנה קבוע והפרמטרים המספריים שלו יכולים להשתנות.
- תכנות ביטוי גנים. מפתח יישומי מחשב, אך בוחן את מערכת הגנוטיפ-פנוטיפ, שבה פרויקטים בגדלים שונים מקודדים על כרומוזומים לינאריים באורך קבוע.
- אסטרטגיה. עובד עם וקטורים של מספרים ממשיים כייצוגים של פתרונות. משתמש בדרך כלל באלגוריתמים של שיעורי מוטציות אבולוציוניים מסתגלים לעצמם.
- פיתוח דיפרנציאלי. מבוסס על הבדלים וקטוריים ולכן מתאים בעיקר לבעיות אופטימיזציה מספרית.
- נוירואבולוציה. בדומה לתכנות אבולוציוני ואלגוריתמים גנטיים. אבל האחרונות הן רשתות עצביות מלאכותיות, המתארות את המבנה והמשקל של הקשרים. קידוד הגנום יכול להיות ישיר או עקיף.
השוואה לתהליכים ביולוגיים
מגבלה אפשרית של אלגוריתמים אבולוציוניים רבים היא היעדר הבחנה ברורה בין גנוטיפ לפנוטיפ. בטבע, ביצית מופרית עוברת תהליך מורכב המכונה embryogensis כדי להתבגר. קידוד עקיף זה נחשב כגורם לחיפושים גנטיים להיות אמינים יותר (כלומר, פחות סיכוי לגרום למוטציות קטלניות) ועשוי גם לשפר את יכולתו של האורגניזם להתפתח. עקיף כזה (במילים אחרות,קידודים יצירתיים או התפתחותיים) מאפשרים גם לאבולוציה לנצל סדירות בסביבה.
עבודה אחרונה בנושא עוברים מלאכותיים או מערכות התפתחותיות שואפת לטפל בבעיות אלו. בעת תכנות ביטוי גנים, אזור הגנוטיפ-פנוטיפ נחקר בהצלחה, כאשר הראשון מורכב מכרומוזומים רב-גנים ליניאריים באורך קבוע, והשני מעצי ביטוי רבים או תוכנות מחשב בגדלים וצורות שונות.
טכניקות קשורות
אלגוריתמים כוללים:
- אופטימיזציה של מושבת נמלים. הוא מבוסס על הרעיון שחרקים מחפשים מזון על ידי חיבור עם פרומונים ליצירת נתיבים. מתאים בעיקר לאופטימיזציה קומבינטורית ולבעיות גרפים.
- אלגוריתם מחוון שורש. היוצר קיבל השראה מתפקודם של שורשי הצמחים בטבע.
- אלגוריתם למושבות דבורים מלאכותיות. מבוסס על התנהגות דבורי דבש. הוא מוצע בעיקר לאופטימיזציה מספרית ומורחבת לפתרון בעיות קומבינטוריות, מוגבלות ורב-אובייקטיביות. אלגוריתם הדבורים מבוסס על התנהגות של חרקים לחיפוש מזון. זה יושם ביישומים רבים כגון ניתוב ותזמון.
- אופטימיזציה של נחיל חלקיקים - מבוסס על רעיונות התנהגות עדר בעלי חיים. וגם מתאים בעיקר למשימות תהליך מספרי.
שיטות מטאוריסטיות פופולריות אחרות
- חיפוש ציד. שיטה המבוססת על תפיסה קבוצתית של בעלי חיים מסוימים, כמו זאבים, למשל, אשרלחלק את חובותיהם להקיף את הטרף. כל אחד מחברי האלגוריתם האבולוציוני מתייחס לאחרים בדרך כלשהי. זה נכון במיוחד עבור המנהיג. זוהי שיטת אופטימיזציה מתמשכת המותאמת כשיטת תהליך קומבינטורית.
- חפש לפי מידות. בניגוד לשיטות מטאוריסטיות מבוססות טבע, אלגוריתם התהליך האדפטיבי אינו משתמש במטאפורה כעיקרון העיקרי שלו. במקום זאת, הוא משתמש בשיטה פשוטה מכוונת ביצועים המבוססת על עדכון פרמטר יחס ממדי החיפוש בכל איטרציה. האלגוריתם של Firefly שואב השראה מהאופן שבו גחליליות מושכות זו את זו עם האור המהבהב שלהן. זה שימושי במיוחד עבור אופטימיזציה רב-מודאלית.
- חפש הרמוניה. מבוסס על רעיונות ההתנהגות של מוזיקאים. במקרה זה, אלגוריתמים אבולוציוניים הם הדרך לאופטימיזציה קומבינטורית.
- עיבוד גאוסי. מבוסס על תורת המידע. משמש כדי למקסם את הביצועים והזמינות הממוצעת. דוגמה לאלגוריתמים אבולוציוניים במצב זה: אנטרופיה בתרמודינמיקה ובתורת המידע.
Memetic
שיטה היברידית המבוססת על רעיון המם של ריצ'רד דוקינס. זה בדרך כלל לובש צורה של אלגוריתם מבוסס אוכלוסיה בשילוב עם נהלי למידה בודדים המסוגלים לבצע חידודים מקומיים. מדגיש שימוש בידע ספציפי לבעיה וניסיונות לארגן חיפושים עדינים וגלובליים בצורה סינרגטית.
אבולוציוניאלגוריתמים הם גישה היוריסטית לבעיות שלא ניתן לפתור בקלות בזמן פולינומי, כגון בעיות NP-קשות קלאסיות וכל דבר אחר שייקח יותר מדי זמן לעיבוד ממצה. בשימוש עצמאי, הם משמשים בדרך כלל לבעיות קומבינטוריות. עם זאת, אלגוריתמים גנטיים משמשים לעתים קרובות במקביל לשיטות אחרות, ופועלים כדרך מהירה למצוא מספר מקומות התחלה אופטימליים לעבוד איתם.
הנחת היסוד של האלגוריתם האבולוציוני (הידוע כיועץ) היא די פשוטה בהתחשב בכך שאתה מכיר את תהליך הברירה הטבעית. הוא מכיל ארבעה שלבים עיקריים:
- initialization;
- choice;
- אופרטורים גנטיים;
- end.
כל אחד מהשלבים האלה תואם בערך להיבט מסוים של הברירה הטבעית ומספק דרכים קלות למודולריזציה של קטגוריית אלגוריתמים זו. במילים פשוטות, ב-EA, החברים המתאימים ביותר ישרדו ויתרבו, בעוד החברים הלא מתאימים ימותו ולא יתרמו למאגר הגנים של הדור הבא.
אתחול
כדי להפעיל את האלגוריתם, תחילה עליך ליצור קבוצה של פתרונות. האוכלוסייה תכיל מספר שרירותי של הצהרות בעיות אפשריות, המכונה לעתים קרובות חברים. לעתים קרובות הם נוצרים באופן אקראי (במגבלות המשימה) או, אם ידוע על ידע קודם, מרוכזים בהיסוס סביב מה שנחשב לאידיאלי. חשוב שהאוכלוסייה תכסה מגוון רחב של פתרונות,כי זה בעצם מאגר גנים. לכן, אם רוצים לחקור אפשרויות רבות ושונות בתוך אלגוריתם, צריך לשאוף לגנים רבים ושונים.
Choice
לאחר יצירת האוכלוסייה, כעת יש להעריך את חבריה בהתאם לפונקציית הכושר. פונקציית הכושר לוקחת את המאפיינים של חבר ונותנת ייצוג מספרי של מידת הכושר של החבר. ליצור אותם יכול להיות לעתים קרובות מאוד קשה. חשוב למצוא מערכת טובה שמייצגת במדויק את הנתונים. זה מאוד ספציפי לבעיה. כעת יש צורך לחשב את ההתאמה של כל המשתתפים ולבחור כמה מהחברים הטובים ביותר.
פונקציות יעד מרובות
EAs ניתן גם להרחיב לשימוש במערכות אלו. זה מסבך מעט את התהליך, כי במקום לזהות נקודה אופטימלית אחת, מתקבל סט בעת השימוש בהם. קבוצת הפתרונות נקראת גבול פארטו ומכילה אלמנטים שמתאימים באותה מידה במובן שאף אחד מהם לא שולט באף אחד אחר.
מפעילים גנטיים
שלב זה כולל שני שלבי משנה: הצלבה ומוטציה. לאחר בחירת המונחים הטובים ביותר (בדרך כלל ה-2 המובילים, אך מספר זה יכול להשתנות), הם משמשים כעת ליצירת הדור הבא באלגוריתם. על ידי יישום המאפיינים של ההורים הנבחרים, נוצרים ילדים חדשים שהם תערובת של תכונות. לעתים קרובות זה יכול להיות קשה בהתאם לסוג הנתונים, אבל בדרך כלל בבעיות קומבינטוריותזה בהחלט אפשרי לערבב ולהוציא שילובים חוקיים.
כעת יש צורך להכניס חומר גנטי חדש לדור. אם הצעד החשוב הזה לא יינקט, המדען יתקע מהר מאוד בקיצוניות מקומית ולא יגיע לתוצאות מיטביות. שלב זה הוא מוטציה, והוא נעשה בפשטות, תוך שינוי של חלק קטן מהילדים באופן שהם ברובם אינם משקפים תת-קבוצות של הגנים של ההורים. מוטציה מתרחשת בדרך כלל באופן הסתברותי, שכן ההסתברות שילד יקבל אותה, כמו גם חומרתה, נקבעת לפי התפלגות.
סיום
בסופו של דבר, האלגוריתם חייב להסתיים. זה קורה בדרך כלל בשני מקרים: או שזה הגיע לזמן ביצוע מקסימלי כלשהו, או שהגיע לסף ביצועים. בשלב זה, הפתרון הסופי נבחר ומוחזר.
דוגמה לאלגוריתמים אבולוציוניים
עכשיו, כדי להמחיש את התוצאה של תהליך זה, אתה צריך לראות את היועץ בפעולה. לשם כך, אנו יכולים להיזכר כיצד כמה דורות של דינוזאורים למדו ללכת (שלטו בהדרגה את הארץ), ייעלו את מבנה גופם והפעילו כוח שרירים. למרות שזוחלים מהדור המוקדם לא יכלו ללכת, היועץ הצליח לפתח אותם לאורך זמן באמצעות מוטציה והצלבה לצורה שיכולה ללכת.
אלגוריתמים אלה הופכים יותר ויותר רלוונטיים בעולם המודרני, מכיוון שפתרונות המבוססים עליהם נמצאים בשימוש הולך וגובר בתעשיות כמו שיווק דיגיטלי, פיננסים ושירותי בריאות.
היכן משתמשים ב-EA?
באופן רחב יותר, אלגוריתמים אבולוציוניים משמשים במגוון רחב של יישומים כגון עיבוד תמונה, ניתוב רכבים, אופטימיזציה של תקשורת סלולרית, פיתוח תוכנה ואפילו אימון רשתות עצביות מלאכותיות. כלים אלו נמצאים בלב רבים מהאפליקציות והאתרים שאנשים משתמשים בהם על בסיס יומי, כולל מפות גוגל ואפילו משחקים כמו הסימס. בנוסף, התחום הרפואי משתמש ב-EA כדי לסייע בקבלת החלטות קליניות בנוגע לטיפול בסרטן. למעשה, אלגוריתמים אבולוציוניים כל כך חזקים שאפשר להשתמש בהם כדי לפתור כמעט כל בעיית אופטימיזציה.
חוק מור
השכיחות הגוברת של EO מונעת משני גורמים עיקריים: כוח מחשוב זמין והצטברות של מערכי נתונים גדולים. את הראשון ניתן לתאר על ידי חוק מור, שקובע בעצם שכמות כוח המחשוב במחשב מוכפלת בערך כל שנתיים. התחזית הזו מתקיימת כבר עשרות שנים. הגורם השני נוגע להסתמכות הגוברת על טכנולוגיה, המאפשרת למוסדות לאסוף כמות גדולה להפליא של נתונים, המאפשרת להם לנתח מגמות ולייעל מוצרים.
איך אלגוריתמים אבולוציוניים יכולים לעזור למשווקים?
תנאי השוק משתנים במהירות ותחרותיים מאוד. זה אילץ את מנהלי השיווק להתחרות על קבלת החלטות טובה יותר. הגדלה של זמיןכוח המחשוב הוביל את העובדים להשתמש ב-EA לפתרון בעיות.
אופטימיזציית המרות
אחת המטרות העיקריות היא להגדיל את שיעור המבקרים באתר. הבעיה הזו מסתכמת באופטימיזציה של מספר המשתמשים שעושים מה שהמשווק רוצה. לדוגמה, אם חברה מוכרת מחשבים ניידים, האידיאל הוא להגדיל את מספר המבקרים באתר שבסופו של דבר קונים את המוצר. זוהי המהות של אופטימיזציה של שיעור ההמרות.
אחד ההיבטים החשובים להפליא הוא בחירת ממשק המשתמש. אם עיצוב אתרים לא מאוד ידידותי למשתמש, יש כאלה שבסופו של דבר לא קונים את המוצר מסיבה כזו או אחרת. המטרה אם כן היא לצמצם את מספר המשתמשים שבסופו של דבר לא מבצעים המרה, מה שמגדיל את הרווח הכולל.
