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

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

ผู้เสนอ
Kalyanmoy Deb and Himanshu Gupta
ปี
2006
ประเภท
Robust evolutionary multi-objective optimization algorithm
กลุ่มวิธี
Simulation / optimization

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

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

ใช้ทำอะไร?

Robust NSGA-II เป็นการขยายอัลกอริทึมเชิงวิวัฒนาการ NSGA-II แบบคลาสสิก เพื่อรองรับความไม่แน่นอนของพารามิเตอร์ โดยค้นหาผลลัพธ์ที่ยอมรับความสูญเสียได้ (Pareto-optimal trade-off solutions) ซึ่งยังคงมีประสิทธิภาพสูงแม้ว่าค่าพารามิเตอร์อินพุตจะเบี่ยงเบนไปจากค่าที่กำหนดไว้ก็ตาม แทนที่จะหาค่าที่เหมาะสมที่สุดของค่าวัตถุประสงค์ ณ จุดเดียว อัลกอริทึมจะประเมินแต่ละผลลัพธ์ที่เสนอขึ้นมาในช่วงหรือการกระจายของการรับรู้ความไม่แน่นอน และเลือกผลลัพธ์ที่ทนทาน (robust) ควบคู่ไปกับการครอบงำแบบพาเรโต (Pareto dominance)

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

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

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

Robust NSGA-II เกิดจากกรอบการหาค่าเหมาะสมที่สุดแบบหลายวัตถุประสงค์ที่ทนทาน ซึ่งกำหนดรูปแบบอย่างเป็นทางการโดย Deb และ Gupta ในปี 2006 ผู้ซึ่งนำเมตริกความทนทานที่ชัดเจนมาใช้ในกลไกการคัดเลือกของ NSGA-II อัลกอริทึม NSGA-II พื้นฐานได้รับการตีพิมพ์โดย Deb, Pratap, Agarwal และ Meyarivan ในปี 2002 งานวิจัยต่อมาโดยนักวิจัยด้านการออกแบบทางวิศวกรรม วิจัยการดำเนินงาน และระบบพลังงาน ได้ขยายกรอบการทำงานนี้ไปยังปัญหาที่มีข้อจำกัดแบบสุ่ม ประเภทความไม่แน่นอนแบบผสม และการประเมินความทนทานโดยใช้ตัวแทน

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

ใช้ Robust NSGA-II เมื่อปัญหาแบบหลายวัตถุประสงค์เกี่ยวข้องกับพารามิเตอร์ที่ไม่แน่นอน (คุณสมบัติวัสดุ ความต้องการ ต้นทุน สภาวะแวดล้อม) และผลลัพธ์ต้องยังคงเป็นที่ยอมรับได้ตลอดการเบี่ยงเบนที่น่าจะเป็นไปได้จากค่าที่กำหนดไว้ ไม่ใช่แค่ ณ จุดออกแบบเดียว เหมาะสำหรับการออกแบบทางวิศวกรรม การวางแผนห่วงโซ่อุปทานภายใต้ความไม่แน่นอนของความต้องการ และการหาค่าเหมาะสมที่สุดของระบบพลังงาน ควรหลีกเลี่ยงเมื่อมีงบประมาณการคำนวณจำกัดมาก เนื่องจากต้นทุนการประเมินตัวอย่างความไม่แน่นอน M ครั้งต่อบุคคลต่อรุ่นจะเพิ่มต้นทุนการประเมินฟังก์ชันเป็น M เท่า นอกจากนี้ ควรหลีกเลี่ยงเมื่อความไม่แน่นอนมีน้อยเมื่อเทียบกับการเปลี่ยนแปลงของวัตถุประสงค์ หรือเมื่อสามารถประเมินฟังก์ชันวัตถุประสงค์ได้เพียงสองหรือสามครั้งต่อผลลัพธ์ที่เสนอขึ้นมาเท่านั้น — ในกรณีนี้ NSGA-II แบบมาตรฐานหรือวิธีที่ใช้ตัวแทน (surrogate-assisted methods) จะมีประสิทธิภาพมากกว่า

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

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

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

จุดแข็ง

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

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

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

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

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

1

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

2

สำหรับแต่ละผลลัพธ์ที่เสนอขึ้นมา x ในประชากร สุ่มตัวอย่าง M ครั้งของการรับรู้ความไม่แน่นอนจากการกระจายพารามิเตอร์ที่ระบุ (หรือแจกแจงกลุ่มที่จัดโครงสร้าง) ประเมินฟังก์ชันวัตถุประสงค์ทั้งหมดภายใต้การรับรู้แต่ละครั้ง และรวบรวมผลลัพธ์เป็นค่าประมาณความทนทานของวัตถุประสงค์ การรวบรวมทั่วไป: ใช้ค่าเฉลี่ยเป็นค่าประมาณความทนทานสำหรับประสิทธิภาพที่คาดหวัง และเพิ่มค่าปรับตามสัดส่วนของค่าเบี่ยงเบนมาตรฐานเพื่อรองรับความแปรปรวน ดังนั้น วัตถุประสงค์ที่ทนทานจะกลายเป็น f_robust(x) = mean[f(x, xi)] + lambda * std[f(x, xi)]

3

ใช้การจัดอันดับแบบไม่ครอบงำอย่างรวดเร็ว (fast non-dominated sorting) กับประชากรโดยใช้ค่าประมาณความทนทานของวัตถุประสงค์แทนค่าที่กำหนดไว้ กำหนดให้แต่ละผลลัพธ์อยู่ในกลุ่มที่ไม่ครอบงำ (non-domination front) F1, F2, ... โดยพิจารณาจากการครอบงำแบบพาเรโตของวัตถุประสงค์ที่ทนทาน ผลลัพธ์ใน F1 คือผลลัพธ์ที่ไม่ถูกครอบงำโดยผลลัพธ์อื่นในแง่ของความทนทาน (robustly non-dominated): ไม่มีผลลัพธ์อื่นใดดีกว่าในทุกวัตถุประสงค์ที่ทนทานพร้อมกัน

4

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

5

ใช้การคัดเลือกแบบทัวร์นาเมนต์ทวิภาค (binary tournament selection) โดยใช้ตัวดำเนินการเปรียบเทียบความแออัด (crowded-comparison operator) กับกลุ่มที่ทนทานและระยะห่างความแออัด สร้างประชากรสืบพันธุ์ Q ขนาด N ผ่านตัวดำเนินการครอสโอเวอร์ (simulated binary crossover) และมิวเทชัน (polynomial mutation) ประเมินผลลัพธ์สืบพันธุ์อีกครั้งโดยใช้การประเมินความทนทานด้วยตัวอย่างความไม่แน่นอน M ตัวต่อแต่ละบุคคล ขั้นตอนนี้มีผลต่อเวลาทำงานอย่างมากเมื่อ M มีค่าสูง

6

รวมประชากรพ่อแม่ P และประชากรสืบพันธุ์ Q เข้าเป็นกลุ่มรวม 2N ผลลัพธ์ จัดอันดับใหม่ตามการครอบงำแบบไม่ครอบงำที่ทนทานและระยะห่างความแออัด เลือก N ผลลัพธ์ที่ดีที่สุดเพื่อสร้างรุ่นถัดไป โดยรักษาความเป็นเอลีท (elitism) สิ้นสุดเมื่อถึงขีดจำกัดรุ่นสูงสุด ปริมาตรไฮเปอร์ (hypervolume) คงที่ หรืองบประมาณการคำนวณหมดสิ้น ส่งคืนชุดผลลัพธ์พาเรโตที่ทนทานสุดท้าย F1

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

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

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

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

NSGA-II แบบมาตรฐานประเมินผลลัพธ์ที่เสนอขึ้นมาแต่ละรายการ ณ ค่าพารามิเตอร์ที่กำหนดไว้ และใช้ค่าวัตถุประสงค์เหล่านั้นสำหรับการครอบงำแบบพาเรโต Robust NSGA-II ประเมินผลลัพธ์แต่ละรายการผ่านการรับรู้พารามิเตอร์ที่ไม่แน่นอน M ครั้ง รวบรวมผลลัพธ์เป็นค่าประมาณความทนทานของวัตถุประสงค์ (เช่น ค่าเฉลี่ยและความแปรปรวน) และใช้ค่าประมาณเหล่านั้นสำหรับการจัดอันดับการครอบงำ สิ่งนี้จะเพิ่มต้นทุนการคำนวณเป็น M เท่า แต่ให้ผลลัพธ์ที่ยังคงสามารถแข่งขันได้เมื่อพารามิเตอร์เบี่ยงเบนไปจากค่าที่กำหนดไว้

ฉันควรใช้จำนวนตัวอย่างความไม่แน่นอน M เท่าใดต่อบุคคล?

ไม่มีกฎสากล จุดเริ่มต้นทั่วไปคือ M = 30 ถึง 50 ตัวอย่างมอนติคาร์โล หากการประเมินวัตถุประสงค์มีต้นทุนต่ำ สำหรับการประเมินที่มีต้นทุนสูง อาจจำเป็นต้องใช้ M = 5 ถึง 10 ทำการศึกษาความไว: เพิ่ม M จนกว่าค่าประมาณความทนทานของวัตถุประสงค์จะคงที่ การสุ่มตัวอย่างแบบกึ่งสุ่ม (Latin hypercube หรือ Sobol) ให้ความครอบคลุมที่ดีกว่าการสุ่มตัวอย่างแบบสุ่มอย่างแท้จริงสำหรับ M เดียวกัน

ฉันสามารถใช้ Robust NSGA-II กับวัตถุประสงค์มากกว่าสามข้อได้หรือไม่?

อัลกอริทึมสามารถนำไปใช้ได้ แต่ประสิทธิภาพจะลดลงด้วยเหตุผลเดียวกับ NSGA-II แบบมาตรฐาน: ระยะห่างความแออัดสูญเสียอำนาจในการแยกแยะในปริภูมิวัตถุประสงค์ที่มีมิติสูง และผลลัพธ์ส่วนใหญ่จะตกอยู่ในกลุ่มที่ไม่ครอบงำกลุ่มแรก สำหรับวัตถุประสงค์สี่ข้อขึ้นไป ควรพิจารณา NSGA-III เวอร์ชันที่ทนทาน ซึ่งใช้การคัดเลือกตามจุดอ้างอิง (reference-point-based selection) แทนระยะห่างความแออัด

ฉันควรเลือกเมตริกความทนทานใด?

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

ฉันจะตรวจสอบได้อย่างไรว่าผลลัพธ์ที่ส่งคืนมีความทนทานอย่างแท้จริง?

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

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

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

  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. Deb, K., & Gupta, H. (2006). Introducing robustness in multi-objective optimization. Evolutionary Computation, 14(4), 463-494.

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