🤖 machine learning

Machine Learning for Two-Stage Graph Sparsification for the Travelling Salesman Problem

تقترح هذه الورقة إطار عمل لتبسيط الرسوم البيانية يتكون من مرحلتين، يجمع بين اتحاد خوارزميات البحث عن أقرب $\alpha$ ( $\alpha$ -Nearest) و POPMUSIC مع نموذج تعلم آلي لتقليل كثافة الرسم البياني المرشح بكفاءة مع الحفاظ على تغطية عالية للمسار الأمثل عبر نماذج متنوعة لمسألة البائع المتجول، متفوقة بذلك على الأساليب العصبية الحالية أحادية المرحلة والمقيدة بالمسافات الإقليدية.

المؤلفون الأصليون: Bo-Cheng Lin, Yi Mei, Mengjie Zhang

نُشر 2026-04-23

📖 4 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: Bo-Cheng Lin, Yi Mei, Mengjie Zhang

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل أنك سائق توصيل يحاول العثور على أسرع مسار مطلق لزيارة 500 مدينة مختلفة ثم العودة إلى منزله. هذه هي مسألة "البائع المتجول" الشهيرة (Traveling Salesman Problem - TSP).

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

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

المشكلة: معضلة "الاعتدال" (Goldilocks Dilemma)

التحدي يكمن في إيجاد القائمة المختصرة المثالية:

طرق كثيرة جداً: سيصبح الكمبيوتر مثقلاً ويستغرق وقتاً طويلاً لحل اللغز.
طرق قليلة جداً: قد تحذف بالخطاً ذلك "الاختصار السري" الوحيد الذي يؤدي إلى المسار المثالي، وتجد نفسك عالقاً مع حل سيء.

لفترة طويلة، استخدم الخبراء قاعدتين مختلفتين (Heuristics) لإنشاء هذه القوائم المختصرة:

قاعدة "ألفا" (Alpha Rule): جيدة في الحفاظ على سلامة المسار، لكن القائمة تظل طويلة جداً.
قاعدة "بوب" (Pop Rule): تصنع قائمة قصيرة جداً، لكنها أحياناً تكون هجومية للغاية وتقطع طرقاً مهمة، خاصة عندما تصبح الرحلة ضخمة (أكثر من 500 مدينة).

لم تنجح قاعدة واحدة بشكل مثالي في كل موقف.

الحل: استراتيجية "شبكة الأمان" المكونة من مرحلتين

اقترح مؤلفو هذه الورقة عملية ذكية مكونة من خطوتين، تشبه فريقاً من محققين يعملان معاً.

المرحلة الأولى: "شبكة الأمان" (تعظيم الاستدعاء - Maximize Recall)

بدلاً من محاولة اختيار أفضل الطرق فوراً، قرروا أن يكونوا حذرين للغاية. لقد أخذوا القوائم المختصرة من كلا قاعدتي "ألفا" و"بوب" ودمجوها معاً.

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

المرحلة الثانية: "الفلتر الذكي" (التقليم المتعلم - Learned Pruning)

الآن، لدينا قائمة طويلة وآمنة. نحتاج إلى تقليمها دون قطع الأشياء الخاطئة. وهنا يأتي دور تعلم الآلة (Machine Learning).

السلاح السري: لأنهم دمجوا القائمتين في المرحلة الأولى، أصبح لديهم دليل خاص. هم يعرفون ما إذا كان الطريق قد ظهر في قائمة كلا الدليلين أم في قائمة دليل واحد فقط.
التشبيه: تخيل أنك حارس بوابة في ملهى ليلي. لديك قائمة بكبار الشخصيات (الطرق الموجودة في كلتا القائمتين) وقائمة بالزبائن المعتادين (الطرق الموجودة في قائمة واحدة فقط).
- كبار الشخصيات (VIPs) من المؤكد تقريباً أنهم سيكونون جزءاً من الحفلة المثالية. احتفظ بهم.
- الزبائن المعتادون هم مزيج من الجيد والسيئ. يعمل الذكاء الاصطناعي هنا كحارس بوابة ذكي، ينظر إلى الزبائن المعتادين ويقرر من يسمح لهم بالدخول ومن يطردهم.
النتيجة: يتعلم الذكاء الاصطناعي أن "الطرق الموجودة في القائمتين = احتفظ بها" و"الطرق الموجودة في قائمة واحدة فقط = ربما تُقطع". إنه يقلم الزوائد، تاركاً قائمة قصوة وفعالة، تضمن بنسبة 99.7% وجود المسار المثالي.

لماذا يعد هذا أمراً هاماً؟

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

الخلاصة

لم يحاول المؤلفون بناء روبوت يحل اللغز بأكمله من الصفر. بدلاً من ذلك، بنوا فلترًا ذكيًا يأخذ أفضل ما في طريقتين موجودتين، يجمعهما ليكون آمناً، ثم يستخدم ذكاءً اصطناعياً بسيطاً لتقليم الزوائد.

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

إليك ملخص تقني مفصل لورقة البحث بعنوان "تعلم الآلة لتبسيط الرسوم البيانية ثنائي المرحلة لمسألة البائع المتجول" من إعداد لين، ومي، وتشانغ.

1. بيان المشكلة

لا تقوم الحلول عالية الأداء لمسألة البائع المتجول (TSP)، مثل LKH (Lin-Kernighan-Helsgaun)، بالبحث عبر جميع الحواف الممكنة ( $N(N-1)/2$ ). بدلاً من ذلك، تعمل على رسم بياني مرشح (candidate graph)، وهو مجموعة فرعية مبسطة من الحواف.

المقايضة: يجب أن يكون الرسم البياني المرشح نادراً بما يكفي لسرعة البحث، وكثيفاً بما يكفي للاحتفاظ بالحواف التي تنتمي إلى الجولة المثلى.
محدودية الاستدلالات الحالية:
- $\alpha$ -Nearest: قوية في الاستدعاء (الحفاظ على الحواف المثلى) عبر مختلف المقاييس، لكنها تنتج رسوماً بيانية كثيفة، مما يبطئ عمل الحلّال (solver).
- POPMUSIC: ينتج رسوماً بيانية نادرة جداً، لكنه يعاني من تدهور كبير في الاستدعاء عند المقاييس الكبيرة ( $N > 200$ ) وعند التوزيعات المكانية الصعبة.
- نهج تعلم الآلة الحالي: معظم طرق تعلم الآلة لتبسيط الرسم البياني في مسألة TSP تعمل على الرسم البياني الكامل. وهذا أمر مكلف حاسوبياً، ويتوسع بشكل سيء، وغالباً ما يقتصر على المسافات الإقليدية (EUC_2D)، مما يجعله يفشل في التعميم على أنواع المسافات الأخرى في TSPLIB (مثل GEO، وATT، وMAN_2D).

السؤال الجوهري: كيف يمكن تقليل كثافة رسم بياني مرشح عالي الاستدعاء دون التخلص من حواف الجولة المثلى الحرجة، مع الحفاظ على القدرة على التعميم عبر مقاييس المسافات وأحجام الحالات المختلفة؟

2. المنهجية: تبسيط الرسم البياني ثنائي المرحلة

يقترح المؤلفون خط إنتاج ثنائي المرحلة يفصل بين تعظيم الاستدعاء وتقليل الكثافة.

المرحلة الأولى: الاتحاد الاستدلالي (تعظيم الاستدعاء)

بدلاً من الاعتماد على استدلال واحد، تبني الطريقة رسماً بيانياً مرشحاً أساسياً ( $G_b$ ) عن طريق أخذ اتحاد استدلالين رائدين:
$E_{union} = E_{\alpha\text{-Nearest}} \cup E_{\text{POPMUSIC}}$

الهدف: تحقيق تغطية شبه مثالية (استدعاء) لحواف الجولة المثلى.
الرؤية الأساسية: هذا الاتحاد يخلق إشارة مصدر-أصل (source-provenance signal). لكل حافة في $G_b$ ، يعرف النموذج ما إذا كانت قد اختيرت بواسطة $\alpha$ -Nearest فقط، أو POPMUSIC فقط، أو كليهما. الحواف الموجودة في كلا الاستدلالين هي إحصائياً مرشحة بقوة لتكون جزءاً من الجولة المثلى.

المرحلة الثانية: التقليم المتعلم (تقليل الكثافة)

يتم تدريب نموذج تعلم آلة لتصنيف الحواف في $G_b$ وتقليم الحواف ذات الدرجات الأقل لإنتاج رسم بياني نهائي مبسط ( $\tilde{G}$ ).

الميزات: يستخدم النموذج ميزات غير مرتبطة بنوع المسافة (الرتب، النسب، الإحصاءات المحلية، وأصل المصدر) بدلاً من الهندسة الإحداثية. هذا يسمح للنموذج بالعمل على EUC_2D وATT وGEO وMAN_2D.
النماذج المختبرة: الانحدار اللوجستي (LR)، وآلات ناقلات الدعم الخطية (Linear SVM)، وXGBoost.
قاعدة التقليم: تُستخدم قاعدة على مستوى العقدة بدلاً من عتبة عالمية. لكل عقدة، يتم ترتيب الحواف حسب الدرجة، ويحدد توزيع softmax محلي كيفية الاحتفاظ بالحواف بناءً على عتبة كتلة تراكمية ( $\eta$ )، مما يضمن حداً أدنى من الدرجة (مثلاً 2) للحفاظ على جدوى الجولة.
بيانات التدريب: تم التدريب على حالات بحجم $N=100$ باستخدام الجولات المثلى الدقيقة (المحسوبة بواسطة Concorde) كعلامات (labels).

3. المساهمات الرئيسية

خط إنتاج ثنائي المرحلة: أول نهج يطبق التقليم المتعلم على رسم بياني مرشح استدلالي مبسط بالفعل بدلاً من الرسم البياني الكامل. هذا يتجنب تعقيد $O(N^2)$ لمعالجة جميع الحواف.
إشارة مصدر-أصل: يثبت أن دمج استدلالين يخلق ميزة قوية (ما إذا كانت الحافة في تقاطع كليهما) مما يجعل مشكلة التعلم قابلة للتطبيق. حتى الانحدار اللوجستي البسيط يحقق أداءً عالياً لأن هذه الإشارة مهيمنة للغاية.
القدرة على التعميم: الطريقة غير مرتبطة بنوع المسافة. فهي تعمل عبر أربعة أعراف مسافات في TSPLIB وخمسة توزيعات مكانية دون الحاجة لإعادة التدريب أو ضبط المعلمات.
القابلية للتوسع: تتوسع الطريقة لتصل إلى أحجام حالات أكبر بـ 5 مرات من حجم التدريب ( $N=500$ مقابل $N=100$ )، متفوقة على الاستدلالات أحادية المرحلة التي تتدهور عند التوسع.

4. النتائج التجريبية

أُجريت التجارب على 20 عائلة من مسائل TSP (4 أنواع مسافات $\times$ 5 توزيعات) بأحجام $N \in \{50, 100, 200, 500\}$ .

تقليل الكثافة: تقلل الطريقة ثنائية المرحلة كثافة الرسم البياني المرشح بنسبة 37% إلى 47% مقارم بالاتحاد الأساسي.
- عند $N=500$ ، ينخفض عدد الحواف من $\approx 5.93N$ (الاتحاد) إلى $\approx 3.14N$ (الاتحاد + XGBoost).
الاحتفاظ بالتغطية: رغم التقليم الشديد، تحتفظ الطريقة بـ $\ge 99.69\%$ من حواف الجولة المثلى عبر جميع الأحجام وأنواع المسافات.
أداء الحلّال (Solver):
- يؤدي تمرير الرسوم البيانية المقلمة إلى LKH إلى تسريع زمن الحل بمقدار 1.20 $\times$ إلى 1.28 $\times$ مقارنة باتحاد المجموعة غير المقلمة.
- فجوة المثالية (Optimality Gap): لا تزداد الفجوة؛ بل في كثير من الحالات، تنخفض قليلاً، مما يشير إلى أن الحواف المقلمة كانت زائدة عن الحاجة.
المقارنة مع الطرق العصبية:
- بالمقارنة مع أحدث المبددات العصبية (DIFUSCO، AttGCN، DIMES) على حالات EUC_2D.
- تحقق الطريقة المقترحة تغطية أعلى (تصل إلى 99.95% مقابل 96-98% للطرق العصبية) وكثافة أقل.
- والأهم من ذلك، تعمل الطريقة المقترحة على المسافات غير الإقليدية حيث تفشل الطرق العصبية.
دراسات الاستئصال (Ablation Studies):
- تطبيق تعلم الآلة مباشرة على الرسم البياني الكامل (تخطي المرحلة الأولى) غير فعال بسبب عدم توازن الفئات والافتقار إلى التوجيه الهيكلي.
- تقليم POPMUSIC وحده ضار لأن الرسم البياني هو بالفعل شديد الندرة؛ الاتحاد ضروري لتوفيد حواف "آمنة" للنموذج ليتعلم منها.

5. الأهمية والقيود

الأهمية:

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

القيود:

الطبيعة التجريبية: لا توجد ضمانات نظرية بأن الحواف المثلى سيتم الحفاظ عليها.
تكلفة التدريب: تتطلب جولات مثلى دقيقة (عبر Concorde) للتدريب، مما يحد من قابليتها للتوسع لأحجام $N$ كبيرة جداً أثناء مرحلة التدريب.
الحالات الصعبة: يتدهور الأداء قليلاً في توزيعات "الممر" (Corridor) عند المقاييس الكبيرة ( $N=500$ )، حيث يصعب تمييز الحواف الطويلة والمهمة عالمياً باستخدام الميزات المحلية.
الاختبار الاصطناعي: تم التقييم على توزيعات اصطناعية؛ وقد يحتاج التحقق من أداء الطريقة على حالات TSPLIB الكلاسيكية (التي قد تمتلك خصائص هيكلية مختلفة) إلى مزيد من الاختبار.

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