อัลกอริทึมทางพันธุกรรม - ครอสโอเวอร์
ในบทนี้เราจะพูดถึงสิ่งที่ Crossover Operator พร้อมกับโมดูลอื่น ๆ การใช้งานและประโยชน์ของพวกเขา
ข้อมูลเบื้องต้นเกี่ยวกับ Crossover
ตัวดำเนินการครอสโอเวอร์นั้นคล้ายคลึงกับการสืบพันธุ์และการผสมข้ามทางชีวภาพ ในนี้มีการเลือกพ่อแม่มากกว่าหนึ่งตัวและมีการผลิตนอกสปริงอย่างน้อยหนึ่งตัวโดยใช้สารพันธุกรรมของพ่อแม่ โดยทั่วไปจะใช้การครอสโอเวอร์ใน GA ที่มีความเป็นไปได้สูง -pc .
ตัวดำเนินการครอสโอเวอร์
ในส่วนนี้เราจะพูดถึงตัวดำเนินการครอสโอเวอร์ที่นิยมใช้กันมากที่สุด เป็นที่น่าสังเกตว่าตัวดำเนินการครอสโอเวอร์เหล่านี้มีลักษณะทั่วไปมากและ GA Designer อาจเลือกใช้ตัวดำเนินการครอสโอเวอร์เฉพาะปัญหาเช่นกัน
One Point Crossover
ในครอสโอเวอร์แบบจุดเดียวนี้จะมีการเลือกจุดครอสโอเวอร์แบบสุ่มและหางของพ่อแม่ทั้งสองจะถูกสลับกันเพื่อให้ได้สปริงใหม่
Multi Point Crossover
ครอสโอเวอร์แบบหลายจุดเป็นลักษณะทั่วไปของครอสโอเวอร์แบบจุดเดียวซึ่งจะมีการสลับส่วนสลับกันเพื่อให้ได้สปริงใหม่
ครอสโอเวอร์เครื่องแบบ
ในการไขว้แบบสม่ำเสมอเราจะไม่แบ่งโครโมโซมออกเป็นส่วน ๆ แต่เราปฏิบัติต่อยีนแต่ละยีนแยกกัน ในการนี้เราจะพลิกเหรียญสำหรับโครโมโซมแต่ละอันเพื่อตัดสินใจว่าจะรวมอยู่ในสปริงหรือไม่ นอกจากนี้เรายังสามารถทำให้เหรียญมีอคติกับพ่อหรือแม่คนใดคนหนึ่งเพื่อให้มีสารพันธุกรรมในตัวเด็กมากขึ้นจากพ่อแม่นั้น
การรวมเลขคณิตทั้งหมด
สิ่งนี้มักใช้สำหรับการแทนค่าจำนวนเต็มและทำงานโดยการหาค่าเฉลี่ยถ่วงน้ำหนักของผู้ปกครองทั้งสองโดยใช้สูตรต่อไปนี้ -
- เด็ก 1 = α.x + (1-α) .y
- เด็ก 2 = α.x + (1-α) .y
เห็นได้ชัดว่าถ้าα = 0.5 ลูกทั้งสองจะเหมือนกันดังที่แสดงในภาพต่อไปนี้
Davis 'Order Crossover (OX1)
OX1 ใช้สำหรับการไขว้แบบเรียงสับเปลี่ยนโดยมีจุดประสงค์เพื่อส่งข้อมูลเกี่ยวกับการสั่งซื้อที่สัมพันธ์กับสปริง มันทำงานดังนี้ -
สร้างจุดครอสโอเวอร์แบบสุ่มสองจุดในพาเรนต์และคัดลอกเซ็กเมนต์ระหว่างจุดเริ่มต้นไปยังลูกแรก
ตอนนี้เริ่มจากจุดครอสโอเวอร์ที่สองในพาเรนต์ที่สองคัดลอกตัวเลขที่ยังไม่ได้ใช้ที่เหลือจากพาเรนต์ที่สองไปยังลูกคนแรกโดยตัดรอบรายการ
ทำซ้ำสำหรับลูกคนที่สองโดยเปลี่ยนบทบาทของผู้ปกครอง
มีครอสโอเวอร์อื่น ๆ อีกมากมายเช่น Partially Mapped Crossover (PMX), ครอสโอเวอร์ตามลำดับ (OX2), ครอสโอเวอร์แบบสุ่ม, Ring Crossover เป็นต้น