อัลกอริทึมทางพันธุกรรม - การเลือกผู้ปกครอง

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

อย่างไรก็ตามควรใช้ความระมัดระวังเพื่อป้องกันไม่ให้โซลูชันที่เหมาะสมอย่างยิ่งอย่างหนึ่งเข้าครอบงำประชากรทั้งหมดในไม่กี่ชั่วอายุคนเนื่องจากสิ่งนี้นำไปสู่การแก้ปัญหาที่อยู่ใกล้กันในพื้นที่โซลูชันจึงนำไปสู่การสูญเสียความหลากหลาย Maintaining good diversityในประชากรมีความสำคัญอย่างยิ่งต่อความสำเร็จของ GA การรับประชากรทั้งหมดด้วยวิธีแก้ปัญหาที่เหมาะสมอย่างยิ่งนี้เรียกว่าpremature convergence และเป็นเงื่อนไขที่ไม่พึงปรารถนาใน GA

การเลือกสัดส่วนการออกกำลังกาย

Fitness Proportionate Selection เป็นวิธีการเลือกผู้ปกครองที่ได้รับความนิยมมากที่สุดวิธีหนึ่ง ในสิ่งนี้ทุกคนสามารถเป็นพ่อแม่ได้ด้วยความน่าจะเป็นซึ่งเป็นสัดส่วนกับความฟิตของตน ดังนั้นช่างฟิตจึงมีโอกาสที่จะผสมพันธุ์และขยายพันธุ์ไปยังรุ่นต่อไปได้ ดังนั้นกลยุทธ์การคัดเลือกดังกล่าวจึงใช้แรงกดดันในการเลือกกับบุคคลที่เหมาะสมกับประชากรมากขึ้นซึ่งจะพัฒนาบุคคลที่ดีขึ้นเมื่อเวลาผ่านไป

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

สามารถใช้การเลือกสัดส่วนการออกกำลังกายได้สองแบบ -

การเลือกวงล้อรูเล็ต

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

เป็นที่ชัดเจนว่าช่างฟิตแต่ละคนมีวงล้อที่มากขึ้นดังนั้นจึงมีโอกาสมากขึ้นที่จะลงจอดที่หน้าจุดคงที่เมื่อล้อหมุน ดังนั้นความน่าจะเป็นในการเลือกแต่ละบุคคลจึงขึ้นอยู่กับความเหมาะสมโดยตรง

การนำไปใช้อย่างชาญฉลาดเราใช้ขั้นตอนต่อไปนี้ -

• คำนวณ S = ผลรวมของ finesses

• สร้างตัวเลขสุ่มระหว่าง 0 ถึง S

• เริ่มจากด้านบนสุดของประชากรให้เพิ่ม finesses ไปยังผลรวม P บางส่วนจนถึง P <S

• บุคคลที่ P เกิน S คือบุคคลที่ถูกเลือก

Stochastic Universal Sampling (SUS)

Stochastic Universal Sampling ค่อนข้างคล้ายกับการเลือกวงล้อรูเล็ต แต่แทนที่จะมีจุดคงที่เพียงจุดเดียวเรามีจุดคงที่หลายจุดดังที่แสดงในภาพต่อไปนี้ ดังนั้นผู้ปกครองทุกคนจะได้รับการคัดเลือกในการหมุนวงล้อเพียงครั้งเดียว นอกจากนี้การตั้งค่าดังกล่าวสนับสนุนให้บุคคลที่มีรูปร่างเหมาะสมสูงได้รับเลือกอย่างน้อยหนึ่งครั้ง

เป็นที่น่าสังเกตว่าวิธีการเลือกสัดส่วนการออกกำลังกายไม่ได้ผลในกรณีที่ฟิตเนสสามารถรับค่าลบได้

การเลือกทัวร์นาเมนต์

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

การเลือกอันดับ

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

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

โครโมโซม	ค่าฟิตเนส	อันดับ
ก	8.1	1
ข	8.0	4
ค	8.05	2
ง	7.95	6
จ	8.02	3
ฉ	7.99	5

การเลือกแบบสุ่ม

ในกลยุทธ์นี้เราสุ่มเลือกผู้ปกครองจากประชากรที่มีอยู่ ไม่มีแรงกดดันในการคัดเลือกต่อบุคคลช่างฟิตดังนั้นจึงมักหลีกเลี่ยงกลยุทธ์นี้