การหาค่าเหมาะสมที่สุดแบบหลายวัตถุประสงค์ — การหาค่าเหมาะสมที่สุดของเป้าหมายที่ขัดแย้งกันไปพร้อมกัน
- ผู้เสนอ
- Vilfredo Pareto (concept); modern computational formulation by Goldberg and Deb et al.
- ปี
- 1896 (concept); 1989–2002 (evolutionary algorithms era)
- ประเภท
- Optimization framework
- กลุ่มวิธี
- Simulation / optimization
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
การหาค่าเหมาะสมที่สุดแบบหลายวัตถุประสงค์ (Multi-Objective Optimization - MOO) เป็นกรอบการทำงานทางคณิตศาสตร์และคอมพิวเตอร์สำหรับการค้นหาคำตอบที่สามารถหาค่าเหมาะสมที่สุดของฟังก์ชันวัตถุประสงค์ที่ขัดแย้งกันตั้งแต่สองฟังก์ชันขึ้นไปได้พร้อมกัน แทนที่จะรวมเป้าหมายทั้งหมดเข้าเป็นค่าสเกลาร์เดียว MOO จะสร้างชุดของคำตอบที่ยอมรับได้ (trade-off solutions) ซึ่งก็คือ Pareto front ซึ่งผู้มีอำนาจตัดสินใจจะเลือกตามความพึงพอใจ วิธีนี้ถูกนำไปใช้อย่างกว้างขวางในการออกแบบทางวิศวกรรม วิจัยดำเนินงาน โลจิสติกส์ เศรษฐศาสตร์ และการวิเคราะห์นโยบาย
แนวคิดเบื้องหลังวิธีการ
ในการตัดสินใจในโลกแห่งความเป็นจริงส่วนใหญ่ การปรับปรุงเป้าหมายหนึ่งมักจะส่งผลเสียต่ออีกเป้าหมายหนึ่ง เช่น การทำให้ผลิตภัณฑ์มีราคาถูกลงมักจะลดทอนคุณภาพ และการลดระยะเวลาในการจัดส่งมักจะเพิ่มต้นทุน การหาค่าเหมาะสมที่สุดแบบหลายวัตถุประสงค์จะจับความตึงเครียดนี้อย่างชัดเจน แทนที่จะซ่อนไว้ภายใต้น้ำหนักที่กำหนดขึ้นเอง วิธีนี้จะแสดงขอบเขตทั้งหมดของค่าที่ยอมรับได้ (Pareto front) ซึ่งทำให้ผู้มีอำนาจตัดสินใจมีตัวเลือกของคำตอบที่ไม่ถูกครอบงำ (non-dominated solutions) ไม่มีคำตอบใดที่ดีที่สุดอย่างเป็นกลาง ความเหมาะสมที่สุดหมายความว่าคุณไม่สามารถปรับปรุงวัตถุประสงค์หนึ่งได้โดยไม่ทำให้วัตถุประสงค์อื่นอย่างน้อยหนึ่งอย่างแย่ลง สิ่งนี้เปลี่ยนบทบาทของอัลกอริทึมจากการกำหนดคำตอบไปสู่การแสดงพื้นที่ของค่าที่ยอมรับได้ โดยสงวนการตัดสินคุณค่าไว้สำหรับผู้มีอำนาจตัดสินใจที่เป็นมนุษย์
ประวัติศาสตร์
Vilfredo Pareto ได้นำเสนอแนวคิดเรื่องค่าที่ยอมรับได้ที่ไม่ถูกครอบงำในวิชาเศรษฐศาสตร์ในปี 1896 การหาค่าเหมาะสมที่สุดแบบหลายวัตถุประสงค์อย่างเป็นทางการเกิดขึ้นในงานวิจัยดำเนินงานในช่วงทศวรรษ 1950–1960 (Kuhn, Tucker; Charnes, Cooper) สาขานี้ได้รับการเปลี่ยนแปลงในช่วงทศวรรษ 1980–1990 โดยแนวทางเชิงวิวัฒนาการ: Goldberg (1989) ได้ร่าง vector-evaluated genetic algorithms และ Deb et al. (2002) ได้นำเสนอ NSGA-II ซึ่งกลายเป็นอัลกอริทึมมาตรฐานที่แพร่หลายและกระตุ้นการเติบโตอย่างรวดเร็วในการประยุกต์ใช้ในสาขาวิศวกรรมและวิทยาศาสตร์
ควรใช้เมื่อใด
ใช้การหาค่าเหมาะสมที่สุดแบบหลายวัตถุประสงค์เมื่อมีวัตถุประสงค์เชิงปริมาณตั้งแต่สองประการขึ้นไปที่ไม่สามารถหาค่าสูงสุดได้พร้อมกันทั้งหมด และเมื่อความโปร่งใสของค่าที่ยอมรับได้มีความสำคัญ (เช่น การออกแบบทางวิศวกรรม ห่วงโซ่อุปทาน การจัดสรรพอร์ต การกำหนดนโยบายสิ่งแวดล้อม) วิธีนี้เหมาะสมอย่างยิ่งเมื่อผู้มีส่วนได้ส่วนเสียไม่เห็นด้วยเรื่องน้ำหนัก หรือเมื่อการเปิดเผยโครงสร้างของค่าที่ยอมรับได้นั้นมีคุณค่าในตัวเอง ไม่ควรใช้เมื่อวัตถุประสงค์สามารถรวมเข้าเป็นมาตรวัดเดียวที่รวมกันได้โดยไม่สูญเสียข้อมูล เมื่อปริภูมิการตัดสินใจมีขนาดใหญ่เกินกว่างบประมาณการคำนวณที่มีอยู่โดยไม่มีอัลกอริทึมการประมาณค่าที่ดี หรือเมื่อผู้มีอำนาจตัดสินใจต้องการคำตอบอัตโนมัติเพียงคำตอบเดียวโดยไม่มีพื้นที่สำหรับการแสดงความพึงพอใจหลังการวิเคราะห์
ข้อจำกัดและข้อควรพิจารณา
- ต้นทุนการคำนวณเพิ่มขึ้นอย่างรวดเร็วตามจำนวนวัตถุประสงค์ (การหาค่าเหมาะสมที่สุดแบบหลายวัตถุประสงค์จำนวนมาก หรือ many-objective optimization โดยที่ k >= 4 นั้นยากกว่าอย่างมาก)
- Pareto front ที่ประมาณค่าได้จาก metaheuristics ไม่ได้รับประกันว่าจะเหมาะสมที่สุด คุณภาพขึ้นอยู่กับการปรับแต่งอัลกอริทึมและงบประมาณ
- การเลือกหลังการวิเคราะห์จาก Pareto front ยังคงต้องการการสอบถามความพึงพอใจ — วิธีการนี้เลื่อนออกไป แทนที่จะกำจัดความจำเป็นในการตัดสินคุณค่า
- การจัดการข้อจำกัดเพิ่มความซับซ้อนและอาจทำให้ Pareto front ที่เป็นไปได้หดตัวอย่างคาดเดาไม่ได้
- การตีความและสื่อสาร Pareto front ที่มีมิติสูงให้กับผู้มีส่วนได้ส่วนเสียที่ไม่ใช่ผู้เชี่ยวชาญนั้นเป็นเรื่องท้าทาย
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- เปิดเผยโครงสร้างค่าที่ยอมรับได้ทั้งหมด แทนที่จะซ่อนไว้ในน้ำหนักที่กำหนดไว้ล่วงหน้า ช่วยให้การตัดสินใจมีข้อมูลรอบด้าน
- สร้างคำตอบที่ไม่ถูกครอบงำหลายคำตอบในการทำงานครั้งเดียว (โดยเฉพาะอย่างยิ่งกับอัลกอริทึมเชิงวิวัฒนาการ) ช่วยลดความจำเป็นในการทำงานซ้ำสำหรับแต่ละชุดน้ำหนัก
- ไม่ขึ้นกับกรอบการทำงาน: สามารถนำไปใช้กับปัญหาแบบต่อเนื่อง ไม่ต่อเนื่อง แบบผสมจำนวนเต็ม และแบบผสมผสาน
- ปรับขนาดได้ตามธรรมชาติสำหรับวัตถุประสงค์ตั้งแต่สามประการขึ้นไป แม้ว่าการแสดงภาพจะยากขึ้นเมื่อมีมากกว่าสองประการ
- ได้รับการสนับสนุนอย่างกว้างขวางจากไลบรารีซอฟต์แวร์ที่มีอยู่ (DEAP, pymoo, jMetal, MATLAB Global Optimization Toolbox)
การประยุกต์ใช้
- การออกแบบโครงสร้างและเครื่องกล (หาค่าต่ำสุดของน้ำหนักและหาค่าสูงสุดของความแข็งแกร่งพร้อมกัน)
- ห่วงโซ่อุปทานและโลจิสติกส์ (หาค่าต่ำสุดของต้นทุน ระยะเวลารอคอย และการปล่อยก๊าซคาร์บอน)
- การจัดสรรพอร์ตในภาคการเงิน (หาค่าสูงสุดของผลตอบแทน หาค่าต่ำสุดของความเสี่ยงและการลดลง)
- นโยบายสิ่งแวดล้อมและพลังงาน (หาค่าต่ำสุดของต้นทุนและการปล่อยก๊าซเรือนกระจกสำหรับส่วนผสมพลังงาน)
- การค้นพบยาและการออกแบบกระบวนการทางเคมี (หาค่าเหมาะสมที่สุดของประสิทธิภาพ ความเป็นพิษ และต้นทุนการสังเคราะห์)
- การปรับแต่งไฮเปอร์พารามิเตอร์ในแมชชีนเลิร์นนิง (ความแม่นยำ เทียบกับ ความซับซ้อนของโมเดล เทียบกับ ความเร็วในการอนุมาน)
วิธีการทำงาน
วิธีการทำงาน
กำหนดเวกเตอร์ตัวแปรตัดสินใจ x ภายในเซตที่เป็นไปได้ X และระบุฟังก์ชันวัตถุประสงค์ k ฟังก์ชัน f_1(x), ..., f_k(x) ที่ต้องการหาค่าต่ำสุด (หรือสูงสุด) นอกจากนี้ ให้ระบุข้อจำกัดที่เป็นสมการหรืออสมการ g(x) <= 0, h(x) = 0 การกำหนดรูปแบบนี้จะทำให้วัตถุประสงค์ทั้งหมดปรากฏชัดเจน แทนที่จะรวมเข้าด้วยกันล่วงหน้า
สูตร
\min_{x \in \mathcal{X}} \mathbf{f}(x) = [f_1(x), f_2(x), \ldots, f_k(x)]^Tสร้างความสัมพันธ์ของการครอบงำ (dominance relation): คำตอบ x* จะครอบงำ x หาก x* ดีอย่างน้อยเท่ากับ x ในทุกวัตถุประสงค์ และดีกว่าอย่างน้อยหนึ่งวัตถุประสงค์ คำตอบจะถือว่าเหมาะสมที่สุดแบบพาเรโต (Pareto-optimal) หรือไม่ถูกครอบงำ (non-dominated) หากไม่มีคำตอบอื่นที่เป็นไปได้ครอบงำมัน เซตของคำตอบที่เหมาะสมที่สุดแบบพาเรโตทั้งหมดคือ Pareto set ภาพของมันในปริภูมิวัตถุประสงค์คือ Pareto front
สูตร
x^* \text{ dominates } x \iff f_i(x^*) \leq f_i(x) \; \forall i, \; \exists j: f_j(x^*) < f_j(x)ใช้อัลกอริทึมการค้นหาเพื่อประมาณค่า Pareto set แนวทางที่ใช้กันทั่วไป ได้แก่ อัลกอริทึมเชิงวิวัฒนาการ (evolutionary algorithms) เช่น NSGA-II, MOEA/D, SPEA2 การแปลงเป็นสเกลาร์ด้วยผลรวมถ่วงน้ำหนัก (weighted-sum scalarization) ที่ทำงานซ้ำๆ ด้วยน้ำหนักที่แตกต่างกัน วิธี epsilon-constraint (หาค่าเหมาะสมที่สุดของวัตถุประสงค์หนึ่งขณะจำกัดค่าของวัตถุประสงค์อื่น) และ metaheuristics เช่น multi-objective particle swarm หรือ simulated annealing การเลือกอัลกอริทึมขึ้นอยู่กับขนาดของปัญหา ความนูน (convexity) และความต่อเนื่อง
รวบรวมและกรองคำตอบที่ไม่ถูกครอบงำที่พบระหว่างการค้นหาเพื่อสร้าง Pareto front ที่ประมาณค่าได้ ตัวชี้วัดคุณภาพ เช่น hypervolume indicator, generational distance และ spread จะวัดว่าการประมาณค่าครอบคลุมและกระจายตัวบน front ที่แท้จริงได้ดีเพียงใด ค่า hypervolume ที่สูงขึ้นและ generational distance ที่ต่ำลงบ่งชี้ถึงการประมาณค่าที่ดีขึ้น
นำเสนอ Pareto front ให้กับผู้มีอำนาจตัดสินใจเพื่อการเลือกขั้นสุดท้าย เครื่องมือต่างๆ ได้แก่ การแสดงภาพแบบโต้ตอบ (scatter plots, parallel coordinate plots) การถ่วงน้ำหนักหลังการวิเคราะห์ (post-hoc weighting) การใช้ TOPSIS กับคำตอบของ Pareto หรือวิธีการอ้างอิงจุด (reference-point methods) เช่น NIMBUS, NAUTILUS คำตอบที่เลือกจะสะท้อนถึงลำดับความสำคัญของผู้มีส่วนได้ส่วนเสีย แทนที่จะเป็นค่าเริ่มต้นของอัลกอริทึม
ข้อผิดพลาดที่พบบ่อย
- การปฏิบัติต่อ Pareto front ในฐานะคำตอบสุดท้ายโดยไม่มีการสอบถามความพึงพอใจของผู้มีส่วนได้ส่วนเสีย — front เป็นข้อมูลป้อนเข้าสำหรับการตัดสินใจ ไม่ใช่การตัดสินใจเอง
- การใช้วิธี weighted-sum scalarization กับปัญหาที่ไม่เป็น convex: ไม่สามารถสร้างคำตอบในส่วน concave ของ Pareto front ได้
- การละเลยตัวชี้วัดความหลากหลายของคำตอบ — อัลกอริทึมอาจลู่เข้าสู่บริเวณเล็กๆ ของ front ทำให้เกิดความเข้าใจผิดว่าครอบคลุมทั้งหมด
- การสับสนระหว่างการหาค่าเหมาะสมที่สุดแบบหลายวัตถุประสงค์กับการตัดสินใจด้วยเกณฑ์หลายประการ (Multi-Criteria Decision Making - MCDM): MOO ค้นหาคำตอบที่เหมาะสมที่สุดแบบพาเรโต ในขณะที่ MCDM จัดอันดับชุดทางเลือกที่มีจำนวนจำกัด — ทั้งสองมีความเสริมกัน ไม่ใช่สิ่งเดียวกัน
- การละเลยงบประมาณการคำนวณ: การรันจำนวนรุ่นไม่เพียงพอใน MOO เชิงวิวัฒนาการจะสร้างการประมาณค่า Pareto ที่ไม่ดี ซึ่งนำไปสู่การตัดสินใจที่ผิดพลาด
คำถามที่พบบ่อย
อะไรคือความแตกต่างระหว่างการหาค่าเหมาะสมที่สุดแบบหลายวัตถุประสงค์ (Multi-Objective Optimization) และการตัดสินใจด้วยเกณฑ์หลายประการ (Multi-Criteria Decision Making - MCDM)?
MOO ค้นหาปริภูมิการตัดสินใจ (ที่อาจมีจำนวนไม่สิ้นสุด) เพื่อสร้างชุดของคำตอบที่เหมาะสมที่สุดแบบพาเรโต ในขณะที่ MCDM ประเมินและจัดอันดับชุดทางเลือกที่มีจำนวนจำกัดที่กำหนดไว้ล่วงหน้า ในทางปฏิบัติ ทั้งสองมักจะถูกรวมเข้าด้วยกัน: MOO สร้าง Pareto front และวิธีการ MCDM (เช่น TOPSIS, VIKOR) จะช่วยในการเลือกจาก front นั้น
การหาค่าเหมาะสมที่สุดแบบหลายวัตถุประสงค์สามารถจัดการกับวัตถุประสงค์ได้กี่ประการ?
วัตถุประสงค์สองหรือสามประการสามารถจัดการได้ด้วยอัลกอริทึมส่วนใหญ่และช่วยให้สามารถแสดงภาพได้โดยตรง สำหรับวัตถุประสงค์สี่ประการขึ้นไป (many-objective optimization) แรงกดดันจากการครอบงำแบบพาเรโตจะอ่อนแอลง คำตอบส่วนใหญ่จะกลายเป็นไม่ถูกครอบงำ และจำเป็นต้องใช้อัลกอริทึมพิเศษ (NSGA-III, MOEA/D) และเทคนิคการลดมิติ
ตัวชี้วัด hypervolume คืออะไร และทำไมจึงสำคัญ?
ตัวชี้วัด hypervolume วัดปริมาตรของปริภูมิวัตถุประสงค์ที่ถูกครอบงำโดยการประมาณค่า Pareto front เมื่อเทียบกับจุดอ้างอิง เป็นตัวชี้วัดคุณภาพแบบเอกภาค (unary quality indicator) ที่ใช้กันอย่างแพร่หลายที่สุด เนื่องจากให้รางวัลทั้งการลู่เข้าสู่ front ที่แท้จริงและความหลากหลายของคำตอบตามแนวหน้า
การเลือก NSGA-II เป็นตัวเลือกที่ดีที่สุดสำหรับการหาค่าเหมาะสมที่สุดแบบหลายวัตถุประสงค์เสมอไปหรือไม่?
NSGA-II เป็นอัลกอริทึมที่ถูกอ้างอิงมากที่สุดและเป็นเกณฑ์มาตรฐานที่แข็งแกร่งสำหรับปัญหาแบบสองและสามวัตถุประสงค์ที่มีตัวแปรต่อเนื่อง สำหรับปัญหาแบบหลายวัตถุประสงค์จำนวนมาก (k >= 4) โดยทั่วไปแล้ว NSGA-III หรือ MOEA/D จะเหมาะสมกว่า สำหรับปัญหาแบบผสมผสานหรือแบบผสมจำนวนเต็ม จำเป็นต้องใช้ออปเรเตอร์เฉพาะสำหรับปัญหานั้นๆ โดยไม่คำนึงถึงอัลกอริทึมพื้นฐาน
การหาค่าเหมาะสมที่สุดแบบหลายวัตถุประสงค์สามารถจัดการกับข้อจำกัดได้หรือไม่?
ได้ แนวทางการจัดการข้อจำกัดที่ใช้กันทั่วไป ได้แก่ ฟังก์ชันการลงโทษ (penalty functions) กฎความเข้ากันได้ (feasibility rules) (เช่น การจัดการข้อจำกัดของ Deb ใน NSGA-II) วิธี epsilon-constraint (ซึ่งเปลี่ยนข้อจำกัดให้เป็นขอบเขตของวัตถุประสงค์รอง) และออปเรเตอร์การแก้ไข (repair operators) การเลือกแนวทางส่งผลกระทบต่อการลู่เข้าอย่างมีนัยสำคัญ โดยเฉพาะอย่างยิ่งเมื่อบริเวณที่เป็นไปได้มีขนาดเล็ก
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Deb, K. (2001). Multi-Objective Optimization Using Evolutionary Algorithms. Wiley, Chichester.
ISBN: 9780471873396คัดลอกแล้วMulti-objective optimization. Wikipedia.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้ว