Multi-Objective Genetic Algorithm (MOGA) — การค้นหาเชิงวิวัฒนาการสำหรับผลเฉลยแบบ Pareto-Optimal
- ผู้เสนอ
- Schaffer, J. D. (early MOGA); Goldberg, D. E. (GA foundations)
- ปี
- 1984
- ประเภท
- Population-based evolutionary optimizer
- กลุ่มวิธี
- Simulation / optimization
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
Multi-Objective Genetic Algorithm (MOGA) เป็นวิธีการคำนวณเชิงวิวัฒนาการที่พัฒนาประชากรของผลเฉลยที่เป็นไปได้ไปสู่แนว Pareto-optimal โดยปรับปรุงฟังก์ชันวัตถุประสงค์ที่ขัดแย้งกันสองฟังก์ชันขึ้นไปพร้อมกัน วิธีนี้หลีกเลี่ยงการรวมการแลกเปลี่ยนให้เป็นคะแนนเดียว แต่จะสร้างชุดของผลเฉลยที่ไม่ถูกครอบงำเพื่อให้ผู้ตัดสินใจเลือก
แนวคิดเบื้องหลังวิธีการ
ลองจินตนาการถึงการเพาะพันธุ์รุ่นต่อ ๆ ไปของแบบร่างที่เป็นไปได้ โดยมีเพียงผลเฉลยที่ไม่ถูกเอาชนะอย่างชัดเจนในทุกวัตถุประสงค์เท่านั้นที่อยู่รอดและสืบพันธุ์ได้ ตลอดหลายชั่วอายุคน ประชากรจะลู่เข้าสู่แนวหน้าของการแลกเปลี่ยนที่ดีที่สุดที่เป็นไปได้ — ไม่มีผลเฉลยใด ๆ บนแนว Pareto นี้ที่สามารถปรับปรุงวัตถุประสงค์หนึ่งได้โดยไม่ทำให้วัตถุประสงค์อื่นแย่ลง MOGA ใช้การดำเนินการทางพันธุกรรม — การเลือก การผสมข้าม และการกลายพันธุ์ — เพื่อสำรวจแนวหน้านี้อย่างมีประสิทธิภาพ แม้ในพื้นที่การค้นหาที่มีมิติสูง ไม่เป็นนูน หรือไม่ต่อเนื่อง ซึ่งวิธีการไล่ระดับแบบคลาสสิกไม่สามารถทำได้
ประวัติศาสตร์
อัลกอริทึมพันธุกรรมหลายวัตถุประสงค์เกิดขึ้นจาก Vector Evaluated Genetic Algorithm (VEGA) ของ Schaffer ในปี 1984 ซึ่งเป็น GA แรกที่จัดการวัตถุประสงค์หลายอย่างอย่างชัดเจน หนังสือของ Goldberg ในปี 1989 ได้กำหนดการจัดอันดับตาม Pareto เป็นกลยุทธ์การกำหนดความเหมาะสมที่เป็นหลักการ สาขาวิชานี้เติบโตอย่างรวดเร็วด้วย MOGA ของ Fonseca และ Fleming (1993), NSGA ของ Srinivas และ Deb (1994) และ NSGA-II ที่เป็นจุดเปลี่ยน (Deb et al., 2002) ซึ่งกลายเป็นมาตรฐานการเปรียบเทียบของสาขาวิชาและยังคงเป็นอัลกอริทึมวิวัฒนาการหลายวัตถุประสงค์ที่ได้รับการอ้างอิงอย่างกว้างขวางที่สุด
ควรใช้เมื่อใด
ใช้ MOGA เมื่อปัญหามีวัตถุประสงค์ที่ขัดแย้งกันตั้งแต่สองข้อขึ้นไปและไม่มีผลเฉลยที่เหมาะสมที่สุดเพียงข้อเดียว — การออกแบบทางวิศวกรรม การกำหนดค่าห่วงโซ่อุปทาน การปรับปรุงพอร์ตการลงทุน และการวางแผนสิ่งแวดล้อมเป็นโดเมนทั่วไป เหมาะสำหรับภูมิทัศน์วัตถุประสงค์ที่ไม่เป็นนูน หลายรูปแบบ หรือแบบกล่องดำ ซึ่งไม่สามารถใช้วิธีการที่อิงตามการไล่ระดับได้ ห้ามใช้เมื่อวัตถุประสงค์เดียวที่กำหนดไว้อย่างดีเพียงพอ (ให้ใช้ GA มาตรฐานหรือการเขียนโปรแกรมเชิงคณิตศาสตร์แทน) เมื่อการประเมินประชากรมีค่าใช้จ่ายในการคำนวณสูงเกินไปและไม่มีตัวแทน เมื่อวัตถุประสงค์สามารถรวมกันได้อย่างถูกต้องด้วยผลรวมถ่วงน้ำหนักที่ทราบโดยไม่สูญเสียข้อมูล หรือเมื่อชุดที่เป็นไปได้ขนาดเล็กอนุญาตให้มีการแจงนับอย่างละเอียด
ข้อจำกัดและข้อควรพิจารณา
- ค่าใช้จ่ายในการคำนวณจะเพิ่มขึ้นตามขนาดประชากรและจำนวนการประเมินฟังก์ชัน; การประเมินการจำลองที่ซับซ้อนแต่ละครั้งอาจมีค่าใช้จ่ายสูง
- การลู่เข้าสู่แนว Pareto ที่แท้จริงไม่ได้รับการรับประกัน — ผลลัพธ์เป็นการประมาณแบบฮิวริสติกที่อ่อนไหวต่อการเลือกไฮเปอร์พารามิเตอร์ (ขนาดประชากร, อัตราการผสมข้าม, อัตราการกลายพันธุ์)
- ประสิทธิภาพลดลงเมื่อจำนวนวัตถุประสงค์เพิ่มขึ้นเกินสามหรือสี่ (การปรับปรุงหลายวัตถุประสงค์ต้องใช้อัลกอริทึมเฉพาะทาง เช่น NSGA-III หรือ MOEA/D)
- ต้องมีการปรับแต่งตัวดำเนินการทางพันธุกรรมและการรักษาความหลากหลายอย่างระมัดระวังเพื่อหลีกเลี่ยงการลู่เข้าก่อนกำหนดหรือการครอบคลุมแนวหน้าไม่ดี
- ไม่ได้ให้ผลเฉลยที่แนะนำเพียงข้อเดียว — การเลือกขั้นสุดท้ายจากแนว Pareto ยังคงต้องใช้การตัดสินคุณค่าหรือกฎการตัดสินใจรอง
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- สร้างชุดของผลเฉลย Pareto-optimal ที่หลากหลายในการรันครั้งเดียว ทำให้ผู้ตัดสินใจมีทางเลือกในการแลกเปลี่ยนที่ชัดเจน แทนที่จะเป็นคำตอบเดียว
- ทำงานบนภูมิทัศน์วัตถุประสงค์ที่ไม่เป็นนูน ไม่ต่อเนื่อง และหลายรูปแบบ โดยไม่จำเป็นต้องใช้การไล่ระดับหรือโครงสร้างทางคณิตศาสตร์ที่เฉพาะเจาะจงกับปัญหา
- อิงตามประชากรโดยธรรมชาติ ทำให้ง่ายต่อการประมวลผลแบบขนานในคอร์หรือระบบแบบกระจาย
- การเข้ารหัสที่ยืดหยุ่นช่วยให้สามารถใช้ตัวแปรต่อเนื่อง จำนวนเต็ม สตริงไบนารี และการเรียงสับเปลี่ยนภายในกรอบเดียวกันได้
- ได้รับการสนับสนุนอย่างดีจากไลบรารีซอฟต์แวร์ที่สมบูรณ์ (DEAP, pymoo, jMetal) และหลักฐานการเปรียบเทียบตลอดหลายทศวรรษ
การประยุกต์ใช้
- การปรับปรุงการออกแบบทางวิศวกรรม — ลดน้ำหนัก ต้นทุน และความเค้นในส่วนประกอบโครงสร้างพร้อมกัน
- ห่วงโซ่อุปทานและโลจิสติกส์ — สร้างสมดุลระหว่างต้นทุน ระยะเวลารอคอยสินค้า และการปล่อยคาร์บอนในการกำหนดค่าเครือข่าย
- นโยบายสิ่งแวดล้อมและพลังงาน — ปรับปรุงพอร์ตการลงทุนพลังงานหมุนเวียนเพื่อต้นทุน ความน่าเชื่อถือ และการปล่อยมลพิษ
- การออกแบบกระบวนการทางเภสัชกรรมและเคมี — เพิ่มผลผลิตและความบริสุทธิ์สูงสุดในขณะที่ลดเวลาปฏิกิริยา
- การปรับแต่งไฮเปอร์พารามิเตอร์การเรียนรู้ของเครื่อง — แลกเปลี่ยนความแม่นยำของโมเดลกับเวลาการฝึกอบรมหรือความสามารถในการตีความ
- การวางผังเมืองและการขนส่ง — ปรับปรุงเครือข่ายเส้นทางเพื่อการครอบคลุม เวลาเดินทาง และต้นทุนโครงสร้างพื้นฐาน
วิธีการทำงาน
วิธีการทำงาน
สร้างประชากรเริ่มต้นของผลเฉลยที่เป็นไปได้ N ตัว (โครโมโซม) แบบสุ่มหรือใช้ฮิวริสติกส์ของโดเมน โดยเข้ารหัสแต่ละผลเฉลยเป็นเวกเตอร์ของตัวแปรการตัดสินใจ กำหนดฟังก์ชันวัตถุประสงค์ k ฟังก์ชัน f1(x), f2(x), ..., fk(x) ที่จะถูกทำให้มีค่าน้อยที่สุดหรือมากที่สุดพร้อมกัน
ประเมินฟังก์ชันวัตถุประสงค์ทั้ง k ฟังก์ชันสำหรับแต่ละบุคคลในประชากร ความเหมาะสมสะท้อนทั้งคุณภาพของผลเฉลยในทุกวัตถุประสงค์และความหลากหลายของการครอบคลุมในพื้นที่วัตถุประสงค์
จัดอันดับบุคคลตามการไม่ถูกครอบงำ: ผลเฉลย x ครอบงำ y หากดีกว่าอย่างน้อยเท่ากันในทุกวัตถุประสงค์และดีกว่าอย่างเคร่งครัดในอย่างน้อยหนึ่งวัตถุประสงค์ ระบุแนวที่ไม่ถูกครอบงำ (ผู้สมัครแนว Pareto) และกำหนดลำดับความสำคัญในการเลือกที่สูงขึ้นให้กับบุคคลที่ถูกครอบงำน้อยกว่า เมตริกความหลากหลาย เช่น ระยะห่างความแออัด (crowding distance) ป้องกันการรวมกลุ่มในพื้นที่แคบของแนวหน้า
ใช้การเลือก (เช่น การเลือกแบบทัวร์นาเมนต์) เพื่อสนับสนุนบุคคลที่ได้รับการจัดอันดับสูงกว่า จากนั้นใช้การผสมข้ามเพื่อรวมคู่ของพ่อแม่และการกลายพันธุ์เพื่อสร้างความหลากหลาย กลไกชนชั้นสูง (Elitism) จะรักษาผลเฉลยที่ไม่ถูกครอบงำที่ดีที่สุดที่พบในแต่ละรุ่น
ทำซ้ำการประเมินความเหมาะสม การจัดอันดับ และการสืบพันธุ์ตามจำนวนรุ่นที่กำหนดไว้ล่วงหน้า หรือจนกว่าจะตรงตามเกณฑ์การลู่เข้า ชุดที่ไม่ถูกครอบงำสุดท้ายจะประมาณแนว Pareto-optimal ซึ่งนำเสนอทางเลือกผลเฉลยการแลกเปลี่ยนที่เหมาะสมที่สุดแก่ผู้ตัดสินใจ
ข้อผิดพลาดที่พบบ่อย
- การถือว่าผลเฉลยทั้งหมดบนแนว Pareto มีความถูกต้องเท่าเทียมกันโดยไม่ให้ผู้เชี่ยวชาญในโดเมนเข้ามามีส่วนร่วมในการเลือกการแลกเปลี่ยนขั้นสุดท้าย อาจนำไปสู่การเลือกที่ตามอำเภอใจหรือไม่สมเหตุสมผล
- การใช้ประชากรที่เล็กเกินไปจะสร้างแนวหน้าที่กระจัดกระจายและไม่เป็นตัวแทน; ประชากรที่ใหญ่เกินไปจะเพิ่มการคำนวณโดยไม่มีประโยชน์ตามสัดส่วน
- การละเลยการจัดการข้อจำกัด — ผลเฉลยที่เป็นไปไม่ได้จะต้องถูกลงโทษหรือแก้ไขอย่างชัดเจน; การไม่ทำเช่นนั้นจะบิดเบือนการค้นหาไปสู่พื้นที่ที่ไม่สามารถทำได้
- การใช้ MOGA กับปัญหาที่มีวัตถุประสงค์มากกว่าสี่ข้อโดยไม่เปลี่ยนไปใช้อัลกอริทึมหลายวัตถุประสงค์จะให้แนวหน้าที่รกและไม่ให้ข้อมูล ซึ่งเกือบทุกผลเฉลยไม่ถูกครอบงำ
- การรายงานเฉพาะแนว Pareto สุดท้ายโดยไม่มีการวินิจฉัยการลู่เข้า (ปริมาตรไฮเปอร์วอลุ่มข้ามรุ่น) ทำให้ไม่สามารถประเมินได้ว่าอัลกอริทึมได้ลู่เข้าจริงหรือไม่
คำถามที่พบบ่อย
MOGA แตกต่างจากการรัน GA แบบวัตถุประสงค์เดียวด้วยผลรวมถ่วงน้ำหนักของวัตถุประสงค์อย่างไร?
วิธีการผลรวมถ่วงน้ำหนักจะรวมวัตถุประสงค์ทั้งหมดเข้าเป็นค่าสเกลาร์เดียวโดยใช้น้ำหนักที่กำหนดไว้ล่วงหน้า ซึ่งสร้างผลเฉลยเดียวที่ขึ้นอยู่กับน้ำหนักเหล่านั้น MOGA จะสร้างแนวหน้าของผลเฉลยที่ไม่ถูกครอบงำทั้งหมดพร้อมกันโดยไม่จำเป็นต้องระบุน้ำหนักล่วงหน้า ทำให้ผู้ตัดสินใจสามารถตรวจสอบการแลกเปลี่ยนและเลือกได้ในภายหลัง
แนว Pareto คืออะไร และทำไมจึงสำคัญ?
แนว Pareto คือชุดของผลเฉลยที่การปรับปรุงวัตถุประสงค์เดียวใด ๆ จำเป็นต้องทำให้วัตถุประสงค์อื่นอย่างน้อยหนึ่งวัตถุประสงค์แย่ลง ซึ่งแสดงถึงภาพรวมที่สมบูรณ์ของการแลกเปลี่ยนที่ทำได้ ผู้ตัดสินใจสามารถตรวจสอบแนวหน้านี้เพื่อทำความเข้าใจว่าต้องเสียสละวัตถุประสงค์หนึ่งไปมากน้อยเพียงใดเพื่อที่จะได้ประโยชน์จากวัตถุประสงค์อื่น
MOGA สามารถจัดการกับวัตถุประสงค์ได้กี่ข้ออย่างมีประสิทธิภาพ?
MOGA รุ่นมาตรฐาน เช่น NSGA-II ทำงานได้ดีสำหรับวัตถุประสงค์สองหรือสามข้อ เมื่อเกินสี่วัตถุประสงค์ สัดส่วนของผลเฉลยที่ไม่ถูกครอบงำจะเพิ่มขึ้นอย่างรวดเร็ว (ปัญหาของมิติในพื้นที่วัตถุประสงค์) ทำให้แนว Pareto มีขนาดใหญ่และแรงกดดันในการเลือกอ่อนแอ อัลกอริทึมหลายวัตถุประสงค์ (NSGA-III, MOEA/D, IBEA) แนะนำสำหรับวัตถุประสงค์สี่ข้อขึ้นไป
ฉันควรใช้เกณฑ์การหยุดแบบใด?
เกณฑ์ทั่วไปได้แก่ จำนวนการประเมินฟังก์ชันที่กำหนดไว้ล่วงหน้า จำนวนรุ่นสูงสุด หรือการลู่เข้าของตัวบ่งชี้ไฮเปอร์วอลุ่ม — ปริมาตรของพื้นที่วัตถุประสงค์ที่ถูกครอบงำโดยการประมาณแนว Pareto ปัจจุบัน — ในแต่ละรุ่น การตรวจสอบการเติบโตของไฮเปอร์วอลุ่มเป็นแนวทางที่มีหลักการมากที่สุด
MOGA สามารถจัดการกับข้อจำกัดได้หรือไม่?
ได้ โดยใช้เทคนิคการจัดการข้อจำกัด: ฟังก์ชันบทลงโทษที่ลดความเหมาะสมของผลเฉลยที่เป็นไปไม่ได้, การเลือกแบบทัวร์นาเมนต์ที่สามารถทำได้ (ผลเฉลยที่ทำได้จะชนะผลเฉลยที่ทำไม่ได้เสมอในการเลือก) หรือตัวดำเนินการซ่อมแซมที่ฉายผลเฉลยที่ไม่สามารถทำได้กลับเข้าสู่พื้นที่ที่สามารถทำได้ การเลือกมีผลต่อพฤติกรรมการลู่เข้าและต้องเป็นไปโดยเจตนา
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Addison-Wesley.
ISBN: 9780201157673คัดลอกแล้ว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คัดลอกแล้ว