Population model (evolutionary algorithm)
একটি বিবর্তনীয় অ্যালগরিদমের (ইএ) জনসংখ্যা মডেল তার জনসংখ্যার কাঠামোগত বৈশিষ্ট্যগুলি বর্ণনা করে যার সাপেক্ষে এর সদস্যরা বিষয়। একটি জনসংখ্যা হল একটি পুনরাবৃত্তিতে বিবেচিত একটি ই. এ-র সমস্ত প্রস্তাবিত সমাধানের সমষ্টি, যাকে জৈবিক ভূমিকা মডেল অনুসারে ব্যক্তিও বলা হয়। একটি জনসংখ্যার ব্যক্তিরা পদ্ধতির জেনেটিক অপারেটরদের সাহায্যে সন্তান হিসাবে আরও ব্যক্তি তৈরি করতে পারে। ই. এ-তে সবচেয়ে সহজ এবং ব্যাপকভাবে ব্যবহৃত জনসংখ্যার মডেল হল বৈশ্বিক বা প্যানমিকটিক মডেল, যা একটি অসংগঠিত জনসংখ্যার সাথে মিলে যায়। এটি প্রতিটি ব্যক্তিকে ক্রসওভার দ্বারা সন্তান উৎপাদনের জন্য অংশীদার হিসাবে জনসংখ্যার অন্য যে কোনও ব্যক্তিকে বেছে নেওয়ার অনুমতি দেয়, যার মাধ্যমে নির্বাচনের বিবরণ অপ্রাসঙ্গিক যতক্ষণ না ব্যক্তিদের যোগ্যতা একটি গুরুত্বপূর্ণ ভূমিকা পালন করে। বৈশ্বিক সঙ্গী নির্বাচনের কারণে, কয়েক প্রজন্মের পরে (একটি ই. এ-র পুনরাবৃত্তি) জনসংখ্যার মধ্যে সামান্য ভাল ব্যক্তিদের জিনগত তথ্য প্রাধান্য পেতে পারে, তবে শর্ত থাকে যে এই পর্যায়ে অন্য কোনও ভাল সন্তান আবির্ভূত হয়নি। যদি এইভাবে পাওয়া সমাধানটি সর্বোত্তম চাওয়া না হয়, তবে তাকে অকাল অভিসরণ বলা হয়। এই প্রভাব প্যানমিকটিক জনসংখ্যার মধ্যে প্রায়শই দেখা যায়। প্রকৃতিতে বৈশ্বিক সঙ্গমের পুকুর খুব কমই পাওয়া যায়। যা প্রচলিত তা হল স্থানিক দূরত্বের কারণে একটি নির্দিষ্ট এবং সীমিত বিচ্ছিন্নতা। ফলস্বরূপ স্থানীয় এলাকাগুলি প্রাথমিকভাবে স্বাধীনভাবে বিকশিত হয় এবং মিউট্যান্টদের বেশ কয়েকটি প্রজন্ম ধরে টিকে থাকার সম্ভাবনা বেশি থাকে। ফলস্বরূপ, জিন পুলে জিনোটাইপিক বৈচিত্র্য একটি প্যানমিকটিক জনসংখ্যার তুলনায় বেশি সময় ধরে সংরক্ষিত থাকে। অতএব, পূর্ববর্তী বিশ্ব জনসংখ্যাকে উপ-কাঠামো দ্বারা বিভক্ত করা সুস্পষ্ট। এই উদ্দেশ্যে দুটি মৌলিক মডেল চালু করা হয়েছিল, দ্বীপ মডেল, যা নির্দিষ্ট উপ-জনসংখ্যায় জনসংখ্যার বিভাজনের উপর ভিত্তি করে যা সময়ে সময়ে ব্যক্তিদের বিনিময় করে এবং প্রতিবেশী মডেল, যা ব্যক্তিদের ওভারল্যাপিং পাড়াগুলিতে বরাদ্দ করে, যা সেলুলার জেনেটিক বা বিবর্তনীয় অ্যালগরিদম (সিজিএ বা সিইএ) নামেও পরিচিত। জনসংখ্যার সংশ্লিষ্ট বিভাজনও পদ্ধতির একটি সংশ্লিষ্ট সমান্তরালকরণের পরামর্শ দেয়। এই কারণে, ই. এ-র সমান্তরালকরণের সাথে সম্পর্কিত সাহিত্যে জনসংখ্যার মডেলের বিষয়টিও প্রায়শই আলোচনা করা হয়। দ্বীপের মডেল দ্বীপের মডেলে, যাকে মাইগ্রেশন মডেল বা মোটা দানা মডেলও বলা হয়, বিবর্তন কঠোরভাবে বিভক্ত উপ-জনসংখ্যায় ঘটে। এগুলি সর্বজনীনভাবে সংগঠিত করা যেতে পারে, তবে তা হওয়ার দরকার নেই। সময়ে সময়ে ব্যক্তিদের বিনিময় হয়, যাকে অভিবাসন বলা হয়। একটি বিনিময়ের মধ্যবর্তী সময়কে একটি যুগ বলা হয় এবং এর সমাপ্তি বিভিন্ন মানদণ্ড দ্বারা শুরু করা যেতে পারেঃ যেমন। একটি নির্দিষ্ট সময়ের পরে বা নির্দিষ্ট সংখ্যক পূর্ণ প্রজন্মের পরে, অথবা স্থবিরতার ঘটনার পরে। স্থবিরতা সনাক্ত করা যেতে পারে, উদাহরণস্বরূপ, দ্বীপে নির্দিষ্ট সংখ্যক প্রজন্ম ধরে কোনও ফিটনেসের উন্নতি হয়নি। দ্বীপের মডেলগুলি বিভিন্ন নতুন কৌশলগত মাপকাঠি প্রবর্তন করেঃ উপ-জনসংখ্যার সংখ্যা উপ-জনসংখ্যার আকার দ্বীপগুলির মধ্যে প্রতিবেশী সম্পর্কঃ তারা নির্ধারণ করে যে কোন দ্বীপগুলিকে প্রতিবেশী হিসাবে বিবেচনা করা হয় এবং এইভাবে ব্যক্তিবিশেষ বিনিময় করতে পারে, একটি সাধারণ একমুখী বলয়ের (কালো তীর) চিত্র দেখুন এবং অতিরিক্ত দ্বিমুখী প্রতিবেশী সম্পর্ক (অতিরিক্ত সবুজ তীর) দ্বারা এর সম্প্রসারণ দেখুন। অভিবাসী নির্বাচনঃ এর জন্য অনেক বিকল্প রয়েছে। ই. জি। সেরা ব্যক্তিরা সবচেয়ে খারাপ বা এলোমেলোভাবে নির্বাচিত ব্যক্তিদের প্রতিস্থাপন করতে পারে। অভিবাসনের হারের উপর নির্ভর করে, এটি একবারে এক বা একাধিক ব্যক্তিকে প্রভাবিত করতে পারে। এই পরামিতিগুলির সাহায্যে, নির্বাচনের চাপ যথেষ্ট পরিমাণে প্রভাবিত হতে পারে। উদাহরণস্বরূপ, এটি দ্বীপগুলির আন্তঃসংযোগের সাথে বৃদ্ধি পায় এবং উপ-জনসংখ্যার সংখ্যা বা যুগের দৈর্ঘ্যের সাথে হ্রাস পায়। নেবারহুড মডেল বা সেলুলার বিবর্তনীয় অ্যালগরিদম নেবারহুড মডেল, যাকে ডিফিউশন মডেল বা সূক্ষ্ম দানাদার মডেলও বলা হয়, এমন একটি জনসংখ্যার ব্যক্তিদের মধ্যে একটি টপোলজিকাল নেবারহুড সম্পর্ককে সংজ্ঞায়িত করে যা তাদের ফেনোটাইপিক বৈশিষ্ট্য থেকে স্বাধীন। এই মডেলের মৌলিক ধারণা হল ইএ জনসংখ্যাকে একটি সংযুক্ত গ্রাফ হিসাবে সংজ্ঞায়িত একটি বিশেষ কাঠামো প্রদান করা, যেখানে প্রতিটি শীর্ষ একটি ব্যক্তি যা তার নিকটতম প্রতিবেশীদের সাথে যোগাযোগ করে। বিশেষত, ব্যক্তিরা ধারণাগতভাবে একটি টরয়েডাল জালে সেট করা হয় এবং শুধুমাত্র ঘনিষ্ঠ ব্যক্তিদের সাথে পুনরায় মিলিত হওয়ার অনুমতি দেওয়া হয়। এটি এক ধরনের এলাকার দিকে পরিচালিত করে যা দূরত্ব দ্বারা বিচ্ছিন্নতা নামে পরিচিত। কোনও ব্যক্তির সম্ভাব্য সঙ্গীদের সেটকে তার প্রতিবেশী বা ডেম বলা হয়। সংলগ্ন চিত্রটি দেখায় যে হলুদ চিহ্নিত দুটি ব্যক্তির দুটি সামান্য ওভারল্যাপিং পাড়া দেখিয়ে, যার মাধ্যমে জেনেটিক তথ্য দুটি ডেমের মধ্যে ছড়িয়ে পড়তে পারে। এটি জানা যায় যে এই ধরনের অ্যালগরিদমে, অনুরূপ ব্যক্তিরা ক্লাস্টার এবং এমন কুলুঙ্গি তৈরি করে যা ডেম সীমানা থেকে স্বাধীন এবং বিশেষত, একটি ডেমের চেয়ে বড় হতে পারে। সংলগ্ন গোষ্ঠীগুলির মধ্যে কোনও স্পষ্ট সীমানা নেই, এবং নিকটবর্তী কুলুঙ্গিগুলি সহজেই প্রতিযোগিতামূলক গোষ্ঠীগুলির দ্বারা উপনিবেশ স্থাপন করা যেতে পারে এবং সম্ভবত এই প্রক্রিয়া চলাকালীন সমাধান সামগ্রীগুলিকে একত্রিত করতে পারে। একই সঙ্গে, আরও দূরবর্তী স্থানগুলি আরও ধীরে ধীরে প্রভাবিত হতে পারে। এই ধরনের জনসংখ্যার ই. এ সেলুলার ই. এ (সি. ই. এ) বা সেলুলার জেনেটিক অ্যালগরিদম (সি. জি. এ) নামেও পরিচিত। একটি জনসংখ্যার ব্যক্তিদের সাজানোর জন্য একটি সাধারণভাবে ব্যবহৃত কাঠামো হল একটি 2ডি টরয়েডাল গ্রিড, যদিও মাত্রার সংখ্যা সহজেই বাড়ানো যেতে পারে (3ডি-তে) বা হ্রাস করা যেতে পারে (1ডি-তে, যেমন। একটি আংটি, ডানদিকে চিত্রটি দেখুন)। গ্রিডে কোনও নির্দিষ্ট ব্যক্তির প্রতিবেশীকে জনসংখ্যার অন্যদের থেকে ম্যানহাটনের দূরত্বের পরিপ্রেক্ষিতে সংজ্ঞায়িত করা হয়। মৌলিক অ্যালগরিদমে, সমস্ত পাড়ার একই আকার এবং অভিন্ন আকৃতি রয়েছে। দুটি ডাইমেনশনাল সি. ই. এ-র জন্য সবচেয়ে বেশি ব্যবহৃত দুটি প্রতিবেশী হল এল5 এবং সি9, বাম দিকের চিত্রটি দেখুন। এখানে, L মানে লিনিয়ার এবং C মানে কম্প্যাক্ট। প্রতিটি ডেম একটি প্যানমিকটিক উপ-জনসংখ্যার প্রতিনিধিত্ব করে যার মধ্যে পিতামাতাকে প্রতিস্থাপন করে সঙ্গী নির্বাচন এবং সন্তানদের গ্রহণযোগ্যতা ঘটে। সন্তান গ্রহণের নিয়মগুলি স্থানীয় প্রকৃতির এবং পাড়ার উপর ভিত্তি করেঃ উদাহরণস্বরূপ, এটি নির্দিষ্ট করা যেতে পারে যে সর্বোত্তম সন্তান অবশ্যই পিতামাতার প্রতিস্থাপনের চেয়ে ভাল হতে হবে বা কম কঠোরভাবে, কেবলমাত্র সবচেয়ে খারাপ ব্যক্তির চেয়ে ভাল হতে হবে। প্রথম নিয়মটি অভিজাত এবং দ্বিতীয় অ-অভিজাত নিয়মের তুলনায় উচ্চতর নির্বাচনী চাপ তৈরি করে। অভিজাত ই. এ-তে, জনসংখ্যার সেরা ব্যক্তি সর্বদা বেঁচে থাকে। এই ক্ষেত্রে, তারা জৈবিক মডেল থেকে বিচ্যুত হয়। আশেপাশের এলাকাগুলির ওভারল্যাপ আশেপাশের সীমানা জুড়ে জেনেটিক তথ্যের বেশিরভাগ ধীর বিস্তার ঘটায়, তাই এর নাম বিস্তার মডেল। একটি উন্নততর বংশধরের এখন জনসংখ্যায় ছড়িয়ে পড়ার জন্য প্যানমিক্সির চেয়ে বেশি প্রজন্মের প্রয়োজন। এটি স্থানীয় কুলুঙ্গির উত্থান এবং তাদের স্থানীয় বিবর্তনকে উৎসাহিত করে, এইভাবে দীর্ঘ সময়ের জন্য জিনগত বৈচিত্র্য সংরক্ষণ করে। ফলাফলটি একটি দৌড়ের সময় অনুসন্ধান স্থানের সাথে খাপ খাইয়ে নেওয়া প্রস্থ এবং গভীর অনুসন্ধানের মধ্যে একটি ভাল এবং গতিশীল ভারসাম্য। কুলুঙ্গি সীমানায় কুলুঙ্গি এবং প্রস্থ অনুসন্ধানে এবং সমগ্র জনসংখ্যার বিভিন্ন কুলুঙ্গির বিবর্তনের মাধ্যমে গভীর অনুসন্ধান করা হয়। একই পাড়ার আকারের জন্য, জেনেটিক তথ্যের বিস্তার সি9-এর মতো ব্লকের তুলনায় এল9-এর মতো লম্বা আকৃতির জন্য বড় এবং আবার একটি বলয়ের তুলনায় উল্লেখযোগ্যভাবে বড়। এর অর্থ হল রিং আশেপাশের অঞ্চলগুলি উচ্চ মানের ফলাফল অর্জনের জন্য উপযুক্ত, যদিও এর জন্য তুলনামূলকভাবে দীর্ঘ সময়ের প্রয়োজন হয়। অন্যদিকে, যদি কেউ প্রাথমিকভাবে দ্রুত এবং ভাল, কিন্তু সম্ভবত উপ-অনুকূল ফলাফলের প্রতি আগ্রহী হয়, 2ডি টপোলজিগুলি আরও উপযুক্ত। তুলনা জেনেটিক অ্যালগরিদম, বিবর্তনীয় কৌশল এবং অন্যান্য ই. এ-তে জনসংখ্যার মডেল উভয়ই প্রয়োগ করার সময়, মোট জনসংখ্যাকে উপ-জনসংখ্যায় বিভক্ত করা সাধারণত অকাল একত্রীকরণের ঝুঁকি হ্রাস করে এবং প্যানমিকটিক ই. এ-তে প্রত্যাশার চেয়ে আরও নির্ভরযোগ্য এবং দ্রুত সামগ্রিকভাবে আরও ভাল ফলাফলের দিকে পরিচালিত করে। প্রতিবেশী মডেলগুলির তুলনায় দ্বীপ মডেলগুলির অসুবিধা রয়েছে যে তারা প্রচুর সংখ্যক নতুন কৌশলগত পরামিতি প্রবর্তন করে। সাহিত্যে এই বিষয়ে বিদ্যমান গবেষণা সত্ত্বেও, ব্যবহারকারীর জন্য প্রতিকূল সেটিংসের একটি নির্দিষ্ট ঝুঁকি রয়ে গেছে। অন্যদিকে, আশেপাশের মডেলগুলির ক্ষেত্রে, শুধুমাত্র আশেপাশের আকার নির্দিষ্ট করতে হবে এবং দ্বিমাত্রিক মডেলের ক্ষেত্রে, আশেপাশের চিত্রের পছন্দ যোগ করা হয়। সমান্তরালতা যেহেতু উভয় জনসংখ্যার মডেল জনসংখ্যার বিভাজনকে বোঝায়, তাই তারা একটি ই. এ সমান্তরাল করার ভিত্তি হিসাবে উপযুক্ত। এটি সেলুলার ইএ-র ক্ষেত্রে আরও বেশি প্রযোজ্য, কারণ তারা কেবল তাদের নিজ নিজ বিভাগের সদস্যদের সম্পর্কে স্থানীয়ভাবে উপলব্ধ তথ্যের উপর নির্ভর করে। সুতরাং, চরম ক্ষেত্রে, প্রতিটি ব্যক্তিকে একটি স্বাধীন এক্সিকিউশন থ্রেড বরাদ্দ করা যেতে পারে, যাতে পুরো সি. ই. এ একটি সমান্তরাল হার্ডওয়্যার প্ল্যাটফর্মে চলতে পারে। দ্বীপ মডেলটি সমান্তরালকরণকেও সমর্থন করে, যেমন। প্রতিটি দ্বীপে একটি প্রসেসর বরাদ্দ করে। যদি দ্বীপগুলির উপ-জনসংখ্যা সর্বজনীনভাবে সংগঠিত হয়, তবে একটি প্রজন্মের বংশধরদের সমস্ত মূল্যায়ন অতিরিক্তভাবে সমান্তরাল করা যেতে পারে। বাস্তব-জগতের প্রয়োগগুলিতে মূল্যায়নগুলি সাধারণত সবচেয়ে বেশি সময়সাপেক্ষ অংশ। অবশ্যই, দ্বীপের উপ-জনসংখ্যাকে সি. ই. এ হিসাবে ডিজাইন করাও সম্ভব, যাতে সি. ই. এ সমান্তরাল করার বিষয়ে আগে দেওয়া বিবৃতিগুলি প্রযোজ্য হয়। এইভাবে, উপযুক্ত সমান্তরালতার সাথে শ্রেণিবদ্ধ জনসংখ্যা কাঠামো তৈরি করা যেতে পারে। সমান্তরালকরণের জন্য কেবল তুলনামূলকভাবে ব্যয়বহুল কম্পিউটার ক্লাস্টারই নয়, সস্তা গ্রাফিক্স কার্ডও (জিপিইউ) ব্যবহার করা যেতে পারে। যাইহোক, এটি জোর দেওয়া গুরুত্বপূর্ণ যে সি. ই. এ, বা দ্বীপপুঞ্জ জুড়ে বিতরণ করা জনসংখ্যার সাথে ই. এ, একটি অনুসন্ধান মডেলের প্রতিনিধিত্ব করে যা ঐতিহ্যবাহী ই. এ থেকে অনেক উপায়ে পৃথক। উপরন্তু, তারা ক্রমিক এবং সমান্তরাল উভয় প্ল্যাটফর্মে চলতে পারে, যা এই সত্যকে তুলে ধরে যে মডেল এবং বাস্তবায়ন দুটি ভিন্ন ধারণা। গ্রন্থপঞ্জি এরিক ক্যান্টু-পাজ (2001): দক্ষ এবং সঠিক সমান্তরাল জেনেটিক অ্যালগরিদম (পিএইচডি থিসিস, ইলিনয় বিশ্ববিদ্যালয়, আরবানা-চ্যাম্পেইন, মার্কিন যুক্তরাষ্ট্র)। স্প্রিঙ্গার, নিউইয়র্ক, নিউইয়র্ক। মার্টিনা গর্জেস-শ্লেইটার (1990): জেনেটিক অ্যালগরিদম এবং জনসংখ্যা কাঠামো-একটি ব্যাপক সমান্তরাল অ্যালগরিদম। পিএইচডি থিসিস, ইউনিভার্সিটাট ডর্টমুন্ড, ফ্যাকাল্টাট ফর ইনফরম্যাটিক, জার্মানি। এনরিক আলবা, বার্নাবে ডরোনসোরো (2008): সেলুলার জেনেটিক অ্যালগরিদম। স্প্রিঙ্গার, নিউইয়র্ক, নিউইয়র্ক। ডির্ক সুদহোল্ট (2015): সমান্তরাল বিবর্তনীয় অ্যালগরিদম। জানুস কাক্প্রজিক-এ, উইটোল্ড পেড্রিকজ (সংস্করণ। ): সমান্তরাল বিবর্তনীয় অ্যালগরিদম। স্প্রিঙ্গার, বার্লিন, হাইডেলবার্গ, পৃ. গ্যাব্রিয়েল লুক, এনরিক আলবা (2011): সমান্তরাল জেনেটিক অ্যালগরিদম। স্প্রিংগার, বার্লিন হাইডেলবার্গ। আরও দেখুন সেলুলার অটোমেটন ডুয়াল-ফেজ বিবর্তন বিবর্তন অ্যালগরিদম