การจำลองการอบเหนียว

จากวิกิพีเดีย สารานุกรมเสรี

การจำลองการอบเหนียว (อังกฤษ: Simulated annealing) เป็นกลวิธีหนึ่งในการแก้ปัญหาการหาค่าเหมาะสมที่สุดเชิงการจัด (combinatorial optimization problem) ซึ่งมักจะใช้เมื่อปริภูมิการค้น (search space) นั้นไม่ต่อเนื่อง การจำลองการอบเหนียวอาจจะมีประสิทธิภาพในการแก้ปัญหาในบางกรณีได้ดีกว่าการแจกแจงจนกว่าจะได้คำตอบ (exhaustive enumeration) หากว่าเป้าหมายเป็นเพียงแค่การหาคำตอบที่จะมาแก้ปัญหาได้ดีในเวลาอันจำกัด ไม่ใช่เพื่อการหาวีธีที่มีประสิทธิภาพที่สุด

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

การอุปมาอุปไมยระหว่างการแก้ปัญหาแบบการหาค่าที่เหมาะที่สุดเชิงการจัดกับกระบวนการอบเหนียวในทางโลหะวิทยานั้นอธิบายได้ดังนี้ สถานะของโลหะจะแทนผลเฉลยที่เป็นไปได้สำหรับปัญหาที่ต้องการหาผลเฉลยที่เหมาะที่สุด สถานะของพลังงานจะเสมือนเป็นค่าของฟังก์ชันเป้าหมาย (Objective function) หรือฟังก์ชันต้นทุน (Cost function) ที่คำนวณได้จากผลเฉลยนั้นๆ ดังนั้นสถานะของพลังงานที่ต่ำที่สุดก็จะเปรียบเสมือนผลเฉลยที่เหมาะที่สุดของปัญหา และการทำให้เย็นลงเร็วเกินไป จะเป็นการค้นพบผลเฉลยเฉพาะพื้นที่

วิธีการจำลองการอบเหนียวนั้นถูกนำเสนอโดย Scott Kirkpatrick, C. Daniel Gelatt and Mario P. Vecchi ในปีค.ศ.1983 ซึ่งดัดแปลงมาจากขั้นตอนวิธี Metropolis-Hastings

ลักษณะโดยทั่วไป[แก้]

ขั้นตอนวิธีในการทำงานจะเป็นลำดับการทำงานแบบวนซ้ำ โดยในแต่ละรอบจะประกอบด้วยการเปลี่ยนแปลงแบบสุ่มจากผลเฉลยปัจจุบันเพื่อสร้างผลเฉลยใหม่ที่ใกล้เคียงกับผลเฉลยปัจจุบัน เมื่อผลเฉลยใหม่ถูกสร้างขึ้นจะคำนวณค่าของฟังก์ชันเป้าหมายหรือฟังก์ชันต้นทุน เพื่อตัดสินใจว่าจะยอมรับให้เป็นผลเฉลยปัจจุบันหรือไม่ หากผลเฉลยใหม่ดีกว่าผลเฉลยปัจจุบันก็จะถูกยอมรับให้เป็นผลเฉลยปัจจุบันแทน แต่ถ้าผลเฉลยใหม่ไม่ดีกว่าผลเฉลยในปัจจุบันก็อาจจะถูกยอมรับได้ โดยใช้กฎบนพื้นฐานความน่าจะเป็นของโบลต์ซมันน์ (Boltzman’s probability) คือ จะมีการสุ่มตัวเลข β ในช่วง 0-1 ขึ้นมาและถ้า β≤e-ΔC/kT ก็จะยอมรับผลเฉลยใหม่ (เมื่อ ΔC คือ ผลต่างระหว่างค่าฟังก์ชันต้นทุนของผลเฉลยทั้งสองซึ่งมีค่ามากกว่าหรือเท่ากับ 0 และ T คือ อุณหภูมิ)

รหัสเทียม[แก้]

s ← s0; e ← E(s)                                // สถานะและค่าพลังงานเริ่มต้น
sbest ← s; ebest ← e                            // คำตอบเริ่มต้นที่ดีที่สุด
k ← 0                                           // สร้างตัวนับเพื่อประเมินค่าระดับพลังงาน
while k < kmax and e > emax                     // เมื่อค่าระดับพลังงานยังไม่มากพอหรือพลังงานที่ได้ยังน้อยเกินไปให้ทำวงวนต่อ
  snew ← neighbour(s)                           // เลือกผลเฉลยใหม่ที่ใกล้เคียง
  enew ← E(snew)                                // คำนวณพลังงานของผลเฉลยใหม่
  if P(e, enew, temp(k/kmax)) > random() then   // ตรวจดูว่าควรจะยอมรับค่าใหม่หรือไม่
    s ← snew; e ← enew                          // ถ้าใช่ก็เปลี่ยนค่าสถานะเป็นค่าใหม่
  if enew < ebest then                          // ตรวจสอบดูว่าคำตอบใหม่ดีกว่าคำตอบที่ดีสุดที่รู้มาหรือเปล่า
    sbest ← snew; ebest ← enew                  // ถ้าใช่ก็ให้เปลี่ยนคำตอบที่ได้เป็นคำตอบที่ดีที่สุด
  k ← k + 1                                     // เสร็จสิ้นการตรวจสอบคำตอบไปหนึ่งคำตอบ
return sbest                                    // ส่งกลับคำตอบที่ดีที่สุดที่หาได้

การเลือกพารามิเตอร์[แก้]

ในการใช้วิธีการจำลองการอบเหนียวกับการแก้ปัญหาที่เฉพาะเจาะจงอย่างใดอย่างหนึ่ง จะต้องระบุพารามิเตอร์ต่อไปนี้: ปริภูมิสถานะ, พลังงาน (เป้าหมาย) หรือฟังก์ชัน E(), ฟังก์ชัน neighbour() ซึ่งเอาไว้สร้างคำตอบอื่นที่เป็นไปได้ ความน่าจะเป็นที่ยอมรับได้หรือฟังก์ชัน P() และตารางเวลาการหลอม temp() และค่าอุณหภูมิเริ่มต้น ตัวเลือกเหล่านี้จะมีผลกระทบอย่างมากต่อประสิทธิภาพการทำงานของขั้นตอนวิธีการอบเหนียว

การเริ่มใหม่[แก้]

ในบางครั้งการเริ่มจากคำตอบเก่าที่ผ่านมาซึ่งเป็นคำตอบที่ดีกว่าคำตอบในปัจจุบันก็ดีกว่าการเริ่มที่สถานะปัจจุบันในทุกๆครั้ง กระบวนการนี้เรียกว่า การเริ่มใหม่ของการจำลองการอบเหนียว การตัดสินใจว่าจะเริ่มใหม่หรือไม่นั้นขึ้นอยู่กับปัจจัยหลายประการ ปัจจัยสำคัญอย่างหนึ่งคือการดูว่าพลังงาน ณ ปัจจุบันสูงกว่าพลังงานที่ดีที่สุดที่เราพบมาแล้วมากเกินไปหรือเปล่า

ตัวอย่างการใช้งาน[แก้]

ตัวอย่างด้านล่างเป็นการนำขั้นตอนวิธีการจำลองการอบเหนียวมาใช้แก้ปัญหาการเดินทางของพนักงานขาย

tspSA( d[1..n][1..n] ) {
 tour = initialTour( d )
 maxT = T = tourLength(d, tour)
 while ( T > 0.001 ) ) {
  N = maxT – T;
  for (i = 1; i <= N; i++) {
   newTour = nextTour( minT )
   dE = tourLength(d,newTour) - tourLength(d,tour)
   if (dE < 0 OR random(0,1) < e-dE/kT ){
    tour = newTour;
   }
  }
  T *= 0.999
 }
 return tour;
}

โดยขั้นตอนวิธีนี้จะรับอาเรย์2มิติที่เป็นเก็บข้อมูลของจุดที่แทนเมืองต่างๆและระยะทางระหว่างเมือง จากนั้นให้สุ่มทางเดินขึ้นมาหนึ่งทางเก็บในตัวแปร tour จากนั้นก็คำนวณหาความยาวของทางเดินนั้นเก็บในตัวแปร maxT กับ T ซึ่ง T แทนอุณหภูมิของระบบ เราจะให้ T ที่ได้นั้นถือว่าเป็นอุณหภูมิเริ่มต้นของระบบ จากนั้นก็เข้าวงวนโดยตรวจสอบค่า T และค่า T จะลดลงเรื่อยๆ ถ้า T ลดลงจน T≤0.001 ก็จะเลิกทำและส่งค่า tour ที่ได้กลับไป โดยในวงวนจะมีค่า N ซึ่งเป็นผลต่างระหว่าง maxT กับ T จากนั้นจะเข้าสู่วงวน for ซึ่งจะสังเกตได้ว่ายิ่งถ้าค่า T สูงจำนวนรอบทำซ้ำจะน้อยแต่ถ้าค่า T ต่ำจำนวนรอบทำซ้ำจะเยอะ โดยในวงวน for ก็จะคำนวณหาทางเดินถัดไป (neighbor solution)โดยเก็บค่าใส่ตัวแปร dE โดยถ้า E เป็นจำนวนบวกแสดงว่าทางเดินใหม่ที่ได้จะยาวขึ้น ถ้า E เป็นจำนวนลบแสดงว่าทางเดินใหม่ที่ได้จะสั้นลง จากนั้นเราก็ดูเงื่อนไขว่าถ้า dE<0 หรือถ้าเราสุ่มตัวเลขที่อยู่ระหว่าง 0 กับ 1 ขึ้นมาแล้วน้อยกว่า e-dE/kT เราก็จะรับทางเดินใหม่ให้เป็นคำตอบของเรา จะสังเกตได้ว่าถ้าค่า T สูง e-dE/kT ก็จะสูงตามไปด้วย หมายความว่าในขณะที่อุณหภูมิสูงนั้นเราก็มีโอกาสที่จะรับคำตอบไว้เยอะเมื่ออุณหภูมิต่ำลงเราก็จะรับคำตอบน้อยลง



วิธีที่เกี่ยวเนื่อง[แก้]

ดูเพิ่ม[แก้]

อ้างอิง[แก้]

  1. เอกสารประกอบการสอนวิชาการออกแบบอัลกอริทึมของ รศ.ดร.สมชาย ประสิทธิ์จูตระกูล
  2. http://www2.cp.eng.chula.ac.th/~somchai/2110427/2546/demo/HW2-TSP/saTSP.htm เก็บถาวร 2009-08-27 ที่ เวย์แบ็กแมชชีน
  3. Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P. (1983). "Optimization by Simulated Annealing". Science 220 (4598): 671–680. doi:10.1126/science.220.4598.671. JSTOR 1690046. PMID 17813860.
  4. http://www.denison.edu/academics/departments/mathcs/schmidt.pdf

แหล่งข้อมูลอื่น[แก้]