ซิมูเลเต็ดอนีลลิง — การหาค่าเหมาะที่สุดเชิงความน่าจะเป็น (Simulated Annealing: Probabilistic Optimization)
- ปี
- 1983
- ประเภท
- Probabilistic metaheuristic / local search
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
Simulated annealing เป็น metaheuristic แบบ local-search เชิงความน่าจะเป็น ซึ่งถูกนำเสนอโดย Kirkpatrick, Gelatt, และ Vecchi ในปี 1983 โดยจำลองกระบวนการ annealing ทางกายภาพในโลหะวิทยา — ซึ่งวัสดุจะถูกให้ความร้อนแล้วค่อยๆ ทำให้เย็นลงเพื่อไปสู่สถานะผลึกที่มีพลังงานต่ำ — และใช้การเปรียบเทียบนี้เพื่อหลุดออกจาก local optima ในปัญหาการหาค่าเหมาะที่สุดทั้งแบบผสม (combinatorial) และแบบต่อเนื่อง (continuous optimization problems).
แนวคิดเบื้องหลังวิธีการ
ลองจินตนาการถึงการพยายามหาจุดที่ต่ำที่สุดในภูมิประเทศที่เป็นเนินเขาในขณะที่ถูกปิดตา การค้นหาแบบละโมบ (greedy search) โดยตรงจะก้าวลงเขาเสมอและติดอยู่ในหุบเขาแรกที่พบ ซึ่งอาจไม่ใช่หุบเขาที่ลึกที่สุด Simulated annealing แนะนำการสุ่มแบบควบคุม: ในช่วงแรก เมื่อ 'อุณหภูมิ' สูง อัลกอริทึมจะยอมก้าวขึ้นเขาเป็นครั้งคราว โดยยอมรับคำตอบที่แย่กว่าโดยบังเอิญ เมื่ออุณหภูมิลดลงตามตารางการลดอุณหภูมิ (cooling schedule) อัลกอริทึมจะเลือกสรรมากขึ้นเรื่อยๆ และลู่เข้าสู่คำตอบหนึ่ง การยอมรับการเคลื่อนที่ที่แย่กว่าที่อุณหภูมิสูงนี้คือสิ่งที่ทำให้วิธีการนี้สามารถหลุดออกจาก local optima ที่ตื้นและสำรวจพื้นที่ปัญหาได้ทั่วถึงยิ่งขึ้น.
ประวัติศาสตร์
Simulated annealing ถูกนำเสนอโดย Kirkpatrick, Gelatt, และ Vecchi ในบทความสำคัญปี 1983 ของพวกเขาในวารสาร Science ซึ่งเปรียบเทียบอย่างชัดเจนระหว่างการอบอ่อนทางอุณหพลศาสตร์ของของแข็งกับการหาค่าเหมาะที่สุดแบบผสม (combinatorial optimisation) แนวคิดเดียวกันนี้ถูกเสนอโดย Cerny (1985) โดยไม่ขึ้นต่อกันในบริบทของปัญหาการเดินทางของพนักงานขาย (travelling salesman problem) van Laarhoven และ Aarts (1987) ได้ให้การวิเคราะห์ทางทฤษฎีที่เข้มงวดเป็นครั้งแรก โดยพิสูจน์คุณสมบัติการลู่เข้าภายใต้ตารางการลดอุณหภูมิต่างๆ นับตั้งแต่นั้นมา วิธีการนี้ได้กลายเป็นหนึ่งใน metaheuristics ที่ได้รับการศึกษาและนำไปใช้อย่างกว้างขวางที่สุด โดยใช้ในการออกแบบทางวิศวกรรม, การวิจัยดำเนินงาน, การจัดวางวงจรรวม (VLSI layout), และการปรับ hyperparameters ของ machine learning.
ควรใช้เมื่อใด
Simulated annealing สามารถนำไปใช้กับปัญหาใดก็ได้ที่สามารถกำหนดโครงสร้างข้างเคียง (neighbourhood structure) ในพื้นที่คำตอบได้ โดยไม่คำนึงว่าฟังก์ชันเป้าหมายสามารถหาอนุพันธ์ได้ เป็น convex หรือแม้แต่สามารถแสดงผลในเชิงวิเคราะห์ได้หรือไม่ เหมาะอย่างยิ่งสำหรับปัญหาแบบผสม (combinatorial problems) (การจัดตาราง, การวางเส้นทาง, ปัญหาเกี่ยวกับกราฟ) และการหาค่าเหมาะที่สุดแบบกล่องดำ (black-box optimisation) แบบต่อเนื่อง ไม่จำเป็นต้องมีข้อมูลการฝึก (training data) หรือข้อสมมติเกี่ยวกับความเป็นปกติ (normality assumption) ตารางการลดอุณหภูมิและโครงสร้างข้างเคียงต้องได้รับการปรับแต่งให้เข้ากับปัญหา การวนซ้ำน้อยกว่าประมาณ 1,000 ครั้งมีความเสี่ยงที่จะลู่เข้าสู่ local optimum ก่อนเวลาอันควร ซึ่งในกรณีนี้ ควรเลือกใช้ deterministic local search ที่ง่ายกว่าแทน.
ข้อจำกัดและข้อควรพิจารณา
- คุณภาพของคำตอบมีความอ่อนไหวต่อตารางการลดอุณหภูมิ; ตารางที่ไม่ดีอาจให้คำตอบไม่ดีไปกว่าการค้นหาแบบสุ่ม.
- โครงสร้างข้างเคียงต้องได้รับการออกแบบสำหรับแต่ละประเภทของปัญหา ซึ่งต้องใช้ความเชี่ยวชาญเฉพาะด้าน.
- การลู่เข้าสู่ global optimum ต้องการการลดอุณหภูมิที่ช้ามากในทางปฏิบัติ ทำให้เวลาทำงานนานสำหรับการรับประกันคุณภาพสูง.
- ไม่ได้ใช้ประโยชน์จากข้อมูล gradient หรือโครงสร้าง ดังนั้นวิธีการที่ใช้ gradient จึงมีประสิทธิภาพเหนือกว่าในปัญหาที่เรียบและหาอนุพันธ์ได้.
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- สามารถหลุดออกจาก local optima ได้ด้วยการยอมรับคำตอบที่แย่กว่าเชิงความน่าจะเป็น ซึ่งแตกต่างจาก hill-climbing แบบบริสุทธิ์.
- สามารถนำไปใช้กับปัญหาแทบทุกประเภท — เชิงการจัดหมู่ (combinatorial), แบบต่อเนื่อง, แบบผสม (mixed) — ตราบใดที่กำหนดโครงสร้างข้างเคียงได้.
- ไม่ต้องการข้อมูล gradient และไม่สนใจโครงสร้างทางคณิตศาสตร์ของฟังก์ชันเป้าหมาย.
- มีการรับประกันทางทฤษฎีในการลู่เข้าสู่ global optimum ภายใต้การลดอุณหภูมิที่ช้าพอ (Hajek 1988).
- มี hyperparameters น้อย: อุณหภูมิเริ่มต้น, อัตราการลดอุณหภูมิ, และโครงสร้างข้างเคียง.
การประยุกต์ใช้
- ปัญหาการจัดตารางและกำหนดเวลาแบบผสม (combinatorial scheduling and timetabling problems) ที่พื้นที่คำตอบมีขนาดใหญ่เกินกว่าจะค้นหาแบบ exhaustive search ได้.
- ปัญหาการเดินทางของพนักงานขายและปัญหาการวางเส้นทางยานพาหนะ (travelling salesman and vehicle routing problems) ในสาขาโลจิสติกส์และการวิจัยดำเนินงาน.
- การจัดวางวงจร VLSI และการวางผังชิป (chip floor-planning) ในวิศวกรรมไฟฟ้า.
- ปัญหาการพับโปรตีนและการจัดรูปโมเลกุล (protein folding and molecular conformation problems) ในชีววิทยาเชิงคำนวณ.
- การปรับ hyperparameters สำหรับโมเดล machine learning เมื่อไม่มีข้อมูล gradient.
- ปัญหาการจัดสรรทรัพยากรและการมอบหมายงาน (resource allocation and assignment problems) ในสาขาวิศวกรรมและวิทยาการจัดการ.
วิธีการทำงาน
วิธีการทำงาน
อัลกอริทึมเริ่มต้นด้วยคำตอบเริ่มต้น — จุดที่เป็นไปได้ใดๆ ในพื้นที่การค้นหา — และอุณหภูมิเริ่มต้นที่สูง คำตอบเริ่มต้นอาจเป็นการสุ่มหรือเฉพาะเจาะจงกับปัญหา อุณหภูมิเริ่มต้นมักจะตั้งไว้สูงพอที่คำตอบข้างเคียงเกือบทุกอันจะถูกยอมรับในตอนเริ่มต้น.
คำตอบข้างเคียง (neighbouring solution) ถูกสร้างขึ้นโดยการใช้การเปลี่ยนแปลงแบบสุ่มเล็กน้อย (a 'move') กับคำตอบปัจจุบัน โครงสร้างข้างเคียง (neighbourhood structure) ต้องปรับให้เข้ากับปัญหา: สำหรับปัญหาการจัดตาราง (scheduling problem) การเคลื่อนที่อาจเป็นการสลับงานสองงาน สำหรับฟังก์ชันต่อเนื่อง อาจเป็นการเพิ่มการรบกวนแบบสุ่มเล็กน้อยให้กับเวกเตอร์พารามิเตอร์ปัจจุบัน.
คำนวณความแตกต่างของค่าเป้าหมายระหว่างคำตอบใหม่และคำตอบปัจจุบัน หากคำตอบใหม่ดีกว่า จะถูกยอมรับเสมอ หากแย่กว่า จะถูกยอมรับด้วยความน่าจะเป็นที่ลดลงตามขนาดของความเสื่อมและอุณหภูมิปัจจุบัน — โดยทั่วไปคือ exp(−ΔE / T) การยอมรับเชิงความน่าจะเป็นนี้เป็นกลไกหลักที่ป้องกันการลู่เข้าก่อนเวลาอันควร (premature convergence).
หลังจากการวนซ้ำแต่ละครั้ง (หรือหลังจากการเคลื่อนที่จำนวนคงที่ที่อุณหภูมิเดียวกัน) อุณหภูมิจะลดลงตามตารางการลดอุณหภูมิ — โดยทั่วไปคือตารางเรขาคณิต T ← α·T โดยที่ α น้อยกว่า 1 เล็กน้อย การเลือกตารางการลดอุณหภูมิส่งผลอย่างมากต่อคุณภาพของคำตอบ: การลดอุณหภูมิเร็วเกินไปจะทำให้การค้นหาติดอยู่ใน local optimum การลดอุณหภูมิช้าเกินไปจะสิ้นเปลืองเวลาในการคำนวณ.
อัลกอริทึมจะหยุดเมื่ออุณหภูมิลดลงต่ำกว่าเกณฑ์ขั้นต่ำ จำนวนการวนซ้ำสูงสุดถึง หรือคำตอบไม่ดีขึ้นเป็นจำนวนขั้นตอนที่ระบุไว้ คำตอบที่ดีที่สุดที่พบตลอดการทำงานทั้งหมด — ไม่ใช่แค่สถานะสุดท้าย — จะถูกส่งคืนเป็นคำตอบ.
ข้อผิดพลาดที่พบบ่อย
- การวนซ้ำน้อยครั้งเกินไป (ประมาณน้อยกว่า 1,000 ครั้ง) ทำให้ตารางการลดอุณหภูมิทำงานไม่ถูกต้องและทำให้การค้นหาติดอยู่ใน local optimum — ควรเลือกใช้ tabu search หรือ deterministic local search หากเวลาทำงานมีจำกัดอย่างมาก.
- การตั้งอุณหภูมิเริ่มต้นต่ำเกินไปหมายความว่าอัลกอริทึมจะทำงานเหมือน greedy hill-climbing ทันทีและสูญเสียความสามารถในการหลุดออกจาก local optima.
- การตั้งอัตราการลดอุณหภูมิเร็วเกินไป (เช่น α ต่ำกว่า 0.9) ทำให้เกิดการลู่เข้าก่อนเวลาอันควร; ตรวจสอบคุณภาพของคำตอบสุดท้ายโดยการเริ่มต้นใหม่จากคำตอบเริ่มต้นหลายๆ แบบ.
- การใช้การเคลื่อนที่ข้างเคียงที่ออกแบบมาสำหรับปัญหาประเภทหนึ่งกับปัญหาที่แตกต่างกันอาจทำให้การเคลื่อนที่ใช้ไม่ได้หรือไม่สมเหตุสมผล — ตรวจสอบเสมอว่าคำตอบข้างเคียงที่สร้างขึ้นทุกอันเป็นคำตอบที่ใช้ได้.
- การรายงานเฉพาะสถานะสุดท้ายแทนที่จะเป็นคำตอบที่ดีที่สุดที่เคยพบระหว่างการทำงาน อาจพลาดค่าเหมาะที่สุดที่แท้จริงซึ่งพบในขั้นตอนกลาง.
คำถามที่พบบ่อย
ฉันจะเลือกตารางการลดอุณหภูมิได้อย่างไร?
ตารางเรขาคณิต T ← α·T โดยที่ α อยู่ระหว่าง 0.90 ถึง 0.99 เป็นจุดเริ่มต้นที่พบบ่อยที่สุด แนวทางปฏิบัติคือการตั้งอุณหภูมิเริ่มต้นให้สูงพอที่ประมาณ 80% ของการเคลื่อนที่ถูกยอมรับในตอนเริ่มต้น จากนั้นลดลงจนกระทั่งน้อยกว่า 1% ของการเคลื่อนที่ขึ้นเขาถูกยอมรับ หากคุณภาพของคำตอบสุดท้ายไม่ดี ให้ลดอัตราการลดอุณหภูมิลง (เพิ่ม α); หากเวลาทำงานนานเกินไป ให้เร่งขึ้น ควรรันอัลกอริทึมหลายๆ ครั้งจากจุดเริ่มต้นที่แตกต่างกันเพื่อประเมินความทนทาน.
Simulated annealing แตกต่างจาก genetic algorithms หรือ particle swarm optimisation อย่างไร?
Simulated annealing รักษาคำตอบเดียวและสำรวจพื้นที่ข้างเคียงผ่านการรบกวนแบบสุ่ม โดยยอมรับคำตอบที่แย่กว่าเชิงความน่าจะเป็น Genetic algorithms และ particle swarm optimisation รักษาประชากรของคำตอบและใช้การผสมข้าม (crossover), การกลายพันธุ์ (mutation), หรือการเคลื่อนที่ของฝูง (swarm movement) เพื่อพัฒนาประชากรนั้น Simulated annealing โดยทั่วไปจะง่ายต่อการนำไปใช้กับปัญหาที่มีโครงสร้างข้างเคียงตามธรรมชาติ ในขณะที่วิธีการที่ใช้ประชากรอาจมีประสิทธิภาพมากกว่าสำหรับปัญหาแบบต่อเนื่องที่มีมิติสูง.
มีการรับประกัน global optimum หรือไม่?
ในทางทฤษฎี ใช่ ภายใต้เงื่อนไขว่าอุณหภูมิจะลดลงช้าพอ (logarithmic cooling) ในทางปฏิบัติ การลดอุณหภูมิช้าขนาดนั้นไม่สามารถทำได้จริงในเชิงคำนวณ คุณภาพของคำตอบจะดีขึ้นเมื่อลดอุณหภูมิช้าลงและมีการวนซ้ำมากขึ้น แต่ไม่มีการรับประกันในเวลาจำกัด การรันอัลกอริทึมหลายครั้งจากจุดเริ่มต้นที่แตกต่างกันและเก็บคำตอบที่ดีที่สุดที่พบเป็นวิธีปฏิบัติเพื่อเพิ่มความมั่นใจ.
เมื่อใดที่ฉันควรเลือกใช้ tabu search หรือ genetic algorithm แทน?
เลือก tabu search เมื่อคุณต้องการการค้นหาแบบกำหนดแน่นอน (deterministic) ที่นำทางด้วยหน่วยความจำ ซึ่งหลีกเลี่ยงการกลับไปที่คำตอบที่เพิ่งเยี่ยมชมและสามารถใช้ประโยชน์จากโครงสร้างปัญหาได้อย่างมีประสิทธิภาพในเวลาทำงานที่สั้นกว่า เลือก genetic algorithm หรือ particle swarm optimisation เมื่อปัญหามีมิติสูงและต่อเนื่อง หรือเมื่อต้องการประชากรของคำตอบที่หลากหลายเพื่อแมปพื้นที่ของค่าเหมาะที่สุด Simulated annealing เป็นตัวเลือกเริ่มต้นที่ดีสำหรับปัญหาแบบผสมที่มีโครงสร้างข้างเคียงที่ชัดเจนและเมื่อความง่ายในการนำไปใช้มีความสำคัญ.
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Kirkpatrick, S., Gelatt, C.D. & Vecchi, M.P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671-680.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วvan Laarhoven, P.J.M. & Aarts, E.H.L. (1987). Simulated Annealing: Theory and Applications. Springer.
ISBN: 9789027725431คัดลอกแล้ว