Simulated Annealing

Euclidean Traveling Salesperson Problem

การจำลองการอบเหนียว (simulated annealing ขอเรียกสั้นๆ ว่า SA) เป็นกลวิธีหนึ่งซึ่งได้รับความนิยมมาก ในการแก้ปัญหาการหาค่าเหมาะที่สุดเชิงการจัด (combinatorial optimization problem) ซึ่งเป็นปัญหา NP–hard จะว่าไปแล้ว SA เป็นกลวิธีการค้นผลเฉลยแบบเฉพาะที่ (local search) ซึ่งมีกระบวนการทำงานแบบวนซ้ำ (iterative) เพื่อค้นผลเฉลยในปริภูมิผลเฉลยไปเรื่อยๆ จนกว่าจะได้ผลลัพธ์ที่พอใจ โดยเริ่มจากผลเฉลยเริ่มต้น 

ในการบ้านครั้งนี้เราสนใจที่จะนำ SA มาใช้แก้ปัญหาการเดินทางของพนักงานขาย (traveling salesperson problem - ขอเรียกสั้นๆ ว่า TSP) โดยจะเป็น TSP บนจุดต่างๆ ในระนาบสองมิติ สิ่งที่ต้องการหาก็คือเส้นทางสั้นสุดที่ผ่านจุดทุกๆ จุดๆ ละหนึ่งครั้ง แล้วกลับมาที่จุดตั้งต้น TSP เป็นปัญหา NP-hard ในปัจจุบันยังไม่มีใครหาอัลกอริทึมซึ่งให้เส้นทางการเดินทางที่สั้นสุดสำหรับทุกๆ instances ของปัญหาได้ในเวลาแบบพหุนาม อย่างไรก็ตามเราสามารถใช้ SA หาเส้นทางที่สั้นๆ ได้ในเวลาที่ยอมรับได้

การทำงานของ SA นั้นล้อเลียนอุณหพลศาสตร์ของกระบวนการอบเหนียว (annealing) ซึ่งเป็นขั้นตอนการลดอุณหภูมิระหว่างการหลอมโลหะเพื่อให้ได้โลหะที่อยู่ในสภาวะที่เหมาะที่สุด (เพื่อให้ได้โลหะที่เหนียว ไม่เปราะ) ในกรณีที่เรานำ SA มาแก้ TSP เราเปรียบเส้นทางการเดินทางที่หาได้ปัจจุบันเสมือนกับเป็นสถานะปัจจุบันของโครงสร้างโลหะในระบบ เปรียบความยาวของเส้นทางเสมือนพลังงานของโครงสร้างของโลหะ และเปรียบการทำงานแบบวนซ้ำเสมือนกับการค่อยๆ ลดอุณหภูมิลงเรื่อยๆ ระหว่างการอบเหนียว ในวงวนการทำงานนั้นจะประกอบด้วยการสร้างเส้นทางใหม่โดยการปรับเปลี่ยนเส้นทางปัจจุบัน จากนั้นตัดสินใจว่าจะยอมรับเส้นทางใหม่ที่หาได้หรือไม่ ซึ่งเปรียบเสมือนกับการเปลี่ยนแปลงโครงสร้างของโลหะระหว่างการอบเหนียว

ประเด็นสำคัญก็อยู่ตรงที่เกณฑ์การยอมรับเส้นทางใหม่นี้ว่าจะตัดสินใจอย่างไร ตรงนี้เองที่อาศัยความรู้จากกระบวนการทางฟิสิกส์ระหว่างการอบเหนียว ซึ่งจะยอมรับโครงสร้างใหม่เสมอถ้าดีกว่า แต่ถ้าเลวลง ก็อาจจะยอมรับภายใต้ความน่าจะเป็นซึ่งมีค่าแปรตามอุณหภูมิขณะนั้นในรูปแบบ e-dE/kt (dE คือพลังงานที่เปลี่ยนแปลง k คือค่าคงตัวของโบลต์ซมันน์ – Boltzmann และ t คืออุณหภูมิปัจจุบันของการอบเหนียว) สำหรับกรณี TSP ก็หมายความเราจะยอมรับเส้นทางใหม่ที่หาได้เสมอถ้าเส้นทางใหม่นั้นมีความยาวสั้นกว่า แต่ถ้ายาวกว่าเราจะยอมรับภายใต้ความน่าจะเป็นในลักษณะเดียวกัน ตรงนี้ตีความได้ว่าเรายอมรับเส้นทางที่ยาวกว่าได้ง่ายในระยะแรกของการวนซ้ำ (เมื่ออุณหภูมิสูง) แต่จะยอมรับเส้นทางที่ยาวกว่ายากขึ้นเรื่อยๆ เมื่ออุณหภูมิลดลง และยอมรับเส้นทางที่ยาวกว่าน้อยได้ง่ายกว่าที่ยาวกว่ามาก การวนซ้ำจะสิ้นสุดเมื่อถึงอุณหภูมิเย็น เขียนโครงหลักของการทำงานได้ดังนี้

 TspSA( p ) {
   tour = initialTour( p )
   t = high_temperature
   while (isHot(t)) {
     do {
       newTour = nextTour(tour)
       dE = length(newTour,p)-length(tour,p)
       if ( dE < 0 || random(0,1) < e-dE/kt ) 
          tour = newTour
     } while( not doneForOneTemperature() )
     t = 0.999 * t
   }
 }

hw427-tsp.jlab

ในแฟ้มนี้มีเมท็อด tspSA ของคลาส TSPwindow และตัวคลาส TSP_SA ที่มีส่วนเกียวข้อง  TSPwindow เป็นคลาสที่เขียนให้เรียบร้อยแล้ว ไม่ต้องแก้ไขใดๆ  เรามาทำความเข้าใจกับเมท็อด tspSA ในคลาสนี้กัน

 private void tspSA(double[][] g) {
   if (tour == null) tour = TSP_SA.initialTour(g.length);
   Thread thisThread = Thread.currentThread();
   while (thisThread == tspThread) { // is alive ?
     pausePressed = false;
     tour = TSP_SA.getTour(TSPwindow.this, g, tour);
     updateTour(tour);
     if (!pausePressed) break; // finished ?
     if (thisThread != tspThread) break; // exit ?
     while (pausePressed) lockPause.lock();  // paused 
   }
 }

เมท็อดนี้ถูกเรียกภายใน run เมท็อดของ thread จึงมีการตรวจสอบว่า thread ตายหรือยัง โดยการพิจารณาเงื่อนไขใน while loop ตัวแปร pausePressed จะเป็นจริงถ้าผู้ใช้ไปกดปุ่ม pause เพื่อหยุดการทำงานชั่วครู่   การเรียก TSP_SA.getTour( )  เป็นการสั่งให้ทำ simulated annealing เพื่อหาการเดินทางไปเรื่อยๆ จนกว่าจะเสร็จ หรือไม่ก็เมื่อผู้ใช้กดปุ่ม PAUSE หรือไม่ก็เมื่อผู้ใช้เลิกโปรแกรมไปเลย  ก็จะ return การทำงานกลับมา  เราก็เพียงแต่ตรวจสอบว่าเป็นกรณีใด ถ้าเป็นการกดปุ่ม pause ก็จะทำ lockPause.lock( ) ซึ่งเป็นกลไกของโปรแกรมที่เขียนซึ่งทำให้การทำงานที่เมท็อดนี้ "ค้าง" จนกว่าจะมีใครสักคนเรียกเมท็อด lockPause.unlock( )  (ตรงนี้จะถูกเรียกเมื่อผู้ใช้กดปุ่ม start อีกครั้งหลัง pause)

คราวนี้มาดู TSP_SA.getTour( ) ดีกว่า เมท็อดนี้ก็เขียนให้เรียบร้อยแล้วเช่นกัน (ไม่ต้องไปแก้ไข) ดังนี้

 public static int[] getTour(TSPwindow window,
                     double[][] graph, int[] tour) {
   double temperature = window.getTemperature();
   double temperatureFactor = window.getTemperatureFactor();
   do {
     tour = oneAnnealingStep(tour, graph, temperature);
     window.updateTour(tour);
     window.setTemperature(temperature);
     temperature *= temperatureFactor;
     try { Thread.sleep(30); }
     catch (InterruptedException e) {};
   } while (temperature > 0.001 && !window.pausePressed());
   return tour;
 }

สิ่งที่รับเข้ามาก็คือ window เป็น window ที่มีไว้รับค่าจากผู้ใช้และแสดงผลให้เห็น  graph เป็น adjacency matrix แทน graph และ tour เป็น array 1 มิติ เก็บลำดับของหมายเลข vertices ต่างๆ ซึ่งแทนลำดับของเมืองที่พนักขายเดินทาง

สองบรรทัดแรกเป็นการรับอุณหภูมิ (temperature) และตัวปรับลดอุณหภูมิ (temperatureFactor) จากนั้นเข้าวงวนการทำงาน เริ่มด้วยการเรียก oneAnnealingStep( ) ซึ่งเป็นเมท็อดที่นักเรียกต้องเขียนเองอย่างละเอียด เราส่งทางเดินที่หาได้จากรอบที่แล้ว ตัวกราฟ และอุณหภูมิ ไปให้ เพื่อให้ oneAnnealingStep( ) จัดการปรับเปลี่ยนทางเดินที่ได้รับไปเรื่อยๆ ณ อุณหภูมิที่กำหนดให้ (ปรับเรื่อยๆ ในที่นี้หมายความว่ามีการปรับไปจำนวนครั้งตามแต่พอใจ เช่นมีการปรับทางเดินเป็นจำนวนครั้ง เท่ากับจำนวนเมืองเป็นต้น  เมื่อ oneAnnealingStep( ) ทำเสร็จ ก็จะแสดงทางเดินใหม่ที่ได้รับและอุณหภูมิ (windows.updateTour( ) และ window.setTemperature( )) แล้วก็ปรับลดอุณหภูมิลง (temperatureFactor ต้องมีค่า < 1 โดยทั่วไปควรปรับลงอย่างช้าๆ เช่นให้ temperatureFactor = 0.999 เป็นต้น)  ปรับเสร็จ ก็หยุดพักสัก 30ms ให้ user เห็นการเปลี่ยนแปลง  แล้วก็ตรวจสอบว่าสมควรเลิกได้หรือยัง  โดยจะเลิกการทำงานก็เมื่อ อุณหภูมิเย็นพอ หรือไม่ผู้ใช้กดปุ่มหยุดหรือเลิกการทำงาน

สิ่งที่ต้องทำ

นักเรียนต้องเขียนสองเมท็อดในคลาส TSP_SA ที่มี pseudo-code ดังนี้

 public static int[] initialTour(int n) {
   int [] tour = new int[n];
   tour[] <-- any permutation of 1,2,...,n
   return tour
 }
 private static int[] oneAnnealingStep(int[] tour,
             double [][] graph, double temperature) {
   for(i=1 to tour.length) {
     newTour <-- create new permutation of 1,2,..,n from
              the current tour
     dE <-- length(graph, newTour) -  length(graph, tour)
     if (dE < 0 or random(0 to 1) < exp(-dE/temperature))
       tour <-- newTour
   }
   return tour
 }

 

สมชาย ประสิทธิ์จูตระกูล
2110427 : การวิเคราะห์และออกแบบอัลกอริทึม