streamalism.org

1. הקדמה

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

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

2. איך עובדת ACO

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

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

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

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

כתוצאה מכך נגיע למסלול הקצר ביותר בין כל הצמתים:

הכלי הנחמד מבוסס GUI לבדיקת ACO נמצא כאן.

3. יישום ג'אווה

3.1. פרמטרים של ACO

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

כפול פרטי c = 1.0; פרטי אלפא כפול = 1; בטא כפולה פרטית = 5; אידוי כפול פרטי = 0.5; כפול פרטי Q = 500; antFactor כפול פרטי = 0.8; כפול פרטי randomFactor = 0.01;

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

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

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

3.2. צור נמלים

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

מבט בטל ציבורי (int currentIndex, int city) {trail [currentIndex + 1] = עיר; ביקר [עיר] = נכון; } ביקור בוליאני ציבורי (int i) {ביקור חוזר [i]; } trailLength כפול ציבורי (גרף כפול [] []) {אורך כפול = גרף [trail [trailSize - 1]] [trail [0]]; עבור (int i = 0; i <trailSize - 1; i ++) {length + = graph [trail [i]] [trail [i + 1]]; } אורך החזרה; } 

3.3. התקנת נמלים

ממש בהתחלה, אנחנו צריכים אתחל את יישום קוד ה- ACO שלנו על ידי מתן מטריצות שבילים ונמלים:

גרף = createRandomMatrix (noOfCities); numberOfCities = graph.length; numberOfAnts = (int) (numberOfCities * antFactor); שבילים = מספר כפול חדש [numberOfCities] [numberOfCities]; הסתברויות = מספר כפול חדש [numberOfCities]; נמלים = נמלה חדשה [numberOfAnts]; IntStream.range (0, numberOfAnts) .forEach (i -> ants.add (Ant (numberOfCities) חדש)));

הבא, אנחנו צריכים הגדר את נמלים מַטרִיצָה להתחיל עם עיר אקראית:

setupAnts () ריק ריק () {IntStream.range (0, numberOfAnts) .forEach (i -> {ants.forEach (ant -> {ant.clear (); ant.visitCity (-1, random.nextInt (numberOfCities)); });}); currentIndex = 0; }

עבור כל איטרציה של הלולאה, נבצע את הפעולות הבאות:

IntStream.range (0, maxIterations) .forEach (i -> {moveAnts (); updateTrails (); updateBest ();});

3.4. להזיז נמלים

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

public void moveAnts () {IntStream.range (currentIndex, numberOfCities - 1) .forEach (i -> {ants.forEach (ant -> {ant.visitCity (currentIndex, selectNextCity (ant));}); currentIndex ++;}) ; }

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

int t = random.nextInt (numberOfCities - currentIndex); if (random.nextDouble () i == t &&! ant.visited (i)) .findFirst (); אם (cityIndex.isPresent ()) {return cityIndex.getAsInt (); }}

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

חלל ציבורי calcProbabilities (Ant ant) ​​{int i = ant.trail [currentIndex]; פרומון כפול = 0.0; עבור (int l = 0; l <numberOfCities; l ++) {if (! ant.visited (l)) {feromone + = Math.pow (trail [i] [l], alpha) * Math.pow (1.0 / graph [i] [l], בטא); }} עבור (int j = 0; j <numberOfCities; j ++) {if (ant.visited (j)) {probabilities [j] = 0.0; } אחר {מניין כפול = Math.pow (מסלולים [i] [j], אלפא) * Math.pow (1.0 / גרף [i] [j], בטא); הסתברויות [j] = מניין / פרומון; }}} 

לאחר שנחשב את ההסתברויות, נוכל להחליט לאיזו עיר נלך באמצעות:

כפול r = random.nextDouble (); סה"כ כפול = 0; עבור (int i = 0; i = r) {return i; }}

3.5. עדכן שבילים

בשלב זה עלינו לעדכן את השבילים ואת הפרומון השמאלי:

עדכון חלל פומבי ציבורי () {for (int i = 0; i <numberOfCities; i ++) {for (int j = 0; j <numberOfCities; j ++) {trail [i] [j] * = אידוי; }} עבור (Ant a: ants) {תרומה כפולה = Q / a.trailLength (גרף); עבור (int i = 0; i <numberOfCities - 1; i ++) {שבילים [a.trail [i]] [a.trail [i + 1]] + = תרומה; } שבילים [a.trail [numberOfCities - 1]] [a.trail [0]] + = תרומה; }}

3.6. עדכן את הפיתרון הטוב ביותר

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

חלל פרטי updateBest () {if (bestTourOrder == null) {bestTourOrder = נמלים [0]. טרייל; bestTourLength = נמלים [0] .traLLength (גרף); } עבור (Ant a: ants) {if (a.trailLength (graph) <bestTourLength) {bestTourLength = a.trailLength (graph); bestTourOrder = a.trail.clone (); }}}

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

4. מסקנה

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

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

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

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