Meta-heuristic হল একটি primary field of stochastic optimization.
Stochastic optimization হল the general class of algorithm and techniques যা randomness use করে optimal বা optimal এর কাছাকাছি solution বের করে আনে।
•যে সকল problem এ আমরা আগে থেকে বুঝতে পারি না যে, optimal solution কেমন হতে পারে।
•যে সকল problem এ আমরা জানি না, principal way তে কিভাবে solution এর দিকে আগাব।
•যে সকল problem এ, brute-force search impossible কারন search space অনেক বড়।
কিন্তু আমাদের কাছে ঐ problem এর কোন candidate solution দিলে test করে দেখতে পাড়ব solution তা কত ভাল।সে সকল problem এ meta-heuristic use করা হয়।
“Meta-heuristics are applied to I know it when I see it problem”
এরকম কোন problem এর সামনে পরলে সবচেয়ে simplest thing যা করতে পারি তা হল random search, আমরা random solution বের করব যতক্ষণ আমাদের কাছে time আছে, সবচেয়ে best solution return করব।
কিন্তু random search এর আগে একটা alternative পথ দেখতে পারি।
আমরা প্রথমে random solution নেই। এই solution একটা ছোট এবং random modification করি। এখন নতুন solution test করি।
যদি দেখি current solution better হয় then old solution ফেলে দিব। যদি না হয় তাহলে current solution ফেলে দিব।
এখন বর্তমান হাতে যে solution আসে তার উপর ছোট ও random modification করব। এভাবে যতক্ষণ পারা যায় repeat করতে থাকব।
এই পধতি কে বলে hill-climbing.এটি হল একটি simple meta-heuristic algorithm.
"It exploits a heuristic belief about your space of candidate solutions which is usually true for many problems: that similar solutions tend to behave similarly (and tend to have similar quality), so small modifications will generally result in small, well-behaved changes in quality, allowing us to “climb the hill” of quality up to good solutions. This heuristic belief is one of the central defining features of meta-heuristics: indeed, nearly all meta-heuristics are essentially elaborate combinations of hill-climbing and random search."
Meta-heuristic দারা যে সকল problem tackle করা যায় সে সকল problem হল sub-class of inverse problem।
Inverse problem কে আমারা এভাবে কল্পনা করতে পাড়ি, মনে করি আমাদের কাছে একটি test function আছে f() যেটা parameter হিসেবে একটি candidate solution কে নিবে এবং ওই solutionটির একটি assessment বা fitness return করবে।
কিন্তু এটা মোটামোট impossible উপরের functionটির inverse function f-1() তৈরি করা যা assessment বা fitness parameter হিসেবে নেয় এবং এমন একটি candidate solution return করবে যার ঐ assessment or fitness থাকবে।
Optimization methods(Meta-heuristic) design করা হয়েছে inverse problem কে overcome করতে।
Stochastic optimization হল the general class of algorithm and techniques যা randomness use করে optimal বা optimal এর কাছাকাছি solution বের করে আনে।
•যে সকল problem এ আমরা আগে থেকে বুঝতে পারি না যে, optimal solution কেমন হতে পারে।
•যে সকল problem এ আমরা জানি না, principal way তে কিভাবে solution এর দিকে আগাব।
•যে সকল problem এ, brute-force search impossible কারন search space অনেক বড়।
কিন্তু আমাদের কাছে ঐ problem এর কোন candidate solution দিলে test করে দেখতে পাড়ব solution তা কত ভাল।সে সকল problem এ meta-heuristic use করা হয়।
“Meta-heuristics are applied to I know it when I see it problem”
এরকম কোন problem এর সামনে পরলে সবচেয়ে simplest thing যা করতে পারি তা হল random search, আমরা random solution বের করব যতক্ষণ আমাদের কাছে time আছে, সবচেয়ে best solution return করব।
কিন্তু random search এর আগে একটা alternative পথ দেখতে পারি।
আমরা প্রথমে random solution নেই। এই solution একটা ছোট এবং random modification করি। এখন নতুন solution test করি।
যদি দেখি current solution better হয় then old solution ফেলে দিব। যদি না হয় তাহলে current solution ফেলে দিব।
এখন বর্তমান হাতে যে solution আসে তার উপর ছোট ও random modification করব। এভাবে যতক্ষণ পারা যায় repeat করতে থাকব।
এই পধতি কে বলে hill-climbing.এটি হল একটি simple meta-heuristic algorithm.
"It exploits a heuristic belief about your space of candidate solutions which is usually true for many problems: that similar solutions tend to behave similarly (and tend to have similar quality), so small modifications will generally result in small, well-behaved changes in quality, allowing us to “climb the hill” of quality up to good solutions. This heuristic belief is one of the central defining features of meta-heuristics: indeed, nearly all meta-heuristics are essentially elaborate combinations of hill-climbing and random search."
Meta-heuristic দারা যে সকল problem tackle করা যায় সে সকল problem হল sub-class of inverse problem।
Inverse problem কে আমারা এভাবে কল্পনা করতে পাড়ি, মনে করি আমাদের কাছে একটি test function আছে f() যেটা parameter হিসেবে একটি candidate solution কে নিবে এবং ওই solutionটির একটি assessment বা fitness return করবে।
কিন্তু এটা মোটামোট impossible উপরের functionটির inverse function f-1() তৈরি করা যা assessment বা fitness parameter হিসেবে নেয় এবং এমন একটি candidate solution return করবে যার ঐ assessment or fitness থাকবে।
Optimization methods(Meta-heuristic) design করা হয়েছে inverse problem কে overcome করতে।
No comments:
Post a Comment