อัลกอริทึมทางพันธุกรรม - ครอสโอเวอร์

ในบทนี้เราจะพูดถึงสิ่งที่ 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 เป็นต้น