Skip to content
กลับไปยังผลการค้นหา

การอบอ่อนจำลองแบบหลายวัตถุประสงค์ (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 พร้อมกัน)
  • ปัญหาการออกแบบเครือข่ายและเส้นทางที่มีวัตถุประสงค์ด้านต้นทุนและความน่าเชื่อถือ
  • การหาค่าที่เหมาะสมที่สุดในการออกแบบทางวิศวกรรม (เช่น การลดน้ำหนักและความเค้นในส่วนประกอบโครงสร้าง)
  • การหาค่าที่เหมาะสมที่สุดของพอร์ตโฟลิโอโดยการสร้างสมดุลระหว่างผลตอบแทนที่คาดหวังและความเสี่ยง
  • การวางแผนการใช้ที่ดินและเชิงพื้นที่โดยมีวัตถุประสงค์ทางเศรษฐกิจและสิ่งแวดล้อมที่แข่งขันกัน
  • การจัดสรรทรัพยากรด้านการดูแลสุขภาพโดยการสร้างสมดุลระหว่างต้นทุน ความครอบคลุม และคุณภาพการบริการ

วิธีการทำงาน

วิธีการทำงาน

1

สร้างคำตอบเริ่มต้น (แบบสุ่มหรือแบบฮิวริสติก) ตั้งอุณหภูมิเริ่มต้น T_0 ให้สูงเพียงพอสำหรับการสำรวจในวงกว้าง เริ่มต้นคลัง Pareto ด้วยคำตอบที่ไม่ถูกครอบงำที่พบ และกำหนดเกณฑ์การหยุด (จำนวนการวนซ้ำสูงสุดหรือเกณฑ์อุณหภูมิต่ำสุด)

2

รบกวนคำตอบปัจจุบันโดยใช้ตัวดำเนินการเพื่อนบ้านที่เหมาะสมกับโครงสร้างปัญหา (เช่น การสลับ การแทรก หรือการรบกวนแบบ Gaussian สำหรับตัวแปรต่อเนื่อง) เพื่อสร้างคำตอบเพื่อนบ้านตัวเลือกหนึ่งรายการหรือมากกว่า

3

ประเมินฟังก์ชันวัตถุประสงค์ทั้งหมดสำหรับคำตอบตัวเลือก (candidate) กำหนดว่าคำตอบนั้นครอบงำ ถูกครอบงำ หรือไม่ถูกครอบงำเมื่อเทียบกับคำตอบปัจจุบันและคำตอบในคลัง Pareto คำตอบที่ไม่ถูกครอบงำจะถูกเพิ่มเข้าไปในคลัง สมาชิกในคลังที่ถูกครอบงำจะถูกลบออก

4

ใช้เกณฑ์การยอมรับวัตถุประสงค์หลายอย่าง หากคำตอบเพื่อนบ้านไม่ถูกครอบงำเมื่อเทียบกับคำตอบปัจจุบัน จะได้รับการยอมรับ หากถูกครอบงำ ก็ยังสามารถยอมรับได้ด้วยความน่าจะเป็น P = exp(−ΔF / T) โดยที่ ΔF รวบรวมการเสื่อมสภาพของวัตถุประสงค์ ทำให้สามารถหลีกหนีจากขอบเขต Pareto เฉพาะที่ได้

สูตร
P(\text{accept}) = \exp\!\left(-\frac{\Delta f}{T}\right)
5

ลดอุณหภูมิตามกำหนดการเย็นตัว โดยทั่วไปจะเป็นแบบเรขาคณิต: T_{k+1} = α · T_k โดยที่ α ∈ (0.8, 0.99) อุณหภูมิที่ต่ำลงจะจำกัดการยอมรับการเคลื่อนไหวที่ด้อยกว่า ทำให้การค้นหาใกล้กับบริเวณที่มีแนวโน้มของขอบเขต Pareto เข้มข้นขึ้นเรื่อย ๆ

สูตร
T_{k+1} = \alpha \cdot T_k, \quad \alpha \in (0,1)
6

ส่งคืนคลัง 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 เพื่อประมาณวัตถุประสงค์) จะเป็นที่นิยมมากกว่า

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. 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
    คัดลอกแล้ว
  2. 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.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว