التهجين (خوارزمية تطورية)

يتم اختيار نقطة عشوائياً على كروموسومات كلا الأبوين، وتُسمى "نقطة عبور". تُتبادل البتات الموجودة على يمين تلك النقطة بين كروموسومي الأبوين. ينتج عن ذلك نسلان، يحمل كل منهما بعض المعلومات الوراثية من كلا الأبوين.

في عملية التقاطع الثنائي، يتم اختيار نقطتي تقاطع عشوائياً من الكروموسومات الأبوية. ويتم تبادل البتات الواقعة بين النقطتين بين الكائنين الأبويين.

يُعادل التزاوج الثنائي إجراء تزاوج أحادي النقطة مرتين بنقطتي تزاوج مختلفتين. ويمكن تعميم هذه الاستراتيجية لتشمل التزاوج متعدد النقاط (k-point cross-) لأي عدد صحيح موجب k، وذلك باختيار k نقطة تزاوج.

في التزاوج المنتظم، يُختار كل بت من أي من الأبوين باحتمالية متساوية. ^{[ 6 ]} تُستخدم أحيانًا نسب خلط أخرى، مما ينتج عنه نسل يرث معلومات وراثية أكثر من أحد الأبوين مقارنةً بالآخر. في التزاوج المنتظم، لا نقسم الكروموسوم إلى أجزاء، بل نتعامل مع كل جين على حدة. في هذه الحالة، نختار عشوائيًا كل كروموسوم لتحديد ما إذا كان سيُضمّن في النسل أم لا.

إذا تم تطبيق قواعد التقاطع الموحد لسلاسل البتات أثناء توليد النسل، فإن هذا يسمى أيضًا إعادة التركيب المنفصل . ^{[ 7 ]}

في عامل إعادة التركيب هذا، قيم الأليلات في جينوم الطفل${\displaystyle a_{i}}$يتم إنتاجها عن طريق مزج أليلات الجينومين الأبويين.${\displaystyle a_{i,P_{1}}}$و${\displaystyle a_{i,P_{2}}}$: ^{[ 7 ] [ 8 ]}

${\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}$

اختيار الفترة الزمنية${\displaystyle [-d,1+d]}$تُثير هذه الأسباب تساؤلات حول بيئة معينة لنطاق قيم النسل، بالإضافة إلى نطاق القيم داخل الجسم الفائق الذي تغطيه قيم الأليلات للجينات الأبوية. قيمة من${\displaystyle 0.25}$يوصى به لـ${\displaystyle d}$لمواجهة الميل إلى تقليل قيم الأليلات الموجودة في مكان آخر${\displaystyle d=0}$[ ^{9 ]​}

يوضح الشكل المجاور، في الحالة ثنائية الأبعاد، نطاق الأليلات الجديدة المحتملة للوالدين النموذجيين${\displaystyle P_{1}=(3,6)}$و${\displaystyle P_{2}=(9,2)}$في عملية إعادة التركيب الوسيطة. نسل عملية إعادة التركيب المنفصلة${\displaystyle C_{1}}$و${\displaystyle C_{2}}$كما يتم رسمها بيانيًا. يُلبي إعادة التركيب الوسيط الحساب الحسابي لقيم الأليلات في جينوم الطفل، وهو ما تتطلبه نظرية الأبجدية الافتراضية. ^{[ 10 ] [ 11 ]} يُستخدم كل من إعادة التركيب المنفصل والوسيط كمعيار في استراتيجية التطور . ^{[ 12 ]}

صُمم عامل PMX كعامل إعادة تركيب لمسائل مشابهة لمسائل البائع المتجول. ^{[ 15 ] [ 16 ]} ويُوضح شرح الإجراء بمثال:

إجراء		مثال		أمثلة على الكروموسومات
		لنفترض أن لدينا تبديلين لنفس المجموعة.		${\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)}$
		موقف${\displaystyle D}$في${\displaystyle P_{1}}$هو أقصى موضع على اليمين و${\displaystyle A}$سيتم وضعها هناك في${\displaystyle P_{C}}$.		${\displaystyle P_{C}=\left(?,?,?,{\underline {D,E,F}},?,A\right)}$
إذا كان المكان الذي يشغله${\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)}$

يعود مفهوم التقاطع الترتيبي إلى ديفيس ^{[ 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{in order from }}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)}$

من بين أمور أخرى، يُعدّ تقاطع الترتيب مناسبًا تمامًا لجدولة سير العمل المتعددة، عند استخدامه بالتزامن مع تقاطع النقطة الواحدة وتقاطع النقاط المتعددة. ^{[ 17 ]}

بمرور الوقت، تم اقتراح عدد كبير من عوامل التزاوج للتباديل، لذا فإن القائمة التالية ليست سوى عينة صغيرة. لمزيد من المعلومات، يُرجى الرجوع إلى المراجع. ^{[ 1 ] [ 5 ] [ 16 ] [ 13 ]}

1. التقاطع الدوري (CX) ^{[ 18 ] [ 16 ]}
2. التقاطع القائم على الترتيب (OX2) ^{[ 5 ] [ 19 ]}
3. التقاطع القائم على الموقع (POS) ^{[ 5 ] [ 19 ]}
4. إعادة تركيب الحواف ^{[ 20 ] [ 16 ]}
5. إعادة تجميع التصويت (VR) ^{[ 13 ]}
6. التقاطع ذو المواضع المتناوبة (AP) ^{[ 13 ]}
7. أقصى تداخل للمواد الحافظة (MPX) ^{[ 5 ] [ 21 ]}
8. دمج التقاطع (MX) ^{[ 5 ] [ 22 ]}
9. عامل التقاطع البنّاء المتسلسل (SCX) ^{[ 23 ]}

يتمثل النهج المعتاد لحل مسائل شبيهة بمسألة البائع المتجول باستخدام الخوارزميات الجينية، أو بشكل أعم، الخوارزميات التطورية، كما عُرض سابقًا، إما في إصلاح النسل غير الشرعي أو تعديل المعاملات بشكل مناسب لمنع ظهور النسل غير الشرعي من الأساس. وبدلاً من ذلك، يقترح ريازي استخدام تمثيل كروموسومي مزدوج، مما يتجنب ظهور النسل غير الشرعي. ^{[ 24 ]}