Agent-Based NSGA-II — การหาค่าเหมาะสมที่สุดแบบหลายวัตถุประสงค์ที่ขับเคลื่อนด้วยการจำลอง
- ผู้เสนอ
- Deb et al. (NSGA-II, 2002); integrated with agent-based modeling frameworks in the 2000s–2010s
- ปี
- 2000s–2010s
- ประเภท
- Simulation-embedded evolutionary multi-objective optimizer
- กลุ่มวิธี
- Simulation / optimization
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
Agent-based NSGA-II ฝังอัลกอริทึมวิวัฒนาการ NSGA-II ไว้ภายในวงรอบการจำลองแบบหลายเอเจนต์ เพื่อให้ค่าวัตถุประสงค์สำหรับแต่ละคำตอบที่เป็นไปได้ถูกกำหนดโดยการรันการจำลองเอเจนต์เต็มรูปแบบ แทนที่จะเป็นการประเมินฟังก์ชันแบบปิด การเชื่อมโยงนี้ช่วยให้สามารถหาค่าเหมาะสมที่สุดแบบหลายวัตถุประสงค์สำหรับระบบที่มีประสิทธิภาพเกิดขึ้นจากปฏิสัมพันธ์ระดับจุลภาคของเอเจนต์อิสระ แทนที่จะมาจากสมการที่สามารถวิเคราะห์ได้
แนวคิดเบื้องหลังวิธีการ
NSGA-II แบบมาตรฐานจะสอบถามสูตรคณิตศาสตร์เพื่อประเมินคะแนนแต่ละคำตอบตามวัตถุประสงค์หลายประการ เมื่อพฤติกรรมของระบบซับซ้อนเกินไปหรือเกิดขึ้นเองจนไม่สามารถแสดงออกมาเป็นสูตรได้ — เช่น โรคระบาด เครือข่ายการจราจร หรือห่วงโซ่อุปทานที่มีผู้แสดงปรับตัวได้ — คุณจะแทนที่สูตรนั้นด้วยการจำลองแบบหลายเอเจนต์ คำตอบที่เป็นไปได้แต่ละรายการจะเข้ารหัสพารามิเตอร์นโยบายหรือกฎของเอเจนต์ การจำลองจะถูกรันไปข้างหน้า ผลลัพธ์รวมจะถูกวัดเป็นค่าวัตถุประสงค์ และการจัดอันดับแบบไม่ถูกครอบงำ (non-dominated sorting) และการเลือกตามระยะห่างของกลุ่ม (crowding-distance selection) ของ NSGA-II จะสร้างแนวหน้าพาเรโต (Pareto front) ที่หลากหลายของคำตอบที่ต้องแลกเปลี่ยนกัน ผลลัพธ์คือชุดของการกำหนดค่าพารามิเตอร์ที่มีประสิทธิภาพแบบพาเรโตพร้อมกันในทุกวัตถุประสงค์ที่จำลอง แม้ว่าวัตถุประสงค์เหล่านั้นจะเกิดขึ้นจากพลวัตการปรับตัวที่ซับซ้อนก็ตาม
ประวัติศาสตร์
NSGA-II ถูกนำเสนอโดย Kalyanmoy Deb และเพื่อนร่วมงานที่ IIT Kanpur ในปี 2002 ในฐานะอัลกอริทึมเชิงวิวัฒนาการหลายวัตถุประสงค์ที่รวดเร็วและรักษาผู้มีคุณสมบัติเหมาะสมที่สุด (elitist) กลายเป็นหนึ่งในอัลกอริทึมที่ถูกอ้างอิงมากที่สุดในสาขาวิทยาการคำนวณเชิงวิวัฒนาการ การสร้างแบบจำลองแบบหลายเอเจนต์ในฐานะกระบวนทัศน์การคำนวณเติบโตขึ้นในช่วงทศวรรษ 1990 ด้วยแพลตฟอร์มต่างๆ เช่น Swarm, NetLogo และ Repast การเชื่อมโยง NSGA-II กับการจำลองแบบหลายเอเจนต์เกิดขึ้นในช่วงทศวรรษ 2000 และ 2010 เมื่อนักวิจัยในสาขาวางผังเมือง นิเวศวิทยา ระบาดวิทยา และการจัดการห่วงโซ่อุปทาน ต้องการหาค่าเหมาะสมที่สุดของนโยบายในระบบที่ซับซ้อนเกินกว่าจะสร้างเป็นสูตรเชิงวิเคราะห์ได้
ควรใช้เมื่อใด
ใช้ Agent-based NSGA-II เมื่อต้องหาค่าเหมาะสมที่สุดพร้อมกันสำหรับสองวัตถุประสงค์ที่ขัดแย้งกันตั้งแต่สองวัตถุประสงค์ขึ้นไป และวัตถุประสงค์เหล่านั้นเกิดขึ้นจากปฏิสัมพันธ์ของเอเจนต์ แทนที่จะเป็นฟังก์ชันแบบปิด — ตัวอย่างเช่น การสร้างสมดุลระหว่างต้นทุนการควบคุมโรคระบาดและกิจกรรมทางเศรษฐกิจในแบบจำลองประชากร หรือการลดต้นทุนห่วงโซ่อุปทานให้เหลือน้อยที่สุดพร้อมกับการเพิ่มความทนทานในเครือข่ายของซัพพลายเออร์ที่ปรับตัวได้ เหมาะสมเมื่อความไม่แน่นอนเป็นส่วนหนึ่งของระบบโดยธรรมชาติและต้องหาค่าเฉลี่ยจากการจำลองซ้ำ ไม่ควรใช้เมื่อมีฟังก์ชันวัตถุประสงค์เชิงวิเคราะห์ที่รวดเร็ว (NSGA-II แบบธรรมดาก็เพียงพอและถูกกว่ามาก) เมื่อมีวัตถุประสงค์เพียงหนึ่งเดียว เมื่อการจำลองเอเจนต์มีค่าใช้จ่ายสูงเกินไปต่อการรันแต่ละครั้งจนทำให้ประชากรจำนวนน้อยก็มีค่าใช้จ่ายในการคำนวณรวมสูงเกินไป หรือเมื่อมีวัตถุประสงค์มากกว่าสามหรือสี่วัตถุประสงค์ (ควรใช้ NSGA-III หรือ MOEA/D แทน)
ข้อจำกัดและข้อควรพิจารณา
- มีค่าใช้จ่ายในการคำนวณสูงมาก: แต่ละรุ่นต้องการการรันการจำลอง N x R ครั้ง โดยที่ R การจำลองซ้ำต่อบุคคลอาจมีจำนวนมาก เวลาจริงทั้งหมดอาจสูงเกินไป
- ประสิทธิภาพลดลงเมื่อมีวัตถุประสงค์มากกว่าสามหรือสี่วัตถุประสงค์ เนื่องจากการจัดอันดับแบบไม่ถูกครอบงำสูญเสียอำนาจในการแยกแยะ และระยะห่างของกลุ่มไม่น่าเชื่อถือในปริภูมิวัตถุประสงค์ที่มีมิติสูง
- ผลลัพธ์ขึ้นอยู่กับความเที่ยงตรงของแบบจำลองการจำลอง กฎของเอเจนต์ที่ไม่สมจริงหรือพารามิเตอร์ที่ปรับเทียบไม่ดีจะให้แนวหน้าพาเรโตที่ไม่ถูกต้องโดยไม่คำนึงถึงคุณภาพของการหาค่าเหมาะสมที่สุด
- ความไม่แน่นอนในการประเมินความเหมาะสมของการจำลองอาจทำให้การเปรียบเทียบการครอบงำเสียหายได้หากจำนวนการจำลองซ้ำ R น้อยเกินไป ซึ่งนำไปสู่การจัดอันดับพาเรโตที่ไม่ถูกต้อง
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- จัดการกับภูมิทัศน์วัตถุประสงค์ที่เกิดขึ้นเอง (emergent) ขึ้นอยู่กับเส้นทาง (path-dependent) และความไม่แน่นอน (stochastic) ที่ไม่สามารถแสดงออกมาในเชิงวิเคราะห์ได้ ทำให้สามารถนำไปใช้กับระบบปรับตัวที่ซับซ้อนได้
- สร้างแนวหน้าพาเรโตเต็มรูปแบบในการรันการหาค่าเหมาะสมที่สุดเพียงครั้งเดียว ทำให้ผู้มีอำนาจตัดสินใจมองเห็นการแลกเปลี่ยนได้อย่างชัดเจนโดยไม่ต้องใช้น้ำหนักความชอบล่วงหน้า
- กลไกการรักษาผู้มีคุณสมบัติเหมาะสมที่สุด (elitism) ของ NSGA-II ช่วยให้มั่นใจได้ว่าคำตอบที่ไม่ถูกครอบงำซึ่งมีคุณภาพสูงจะไม่ถูกทิ้งไปข้ามรุ่น
- การหาค่าเฉลี่ยการจำลองซ้ำภายในแต่ละการประเมินความเหมาะสม (fitness evaluation) ช่วยให้วิธีการนี้สามารถจัดการกับสัญญาณรบกวนจากการจำลองแบบสุ่มได้อย่างมีหลักการ
- เข้ากันได้กับแพลตฟอร์มการจำลองแบบหลายเอเจนต์ (NetLogo, Repast, AnyLogic, Mesa) ผ่านอินเทอร์เฟซตัวห่อหุ้มมาตรฐาน
การประยุกต์ใช้
- การออกแบบการแทรกแซงโรคระบาด: การค้นหาชุดค่าผสมที่เหมาะสมที่สุดแบบพาเรโตของการครอบคลุมการฉีดวัคซีนและการจำกัดการเคลื่อนย้าย ที่ร่วมกันลดภาระการติดเชื้อและต้นทุนทางเศรษฐกิจในแบบจำลองเอเจนต์ประชากร
- การวางผังการใช้ที่ดินและการขนส่งในเมือง: การหาค่าเหมาะสมที่สุดของพารามิเตอร์การแบ่งเขตและการลงทุนโครงสร้างพื้นฐานที่เกิดขึ้นเป็นผลลัพธ์ของการจราจรติดขัด การปล่อยมลพิษ และความเท่าเทียมกันจากปฏิสัมพันธ์ของเอเจนต์ผู้พักอาศัยและยานพาหนะ
- การออกแบบเครือข่ายห่วงโซ่อุปทาน: การระบุการกำหนดค่าเชิงนโยบายที่สร้างสมดุลระหว่างต้นทุน เวลานำ และความทนทานต่อการหยุดชะงักทั่วทั้งเครือข่ายของเอเจนต์ซัพพลายเออร์และผู้จัดจำหน่ายที่ปรับตัวได้
- การจัดการการเก็บเกี่ยวทางนิเวศวิทยา: การหาค่าเหมาะสมที่สุดของกฎการเก็บเกี่ยวเพื่อเพิ่มผลผลิตทางเศรษฐกิจและรักษาสภาพความหลากหลายทางชีวภาพพร้อมกันในแบบจำลองระบบนิเวศแบบหลายเอเจนต์
- การควบคุมไมโครกริดพลังงาน: การหาค่าเหมาะสมที่สุดร่วมกันของกลยุทธ์การเสนอราคาของเอเจนต์ผู้ผลิต-ผู้บริโภค (prosumer) เพื่อลดต้นทุนกริดและการปล่อยคาร์บอนภายใต้การสร้างพลังงานหมุนเวียนแบบสุ่ม
- การวิเคราะห์นโยบายความไม่เท่าเทียมกันทางสังคม: การค้นหาชุดพารามิเตอร์การแทรกแซงที่ร่วมกันปรับปรุงความเท่าเทียมกันของรายได้และประสิทธิภาพของตลาดแรงงานในแบบจำลองเศรษฐกิจแบบหลายเอเจนต์
วิธีการทำงาน
วิธีการทำงาน
กำหนดตัวแปรการตัดสินใจ (พารามิเตอร์พฤติกรรมเอเจนต์ คันโยกเชิงนโยบาย การจัดสรรทรัพยากร) และแจกแจงวัตถุประสงค์ที่ขัดแย้งกันเพื่อหาค่าเหมาะสมที่สุด (เช่น ลดต้นทุนและเพิ่มอัตราการให้บริการ) สร้างหรือกำหนดพารามิเตอร์แบบจำลองการจำลองแบบหลายเอเจนต์ที่รับเวกเตอร์ตัวแปรการตัดสินใจและส่งคืนการวัดวัตถุประสงค์เมื่อสิ้นสุดการรันการจำลองแต่ละครั้ง ระบุข้อจำกัด ระยะเวลาการจำลอง และจำนวนการจำลองซ้ำแบบสุ่มต่อการประเมินแต่ละครั้ง
เริ่มต้นประชากรของเวกเตอร์คำตอบที่เป็นไปได้ N โดยการสุ่มตัวอย่างปริภูมิการตัดสินใจแบบสม่ำเสมอ หรือใช้การสุ่มตัวอย่างแบบ Latin hypercube แต่ละบุคคลแสดงถึงการกำหนดค่าพารามิเตอร์เอเจนต์หรือการตั้งค่านโยบาย กำหนดไฮเปอร์พารามิเตอร์ของ NSGA-II: ขนาดประชากร N ความน่าจะเป็นของการผสมข้าม (crossover) อัตราการกลายพันธุ์ (mutation) และจำนวนรุ่นสูงสุด
สำหรับแต่ละบุคคลในประชากรปัจจุบัน ให้รันการจำลองแบบหลายเอเจนต์ R ครั้ง (การจำลองซ้ำ) และหาค่าเฉลี่ยของค่าวัตถุประสงค์ที่ได้เพื่อลดสัญญาณรบกวนแบบสุ่ม บันทึกเวกเตอร์วัตถุประสงค์เฉลี่ยสำหรับแต่ละบุคคล ขั้นตอนนี้มีค่าใช้จ่ายในการคำนวณสูง: N บุคคล คูณ R การจำลองซ้ำ คูณ T ขั้นตอนเวลาจำลองต่อการประเมิน
ใช้การจัดอันดับแบบไม่ถูกครอบงำอย่างรวดเร็ว (fast non-dominated sorting) เพื่อจัดอันดับบุคคลทั้งหมดออกเป็นแนวหน้าพาเรโต F1, F2, ... แนวหน้า F1 ประกอบด้วยคำตอบที่ไม่ถูกครอบงำโดยคำตอบอื่นใด; F2 ประกอบด้วยคำตอบที่ถูกครอบงำโดยสมาชิก F1 เท่านั้น และต่อไปเรื่อยๆ ภายในแต่ละแนวหน้า ให้คำนวณระยะห่างของกลุ่ม (crowding distance) — ผลรวมของช่องว่างระหว่างเพื่อนบ้านที่ปรับขนาดแล้วตามแกนวัตถุประสงค์แต่ละแกน — เพื่อวัดปริมาณว่าแต่ละคำตอบอยู่ห่างจากคำตอบอื่นเพียงใด และรักษาความหลากหลายทั่วทั้งแนวหน้า
เลือกพ่อแม่ผ่านการแข่งขันแบบทวิภาคี (binary tournament) โดยใช้ตัวดำเนินการเปรียบเทียบแบบกลุ่ม (crowded-comparison operator): ให้ความสำคัญกับบุคคลในแนวหน้าที่มีหมายเลขต่ำกว่า โดยใช้ระยะห่างของกลุ่มที่มากกว่าในการตัดสินกรณีที่เท่ากัน ใช้การผสมข้ามแบบจำลองทวิภาคี (simulated binary crossover - SBX) และการกลายพันธุ์แบบพหุนาม (polynomial mutation) เพื่อสร้างลูกหลาน N ตัว รวมพ่อแม่และลูกหลานเข้าเป็นกลุ่ม 2N บุคคล จัดอันดับใหม่ และเก็บ N บุคคลที่ดีที่สุดไว้สำหรับรุ่นถัดไป โดยใช้ลำดับชั้นของแนวหน้าและระยะห่างของกลุ่มเป็นตัวตัดสิน
หลังจากถึงเกณฑ์การหยุด (งบประมาณรุ่นหมดลง หรือการบรรจบกันของ hypervolume ได้รับการยืนยัน) ให้ส่งคืนแนวหน้า F1 ของประชากรสุดท้ายเป็นชุดที่ประมาณค่าเหมาะสมที่สุดแบบพาเรโต แสดงภาพพื้นผิวการแลกเปลี่ยนในปริภูมิวัตถุประสงค์ และรายงาน hypervolume หรือ inverted generational distance (IGD) เป็นตัวชี้วัดคุณภาพที่รวบรวมจากการรันอิสระหลายครั้ง
ข้อผิดพลาดที่พบบ่อย
- การใช้จำนวนการจำลองซ้ำน้อยเกินไปต่อบุคคล (R = 1 หรือ 2) เมื่อการจำลองมีความไม่แน่นอน — การประมาณค่าความเหมาะสมที่มีสัญญาณรบกวนทำให้ขั้นตอนการจัดอันดับแบบครอบงำจำแนกคำตอบผิดพลาดและทำให้แนวหน้าพาเรโตเสียหาย
- การตั้งค่าขนาดประชากร N เล็กกว่าความซับซ้อนที่คาดหวังของแนวหน้าพาเรโต ซึ่งบังคับให้อัลกอริทึมต้องทิ้งภูมิภาคทั้งหมดของปริภูมิการแลกเปลี่ยนและส่งคืนแนวหน้าที่แตกเป็นเสี่ยงๆ
- การใช้วิธีการนี้กับวัตถุประสงค์สี่วัตถุประสงค์หรือมากกว่านั้นโดยไม่เปลี่ยนไปใช้ NSGA-III หรือ MOEA/D ทำให้บุคคลส่วนใหญ่กระจุกตัวอยู่ในแนวหน้า F1 และทำให้การเลือกเกือบจะเป็นแบบสุ่ม
- การผสมผสานการปรับเทียบแบบจำลองเอเจนต์และการหาค่าเหมาะสมที่สุด: แบบจำลองการจำลองต้องได้รับการปรับเทียบกับข้อมูลที่สังเกตได้ก่อนเริ่มการหาค่าเหมาะสมที่สุด — การหาค่าเหมาะสมที่สุดของแบบจำลองที่ไม่ได้ปรับเทียบจะให้แนวหน้าพาเรโตที่ไม่มีความถูกต้องในโลกแห่งความเป็นจริง
- การละเลยการคำนวณแบบขนาน: เนื่องจากแต่ละการรันการจำลองเป็นอิสระต่อกัน Agent-based NSGA-II จึงสามารถขนานกันได้อย่างง่ายดาย การรันแบบเธรดเดียวจะทำให้ฮาร์ดแวร์ที่มีอยู่สูญเปล่าและทำให้เวลารันนานเกินความจำเป็น
คำถามที่พบบ่อย
Agent-based NSGA-II แตกต่างจาก NSGA-II แบบธรรมดาอย่างไร?
NSGA-II แบบธรรมดาประเมินแต่ละคำตอบโดยการเรียกใช้ฟังก์ชันเชิงวิเคราะห์ ซึ่งรวดเร็ว Agent-based NSGA-II แทนที่การเรียกใช้ฟังก์ชันนั้นด้วยการรันการจำลองแบบหลายเอเจนต์เต็มรูปแบบ ทำให้สามารถหาค่าเหมาะสมที่สุดสำหรับวัตถุประสงค์ที่เกิดขึ้นเองและขึ้นอยู่กับเส้นทางได้ แต่มีค่าใช้จ่ายในการคำนวณต่อการประเมินสูงขึ้นอย่างมาก
ฉันควรทำการจำลองซ้ำกี่ครั้งต่อการประเมินแต่ละบุคคล?
เพียงพอที่สัมประสิทธิ์ความแปรปรวน (coefficient of variation) ของแต่ละวัตถุประสงค์จากการจำลองซ้ำจะลดลงต่ำกว่าประมาณ 5-10% เริ่มต้นด้วย R = 10 และเพิ่มขึ้นจนกว่าค่าประมาณวัตถุประสงค์จะคงที่ สำหรับแบบจำลองที่มีความไม่แน่นอนสูง อาจต้องใช้ R = 30 ถึง 50 ซึ่งจะคูณค่าใช้จ่ายตามไปด้วย
ฉันจะทำให้ Agent-based NSGA-II สามารถคำนวณได้จริงได้อย่างไร?
ทำการคำนวณแบบขนานผ่านคอร์ CPU หรือคลัสเตอร์ — การรันการจำลองของแต่ละบุคคลเป็นอิสระต่อกันและสามารถขนานกันได้อย่างง่ายดาย ใช้แบบจำลองตัวแทน (surrogate models) (เช่น Gaussian processes หรือ neural networks) เพื่อประมาณค่าความเหมาะสมสำหรับการคัดกรองเบื้องต้นอย่างรวดเร็ว โดยสงวนการประเมินการจำลองเต็มรูปแบบไว้สำหรับผู้ที่น่าสนใจ
จะเกิดอะไรขึ้นหากฉันมีวัตถุประสงค์สี่วัตถุประสงค์หรือมากกว่านั้น?
เปลี่ยนไปใช้ NSGA-III หรือ MOEA/D ในรูปแบบ Agent-based NSGA-III ใช้การเลือกตามจุดอ้างอิง (reference-point-based selection) แทนระยะห่างของกลุ่ม ซึ่งรักษาความหลากหลายได้อย่างมีประสิทธิภาพในวัตถุประสงค์สี่วัตถุประสงค์หรือมากกว่านั้น MOEA/D แยกปัญหาย่อยออกเป็นปัญหาย่อยแบบสเกลาร์ (scalar subproblems) และปรับขนาดได้ดีกับสถานการณ์ที่มีวัตถุประสงค์จำนวนมาก
ฉันจะตรวจสอบได้อย่างไรว่าแนวหน้าพาเรโตน่าเชื่อถือ?
ทำการรันการหาค่าเหมาะสมที่สุดอิสระอย่างน้อย 10 ครั้ง ด้วยเมล็ดสุ่ม (random seeds) ที่แตกต่างกัน และคำนวณ hypervolume หรือ IGD สำหรับแต่ละครั้ง รายงานค่ามัธยฐานและช่วงควอร์ไทล์ระหว่างการรัน การบรรจบกันของ 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คัดลอกแล้วMacal, C. M., & North, M. J. (2010). Tutorial on agent-based modelling and simulation. Journal of Simulation, 4(3), 151-162.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว