Residual-Guided Simulated Annealing for Multi-Dimensional Subset Sum

في عالم علوم الحاسوب، هناك فئة من الألغاز تُعرف باسم مسألة مجموع المجموعات الفرعية (subset sum problem). تخيل أن لديك مجموعة كبيرة من العناصر، لكل منها وزن محدد، ويُطلب منك إيجاد مجموعة منها تجمع أوزانها لتصل إلى رقم مستهدف دقيق. تبدو هذه المهمة بسيطة عندما يكون هناك هدف واحد فقط للوصول إليه، لكن الصعوبة تتضاعف عندما يتعين عليك تلبية عدة أهداف مختلفة في آن واحد. هذه النسخة الأكثر صعوبة تُسمى مسألة المجموع الفرعي متعدد الأبعاد، أو في المجتمع البحثي، مسألة "تقسيم السوق" (Market Split). وهي تطلب من الحاسوب تقسيم مجموعة من العناصر إلى مجموعتين بحيث يتطابق إجمالي الوزن لكل مجموعة مع مجموعة محددة من الأهداف عبر فئات متعددة في وقت واحد. هذه الألغاز ليست مجرد تمارين أكاديمية؛ فهي تمثل تحديًا جوهريًا في مجال الأمثلة (optimization)، حيث تختبر حدود قدرة الحواسيب على التنقل في مشهد معقد من الاحتمالات لإيجاد تطابق مثالي. ولعقود من الزمن، كافح الباحثون مع هذه المسائل لأن عدد التشكيلات الممكنة ينمو بسرعة كبيرة لدرجة أن أقوى الحواسيب الفائقة قد تضل الطريق، عاجزة عن إيجاد الحل المثالي الوحيد وسط مليارات المنعطفات الخاطئة.

قام باحث يدعى سريكوتان إل. إس. (Sreekuttan L. S.) من شركة بلوك كوانتوم (Bloq Quantum) في الهند، مؤخرًا، بمعالجة هذا التحدي باستخدام نهج جديد مصمم ليس لإيجاد الإجابة المثالية، بل للوصول إلى نتيجة قريبة جدًا منها عندما تكون الإجابة المثالية بعيدة المنال. تركز الدراسة على مجموعة محددة من الألغاز الصعبة من مكتبة قياسية تُستخدم لاختبار طرق الأمثلة. وبدلاً من محاولة حل المسألة عن طريق فحص كل الاحتمالات، وهو أمر مستحيل للمجموعات الكبيرة، طور الباحث طريقة تسمى "التلدين المحاكي الموجه بالبواقي" (Residual-Guided Simulated Annealing). لفهم كيفية عمل ذلك، تخيل أنك تحاول موازنة ميزان به عدة أوزان مختلفة. إذا مال الميزان إلى أحد الجانبين، فأنت تعرف بالضبط مقدار الوزن الذي ينقصك. تستخدم هذه الطريقة ذلك "المقدار المفقود"، أو الخطأ، لتوجيه خطوتها التالية. فعندما يقرر الحاسوب استبدال عنصر في مجموعته الحالية بعنصر آخر، فإنه لا يختار عشوائيًا؛ بل يحسب بالضبط ما يجب أن يكون عليه العنصر الجديد لإلغاء الخطأ، ثم يبحث عن العنصر المتاح الذي يقترب أكثر من ذلك الاستبدال المثالي. إنه بحث ذكي وتوجيهي يصحح مساره باستمرار بناءً على مدى بعده عن الهدف.

اختبر الباحث هذه الطريقة الجديدة مقابل النهج القديمة الأكثر عشوائية وضد العديد من البرامج الحاسوبية القوية الأخرى. أُجريت التجارب على ثماني نسخ مختلفة من مسألة "تقسيم السوق"، تتراوح من الأحجام الصغيرة التي يمكن التحكم فيها إلى نسخة رائدة تُعتبر صعبة للغاية. في الجولة الأولى من الاختبارات، وُضعت الطريقة الجديدة في مواجهة طريقة تقوم بتبديلات عشوائية دون استخدام الخطأ لتوجيه خياراتها. أظهرت النتائج ميزة واضحة للنهج الموجه. وفي أصعب حالة اختبار، تركت الطريقة العشوائية متوسط خطأ يبلغ حوالي 104 وحدات، بينما قللت الطريقة الموجهة الجديدة ذلك الخطأ إلى حوالي 100 وحدة. ورغم أن هذا الفرق قد يبدو صغيرًا، إلا أنه في سياق هذه الألغاز، يمثل تحسنًا كبيرًا في إيجاد حل أقرب بكثير إلى الكمال. كما اختبرت الدراسة مسارًا كاملاً يتضمن هذه الطريقة الموجهة جنبًا إلى جنب مع بعض الخطوات الداعمة الأخرى، مما أدى إلى خفض الخطأ بشكل أكبر إلى حوالي 100.37 وحدة في المتوسط. ومن الأهمية بمكان أن أيًا من عمليات التشغيل في هذه المرحلة الأولية لم تجد حلاً مثاليًا، لكن الطريقة الموجهة أنتجت باستمرار نتائج كانت أقرب بكيد من المحاولات العشوائية.

ولرؤية مدى صمود هذه الطريقة في منافسة أوسع، وسع الباحث الدراسة لتشمل نطاقًا أوسع من الحدود الزمنية وقارن الطريقة الجديدة مع ستة برامج أخرى راسخة، بما في ذلك بعض البرامج المصممة لإيجاد إجابات دقيقة. أُجريت الاختبارات بحد زمني صارم قدره 25 ثانية. في هذا السباق، أثبتت الطريقة الموجهة الجديدة أنها موثوقة للغاية. وبينما فشلت العديد من البرامج القوية الأخرى في تقديم أي إجابة صالحة للاستخدام ضمن الحد الزمني، أنتجت الطريقة الموجهة نتيجة باستمرار. وعند تمديد الحد الزمني إلى 300 ثانية، استمرت الطريقة الموجهة في التحسن، حيث وصلت إلى متوسط خطأ قدره 36.54 وحدة. وبالمقارنة، أنتجت طريقة تعتمد على نوع مختلف من البحث العشوائي خطأ قدره 263.46 وحدة، بينما استقرت خوارزمية جينية شهيرة أخرى عند 72.27 وحدة. تمكنت الطريقة الموجهة من إيجاد حل أقرب بكثير إلى الهدف مقارنة بمنافسيها، رغم أنها لم تدّع إيجاد الإجابة الدقيقة والمثالية.

تفرق الدراسة بوضوح بين إيجاد حل مثالي وإيجاد حل جيد جدًا. يصرح الباحث صراحةً بأن هذه الطريقة لا تثبت وجود حل مثالي أو عدم وجوده؛ بل هي ببساطة تجد حلاً قريبًا جدًا من المثالية. في عالم هذه الألغاز، يعني "الحل المثالي" تطابق الأرقام تمامًا، بينما يعني "الحل شبه الممكن" (near-feasible) أن الأرقام قريبة جدًا. الطريقة الجديدة ممتازة في إيجاد هذه الحلول شبه المثالية بسرعة. إنها تعمل كأداة قوية للوصول بالحاسوب إلى نقطة تكون فيها قريبة جدًا من الإجابة، والتي يمكن استخدامها كنقطة انطلاق لطرق أخرى قد تصل في النهاية إلى الحل الدقيق. يسلط البحث الضوء على أنه بالنسبة لأصعب النسخ من هذه الألغاز، حيث غالبًا ما تنفد من البرامج الدقيقة الوقت أو الذاكرة، يوفر هذا النهج الموجه وسيلة موثوقة للوصتمع من الهدف في غضون ثوانٍ.

تشير النتائج إلى أن استخدام الخطأ في الحساب لتوجيه البحث هو استراتيجية فعالة للغاية. فمن خلال النظر في ما هو مفقود والبحث عن العنصر الذي يسد تلك الفجوة بأفضل شكل، يتجنب الحاسوب التسكع بلا هدف الذي يميز الطرق العشوائية القديمة. هذا النهج لا يحل محل الحاجة إلى البرامج الدقيقة عندما تكون الإجابة المثالية مطلوبة، ولكنه يوفر طريقة قوية وشفافة للتعامل مع الحالات الأكثر صعوبة حيث تعاني الطرق الدقيقة. وتخلص الدراسة إلى أنه بالنسبة لهذه الأنواع المحددة من الألغاز الصعبة، تنتج الطريقة الموجهة باستمرار نتائج ذات خطأ منخفض ومحققة وقابلة للتكرار. إنها تقدم معيارًا جديدًا لكيفية مقاربة هذه المشكلات، مما يظهر أنه حتى عندما يكون الحل المثالي بعيد المنال، فإن البحث الذكي والموجه يمكن أن يقترب بشكل ملحوظ، مما يوفر أداة قيمة للباحثين والمهندسين العاملين في تحديات الأمثلة المعقدة.