আজকের আধুনিক মানুষসহ সামগ্রিক প্রাণিকুল একদিনে পৃথিবীতে আসেনি। লক্ষ লক্ষ বছরের অভিযোজন আর বিবর্তনের ফলস্বরূপ একসময়ের গুহাবাসী প্রাইমেট থেকে আমরা আজকের হোমো স্যাপিয়েন্স। আর এই বিবর্তনের মূল চালিকাশক্তি প্রকৃতি ও পরিবেশ। প্রকৃতি নিয়ত পরিবর্তনশীল। পরিবর্তিত পরিবেশে একমাত্র প্রকৃতিই নির্বাচন করে সমস্ত উদ্ভিদ, প্রাণীসহ অন্যান্য প্রাকৃতিক উপাদানসমূহ। শুধুমাত্র প্রাকৃতিক নির্বাচনের কারণেই টিকে থাকতে না পেরে অনেক সম্প্রদায়ের প্রাণী আজ বিলুপ্ত। আমাদের জীববিজ্ঞান সেই কথাই বলে। কথায় আছে - 'জ্ঞান অভিন্ন, কিন্তু জ্ঞানের প্রয়োগ বিভিন্ন '। তাই প্রাকৃতিক নির্বাচন ও বিবর্তনবাদের তত্ত্বটি শুধু প্রাণীকুলের উৎপত্তি আর অস্তিত্বকেই ব্যাখ্যা করে না, ভৌত বিজ্ঞানের দুনিয়াতেও গাণিতিক ও সায়েন্টিফিক কম্পিউটেশনের কাজে আমরা এই তত্ত্বকে কাজে লাগাতে পেরেছি জেনেটিক অ্যালগরিদম নামে। প্রাকৃতিক নির্বাচনের গল্প এবং বাস্তব জীবনে জেনেটিক অ্যালগরিদমের প্রয়োগ অনুসন্ধান করতেই এখনকার এই ক্ষুদ্র প্রয়াস।

প্রাকৃতিক নির্বাচন ও বিবর্তনবাদ

১৮৫৯ সালের কথা। 'অন দ্য অরিজিন অফ স্পিসিজ' (On the Origin of Species) নামে একটি বই প্রকাশিত হল। বইটির লেখক ব্রিটিশ বিজ্ঞানী চার্লস ডারউইন যিনি দীর্ঘ ৫ বছরের (১৮৩১~১৮৩৬) বিশ্বভ্রমণ শেষে তাঁর অভিজ্ঞতালব্ধ জ্ঞান লিপিবদ্ধ করেন বইটিতে। ভ্রমণকালে তিনি প্রশান্ত মহাসাগরীয় বিভিন্ন দ্বীপ ও দক্ষিণ আমেরিকায় বসবাসরত বিভিন্ন জীব প্রজাতির নমুনা সংগ্রহ করেন এবং পরবর্তীকালে গবেষণা ও পরীক্ষা-নিরীক্ষার ফলাফল অত্যন্ত সরল ভাষায় তাঁর বইতে তুলে ধরেন। বইটির মাধ্যমে ডারউইন প্রকৃতি, বিজ্ঞান-দর্শন এবং সাধারণভাবে জীবকূলের উৎপত্তি ও বণ্টন, জীববৈচিত্র্যে ও ক্রমবিবর্তন বিষয়ে এক নতুন বৈজ্ঞানিক ধারণার সূচনা করেন যা আধুনিককালের বিজ্ঞান সম্প্রদায়ের কাছে মোটামুটিভাবে পরীক্ষিত সত্য।

একটি বায়োলজিক্যাল অণুগল্প:
ডারউইনের প্রাকৃতিক নির্বাচন তত্ত্ব নিয়ে বলতে গেলে একটুখানি বায়োলজির কথা না বললেই নয়। প্রতিটি প্রাণীদেহ অসংখ্য কোষ দিয়ে গঠিত আর প্রতিটি কোষের অপরিহার্য অংশ নিউক্লিয়াস। প্রতিটি প্রাণীকোষের নিউক্লিয়াসে ক্রোমোজোম থাকে আর প্রতিটি ক্রোমোজোমে থাকে অসংখ্য জিন। জিন হল ডিএনএ(DNA) নামক রাসায়নিক অণুর সিকোয়েন্স। জিনগুলোই প্রাণীর শারীরিক ও চারিত্রিক বৈশিষ্ট্যের জন্য দায়ী। প্রতিটি প্রজাতির প্রাণীকোষে একটি নির্দিষ্ট জিনবিন্যাস থাকে যাকে বলে জিনোটাইপ। একই প্রজাতির একাধিক প্রাণীর জিনবিন্যাসের সংমিশ্রণের প্রক্রিয়াটি জেনেটিক রিকম্বিনেশন বা ক্রসওভার(Genetic Recombination) নামে পরিচিত। এই জেনেটিক রিকম্বিনেশনের মাধ্যমেই নতুন বংশধর সৃষ্টি হয়।

প্রাণীকোষে জিন ও ক্রোমোজোমের অবস্থান


অন্যদিকে প্রাণীবৈচিত্র্য সৃষ্টির পিছনে কাজ করে মিউটেশন। মিউটেশন একটি অনিয়মিত(random) প্রক্রিয়া যা প্রাণীর জিনবিন্যাসের আকস্মিক পরিবর্তন সাধন করে। জেনেটিক মিউটেশনের মাধ্যমেই নতুন প্রজাতির প্রাণীর সৃষ্টি হয়। এবারে প্রাকৃতিক নির্বাচনের বিষয়টি খুব সহজ একটি গল্পের মাধ্যমে দেখা যাক।

তৃণভোজী জিরাফকে আমরা সবাই চিনি। এরা এমন অঞ্চলে বাস করে যেখানকার অধিকাংশ গাছগুলো লম্বা এবং মাটি থেকে অনেক উঁচুতে পাতা ধরে। ফলে এই এলাকায় জীবনধারণকারী তৃণভোজী প্রাণীদের পাতার নাগাল পাওয়ার জন্য অবশ্যই গলা লম্বা হতে হবে। আমরা জিরাফের ২ ধরনের পূর্বপুরুষের কথা জানতে পারিঃ লম্বা গলাবিশিষ্ট জিরাফ এবং খাটো গলাবিশিষ্ট জিরাফ। সম্ভবত এক ধরনের মিউটেশনের ফলে লম্বা গলাবিশিষ্ট জিরাফের সৃষ্টি হয়েছিল, আর অন্য এক ধরনের মিউটেশনের ফলে সৃষ্টি হয়েছিল খাটো গলাবিশিষ্ট জিরাফ।

স্বাভাবিকভাবেই যেসব জিরাফের গলা অপেক্ষাকৃত লম্বা, তারাই বেশি বেশি খাদ্য সংগ্রহ করতে পারবে এবং তাদের বেঁচে থাকার সম্ভাবনা ছোট গলার জিরাফের তুলনায় অনেক বেড়ে যাবে। শুধু তাই নয়, নিজেদের মধ্যে লড়াইয়ের সময়েও লম্বা গলাধারী জিরাফ খাটো গলাধারী জিরাফ থেকে এগিয়ে থাকবে। একইভাবে লম্বা গলাধারী জিরাফ খাটো গলাধারী জিরাফের তুলনায় বেশি প্রজনন প্রক্রিয়ায় অংশ নেবে ও লম্বা গলাধারী সন্তানাদির জন্ম দেবে। অন্যদিকে খাদ্যের অভাবে খাটো গলাধারী জিরাফ টিকবে না এবং প্রজননের অভাবে এসব জিরাফের উৎপাদন কমে যাবে। এভাবে কয়েক প্রজন্ম পর দেখা যাবে জিরাফের প্রায় সব সদস্যের গলা লম্বা।

জিরাফের যোগ্য প্রজাতির প্রাকৃতিক নির্বাচন

সুতরাং যে মিউটেশন লম্বা গলাবিশিষ্ট জিরাফের সৃষ্টি করেছিল, সেই মিউটেশন প্রকৃতিতে টিকে থাকার সুবিধা প্রদান করেছিল। আর অন্য মিউটেশনের কারণে প্রকৃতিতে টিকে থাকতে না পেরে খাটো গলাবিশিষ্ট জিরাফের বিলুপ্তি ঘটেছে।

প্রাণীজগতের ইতিহাসে এরকম আরও অনেক নমুনা রয়েছে প্রাকৃতিক নির্বাচনের। ডারউইন তত্ত্বের মূলকথা একটাই - প্রকৃতি ও পারিপার্শ্বিকতার সাথে খাপ খাইয়ে চলার জন্য জিনবিন্যাসের সঠিক পরিবর্তনের মাধ্যমে প্রজন্ম থেকে প্রজন্ম প্রজাতির ক্রমবিকাশ চলতে থাকবে। এটি মূলত ‘survival of the fittest’ মেকানিজম যেখানে একমাত্র যোগ্য প্রজাতিই টিকে থাকবে।

জেনেটিক অ্যালগরিদম

ডারউইনের প্রতিষ্ঠিত প্রাকৃতিক নির্বাচন তত্ত্ব কেবল বায়োলজিতেই সীমাবদ্ধ থাকেনি। প্রাণীকোষের জিনবিন্যাসের পরিবর্তনের মাধ্যমে যোগ্য প্রজাতি নির্বাচন করার নীতিকে গণিত ও কম্পিউটার সায়েন্সের অনেক জটিল সমস্যার সমাধানে কাজে লাগাতে এক বিশেষ ধরনের অ্যালগরিদমের সূচনা হয়েছে - যা জেনেটিক অ্যালগরিদম নামে পরিচিত। প্রাকৃতিক নিয়মের মত বাস্তব জীবনের বিভিন্ন সমস্যার অনেক রকম সীমাবদ্ধতা থাকে। সেসব সীমাবদ্ধতার মধ্যে থেকে যেকোনো সমস্যার উপযুক্ত সমাধান খুঁজতে সাহায্য করে এই জেনেটিক অ্যালগরিদম।

ডারউইন তত্ত্বে আমরা দেখেছি একটি প্রাকৃতিক এলাকায় বসবাসরত পূর্বপুরুষের মধ্যে যারা প্রকৃতির সাথে নিজেদের যোগ্যভাবে মানিয়ে নিতে পারে, তারাই প্রজননে অংশগ্রহণ করে এবং কিছু র‍্যান্ডম মিউটেশনের মাধ্যমে নতুন বংশধর সৃষ্টি হয়। প্রজন্মের পর প্রজন্ম এই প্রক্রিয়া চলতে থাকে যতক্ষণ না পর্যন্ত যোগ্যতম প্রজাতির উৎপত্তি হয়। এই নিরবিচ্ছিন্ন প্রক্রিয়াটাকেই একটা জেনেটিক অ্যালগরিদমের রূপ দেওয়া হয় বিভিন্ন ইটারেশনের(iteration) মাধ্যমে। তাই বলা হয়, জেনেটিক অ্যালগরিদম একটি ইটারেটিভ(iterative) অ্যালগরিদম।

প্রাকৃতিক নির্বাচনের মূল লক্ষ্য যেমন প্রাকৃতিক নিয়মের সাথে যোগ্যতার মাপকাঠিতে রিকম্বিনেশন ও মিউটেশনের মাধ্যমে যোগ্য প্রজাতি নির্বাচন করা, তেমনিভাবে জেনেটিক অ্যালগরিদমের লক্ষ্য হল যোগ্যতার মাপকাঠিতে রিকম্বিনেশন ও মিউটেশনের মত কিছু অপারেশনের মাধ্যমে বাস্তব জীবনের কোন সমস্যার যোগ্যতম সমাধান খুঁজে বের করা। জেনেটিক অ্যালগরিদম নিয়ে আলোচনার শুরুতেই প্রাকৃতিক নির্বাচনে ব্যবহৃত পরিভাষা ও জেনেটিক অ্যালগরিদমের পরিভাষার মধ্যে একটা অ্যানালজি দেওয়ার চেষ্টা করিঃ

প্রাকৃতিক নির্বাচন ও জেনেটিক অ্যালগরিদমের পারিভাষিক অ্যানালজি

এই অ্যানালজির উপর ভিত্তি করে আমরা প্রাকৃতিক নির্বাচনের গল্প থেকে জেনেটিক অ্যালগরিদমের কার্যপদ্ধতি সাজাবো। এবার তাহলে জেনেটিক অ্যালগরিদম ব্যবহার করে সমস্যা সমাধানের পদ্ধতি নিয়ে কথা বলা যাকঃ

সমস্যা চিহ্নিতকরণ:
শুরুতেই আমাদেরকে সমস্যা ও সমস্যার যাবতীয় সীমাবদ্ধতাসমূহ (constraints) চিহ্নিত করতে হবে - যাকে আমরা বলবো আমাদের 'প্রবলেম ডোমেন'। একটা উদাহরণ দিই। ধরা যাক, একটি পাসওয়ার্ড-প্রটেক্টেড স্মার্ট দরজার লক খুলতে হবে। এজন্য বিভিন্ন পাসওয়ার্ড দিয়ে চেষ্টা করতে হবে এই শর্তে যে, পাসওয়ার্ডটি শুধুমাত্র সংখ্যা দিয়ে গঠিত এবং গড়পড়তা একজন মানুষ ১০ ডিজিটের বেশি পাসওয়ার্ড মনে রাখতে পারে না। এভাবে সমস্যা ও সীমাবদ্ধতাসমূহ সনাক্ত করে নিতে হবে।

প্রাথমিক সম্ভাব্য সমাধান (পূর্বপুরুষ):  
এরপর আমাদের সমস্যার কিছু প্রাথমিক সম্ভাব্য সমাধান খুঁজতে হবে। সম্ভাব্য সকল সমাধানের একটি সেট গঠন করতে হবে - প্রাকৃতিক নির্বাচনের পরিভাষায় যারা পূর্বপুরুষ। আমাদের মূল লক্ষ্য হবে জেনেটিক অ্যালগরিদম ব্যবহার করে এই সম্ভাব্য সমাধানগুলোর ক্রমপরিবর্তনের মাধ্যমে উপযুক্ত সমাধান বের করা।

প্রজাতির একেকটি প্রাণীর যেমন একটি নির্দিষ্ট জিনোটাইপ থাকে, সেইরকম আমাদের সমাধান সেটের প্রতিটি সমাধানের একটি নির্দিষ্ট প্যাটার্ন থাকবে যা গঠিত হবে কিছু প্যারামিটার দিয়ে। উদাহরণস্বরূপ - কোনও সমস্যার যদি ২টি অজানা রাশির মান নির্ণয়ের প্রয়োজন হয় যাদের সম্ভাব্য মান হতে পারে (1,3), (2,5) অথবা (0,1), তাহলে আমাদের প্রাথমিক সমাধানের সেটটি হবে {(1,3),(2,5),(0,1)}, যেখানে (1,3), (2,5) এবং (0,1) প্রত্যেকেই একেকটি সম্ভাব্য সমাধান অর্থাৎ জিনোটাইপ। আর 1,3,2,5 এগুলো হচ্ছে সমাধান প্যারামিটার বা জিনোটাইপের জিন। সম্ভাব্য সমাধানের (জিনোটাইপ) দৈর্ঘ্য কত হবে এবং তাতে কতগুলো প্যারামিটার (জিন) থাকবে তা নির্ভর করে সংশ্লিষ্ট সমস্যার উপরে।

ফিটনেস-ভিত্তিক যোগ্য সমাধান নির্বাচন:
ফিটনেসের ভিত্তিতে যেমন প্রজাতির নির্বাচন হয়ে থাকে, তেমনি আমাদের সম্ভাব্য সকল সমাধানের ফিটনেস যাচাই করা হবে যার ভিত্তিতে প্রাপ্ত অধিকতর যোগ্য সমাধান নিয়ে ১ম প্রজন্ম গঠন করা হবে।

প্রতিটি সমস্যার জন্য একটি ফিটনেস ফাংশনকে সংজ্ঞায়িত করতে হবে। এই ফিটনেস ফাংশন বিভিন্ন নামে পরিচিত, যেমনঃ অপটিমাইজেশন সমস্যার সমাধানের ক্ষেত্রে ফিটনেস ফাংশনকে অবজেকটিভ ফাংশন, আবার ইকোনোমিক সমস্যার সমাধানের ক্ষেত্রে ফিটনেস ফাংশনকে কস্ট ফাংশন বলা হয়। উদাহরণস্বরূপ - কোনও সমস্যার ফিটনেস ফাংশনকে যদি এভাবে সংজ্ঞায়িত করা হয়ঃ

তাহলে এই সমস্যার সম্ভাব্য সমাধান (8,2) এর ফিটনেস ভ্যালু ক্যালকুলেট করলে পাই,

প্রবলেম ডোমেনের উপর ভিত্তি করে বিভিন্ন ধরনের সমস্যার জন্য বিভিন্ন রকমের ফিটনেস ফাংশন ব্যবহার করতে হয়। এভাবে সকল সম্ভাব্য সমাধানের ফিটনেস ভ্যালু নির্ণয় করা হয়।

এরপর নির্বাচন। ফিটনেস ভ্যালুর উপর ভিত্তি করে যোগ্য সমাধান নির্বাচনের বেশ কিছু কার্যকরী পদ্ধতি রয়েছে। এর মধ্যে সহজতম 'টুর্নামেন্ট পদ্ধতি' নিয়ে আলোচনা করা যাকঃ

টুর্নামেন্ট পদ্ধতি:
ধরা যাক, আমাদের প্রাথমিক সমাধান সেটের সদস্য সংখ্যা n, অর্থাৎ n সংখ্যক প্রাথমিক সমাধান থেকে ফিটনেস ভ্যালুর ভিত্তিতে যোগ্য সমাধান বাছাই করতে হবে পরবর্তী ধাপের জন্য।

টুর্নামেন্ট পদ্ধতিতে বাছাইকরণের জন্য একটি প্যারামিটার থাকে যা টুর্নামেন্ট প্যারামিটার নামে পরিচিত। যদি টুর্নামেন্ট প্যারামিটারের মান k হয়, তাহলে এটি k-way টুর্নামেন্ট নামে পরিচিত। k-way টুর্নামেন্টের জন্য n সংখ্যক প্রাথমিক সমাধান থেকে সম্পূর্ণ র‍্যান্ডমভাবে k সংখ্যক সমাধান বাছাই করা হয়। অতঃপর এই k সংখ্যক সমাধানের মধ্যে টুর্নামেন্ট অনুষ্ঠিত হয় এবং সর্বোচ্চ ফিটনেস ভ্যালুবিশিষ্ট সমাধানটি টুর্নামেন্টের বিজয়ী বলে ঘোষিত হয় এবং পরবর্তী ধাপের জন্য নির্বাচিত হয়। এভাবে বেশ কয়েকটি টুর্নামেন্ট চালানো হয় এবং প্রতিটি টুর্নামেন্টের মাধ্যমে একটি করে সমাধান নির্বাচিত হয়। প্রাথমিক সমাধান সেটের ভিতর থেকে এভাবে নির্বাচিত সমাধানগুলোকে এরপর ক্রসওভার ধাপে পাঠানো হয়।

ক্রসওভার:
ফিটনেস ভ্যালুর উপর ভিত্তি করে টুর্নামেন্ট পদ্ধতিতে প্রাপ্ত যোগ্য সমাধানগুলো থেকে প্যারেন্ট সমাধান বাছাই করতে হয়, যারা ক্রসওভারে অংশ নেবে। প্যারেন্ট সমাধান অনেকভাবে বাছাই করা যেতে পারে। সবথেকে সহজ হচ্ছে র‍্যান্ডমভাবে প্যারেন্ট সমাধান বাছাই করা। যদি n সংখ্যক যোগ্য সমাধান নির্বাচন করা হয়ে থাকে, তাহলে n/2 সংখ্যক প্যারেন্ট সমাধান বাছাই করা হয়। বাছাইকৃত প্যারেন্ট সমাধানগুলোর প্রতিটি সমাধানযুগলের মধ্যে একবার করে ক্রসওভার সংঘটিত হয়। এবারে ক্রসওভার প্রক্রিয়া নিয়ে বলা যাক।

একেকটি ক্রসওভারের সময় অংশগ্রহণকারী প্যারেন্ট সমাধানযুগলের জিনোটাইপের এক/একাধিক নির্দিষ্ট স্থানে উভয় প্যারেন্টের সমাধান প্যারামিটারগুলোর মধ্যে রিকম্বিনেশন ঘটে। একটি উদাহরণ দেই - ধরা যাক, কোনও সমস্যার প্রাথমিক সমাধান সেটের (1,3,4) এবং (1,0,-1) এই দুটি প্যারেন্ট সমাধান ক্রসওভারে অংশগ্রহণ করেছে। উভয়েই ৩ প্যারামিটারবিশিষ্ট সমাধান। এবারে সমাধানদুটির জিনোটাইপে র‍্যান্ডমভাবে একটি স্থান নির্বাচন করা হল, ধরি ৩। তাহলে উভয় জিনোটাইপের ৩য় স্থানে সমাধানদুটির মধ্যে প্যারামিটার বিনিময় হবে - যার ফলে নতুন সমাধান পাওয়া যাবে। ১ম প্যারেন্ট থেকে (1,3,?) এবং ২য় প্যারেন্ট থেকে (?,?,-1) এর সংমিশ্রণে সৃষ্ট নতুন সমাধানের জিনোটাইপ হবে (1,3,-1)। এভাবে একটিমাত্র স্থানে সৃষ্ট রিকম্বিনেশনকে সিঙ্গেল পয়েন্ট ক্রসওভার বলে। প্রয়োজনে মাল্টিপল পয়েন্ট ক্রসওভার করা যেতে পারে।

দুইটি জিনোটাইপের সিঙ্গেল পয়েন্ট ক্রসওভার


এভাবে প্রতিটি ক্রসওভারের মাধ্যমে একটি করে নতুন সমাধানের আবির্ভাব ঘটে। এই নতুন সমাধানটি চাইল্ড সমাধান নামে পরিচিত।

মিউটেশন:
ক্রসওভারের মাধ্যমে প্রাপ্ত চাইল্ড সমাধানের মধ্যে কেবল প্যারেন্ট সমাধানযুগলের জেনেটিক বৈশিষ্ট্যের প্রতিফলন ঘটেছে। কিন্তু নতুন বৈশিষ্ট্যের সংযোজনের জন্য অবশ্যই মিউটেশনের প্রয়োজন। মিউটেশন অতি অনিয়মিত ও আকস্মিক একটি প্রক্রিয়া। বায়োলজিক্যাল মিউটেশনে বছরের পর বছর ধরে অতি ধীরগতিতে কোষের জিনবিন্যাসে পরিবর্তন যোগ হয়। তেমনিভাবে জেনেটিক অ্যালগরিদমেও খুবই অনিয়মিতভাবে এবং হাল্কাভাবে মিউটেশন যোগ করা হবে। মিউটেশনের জন্য র‍্যান্ডমভাবে নির্বাচিত চাইল্ড সমাধানের এক/একাধিক সমাধান প্যারামিটারের মান পরিবর্তন করা হয় যাদেরকে মিউট্যান্ট প্যারামিটার বলে। এই পরিবর্তন খুবই র‍্যান্ডম ও অনিয়ন্ত্রিতভাবে হতে পারে। তবে আমরা র‍্যান্ডমভাবে নিয়ন্ত্রিত মিউটেশন নিয়ে কাজ করবো।

ডিএনএ অণুর জেনেটিক মিউটেশন

মিউটেশনের জন্য শুরুতে সিদ্ধান্ত নিতে হয় - চাইল্ড সমাধানগুলোর মধ্যে কতগুলো সমাধান প্যারামিটার মিউটেশনের শিকার হবে। নিয়ন্ত্রিত মিউটেশনের জন্য মিউট্যান্ট প্যারামিটারগুলোকে অবশ্যই একটি নির্দিষ্ট ডোমেনের ভিতরে থাকতে হবে।

উদাহরণস্বরূপ - মনে করি, কোনও সমস্যার সমাধান প্যারামিটারগুলো সর্বদা [-10,10] ডোমেনের ভিতরে থাকবে। এখন যদি ক্রসওভারের পর প্রাপ্ত চাইল্ড সমাধানের সংখ্যা ১০ হয় এবং প্রতিটি সমাধানে ৩টি প্যারামিটার হিসাবে সর্বমোট ৩০টি প্যারামিটার থাকে, তাহলে মোটামুটিভাবে এর ১০% বা ৩টি প্যারামিটারকে মিউটেশন করা যায়। এই ৩ টি প্যারামিটারের অবস্থান র‍্যান্ডমভাবে নির্ণয় করা হয় এবং মিউট্যান্ট প্যারামিটারগুলোকে অবশ্যই [-10,10] ডোমেনের ভিতরে র‍্যান্ডমভাবে বাছাই করা হয় যা নিয়ন্ত্রিত মিউটেশনকে নিশ্চিত করে। যেমনঃ (-1,2,0) সমাধানটির ২য় অবস্থানে মিউটেশনের পর প্রাপ্ত সমাধান হতে পারে (-1,7,0)

একটি সমাধান প্যারামিটারের মিউটেশন


এভাবে প্রতি প্রজন্মে একবার করে মিউটেশন সংঘটিত হয়।

নতুন প্রজন্ম গঠন:
টুর্নামেন্ট পদ্ধতিতে নির্বাচনের পর প্রাপ্ত সমাধান সেটের প্যারেন্ট সমাধানগুলোকে ক্রসওভার ও মিউটেশনের পর প্রাপ্ত চাইল্ড সমাধান দিয়ে প্রতিস্থাপন করলে ১ম প্রজন্মের সমাধান সেট পাওয়া যায়। এবারে এই ১ম প্রজন্মের সমাধান সেটের উপরে ফিটনেস-ভিত্তিক নির্বাচন, ক্রসওভার ও মিউটেশন প্রক্রিয়া সম্পন্ন করার পর একইভাবে ২য় প্রজন্মের সমাধান সেট তৈরি হবে। এভাবে নতুন নতুন প্রজন্মের সমাধান সেট পাওয়া যাবে। প্রতিটি নতুন প্রজন্মের সমাধানের ফিটনেস যাচাই করলে দেখা যাবে প্রজন্ম থেকে প্রজন্ম ফিটনেস বাড়ছে। এটাই জেনেটিক অ্যালগরিদমের সার্থকতা।

পরিসমাপ্তি:
প্রতিটি অ্যালগরিদমের একটা সূচনা থাকে, তেমনি থাকে পরিসমাপ্তি। প্রজন্ম থেকে প্রজন্ম ফিটনেস বাড়তে বাড়তে একসময় শেষবিন্দুতে পৌঁছে যায় যেখানে দৃশ্যত ফিটনেসের বৃদ্ধি আর লক্ষ্য করা যায় না। একে বলা হয় স্যাচুরেশন লিমিট (Saturation Limit)। এই পর্যায়ে জেনেটিক অ্যালগরিদমের পরিসমাপ্তি ঘটে এবং সর্বশেষ প্রজন্মের সমাধান সেটের মধ্যে থেকে সর্বাধিক ফিটনেসবিশিষ্ট সমাধানটিকে আমাদের সমস্যার কাঙ্ক্ষিত সমাধান হিসেবে গ্রহণ করা হয়।

সামগ্রিকভাবে জেনেটিক অ্যালগরিদমের ইটারেটিভ কার্যপদ্ধতিটি নিচের ওয়ার্কফ্লো অনুসারে দেখানো যায়ঃ

জেনেটিক অ্যালগরিদমের সাহায্যে সমস্যা সমাধানের ওয়ার্কফ্লো

জেনেটিক অ্যালগরিদম ব্যবহার করে সমস্যার সমাধান

রোবোটিক্স শব্দটির সাথে আমরা কে না পরিচিত! ইলেকট্রিক্যাল ও মেকানিক্যাল ইঞ্জিনিয়ারিং থেকে শুরু করে ন্যানোইলেক্ট্রনিক্স ও কম্পিউটার সায়েন্সের মত বিজ্ঞান ও প্রযুক্তির বিশাল দুনিয়াকে একত্র করেছে এই রোবোটিক্স। রোবোটিক্সের খুব ছোট্ট একটি সমস্যার উদাহরণ দিয়ে আমরা জেনেটিক অ্যালগরিদমের প্রয়োগ ব্যাখ্যা করবো।

রোবোটিক্সের একটি গুরুত্বপূর্ণ শাখা মোশন প্ল্যানিং(Motion Planning) যা রোবটের স্বয়ংক্রিয় চলাচল বা গতিবিধি নিয়ে কাজ করে। আমরা এক ধরনের নেভিগেটর রোবট নিয়ে কথা বলবো। নেভিগেটর রোবটের কাজ হল পারিপার্শ্বিক অবস্থা(যেমন - দৃঢ় প্রতিবন্ধকতা, তাপমাত্রা, রেডিয়েশন ইত্যাদি) বিবেচনা করে গন্তব্যের উদ্দেশ্যে নিরাপদ স্থান বরাবর চলাচল করা।

সমস্যার বিবরণ:
একটি দ্বিমাত্রিক ওয়ার্কস্পেস কল্পনা করা যাক যেখানে রয়েছে একটি নেভিগেটর রোবট। আরও রয়েছে মহামূল্যবান একটি স্বর্ণচাকতি। রোবট ও স্বর্ণচাকতির মাঝখানে রয়েছে বেশ কিছু দৃঢ় প্রতিবন্ধকতা(Solid Obstacles)। রোবটটি যাবতীয় প্রতিবন্ধকতা এড়িয়ে একমাত্র ফ্রি স্পেস বরাবর চলাচল করতে পারে। রোবটটির একমাত্র লক্ষ্য স্বর্ণচাকতিটি অর্জন করা।

রোবট নেভিগেশনের একটি 2-D ওয়ার্কস্পেস

রোবটটিকে মোট ৪ লেভেলের প্রতিবন্ধকতা অতিক্রম করে ৫ম লেভেলে স্বর্ণচাকতিটির কাছে পৌঁছাতে হবে। প্রতিটি লেভেলের প্রতিবন্ধকতা অতিক্রমের জন্য তাকে কিছু রিসোর্স খরচ করতে হবে। রিসোর্স বিভিন্ন রকম হতে পারে, যেমন - মেকানিক্যাল, কম্পিউটেশনাল, ইলেকট্রিক্যাল ইত্যাদি। বিভিন্ন লেভেলের প্রতিবন্ধকতা অতিক্রমের জন্য প্রয়োজনীয় রিসোর্সের পরিমাণকে কিছু ফ্যাক্টর দিয়ে বুঝানো হয়। যেমন - এক লেভেল থেকে আরেক লেভেলে যাবার জন্য একটি নির্দিষ্ট কস্ট ফ্যাক্টর(C) রয়েছে। আবার একই লেভেলের বিভিন্ন সম্ভাব্য পথের রয়েছে বিভিন্ন রিস্ক ফ্যাক্টর(R)। রোবটটিকে কোন একটি সম্ভাব্য পথ দিয়ে একটি লেভেল অতিক্রম করে পরবর্তী লেভেলে যেতে গেলে কস্ট ফ্যাক্টর x রিস্ক ফ্যাক্টর (CxR) পরিমাণ রিসোর্স খরচ করতে হবে। শুধু তাই নয়, একই লেভেলের বিভিন্ন সম্ভাব্য পথের জন্য রয়েছে কিছু রিওয়ার্ড পয়েন্টসও(P)।

ওয়ার্কস্পেসের বিভিন্ন লেভেল ও সম্ভাব্য পথসমূহ

প্রতিটি লেভেলের কস্ট ফ্যাক্টর এবং বিভিন্ন সম্ভাব্য পথের সাথে সংশ্লিষ্ট রিস্ক ফ্যাক্টর ও রিওয়ার্ড পয়েন্টসের তালিকা নিচের টেবিলে দেওয়া হলঃ

লক্ষণীয় যে, ৫ম লেভেলে রয়েছে একমাত্র স্বর্ণচাকতিটি যেটিকে অর্জন করার সাথে সাথে 100 রিওয়ার্ড পয়েন্ট পাওয়া যাবে এবং ৪র্থ লেভেল থেকে ৫ম লেভেলে স্বর্ণচাকতি পর্যন্ত পৌঁছানোর জন্য কস্ট ফ্যাক্টর 50। এই লেভেলের কোনও রিস্ক ফ্যাক্টর নেই।

এখানে মোট সম্ভাব্য রুটের সংখ্যা 2 x 3 x 3 x 2 = 36 টি। উদাহরণস্বরূপ - যদি ১ম লেভেলের ২য় পথ, ২য় লেভেলের ১ম পথ, ৩য় লেভেলের ৩য় পথ এবং ৪র্থ লেভেলের ১ম পথ বরাবর যাওয়া হয়, তাহলে রুটটি হবে (2,1,3,1)। এক্ষেত্রে প্রয়োজনীয় মোট রিসোর্সের পরিমাণ = 5x8 + 10x11 + 20x9 + 40x12 + 50 = 860 এবং মোট প্রাপ্ত রিওয়ার্ডের পরিমাণ = 10+8+20+10+100 = 148। অর্থাৎ এই রুটে রোবটটি 860 ইউনিট রিসোর্স খরচ করবে এবং 148 টি রিওয়ার্ড পয়েন্ট পাবে। তবে আমরা আশা করি এর থেকেও কম রিসোর্সে বা অধিক রিওয়ার্ড পয়েন্ট অর্জন করে গন্তব্যে পৌঁছানো সম্ভব।

তাই আমাদের লক্ষ্য - রোবটটির জন্য একটি নিরবচ্ছিন্ন অপটিমাম পথের পরিকল্পনা করা যেখানে সে অপেক্ষাকৃত কম রিসোর্সে ও অধিক রিওয়ার্ড অর্জন করে গন্তব্যে পৌঁছাতে পারে। এটি খুব সহজ একটি অপটিমাইজেশন প্রবলেম। এবারে জেনেটিক অ্যালগরিদম প্রয়োগ করে সমস্যাটি সমাধানের দিকে যাওয়া যাক।

সমাধান:
আমাদের সমস্যার চিহ্নিতকরণ মোটামুটি শেষ। এবারে প্রাথমিক সম্ভাব্য সমাধান বাছাই করা যাক।

আমরা ৩৬টি সম্ভাব্য রুটের মধ্যে যেকোনো ৬টি রুটকে সম্ভাব্য সমাধান হিসেবে বাছাই করি। যেমনঃ (1,3,3,2),(2,1,1,2),(2,2,2,2),(2,3,3,1),(1,3,3,1) এবং (2,1,1,1)

প্রতিটি রুটের সাথে নির্দিষ্ট কস্ট ফ্যাক্টর, রিস্ক ফ্যাক্টর ও রিওয়ার্ড পয়েন্ট আছে যার ভিত্তিতে আমরা রুটের ফিটনেস গণনা করবো। একটি রুট অপর আরেকটি রুট থেকে ভাল নাকি খারাপ সেটা বিবেচনা করবো একটি অনুপাতের মাধ্যমেঃ

অনুপাতটির মান যত কম হবে, রুটটি ততই ভাল বা রুটটির ফিটনেস ততই বেশি। সুতরাং এই অনুপাতটির উপর ভিত্তি করে আমাদের ফিটনেস ফাংশনকে বাছাই করবো এভাবেঃ

আমাদের লক্ষ্য থাকবে এই ফাংশনের মানকে মিনিমাইজ করা। যে রুটের জন্য এই ফাংশনের সর্বনিন্ম মান পাওয়া যাবে, সেটিই হবে কাঙ্ক্ষিত রুট।

১ নং ফাংশন অনুযায়ী সম্ভাব্য সমাধান সেটের ফিটনেস ভ্যালু গণনা করলে পাই, 0.1596, 0.1597, 0.1519, 0.1457, 0.1512 এবং 0.1503

এরপর টুর্নামেন্ট পদ্ধতিতে যোগ্য সমাধান নির্বাচন। আমরা 2-way টুর্নামেন্ট পদ্ধতি ব্যবহার করবো অর্থাৎ একেকটি টুর্নামেন্টের জন্য ২টি করে সমাধান র‍্যান্ডমভাবে বাছাই করা হবে। যেহেতু আমাদের প্রাথমিক সম্ভাব্য সমাধান ৬টি, তাই আমরা ৬টি টুর্নামেন্ট আয়োজন করবো এবং ফিটনেস ভ্যালুর ভিত্তিতে ৬টি যোগ্য সমাধান বাছাই করে নেবো। ধরে নেই, টুর্নামেন্টের পর প্রাপ্ত যোগ্য সম্ভাব্য সমাধান সেট = (2,1,1,2), (2,1,1,1), (1,3,3,1), (1,3,3,2), (2,2,2,2)

এবারে প্যারেন্ট সমাধান নির্বাচন। র‍্যান্ডমভাবে ৩টি প্যারেন্ট সমাধান নির্বাচন করি, যেমন - (2,1,1,1),(1,3,3,1),(2,2,2,2)। তাহলে অবশিষ্ট নন-প্যারেন্ট সমাধানঃ (1,3,3,2),(2,1,1,2)। একইসাথে ৩টি ক্রসওভার পজিশন র‍্যান্ডমভাবে নির্বাচন করি, যেমন - 4,4,3। নির্বাচিত পজিশন অনুযায়ী প্যারেন্ট সমাধানগুলোর মধ্যে ক্রসওভারের পর প্রাপ্ত চাইল্ড সমাধান - (2,1,1,1),(1,3,3,2),(2,2,1,1)

অতঃপর মিউটেশন। চাইল্ড সমাধান সেটে মোট সমাধান প্যারামিটারের সংখ্যা = 12। যেহেতু, 12 x 10% = 1.2 ⋍ 1, সুতরাং ১টি প্যারামিটারকে র‍্যান্ডমভাবে নির্বাচন করে তার মিউটেশন করা হবে। যেমন - ৬ নম্বর প্যারামিটারকে র‍্যান্ডমভাবে নির্বাচন করা হল যা ২য় চাইল্ড সমাধানের ২য় প্যারামিটার। উক্ত প্যারামিটারকে [1,3] ডোমেনে মিউটেশন করা হলে প্রাপ্ত চাইল্ড সমাধান -  (2,1,1,1),(1,1,3,2),(2,2,1,1)

এবারে মিউটেশনের পর প্রাপ্ত চাইল্ড সমাধানগুলোকে নন-প্যারেন্ট সমাধানগুলোর সাথে একীভূত করলেই আমাদের ১ম প্রজন্মের সমাধান সেট প্রস্তুতঃ (2,1,1,2),(2,1,1,1),(1,1,3,2),(1,3,3,2),(2,2,1,1)

১ নং ফাংশন অনুযায়ী ১ম প্রজন্মের সমাধান সেটের ফিটনেস গণনা করলে পাই, 0.1597, 0.1503, 0.1605, 0.1596 এবং 0.1514

দেখা যাচ্ছে, আমাদের প্রাথমিক সমাধান সেটের ফিটনেস অপেক্ষা ১ম প্রজন্মের সমাধান সেটের সর্বোচ্চ ফিটনেস বেশি অর্থাৎ আমরা যোগ্যতর সমাধান অর্জনের পথে এগোচ্ছি। এভাবে আমরা ১০ম প্রজন্ম প্রাপ্তি পর্যন্ত গণনা করবো। পরবর্তী প্রজন্মের সমাধান সেটের হিসাবগুলো নিচের ডেটা টেবিলে লিপিবদ্ধ করা হলঃ

* পূর্বপুরুষকে 0 তম প্রজন্ম হিসাবে বিবেচনা করা হয়েছে
* মিউট্যান্ট প্যারামিটারকে লাল রঙ দ্বারা চিহ্নিত করা হয়েছে

প্রতিটি প্রজন্মের বিপরীতে সর্বোচ্চ ফিটনেস ভ্যালুর গ্রাফ অঙ্কন করলে পাই,

প্রজন্ম vs সর্বোচ্চ ফিটনেস গ্রাফ

গ্রাফ ও ডেটা টেবিল থেকে দেখা যাচ্ছে যে, ৪র্থ প্রজন্মের সমাধান সেটে আমরা সর্বোচ্চ ফিটনেসবিশিষ্ট সমাধান পেয়েছি যার ফিটনেস ভ্যালু 0.1677 এবং কাঙ্ক্ষিত রুটটি (1,2,1,2)

রোবট নেভিগেশনের কাঙ্ক্ষিত অপটিমাম রুট

জেনেটিক অ্যালগরিদমের বিবিধ ব্যবহারসমূহ

আমাদের সমস্যাটিতে মোট সম্ভাব্য রুট ছিল ৩৬টি, যাকে বলে সার্চ স্পেস(Search Space)। চাইলে সহজেই ৩৬টি রুটের জন্য আলাদা করে কস্ট ও রিওয়ার্ড পয়েন্ট হিসাব করে অপটিমাম রুট নির্ণয় করা যেত। তাই স্বাভাবিকভাবেই মনে হতে পারে এ ধরনের সমস্যার ক্ষেত্রে জেনেটিক অ্যালগরিদমের মত কোনও কিছু কেন দরকার। কারণ সমস্যাটির সার্চ স্পেস অত্যন্ত ক্ষুদ্র। কিন্তু বাস্তবে বিজ্ঞান ও প্রযুক্তির দুনিয়ায় এমন অনেক সমস্যা বিরাজ করে যাদের সার্চ স্পেস অনেক অনেক বড়। যেমন - আর্টিফিশিয়াল ইন্টেলিজেন্স(Artificial Intelligence) সম্পন্ন স্মার্ট রোবটের জন্য মানব-মস্তিষ্কের আদলে আর্টিফিশিয়াল নিউরাল নেটওয়ার্ক(Artificial Neural Network) তৈরি করা হয় যেখানে হাজারের উপরে প্যারামিটার থাকতে পারে। এত অধিক সংখ্যক প্যারামিটারের নির্বাচন ও অপটিমাইজেশনে জেনেটিক অ্যালগরিদমকে কাজে লাগানো যেতে পারে। শুধু তাই নয়, ইমেজ প্রসেসিং ও অ্যানালাইসিসে জেনেটিক অ্যালগরিদমের প্রয়োগ রয়েছে।জেনেটিক অ্যালগরিদম ব্যবহার করে অপটিমাম পদ্ধতিতে একটি ছবির গুরুত্বপূর্ণ ফিচারগুলো বাছাই করে ছবির পরিবর্ধন ও সংস্করণ করে অধিকতর অ্যানালাইসিসের জন্য প্রস্তুত করা হয়।

জেনেটিক অ্যালগরিদম কোনো ডিটারমিনিস্টিক অ্যালগরিদম(Deterministic Algorithm) নয়। এটি একটি ডাইন্যামিক অ্যালগরিদম(Dynamic Algorithm) যা সম্পূর্ণভাবে র‍্যান্ডমনেসের (randomness) উপরে প্রতিষ্ঠিত। তাই বড় সার্চ স্পেসবিশিষ্ট প্রবলেম ডোমেনের ক্ষেত্রে সঠিক ফিটনেস ফাংশন নির্বাচনসাপেক্ষে জেনেটিক অ্যালগরিদম অত্যন্ত ভাল কাজ করে। তত্ত্বীয়ভাবে এটা কিভাবে কাজ করে জানতে হলে সবথেকে সুন্দর ও জটিল কিছু গাণিতিক ব্যাপার-স্যাপার দিয়ে মস্তিষ্কের নিউরোনগুলোকে অনুরণিত করার প্রয়োজন হবে যা আমাদের এই আলোচনার বাইরে।

রোবোটিক্স ও আর্টিফিশিয়াল ইন্টেলিজেন্সের বাইরেও কম্পিউটেশনের জগতে ক্রিপ্টোগ্রাফিক অ্যানালাইসিস(Cryptographic Analysis), গেম থিওরী(Game Theory), অপটিমাম নেটওয়ার্ক রাউটিং সিস্টেম(Optimum Network Routing System) ডিজাইনসহ জীববিজ্ঞান ও ইকোনোমিক্সের বিভিন্ন ক্ষেত্রে জেনেটিক অ্যালগরিদম ব্যবহৃত হয়। এছাড়াও সফটওয়্যার টেস্টিংয়ে মিউটেশন টেস্টিংসহ অপটিমাম হোয়াইট বক্স বা স্ট্রাকচারাল টেস্টকেস(White-box/Structural Test Case) নির্বাচনে জেনেটিক অ্যালগরিদমের ব্যবহার আছে।

রেফারেন্স বই

ডারউইনের প্রাকৃতিক নির্বাচন ও বিবর্তনের তত্ত্ব কিভাবে ভৌত বিজ্ঞান ও প্রযুক্তির দুনিয়াতে কমপ্লেক্স আর্টিফিশিয়াল সিস্টেমের ডিজাইন ও ডেভেলপমেন্টে  কাজ করতে পারে তার গাণিতিক ফ্রেমওয়ার্ক সম্পর্কে বিস্তারিত জানার জন্য প্রফেসর জন হল্যান্ডের ‘Adaptation in Natural and Artificial Systems’ বইটি অবশ্য পাঠ্য।

যে কোনও জিজ্ঞাসা বা পরামর্শের জন্য কমেন্ট করুন অথবা ইমেইল করুন [email protected] ঠিকানায়