Geometric Characteristics of Subproblems in Ising-Machine-Assisted Large Neighborhood Search

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

ولمساعدة الحواسيب على حل هذه الألغاز، بنى العلماء "آلات إيسينج" (Ising machines) خاصة. يمكنك التفكير فيها كأدوات تخمين عالية التقنية وسريعة للغاية. لقد صُممت لتجد "حالة الطاقة الأدنى" للنظام، والتي تعني بلغة الرياضيات إيجاد الحل ذي التكلفة الأقل (مثل المسافة الأقصر). ومع ذلك، هناك عقبة: هذه الآلات لها حد أقصى للحجم. فإذا كان اللغز كبيرًا جدًا، فلن تتمكن الآلة من استيعاب جميع القطع، أو ستصبح جودة تخميناتها غير دقيقة. لذا، بدلًا من مواجهة هذا اللغز الوحشي دفعة واحدة، يستخدم الباحثون استراتيجية تسمى البحث في الجوار الكبير (Large Neighborhood Search - LNS). وهي تشبه أخذ قطعة صغيرة قابلة للمضغ من اللغز، وإصلاح بقية الأجزاء، ثم سؤال الآلة عن إعادة ترتيب تلك القطعة الصغيرة فقط لمعرفة ما إذا كان بإمكانها تحسين الصورة بأكملها. بعد ذلك، تنتقل إلى قطعة أخرى، وتكرر العملية.

ولكن هنا يبرز السؤال المليوني: عندما تقطع تلك القطعة الصغيرة، كيف تقرر أي القطع ستتضمنها؟ هل يهم إذا اخترت حفنة عشوائية من القطع، أم أنك تختار مجموعة تبدو بالفعل كمجموعة مرتبة ومنسجمة؟ قرر فريق من الباحثين في جامعة كيو (Keio University) وضع هذا الاختبار. وتشير نتائجهم إلى أن "شكل" القطعة التي تختارها لا يقل أهمية عن "حجمها".

المواجهة الكبرى بين المشكلات الفرعية

في هذه الدراسة، أقام المؤلفان، ماساشي ياماشيتا وشو تاناكا، منافسة ودية بين طريقتين مختلفتين لتقطيع "مسألة توجيه المركبات" (VRP) لتغذية آلة إيسينج بها. أرادا معرفة ما إذا كانت طريقة اختيار القطع تهم، حتى لو تأكدوا أن كلتا الطريقتين تختاران نفس العدد بالضبط من القطع (المتغيرات الثنائية).

المتنافسان:

1. LNS-K (عدّاء المسارات): تنظر هذه الطريقة إلى الحل الحالي كخريطة. فهي تختار بضع شاحنات توصيل محددة وتأخذ جميع العملاء الذين تزورهم تلك الشاحنات حاليًا. إنها تحترم "المسار" كوحدة واحدة. فإذا كانت شاحنة تسير في حلقة في الشمال، فإن LNS-K تأخذ تلك الحلقة الشمالية بالكامل.
2. LNS-Q (المتغير المتنزه): تتجاهل هذه الطريقة الشاحنات والمسارات. بدلًا من ذلك، تنظر إلى القائمة الخام لمتغيرات الحاسوب (الأصفار والآحاد) وتختار حفنة عشوائية من المتغيرات النشطة. ثم تأخذ أي متغيرات أخرى مرتبطة بها رياضيًا بموجب قواعد المسألة. الأمر يشبه اختيار قطع أحجية عشوائية بناءً على لونها، دون الاهتمام بما إذا كانت تنتمي إلى قسم معين من الصورة.

التجربة:
أجرى الباحثون هاتين الطريقتين على مسألة توصيل تضم 400 عميل باستخدام آلة إيسينج قوية تعمل بوحدة معالجة رسومات (GPU) (واختبارات أصغر على مبرد كمي). وقد طابقوا بعناية "حجم" المشكلات الفرعية، مما ضمن أن LNS-K و LNS-Q كلاهما يحلان قطعًا تحتوي على نفس العدد بالضبط من المتغيرات. كما منحا كلتا الطريقتين نفس الوقت الإجمالي لـ "التفكير" (وقت التلدين/annealing time) لمعرفة أيهما يمكنه إيجاد مسافة قيادة إجمالية أقصر.

النتائج:
كانت النتيجة واضحة ومفاجئة. على الرغم من أن كلتا الطريقتين كانتا تحلان قطعًا بنفس الحجم تمامًا، إلا أن LNS-K وجدت باستمرار حلولاً أفضل من LNS-Q. كانت المسارات التي أنتجتها طريقة "عدّاء المسارات" أقصر، وكان التحسن يحدث بشكل أسرع.

لكن الجزء الأكثر إثارة للاهتمام لم يكن مجرد النتيجة النهائية؛ بل كان في كيفية الوصول إليها. تتبع الباحثون "تباين الموقع" للعملاء المختارين في كل خطوة. تخيل رسم دائرة حول العملاء الذين تزورهم شاحنة ما.

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

ماذا يعني هذا؟

تشير الورقة البحثية إلى أنه عندما تستخدم آلة إيسينج لحل المشكلات الكبيرة خطوة بخطوة، فإن الحجم ليس كل شيء. لا يمكنك فقط القول: "سأعطي الآلة 1,000 متغير لتلعب بها"، وتتوقع أفضل نتيجة. كيفية اختيار تلك الـ 1,000 متغير أمر بالغ الأهمية.

وجد المؤلفون أن بناء المشكلات الفرعية بناءً على البنية الدلالية (semantic structure) للمسألة (مثل إبقاء مسار شاحنة كاملة معًا) يعمل بشكل أفضل من مجرد التقاط متغيرات عشوائية بناءً على القيود الرياضية. يبدو أنه عندما تحافظ على "المسار" سليمًا، يمكن للآلة إجراء تحسينات أذكى وأكثر موضعية، حيث تقوم فعليًا بـ "التقريب" (zooming in) على تجمعات صغيرة من العملاء يمكن إصلاحها، بدلًا من محاولة التعامل مع فوضى مشتتة.

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