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

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

ผู้เสนอ
Deb, K. & Gupta, H.
ปี
2006
ประเภท
Optimization framework
กลุ่มวิธี
Simulation / optimization

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

การหาค่าเหมาะสมที่สุดแบบหลายวัตถุประสงค์ที่ทนทาน (Robust Multi-Objective Optimization - RMOO) เป็นกรอบการทำงานสำหรับการค้นหาคำตอบที่ปรับวัตถุประสงค์ที่ขัดแย้งกันหลายประการให้เหมาะสมที่สุดไปพร้อมๆ กัน โดยยังคงไม่ไวต่อการรบกวนในตัวแปรตัดสินใจหรือพารามิเตอร์ของปัญหา ซึ่งแตกต่างจาก MOO แบบดั้งเดิม RMOO ได้รวมความไม่แน่นอนเข้าสู่กระบวนการหาค่าเหมาะสมที่สุดอย่างชัดเจน โดยสร้างชุดคำตอบพาเรโตที่ทนทาน ซึ่งสมาชิกแต่ละตัวทำงานได้ดีไม่เพียงแค่ที่จุดออกแบบตามชื่อเท่านั้น แต่ยังรวมถึงบริเวณใกล้เคียงของสภาวะการทำงานที่เป็นไปได้ด้วย

แนวคิดเบื้องหลังวิธีการ

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

ประวัติศาสตร์

การหาค่าเหมาะสมที่สุดแบบทนทานมีต้นกำเนิดมาจาก Soyster (1973) และได้รับการพัฒนาอย่างเข้มงวดโดย Ben-Tal และ Nemirovski ในช่วงปลายทศวรรษ 1990 สำหรับโปรแกรมคอนเวกซ์วัตถุประสงค์เดียว การขยายไปยังหลายวัตถุประสงค์ได้รับแรงผลักดันจากบทความ Evolutionary Computation ของ Deb และ Gupta ในปี 2006 ซึ่งได้นำเสนอแนวคิด robust dominance และสาธิต RMOO ผ่าน NSGA-II variants ตั้งแต่นั้นมา สาขานี้ได้เติบโตขึ้นอย่างมาก โดยได้รวมการวิเคราะห์ความไวตามความแปรปรวน สูตร minimax และชุดความไม่แน่นอนที่ขับเคลื่อนด้วยข้อมูล

ควรใช้เมื่อใด

ใช้ RMOO เมื่อ: (1) ปัญหามีวัตถุประสงค์ที่ขัดแย้งกันตั้งแต่สองประการขึ้นไปที่ไม่สามารถรวมเป็นเกณฑ์เดียวได้ (2) ข้อมูลนำเข้า พารามิเตอร์ หรือสภาวะการทำงานมีความไม่แน่นอนหรือแปรปรวน และ (3) คำตอบที่ดูเหมาะสมที่สุดภายใต้สภาวะตามชื่ออาจเปราะบางจนยอมรับไม่ได้ในทางปฏิบัติ เหมาะสำหรับ การออกแบบทางวิศวกรรม, ห่วงโซ่อุปทาน, การหาค่าเหมาะสมของพอร์ตโฟลิโอ, และนโยบายสิ่งแวดล้อม **ห้าม** ใช้ RMOO เมื่อวัตถุประสงค์สามารถรวมเป็นเกณฑ์เดียวได้โดยไม่สูญเสียข้อมูลที่มีความหมาย (ใช้การหาค่าเหมาะสมแบบทนทานเชิงสเกลาร์แทน) เมื่อความไม่แน่นอนน้อยมากหรือสามารถควบคุมได้อย่างสมบูรณ์ เมื่อชุดที่ทำได้มีขนาดเล็กมากและสามารถแจงนับได้ง่ายกว่า หรือเมื่องบประมาณการคำนวณไม่เพียงพอสำหรับการประเมินวัตถุประสงค์ซ้ำๆ ต่อผู้สมัครแต่ละราย

ข้อจำกัดและข้อควรพิจารณา

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

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • ค้นหาคำตอบที่เหมาะสมแบบพาเรโตและไม่ไวต่อความไม่แน่นอน ซึ่งช่วยเพิ่มความน่าเชื่อถือในโลกแห่งความเป็นจริง
  • สร้างแบบจำลองการแลกเปลี่ยนระหว่างประสิทธิภาพและความทนทานอย่างชัดเจน ทำให้ผู้มีอำนาจตัดสินใจได้รับข้อมูลที่สมบูรณ์ยิ่งขึ้น
  • เข้ากันได้กับอัลกอริทึมหลายวัตถุประสงค์พื้นฐานส่วนใหญ่ (NSGA-II, MOEA/D, SPEA2) ด้วยการปรับเปลี่ยนเล็กน้อย
  • จัดการได้ทั้งความไม่แน่นอนเชิงญาณ (epistemic uncertainty - ชุดที่มีขอบเขต) และความไม่แน่นอนเชิงสุ่ม (aleatory uncertainty - การแจกแจงความน่าจะเป็น)
  • สร้างชุดคำตอบพาเรโตที่หลากหลาย ช่วยให้สามารถแสดงความพึงพอใจได้อย่างมีข้อมูลหลังจากการหาค่าเหมาะสม

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

  • การออกแบบโครงสร้างอากาศยาน: การลดน้ำหนักและความเค้นภายใต้ความคลาดเคลื่อนในการผลิตและความแปรปรวนของภาระ
  • การออกแบบเครือข่ายห่วงโซ่อุปทาน: การสร้างสมดุลระหว่างต้นทุนและระดับการบริการภายใต้ความไม่แน่นอนของอุปสงค์และระยะเวลารอคอย
  • การวางแผนระบบพลังงาน: การหาค่าเหมาะสมที่สุดของกำลังการผลิตพลังงานหมุนเวียนและความน่าเชื่อถือภายใต้ความผันผวนของสภาพอากาศและความต้องการ
  • นโยบายสิ่งแวดล้อม: การแลกเปลี่ยนระหว่างต้นทุนทางเศรษฐกิจและผลกระทบทางนิเวศวิทยาภายใต้แบบจำลองการปล่อยมลพิษที่ไม่แน่นอน
  • การจัดการพอร์ตการลงทุนทางการเงิน: การเพิ่มผลตอบแทนและลดความเสี่ยงภายใต้ความไม่แน่นอนของสถานการณ์ตลาด
  • การหาค่าเหมาะสมที่สุดของกระบวนการผลิตยา: การสร้างสมดุลระหว่างผลผลิตและความบริสุทธิ์ภายใต้ความแปรปรวนของวัตถุดิบและสภาวะปฏิกิริยา

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

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

1

กำหนดฟังก์ชันวัตถุประสงค์ m ฟังก์ชัน f_1(x), ..., f_m(x) ที่จะลดค่า (หรือเพิ่มค่า) ให้เหมาะสมที่สุดไปพร้อมๆ กัน ภายใต้ข้อจำกัด g(x) <= 0 ระบุว่าพารามิเตอร์ใด x หรือปัจจัยแวดล้อมที่ไม่แน่นอน และระบุชุดความไม่แน่นอนหรือการแจกแจงของพารามิเตอร์เหล่านั้น

2

แทนที่ความไม่แน่นอนด้วยชุดการรบกวนที่มีขอบเขต (ความทนทานแบบกรณีที่เลวร้ายที่สุด / minimax robustness) หรือด้วยการแจกแจงความน่าจะเป็นเหนือพารามิเตอร์ที่ไม่แน่นอน (ความทนทานตามค่าคาดหวัง หรือตามความแปรปรวน) ตัวเลือกทั่วไป ได้แก่ ความไม่แน่นอนแบบกล่อง (box uncertainty) ความไม่แน่นอนแบบวงรี (ellipsoidal uncertainty) หรือการแจกแจงที่สุ่มตัวอย่างแบบ Monte Carlo

3

กำหนดมาตรวัดความทนทานสำหรับวัตถุประสงค์แต่ละรายการ ตัวชี้วัดทั่วไป ได้แก่ ค่าเฉลี่ย E[f_i(x, xi)] และความแปรปรวน Var[f_i(x, xi)] ภายใต้ความไม่แน่นอน xi หรือค่ากรณีที่เลวร้ายที่สุด max_{xi in U} f_i(x, xi) ตัวชี้วัดเหล่านี้จะเสริมหรือแทนที่ค่าวัตถุประสงค์ตามชื่อในการทดสอบการครอบงำแบบพาเรโต (Pareto dominance test)

4

ใช้อัลกอริทึมวิวัฒนาการแบบหลายวัตถุประสงค์ (โดยทั่วไปคือ NSGA-II หรือ MOEA/D) ซึ่งการประเมินค่าความเหมาะสม (fitness evaluation) แต่ละครั้งจะคำนวณมาตรวัดความทนทาน — เช่น โดยการหาค่าเฉลี่ยจากการสุ่มตัวอย่างการรบกวน หรือการแก้ปัญหาย่อยกรณีที่เลวร้ายที่สุด แรงกดดันในการคัดเลือกจะขึ้นอยู่กับการครอบงำแบบทนทาน (robust dominance): คำตอบ A ครอบงำแบบทนทาน B ถ้า A ดีอย่างน้อยเท่ากับ B ในมาตรวัดวัตถุประสงค์แบบทนทานทั้งหมด และดีกว่าอย่างน้อยหนึ่งรายการ

5

หลังจากการลู่เข้า (convergence) ให้รวบรวมชุดคำตอบพาเรโตที่ทนทาน — ซึ่งเป็นชุดของคำตอบที่ไม่ถูกครอบงำแบบทนทาน วิเคราะห์พื้นผิวการแลกเปลี่ยน (trade-off surface): คำตอบที่อยู่ใกล้จุดสุดขั้วจะเพิ่มวัตถุประสงค์แบบทนทานเพียงอย่างเดียวให้สูงสุด คำตอบที่อยู่ตรงกลางจะสร้างสมดุลระหว่างวัตถุประสงค์หลายประการกับความแปรปรวนปานกลางภายใต้ความไม่แน่นอน

6

นำเสนอชุดคำตอบพาเรโตที่ทนทานแก่ผู้มีอำนาจตัดสินใจ พร้อมกับโปรไฟล์ความทนทาน (เช่น แผนภาพไวโอลินของการแจกแจงวัตถุประสงค์) ใช้วิธีการแสดงความพึงพอใจหลังการหาค่าเหมาะสม (post-hoc preference articulation) (ผลรวมถ่วงน้ำหนัก, TOPSIS บนค่าเฉลี่ยและความแปรปรวน) หรือการเลือกแบบโต้ตอบเพื่อระบุคำตอบที่ต้องการสุดท้าย

ข้อผิดพลาดที่พบบ่อย

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

คำถามที่พบบ่อย

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

MOO มาตรฐานค้นหาคำตอบที่เหมาะสมแบบพาเรโตที่ค่าพารามิเตอร์ตามชื่อที่กำหนด RMOO กำหนดเพิ่มเติมว่าคำตอบยังคงดีเมื่อพารามิเตอร์เบี่ยงเบนไปจากค่าตามชื่อ โดยการฝังการประเมินความไม่แน่นอนไว้ในการประเมินการครอบงำและค่าความเหมาะสม

ฉันควรเลือกมาตรวัดความทนทานแบบใด: กรณีที่เลวร้ายที่สุด หรือ ค่าคาดหวัง

กรณีที่เลวร้ายที่สุด (minimax) เหมาะสมเมื่อความล้มเหลวภายใต้สถานการณ์ใดๆ เป็นสิ่งที่ยอมรับไม่ได้ (ระบบที่สำคัญต่อความปลอดภัย) ตัวชี้วัดค่าคาดหวังหรือค่าเฉลี่ย-ความแปรปรวน เหมาะสำหรับสถานการณ์ที่การเบี่ยงเบนเป็นครั้งคราวสามารถยอมรับได้ และการอนุรักษ์นิยมเกินไปจะมีค่าใช้จ่ายสูง การเลือกควรขึ้นอยู่กับระดับความเสี่ยงของสาขานั้นๆ

RMOO สามารถรวมเข้ากับอัลกอริทึมวิวัฒนาการหลายวัตถุประสงค์ใดๆ ได้หรือไม่

ได้ RMOO เป็นกรอบการทำงาน ไม่ใช่อัลกอริทึมที่ตายตัว การประเมินความทนทานจะแทนที่หรือเสริมการประเมินวัตถุประสงค์ตามชื่อภายใน MOEA ใดๆ NSGA-II เป็นที่นิยมใช้มากที่สุด แต่ MOEA/D, SPEA2 และอื่นๆ ก็ทำงานได้เช่นกัน โดยมีการปรับเปลี่ยนฟังก์ชันค่าความเหมาะสมให้เหมาะสม

ต้องใช้ตัวอย่างความไม่แน่นอนกี่ตัวอย่างต่อผู้สมัครแต่ละราย

แนวปฏิบัติทั่วไปใช้ตัวอย่าง 30–200 ตัวอย่างสำหรับการประมาณค่าคาดหวัง และมากกว่านั้นสำหรับการประมาณค่าความแปรปรวน ลำดับ Quasi-Monte Carlo หรือการสุ่มตัวอย่างแบบ Latin hypercube ช่วยลดจำนวนที่ต้องการ แผนการสุ่มตัวอย่างแบบปรับได้ที่ใช้ตัวอย่างน้อยในช่วงต้นของการค้นหาและมากขึ้นเมื่อใกล้จะลู่เข้าก็เป็นเรื่องปกติเช่นกัน

RMOO สามารถนำไปใช้กับปัญหาแบบไม่ต่อเนื่องหรือแบบผสมได้หรือไม่

ได้ แม้ว่าปัญหาย่อยกรณีที่เลวร้ายที่สุดเหนือชุดความไม่ต่อเนื่องอาจเป็น NP-hard มาตรวัดความทนทานแบบสุ่มตัวอย่าง (ค่าคาดหวัง, CVaR) มีประโยชน์มากกว่าในบริบทแบบผสมเมื่อเทียบกับการกำหนดสูตร minimax ที่แน่นอน

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

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

  1. Deb, K., & Gupta, H. (2006). Introducing robustness in multi-objective optimization. Evolutionary Computation, 14(4), 463–494.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Robust optimization. Wikipedia.

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