מבוא לספריית ג'נטיקס
1. הקדמה
מטרת סדרה זו היא להסביר את הרעיון של אלגוריתמים גנטיים ולהראות את היישומים הידועים ביותר.
במדריך זה, אנו לתאר ספריית Jenetics Java חזקה מאוד שיכולה לשמש לפתרון בעיות אופטימיזציה שונות.
אם אתה מרגיש שאתה צריך ללמוד עוד על אלגוריתמים גנטיים, אנו ממליצים להתחיל במאמר זה.
2. איך זה עובד?
על פי המסמכים הרשמיים שלה, ג'נטיקס היא ספריה המבוססת על אלגוריתם אבולוציוני שנכתב בג'אווה. שורשיהם של אלגוריתמים אבולוציוניים הם בביולוגיה, מכיוון שהם משתמשים במנגנונים בהשראת האבולוציה הביולוגית, כגון רבייה, מוטציה, רקומבינציה וסלקציה.
Jenetics מיושם באמצעות Java זרם ממשק, כך שהוא עובד בצורה חלקה עם שאר Java זרם ממשק API.
התכונות העיקריות הן:
- מזעור ללא חיכוך - אין צורך לשנות או לשנות את פונקציית הכושר; אנחנו פשוט יכולים לשנות את התצורה של מנוע בכיתה ואנחנו מוכנים להתחיל את היישום הראשון שלנו
- ללא תלות - אין צורך בספריות צד-שלישי לזמן ריצה לשימוש ב- Jenetics
- Java 8 מוכן - תמיכה מלאה ב זרם וביטויי למבדה
- רב-הברגה - ניתן לבצע צעדים אבולוציוניים במקביל
על מנת להשתמש ב- Jenetics, עלינו להוסיף את התלות הבאה שלנו pom.xml:
io.jenetics jenetics 3.7.0 את הגרסה האחרונה ניתן למצוא ב- Maven Central.
3. השתמש במקרים
כדי לבדוק את כל התכונות של Jenetics, ננסה לפתור בעיות אופטימיזציה ידועות שונות, החל מאלגוריתם בינארי פשוט וכלה בבעיית הכנאפה.
3.1. אלגוריתם גנטי פשוט
נניח כי עלינו לפתור את הבעיה הבינארית הפשוטה ביותר, בה עלינו לייעל את מיקומי ה- 1 ביט בכרומוזום המורכב מ- 0 ו- 1. ראשית, עלינו להגדיר את המפעל המתאים לבעיה:
בית חרושת gtf = Genotype.of (BitChromosome.of (10, 0.5)); יצרנו את ביט כרומוזום באורך של 10, וההסתברות שיהיו 1 בכרומוזום שווה ל- 0.5.
עכשיו, בואו ניצור את סביבת הביצוע:
מנוע מנוע = Engine.builder (SimpleGeneticAlgorithm :: eval, gtf) .build ();ה eval () השיטה מחזירה את ספירת הסיביות:
הערכה שלמה שלמה פרטית (גנוטיפ gt) {החזר gt.getChromosome (). כמו (BitChromosome.class) .bitCount (); }בשלב האחרון אנו מתחילים את האבולוציה ואוספים את התוצאות:
תוצאת גנוטיפ = engine.stream () .limit (500) .collect (EvolutionResult.toBestGenotype ());התוצאה הסופית תיראה דומה לזו:
לפני האבולוציה: [00000010 | 11111100] אחרי האבולוציה: [00000000 | 11111111]הצלחנו לייעל את המיקום של 1 בגן.
3.2. בעיית סכום משנה של קבוצת משנה
מקרה שימוש נוסף עבור Jenetics הוא לפתור את בעיית סכום המשנה. בקצרה, האתגר לאופטימיזציה הוא, בהינתן קבוצה של מספרים שלמים, עלינו למצוא תת קבוצה שאינה ריקה שסכומה הוא אפס.
ישנם ממשקים מוגדרים מראש ב- Jenetics לפיתרון בעיות כאלה:
מחלקה ציבורית SubsetSum מיישמת בעיה { // יישום } כפי שאנו רואים, אנו מיישמים את ה- בְּעָיָה, שיש לו שלושה פרמטרים:
- - סוג הטיעון של פונקציית הכושר הבעייתית, במקרה שלנו גודל בלתי משתנה, מסודר, קבוע מספר שלם סדר פעולות ISeq
- - סוג הגן איתו מנוע האבולוציה עובד, במקרה זה ניתן לספור מספר שלם גנים EnumGene
- - סוג התוצאה של פונקציית הכושר; הנה זה מספר שלם
על מנת להשתמש ב- בְּעָיָה ממשק, עלינו לבטל שתי שיטות:
פונקציה ציבורית @Override כושר () {להחזיר תת קבוצה -> Math.abs (subset.stream () .mapToInt (Integer :: intValue) .sum ()); } @Override Codec ציבורי codec () {return codecs.ofSubSet (basicSet, size); } בראשונה אנו מגדירים את פונקציית הכושר שלנו, ואילו השנייה היא מחלקה המכילה שיטות מפעל ליצירת קידודים נפוצים של בעיות, למשל, למצוא את קבוצת המשנה הטובה ביותר בגודל קבוע מערכה בסיסית נתונה, כמו במקרה שלנו.
עכשיו נוכל להמשיך לחלק העיקרי. בהתחלה, עלינו ליצור קבוצת משנה שתשמש בבעיה:
בעיית SubsetSum = of (500, 15, LCG64ShiftRandom חדש (101010));שים לב שאנחנו משתמשים ב- LCG64ShiftRandom גנרטור המסופק על ידי Jenetics. בשלב הבא אנו בונים את מנוע הפיתרון שלנו:
בשלב הבא אנו בונים את מנוע הפיתרון שלנו:
מנוע engine = Engine.builder (problem) .minimizing () .maximalPhenotypeAge (5). alterers (new PartiallyMatchedCrossover (0.4), Mutator new (0.3)) .build (); אנו מנסים למזער את התוצאה (באופן אופטימלי התוצאה תהיה 0) על ידי הגדרת גיל הפנוטיפ והמשתנים המשמשים לשינוי הצאצאים. בשלב הבא נוכל להשיג את התוצאה:
פנוטיפ תוצאה = engine.stream () .limit (limit.bySteadyFitness (55)) .collect (EvolutionResult.toBestPhenotype ()); שים לב שאנחנו משתמשים מאתSteadyFitness () המחזיר פרדיקט, שיחתוך את זרם האבולוציה אם לא ניתן היה למצוא פנוטיפ טוב יותר לאחר מספר הדורות הנתון ויאסוף את התוצאה הטובה ביותר. אם יתמזל מזלנו, ויש פיתרון לסט שנוצר באופן אקראי, נראה משהו דומה לזה:
אם יתמזל מזלנו, ויש פיתרון לסט שנוצר באופן אקראי, נראה משהו דומה לזה:
[85|-76|178|-197|91|-106|-70|-243|-41|-98|94|-213|139|238|219] --> 0אחרת, סכום קבוצת המשנה יהיה שונה מ- 0.
3.3. תרמיל בעיית התאמה ראשונה
ספריית Jenetics מאפשרת לנו לפתור בעיות מתוחכמות עוד יותר, כמו בעיית הכנאפה. בקצרה, בבעיה זו, יש לנו מקום מוגבל בתיק התרמיל שלנו, ועלינו להחליט אילו פריטים להכניס פנימה.
נתחיל עם הגדרת גודל התיק ומספר הפריטים:
int nitems = 15; כפול ksSize = nItems * 100.0 / 3.0;בשלב הבא ניצור מערך אקראי המכיל פריט כנאפה אובייקטים (מוגדרים על ידי גודל ו ערך ונניח פריטים אלה באופן אקראי בתוך הכנאפה, בשיטת First Fit:
KnapsackFF ff = KnapsackFF חדש (Stream.generate (KnapsackItem :: random) .limit (nItems) .toArray (KnapsackItem [] :: new), ksSize);לאחר מכן, עלינו ליצור את מנוע:
מנוע מנוע = Engine.builder (ff, BitChromosome.of (nItems, 0.5)) .populationSize (500) .survivorsSelector (TournamentSelector new (5)) .offspringSelector (RouletteWheelSelector חדש ()). משתנים (מוטאטור חדש (0.115), חדש SinglePointCrossover (0.16)) .build ();יש לציין כמה נקודות כאן:
- גודל האוכלוסייה הוא 500
- הצאצאים ייבחרו באמצעות בחירת הטורניר והגלגלת
- כפי שעשינו בסעיף התחתון הקודם, עלינו להגדיר את החליפין עבור הצאצאים שזה עתה נוצרו
יש גם תכונה אחת חשובה מאוד של ג'נטיקס. אנו יכולים לאסוף בקלות את כל הסטטיסטיקה והתובנות מכל משך הסימולציה. אנו הולכים לעשות זאת באמצעות EvolutionStatistics מעמד:
סטטיסטיקה של EvolutionStatistics = EvolutionStatistics.ofNumber ();לבסוף, בואו נפעיל את הסימולציות:
פנוטיפ הטוב ביותר = engine.stream () .limit (bySteadyFitness (7)) .limit (100) .peek (סטטיסטיקה) .collect (toBestPhenotype ());לידיעתך אנו מעדכנים את סטטיסטיקת ההערכה לאחר כל דור, המוגבל ל -7 יציבות יציבות ולכל היותר 100 דורות בסך הכל. בפירוט רב יותר ישנם שני תרחישים אפשריים:
- אנו משיגים 7 דורות יציבים ואז הסימולציה נעצרת
- אנחנו לא יכולים להשיג 7 דורות יציבים בפחות מ -100 דורות, ולכן הסימולציה נעצרת בגלל השנייה לְהַגבִּיל()
חשוב שתהיה מגבלת דורות מקסימאלית, אחרת ייתכן שהסימולציות לא ייפסקו בזמן סביר.
התוצאה הסופית מכילה מידע רב:
+ ------------------------------------------------- -------------------------- + | סטטיסטיקה של זמן | + --------------------------------------------------------- -------------------------- + | בחירה: סכום = 0,039207931000 ש; ממוצע = 0,003267327583 ש | | שינוי: סכום = 0,065145069000 ש '; ממוצע = 0,005428755750 ש | | חישוב כושר: סכום = 0,029678433000 שניות; ממוצע = 0,002473202750 שניות | | ביצוע כולל: סכום = 0,111383965000 שניות; ממוצע = 0,009281997083 ש | + ------------------------------------------------- -------------------------- + | סטטיסטיקה של אבולוציה | + --------------------------------------------------------- -------------------------- + | דורות: 12 | | שונה: סכום = 7 664; ממוצע = 638,666666667 | | נהרג: סכום = 0; ממוצע = 0,000000000 | | לא חוקי: סכום = 0; ממוצע = 0,000000000 | + --------------------------------------------------------- -------------------------- + | נתונים סטטיסטיים על אוכלוסייה + --------------------------------------------------------- -------------------------- + | גיל: מקסימום = 10; ממוצע = 1,792167; var = 4,657748 | | כושר: | | דקה = 0,000000000000 | | מקסימום = 716,684883338605 | | ממוצע = 587,012666759785 | | var = 17309,892287851708 | | std = 131,567063841418 | + --------------------------------------------------------- -------------------------- +בפעם המיוחדת הזו הצלחנו להכניס פריטים עם ערך כולל של 716,68 בתרחיש הטוב ביותר. אנו יכולים גם לראות את הסטטיסטיקה המפורטת של האבולוציה והזמן.
איך לבדוק?
זהו תהליך פשוט למדי - פשוט פתח את הקובץ הראשי הקשור לבעיה והפעל תחילה את האלגוריתם. ברגע שיש לנו רעיון כללי, אז נוכל להתחיל לשחק עם הפרמטרים.
4. מסקנה
במאמר זה סקרנו את תכונות ספריית Jenetics המבוססות על בעיות אופטימיזציה אמיתיות.
הקוד זמין כפרויקט Maven ב- GitHub. שים לב שסיפקנו את דוגמאות הקוד לאתגרי אופטימיזציה רבים יותר, כגון שיא ספרינגסטין (כן, הוא קיים!) ובעיות מוכר מטיילים.
לכל המאמרים בסדרה, כולל דוגמאות אחרות לאלגוריתמים גנטיים, עיין בקישורים הבאים:
- כיצד לעצב אלגוריתם גנטי בג'אווה
- בעיית איש המכירות המטייל בג'אווה
- מיטוב מושבת נמלים
- מבוא לספריית Jenetics (זה)
