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

อัลกอริทึมพันธุกรรมที่แข็งแกร่ง — การหาค่าเหมาะที่สุดเชิงวิวัฒนาการภายใต้ความไม่แน่นอน

ผู้เสนอ
Jin, Y. and Branke, J. (systematic formalization); roots in Holland (1975)
ปี
2005 (systematic survey); earlier applications from late 1990s
ประเภท
Metaheuristic evolutionary optimizer with robustness mechanism
กลุ่มวิธี
Simulation / optimization

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

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

ใช้ทำอะไร?

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

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

อัลกอริทึมพันธุกรรมแบบคลาสสิกค้นหาคำตอบที่ดีที่สุด แต่ 'ดีที่สุด' ภายใต้เงื่อนไขในอุดมคติอาจเปราะบางในทางปฏิบัติ — การเปลี่ยนแปลงเล็กน้อยในอินพุตสามารถทำให้ประสิทธิภาพลดลง Robust GA จะถามคำถามที่แตกต่างออกไป: คำตอบใดที่ยังคงดีพอสมควรในช่วงของการรบกวนที่คาดหวัง? มันทำเช่นนี้โดยการสุ่มตัวอย่างละแวกใกล้เคียงของผู้สมัครแต่ละรายระหว่างการประเมินค่าความเหมาะสม และให้รางวัลแก่ผู้สมัครที่ประสิทธิภาพลดลงอย่างค่อยเป็นค่อยไป แทนที่จะลดลงอย่างรุนแรง ผลลัพธ์คือประชากรที่ถูกพัฒนาขึ้นซึ่งไม่ใช่แค่ดีที่สุดเท่านั้น แต่ยังใกล้เคียงกับดีที่สุดอย่างน่าเชื่อถือภายใต้เงื่อนไขการปฏิบัติงานที่สมจริง

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

การหาค่าเหมาะที่สุดที่แข็งแกร่งในวิวัฒนาการเชิงคำนวณเกิดขึ้นในช่วงปลายทศวรรษ 1990 โดยได้รับแรงผลักดันจากปัญหาการออกแบบทางวิศวกรรมที่ความคลาดเคลื่อนในการผลิตทำให้การออกแบบที่เหมาะสมตามชื่อไม่น่าเชื่อถือ การสำรวจของ Jin และ Branke ในปี 2005 ของ IEEE ได้จัดระบบสาขานี้ โดยแยกประเภทของความไม่แน่นอนและมาตรวัดความแข็งแกร่ง การทบทวนที่ครอบคลุมของ Beyer และ Sendhoff ในปี 2007 ได้สร้างรากฐานทางทฤษฎีที่เชื่อมโยง EA ที่แข็งแกร่งกับการหาค่าเหมาะที่สุดที่แข็งแกร่งแบบคลาสสิก ทำให้ Robust GA กลายเป็นสาขาย่อยที่ได้รับการยอมรับของการคำนวณเชิงวิวัฒนาการ

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

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

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

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

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

จุดแข็ง

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

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

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

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

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

1

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

2

เลือกและกำหนดสูตรมาตรวัดความแข็งแกร่งสำหรับคำตอบผู้สมัครแต่ละราย x ตัวเลือกทั่วไป ได้แก่: (1) ค่าความเหมาะสมที่คาดหวังจากการกระจายการรบกวน E[f(x+δ)]; (2) การรวมกันแบบถ่วงน้ำหนักของค่าเฉลี่ยและความแปรปรวน E[f] + λ·Var[f]; หรือ (3) ค่าความเหมาะสมกรณีที่เลวร้ายที่สุด min ในชุดความไม่แน่นอนที่มีขอบเขต มาตรวัดนี้จะแทนที่หรือเสริมฟังก์ชันความเหมาะสมตามชื่อ

3

เริ่มต้นประชากรของผู้สมัคร N คนโดยใช้วิธีการเริ่มต้น GA มาตรฐาน (แบบสุ่ม, Latin hypercube, หรือฮิวริสติกเฉพาะโดเมน) ตรวจสอบให้แน่ใจว่าประชากรมีความหลากหลายเพื่อสนับสนุนการสำรวจขอบเขต Pareto ที่แข็งแกร่ง โดยเฉพาะอย่างยิ่งเมื่อความแข็งแกร่งและความเหมาะสมตามชื่อเป็นวัตถุประสงค์ที่แข่งขันกัน

4

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

5

ใช้ตัวดำเนินการคัดเลือก (tournament, rank-based, หรือ fitness-proportionate), crossover และ mutation เช่นเดียวกับใน GA มาตรฐาน เนื่องจากความแข็งแกร่งอาจขัดแย้งกับความเป็นเลิศ การกำหนดสูตรแบบหลายวัตถุประสงค์ (เช่น การพิจารณาค่าเฉลี่ยประสิทธิภาพและความแปรปรวนของประสิทธิภาพเป็นวัตถุประสงค์แยกต่างหากด้วย NSGA-II) เป็นเรื่องปกติ Niching หรือ fitness sharing สามารถรักษาความหลากหลายตลอดแนวการแลกเปลี่ยนระหว่างความแข็งแกร่งและประสิทธิภาพสูงสุด

6

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

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

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

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

Robust GA แตกต่างจากอัลกอริทึมพันธุกรรมมาตรฐานอย่างไร

GA มาตรฐานจะประเมินค่าความเหมาะสมของผู้สมัครแต่ละรายที่จุดออกแบบตามชื่อ Robust GA จะประเมินค่าความเหมาะสมโดยการสุ่มตัวอย่างในละแวกใกล้เคียงของการรบกวนรอบๆ ผู้สมัครแต่ละราย ดังนั้นแรงกดดันในการคัดเลือกจะให้รางวัลแก่โซลูชันที่ทำงานได้ดีโดยเฉลี่ย (หรือในกรณีที่เลวร้ายที่สุด) แทนที่จะเป็นเพียงจุดเดียว สิ่งนี้เปลี่ยนความหมายของ 'ดีกว่า' ในระหว่างการวิวัฒนาการ

โดยทั่วไปต้องใช้ตัวอย่างการรบกวนกี่ตัวต่อบุคคล

จำนวนที่ต้องการขึ้นอยู่กับระดับสัญญาณรบกวนและความแม่นยำที่จำเป็นสำหรับการประมาณค่าความแข็งแกร่ง ในทางปฏิบัติ 10–50 ตัวอย่างต่อบุคคลต่อรุ่นเป็นเรื่องปกติสำหรับปัญหาที่มีสัญญาณรบกวนปานกลาง สำหรับการประเมินค่าที่แพงมาก จะใช้แบบจำลองตัวแทนหรือการขยายตัวของโพลีโนเมียลเพื่อลดการเรียกใช้การจำลองโดยตรงในขณะที่ยังคงรักษาความเที่ยงตรงทางสถิติ

Robust GA สามารถรวมกับการหาค่าเหมาะที่สุดแบบหลายวัตถุประสงค์ได้หรือไม่

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

อะไรคือสิ่งที่ทำให้ความแข็งแกร่งที่อิงตามค่าคาดหวังแตกต่างจากความแข็งแกร่งกรณีที่เลวร้ายที่สุดใน RGA

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

Robust GA เหมาะสมหรือไม่เมื่อการกระจายความไม่แน่นอนไม่เป็นที่รู้จัก

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

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

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

  1. Jin, Y., Branke, J. (2005). Evolutionary optimization in uncertain environments — a survey. IEEE Transactions on Evolutionary Computation, 9(3), 303–317.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Beyer, H.-G., Sendhoff, B. (2007). Robust optimization — A comprehensive survey. Computer Methods in Applied Mechanics and Engineering, 196(33–34), 3190–3218.

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