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

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

รายการตัวดำเนินการที่แสดงด้านล่างนี้ไม่ได้ครอบคลุมทั้งหมด และใช้เป็นเพียงตัวอย่างประกอบของตัวดำเนินการทางพันธุกรรมแบบไดอะดิกประเภทนี้เท่านั้น สามารถดูตัวดำเนินการเพิ่มเติมและรายละเอียดเพิ่มเติมได้ในเอกสารอ้างอิง^{[ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ]}

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

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

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

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

ในการผสมแบบสม่ำเสมอ โดยทั่วไปแล้ว แต่ละบิตจะถูกเลือกจากพ่อแม่ทั้งสองฝ่ายด้วยความน่าจะเป็นเท่ากัน^{[ 6 ]}บางครั้งมีการใช้อัตราส่วนการผสมอื่นๆ ซึ่งส่งผลให้ลูกหลานได้รับข้อมูลทางพันธุกรรมจากพ่อแม่ฝ่ายหนึ่งมากกว่าอีกฝ่ายหนึ่ง ในการผสมแบบสม่ำเสมอ เราไม่ได้แบ่งโครโมโซมออกเป็นส่วนๆ แต่เราจะพิจารณาแต่ละยีนแยกกัน ในกรณีนี้ เราจะโยนเหรียญสำหรับแต่ละโครโมโซมเพื่อตัดสินใจว่าจะรวมไว้ในลูกหลานหรือไม่

สำหรับตัวดำเนินการครอสโอเวอร์ที่นำเสนอข้างต้น และสำหรับตัวดำเนินการครอสโอเวอร์อื่นๆ ส่วนใหญ่สำหรับสตริงบิตนั้น ก็สามารถนำไปประยุกต์ใช้กับจีโนมค่าจำนวนเต็มหรือค่าจริงได้เช่นกัน โดยที่แต่ละยีนประกอบด้วยจำนวนเต็มหรือค่าจริง แทนที่จะคัดลอกบิตแต่ละตัว ก็จะคัดลอกจำนวนเต็มหรือค่าจริงเข้าไปในจีโนมลูก ลูกหลานจะอยู่บนมุมที่เหลือของไฮเปอร์บอดี้ที่เกิดจากพ่อแม่ทั้งสองดังตัวอย่างในภาพประกอบสำหรับกรณีสามมิติ ${\displaystyle P_{1}=(1.5,6,8)}$${\displaystyle P_{2}=(7,2,1)}$

หากใช้กฎของการผสมข้ามแบบสม่ำเสมอสำหรับสตริงบิตในระหว่างการสร้างลูกหลาน จะเรียกว่าการรวมตัวแบบไม่ต่อเนื่อง^{[ 7 ]}

ในตัวดำเนินการการรวมตัวนี้ ค่าอัลลีลของจีโนมลูกจะถูกสร้างขึ้นโดยการผสมอัลลีลของจีโนมพ่อแม่ทั้งสองและ: ^{[ 7 ] [ 8 ]}${\displaystyle a_{i}}$${\displaystyle a_{i,P_{1}}}$${\displaystyle a_{i,P_{2}}}$

${\displaystyle \alpha _{i}=\alpha _{i,P_{1}}\cdot \beta _{i}+\alpha _{i,P_{2}}\cdot \left(1-\beta _{i}\right)\quad {\mathsf {with}}\quad \beta _{i}\in \left[-d,1+d\right]}$กระจายอย่างเท่าเทียมกันแบบสุ่มต่อยีน${\displaystyle i}$

การเลือกช่วงเวลาส่งผลให้ นอกจากภายในไฮเปอร์บอดี้ที่ครอบคลุมโดยค่าอัลลีลของยีนพ่อแม่แล้ว ยังมีสภาพแวดล้อมบางอย่างสำหรับช่วงค่าของลูกหลานที่ต้องพิจารณาด้วยแนะนำให้ใช้ค่าเพื่อต่อต้านแนวโน้มที่จะลดค่าอัลลีลที่มีอยู่^{[ 9 ]}${\displaystyle [-d,1+d]}$${\displaystyle 0.25}$${\displaystyle d}$${\displaystyle d=0}$

รูปที่อยู่ติดกันแสดงช่วงของอัลลีลใหม่ที่เป็นไปได้ของพ่อแม่ตัวอย่างทั้งสองและในการรวมตัวใหม่ระดับกลางสำหรับกรณีสองมิติ ลูกหลานของการรวมตัวใหม่แบบไม่ต่อเนื่องก็ถูกพล็อตไว้ด้วย การรวมตัวใหม่ระดับกลางเป็นไปตามการคำนวณทางคณิตศาสตร์ของค่าอัลลีลของจีโนมลูกที่จำเป็นโดยทฤษฎีตัวอักษรเสมือน^{[ 10 ] [ 11 ]}การรวมตัวใหม่แบบไม่ต่อเนื่องและระดับกลางถูกใช้เป็นมาตรฐานในกลยุทธ์วิวัฒนาการ^{[ 12 ]}${\displaystyle P_{1}=(3,6)}$${\displaystyle P_{2}=(9,2)}$${\displaystyle C_{1}}$${\displaystyle C_{2}}$

สำหรับงานเชิงการจัดเรียงมัก ใช้ การเรียงสับเปลี่ยนที่ออกแบบมาโดยเฉพาะสำหรับจีโนมซึ่งเป็นการเรียงสับเปลี่ยนของเซต อยู่แล้ว เซตพื้นฐานมักเป็นเซตย่อยของหรือหากใช้การผสมข้ามแบบ 1 จุด หรือ n จุด หรือแบบสม่ำเสมอสำหรับจีโนมจำนวนเต็ม จีโนมลูกอาจมีค่าบางค่าซ้ำกัน และบางค่าอาจหายไป ซึ่งสามารถแก้ไขได้ด้วยการซ่อมแซมทางพันธุกรรมเช่น โดยการแทนที่ยีนที่ซ้ำซ้อนด้วยยีนที่หายไปจากจีโนมลูกอีกตัวหนึ่งโดยยึดตำแหน่งให้ถูกต้อง ${\displaystyle \mathbb {N} }$${\displaystyle \mathbb {N} _{0}}$

เพื่อหลีกเลี่ยงการสร้างลูกหลานที่ไม่ถูกต้อง ได้มีการพัฒนาตัวดำเนินการครอสโอเวอร์พิเศษสำหรับการเรียงสับเปลี่ยน^{[ 13 ]}ซึ่งตรงตามข้อกำหนดพื้นฐานของตัวดำเนินการดังกล่าวสำหรับการเรียงสับเปลี่ยน กล่าวคือ องค์ประกอบทั้งหมดของการเรียงสับเปลี่ยนเริ่มต้นก็มีอยู่ในการเรียงสับเปลี่ยนใหม่ด้วย และมีการเปลี่ยนแปลงเฉพาะลำดับเท่านั้น สามารถแยกแยะได้ระหว่างงานเชิงคอมบินาทอริก ซึ่งลำดับทั้งหมดเป็นที่ยอมรับ และงานที่มีข้อจำกัดในรูปแบบของลำดับบางส่วนที่ไม่สามารถยอมรับได้ ตัวอย่างที่รู้จักกันดีของงานประเภทแรกคือปัญหาพนักงานขายเดินทาง (TSP) ซึ่งเป้าหมายคือการเยี่ยมชมชุดของเมืองเพียงครั้งเดียวในเส้นทางที่สั้นที่สุด ตัวอย่างของงานประเภทที่มีข้อจำกัดคือการจัดตารางเวลาของเวิร์กโฟลว์ หลายรายการ เวิร์กโฟลว์เกี่ยวข้องกับข้อจำกัดลำดับในขั้นตอนการทำงานแต่ละขั้นตอน ตัวอย่างเช่น ไม่สามารถตัดเกลียวได้จนกว่าจะเจาะรูที่เกี่ยวข้องในชิ้นงาน ปัญหาดังกล่าวเรียกว่า การเรียงสับเปลี่ยน ตาม ลำดับ

ต่อไปนี้ จะนำเสนอตัวดำเนินการครอสโอเวอร์สองตัวเป็นตัวอย่าง ได้แก่ ครอสโอเวอร์แบบแมปบางส่วน (PMX) ซึ่งได้รับแรงบันดาลใจจากปัญหา TSP และครอสโอเวอร์แบบเรียงลำดับ (OX1) ซึ่งออกแบบมาสำหรับการเรียงสับเปลี่ยนตามลำดับ ในแต่ละกรณี สามารถสร้างลูกหลานตัวที่สองได้โดยการสลับโครโมโซมของพ่อแม่

ตัวดำเนินการ PMX ได้รับการออกแบบให้เป็นตัวดำเนินการการรวมใหม่สำหรับปัญหาประเภท TSP ^{[ 14 ] [ 15 ]}คำอธิบายของขั้นตอนแสดงให้เห็นโดยตัวอย่าง:

ขั้นตอน		ตัวอย่าง		ตัวอย่างโครโมโซม
		ให้มีการเรียงสับเปลี่ยนสองแบบของเซตเดียวกัน		${\displaystyle P_{0}=\left(A,B,C,D,E,F,G,H\right)}$และ${\displaystyle P_{1}=\left(C,G,E,A,F,H,B,D\right)}$
สุ่มเลือกจุดตัดสองจุดที่ก่อให้เกิดส่วนของยีนใน. ${\displaystyle P_{0}}$		ตรงนี้คือตำแหน่งยีนที่ 4 ถึง 6		${\displaystyle P_{0}=\left(A,B,C,{\underline {D,E,F}},G,H\right)}$
ส่วนที่เลือกจะถูกคัดลอกไปยังโครโมโซมของลูกในตำแหน่งเดียวกัน		ตำแหน่งงานว่างจะแสดงด้วยเครื่องหมายคำถาม		${\displaystyle P_{C}=\left(?,?,?,{\underline {D,E,F}},?,?\right)}$
มองหายีนที่ยังไม่ถูกคัดลอกในส่วนที่สอดคล้องกัน โดยเริ่มจากจุดไขว้แรก สำหรับแต่ละยีนที่พบ (เรียกว่า) ให้ตรวจสอบในลูกหลานว่าองค์ประกอบใด (เรียกว่า) ถูกคัดลอกมาแทนที่จากคัดลอก ไปยังตำแหน่งที่ อยู่ในในถ้าตำแหน่งนั้นยังว่างอยู่ มิเช่นนั้น ให้ดำเนินการต่อในขั้นตอนถัดไป ${\displaystyle P_{1}}$${\displaystyle m}$${\displaystyle n}$${\displaystyle P_{0}}$${\displaystyle m}$${\displaystyle n}$${\displaystyle P_{1}}$		ยีนนี้เป็นยีนแรกที่ไม่ถูกคัดลอกในส่วนที่เกี่ยวข้องของ: ยีนนี้ถูกคัดลอกมาจากในตำแหน่งของมันใน${\displaystyle A}$${\displaystyle P_{1}}$${\displaystyle \left(...,A,F,H,...\right)}$${\displaystyle D}$${\displaystyle P_{0}}$${\displaystyle P_{C}}$		${\displaystyle P_{C}=\left(?,?,?,{\underline {{\mathbf {D}},E,F}},?,?\right)}$
		ตำแหน่งของin คือตำแหน่งขวาสุด และจะถูกวางไว้ที่นั่นใน.${\displaystyle D}$${\displaystyle P_{1}}$${\displaystyle A}$${\displaystyle P_{C}}$		${\displaystyle P_{C}=\left(?,?,?,{\underline {D,E,F}},?,A\right)}$
ถ้าตำแหน่งที่in ครอบครองอยู่นั้น มีองค์ประกอบในลูกหลาน ครอบครองอยู่แล้ว จะนำองค์ประกอบนั้นไปใส่ในตำแหน่งที่in ครอบครอง อยู่ ${\displaystyle n}$${\displaystyle P_{1}}$${\displaystyle k}$${\displaystyle m}$${\displaystyle k}$${\displaystyle P_{1}}$		ยีนถัดไปคือและยีนนี้ได้ถูกคัดลอกไปยังโครโมโซมของลูกแล้ว ดังนั้น ยีนถัดไปที่จะต้องจัดการคือตำแหน่งของมันในลูกหลานจะเป็นตำแหน่งของในอย่างไรก็ตาม ตำแหน่งนี้ถูกครอบครองโดยยีน แล้วดังนั้นจึงถูกคัดลอกไปยังตำแหน่งของใน${\displaystyle \left(...,A,F,H,...\right)}$${\displaystyle F}$${\displaystyle H}$${\displaystyle F}$${\displaystyle P_{1}}$${\displaystyle E}$${\displaystyle H}$${\displaystyle E}$${\displaystyle P_{1}}$		${\displaystyle P_{C}=\left(?,?,H,{\underline {D,E,F}},?,A\right)}$
หลังจากประมวลผลยีนจากส่วนที่เลือกไว้ในจีโนมต้นกำเนิดแล้ว ตำแหน่งที่เหลือในจีโนมลูกหลานจะถูกเติมด้วยยีนจากจีโนมต้นกำเนิดที่ยังไม่ได้คัดลอก โดยเรียงตามลำดับการปรากฏ ซึ่งจะทำให้ได้จีโนมลูกหลานที่สมบูรณ์ ${\displaystyle P_{1}}$${\displaystyle P_{1}}$		ยีนที่ถูกคัดลอกมาจากคือและ${\displaystyle P_{1}}$${\displaystyle C,G}$${\displaystyle B}$		${\displaystyle P_{C}=\left(C,G,H,{\underline {D,E,F}},B,A\right)}$

ลำดับการไขว้กลับไปถึง Davis ^{[ 1 ]}ในรูปแบบดั้งเดิมและนำเสนอในเวอร์ชันทั่วไปเล็กน้อยที่มีจุดไขว้มากกว่าสองจุด โดยจะถ่ายทอดข้อมูลเกี่ยวกับลำดับสัมพัทธ์จากพ่อแม่ตัวที่สองไปยังลูกหลาน ก่อนอื่น จำนวนและตำแหน่งของจุดไขว้จะถูกกำหนดแบบสุ่ม จากนั้นลำดับยีนที่ได้จะถูกประมวลผลตามที่อธิบายไว้ด้านล่าง:

ขั้นตอน		ตัวอย่าง		ตัวอย่างโครโมโซม
		ให้มีการเรียงสับเปลี่ยนสองแบบของเซตเดียวกัน		${\displaystyle P_{0}=\left(A,B,C,D,E,F,G,H,I,J\right)}$และ${\displaystyle P_{1}=\left(B,D,A,H,J,C,E,G,F,I\right)}$
สุ่มเลือกส่วนของยีนใน. ${\displaystyle P_{0}}$		นี่คือสองส่วนจากตำแหน่งยีนที่ 1 ถึง 2 และจาก 6 ถึง 8		${\displaystyle P_{0}=\left({\underline {A,B}},C,D,E,{\underline {F,G,H}},I,J\right)}$
ในฐานะการเรียงสับเปลี่ยนของลูก การเรียงสับเปลี่ยนจะถูกสร้างขึ้นโดยมีส่วนของยีนที่เลือกไว้ในตำแหน่งเดียวกัน ${\displaystyle P_{0}}$		ตำแหน่งงานว่างจะแสดงด้วยเครื่องหมายคำถาม		${\displaystyle P_{C}=\left(A,B,?,?,?,F,G,H,?,?\right)}$
ยีนที่ขาดหายไปที่เหลือก็ถูกถ่ายโอนเช่นกัน แต่เรียงตามลำดับที่ปรากฏในไฟล์ ${\displaystyle P_{1}}$		ยีนที่หายไปในตัวอย่างนี้คือ:${\displaystyle P_{0}}$		${\displaystyle P_{\text{missing}}=\left\{C,D,E,I,J\right\}}$ ${\displaystyle P_{{\text{ตามลำดับจาก }}P_{1}}=\left(D,J,C,E,I\right)}$
ผลลัพธ์ที่ได้คือจีโนมของเด็กที่สมบูรณ์		ยีนที่ถูกถ่ายโอนจะถูกขีดเส้นใต้:		${\displaystyle P_{C}=\left(A,B,{\underline {D,J,C}},F,G,H,{\underline {E,I}}\right)}$

นอกจากนี้ การสลับลำดับยังเหมาะอย่างยิ่งสำหรับการกำหนดตารางเวลาเวิร์กโฟลว์หลายรายการ เมื่อใช้ร่วมกับการสลับแบบ 1 จุดและ n จุด^{[ 16 ]}

เมื่อเวลาผ่านไป มีการเสนอตัวดำเนินการครอสโอเวอร์จำนวนมากสำหรับการเรียงสับเปลี่ยน ดังนั้นรายการต่อไปนี้จึงเป็นเพียงการเลือกเล็กน้อย สำหรับข้อมูลเพิ่มเติม ผู้อ่านสามารถอ้างอิงถึงเอกสารอ้างอิงได้^{[ 1 ] [ 5 ] [ 15 ] [ 13 ]}

1. วงจรครอสโอเวอร์ (CX) ^{[ 17 ] [ 15 ]}
2. ครอสโอเวอร์ตามลำดับ (OX2) ^{[ 5 ] [ 18 ]}
3. ครอสโอเวอร์ตามตำแหน่ง (POS) ^{[ 5 ] [ 18 ]}
4. การรวมขอบใหม่^{[ 19 ] [ 15 ]}
5. การรวมเสียงโหวต (VR) ^{[ 13 ]}
6. การไขว้ตำแหน่งสลับกัน (AP) ^{[ 13 ]}
7. การข้ามสารกันบูดสูงสุด (MPX) ^{[ 5 ] [ 20 ]}
8. การรวมครอสโอเวอร์ (MX) ^{[ 5 ] [ 21 ]}
9. ตัวดำเนินการครอสโอเวอร์เชิงสร้างสรรค์แบบลำดับ (SCX) ^{[ 22 ]}

แนวทางปกติในการแก้ปัญหาที่คล้ายกับ TSP โดยใช้อัลกอริธึมทางพันธุกรรมหรือโดยทั่วไปแล้วอัลกอริธึมวิวัฒนาการที่นำเสนอไว้ก่อนหน้านี้ คือการซ่อมแซมลูกหลานที่ผิดกฎหมายหรือปรับตัวดำเนินการให้เหมาะสมเพื่อไม่ให้เกิดลูกหลานที่ผิดกฎหมายตั้งแต่แรก อีกทางเลือกหนึ่ง Riazi แนะนำให้ใช้การแสดงโครโมโซมคู่ซึ่งช่วยหลีกเลี่ยงลูกหลานที่ผิดกฎหมาย^{[ 23 ]}

• อัลกอริทึมวิวัฒนาการ
• การแสดงออกทางพันธุกรรม
• ฟังก์ชั่นฟิตเนส
• การคัดเลือก (อัลกอริธึมทางพันธุกรรม)

• จอห์น ฮอลแลนด์ (1975). การปรับตัวในระบบธรรมชาติและระบบประดิษฐ์วิทยานิพนธ์ปริญญาเอกสำนักพิมพ์มหาวิทยาลัยมิชิแกนแอนอาร์เบอร์ รัฐมิชิแกนISBN 0-262-58111-6.
• Schwefel, Hans-Paul (1995). วิวัฒนาการและการแสวงหาสิ่งที่ดีที่สุด . นิวยอร์ก: John Wiley & Sons. ISBN 0-471-57148-2.
• เดวิส, ลอว์เรนซ์ (1991). คู่มืออัลกอริทึมทางพันธุกรรม . นิวยอร์ก: แวน นอสแตรนด์ ไรน์โฮลด์. ISBN 0-442-00173-8. OCLC  23081440 .
• Eiben, AE; Smith, JE (2015). บทนำสู่การคำนวณเชิงวิวัฒนาการชุดการคำนวณทางธรรมชาติ เบอร์ลิน, ไฮเดลเบิร์ก: Springer. doi : 10.1007/978-3-662-44874-8 . ISBN 978-3-662-44873-1. S2CID  20912932 .
• Yu, Xinjie; Gen, Mitsuo (2010). บทนำสู่ขั้นตอนวิธีเชิงวิวัฒนาการ วิศวกรรมการตัดสินใจ ลอนดอน: Springer. doi : 10.1007/978-1-84996-129-5 . ISBN 978-1-84996-128-8.
• Bäck, Thomas; Fogel, David B.; Michalewicz, Zbigniew, บรรณาธิการ (1999). การคำนวณเชิงวิวัฒนาการ เล่ม 1 อัลกอริทึมและตัวดำเนินการพื้นฐานบริสตอล: สำนักพิมพ์สถาบันฟิสิกส์ISBN 0-585-30560-9. OCLC  45730387 .

• กลุ่มข่าว: comp.ai.genetic FAQ - ดูหัวข้อเกี่ยวกับการไขว้กัน (หรือที่เรียกว่าการรวมตัวใหม่)