Crossover (genetic algorithm)
جینیاتی الگورتھم اور ارتقائی حساب میں، کراس اوور، جسے ریکومبینیشن بھی کہا جاتا ہے، ایک جینیاتی آپریٹر ہے جو نئی اولاد پیدا کرنے کے لیے دو والدین کی جینیاتی معلومات کو یکجا کرنے کے لیے استعمال ہوتا ہے۔ یہ موجودہ آبادی سے نئے حل پیدا کرنے کا ایک طریقہ ہے، اور یہ کراس اوور کے مترادف ہے جو حیاتیات میں جنسی پنروتپادن کے دوران ہوتا ہے۔ حل موجودہ حل کی کلوننگ کے ذریعے بھی تیار کیے جا سکتے ہیں، جو غیر جنسی تولید کے مترادف ہے۔ نئے پیدا شدہ حلوں کو آبادی میں شامل کرنے سے پہلے تبدیل کیا جا سکتا ہے۔ ارتقائی حساب میں مختلف الگورتھم جینیاتی معلومات کو ذخیرہ کرنے کے لیے مختلف ڈیٹا ڈھانچے کا استعمال کر سکتے ہیں، اور ہر جینیاتی نمائندگی کو مختلف کراس اوور آپریٹرز کے ساتھ دوبارہ ملایا جا سکتا ہے۔ عام ڈیٹا ڈھانچے جنہیں کراس اوور کے ساتھ دوبارہ ملایا جا سکتا ہے وہ بٹ صف، حقیقی اعداد کے ویکٹر، یا درخت ہیں۔ ذیل میں پیش کردہ آپریٹرز کی فہرست کسی بھی طرح سے مکمل نہیں ہے اور بنیادی طور پر اس ڈائیڈک جینیاتی آپریٹر کی قسم کی مثالی مثال کے طور پر کام کرتی ہے۔ مزید آپریٹرز اور مزید تفصیلات ادب میں مل سکتی ہیں۔ بائنری صفوں کے لیے کراس اوور روایتی جینیاتی الگورتھم جینیاتی معلومات کو کروموسوم میں محفوظ کرتے ہیں جس کی نمائندگی بٹ صف کرتی ہے۔ بٹ صفوں کے لیے کراس اوور طریقے مقبول ہیں اور جینیاتی دوبارہ ملاپ کی ایک مثالی مثال ہیں۔ ایک نکاتی کراس اوور دونوں والدین کے کروموسوم پر ایک نقطہ تصادفی طور پر اٹھایا جاتا ہے، اور اسے 'کراس اوور پوائنٹ' نامزد کیا جاتا ہے۔ اس نقطہ کے دائیں طرف کے بٹس کو دو پیرنٹ کروموسوم کے درمیان تبدیل کیا جاتا ہے۔ اس کے نتیجے میں دو اولاد پیدا ہوتی ہیں، جن میں سے ہر ایک میں دونوں والدین سے کچھ جینیاتی معلومات ہوتی ہیں۔ دو نکاتی اور کے نکاتی کراس اوور دو نکاتی کراس اوور میں، دو کراس اوور پوائنٹس کو بے ترتیب طور پر پیرنٹ کروموسوم سے منتخب کیا جاتا ہے۔ دونوں نکات کے درمیان بٹس کو پیرنٹ حیاتیات کے درمیان تبدیل کیا جاتا ہے۔ دو نکاتی کراس اوور مختلف کراس اوور پوائنٹس کے ساتھ دو سنگل پوائنٹ کراس اوور انجام دینے کے برابر ہے۔ اس حکمت عملی کو کسی بھی مثبت عدد k کے لیے k-پوائنٹ کراس اوور میں عام کیا جا سکتا ہے، k کراس اوور پوائنٹس کو چن کر۔ یکساں کراس اوور میں، عام طور پر، ہر بٹ کو مساوی امکان کے ساتھ کسی بھی پیرنٹ سے منتخب کیا جاتا ہے۔ دیگر اختلاط تناسب بعض اوقات استعمال کیے جاتے ہیں، جس کے نتیجے میں اولاد ہوتی ہے جو دوسرے کے مقابلے میں ایک والدین سے زیادہ جینیاتی معلومات حاصل کرتی ہے۔ یکساں کراس اوور میں، ہم کروموسوم کو حصوں میں تقسیم نہیں کرتے، بلکہ ہم ہر جین کا الگ سے علاج کرتے ہیں۔ اس میں، ہم بنیادی طور پر ہر کروموسوم کے لیے ایک سکہ پلٹاتے ہیں تاکہ یہ فیصلہ کیا جا سکے کہ اسے آف اسپرنگ میں شامل کیا جائے گا یا نہیں۔ عدد یا حقیقی قدر والے جینوموں کے لیے کراس اوور اوپر پیش کردہ کراس اوور آپریٹرز کے لیے اور بٹ سٹرنگز کے لیے زیادہ تر دوسرے کراس اوور آپریٹرز کے لیے، یہ مانا جاتا ہے کہ ان کا اطلاق انٹیجر یا حقیقی قدر والے جینوموں کے مطابق بھی کیا جا سکتا ہے جن کے جین ہر ایک عدد یا حقیقی قدر والے نمبر پر مشتمل ہوتے ہیں۔ انفرادی بٹس کے بجائے، انٹیجر یا حقیقی قدر والے نمبروں کو پھر صرف چائلڈ جینوم میں نقل کیا جاتا ہے۔ اولاد ہائپر باڈی کے بقیہ کونوں پر پڑی ہوتی ہے جس پر دونوں والدین پھیلے ہوتے ہیں اور، جیسا کہ سہ جہتی کیس کے ساتھ والی تصویر میں مثال دی گئی ہے۔ ڈسکریٹ ریکومبینیشن اگر بٹ سٹرنگز کے لیے یکساں کراس اوور کے قوانین کو اولاد کی نسل کے دوران لاگو کیا جاتا ہے، تو اسے ڈسکریٹ ریکومبینیشن بھی کہا جاتا ہے۔ انٹرمیڈیٹ ریکومبینیشن اس ریکومبینیشن آپریٹر میں، چائلڈ جینوم کی ایلیل ویلیوز دو پیرنٹ جینومز کے ایلیلز کو ملا کر تیار کی جاتی ہیں اور: تصادفی طور پر فی جین یکساں طور پر تقسیم کیا جاتا ہے۔ وقفے کا انتخاب اس وجہ سے ہوتا ہے کہ ہائپر باڈی کے اندرونی حصے کے علاوہ پیرنٹ جینز کی ایلیل ویلیوز کے ذریعہ پھیلا ہوا ہے، اضافی طور پر اولاد کی اقدار کی حد کے لیے ایک مخصوص ماحول سوال میں ہے۔ ایلیل اقدار کو کم کرنے کے رجحان کا مقابلہ کرنے کے لیے ایک قدر کی سفارش کی جاتی ہے جو بصورت دیگر پر موجود ہوتی ہے۔ ملحقہ شکل دو جہتی کیس کے لیے دو مثالی والدین کے ممکنہ نئے ایلیلز کی حد اور انٹرمیڈیٹ ریکومبینیشن کو ظاہر کرتی ہے۔ مجرد ریکومبینیشن کی اولاد بھی پلاٹ کی جاتی ہیں۔ انٹرمیڈیٹ ریکومبینیشن ورچوئل الفابیٹ تھیوری کے ذریعہ درکار چائلڈ جینوم کی ایلیل اقدار کے ریاضی کے حساب کو مطمئن کرتی ہے۔ ارتقاء کی حکمت عملی میں مجرد اور درمیانی دوبارہ ملاپ کو ایک معیار کے طور پر استعمال کیا جاتا ہے۔ ترتیبات کے لیے کراس اوور مشترکہ کاموں کے لیے، ترتیبات عام طور پر استعمال کی جاتی ہیں جو خاص طور پر جینومز کے لیے ڈیزائن کی جاتی ہیں جو خود کسی سیٹ کی ترتیبات ہوتی ہیں۔ بنیادی سیٹ عام طور پر یا کا ذیلی سیٹ ہوتا ہے۔ اگر انٹیجر جینومز کے لیے 1-یا n-پوائنٹ یا یکساں کراس اوور استعمال کیا جاتا ہے، تو چائلڈ جینوم میں کچھ اقدار دو بار ہو سکتی ہیں اور دیگر غائب ہو سکتے ہیں۔ اس کا علاج جینیاتی مرمت کے ذریعے کیا جا سکتا ہے، مثلا۔ دوسرے بچے کے جینوم سے گمشدہ جینوں کے لیے پوزیشن کی وفاداری میں بے کار جینوں کی جگہ لے کر۔ غلط اولاد کی نسل سے بچنے کے لیے، ترتیب کے لیے خصوصی کراس اوور آپریٹرز تیار کیے گئے ہیں جو ترتیب کے لیے ایسے آپریٹرز کی بنیادی ضروریات کو پورا کرتے ہیں، یعنی کہ ابتدائی ترتیب کے تمام عناصر بھی نئے میں موجود ہوتے ہیں اور صرف ترتیب کو تبدیل کیا جاتا ہے۔ اسے مشترکہ کاموں کے درمیان ممتاز کیا جا سکتا ہے، جہاں تمام ترتیب قابل قبول ہیں، اور جہاں ناقابل قبول جزوی ترتیب کی شکل میں رکاوٹیں ہیں۔ پہلے ٹاسک کی قسم کا ایک معروف نمائندہ ٹریولنگ سیلز مین مسئلہ (ٹی ایس پی) ہے، جہاں مقصد مختصر ترین دورے پر بالکل ایک بار شہروں کے ایک سیٹ کا دورہ کرنا ہے۔ محدود کام کی قسم کی ایک مثال متعدد ورک فلوز کا شیڈولنگ ہے۔ ورک فلو میں انفرادی کام کے کچھ مراحل پر ترتیب کی رکاوٹیں شامل ہوتی ہیں۔ مثال کے طور پر، دھاگے کو اس وقت تک نہیں کاٹا جا سکتا جب تک کہ متعلقہ سوراخ کو ورک پیس میں کھود نہ لیا جائے۔ اس طرح کے مسائل کو ترتیب پر مبنی تغیرات بھی کہا جاتا ہے۔ مندرجہ ذیل میں، دو کراس اوور آپریٹرز کو مثال کے طور پر پیش کیا گیا ہے، جزوی طور پر نقشہ شدہ کراس اوور (پی ایم ایکس) جو ٹی ایس پی سے متاثر ہے اور آرڈر کراس اوور (او ایکس 1) جو آرڈر پر مبنی تغیرات کے لیے ڈیزائن کیا گیا ہے۔ والدین کے کروموسوم کا تبادلہ کرکے ہر معاملے میں دوسری اولاد پیدا کی جا سکتی ہے۔ جزوی طور پر نقشہ بند کراس اوور (پی ایم ایکس) پی ایم ایکس آپریٹر کو ٹی ایس پی جیسے مسائل کے لیے ریکومبینیشن آپریٹر کے طور پر ڈیزائن کیا گیا تھا۔ طریقہ کار کی وضاحت ایک مثال سے واضح کی گئی ہے: آرڈر کراس اوور (OX1) آرڈر کراس اوور اپنی اصل شکل میں ڈیوس کے پاس واپس جاتا ہے اور یہاں دو سے زیادہ کراس اوور پوائنٹس کے ساتھ قدرے عمومی ورژن میں پیش کیا گیا ہے۔ یہ دوسرے والدین سے اولاد میں رشتہ دار ترتیب کے بارے میں معلومات منتقل کرتا ہے۔ سب سے پہلے، کراس اوور پوائنٹس کی تعداد اور پوزیشن کا تعین تصادفی طور پر کیا جاتا ہے۔ اس کے نتیجے میں جین کے ترتیبات پر عمل کیا جاتا ہے جیسا کہ ذیل میں بیان کیا گیا ہے: دوسری چیزوں کے علاوہ، آرڈر کراس اوور متعدد ورک فلوز کے شیڈولنگ کے لیے موزوں ہے، جب 1-اور n-پوائنٹ کراس اوور کے ساتھ مل کر استعمال کیا جاتا ہے۔ ترتیبات کے لیے مزید کراس اوور آپریٹرز وقت کے ساتھ، ترتیبات کے لیے کراس اوور آپریٹرز کی ایک بڑی تعداد تجویز کی گئی ہے، اس لیے درج ذیل فہرست صرف ایک چھوٹا انتخاب ہے۔ مزید معلومات کے لیے قارئین کو ادب کا حوالہ دیا جاتا ہے۔ سائیکل کراس اوور (سی ایکس) آرڈر بیسڈ کراس اوور (او ایکس 2) پوزیشن بیسڈ کراس اوور (پی او ایس) ایج ریکومبینیشن ووٹنگ ریکومبینیشن (وی آر) الٹرنیٹنگ پوزیشن کراس اوور (اے پی) میکسمل پریزرویٹو کراس اوور (ایم پی ایکس) مرج کراس اوور (ایم ایکس) سیکوینشیل کنسٹرکٹو کراس اوور آپریٹر (ایس سی ایکس) جینیاتی یا زیادہ عام طور پر، ارتقائی الگورتھم کے ذریعے ٹی ایس پی جیسے مسائل کو حل کرنے کا معمول کا طریقہ، جو پہلے پیش کیا گیا ہے، یا تو غیر قانونی اولاد کی مرمت کرنا ہے یا آپریٹرز کو مناسب طریقے سے ایڈجسٹ کرنا ہے تاکہ پہلی جگہ پر غیر قانونی اولاد پیدا نہ ہو۔ متبادل طور پر، ریازی دوہرے کروموسوم کی نمائندگی کے استعمال کی تجویز کرتا ہے، جو غیر قانونی اولاد سے بچتا ہے۔ ایوولوشنری الگورتھم جینیاتی نمائندگی فٹنس فنکشن سلیکشن (جینیاتی الگورتھم) ببلیوگرافی جان ہالینڈ (1975) بھی دیکھیں۔ قدرتی اور مصنوعی نظام میں موافقت، پی ایچ ڈی مقالہ، یونیورسٹی آف مشی گن پریس، این آربر، مشی گن۔ ۔ حوالہ جات بیرونی روابط نیوز گروپ: comp.ai.genetic عمومی سوالات-کراس اوور پر سیکشن دیکھیں (جسے ریکومبینیشن بھی کہا جاتا ہے)۔ ارتقائی الگورتھم جینیاتی الگورتھم