การจำลองการอบเหนียว
การจำลองการอบเหนียว ()
เป็นกลวิธีหนึ่งในการแก้ปัญหาการหาค่าเหมาะสมที่สุดเชิงการจัด (combinatorial optimization problem) ซึ่งมักจะใช้เมื่อปริภูมิการค้น () นั้นไม่ต่อเนื่อง การจำลองการอบเหนียวอาจจะมีประสิทธิภาพในการแก้ปัญหาในบางกรณีได้ดีกว่าการแจกแจงจนกว่าจะได้คำตอบ (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 คือ ผลต่างระหว่างค่าฟังก์ชันต้นทุนของผลเฉลยทั้งสองซึ่งมีค่ามากกว่าหรือเท่ากับ 0 และ T คือ อุณหภูมิ)
ในการใช้วิธีการจำลองการอบเหนียวกับการแก้ปัญหาที่เฉพาะเจาะจงอย่างใดอย่างหนึ่ง จะต้องระบุพารามิเตอร์ต่อไปนี้: ปริภูมิสถานะ, พลังงาน (เป้าหมาย) หรือฟังก์ชัน E(), ฟังก์ชัน neighbour() ซึ่งเอาไว้สร้างคำตอบอื่นที่เป็นไปได้ ความน่าจะเป็นที่ยอมรับได้หรือฟังก์ชัน P() และตารางเวลาการหลอม temp() และค่าอุณหภูมิเริ่มต้น ตัวเลือกเหล่านี้จะมีผลกระทบอย่างมากต่อประสิทธิภาพการทำงานของขั้นตอนวิธีการอบเหนียว
ในบางครั้งการเริ่มจากคำตอบเก่าที่ผ่านมาซึ่งเป็นคำตอบที่ดีกว่าคำตอบในปัจจุบันก็ดีกว่าการเริ่มที่สถานะปัจจุบันในทุกๆครั้ง กระบวนการนี้เรียกว่า การเริ่มใหม่ของการจำลองการอบเหนียว การตัดสินใจว่าจะเริ่มใหม่หรือไม่นั้นขึ้นอยู่กับปัจจัยหลายประการ ปัจจัยสำคัญอย่างหนึ่งคือการดูว่าพลังงาน ณ ปัจจุบันสูงกว่าพลังงานที่ดีที่สุดที่เราพบมาแล้วมากเกินไปหรือเปล่า
ตัวอย่างด้านล่างเป็นการนำขั้นตอนวิธีการจำลองการอบเหนียวมาใช้แก้ปัญหาการเดินทางของพนักงานขาย
โดยขั้นตอนวิธีนี้จะรับอาเรย์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
เราก็จะรับทางเดินใหม่ให้เป็นคำตอบของเรา จะสังเกตได้ว่าถ้าค่า T สูง e ก็จะสูงตามไปด้วย
หมายความว่าในขณะที่อุณหภูมิสูงนั้นเราก็มีโอกาสที่จะรับคำตอบไว้เยอะเมื่ออุณหภูมิต่ำลงเราก็จะรับคำตอบน้อยลง