শেখা স্থানীয় অনুসন্ধান হিউরিস্টিকসের সীমা উন্মোচন করা: আপনি কি নম্রদের মধ্যে সবচেয়ে শক্তিশালী?

লিঙ্কের টেবিল

বিমূর্ত এবং ভূমিকা

সম্পর্কিত কাজ

সর্বোচ্চ-কাট জন্য মূল্যায়ন

SAT-এর জন্য মূল্যায়ন

সারাংশ এবং আউটলুক, রেফারেন্স

সম্পূরক উপকরণ

বিমূর্ত

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

1। পরিচিতি

NP-হার্ড কম্বিনেটরিয়াল অপ্টিমাইজেশান (CO) সমস্যার জন্য কার্যকর হিউরিস্টিকস বা আনুমানিক অ্যালগরিদম ডিজাইন করা একটি চ্যালেঞ্জিং কাজ, প্রায়ই ডোমেন জ্ঞান এবং ব্যাপক ট্রায়াল-এন্ড-এরর প্রয়োজন হয়। এইভাবে, একটি সমস্যার অন্তর্নিহিত কাঠামোকে কাজে লাগানোর অ্যালগরিদমগুলি শেখার জন্য মেশিন লার্নিংয়ের মাধ্যমে এই চাহিদাপূর্ণ এবং ক্লান্তিকর নকশা প্রক্রিয়াটিকে স্বয়ংক্রিয় করার ধারণাটি গবেষকদের মধ্যে উল্লেখযোগ্য আগ্রহ অর্জন করেছে (বেলো এট আল।, 2016; খলিল এট আল।, 2017; বেঙ্গিও এট আল। ., 2021; ডং এট আল।, 2021)। বিশেষত, এই কাজগুলির একটি উল্লেখযোগ্য অংশ (খলিল এট আল।, 2017; ব্যারেট এট আল।, 2020; ইয়ল্কু এবং পোকজোস, 2019) CO সমস্যার জন্য গ্রাফ নিউরাল নেটওয়ার্ক (GNNs) নিয়োগে মনোনিবেশ করেছে। কম্পিউটেশনাল চাহিদা থাকা সত্ত্বেও, এই GNN-ভিত্তিক পন্থাগুলি নির্দিষ্ট সমস্যার জন্য তৈরি SOTA হিউরিস্টিকসের তুলনায় প্রতিযোগিতামূলক কর্মক্ষমতা প্রদর্শন করেছে।

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

শিক্ষা-ভিত্তিক পদ্ধতির একটি উপসেট (খলিল এট আল।, 2017; ইয়ল্কু এবং পকজোস, 2019; ব্যারেট এট আল।, 2020, 2022) ঐতিহ্যগত হিউরিস্টিকসের কার্যকারিতা বা আচরণকে অন্তর্ভুক্ত করে, সম্ভাব্যভাবে তাকে একীভূত করে উন্নত বা উন্নত কর্মক্ষমতা প্রদান করে। মেশিন লার্নিং উপাদান সঙ্গে নীতি. যদি সমন্বিত হিউরিস্টিকসের সাথে একটি বিস্তৃত তুলনা এবং গভীর শিক্ষার স্থাপত্যের একটি বিমোচন অধ্যয়নের অভাব থাকে, তবে গভীর শিক্ষার স্থাপত্যের নির্দিষ্ট অবদান নির্ধারণ করা চ্যালেঞ্জিং হয়ে ওঠে। ফলস্বরূপ, যদি সমন্বিত হিউরিস্টিকস শক্তিশালী হয়, তবে শেখা হিউরিস্টিকস নির্বিঘ্নে বেসলাইন হিউরিস্টিকসকে ছাড়িয়ে যেতে পারে, যখন গভীর শিক্ষার স্থাপত্যটি সামান্য ভূমিকা পালন করে।

শিক্ষিত হিউরিস্টিকসের আরেকটি বড় কৃতিত্ব (খলিল এট আল।, 2017; ব্যারেট এট আল।, 2020; টোয়েনশফ এট আল।, 2019), প্রাথমিকভাবে একটি নির্দিষ্ট বিতরণ থেকে ছোট এবং নির্দিষ্ট দৃষ্টান্তের উপর প্রশিক্ষিত, যখন থেকে বড় উদাহরণগুলিতে পরীক্ষা করা হয় তখন চিত্তাকর্ষক কর্মক্ষমতা প্রদর্শন করে বিভিন্ন বিতরণ। এই অর্জনটি একটি উল্লেখযোগ্য কৃতিত্ব হিসাবে দাঁড়িয়েছে, শিক্ষা-ভিত্তিক পদ্ধতির নিয়োগের মূল উদ্দেশ্যের সাথে সারিবদ্ধ করে: ব্যাপক কাস্টমাইজেশন এবং ডোমেন-নির্দিষ্ট জ্ঞানের প্রয়োজনীয়তা হ্রাস করা যা প্রায়শই হিউরিস্টিকসের দ্বারা প্রয়োজনীয়। যদিও হাইপারপ্যারামিটার সহ ধ্রুপদী হিউরিস্টিকগুলিও চ্যালেঞ্জের সম্মুখীন হতে পারে যদি সেগুলি একটি নির্দিষ্ট বন্টনের জন্য সূক্ষ্মভাবে তৈরি হয়, তবে তারা বিভিন্ন বিতরণ জুড়ে সাধারণীকরণও করতে পারে। প্রাথমিক অনুসন্ধানটি শাস্ত্রীয় হিউরিস্টিকসের তুলনায় শেখা হিউরিস্টিকস প্রকৃতপক্ষে উচ্চতর সাধারণীকরণ প্রদর্শন করে কিনা তা ঘিরে আবর্তিত হয়। শাস্ত্রীয় হিউরিস্টিকসের বিপরীতে শেখা হিউরিস্টিকসের একটি পুঙ্খানুপুঙ্খ এবং অন্তর্দৃষ্টিপূর্ণ তুলনা শেখা হিউরিস্টিকসের সাধারণীকরণের ক্ষেত্রে মূল্যবান অন্তর্দৃষ্টি প্রদান করে।

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

সুনির্দিষ্টভাবে, আমরা নিম্নলিখিত প্রশ্নগুলি জিজ্ঞাসা করি এবং উত্তর দিই:

1. শেখা হিউরিস্টিক কি অতিরিক্ত প্যারামিটারাইজড হতে পারে? একেবারে। ECO-DQN-এ GNN-কে রৈখিক রিগ্রেশন দিয়ে প্রতিস্থাপন করে এবং ECO-DQN (Barrett et al., 2020) এর বৈশিষ্ট্যগুলির একটি উপসেট ব্যবহার করে যা Tabu Search (Glover, 1990) এর সাথে লিঙ্ক করে, আমরা ECO-DQN-এর একটি ছাঁটাই সংস্করণ প্রবর্তন করি যার নাম SoftTabu। . আমাদের অধ্যয়ন দেখায় যে SoftTabu NPhard ম্যাক্সিমাম-কাট (ম্যাক্স-কাট) সমস্যার জন্য ECO-DQN-এর তুলনায় উচ্চতর কর্মক্ষমতা এবং সাধারণীকরণ প্রদর্শন করে।

2. বেসলাইন পক্ষপাত কি শেখা হিউরিস্টিকসের উচ্চতর কর্মক্ষমতার জন্য দায়ী করা যেতে পারে? হ্যাঁ, আমরা দেখাই যে SoftTabu, একটি ভ্যানিলা শিখেছে হিউরিস্টিক, S2V-DQN (খলিল এট আল।, 2017) ম্যাক্স-কাট সমস্যার জন্য এবং GNNSAT (Yolcu and P´oczos, 2019) বুলিয়ান স্যাটিসফাইবিলিটি (SAT)-এর জন্য ছাড়িয়ে যেতে পারে।

*৩. দৃষ্টান্ত নির্বাচনের পক্ষপাতের কারণে শেখা হিউরিস্টিক কি উচ্চতর সাধারণীকরণ প্রদর্শন করতে পারে?*হ্যাঁ, আমরা দেখাই যে ECO-DQN কঠিন পরিস্থিতিতে দুর্বল সাধারণীকরণ দেখায় এবং সহজেই অনুসন্ধানের জায়গায় আটকে যায়।