การจำลองการอบเหน ยว อ งกฤษ Simulated annealing เป นกลว ธ หน งในการแก ป ญหาการหาค าเหมาะสมท ส ดเช งการจ ด combinatorial o

การจำลองการอบเหนียว (อังกฤษ: 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 ก็จะสูงตามไปด้วย หมายความว่าในขณะที่อุณหภูมิสูงนั้นเราก็มีโอกาสที่จะรับคำตอบไว้เยอะเมื่ออุณหภูมิต่ำลงเราก็จะรับคำตอบน้อยลง

วิธีที่เกี่ยวเนื่อง

Quantum annealing
Stochastic tunneling
Tabu search
Reactive search optimization
Stochastic gradient descent
Genetic algorithms
Graduated optimization
Ant colony optimization (ACO)
The cross-entropy method (CE)
Harmony search
Stochastic optimization
Particle swarm optimization
Intelligent Water Drops (IWD)
Parallel tempering

ดูเพิ่ม

Adaptive simulated annealing
Markov chain
Combinatorial optimization
Automatic label placement
Multidisciplinary optimization
Place and route
Molecular dynamics
Traveling salesman problem
Reactive search optimization
Graph cuts in computer vision
Particle swarm optimization
Intelligent Water Drops

อ้างอิง

เอกสารประกอบการสอนวิชาการออกแบบอัลกอริทึมของ รศ.ดร.สมชาย ประสิทธิ์จูตระกูล
http://www2.cp.eng.chula.ac.th/~somchai/2110427/2546/demo/HW2-TSP/saTSP.htm 2009-08-27 ที่ เวย์แบ็กแมชชีน
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.
http://www.denison.edu/academics/departments/mathcs/schmidt.pdf

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

วิดีโอจำลองแนวคิดของขั้นตอนวิธีการจำลองการอบเหนียว
ภาพจำลองการใช้การจำลองการอบเหนียวแก้ปัญหา N-Queens puzzle 2009-08-30 ที่ เวย์แบ็กแมชชีน