דוגמה מהירה להתפתחות גנטית ב- JavaScript: בואו נעשה תינוק.

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

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

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

אני לוקח השפעה כבדה להפליא מרכבת הקידוד: אתגר הקידוד מספר 29 כהשראה לכך. קישור אליו כאן. הוא קיבל השראה על ידי רקטות חכמות, כך שלמרות שאני לא עושה שום דבר חדש או מקורי, אני מקווה שהוא ישמש דוגמא לאלגוריתם של התפתחות גנטית. אני משתמש בספריית P5.JS, שאסכם כספריית JavaScript חזותית.

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

יש לי שתי ספריות ל- P5. הראשי מטפל ברישום למסך, יישום משתנים וכו '. מקל הוא הקו שיתפתח, אוכלוסיה היא אוסף של מקלות, ו- dna זה מה שהייתי מחשיב את ליבת האלגוריתם הגנטי. בואו נסתכל על הקוד עבור סטיק:

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

אוכלוסייה באמת לא כל כך מעניינת. זה יוצר 25 מקלות, שלדעתי מספיקים לאוכלוסייה, ואז מעבירים אותם על המסך. לא מפריעים חסמים בפונקציה זו! DNA:

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

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

אז אם אנו מנהלים את זה כפי שהוא כרגע, אנו מקבלים את זה:

המקלות הקטנים והמבולבלים

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

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

כך נוכל להתחיל ליישם זאת על ידי מתן לכל מקל משתנה חדש: כושר.

var כושר = 0

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

this.calculateFitness = פונקציה () {
var מרחק = dist (this.pos.x, this.pos.y, target.x, target.y)
עדות זו = 1 / מרחק
}

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

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

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

די מגניב, המקלות שלנו מסוגלים כעת לנצל את המיטב מהיכולות של קודמים, ולהשתמש בהם כדי למצוא את המעגל! אם אנו מסתכלים על זה בפעולה:

המקלות עדיין מבולבלים אך מעט חכמים יותר.

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

החכמים מאוד, מקלות אלפא.

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

מקל גאונות (ים)!

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

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

הקוד המלא שלי.