বিষয়বস্তুতে চলুন

গাণিতিক কাম্যতমকরণ

উইকিপিডিয়া, মুক্ত বিশ্বকোষ থেকে

গণিত, কম্পিউটার বিজ্ঞান এবং অর্থশাস্ত্রে কাম্যতমকরণ (ইংরেজি: Optimization) বা গাণিতিক প্রোগ্রামিং বলতে কোনো সেটে বিদ্যমান অনেকগুলো বিকল্প থেকে সবচেয়ে ভালো বা সর্বোচ্চ সন্তুষ্টি প্রদানকারী বিকল্পটি বেছে নেওয়াকে বোঝায়।

সাধারণত এটি এমন সব সমস্যা নিয়ে গবেষণাকে বোঝায়, যেখানে একটি নির্দিষ্ট সেট থেকে বাস্তব বা পূর্ণসংখ্যা চলকের মান সুশৃঙ্খলভাবে নির্বাচনের মাধ্যমে কোনো বাস্তব ফাংশনের সর্বোচ্চ বা সর্বনিম্ন মান বের করার চেষ্টা করা হয়।

অপ্টিমাইজেশন সমস্যা

[সম্পাদনা]

অপ্টিমাইজেশন সমস্যাগুলোকে চলকগুলো অবিচ্ছিন্ন নাকি বিচ্ছিন্ন, তার ওপর ভিত্তি করে দুটি ভাগে ভাগ করা যায়:

একটি অপ্টিমাইজেশন সমস্যাকে নিচের উপায়ে উপস্থাপন করা যায়:

প্রদত্ত: কোনো সেট A থেকে বাস্তব সংখ্যার সেটে একটি ফাংশন f:A→ℝ
নির্ণেয়: x0 ∈ A এমন একটি উপাদান, যেন সমস্ত x ∈ A-এর জন্য f(x) ≥ f(x)0 হয় ("সর্বনিম্নকরণ") অথবা f(x) ≤ f(x)0 হয় ("সর্বোচ্চকরণ")।

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

যেহেতু নিচের সম্পর্কটি বৈধ:

f(𝐱0)≥f(𝐱)⇔−f(𝐱0)≤−f(𝐱),

তাই কেবল সর্বনিম্নকরণ সমস্যা সমাধান করাই যথেষ্ট। তবে বিপরীতভাবে কেবল সর্বোচ্চকরণ সমস্যা বিবেচনা করাও বৈধ।

পদার্থবিজ্ঞানের ক্ষেত্রে এই কৌশলে তৈরি সমস্যাগুলোকে অনেক সময় শক্তি সর্বনিম্নকরণ বলা হয়।[১] এখানে ফাংশন f-এর মানকে মডেলকৃত সিস্টেমের শক্তি হিসেবে বিবেচনা করা হয়। মেশিন লার্নিংয়ে, একটি কস্ট ফাংশন ব্যবহার করে ডেটা মডেলের গুণমান ক্রমাগত মূল্যায়ন করা প্রয়োজন, যেখানে সর্বনিম্ন মানটি সম্ভাব্য কাম্য প্যারামিটার এবং কাম্য (সর্বনিম্ন) ত্রুটিকে নির্দেশ করে।

সাধারণত A হলো ইউক্লিডীয় স্থান ℝn-এর একটি উপসেট, যা প্রায়শই কিছু সীমাবদ্ধতা, সমতা বা অসমতার মাধ্যমে নির্দিষ্ট করা থাকে। f-এর ডোমেইন A-কে 'অনুসন্ধান স্থান' বা 'পছন্দের সেট' বলা হয়, আর A-এর উপাদানগুলোকে 'সম্ভাব্য সমাধান' বলা হয়।

ফাংশন f-কে বিভিন্ন ক্ষেত্রে 'অবজেক্টিভ ফাংশন', 'ক্রাইটেরিয়ন ফাংশন', 'লস ফাংশন', 'কস্ট ফাংশন' (সর্বনিম্নকরণের ক্ষেত্রে),[২] 'ইউটিলিটি ফাংশন' বা 'ফিটনেস ফাংশন' (সর্বোচ্চকরণের ক্ষেত্রে) অথবা কোনো কোনো ক্ষেত্রে 'এনার্জি ফাংশন' বা 'এনার্জি ফাংশনাল' বলা হয়। একটি সম্ভাব্য সমাধান যা অবজেক্টিভ ফাংশনকে সর্বনিম্ন (বা সর্বোচ্চ) করে, তাকে 'কাম্য সমাধান' বলা হয়।

গণিতে প্রচলিত অপ্টিমাইজেশন সমস্যাগুলো সাধারণত সর্বনিম্নকরণের মাধ্যমে প্রকাশ করা হয়।

একটি 'স্থানীয় সর্বনিম্ন' x* হলো এমন একটি উপাদান, যার জন্য এমন একটি δ > 0 বিদ্যমান যে:

∀𝐱∈Awhere‖𝐱−𝐱∗‖≤δ,

এই শর্তে f(x*) ≤ f(x) সম্পর্কটি সত্য হয়। অর্থাৎ, x*-এর আশেপাশের অঞ্চলে ফাংশনের সমস্ত মান ওই বিন্দুটির মানের চেয়ে বড় বা সমান। স্থানীয় সর্বোচ্চের সংজ্ঞা একইভাবে দেওয়া হয়।

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

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

ইতিহাস

[সম্পাদনা]

কাম্যতমকরণের প্রাচীনতম কৌশলগুলোর মধ্যে একটি হলো গাউসের ঢালুতম-অবতরণ পদ্ধতি। ঐতিহাসিকভাবে কাম্যতমকরণের গবেষণার একটি বড় অংশ রৈখিক বিশ্লেষণ তথা রৈখিক প্রোগ্রামিংয়ের সাথে জড়িত। ১৯৪৭ সালে জর্জ ডানৎসিখের উদ্ভাবিত সিম্প্লেক্স অ্যালগরিদম রৈখিক প্রোগ্রামিং গবেষণার একটি মাইলফলক হিসেবে বিবেচিত হয়।

নিচে কাম্যতমকরণ গবেষণায় গুরুত্বপূর্ণ অবদান রাখা গণিতবিদদের একটি তালিকা দেওয়া হলো:

প্রধান শাখাক্ষেত্রসমূহ

[সম্পাদনা]
  • উত্তল প্রোগ্রামিংয়ের মূল বিষয় হলো উত্তল লক্ষ্য ফাংশন, যার সীমাবদ্ধতাগুলো একটি উত্তল সেট তৈরি করে। উত্তল প্রোগ্রামিংকে অরৈখিক প্রোগ্রামিংয়ের একটি বিশেষ শাখা এবং রৈখিক সমস্যা ও উত্তল দ্বিঘাত প্রোগ্রামিংয়ের সাধারণ রূপ হিসেবে দেখা হয়।
    • রৈখিক প্রোগ্রামিং হলো একধরনের উত্তল সমস্যা, যেখানে লক্ষ্য ফাংশনটি রৈখিক এবং সীমাবদ্ধতাগুলোকে কেবল রৈখিক সমতা বা অসমতা দ্বারা প্রকাশ করা হয়। এই সেটটি সীমিত হলে তা একটি বহুতলকের আকার ধারণ করে।
    • দ্বিতীয় ক্রমের কোণক প্রোগ্রামিংয়ে বিশেষ ধরনের দ্বিঘাত সমস্যা নিয়ে আলোচনা করা হয়।
    • প্রায়নির্ধারিত প্রোগ্রামিং (semidefinite programming) হলো উত্তল প্রোগ্রামিংয়ের একটি শাখা, যেখানে চলকগুলো হলো প্রায়নির্ধারিত ম্যাট্রিক্স।
    • কোণক প্রোগ্রামিং হলো উত্তল প্রোগ্রামিংয়ের একটি সাধারণ শাখা। রৈখিক, দ্বিতীয় ক্রমের কোণক এবং প্রায়নির্ধারিত প্রোগ্রামিং—এই প্রত্যেকটিকেই কোণক প্রোগ্রামিংয়ের বিশেষ রূপ হিসেবে দেখা যায়।
    • জ্যামিতিক প্রোগ্রামিং হলো একধরনের কাম্যতমকরণ কৌশল, যেখানে লক্ষ্য এবং অসমতা ফাংশনগুলো পসিনমিয়াল এবং সমতা ফাংশনগুলো মনমিয়াল। জ্যামিতিক প্রোগ্রামিংকে সরাসরি উত্তল প্রোগ্রামিং আকারে সমাধান করা না গেলেও, সেটিকে উত্তল প্রোগ্রামিং সমস্যায় রূপান্তর করা সম্ভব।
  • পূর্ণসংখ্যা প্রোগ্রামিং হলো রৈখিক প্রোগ্রামিংয়ের একটি ধরন, যেখানে কিছু বা সবগুলো চলক কেবল পূর্ণসংখ্যায় মান গ্রহণ করে। এর ফলে সমস্যাটি আর উত্তল প্রোগ্রামিংয়ের আওতায় থাকে না এবং সাধারণ রৈখিক প্রোগ্রামিংয়ের তুলনায় এটি সমাধান করা বেশ কঠিন।
  • দ্বিঘাত প্রোগ্রামিংয়ে লক্ষ্য ফাংশনটি দ্বিঘাতবিশিষ্ট হয় এবং সমতা ও অসমতাগুলো রৈখিক থাকে। দ্বিঘাত পদটির বিশেষ একটি আকারের ক্ষেত্রে সমস্যাটি একটি উত্তল প্রোগ্রামিং সমস্যায় পরিণত হয়।
  • অরৈখিক প্রোগ্রামিংয়ের গবেষণায় এমন সমস্যা নিয়ে আলোচনা করা হয়, যেখানে লক্ষ্য ফাংশন বা সীমাবদ্ধতা—অথবা উভয়ই—অরৈখিক হয়।
  • অনির্ধারিত প্রোগ্রামিং গবেষণায় এমন সমস্যা বিবেচনা করা হয়, যেখানে সীমাবদ্ধতা বা প্যারামিটারগুলো দৈব চলকের ওপর নির্ভর করে।
  • রোবাস্ট প্রোগ্রামিং অনির্ধারিত প্রোগ্রামিংয়ের মতোই কাম্যতমকরণ সমস্যার উপাত্তের অনিশ্চয়তা নিয়ে কাজ করে। তবে এখানে দৈব চলক বিবেচনা না করে উপাত্তের ত্রুটিকে গুরুত্ব দিয়ে সমস্যার সমাধান করা হয়।
  • কম্বিনেটোরিয়াল সেরাঅনুকুলকরণ
  • অসীমমাত্রিক সেরাঅনুকুলকরণ
  • অধি-আবিষ্করণী (Metaheuristic) গবেষণায় সমস্যার ব্যাপারে খুব সামান্য অনুমান করা হয় এবং এ ধরনের কৌশল সমাধান-ক্ষেত্রের বিশাল অঞ্চলে অনুসন্ধান চালাতে পারে। তবে অধি-আবিষ্করণী পদ্ধতি সর্বদা সর্বোত্তম সমাধান পাওয়ার নিশ্চয়তা দেয় না।

কিছু উপক্ষেত্রে কৌশলগুলো মূলত গতিশীল প্রেক্ষাপটে অপ্টিমাইজেশনের জন্য নকশা করা হয়; অর্থাৎ সময়ের সাথে সিদ্ধান্ত গ্রহণের জন্য:

বহু-উদ্দেশ্য অপ্টিমাইজেশন

[সম্পাদনা]

একটি অপ্টিমাইজেশন সমস্যায় একাধিক উদ্দেশ্য যোগ করলে জটিলতা বৃদ্ধি পায়। উদাহরণস্বরূপ, কোনো কাঠামোগত নকশা অপ্টিমাইজ করার সময় আপনি এমন একটি নকশা চাইতে পারেন যা একই সঙ্গে হালকা এবং দৃঢ়। যেহেতু এই দুটি উদ্দেশ্য পরস্পরবিরোধী, তাই এখানে একটি সমঝোতা বা ট্রেড-অফ বিদ্যমান। একটি সবচেয়ে হালকা নকশা, একটি সবচেয়ে দৃঢ় নকশা এবং ওজন ও দৃঢ়তার মধ্যে ভারসাম্যপূর্ণ অসংখ্য নকশা থাকতে পারে। এই সমঝোতামূলক নকশাগুলোর সেটকে প্যারেটো সেট বলা হয়। সেরা নকশাগুলোর ওজনের বিপরীতে দৃঢ়তা চিত্রিত করলে যে বক্ররেখা তৈরি হয়, তাকে প্যারেটো ফ্রন্টিয়ার বলা হয়।

কোনো নকশাকে প্যারেটো সর্বোত্তম বলা হয় যদি সেটি অন্য কোনো নকশা দ্বারা অধীনস্থ না হয়। একটি প্যারেটো সর্বোত্তম নকশাকে অন্তত একটি দিক থেকে অন্য কোনো নকশার চেয়ে ভালো হতে হবে। যদি কোনো নকশা সব দিক থেকেই অন্য কোনো নকশার চেয়ে খারাপ হয়, তবে সেটি অধীনস্থ এবং প্যারেটো সর্বোত্তম নয়।

বহু-মোডাল অপ্টিমাইজেশন

[সম্পাদনা]

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

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

তথ্যসূত্র

[সম্পাদনা]
  1. ↑ Hartmann, Alexander K; Rieger, Heiko (২০০২)। Optimization algorithms in physics। Citeseer।
  2. ↑ Erwin Diewert, W. (২০১৭), "Cost Functions", The New Palgrave Dictionary of Economics (ইংরেজি ভাষায়), London: Palgrave Macmillan UK, পৃ. ১–১২, ডিওআই:10.1057/978-1-349-95121-5_659-2, আইএসবিএন ৯৭৮-১-৩৪৯-৯৫১২১-৫, সংগ্রহের তারিখ ১৮ আগস্ট ২০২৪