streamalism.org

1. הקדמה

מטרת הסדרה הזו היא להסביר את הרעיון של אלגוריתמים גנטיים.

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

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

2. כיצד עובדים אלגוריתמים גנטיים

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

אלגוריתם מתחיל עם סט פתרונות (מיוצג על ידי יחידים) שקוראים לו אוּכְלוֹסִיָה. פתרונות מאוכלוסייה אחת נלקחים ומשמשים ליצירת א אוכלוסייה חדשה, שכן יש סיכוי שהאוכלוסייה החדשה תהיה טובה יותר מהזקנה.

אנשים שנבחרו ליצור פתרונות חדשים (צֶאֱצָאִים) נבחרים על פי שלהם כושר - ככל שהם מתאימים יותר, כך יש להם יותר סיכויים להתרבות.

3. אלגוריתם גנטי בינארי

בואו נסתכל על התהליך הבסיסי לאלגוריתם גנטי פשוט.

3.1. אִתחוּל

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

SimpleGeneticAlgorithm.runAlgorithm (50, "1011000100000100010000100000100111001000000100000100000000001111");

בדוגמה לעיל, אוּכְלוֹסִיָה הגודל הוא 50, והפתרון הנכון מיוצג על ידי מחרוזת הסיביות הבינארית שאנו עשויים לשנות בכל עת.

בשלב הבא אנו הולכים לשמור את הפתרון הרצוי שלנו וליצור אקראי אוּכְלוֹסִיָה:

setSolution (פתרון); אוכלוסייה myPop = אוכלוסייה חדשה (אוכלוסיית גודל, נכון);

עכשיו אנחנו מוכנים להפעיל את הלולאה הראשית של התוכנית.

3.2. בדיקת כושר

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

בעוד (myPop.getFittest (). getFitness () <getMaxFitness ()) {System.out.println ("דור:" + generationCount + "גנים נכונים שנמצאו:" + myPop.getFittest (). getFitness ()); myPop = evolvePopulation (myPop); generationCount ++; }

נתחיל בהסבר איך אנחנו הכי מתאימים אִישִׁי:

public int getFitness (יחיד אישי) {int fitness = 0; עבור (int i = 0; i <individual.getDefaultGeneLength () && i <solution.length; i ++) {if (individual.getSingleGene (i) == פתרון [i]) {כושר ++; }} להחזיר כושר; }

כפי שאנו יכולים לראות, אנו משווים שניים אִישִׁי חפצים טיפין טיפין. אם לא נוכל למצוא פיתרון מושלם, עלינו להמשיך לשלב הבא, שהוא אבולוציה של אוּכְלוֹסִיָה.

3.3. צֶאֱצָאִים

בשלב זה עלינו ליצור חדש אוּכְלוֹסִיָה. ראשית, אנחנו צריכים בחר שני הורים אִישִׁי חפצים מ אוּכְלוֹסִיָה, על פי כושרם. שימו לב שמועיל לאפשר את הטוב ביותר אִישִׁי מהדור הנוכחי כדי לעבור לדור הבא, ללא שינוי. אסטרטגיה זו מכונה אליטיזם:

אם (אליטיזם) {newPopulation.getIndividuals (). להוסיף (0, pop.getFittest ()); אליטיזם אופסט = 1; } אחר {elitismOffset = 0; }

על מנת לבחור שניים הטובים ביותר אִישִׁי אובייקטים, אנו הולכים ליישם אסטרטגיית בחירת טורניר:

טורניר פרטי אישי בחירה (אוכלוסיית פופ) {טורניר אוכלוסיה = אוכלוסייה חדשה (טורניר גודל, שקר); עבור (int i = 0; i <tournamentSize; i ++) {int randomId = (int) (Math.random () * pop.getIndividuals (). size ()); turn.getIndividuals (). להוסיף (i, pop.getIndividual (randomId)); } בכושר בודד = טורניר. GetFittest (); לחזור בכושר הטוב ביותר; }

הזוכה בכל טורניר (זה עם הכושר הטוב ביותר) נבחר לשלב הבא, כלומר הצלבה:

מוצלב פרטי אינדיבידואלי (אינדיבידואלי אינדיבידואלי, אינדיבידואלי אינדיביד 2) {אינדיבידואלי newSol = אינדיבידואל חדש (); עבור (int i = 0; i <newSol.getDefaultGeneLength (); i ++) {if (Math.random () <= uniformRate) {newSol.setSingleGene (i, indiv1.getSingleGene (i)); } אחר {newSol.setSingleGene (i, indiv2.getSingleGene (i)); }} להחזיר newSol; }

במוצלב, אנו מחליפים ביטים מכל בחירה אִישִׁי במקום שנבחר באופן אקראי. התהליך כולו מתנהל בתוך הלולאה הבאה:

עבור (int i = elitismOffset; i <pop.getIndividuals (). size (); i ++) {אינדיבידואלי אינדיבידואלי = טורניר סלקציה (pop); אינדיבידואלי אינדיבידואלי = טורניר סלקציה (פופ); אינדיבידואלי אינדיבידואלי = מוצלב (indiv1, indiv2); newPopulation.getIndividuals (). הוסף (i, newIndiv); }

כפי שאנו רואים, לאחר ההצלבה, אנו מניחים צאצאים חדשים אצל חדש אוּכְלוֹסִיָה. שלב זה נקרא קַבָּלָה.

לבסוף, אנו יכולים לבצע א מוּטָצִיָה. מוטציה משמשת לשמירה על מגוון גנטי מדור אחד של אוּכְלוֹסִיָה לבא בתור. השתמשנו ב- היפוך קצת סוג של מוטציה, שבה ביטים אקראיים פשוט הופכים:

מוטציה חלל פרטית (אינדיבידואלי אישי) {עבור (int i = 0; i <indiv.getDefaultGeneLength (); i ++) {if (Math.random () <= mutationRate) {גן בתים = (byte) Math.round (Math. אַקרַאִי()); indiv.setSingleGene (i, גן); }}}

כל סוגי המוטציה והקרוסאובר מתוארים יפה במדריך זה.

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

4. טיפים וטריקים

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

• שיעור מוצלב - זה צריך להיות גבוה בערך 80%-95%
• שיעור מוטציה - זה צריך להיות נמוך מאוד, בסביבה 0.5%-1%.
• גודל אוכלוסייה גודל אוכלוסייה טוב הוא בערך 20-30עם זאת, בחלק מהבעיות גדלים 50-100 טובים יותר
• בְּחִירָה - בסיסי בחירת גלגל רולטה יכול לשמש עם המושג אליטיזם
• סוג מוצלב ומוטציה - זה תלוי בקידוד ובבעיה

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

5. מסקנה

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

קוד המקור השלם של קטעי הקוד במדריך זה זמין בפרויקט GitHub.

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

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

• כיצד לעצב אלגוריתם גנטי? (זֶה)
• בעיית איש המכירות המטייל בג'אווה