การหาค่าเหมาะที่สุดหลายวัตถุประสงค์เชิงสุ่ม — การหาค่าเหมาะที่สุดสำหรับหลายวัตถุประสงค์ที่ขัดแย้งกันภายใต้ความไม่แน่นอน
- ผู้เสนอ
- Various (Fonseca, Fleming, Deb, Zitzler, and others)
- ปี
- 1990s–2000s
- ประเภท
- Stochastic metaheuristic optimization
- กลุ่มวิธี
- Simulation / optimization
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
การหาค่าเหมาะที่สุดหลายวัตถุประสงค์เชิงสุ่ม (Stochastic Multi-Objective Optimization หรือ SMOO) เป็นกลุ่มของวิธีการที่ใช้ในการหาค่าเหมาะที่สุดสำหรับวัตถุประสงค์ที่ขัดแย้งกันตั้งแต่สองอย่างขึ้นไปพร้อมกัน เมื่อพารามิเตอร์ ต้นทุน หรือข้อจำกัดมีความไม่แน่นอนหรือเป็นแบบสุ่ม แทนที่จะได้ผลลัพธ์ที่เหมาะสมที่สุดเพียงหนึ่งเดียว วิธีการนี้จะสร้างแนว Pareto ของผลลัพธ์ที่ไม่ถูกครอบงำ (non-dominated solutions) ซึ่งแต่ละผลลัพธ์แสดงถึงความสมดุลที่แตกต่างกันระหว่างวัตถุประสงค์ภายใต้แบบจำลองความไม่แน่นอน
แนวคิดเบื้องหลังวิธีการ
การตัดสินใจส่วนใหญ่ในโลกแห่งความเป็นจริงเกี่ยวข้องกับการแลกเปลี่ยนระหว่างเป้าหมายหลายประการ เช่น การลดต้นทุนในขณะที่เพิ่มคุณภาพและความเร็ว และโลกก็เต็มไปด้วยความไม่แน่นอน SMOO ตระหนักดีว่าค่าฟังก์ชันวัตถุประสงค์ไม่ใช่ตัวเลขที่ตายตัว แต่เป็นตัวแปรสุ่มที่ได้รับอิทธิพลจากปัจจัยนำเข้าที่ไม่แน่นอน เช่น อุปสงค์ ราคา หรืออัตราความล้มเหลว ด้วยการสุ่มตัวอย่างหรือการแพร่กระจายความไม่แน่นอนนั้นผ่านการประเมินวัตถุประสงค์หลายครั้ง วิธีการนี้จะค้นหาชุดของผลลัพธ์การแลกเปลี่ยนที่แข็งแกร่ง (robust trade-off solutions) ซึ่งยังคงไม่ถูกครอบงำภายใต้สถานการณ์ความไม่แน่นอนที่เป็นจริง ทำให้ผู้ตัดสินใจมีทางเลือกที่แท้จริง แทนที่จะเป็นคำตอบเดียวที่แม่นยำอย่างผิดพลาด
ประวัติศาสตร์
การหาค่าเหมาะที่สุดหลายวัตถุประสงค์ภายใต้ความไม่แน่นอนเกิดขึ้นในช่วงทศวรรษ 1990 พร้อมกับการเพิ่มขึ้นของการหาค่าเหมาะที่สุดหลายวัตถุประสงค์เชิงวิวัฒนาการ ผลงานสำคัญของ Fonseca และ Fleming (1993) และ Deb et al. (2002) ได้วางรากฐานกรอบการทำงานเชิงวิวัฒนาการที่อิงตาม Pareto การรวมองค์ประกอบเชิงสุ่ม — ผ่านวัตถุประสงค์ค่าคาดหวัง ข้อจำกัดโอกาส และวิธีการที่อิงตามสถานการณ์จำลอง — กลายเป็นพื้นที่วิจัยที่กระตือรือร้นตลอดช่วงทศวรรษ 2000 และ 2010 โดยได้รับการสนับสนุนจากพลังการคำนวณที่เพิ่มขึ้นซึ่งช่วยให้สามารถค้นหาที่ต้องใช้ Monte Carlo จำนวนมากได้
ควรใช้เมื่อใด
ใช้ Stochastic MOO เมื่อมีวัตถุประสงค์ที่ขัดแย้งกันอย่างแท้จริงตั้งแต่สองอย่างขึ้นไป และพารามิเตอร์หลัก (อุปสงค์ ต้นทุน ระยะเวลา ความน่าจะเป็นของความล้มเหลว) มีความไม่แน่นอนหรือผันแปร เหมาะสำหรับการออกแบบทางวิศวกรรมภายใต้ความไม่แน่นอน การวางแผนห่วงโซ่อุปทาน การหาค่าเหมาะที่สุดของพอร์ตการลงทุนด้านพลังงาน และการประเมินนโยบายที่มีเกณฑ์สวัสดิการหลายประการ ห้ามใช้เมื่อพารามิเตอร์ทั้งหมดเป็นแบบกำหนด (ใช้ MOO มาตรฐานแทน) เมื่อมีวัตถุประสงค์เดียวเท่านั้นที่สำคัญ (ใช้การหาค่าเหมาะที่สุดเชิงสุ่มแบบวัตถุประสงค์เดียว) เมื่อความไม่แน่นอนเป็นแบบญาณวิทยาและไม่สามารถหาปริมาณได้ หรือเมื่องบประมาณการคำนวณมีจำกัดเกินไปที่จะรองรับการประเมินฟังก์ชันเชิงสุ่มซ้ำๆ — ผลลัพธ์ที่เป็นไปได้แต่ละรายการอาจต้องใช้การสุ่มตัวอย่างแบบ Monte Carlo หลายสิบถึงหลายพันครั้ง
ข้อจำกัดและข้อควรพิจารณา
- มีค่าใช้จ่ายในการคำนวณสูง: การประเมินฟังก์ชันแต่ละครั้งต้องใช้การสุ่มตัวอย่างแบบ Monte Carlo หรือการแจกแจงสถานการณ์จำลอง ซึ่งคูณด้วยการประเมินจำนวนมากที่จำเป็นสำหรับการค้นหาหลายวัตถุประสงค์
- ผลลัพธ์ขึ้นอยู่กับคุณภาพของแบบจำลองความไม่แน่นอนอย่างมาก; ข้อสมมติฐานการแจกแจงที่ไม่ดีนำไปสู่แนว Pareto ที่ทำให้เข้าใจผิด
- การบรรจบกันสู่แนว Pareto เชิงสุ่มที่แท้จริงทำได้ยากกว่าในกรณีเชิงกำหนด; ความเชื่อมั่นในผลลัพธ์ต้องอาศัยการวิเคราะห์ทางสถิติอย่างรอบคอบ
- จำนวนผลลัพธ์ Pareto ที่มากเกินไปอาจทำให้ผู้ตัดสินใจสับสนได้หากไม่มีเครื่องมือการแสดงภาพหรือการแสดงความชอบที่มีประสิทธิภาพ
- ต้องมีข้อมูลเพียงพอหรือความรู้ในโดเมนเพื่อระบุการแจกแจงความไม่แน่นอนสำหรับพารามิเตอร์ที่ไม่แน่นอนแต่ละตัว
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- คำนึงถึงความไม่แน่นอนในค่าวัตถุประสงค์อย่างชัดเจน ทำให้ได้ผลลัพธ์ที่แข็งแกร่งต่อความผันแปรของพารามิเตอร์ แทนที่จะเป็นค่าเหมาะที่สุดภายใต้ค่าคงที่ที่สมมติขึ้นเท่านั้น
- สร้างแนว Pareto ของผลลัพธ์การแลกเปลี่ยนที่สมบูรณ์ ทำให้ผู้ตัดสินใจมีอิสระในการเลือกทางเลือกตามความชอบ
- เข้ากันได้กับการแสดงความไม่แน่นอนที่หลากหลาย (การแจกแจง สถานการณ์จำลอง ชุดความคลุมเครือ) และกลไกการหาค่าเหมาะที่สุด (อัลกอริทึมเชิงวิวัฒนาการ การแยกส่วน วิธีการช่วยโดยตัวแทน)
- จับความสัมพันธ์การครอบงำเชิงสุ่มระหว่างผลลัพธ์ที่ MOO เชิงกำหนดจะพลาดไป
- สามารถนำไปใช้ได้ในหลากหลายสาขา รวมถึงวิศวกรรมศาสตร์ โลจิสติกส์ การเงิน และนโยบายสาธารณะ
การประยุกต์ใช้
- การออกแบบทางวิศวกรรม: การหาค่าเหมาะที่สุดของน้ำหนักโครงสร้าง ต้นทุน และความน่าเชื่อถือพร้อมกันเมื่อคุณสมบัติของวัสดุมีความไม่แน่นอน
- การจัดการห่วงโซ่อุปทาน: การสร้างสมดุลระหว่างต้นทุน ระดับการบริการ และการปล่อยคาร์บอนภายใต้อุปสงค์และระยะเวลารอคอยที่ไม่แน่นอน
- ระบบพลังงาน: การวางแผนพอร์ตการลงทุนการผลิตที่ลดต้นทุนและการปล่อยมลพิษในขณะที่บรรลุเป้าหมายความน่าเชื่อถือภายใต้ผลผลิตพลังงานหมุนเวียนที่ผันแปร
- การหาค่าเหมาะที่สุดของพอร์ตการลงทุนทางการเงิน: การเพิ่มผลตอบแทนที่คาดหวังในขณะที่ลดความเสี่ยง (CVaR) ภายใต้ผลตอบแทนสินทรัพย์ที่ไม่แน่นอน
- การออกแบบเครือข่ายการขนส่ง: การลดเวลาเดินทางและต้นทุนโครงสร้างพื้นฐานภายใต้อุปสงค์การจราจรในอนาคตที่ไม่แน่นอน
- การจัดสรรทรัพยากรด้านการดูแลสุขภาพ: การสร้างสมดุลระหว่างผลลัพธ์การรักษาและงบประมาณภายใต้อัตราการมาถึงของผู้ป่วยและประสิทธิภาพการรักษาที่ไม่แน่นอน
วิธีการทำงาน
วิธีการทำงาน
กำหนดเวกเตอร์ของฟังก์ชันวัตถุประสงค์ f(x) = [f1(x,xi), f2(x,xi), ..., fk(x,xi)] โดยที่ x คือเวกเตอร์ตัวแปรตัดสินใจ และ xi แทนพารามิเตอร์ที่ไม่แน่นอน ระบุขอบเขตของตัวแปรตัดสินใจ ข้อจำกัดเชิงกำหนดและเชิงสุ่ม และโครงสร้างความไม่แน่นอน (การแจกแจง สถานการณ์จำลอง หรือชุดความคลุมเครือ)
แสดงพารามิเตอร์ที่ไม่แน่นอนผ่านการแจกแจงความน่าจะเป็น (เช่น Normal, Uniform, empirical) ชุดสถานการณ์จำลองแบบไม่ต่อเนื่องพร้อมความน่าจะเป็นที่เกี่ยวข้อง หรือชุดความคลุมเครือที่แข็งแกร่ง เลือกการแสดงผลที่ตรงกับข้อมูลที่มีอยู่: วิธีการที่อิงตามสถานการณ์จำลองต้องการข้อสมมติฐานการแจกแจงน้อยกว่า; แบบจำลองการแจกแจงเต็มรูปแบบช่วยให้สามารถสุ่มตัวอย่างแบบ Monte Carlo ได้
ใช้อัลกอริทึมการค้นหาหลายวัตถุประสงค์ ซึ่งโดยทั่วไปคืออัลกอริทึมเชิงวิวัฒนาการ เช่น NSGA-II, MOEA/D หรือ SPEA2 หรือการแยกส่วนการโปรแกรมเชิงคณิตศาสตร์ เพื่อสำรวจพื้นที่การตัดสินใจและรักษากลุ่มประชากรหรือคลังข้อมูลของผลลัพธ์ที่ไม่ถูกครอบงำที่เป็นไปได้ตลอดการวนซ้ำ
สำหรับแต่ละผลลัพธ์ที่เป็นไปได้ x ที่พบระหว่างการค้นหา ให้ประเมินวัตถุประสงค์เชิงสุ่มโดยการคำนวณค่าคาดหวัง E[fi(x,xi)], ค่าความแปรปรวน, ค่าความเสี่ยงแบบมีเงื่อนไข (CVaR) หรือค่าเฉลี่ยตามสถานการณ์จำลองผ่านการสุ่มตัวอย่างแบบ Monte Carlo หรือการอินทิเกรตเชิงวิเคราะห์ ซึ่งจะแทนที่การประเมินฟังก์ชันเชิงกำหนดด้วยการประมาณค่าความเหมาะสมที่แข็งแกร่งทางสถิติ
อัปเดตและตัดแต่งคลังข้อมูลที่ไม่ถูกครอบงำโดยใช้ความสัมพันธ์การครอบงำของ Pareto ที่นำไปใช้กับค่าวัตถุประสงค์เชิงสุ่มที่ประมาณไว้ ผลลัพธ์ x ครอบงำ x' หากเวกเตอร์วัตถุประสงค์ที่ประมาณไว้ไม่แย่กว่าในทุกมิติและดีกว่าอย่างเคร่งครัดในอย่างน้อยหนึ่งมิติ โดยคำนึงถึงความไม่แน่นอนของการประมาณค่าหากจำเป็น
นำเสนอแนว Pareto เชิงสุ่มที่ประมาณไว้แก่ผู้ตัดสินใจ พร้อมด้วยช่วงความเชื่อมั่นหรือการแจกแจงความน่าจะเป็นเหนือวัตถุประสงค์สำหรับแต่ละผลลัพธ์ Pareto ช่วยให้สามารถเลือกผลลัพธ์ที่ต้องการได้โดยใช้การปรับค่าฟังก์ชันให้เป็นสเกลาร์ วิธีการจุดอ้างอิง หรือการวิเคราะห์การแลกเปลี่ยนแบบโต้ตอบ
ข้อผิดพลาดที่พบบ่อย
- การใช้ตัวอย่าง Monte Carlo น้อยเกินไปต่อการประเมินทำให้เกิดการประมาณค่าความเหมาะสมที่มีสัญญาณรบกวน ซึ่งบิดเบือนการเปรียบเทียบการครอบงำของ Pareto และทำให้การค้นหาเข้าใจผิด
- การถือว่าวัตถุประสงค์ที่ไม่แน่นอนเป็นแบบกำหนดโดยการเสียบค่าพารามิเตอร์เฉลี่ยเข้าไปละเลยความแปรปรวนและอาจให้ผลลัพธ์ที่ทำงานได้ไม่ดีภายใต้สถานการณ์จริง
- การรวมการหาค่าเหมาะที่สุดที่แข็งแกร่ง (กรณีที่เลวร้ายที่สุด) เข้ากับการหาค่าเหมาะที่สุดเชิงสุ่ม (ค่าคาดหวัง): การกำหนดสูตรทั้งสองแบบให้แนว Pareto ที่แตกต่างกันและเหมาะกับทัศนคติความเสี่ยงที่แตกต่างกัน
- การละเลยความไม่แน่นอนของข้อจำกัด: การไม่สร้างแบบจำลองข้อจำกัดเชิงสุ่มเป็นข้อจำกัดโอกาสหรือข้อจำกัดค่าคาดหวังนำไปสู่ผลลัพธ์ที่ไม่สามารถทำได้ในทางปฏิบัติ
- การรายงานแนว Pareto โดยไม่มีช่วงความเชื่อมั่นทำให้ผู้มีส่วนได้ส่วนเสียเข้าใจผิดว่าการประมาณค่าวัตถุประสงค์มีความแม่นยำ
คำถามที่พบบ่อย
Stochastic MOO แตกต่างจากการหาค่าเหมาะที่สุดหลายวัตถุประสงค์ (เชิงกำหนด) มาตรฐานอย่างไร?
ใน MOO เชิงกำหนด ค่าฟังก์ชันวัตถุประสงค์จะคงที่สำหรับเวกเตอร์การตัดสินใจที่กำหนด ใน Stochastic MOO วัตถุประสงค์เป็นตัวแปรสุ่มเนื่องจากพารามิเตอร์บางตัวมีความไม่แน่นอน ผลลัพธ์ที่เป็นไปได้แต่ละรายการจะต้องได้รับการประเมินโดยการประมาณประสิทธิภาพที่คาดหวัง (หรือมาตรวัดความเสี่ยง) ในสถานการณ์ความไม่แน่นอน ซึ่งโดยทั่วไปทำได้โดยการสุ่มตัวอย่างแบบ Monte Carlo ทำให้การหาค่าเหมาะที่สุดมีความต้องการการคำนวณสูงขึ้นอย่างมาก
ต้องใช้ตัวอย่าง Monte Carlo กี่ตัวอย่างต่อการประเมินผลลัพธ์หนึ่งครั้ง?
ไม่มีกฎสากล; ขึ้นอยู่กับความแปรปรวนของวัตถุประสงค์และความแม่นยำของการประมาณค่าที่ต้องการ จุดเริ่มต้นทั่วไปคือ 100–1000 ตัวอย่างต่อการประเมิน แต่ผู้ปฏิบัติงานควรทำการศึกษาเบื้องต้นเพื่อประเมินว่าต้องใช้ตัวอย่างจำนวนเท่าใดจึงจะให้การประมาณค่าความเหมาะสมที่เสถียรและการจัดอันดับ Pareto ที่เสถียร
ฉันสามารถใช้อัลกอริทึมหลายวัตถุประสงค์ใดก็ได้เป็นกลไกการค้นหาหรือไม่?
ได้ NSGA-II, MOEA/D, SPEA2 และอัลกอริทึมที่อิงตาม Pareto หรือการแยกส่วนอื่นๆ สามารถปรับเปลี่ยนได้โดยการแทนที่การประเมินฟังก์ชันเชิงกำหนดด้วยการประเมินเชิงสุ่ม ตัวแปรที่ช่วยโดยตัวแทนได้รับความนิยมมากขึ้นเพื่อลดจำนวนการประเมินเชิงสุ่มที่มีค่าใช้จ่ายสูง
ฉันควรใช้มาตรวัดความเสี่ยงใดสำหรับวัตถุประสงค์เชิงสุ่ม?
ขึ้นอยู่กับบริบทการตัดสินใจ ค่าคาดหวังเหมาะสมสำหรับผู้มีส่วนได้ส่วนเสียที่ไม่คำนึงถึงความเสี่ยง; ความแปรปรวนหรือส่วนเบี่ยงเบนมาตรฐานจะลงโทษความผันแปร; CVaR (Conditional Value-at-Risk) จะจับความเสี่ยงส่วนท้ายสำหรับการตั้งค่าที่หลีกเลี่ยงความเสี่ยง สำหรับความน่าเชื่อถือทางวิศวกรรม ความน่าจะเป็นของการปฏิบัติตามข้อจำกัด (ข้อจำกัดโอกาส) มักจะมีความหมายมากกว่าค่าคาดหวัง
การหาค่าเหมาะที่สุดที่แข็งแกร่งเหมือนกับการหาค่าเหมาะที่สุดหลายวัตถุประสงค์เชิงสุ่มหรือไม่?
ไม่ การหาค่าเหมาะที่สุดที่แข็งแกร่งมักใช้แบบจำลองความไม่แน่นอนกรณีที่เลวร้ายที่สุด (การกำหนดสูตร min-max) โดยไม่จำเป็นต้องมีการแจกแจงความน่าจะเป็น Stochastic MOO ใช้แบบจำลองความน่าจะเป็นและหาค่าเหมาะที่สุดของค่าวัตถุประสงค์ที่คาดหวังหรือปรับความเสี่ยง ทั้งสองจัดการกับความไม่แน่นอน แต่เข้ารหัสทัศนคติความเสี่ยงที่แตกต่างกันและต้องการข้อมูลความไม่แน่นอนประเภทที่แตกต่างกัน
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Deb, K. (2001). Multi-Objective Optimization Using Evolutionary Algorithms. Wiley, Chichester.
ISBN: 9780471873396คัดลอกแล้วCaramia, M., Dell'Olmo, P. (2008). Multi-Objective Management in Freight Logistics. Springer, London.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว