Simulated Annealing
SA ถูกพัฒนาขึ้นโดย Kirkpatrick, Gelatt and Vecchi (1983) ขั้นตอนวิธีนี้มี พื้นฐานการทำงานมาจากการอุปมาอุปไมยระหว่างการ annealing โลหะกับการแก้ปัญหาแบบการหาค่าเหมาะสมที่สุดเชิงการจัด (combinatorial optimization problem)
Annealing คือ กระบวนการอบเหนียวซึ่งเป็นการลดอุณหภูมิระหว่างการหลอมโดยจะให้ความร้อนและมีการลดอุณหภูมิลงอย่างช้าๆ จนกระทั่งโลหะอยู่ในสภาวะที่เหมาะสมที่สุด คือ ได้โลหะที่เหนียวไม่เปราะ โดยอะตอมจะมีพลังงานสูงเมื่ออยู่ในอุณหภูมิที่สูงและจะมีอิสระในการจัดเรียงตัวมาก เมื่อมีการลดอุณหภูมิพลังงานก็จะลดลงตามไปด้วย โครงสร้างของโลหะจะจัดเข้าอย่างเป็นระเบียบเมื่อระบบมีพลังงานต่ำที่สุด ถ้ามีการลดอุณหภูมิลงอย่างรวดเร็วหรือทำให้เย็นเร็วเกินไป ก็จะทำให้โครงสร้างของโลหะไม่สม่ำเสมอและเกิดรอยร้าวขึ้นได้
การอุปมาอุปไมยระหว่างการแก้ปัญหาแบบการหาค่าที่เหมาะที่สุดเชิงการจัดกับกระบวนการ Annealing คือ สถานะของโลหะจะแทนผลเฉลยที่เป็นไปได้สำหรับปัญหาที่ต้องการหาผลเฉลยที่เหมาะที่สุด สถานะของพลังงานจะเสมือนเป็นค่าของฟังก์ชั่นเป้าหมาย (Objective function) หรือฟังก์ชั่นต้นทุน (Cost function) ที่คำนวณได้จากผลเฉลยนั้นๆ ดังนั้นสถานะของพลังงานที่ต่ำที่สุดก็จะเปรียบเสมือนผลเฉลยที่เหมาะที่สุดของปัญหา และการทำให้เย็นลงเร็วเกินไป ก็คือการค้นพบผลเฉลยเฉพาะพื้นที่
ขั้นตอนวิธีในการทำงานจะเป็นลำดับการทำงานแบบวนซ้ำ โดยในแต่ละรอบจะประกอบด้วยการเปลี่ยนแปลงแบบสุ่มจากผลเฉลยปัจจุบันเพื่อสร้างผลเฉลยใหม่ที่ใกล้เคียง (Neighbourhood) กับผลเฉลยปัจจุบัน (Current solution) เมื่อผลเฉลยใหม่ถูกสร้างขึ้นจะคำนวณค่าของฟังก์ชั่นเป้าหมายหรือฟังก์ชั่นต้นทุน เพื่อตัดสินใจว่าจะยอมรับให้เป็นผลเฉลยปัจจุบันหรือไม่ หากผลเฉลยใหม่ดีกว่าผลเฉลยปัจจุบันก็จะถูกยอมรับให้เป็นผลเฉลยปัจจุบันแทน แต่ถ้าผลเฉลยใหม่ไม่ดีกว่าผลเฉลยในปัจจุบันก็อาจจะถูกยอมรับได้ โดยใช้กฎบนพื้นฐานความน่าจะเป็นของโบลต์ซมันน์ (Boltzman’s probability) คือ จะมีการสุ่มตัวเลข d ในช่วง 0-1 ขึ้นมาและถ้า d £ e(-DC/T) ก็จะยอมรับผลเฉลยใหม่ (เมื่อ DC คือ ผลต่างระหว่างค่าฟังก์ชั่นต้นทุนของผลเฉลยทั้งสองซึ่งมีค่ามากกว่าหรือเท่ากับ 0 และ T คือ อุณหภูมิ)
หากนำ SA มาแก้ปัญหาการจัดตาราง อาจจะสามารถพิจารณาว่ามี objects ที่ต้องจัดตารางอยู่จำนวนหนึ่ง โดยเป้าหมายคือต้องการหาตารางที่ทำให้ได้ค่าฟังก์ชั่นต้นทุน (หรือฟังก์ชั่นเป้าหมาย) ต่ำสุด ตารางเริ่มต้นก็จะถูกสร้างขึ้นโดยการสุ่มจัดตารางของ objects เหล่านั้น ส่วนค่าเริ่มต้นของฟังก์ชั่นต้นทุน (CO) และอุณหภูมิ (TO) จะถูกคำนวณค่าออกมา ลำดับต่อไปก็จะมีการสร้างตารางใหม่โดยวิธีสุ่ม Objects แล้วทำการสลับที่การจัดเรียงจากนั้นทำการคำนวณค่าฟังก์ชั่นต้นทุนที่เปลี่ยนไป (DC) ถ้า DC £ 0 ตารางใหม่ก็จะถูกยอมรับอย่างไรก็ตาม ถ้า C £ e(-DC/T) และทำการสุ่มค่าตัวเลข d ในช่วง 0 – 1 ถ้า d £ e(-DC/T) ตารางใหม่จะถูกยอมรับและหลังจากดำเนินการสลับที่ในตาราง อุณหภูมิก็จะลดลงด้วยอัตราการลดอุณหภูมิที่กำหนด R โดย Tn = Tn-1 *R เมื่อ 0 £ R < 1 และ T เป็นเลขจำนวนจริง
ตัวอย่างของงานวิจัยที่ประยุกต์ใช้ SA คือ Abramson (1991) ได้ใช้ SA แก้ปัญหาการจัดตารางสอนของโรงเรียน โดยทดสอบกับข้อมูลทั้งที่ได้จากการสุ่มแบบอัตโนมัติจากโปรแกรมและข้อมูลจริงจากโรงเรียนมัธยมศึกษา โดยมีเป้าหมายเพื่อให้ได้ตารางที่มีค่าฟังก์ชั่นต้นทุนน้อยที่สุด และได้ทดสอบกับขั้นตอนวิธีแบบอนุกรม (Serial) พบว่าค่าเฉลี่ยเริ่มต้นของ ฟังก์ชั่นต้นทุนจะสูงขึ้นตามความซับซ้อนของปัญหา ค่าฟังก์ชั่นต้นทุนน้อยที่สุดได้มาจากการกำหนดอัตราการลดอุณหภูมิ (cooling rate) อย่างช้าๆ และพบว่าใช้เวลาในการประมวลผลนานมาก จึงได้เสนอแนะขั้นตอนวิธีแบบขนาน (parallel) เพื่อช่วยลดเวลาในการประมวลผล
ความเห็น (2)
ขอบคุณสำหรับบทความ ค่ะ
ขอบคุณครับ