การอบอ่อนจำลองแบบหลายวัตถุประสงค์ (Multi-Objective Simulated Annealing: MOSA)
- ผู้เสนอ
- Serafini, P.; Czyzak, P. and Jaszkiewicz, A.
- ปี
- 1992–1998
- ประเภท
- Metaheuristic / Pareto-based optimizer
- กลุ่มวิธี
- Simulation / optimization
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
Multi-Objective Simulated Annealing (MOSA) เป็นการขยายแนวคิดของ เมตาฮิวริสติก (metaheuristic) แบบ simulated annealing แบบดั้งเดิมไปยังปัญหาที่มีฟังก์ชันวัตถุประสงค์ที่ขัดแย้งกันตั้งแต่สองฟังก์ชันขึ้นไป แทนที่จะลู่เข้าสู่ค่าที่เหมาะสมที่สุดเพียงค่าเดียว MOSA จะสำรวจปริภูมิคำตอบแบบสุ่มและเก็บรักษาคลังของคำตอบที่ไม่ถูกครอบงำ (non-dominated) ไว้ ซึ่งนำเสนอทางเลือกการแลกเปลี่ยนที่หลากหลายแก่ผู้ตัดสินใจ แทนที่จะเป็นคำตอบเดียวที่กำหนดไว้ล่วงหน้า
แนวคิดเบื้องหลังวิธีการ
Simulated annealing แบบดั้งเดิมเลียนแบบการเย็นตัวอย่างควบคุมของโลหะเพื่อหลีกเลี่ยงค่าเหมาะที่สุดเฉพาะที่ (local optima) โดยยอมรับคำตอบที่แย่กว่าเป็นครั้งคราวเมื่ออุณหภูมิสูง จากนั้นจึงมีความเฉพาะเจาะจงมากขึ้นเมื่ออุณหภูมิลดลง MOSA ใช้กลไกการหลุดพ้นแบบสุ่มเดียวกันนี้กับวัตถุประสงค์หลายอย่างพร้อมกัน เมื่อคำตอบตัวเลือก (candidate)แย่ลงในบางวัตถุประสงค์ แต่ดีขึ้นในวัตถุประสงค์อื่น ๆ ตรรกะการครอบงำจะกำหนดว่าคำตอบนั้นจะเข้าสู่คลัง Pareto หรือไม่ กำหนดการเย็นตัวจะค่อย ๆ ลดความเป็นสุ่มลง โดยมุ่งเน้นการค้นหาใกล้กับขอบเขต Pareto ผลลัพธ์ที่ได้คือการประมาณค่าของขอบเขต Pareto ที่แท้จริง โดยไม่จำเป็นต้องใช้ข้อมูลเกรเดียนต์หรือข้อสมมติฐานเกี่ยวกับความนูน
ประวัติศาสตร์
Simulated annealing ถูกนำเสนอโดย Kirkpatrick et al. ในปี 1983 Serafini (1992) เป็นหนึ่งในคนกลุ่มแรก ๆ ที่เสนอการขยายไปยังวัตถุประสงค์หลายอย่างอย่างเป็นทางการ Czyzak และ Jaszkiewicz (1998) ได้พัฒนา Pareto Simulated Annealing (PSA) ซึ่งกำหนดให้คลัง Pareto เป็นโครงสร้างผลลัพธ์หลัก และให้สูตรเกณฑ์การยอมรับที่ใช้กันอย่างแพร่หลายในปัจจุบัน ตั้งแต่นั้นมา MOSA ได้ถูกนำไปใช้ในการออกแบบทางวิศวกรรม การจัดตารางเวลา และโลจิสติกส์
ควรใช้เมื่อใด
ใช้ MOSA เมื่อคุณเผชิญกับปัญหาการหาค่าที่เหมาะสมที่สุดที่มีวัตถุประสงค์ที่ขัดแย้งกันตั้งแต่สองวัตถุประสงค์ขึ้นไป และมีทั้งตัวแปรการตัดสินใจแบบต่อเนื่องหรือแบบผสม โดยเฉพาะอย่างยิ่งเมื่อภูมิทัศน์ของวัตถุประสงค์ไม่เป็น convex, มีหลายโหมด หรือไม่ต้องใช้เกรเดียนต์ (gradient) เหมาะสำหรับปัญหาการจัดตารางเวลา การกำหนดเส้นทาง การออกแบบทางวิศวกรรม และการจัดสรรทรัพยากร ซึ่งขอบเขตการแลกเปลี่ยนที่ชัดเจนมีประโยชน์มากกว่าผลรวมถ่วงน้ำหนักเพียงค่าเดียว ควรเลือก MOSA มากกว่า Monte Carlo แบบสุ่มล้วน ๆ เมื่อคุณต้องการการหาค่าที่เหมาะสมที่สุด แทนที่จะเป็นการวัดปริมาณความไม่แน่นอน อย่าใช้ MOSA เมื่อปัญหามีวัตถุประสงค์เดียว (SA แบบดั้งเดิมก็เพียงพอแล้ว) เมื่อขอบเขต Pareto ต้องหาได้อย่างแม่นยำ (อัลกอริทึมที่แม่นยำจะดีกว่าสำหรับปัญหาขนาดเล็ก) เมื่อจำนวนวัตถุประสงค์เกินประมาณห้า (วิธีการที่ใช้ hypervolume จะปรับขนาดได้ดีกว่า) หรือเมื่อการประเมินวัตถุประสงค์มีค่าใช้จ่ายสูงมากต่อการเรียก (วิธีการที่ใช้ surrogate จะดีกว่า)
ข้อจำกัดและข้อควรพิจารณา
- คุณภาพของคำตอบและการครอบคลุมขอบเขต Pareto ขึ้นอยู่กับการเลือกอุณหภูมิเริ่มต้น อัตราการเย็นตัว และตัวดำเนินการเพื่อนบ้าน ซึ่งต้องมีการปรับแต่งเฉพาะสำหรับปัญหา
- การลู่เข้าสู่ขอบเขต Pareto ที่มีคุณภาพสูงอาจต้องใช้การประเมินวัตถุประสงค์จำนวนมาก ทำให้ช้าสำหรับแบบจำลองการจำลองที่มีค่าใช้จ่ายสูง
- การจัดการและอัปเดตคลัง Pareto ทำให้เกิดค่าใช้จ่ายเพิ่มเติม และคลังอาจมีขนาดใหญ่ เพิ่มต้นทุนหน่วยความจำและการเปรียบเทียบ
- แตกต่างจากวิธีการแบบประชากร (เช่น NSGA-II) ลักษณะเส้นทางเดียวของ MOSA พื้นฐานอาจทำให้การครอบคลุมขอบเขต Pareto ไม่สม่ำเสมอ
- การรับประกันการลู่เข้าทางทฤษฎีต้องการกำหนดการเย็นตัวที่ช้าอย่างไม่สิ้นสุด ซึ่งไม่สามารถทำได้จริง กำหนดการที่จำกัดจะเสียสละการรับประกันความเป็นค่าที่เหมาะสมที่สุด
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- ไม่ต้องการข้อมูล gradient และจัดการกับภูมิทัศน์ของวัตถุประสงค์ที่ไม่เป็น convex, ไม่ต่อเนื่อง และมีหลายโหมด
- การยอมรับคำตอบที่ด้อยกว่าแบบสุ่มช่วยให้หลีกหนีจากขอบเขต Pareto เฉพาะที่ซึ่งวิธีการแบบละโมบเพียงอย่างเดียวติดอยู่
- สร้างค่าประมาณที่หลากหลายของขอบเขต Pareto ทั้งหมดในการทำงานเดียว ทำให้ผู้ตัดสินใจมีทางเลือกในการแลกเปลี่ยนที่ชัดเจน
- การนำไปใช้งานนั้นตรงไปตรงมา และกำหนดการเย็นตัวให้พารามิเตอร์ที่เข้าใจง่ายเพื่อปรับสมดุลระหว่างการสำรวจและการใช้ประโยชน์
- สามารถนำไปใช้กับปัญหาการหาค่าที่เหมาะสมที่สุดทั้งแบบต่อเนื่องและแบบผสม โดยมีการปรับเปลี่ยนน้อยที่สุด
การประยุกต์ใช้
- การจัดตารางเวลาแบบ job-shop และ flow-shop แบบหลายวัตถุประสงค์ (ลด makespan และ tardiness พร้อมกัน)
- ปัญหาการออกแบบเครือข่ายและเส้นทางที่มีวัตถุประสงค์ด้านต้นทุนและความน่าเชื่อถือ
- การหาค่าที่เหมาะสมที่สุดในการออกแบบทางวิศวกรรม (เช่น การลดน้ำหนักและความเค้นในส่วนประกอบโครงสร้าง)
- การหาค่าที่เหมาะสมที่สุดของพอร์ตโฟลิโอโดยการสร้างสมดุลระหว่างผลตอบแทนที่คาดหวังและความเสี่ยง
- การวางแผนการใช้ที่ดินและเชิงพื้นที่โดยมีวัตถุประสงค์ทางเศรษฐกิจและสิ่งแวดล้อมที่แข่งขันกัน
- การจัดสรรทรัพยากรด้านการดูแลสุขภาพโดยการสร้างสมดุลระหว่างต้นทุน ความครอบคลุม และคุณภาพการบริการ
วิธีการทำงาน
วิธีการทำงาน
สร้างคำตอบเริ่มต้น (แบบสุ่มหรือแบบฮิวริสติก) ตั้งอุณหภูมิเริ่มต้น T_0 ให้สูงเพียงพอสำหรับการสำรวจในวงกว้าง เริ่มต้นคลัง Pareto ด้วยคำตอบที่ไม่ถูกครอบงำที่พบ และกำหนดเกณฑ์การหยุด (จำนวนการวนซ้ำสูงสุดหรือเกณฑ์อุณหภูมิต่ำสุด)
รบกวนคำตอบปัจจุบันโดยใช้ตัวดำเนินการเพื่อนบ้านที่เหมาะสมกับโครงสร้างปัญหา (เช่น การสลับ การแทรก หรือการรบกวนแบบ Gaussian สำหรับตัวแปรต่อเนื่อง) เพื่อสร้างคำตอบเพื่อนบ้านตัวเลือกหนึ่งรายการหรือมากกว่า
ประเมินฟังก์ชันวัตถุประสงค์ทั้งหมดสำหรับคำตอบตัวเลือก (candidate) กำหนดว่าคำตอบนั้นครอบงำ ถูกครอบงำ หรือไม่ถูกครอบงำเมื่อเทียบกับคำตอบปัจจุบันและคำตอบในคลัง Pareto คำตอบที่ไม่ถูกครอบงำจะถูกเพิ่มเข้าไปในคลัง สมาชิกในคลังที่ถูกครอบงำจะถูกลบออก
ใช้เกณฑ์การยอมรับวัตถุประสงค์หลายอย่าง หากคำตอบเพื่อนบ้านไม่ถูกครอบงำเมื่อเทียบกับคำตอบปัจจุบัน จะได้รับการยอมรับ หากถูกครอบงำ ก็ยังสามารถยอมรับได้ด้วยความน่าจะเป็น P = exp(−ΔF / T) โดยที่ ΔF รวบรวมการเสื่อมสภาพของวัตถุประสงค์ ทำให้สามารถหลีกหนีจากขอบเขต Pareto เฉพาะที่ได้
สูตร
P(\text{accept}) = \exp\!\left(-\frac{\Delta f}{T}\right)ลดอุณหภูมิตามกำหนดการเย็นตัว โดยทั่วไปจะเป็นแบบเรขาคณิต: T_{k+1} = α · T_k โดยที่ α ∈ (0.8, 0.99) อุณหภูมิที่ต่ำลงจะจำกัดการยอมรับการเคลื่อนไหวที่ด้อยกว่า ทำให้การค้นหาใกล้กับบริเวณที่มีแนวโน้มของขอบเขต Pareto เข้มข้นขึ้นเรื่อย ๆ
สูตร
T_{k+1} = \alpha \cdot T_k, \quad \alpha \in (0,1)ส่งคืนคลัง Pareto สุดท้ายเป็นผลลัพธ์ ประมวลผลภายหลังเพื่อกำจัดคำตอบที่ถูกครอบงำซึ่งอาจสะสมอยู่ และนำเสนอคลังเป็นค่าประมาณแบบไม่ต่อเนื่องของขอบเขต Pareto-optimal สำหรับการเลือกของผู้ตัดสินใจ
ข้อผิดพลาดที่พบบ่อย
- การตั้งค่าอุณหภูมิเริ่มต้นต่ำเกินไปจะทำให้ลู่เข้าสู่บริเวณเฉพาะของขอบเขต Pareto ก่อนเวลาอันควร ควรปรับเทียบ T_0 เสมอเพื่อให้แน่ใจว่าอัตราการยอมรับเริ่มต้นอยู่ที่ประมาณ 70–90%
- การใช้อัตราการเย็นตัว α ที่ใกล้กับ 1.0 มากเกินไปจะทำให้การทำงานใช้เวลานานเกินไป การใช้อัตราที่ใกล้กับ 0 มากเกินไปจะทำให้ลู่เข้าอย่างรวดเร็วก่อนที่ขอบเขต Pareto จะได้รับการสำรวจอย่างเพียงพอ
- การกำหนด ΔF สำหรับความน่าจะเป็นในการยอมรับด้วยผลรวมของความแตกต่างของวัตถุประสงค์แบบง่าย ๆ จะผสมสเกลที่ไม่สามารถเปรียบเทียบกันได้ ควรปรับวัตถุประสงค์แต่ละรายการให้เป็นมาตรฐานก่อนการรวม
- การละเลยการลบคำตอบที่ถูกครอบงำออกจากคลังเป็นระยะ ๆ จะทำให้คลังขยายใหญ่ขึ้นและลดคุณภาพของผลลัพธ์สุดท้าย
- การประเมินความสำเร็จในการทำงานเดียวอาจทำให้เข้าใจผิดได้เนื่องจากความแปรปรวนแบบสุ่ม ควรทำการรวมผลลัพธ์จากการทำงานอิสระหลายครั้งเสมอ
คำถามที่พบบ่อย
MOSA แตกต่างจาก NSGA-II อย่างไร?
NSGA-II เป็นอัลกอริทึมเชิงวิวัฒนาการแบบประชากรที่พัฒนาชุดของคำตอบพร้อมกันโดยใช้การผสมข้าม การกลายพันธุ์ และการจัดอันดับแบบไม่ถูกครอบงำ ในขณะที่ MOSA เป็นวิธีการแบบเส้นทางที่สำรวจคำตอบทีละคำตอบโดยใช้การเคลื่อนไหวแบบสุ่ม MOSA มักจะง่ายต่อการนำไปใช้และทำงานได้ดีกับปัญหาแบบผสม ในขณะที่ NSGA-II โดยทั่วไปให้การครอบคลุมขอบเขต Pareto ที่ดีกว่าสำหรับปัญหาแบบต่อเนื่องและปรับขนาดได้คาดการณ์ได้มากกว่า
ฉันควรกำหนดอุณหภูมิเริ่มต้น T_0 อย่างไร?
หลักการทั่วไปคือการดำเนินการระยะเริ่มต้นสั้น ๆ และเลือก T_0 เพื่อให้ประมาณ 80% ของการเคลื่อนไหวแบบเพื่อนบ้านแบบสุ่มได้รับการยอมรับ สิ่งนี้ทำให้มั่นใจได้ถึงการสำรวจในวงกว้างในตอนเริ่มต้น ขอแนะนำให้ปรับเทียบเฉพาะสำหรับปัญหา เนื่องจากมาตราส่วนอุณหภูมิที่เหมาะสมขึ้นอยู่กับขนาดของความแตกต่างของฟังก์ชันวัตถุประสงค์
MOSA สามารถจัดการกับวัตถุประสงค์มากกว่าสองวัตถุประสงค์ได้หรือไม่?
ได้ แต่ประสิทธิภาพจะลดลงเมื่อจำนวนวัตถุประสงค์เพิ่มขึ้น ต้นทุนการจัดการคลัง Pareto จะเพิ่มขึ้น และสัดส่วนของคำตอบที่ไม่ถูกครอบงำจะเพิ่มขึ้นอย่างรวดเร็ว ทำให้เกณฑ์การยอมรับมีความแตกต่างน้อยลง สำหรับปัญหาที่มีวัตถุประสงค์มากกว่าสี่หรือห้าวัตถุประสงค์ โดยทั่วไปจะนิยมใช้วิธีการที่ใช้ตัวบ่งชี้ hypervolume หรือวิธีการที่ใช้การแยกส่วน (เช่น MOEA/D) มากกว่า
ฉันจะรู้ได้อย่างไรว่าเมื่อใดควรหยุดอัลกอริทึม?
เกณฑ์การหยุดทั่วไป ได้แก่ การถึงอุณหภูมิต่ำสุด การใช้โควตาการวนซ้ำสูงสุดหมด หรือการสังเกตว่าไม่มีการปรับปรุงในตัวบ่งชี้ hypervolume ของคลัง Pareto ในช่วงจำนวนการวนซ้ำที่กำหนด ในทางปฏิบัติ การเปรียบเทียบคลังคุณภาพจากการทำงานหลายครั้งด้วยโควตาการวนซ้ำที่แตกต่างกันเป็นวิธีที่เชื่อถือได้ในการวินิจฉัยการลู่เข้า
MOSA เหมาะสมกับแบบจำลองการจำลองที่มีค่าใช้จ่ายสูงหรือไม่?
โดยทั่วไปแล้ว ไม่ได้หากไม่มีการปรับเปลี่ยน แต่ละรอบการทำงานต้องการการประเมินฟังก์ชันวัตถุประสงค์อย่างน้อยหนึ่งครั้ง และ MOSA โดยทั่วไปต้องการการวนซ้ำหลายพันครั้งเพื่อให้ได้ค่าประมาณขอบเขต Pareto ที่ดี เมื่อการประเมินแต่ละครั้งเกี่ยวข้องกับการจำลองที่มีค่าใช้จ่ายสูง เวอร์ชันของ MOSA ที่ใช้ตัวช่วย (surrogate-assisted) (โดยใช้ metamodels เพื่อประมาณวัตถุประสงค์) จะเป็นที่นิยมมากกว่า
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Czyzak, P., Jaszkiewicz, A. (1998). Pareto simulated annealing — a metaheuristic technique for multiple-objective combinatorial optimization. Journal of Multi-Criteria Decision Analysis, 7(1), 34–47.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วSerafini, P. (1992). Simulated annealing for multi-objective optimization problems. In Proceedings of the Tenth International Conference on Multiple Criteria Decision Making, Taipei, Taiwan, pp. 87–96.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้ว