Crossover (genetic algorithm)
জেনেটিক অ্যালগরিদম এবং বিবর্তনীয় গণনায়, ক্রসওভার, যাকে পুনঃসংযোগও বলা হয়, একটি জেনেটিক অপারেটর যা দুই পিতামাতার জেনেটিক তথ্য একত্রিত করে নতুন সন্তান তৈরি করতে ব্যবহৃত হয়। এটি একটি বিদ্যমান জনসংখ্যা থেকে নতুন সমাধান তৈরি করার একটি উপায়, এবং জীববিজ্ঞানে যৌন প্রজননের সময় ঘটে যাওয়া ক্রসওভারের অনুরূপ। একটি বিদ্যমান সমাধান ক্লোনিংয়ের মাধ্যমেও সমাধান তৈরি করা যেতে পারে, যা অযৌন প্রজননের অনুরূপ। নতুন উৎপন্ন দ্রবণগুলি জনসংখ্যার সাথে যুক্ত হওয়ার আগে পরিবর্তিত হতে পারে। বিবর্তনীয় গণনায় বিভিন্ন অ্যালগরিদম জেনেটিক তথ্য সংরক্ষণের জন্য বিভিন্ন তথ্য কাঠামো ব্যবহার করতে পারে এবং প্রতিটি জেনেটিক উপস্থাপনাকে বিভিন্ন ক্রসওভার অপারেটরের সাথে পুনরায় একত্রিত করা যেতে পারে। সাধারণ তথ্য কাঠামো যা ক্রসওভারের সাথে পুনরায় সংযুক্ত করা যেতে পারে তা হল বিট অ্যারে, বাস্তব সংখ্যার ভেক্টর বা গাছ। নীচে উপস্থাপিত অপারেটরদের তালিকা কোনওভাবেই সম্পূর্ণ নয় এবং মূলত এই ডাইডিক জেনেটিক অপারেটর প্রকারের একটি অনুকরণীয় দৃষ্টান্ত হিসাবে কাজ করে। আরও অপারেটর এবং আরও বিশদ সাহিত্যে পাওয়া যাবে। বাইনারি অ্যারেগুলির জন্য ক্রসওভার ঐতিহ্যবাহী জেনেটিক অ্যালগরিদমগুলি একটি বিট অ্যারে দ্বারা প্রতিনিধিত্ব করা ক্রোমোসোমে জেনেটিক তথ্য সঞ্চয় করে। বিট অ্যারেগুলির জন্য ক্রসওভার পদ্ধতিগুলি জনপ্রিয় এবং জেনেটিক পুনর্মিলনের একটি দৃষ্টান্তমূলক উদাহরণ। এক-বিন্দু ক্রসওভার পিতামাতার উভয় ক্রোমোজোমের একটি বিন্দু এলোমেলোভাবে বাছাই করা হয় এবং একটি 'ক্রসওভার পয়েন্ট' মনোনীত করা হয়। সেই বিন্দুর ডানদিকে বিট দুটি মূল ক্রোমোজোমের মধ্যে অদলবদল করা হয়। এর ফলে দুটি সন্তান হয়, প্রতিটি পিতামাতা উভয়ের কাছ থেকে কিছু জিনগত তথ্য বহন করে। দুই-বিন্দু এবং কে-বিন্দু ক্রসওভার দুই-বিন্দু ক্রসওভারে, মূল ক্রোমোজোম থেকে দুটি ক্রসওভার পয়েন্ট এলোমেলোভাবে বাছাই করা হয়। দুটি বিন্দুর মধ্যে থাকা বিটগুলি মূল জীবের মধ্যে অদলবদল করা হয়। দুই-পয়েন্ট ক্রসওভার বিভিন্ন ক্রসওভার পয়েন্ট সহ দুটি একক-পয়েন্ট ক্রসওভার সম্পাদন করার সমতুল্য। এই কৌশলটি কে-ক্রসওভার পয়েন্ট বাছাই করে যে কোনও ধনাত্মক পূর্ণসংখ্যা কে-এর জন্য কে-পয়েন্ট ক্রসওভারে সাধারণীকরণ করা যেতে পারে। ইউনিফর্ম ক্রসওভারে, সাধারণত, প্রতিটি বিট সমান সম্ভাব্যতা সহ উভয় প্যারেন্ট থেকে বেছে নেওয়া হয়। অন্যান্য মিশ্রণ অনুপাত কখনও কখনও ব্যবহার করা হয়, যার ফলে সন্তানরা অন্যের তুলনায় এক পিতামাতার কাছ থেকে বেশি জিনগত তথ্য উত্তরাধিকার সূত্রে পায়। একটি অভিন্ন ক্রসওভারে, আমরা ক্রোমোজোমকে খণ্ডে বিভক্ত করি না, বরং আমরা প্রতিটি জিনকে আলাদাভাবে চিকিত্সা করি। এতে, আমরা মূলত প্রতিটি ক্রোমোজোমের জন্য একটি মুদ্রা উল্টাই এটি নির্ধারণ করতে যে এটি অফ-স্প্রিং-এ অন্তর্ভুক্ত করা হবে কিনা। পূর্ণসংখ্যা বা বাস্তব-মূল্যবান জিনোমের জন্য ক্রসওভার উপরে উপস্থাপিত ক্রসওভার অপারেটরদের জন্য এবং বিট স্ট্রিংয়ের জন্য বেশিরভাগ অন্যান্য ক্রসওভার অপারেটরদের জন্য, এটি ধারণ করে যে এগুলি পূর্ণসংখ্যা বা বাস্তব-মূল্যবান জিনোমের জন্যও প্রয়োগ করা যেতে পারে যার প্রতিটি জিন একটি পূর্ণসংখ্যা বা বাস্তব-মূল্যবান সংখ্যা নিয়ে গঠিত। পৃথক বিটের পরিবর্তে, পূর্ণসংখ্যা বা বাস্তব-মূল্যবান সংখ্যাগুলি কেবল চাইল্ড জিনোমে অনুলিপি করা হয়। সন্তানরা দুই পিতামাতার দ্বারা বিস্তৃত হাইপারবডি-র অবশিষ্ট কোণে থাকে এবং ত্রিমাত্রিক ক্ষেত্রে সহগামী ছবিতে যেমন উদাহরণ দেওয়া হয়েছে। বিচ্ছিন্ন পুনঃসংযোগ যদি বিট স্ট্রিংয়ের জন্য অভিন্ন ক্রসওভারের নিয়মগুলি বংশধরের প্রজন্মের সময় প্রয়োগ করা হয়, তবে এটিকে বিচ্ছিন্ন পুনঃসংযোগও বলা হয়। মধ্যবর্তী পুনঃসংযোগ এই পুনঃসংযোগ পরিচালকের মধ্যে, শিশু জিনোমের অ্যালিল মানগুলি দুটি মূল জিনোমের অ্যালিলগুলি মিশ্রিত করে তৈরি করা হয় এবংঃ জিন প্রতি এলোমেলোভাবে সমানভাবে বিতরণ করা হয় ব্যবধানের পছন্দটি কারণ করে যে মূল জিনের অ্যালিল মান দ্বারা বিস্তৃত হাইপারবডিটির অভ্যন্তর ছাড়াও অতিরিক্তভাবে সন্তানের মানগুলির পরিসরের জন্য একটি নির্দিষ্ট পরিবেশ প্রশ্নবিদ্ধ। অ্যালিল মানগুলি হ্রাস করার প্রবণতাকে প্রতিহত করার জন্য একটি মান সুপারিশ করা হয় যা অন্যথায় বিদ্যমান। সংলগ্ন চিত্রটি দ্বিমাত্রিক ক্ষেত্রে দুটি অনুকরণীয় পিতামাতার সম্ভাব্য নতুন অ্যালিলের পরিসীমা এবং মধ্যবর্তী পুনঃসংযোগ দেখায়। বিচ্ছিন্ন পুনর্মিলনের বংশধর এবং প্লট করা হয়। মধ্যবর্তী পুনঃসংযোগ ভার্চ্যুয়াল বর্ণমালা তত্ত্ব দ্বারা প্রয়োজনীয় শিশু জিনোমের অ্যালিল মানগুলির গাণিতিক গণনাকে সন্তুষ্ট করে। বিচ্ছিন্ন এবং মধ্যবর্তী পুনর্মিলন বিবর্তন কৌশলে একটি মান হিসাবে ব্যবহৃত হয়। বিন্যাসের জন্য ক্রসওভার সমন্বিত কাজের জন্য, বিন্যাসগুলি সাধারণত ব্যবহার করা হয় যা বিশেষভাবে জিনোমের জন্য ডিজাইন করা হয় যা নিজেই একটি সেটের বিন্যাস। অন্তর্নিহিত সেটটি সাধারণত বা এর একটি উপসেট হয়। যদি এই ধরনের জিনোমের জন্য পূর্ণসংখ্যা জিনোমের জন্য 1-বা এন-পয়েন্ট বা ইউনিফর্ম ক্রসওভার ব্যবহার করা হয়, তবে একটি শিশু জিনোমে কিছু মান দুবার থাকতে পারে এবং অন্যগুলি অনুপস্থিত থাকতে পারে। এটি জেনেটিক মেরামতের মাধ্যমে নিরাময় করা যেতে পারে, যেমন। অন্যান্য শিশু জিনোম থেকে অনুপস্থিত জিনগুলির জন্য অবস্থানগত বিশ্বস্ততায় অপ্রয়োজনীয় জিনগুলিকে প্রতিস্থাপন করে। অবৈধ বংশধরের জন্ম এড়ানোর জন্য, বিন্যাসের জন্য বিশেষ ক্রসওভার অপারেটর তৈরি করা হয়েছে যা বিন্যাসের জন্য এই ধরনের অপারেটরদের মৌলিক প্রয়োজনীয়তা পূরণ করে, যথা প্রাথমিক বিন্যাসের সমস্ত উপাদানও নতুনটিতে উপস্থিত থাকে এবং শুধুমাত্র ক্রম পরিবর্তন করা হয়। এটি সমন্বিত কাজগুলির মধ্যে পার্থক্য করা যেতে পারে, যেখানে সমস্ত ক্রম গ্রহণযোগ্য এবং যেখানে অগ্রহণযোগ্য আংশিক ক্রমের আকারে সীমাবদ্ধতা রয়েছে। প্রথম কাজের প্রকারের একটি সুপরিচিত প্রতিনিধি হল ট্রাভেল সেলসম্যান প্রবলেম (টিএসপি), যেখানে লক্ষ্য হল সংক্ষিপ্ততম সফরে ঠিক একবার শহরগুলির একটি সেট পরিদর্শন করা। সীমাবদ্ধ কাজের প্রকারের একটি উদাহরণ হল একাধিক কর্মপ্রবাহের সময়সূচী। কর্মপ্রবাহে কিছু পৃথক কাজের ধাপে ক্রমের সীমাবদ্ধতা জড়িত থাকে। উদাহরণস্বরূপ, একটি ওয়ার্কপিসে সংশ্লিষ্ট গর্তটি ড্রিল না করা পর্যন্ত একটি সুতা কাটা যায় না। এই ধরনের সমস্যাগুলিকে ক্রম-ভিত্তিক বিন্যাসও বলা হয়। নিম্নলিখিত দুটি ক্রসওভার অপারেটরকে উদাহরণ হিসাবে উপস্থাপন করা হয়েছে, আংশিকভাবে ম্যাপ করা ক্রসওভার (পিএমএক্স) টিএসপি দ্বারা অনুপ্রাণিত এবং অর্ডার-ভিত্তিক বিন্যাসের জন্য ডিজাইন করা অর্ডার ক্রসওভার (ওএক্স1)। প্রতিটি ক্ষেত্রে মূল ক্রোমোজোম বিনিময় করে একটি দ্বিতীয় সন্তান তৈরি করা যেতে পারে। আংশিকভাবে ম্যাপ করা ক্রসওভার (পি. এম. এক্স) পি. এম. এক্স অপারেটরটি সমস্যার মতো টি. এস. পি-র জন্য একটি পুনর্মিলন অপারেটর হিসাবে ডিজাইন করা হয়েছিল। পদ্ধতির ব্যাখ্যাটি একটি উদাহরণ দ্বারা চিত্রিত করা হয়েছেঃ অর্ডার ক্রসওভার (ওএক্স1) অর্ডার ক্রসওভারটি তার মূল আকারে ডেভিসের কাছে ফিরে যায় এবং এখানে দুটিরও বেশি ক্রসওভার পয়েন্ট সহ সামান্য সাধারণীকৃত সংস্করণে উপস্থাপন করা হয়েছে। এটি দ্বিতীয় পিতামাতার কাছ থেকে বংশধরদের কাছে আপেক্ষিক ক্রম সম্পর্কে তথ্য স্থানান্তর করে। প্রথমত, ক্রসওভার পয়েন্টগুলির সংখ্যা এবং অবস্থান এলোমেলোভাবে নির্ধারণ করা হয়। ফলস্বরূপ জিন সিকোয়েন্সগুলি নীচে বর্ণিত হিসাবে প্রক্রিয়া করা হয়ঃ অন্যান্য বিষয়গুলির মধ্যে, অর্ডার ক্রসওভার একাধিক ওয়ার্কফ্লো নির্ধারণের জন্য উপযুক্ত, যখন 1-এবং এন-পয়েন্ট ক্রসওভারের সাথে একত্রে ব্যবহৃত হয়। ক্রমবিন্যাসের জন্য আরও ক্রসওভার অপারেটর সময়ের সাথে সাথে, ক্রমবিন্যাসের জন্য বিপুল সংখ্যক ক্রসওভার অপারেটরের প্রস্তাব দেওয়া হয়েছে, তাই নিম্নলিখিত তালিকাটি কেবল একটি ছোট নির্বাচন। আরও তথ্যের জন্য পাঠককে সাহিত্যে উল্লেখ করা হয়। সাইকেল ক্রসওভার (সিএক্স) অর্ডার-ভিত্তিক ক্রসওভার (ওএক্স2) পজিশন-ভিত্তিক ক্রসওভার (পিওএস) এজ রিকম্বিনেশন ভোটিং রিকম্বিনেশন (ভিআর) অল্টারনেটিং-পজিশন ক্রসওভার (এপি) ম্যাক্সিমাল প্রিজারভেটিভ ক্রসওভার (এমপিএক্স) মার্জ ক্রসওভার (এমএক্স) সিকোয়েন্সিয়াল কনস্ট্রাকটিভ ক্রসওভার অপারেটর (এসসিএক্স) জেনেটিক বা আরও সাধারণভাবে, বিবর্তনীয় অ্যালগরিদম দ্বারা টিএসপি-এর মতো সমস্যা সমাধানের সাধারণ পদ্ধতি, যা আগে উপস্থাপিত হয়েছে, তা হল অবৈধ বংশধরদের মেরামত করা বা অপারেটরদের যথাযথভাবে সামঞ্জস্য করা যাতে অবৈধ বংশধরদের জন্ম না হয়। বিকল্পভাবে, রিয়াজি একটি দ্বৈত ক্রোমোজোম উপস্থাপনা ব্যবহারের পরামর্শ দেয়, যা অবৈধ সন্তানকে এড়িয়ে চলে। আরও দেখুন বিবর্তনীয় অ্যালগরিদম জেনেটিক উপস্থাপনা ফিটনেস ফাংশন নির্বাচন (জেনেটিক অ্যালগরিদম) গ্রন্থপঞ্জি জন হল্যান্ড (1975)। অ্যাডাপটেশন ইন ন্যাচারাল অ্যান্ড আর্টিফিশিয়াল সিস্টেমস, পিএইচডি থিসিস, ইউনিভার্সিটি অফ মিশিগান প্রেস, অ্যান আরবোর, মিশিগান। । তথ্যসূত্র বাইরের লিঙ্ক নিউজগ্রুপঃ comp.ai.genetic এফএকিউ-ক্রসওভারের বিভাগটি দেখুন (যা পুনর্মিলন নামেও পরিচিত)। বিবর্তনীয় অ্যালগরিদম জেনেটিক অ্যালগরিদম