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

Stochastic NSGA-II — การปรับให้เหมาะสมหลายวัตถุประสงค์เชิงวิวัฒนาการภายใต้ความไม่แน่นอน

ผู้เสนอ
Deb, K. et al. (NSGA-II base); Hughes, E. J. and subsequent researchers for stochastic extensions
ปี
2001–2002
ประเภท
Evolutionary multi-objective optimization under uncertainty
กลุ่มวิธี
Simulation / optimization

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

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

ใช้ทำอะไร?

Stochastic NSGA-II เป็นการต่อยอดอัลกอริทึมเชิงวิวัฒนาการ NSGA-II เพื่อจัดการกับฟังก์ชันวัตถุประสงค์ที่มีสัญญาณรบกวน ไม่แน่นอน หรือเป็นเชิงความน่าจะเป็น โดยการหาค่าเฉลี่ยหรือสุ่มตัวอย่างวัตถุประสงค์เชิงสุ่มจากการประเมินหลายครั้ง อัลกอริทึมนี้สามารถระบุผลเฉลย Pareto-optimal ที่ทนทานต่อความไม่แน่นอน ทำให้เหมาะสำหรับปัญหาการออกแบบทางวิศวกรรม ห่วงโซ่อุปทาน และการปรับให้เหมาะสมเชิงนโยบายที่ความผันแปรในโลกแห่งความเป็นจริงมีความสำคัญ

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

NSGA-II เป็นหนึ่งในอัลกอริทึมที่มีประสิทธิภาพสูงสุดสำหรับการค้นหาชุดผลเฉลย Pareto-optimal ที่หลากหลายซึ่งมีการแลกเปลี่ยนกันในปัญหาหลายวัตถุประสงค์ อย่างไรก็ตาม เวอร์ชันมาตรฐานจะสมมติว่าการประเมินวัตถุประสงค์เป็นแบบกำหนดค่าได้ (deterministic) ในทางปฏิบัติ การจำลอง การทดลอง และระบบจริงมักจะให้ผลลัพธ์ที่มีสัญญาณรบกวน Stochastic NSGA-II แก้ปัญหานี้โดยการสุ่มตัวอย่างซ้ำหรือประมาณค่าทางสถิติของความเหมาะสมที่แท้จริงของแต่ละผลเฉลย จากนั้นจึงใช้การจัดเรียงแบบไม่ถูกครอบงำอย่างรวดเร็ว (fast non-dominated sorting) และการเลือกตามระยะห่างความหนาแน่น (crowding distance selection) ของ NSGA-II เพื่อนำทางไปตาม Pareto front ได้อย่างน่าเชื่อถือแม้จะมีสัญญาณรบกวนก็ตาม แนวคิดหลักคือการจัดอันดับผลเฉลยตามประสิทธิภาพที่คาดหวัง หรือตามความน่าจะเป็นของการครอบงำ จะสามารถกู้คืนโครงสร้าง Pareto ที่ถูกต้องได้แม้ว่าการประเมินแต่ละครั้งจะไม่น่าเชื่อถือก็ตาม

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

NSGA-II ได้รับการแนะนำโดย Deb et al. ในปี 2002 ในฐานะอัลกอริทึมพันธุกรรมหลายวัตถุประสงค์แบบเร็วและชนชั้นสูง และกลายเป็นมาตรฐานการวัดผลอย่างรวดเร็ว ส่วนขยายเชิงสุ่มปรากฏขึ้นไม่นานหลังจากนั้น โดยได้รับแรงผลักดันจากชุมชนการปรับให้เหมาะสมทางวิศวกรรมที่ต้องการจัดการกับสัญญาณรบกวนจากการจำลอง Hughes (2001) ได้กำหนดรูปแบบการจัดอันดับหลายวัตถุประสงค์ภายใต้ความไม่แน่นอน ตั้งแต่กลางทศวรรษ 2000 มีตัวแปรจำนวนมากปรากฏขึ้น ครอบคลุมการสุ่มตัวอย่างซ้ำแบบปรับตัว ความน่าจะเป็นของการครอบงำ และการปรับปรุงปริมาตรไฮเปอร์ที่คาดหวังภายใต้สัญญาณรบกวน

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

ใช้ Stochastic NSGA-II เมื่อคุณเผชิญกับปัญหาการปรับให้เหมาะสมหลายวัตถุประสงค์ที่วัตถุประสงค์ถูกประเมินผ่านการจำลอง การทดลอง หรือเซ็นเซอร์ที่มีสัญญาณรบกวน และคุณต้องการผลเฉลยที่ยังคงดีตลอดช่วงของความไม่แน่นอน — ไม่ใช่แค่โดยเฉลี่ย เหมาะอย่างยิ่งสำหรับการออกแบบทางวิศวกรรมภายใต้ความคลาดเคลื่อนในการผลิต การปรับให้เหมาะสมห่วงโซ่อุปทานที่มีความไม่แน่นอนของอุปสงค์ และแบบจำลองสิ่งแวดล้อมหรือนโยบายที่มีปัจจัยนำเข้าเชิงสุ่ม อย่าใช้เมื่อวัตถุประสงค์เป็นแบบกำหนดค่าได้และประเมินได้ง่าย (NSGA-II มาตรฐานก็เพียงพอแล้ว) เมื่อจำนวนการทำซ้ำที่จำเป็นสำหรับการประมาณค่าที่น่าเชื่อถือทำให้งบประมาณทั้งหมดไม่สามารถทำได้ หรือเมื่อปัญหาเป็นแบบวัตถุประสงค์เดียว (ใช้ EA แบบวัตถุประสงค์เดียวเชิงสุ่มแทน) หลีกเลี่ยงเมื่อการแจกแจงสัญญาณรบกวนไม่คงที่อย่างมากหรือไม่เป็นไปตามสมมติฐานการสุ่มแบบ i.i.d.

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

  • ต้นทุนการคำนวณจะเพิ่มขึ้นตามจำนวนการทำซ้ำ r ต่อการประเมิน คูณด้วยขนาดประชากรและจำนวนรุ่น — อาจกลายเป็นสิ่งต้องห้ามสำหรับการจำลองที่มีค่าใช้จ่ายสูง
  • การเลือกจำนวนการทำซ้ำ r ที่เหมาะสมไม่ใช่เรื่องง่าย: น้อยเกินไปทำให้เกิดข้อผิดพลาดในการจัดอันดับ มากเกินไปทำให้สิ้นเปลืองงบประมาณ
  • ไม่มีการรับประกันการลู่เข้าอย่างเป็นทางการไปยัง Pareto front เชิงสุ่มที่แท้จริง คุณภาพขึ้นอยู่กับงบประมาณและระดับสัญญาณรบกวน
  • การเปรียบเทียบการครอบงำโดยใช้ค่าเฉลี่ยที่ประมาณค่าไว้ละเลยความไม่แน่นอนของการประมาณค่า ซึ่งอาจทำให้เกิดการจัดอันดับผิดพลาดภายใต้สัญญาณรบกวนสูง

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

จุดแข็ง

  • สืบทอดความสามารถในการค้นหา Pareto-front ที่แข็งแกร่งและการรักษาสภาพความหลากหลายของ NSGA-II ผ่านการจัดเรียงแบบไม่ถูกครอบงำและระยะห่างความหนาแน่น
  • คำนึงถึงสัญญาณรบกวนของฟังก์ชันวัตถุประสงค์อย่างชัดเจน ทำให้ได้ผลเฉลยที่แข็งแกร่งและน่าเชื่อถือในการใช้งานจริง
  • กรอบการทำงานที่ยืดหยุ่น — การประมาณค่าเชิงสุ่มสามารถใช้การหาค่าเฉลี่ย ความแข็งแกร่งตามควอนไทล์ หรือความน่าจะเป็นของการครอบงำ โดยไม่ต้องเปลี่ยนอัลกอริทึมหลัก
  • สามารถใช้ได้กับแบบจำลองการจำลองแบบกล่องดำที่ไม่มีข้อมูลการไล่ระดับ
  • สร้าง Pareto front ที่สมบูรณ์ แทนที่จะเป็นผลเฉลยเดียว ทำให้ผู้ตัดสินใจมีทางเลือกในการแลกเปลี่ยนที่ชัดเจน

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

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

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

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

1

กำหนดปัญหาการปรับให้เหมาะสมหลายวัตถุประสงค์ด้วยฟังก์ชันวัตถุประสงค์เชิงสุ่ม k ฟังก์ชัน f_1(x,xi), ..., f_k(x,xi) โดยที่ xi แทนพารามิเตอร์สุ่มที่ได้จากการแจกแจงที่ทราบหรือประมาณค่าไว้ ระบุขอบเขตตัวแปรตัดสินใจ ข้อจำกัด และจำนวนการประเมินซ้ำ (replicates) r ที่ใช้ในการประมาณค่าคาดหวังของแต่ละวัตถุประสงค์

2

เริ่มต้นประชากรของผลเฉลยผู้สมัคร N ตัวแบบสุ่มภายในพื้นที่การตัดสินใจที่เป็นไปได้ สำหรับแต่ละบุคคล กำหนดเวกเตอร์ประมาณค่าความเหมาะสมที่มีความยาว k โดยเริ่มต้นเป็นศูนย์ กำหนดตัวนับรุ่น g = 0 และกำหนดเกณฑ์การหยุด (จำนวนรุ่นสูงสุด G_max หรือความคลาดเคลื่อนของการลู่เข้า)

3

สำหรับแต่ละบุคคล x_i ในประชากร ให้ประเมินแต่ละวัตถุประสงค์ f_j(x_i, xi) จำนวน r ครั้ง โดยการสุ่มตัวอย่าง xi จากการแจกแจง (หรือเรียกใช้การจำลองซ้ำ r ครั้ง) ประมาณค่าวัตถุประสงค์ที่แท้จริงเป็นค่าเฉลี่ยตัวอย่าง: f_j_hat(x_i) = (1/r) * sum_{l=1}^{r} f_j(x_i, xi_l) อาจคำนวณค่าความคลาดเคลื่อนมาตรฐานเพื่อใช้ในการแจ้งกลยุทธ์การสุ่มตัวอย่างซ้ำแบบปรับตัว

4

ใช้การจัดเรียงแบบไม่ถูกครอบงำอย่างรวดเร็ว (fast non-dominated sorting) กับเวกเตอร์วัตถุประสงค์ที่ประมาณค่าไว้ ผลเฉลย x_a ครอบงำ x_b หาก f_j_hat(x_a) <= f_j_hat(x_b) สำหรับทุก j และน้อยกว่าอย่างเคร่งครัดสำหรับอย่างน้อยหนึ่ง j กำหนดแต่ละผลเฉลยให้อยู่ในอันดับ Pareto front F_1, F_2, ... โดยที่ F_1 มีผลเฉลยที่ไม่ถูกครอบงำโดยผลเฉลยอื่นใด

5

เลือกพ่อแม่โดยใช้การเลือกแบบทัวร์นาเมนต์ไบนารี (binary tournament selection) โดยอิงตามอันดับ Pareto และระยะห่างความหนาแน่น (เพื่อรักษาสภาพความหลากหลาย) ใช้ตัวดำเนินการทางพันธุกรรม — การผสมข้ามแบบไบนารีจำลอง (simulated binary crossover, SBX) และการกลายพันธุ์พหุนาม (polynomial mutation) — เพื่อสร้างประชากรรุ่นลูก Q ที่มีขนาด N รวมประชากรพ่อแม่และรุ่นลูก (ขนาด 2N) ประเมินวัตถุประสงค์เชิงสุ่มใหม่ จัดเรียงใหม่ และเลือกผลเฉลย N อันดับแรกตามอันดับแล้วตามระยะห่างความหนาแน่น

6

เพิ่มค่า g หาก g < G_max และ Pareto front ยังไม่เสถียร ให้ทำซ้ำจากขั้นตอนการประเมินเชิงสุ่ม มิฉะนั้น ให้ส่งคืน Pareto front สุดท้าย F_1 เป็นชุดของผลเฉลยที่ทนทานและไม่ถูกครอบงำ รายงาน Pareto front โดยประมาณในพื้นที่วัตถุประสงค์สำหรับการเลือกของผู้ตัดสินใจ

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

  • การใช้การทำซ้ำเพียงครั้งเดียว (r=1) ต่อบุคคลถือว่าสัญญาณรบกวนเป็นสัญญาณ ซึ่งนำไปสู่ Pareto fronts ที่ไม่เสถียรอย่างมากในการทำงานซ้ำ — ควรใช้ r >= 3 เป็นอย่างน้อยและตรวจสอบการลู่เข้า
  • การละเลยความแปรปรวนของวัตถุประสงค์เชิงสุ่มอาจเลือกผลเฉลยที่ดูดีโดยเฉลี่ย แต่มีประสิทธิภาพไม่ดีในสถานการณ์หาง — พิจารณาสูตรวัตถุประสงค์ตามควอนไทล์หรือกรณีที่เลวร้ายที่สุดเมื่อความเสี่ยงหางมีความสำคัญ
  • การใช้วิธีการโดยไม่ตรวจสอบว่าสัญญาณรบกวนคงที่หรือไม่: หากคุณสมบัติของสัญญาณรบกวนเปลี่ยนแปลงไปตามค่าตัวแปรตัดสินใจ จำเป็นต้องมีการสุ่มตัวอย่างซ้ำแบบปรับตัวหรือแบบจำลองเฮเทอโรสเคดาสติก
  • การถือว่า Pareto front ที่ได้เป็นผลการตัดสินใจขั้นสุดท้ายโดยไม่ประเมินความแข็งแกร่งนอกตัวอย่าง — ควรตรวจสอบผลเฉลยที่แนะนำด้วยการจำลองที่ไม่ได้ใช้ในการฝึก

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

ฉันควรใช้จำนวนการทำซ้ำ r เท่าใดต่อการประเมินแต่ละบุคคล?

จุดเริ่มต้นทั่วไปคือ r = 5–30 ขึ้นอยู่กับสัมประสิทธิ์ความแปรปรวนของวัตถุประสงค์ กลยุทธ์การปรับตัวที่จัดสรรการทำซ้ำมากขึ้นให้กับผลเฉลยชั้นยอดหรือใช้การสุ่มตัวอย่างแบบลำดับจนกว่าจะถึงเกณฑ์ความเชื่อมั่นจะมีประสิทธิภาพมากกว่า สำหรับการจำลองที่มีค่าใช้จ่ายสูง r = 3–5 ที่มีประชากรขนาดใหญ่มักจะเป็นการประนีประนอมที่ใช้ได้จริง

Stochastic NSGA-II แตกต่างจาก NSGA-II มาตรฐานอย่างไร?

ความแตกต่างเชิงโครงสร้างเพียงอย่างเดียวคือในการประเมินวัตถุประสงค์: NSGA-II มาตรฐานประเมิน f(x) เพียงครั้งเดียวและสมมติว่าผลลัพธ์ถูกต้อง ในขณะที่ Stochastic NSGA-II ประเมิน f(x, xi) r ครั้งและใช้ค่าเฉลี่ยตัวอย่าง (หรือสถิติความแข็งแกร่งอื่น ๆ) เป็นวัตถุประสงค์ที่มีประสิทธิภาพ กลไกการจัดเรียง การเลือก และตัวดำเนินการทางพันธุกรรมทั้งหมดจะยังคงเหมือนเดิม

ฉันสามารถใช้ Stochastic NSGA-II กับความน่าจะเป็นของการครอบงำแทนวัตถุประสงค์เฉลี่ยได้หรือไม่?

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

จะเกิดอะไรขึ้นถ้าการจำลองของฉันมีค่าใช้จ่ายสูงเกินไปสำหรับการทำซ้ำหลายครั้ง?

พิจารณาแนวทางที่ใช้ตัวแทนช่วย: สร้างกระบวนการเกาส์เซียนหรือเมตาโมเดลโครงข่ายประสาทเทียมของฟังก์ชันวัตถุประสงค์ ใช้เพื่อประมาณทั้งค่าเฉลี่ยและความแปรปรวนอย่างประหยัด และใช้เกณฑ์การปรับปรุงที่คาดหวังหรือความน่าจะเป็นของการปรับปรุงแทนการประเมินโดยตรงซ้ำๆ

Stochastic NSGA-II รับประกันว่าจะพบ Pareto front เชิงสุ่มที่แท้จริงหรือไม่?

ไม่ เหมือนกับอัลกอริทึมเชิงวิวัฒนาการทั้งหมด มันเป็นฮิวริสติกที่ไม่มีการรับประกันการลู่เข้าในเวลาจำกัดไปยัง front ที่แท้จริง คำแนะนำเชิงปฏิบัติ: เรียกใช้การทดลองอิสระหลายครั้ง เปรียบเทียบ fronts ที่ได้โดยใช้ตัวบ่งชี้ปริมาตรไฮเปอร์ และเพิ่มขนาดประชากรหรือจำนวนรุ่นหาก fronts แตกต่างกันอย่างมากในการทำงานซ้ำ

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

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

  1. Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182–197.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Hughes, E. J. (2001). Evolutionary multi-objective ranking with uncertainty and noise. In Proceedings of the First International Conference on Evolutionary Multi-Criterion Optimization (EMO 2001), Lecture Notes in Computer Science, vol. 1993, pp. 329–343. Springer.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว