Multi-objective optimization — การเพิ่มประสิทธิภาพหลายวัตถุประสงค์

การปรับให้เหมาะสมแบบหลายเกณฑ์ (หรือ การโปรแกรมแบบหลายเกณฑ์ อังกฤษ: multi-objective optimization, multi-criteria optimization) — คือสาขาหนึ่งของการปรับให้เหมาะสมทางคณิตศาสตร์ที่ศึกษาปัญหาการปรับให้เหมาะสมพร้อมกันตามฟังก์ชันวัตถุประสงค์ (เกณฑ์) ตั้งแต่สองฟังก์ชันขึ้นไป ซึ่งโดยทั่วไปมักขัดแย้งกัน ในรูปแบบทางการ ปัญหาดังกล่าวเขียนในรูปการหาค่าต่ำสุดของฟังก์ชันวัตถุประสงค์เชิงเวกเตอร์บนเซตของคำตอบที่เป็นไปได้

นิยามและศัพท์บัญญัติ

ปัญหาการปรับให้เหมาะสมแบบหลายเกณฑ์ในรูปแบบทั่วไปเขียนได้ดังนี้: $\underset{x\in S}{min}\{f_1(x),f_2(x),\dots ,f_k(x)\}$ โดยที่ $S\subseteq {ℝ}^n$ คือเซตของคำตอบที่เป็นไปได้ซึ่งไม่ว่างเปล่า และ $f_i:S\to ℝ$ คือฟังก์ชันวัตถุประสงค์ ($k\ge 2$) เวกเตอร์ $f(x)=(f_1(x),\dots ,f_k(x))$ เรียกว่าเวกเตอร์วัตถุประสงค์

ต่างจากการปรับให้เหมาะสมแบบสเกลาร์ ในการกำหนดปัญหาแบบหลายเกณฑ์มักไม่มีคำตอบเดียวที่ปรับปรุงค่าของเกณฑ์ทั้งหมดพร้อมกันได้ ดังนั้นแนวคิดคลาสสิกของค่าเหมาะที่สุดจึงถูกขยายโดยใช้แนวคิดความเหมาะสมตามแบบพาเรโต

• คำตอบพาเรโต (คำตอบที่เหมาะสมตามพาเรโตหรือคำตอบที่มีประสิทธิภาพ): คำตอบที่เป็นไปได้ $x^{\ast }\in S$ ซึ่งไม่มีคำตอบอื่น $x\in S$ ที่ทำให้ $f_i(x)\le f_i(x^{\ast })$ สำหรับทุก $i=1,\dots ,k$ และ $f_j(x)<f_j(x^{\ast })$ สำหรับดัชนีอย่างน้อยหนึ่งตัว $j$ กล่าวอีกนัยหนึ่ง คำตอบจะเหมาะสมตามพาเรโตหากไม่สามารถปรับปรุงค่าของเกณฑ์ใดๆ ได้โดยไม่ทำให้เกณฑ์อื่นอย่างน้อยหนึ่งเกณฑ์แย่ลง
• แนวรบพาเรโต (หรือเซตพาเรโต): เซตของเวกเตอร์วัตถุประสงค์ทั้งหมดที่สอดคล้องกับคำตอบที่เหมาะสมตามพาเรโต
• คำตอบที่เหมาะสมตามพาเรโตแบบอ่อน: คำตอบ $x^{\ast }\in S$ ซึ่งไม่มีคำตอบอื่น $x\in S$ ที่ทำให้ $f_i(x)<f_i(x^{\ast })$ สำหรับทุก $i$

คุณสมบัติสำคัญและทฤษฎีบท

• ทฤษฎีบทผลรวมถ่วงน้ำหนัก: ในปัญหาแบบนูน (ที่ฟังก์ชัน $f_i(x)$ ทั้งหมดและเซต $S$ มีความนูน) คำตอบที่เหมาะสมตามพาเรโตใดๆ $x^{\ast }$ คือคำตอบของปัญหาสเกลาร์การหาค่าต่ำสุดของผลรวมถ่วงน้ำหนักของเกณฑ์ $\underset{x\in S}{min}\sum _{i=1}^k{w}_i{f}_i(x)$ สำหรับชุดน้ำหนักที่ไม่เป็นลบบางชุด $w_i\ge 0$ อย่างไรก็ตาม ในปัญหาที่ไม่นูน วิธีนี้อาจไม่สามารถค้นหาบางส่วนของแนวรบพาเรโตได้

• เงื่อนไขความเหมาะสมของ Karush–Kuhn–Tucker (KKT): เงื่อนไขที่จำเป็นสำหรับความเหมาะสมของปัญหาที่มีความเรียบถูกขยายสู่กรณีหลายเกณฑ์ ที่จุดที่เหมาะสมตามพาเรโตจะมีชุดตัวคูณ (น้ำหนัก) ที่ไม่เป็นลบซึ่งไม่เป็นศูนย์ โดยที่ gradient ของฟังก์ชันวัตถุประสงค์และข้อจำกัดที่ใช้งานอยู่มีความสัมพันธ์เชิงเส้นตรง

• คุณสมบัติของเซตคำตอบ: แนวรบพาเรโตมีลักษณะเชิงคุณภาพที่สำคัญหลายประการ ขอบเขตของมันถูกกำหนดโดย จุดอุดมคติ (ประกอบจากค่าต่ำสุดของแต่ละเกณฑ์) และ จุดนาดีร์ (ประกอบจากค่าสูงสุดของแต่ละเกณฑ์บนแนวรบ)

ตัวอย่าง

• ปัญหาเชิงเส้น: หาค่าต่ำสุดของ $f_1(x)=-x_1$ และ $f_2(x)=-x_2$ ภายใต้ข้อจำกัด $x_1+x_2\le 1$, $x_1,x_2\ge 0$ ที่นี่การปรับปรุงเกณฑ์หนึ่ง (เช่น การเพิ่ม $x_1$) ย่อมนำไปสู่การทำให้เกณฑ์อื่นแย่ลงอย่างหลีกเลี่ยงไม่ได้ (การลดลงของ $x_2$) เซตของคำตอบที่เหมาะสมตามพาเรโตคือส่วนของเส้นตรง $x_1+x_2=1$
• ปัญหาที่ไม่นูน: หาค่าต่ำสุดของ $f_1(x)=x^2$ และ $f_2(x)=(x-2{)}^2$ บนช่วง $[0,2]$ แนวรบพาเรโตมีลักษณะไม่นูน วิธีผลรวมถ่วงน้ำหนักที่มีน้ำหนักบวกไม่สามารถค้นหาคำตอบภายในช่วงนี้ได้ (เช่น ที่จุด $x=1$) เนื่องจากการรวมเชิงเส้นของเกณฑ์จะบรรลุค่าต่ำสุดเฉพาะที่จุดปลาย $x=0$ หรือ $x=2$ เท่านั้น

แนวคิดที่เกี่ยวข้องและการประยุกต์ใช้

การปรับให้เหมาะสมแบบหลายเกณฑ์มีความสัมพันธ์ใกล้ชิดกับการตัดสินใจแบบหลายเกณฑ์ (MCDM) ซึ่งศึกษาการเลือกทางเลือกที่ดีที่สุดโดยคำนึงถึงความต้องการของผู้ตัดสินใจ วิธีหลักในการแปลงปัญหาหลายเกณฑ์ให้เป็นสเกลาร์ (การทำสเกลาไรเซชัน) ได้แก่:

• วิธีผลรวมถ่วงน้ำหนัก
• วิธีข้อจำกัด $\epsilon$: ปรับให้เหมาะสมเกณฑ์หนึ่งในขณะที่แปลงเกณฑ์อื่นเป็นข้อจำกัดในรูปแบบ $f_i(x)\le {\epsilon }_i$ วิธีนี้สามารถค้นหาคำตอบบนส่วนที่ไม่นูนของแนวรบได้

การปรับให้เหมาะสมแบบหลายเกณฑ์มีการประยุกต์ใช้อย่างกว้างขวางในการออกแบบทางวิศวกรรม เศรษฐศาสตร์ (เช่น การปรับพอร์ตโฟลิโอให้เหมาะสม) การบริหารจัดการ และนิเวศวิทยา

ดูเพิ่มเติม

• ความเหมาะสมตามพาเรโต
• การปรับให้เหมาะสมเชิงเวกเตอร์
• ทฤษฎีการตัดสินใจ
• ระบบสนับสนุนการตัดสินใจ
• การวิจัยเชิงปฏิบัติการ