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

การหาค่าเหมาะสมที่สุดแบบหลายวัตถุประสงค์ — การหาค่าเหมาะสมที่สุดของเป้าหมายที่ขัดแย้งกันไปพร้อมกัน

ผู้เสนอ
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)

การประยุกต์ใช้

  • การออกแบบโครงสร้างและเครื่องกล (หาค่าต่ำสุดของน้ำหนักและหาค่าสูงสุดของความแข็งแกร่งพร้อมกัน)
  • ห่วงโซ่อุปทานและโลจิสติกส์ (หาค่าต่ำสุดของต้นทุน ระยะเวลารอคอย และการปล่อยก๊าซคาร์บอน)
  • การจัดสรรพอร์ตในภาคการเงิน (หาค่าสูงสุดของผลตอบแทน หาค่าต่ำสุดของความเสี่ยงและการลดลง)
  • นโยบายสิ่งแวดล้อมและพลังงาน (หาค่าต่ำสุดของต้นทุนและการปล่อยก๊าซเรือนกระจกสำหรับส่วนผสมพลังงาน)
  • การค้นพบยาและการออกแบบกระบวนการทางเคมี (หาค่าเหมาะสมที่สุดของประสิทธิภาพ ความเป็นพิษ และต้นทุนการสังเคราะห์)
  • การปรับแต่งไฮเปอร์พารามิเตอร์ในแมชชีนเลิร์นนิง (ความแม่นยำ เทียบกับ ความซับซ้อนของโมเดล เทียบกับ ความเร็วในการอนุมาน)

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

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

1

กำหนดเวกเตอร์ตัวแปรตัดสินใจ 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
2

สร้างความสัมพันธ์ของการครอบงำ (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)
3

ใช้อัลกอริทึมการค้นหาเพื่อประมาณค่า Pareto set แนวทางที่ใช้กันทั่วไป ได้แก่ อัลกอริทึมเชิงวิวัฒนาการ (evolutionary algorithms) เช่น NSGA-II, MOEA/D, SPEA2 การแปลงเป็นสเกลาร์ด้วยผลรวมถ่วงน้ำหนัก (weighted-sum scalarization) ที่ทำงานซ้ำๆ ด้วยน้ำหนักที่แตกต่างกัน วิธี epsilon-constraint (หาค่าเหมาะสมที่สุดของวัตถุประสงค์หนึ่งขณะจำกัดค่าของวัตถุประสงค์อื่น) และ metaheuristics เช่น multi-objective particle swarm หรือ simulated annealing การเลือกอัลกอริทึมขึ้นอยู่กับขนาดของปัญหา ความนูน (convexity) และความต่อเนื่อง

4

รวบรวมและกรองคำตอบที่ไม่ถูกครอบงำที่พบระหว่างการค้นหาเพื่อสร้าง Pareto front ที่ประมาณค่าได้ ตัวชี้วัดคุณภาพ เช่น hypervolume indicator, generational distance และ spread จะวัดว่าการประมาณค่าครอบคลุมและกระจายตัวบน front ที่แท้จริงได้ดีเพียงใด ค่า hypervolume ที่สูงขึ้นและ generational distance ที่ต่ำลงบ่งชี้ถึงการประมาณค่าที่ดีขึ้น

5

นำเสนอ 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) การเลือกแนวทางส่งผลกระทบต่อการลู่เข้าอย่างมีนัยสำคัญ โดยเฉพาะอย่างยิ่งเมื่อบริเวณที่เป็นไปได้มีขนาดเล็ก

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

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

  1. Deb, K. (2001). Multi-Objective Optimization Using Evolutionary Algorithms. Wiley, Chichester.

    ISBN: 9780471873396
    คัดลอกแล้ว
  2. Multi-objective optimization. Wikipedia.

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