NSGA-II — ขั้นตอนวิธีเชิงพันธุกรรมแบบจัดลำดับไม่ถูกครอบงำ II (Non-dominated Sorting Genetic Algorithm II)
- ปี
- 2002
- ประเภท
- Evolutionary multi-objective optimisation algorithm
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
NSGA-II (Non-dominated Sorting Genetic Algorithm II) เป็นอัลกอริทึมอ้างอิงมาตรฐานสำหรับการหาค่าเหมาะสมที่สุดแบบหลายวัตถุประสงค์เชิงวิวัฒนาการ (multi-objective evolutionary optimisation) ซึ่ง Deb, Pratap, Agarwal และ Meyarivan ได้นำเสนอในปี 2002 แทนที่จะยุบรวมวัตถุประสงค์ที่ขัดแย้งกันหลายประการให้เป็นคะแนนเดียว อัลกอริทึมนี้จะพัฒนาประชากรของคำตอบที่เป็นไปได้ (candidate solutions) ข้ามรุ่น (generations) และส่งคืนชุดของคำตอบที่ยอมแลกเปลี่ยนกันได้แบบพาเรโต (Pareto-optimal trade-off solutions) ซึ่งก็คือ พาเรโตฟรอนต์ (Pareto front) โดยใช้วิธีการจัดลำดับแบบไม่ถูกครอบงำที่รวดเร็ว (fast non-dominated sorting) และตัวชี้วัดระยะห่างความแออัด (crowding distance metric) เพื่อรักษาความหลากหลาย
แนวคิดเบื้องหลังวิธีการ
ลองนึกภาพว่าคุณต้องการออกแบบผลิตภัณฑ์ที่ราคาถูกที่สุดและทนทานที่สุดไปพร้อมๆ กัน โดยทั่วไปแล้ว การที่ราคาถูกลงมักจะหมายถึงความทนทานที่น้อยลง ดังนั้นจึงไม่มีคำตอบที่สมบูรณ์แบบเพียงคำตอบเดียว แต่จะมีชุดของการประนีประนอมที่สมเหตุสมผลอยู่ NSGA-II ทำงานเหมือนกับประชากรของการออกแบบที่แข่งขันกัน: ในแต่ละรุ่น คำตอบที่ด้อยกว่าซึ่งถูกครอบงำโดยคำตอบอื่นในทุกวัตถุประสงค์จะถูกกำจัดออกไป และคำตอบที่เหลือรอดจะถูกกระจายออกไปเพื่อให้ครอบคลุมช่วงของการแลกเปลี่ยนกันได้ทั้งหมด แทนที่จะกระจุกตัวอยู่ที่มุมใดมุมหนึ่ง หลังจากผ่านไปหลายรุ่น คุณจะได้ชุดทางเลือกที่หลากหลาย ซึ่งก็คือ พาเรโตฟรอนต์ ซึ่งคุณสามารถเลือกการประนีประนอมที่เหมาะสมกับลำดับความสำคัญของคุณได้
ประวัติศาสตร์
NSGA-II ได้รับการตีพิมพ์โดย Kalyanmoy Deb และเพื่อนร่วมงานที่ Indian Institute of Technology Kanpur ในปี 2002 ในฐานะผู้สืบทอดที่ปรับปรุงอย่างมากจาก NSGA ดั้งเดิม (Srinivas & Deb, 1994) นวัตกรรมที่สำคัญคือกระบวนการจัดลำดับแบบไม่ถูกครอบงำที่รวดเร็วซึ่งมีความซับซ้อน O(MN²) ตัวดำเนินการระยะห่างความแออัดที่ชัดเจนเพื่อรักษาความหลากหลายของคำตอบโดยไม่ต้องใช้พารามิเตอร์การแบ่งปัน (sharing parameter) และกลไกการคัดเลือกแบบ elitist บทความในปี 2002 ใน IEEE Transactions on Evolutionary Computation ได้กลายเป็นหนึ่งในงานที่มีการอ้างอิงมากที่สุดในสาขาวิทยาการวิวัฒนาการ (evolutionary computation) และทำให้ NSGA-II กลายเป็นมาตรฐานโดยพฤตินัยสำหรับอัลกอริทึมวิวัฒนาการหลายวัตถุประสงค์ (multi-objective evolutionary algorithms) รุ่นต่อมา — NSGA-III (2014) และอื่นๆ — ได้ขยายกรอบการทำงานไปยังปัญหาที่มีวัตถุประสงค์จำนวนมาก (many-objective problems)
ควรใช้เมื่อใด
NSGA-II สามารถนำไปใช้ได้ทุกเมื่อที่มีปัญหาซึ่งมีฟังก์ชันวัตถุประสงค์ที่ขัดแย้งกันตั้งแต่สองฟังก์ชันขึ้นไป ซึ่งไม่สามารถรวมเข้าเป็นเกณฑ์เดียวได้โดยไม่สูญเสียข้อมูล ตัวแปรตัดสินใจสามารถเป็นแบบต่อเนื่อง (continuous), แบบไบนารี (binary), หรือแบบหมวดหมู่ (categorical) และไม่จำเป็นต้องมีข้อสมมติฐานเกี่ยวกับการกระจายตัวบนภูมิทัศน์วัตถุประสงค์ (objective landscape) อัลกอริทึมนี้เหมาะสำหรับการออกแบบทางวิศวกรรม (engineering design), การจัดสรรทรัพยากร (resource allocation), การจัดตารางเวลา (scheduling), และปัญหาพอร์ตการลงทุน (portfolio problems) ที่ชุดคำตอบที่ยอมแลกเปลี่ยนกันได้มีประโยชน์มากกว่าค่าที่เหมาะสมที่สุดเพียงค่าเดียว จำเป็นต้องมีจำนวนรุ่นที่เพียงพอ (โดยทั่วไปคือหลายร้อยรุ่นหรือมากกว่า) เพื่อให้ได้ความครอบคลุมของฟรอนต์ที่ดี การรันน้อยรุ่นเกินไปเป็นโหมดความล้มเหลวหลัก
ข้อจำกัดและข้อควรพิจารณา
- ประสิทธิภาพลดลงเมื่อจำนวนวัตถุประสงค์เพิ่มขึ้นเกินสามหรือสี่วัตถุประสงค์ — ระยะห่างความแออัดกลายเป็นมาตรวัดความหลากหลายที่ไม่ดีในมิติสูง
- ต้องมีการปรับแต่งขนาดประชากรและจำนวนรุ่นอย่างระมัดระวัง การมีจำนวนรุ่นน้อยเกินไปจะทำให้ฟรอนต์ครอบคลุมไม่เพียงพอ
- การประเมินฟังก์ชันวัตถุประสงค์ที่เกี่ยวข้องกับการจำลองที่มีค่าใช้จ่ายสูงทำให้อัลกอริทึมมีต้นทุนในการคำนวณสูง
- ผลลัพธ์เป็นแบบสุ่ม (stochastic): seed สุ่ม (random seeds) ที่แตกต่างกันสามารถให้ผลลัพธ์พาเรโตฟรอนต์ที่แตกต่างกันได้ ดังนั้นจึงแนะนำให้รันหลายครั้งและทำการเปรียบเทียบทางสถิติ (เช่น hypervolume)
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- สร้างชุดคำตอบที่ยอมแลกเปลี่ยนกันได้แบบพาเรโตที่หลากหลายในการรันครั้งเดียว หลีกเลี่ยงความจำเป็นในการหาค่าเหมาะสมที่สุดซ้ำๆ ด้วยน้ำหนักที่แตกต่างกัน
- การจัดลำดับแบบไม่ถูกครอบงำที่รวดเร็วทำงานในเวลา O(MN²) (M วัตถุประสงค์, N ขนาดประชากร) ทำให้สามารถจัดการได้สำหรับปัญหาขนาดปานกลาง
- การคัดเลือกแบบ elitistรับประกันว่าคำตอบที่ดีที่พบตั้งแต่เนิ่นๆ จะไม่ถูกทิ้งไป
- สามารถนำไปใช้กับตัวแปรตัดสินใจแบบต่อเนื่อง, แบบไบนารี, และแบบหมวดหมู่ได้โดยไม่มีข้อสมมติฐานเกี่ยวกับการกระจายตัว
- ผ่านการใช้งานอย่างกว้างขวางในสาขาวิศวกรรม, การวิจัยดำเนินงาน, และวิทยาการคำนวณ
การประยุกต์ใช้
- การออกแบบทางวิศวกรรม: การลดน้ำหนักและเพิ่มความแข็งแรงของโครงสร้างในส่วนประกอบทางกลพร้อมๆ กัน
- ระบบสิ่งแวดล้อมและพลังงาน: การสร้างสมดุลระหว่างต้นทุน การปล่อยมลพิษ และความน่าเชื่อถือในการวางแผนโครงข่ายไฟฟ้าหรือพลังงานหมุนเวียน
- การดูแลสุขภาพและการวิจัยดำเนินงาน: การจัดตารางเวลาที่ปรับให้เหมาะสมกับเวลารอคอยของผู้ป่วย การใช้ทรัพยากร และต้นทุนไปพร้อมๆ กัน
- การหาค่าเหมาะสมที่สุดของพอร์ตการลงทุนทางการเงินและการเลือกโครงการทางธุรกิจ: การแลกเปลี่ยนระหว่างผลตอบแทน ความเสี่ยง และสภาพคล่อง
- การปรับแต่งไฮเปอร์พารามิเตอร์ (Hyperparameter tuning) ในการเรียนรู้ของเครื่อง (machine learning): การเพิ่มความแม่นยำควบคู่กับการลดความซับซ้อนของแบบจำลองหรือเวลาในการอนุมาน (inference time)
วิธีการทำงาน
วิธีการทำงาน
ประชากรของคำตอบที่เป็นไปได้ถูกสร้างขึ้นโดยการสุ่มตัวอย่างตัวแปรตัดสินใจ (decision variables) แบบสุ่ม (หรือตามการออกแบบ) ภายในขอบเขตของมัน ขนาดของประชากรถูกกำหนดให้ใหญ่พอที่จะรับประกันความหลากหลายทั่วทั้งปริภูมิวัตถุประสงค์ (objective space) ตั้งแต่เริ่มต้น
คำตอบที่เป็นไปได้แต่ละรายการจะถูกถอดรหัสเป็นค่าตัวแปรตัดสินใจ และฟังก์ชันวัตถุประสงค์แต่ละรายการจะถูกประเมิน ผลลัพธ์ที่ได้คือเวกเตอร์ของคะแนนวัตถุประสงค์ต่อแต่ละตัวในประชากร ขั้นตอนนี้มักจะเป็นคอขวดในการคำนวณเมื่อวัตถุประสงค์เกี่ยวข้องกับการจำลองหรือแบบจำลองที่มีค่าใช้จ่ายสูง
คำตอบจะถูกจัดอันดับด้วยการจัดลำดับแบบไม่ถูกครอบงำ (non-dominated sorting): ฟรอนต์แรกประกอบด้วยคำตอบทั้งหมดที่ไม่มีคำตอบอื่นใดครอบงำในทุกวัตถุประสงค์ ฟรอนต์ที่สองประกอบด้วยคำตอบที่ถูกครอบงำโดยคำตอบในฟรอนต์แรกเท่านั้น และต่อไปเรื่อยๆ ภายในแต่ละฟรอนต์ จะมีการคำนวณคะแนนระยะห่างความแออัด (crowding distance score) เพื่อวัดว่าคำตอบนั้นแยกจากเพื่อนบ้านมากน้อยเพียงใด — ระยะห่างความแออัดที่สูงขึ้นหมายความว่าคำตอบนั้นอยู่ในบริเวณที่แออัดน้อยกว่าของฟรอนต์
กลยุทธ์การคัดเลือกแบบ elitist (elitist selection strategy) จะรวมประชากรปัจจุบันเข้ากับลูกหลาน (offspring) และเก็บรักษาตัวที่ดีที่สุด N ตัว โดยเติมฟรอนต์ตามลำดับและใช้ระยะห่างความแออัดเพื่อตัดสินกรณีที่เท่ากันในฟรอนต์สุดท้ายที่ยอมรับได้ วิธีนี้รับประกันว่าคำตอบที่ดีที่พบในรุ่นก่อนๆ จะไม่สูญหายไป
ตัวที่ถูกเลือกจะสืบพันธุ์ผ่านตัวดำเนินการทางพันธุกรรม (genetic operators) — การคัดเลือกแบบทัวร์นาเมนต์ไบนารี (binary tournament selection), การผสมข้ามแบบไบนารีจำลอง (simulated binary crossover - SBX), และการกลายพันธุ์แบบพหุนาม (polynomial mutation) — เพื่อสร้างประชากรลูกหลานใหม่ ตัวดำเนินการเหล่านี้จะรักษาความแปรปรวนที่มีความหมายไว้ในขณะที่สำรวจบริเวณใกล้เคียงของคำตอบที่มีแนวโน้มดี
ทำซ้ำขั้นตอนประเมิน–วิวัฒนาการ–คัดเลือก ตามจำนวนรุ่นที่กำหนด การลู่เข้า (convergence) จะถูกตัดสินโดยการตรวจสอบด้วยสายตาของพาเรโตฟรอนต์ หรือโดยการติดตามตัวบ่งชี้ไฮเปอร์โวลุ่ม (hypervolume indicator) ผลลัพธ์สุดท้ายคือชุดคำตอบที่ไม่ถูกครอบงำซึ่งประมาณค่าพาเรโตฟรอนต์ที่แท้จริง
ข้อผิดพลาดที่พบบ่อย
- การรันน้อยกว่าหลายร้อยรุ่นมักจะให้พาเรโตฟรอนต์ที่ไม่สมบูรณ์ หากงบประมาณในการคำนวณมีจำกัด ให้พิจารณาการหาค่าเหมาะสมที่สุดแบบวัตถุประสงค์เดียวแบบถ่วงน้ำหนัก (weighted single-objective optimisation) แทน
- การมองปัญหาที่มีวัตถุประสงค์เดียวเป็นปัญหาหลายวัตถุประสงค์นั้นไม่จำเป็น — ควรใช้อัลกอริทึมหาค่าเหมาะสมที่สุดแบบวัตถุประสงค์เดียว
- การละเลยการกำหนดขอบเขตตัวแปรที่สมเหตุสมผลจะนำไปสู่ประชากรที่ไม่สามารถเข้าถึงบริเวณที่เป็นไปได้หรือมีความหมายของปริภูมิการค้นหาได้
- การรายงานคำตอบเพียงคำตอบเดียวจากพาเรโตฟรอนต์โดยไม่เปิดเผยฟรอนต์ทั้งหมด จะบดบังโครงสร้างการแลกเปลี่ยนที่ NSGA-II ถูกออกแบบมาเพื่อเปิดเผย
คำถามที่พบบ่อย
NSGA-II ต้องการจำนวนรุ่นกี่รุ่น?
ไม่มีกฎสากล แต่การรันน้อยกว่าไม่กี่ร้อยรุ่นมักจะให้พาเรโตฟรอนต์ที่ไม่สมบูรณ์ แนวทางปฏิบัติคือการพล็อตตัวบ่งชี้ hypervolume ในแต่ละรุ่นและหยุดเมื่อค่าคงที่ หากงบประมาณในการคำนวณไม่อำนวย การใช้อัลกอริทึมหาค่าเหมาะสมที่สุดแบบวัตถุประสงค์เดียวแบบถ่วงน้ำหนักเป็นทางเลือกที่ปลอดภัยกว่า
พาเรโตฟรอนต์คืออะไร?
พาเรโตฟรอนต์คือชุดของคำตอบที่ไม่มีการปรับปรุงในวัตถุประสงค์หนึ่งโดยไม่ทำให้วัตถุประสงค์อื่นอย่างน้อยหนึ่งอย่างแย่ลง NSGA-II จะประมาณค่าฟรอนต์นี้ ทำให้คุณได้ชุดทางเลือกที่สมดุลทั้งหมด แทนที่จะเป็นคำตอบเดียว
NSGA-II สามารถจัดการกับวัตถุประสงค์มากกว่าสองวัตถุประสงค์ได้หรือไม่?
ได้ แต่ระยะห่างความแออัด — กลไกความหลากหลาย — จะมีประสิทธิภาพน้อยลงเมื่อจำนวนวัตถุประสงค์เกินสามหรือสี่วัตถุประสงค์ (กรณี 'many-objective') สำหรับปัญหาที่มีวัตถุประสงค์ตั้งแต่ห้าวัตถุประสงค์ขึ้นไป โดยทั่วไปจะแนะนำให้ใช้ NSGA-III หรืออัลกอริทึมที่ใช้การแยกส่วน (decomposition-based algorithms) เช่น MOEA/D
NSGA-II เป็นแบบกำหนดแน่นอน (deterministic) หรือไม่?
ไม่ ตัวดำเนินการทางพันธุกรรมและประชากรเริ่มต้นเกี่ยวข้องกับความสุ่ม ดังนั้นการรันที่แตกต่างกันด้วย seed สุ่มที่แตกต่างกันอาจให้ผลลัพธ์พาเรโตฟรอนต์ที่แตกต่างกัน แนวทางปฏิบัติที่ดีที่สุดคือการรันอัลกอริทึมหลายครั้งและเปรียบเทียบคุณภาพของฟรอนต์โดยใช้ตัวบ่งชี้ hypervolume
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
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คัดลอกแล้วZitzler, E., Deb, K. & Thiele, L. (2000). Comparison of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation, 8(2), 173-195.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว