בעיית איש המכירות המטייל בג'אווה

1. הקדמה

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

2. חישול מדומה

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

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

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

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

לאלגוריתם יש כמה פרמטרים לעבוד:

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

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

3. בעיית איש מכירות נוסע

בעיית איש המכירות המטייל (TSP) היא בעיית האופטימיזציה למדעי המחשב הידועה ביותר בעולם מודרני.

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

4. דגם ג'אווה

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

@Data class class עיר {private int x; פרטית int y; עיר ציבורית () {this.x = (int) (Math.random () * 500); this.y = (int) (Math.random () * 500); } מרחק כפול ציבוריToCity (עיר עיר) {int x = Math.abs (getX () - city.getX ()); int y = Math.abs (getY () - city.getY ()); להחזיר את Math.sqrt (Math.pow (x, 2) + Math.pow (y, 2)); }}

הקונסטרוקטור של עִיר המחלקה מאפשרת לנו ליצור מיקומים אקראיים של הערים. ה distanceToCity (..) ההיגיון אחראי לחישובים הנוגעים למרחק בין הערים.

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

חלל ציבורי generateInitialTravel () {if (travel.isEmpty ()) נסיעות חדשות (10); Collections.shuffle (נסיעות); }

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

swapCities חלל ציבורי () {int a = createRandomIndex (); int b = createRandomIndex (); previousTravel = נסיעות; עיר x = נסיעה. קבל (א); עיר y = travel.get (b); travel.set (a, y); travel.set (b, x); }

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

חלל ציבורי revertSwap () {travel = previousTravel; }

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

public int getDistance () {int מרחק = 0; עבור (int index = 0; index <travel.size (); index ++) {City starting = getCity (index); יעד עיר; אם (אינדקס + 1 <travel.size ()) {יעד = getCity (אינדקס + 1); } אחר {יעד = getCity (0); } מרחק + = start.distanceToCity (יעד); } מרחק חזרה; }

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

5. יישום חישול מדומה

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

על מנת להתחיל בתהליך עלינו לספק שלושה פרמטרים עיקריים, כלומר מתחיל טמפרטורה, numberOfIterations ו קירור מחיר:

כפול ציבורי לדמות חישול (התחלה כפולה טמפרטורה, מספר אינטל אופציות, קירור כפול מחיר) {כפול t = התחלה טמפרטורה; travel.generateInitialTravel (); bestDistance כפול = travel.getDistance (); נסיעה הנוכחית פתרון = נסיעה; // ...}

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

בשלב הבא אנו מתחילים לולאת סימולציות עיקרית:

עבור (int i = 0; i 0.1) {// ...} אחר {המשך; }}

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

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

currentSolution.swapCities (); CurrentDistance כפול = currentSolution.getDistance (); אם (currentDistance <bestDistance) {bestDistance = currentDistance; } אחר אם (Math.exp ((bestDistance - currentDistance) / t) <Math.random ()) {currentSolution.revertSwap (); }

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

יתר על כן, אנו מחשבים את מרחק הנוכחי. אם מחושב לאחרונה מרחק הנוכחי נמוך מ- bestDistanceאנו שומרים את זה כטוב ביותר.

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

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

t * = cooling rate;

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

שימו לב לעצות המעטות כיצד לבחור את פרמטרי הסימולציה הטובים ביותר:

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

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

6. מסקנה

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

היישום המלא של מאמר זה ניתן למצוא באתר GitHub.


$config[zx-auto] not found$config[zx-overlay] not found