نحو تمثيل عام لمشكلات التوليف للمقاربات المبنية على التعلم

Léo Boisvert

Hélène Verhaeghe

Quentin Cappart

مُلَخَّص

في السنوات الأخيرة، كان هناك اهتمام متزايد باستخدام المقاربات المبنية على التعلم لحل مشكلات التوليف، سواء بطريقة نهائية أو بالتعاون مع خوارزميات التحسين التقليدية. في كلا السيناريوهين، يكمن التحدي في ترميز مشكلات التوليف المستهدفة إلى هيكل متوافق مع خوارزمية التعلم. لقد اقترحت العديد من الأعمال السابقة تمثيلات محددة للمشكلة، غالبًا على شكل رسم بياني، للاستفادة من مزايا الشبكات العصبية البيانية. ومع ذلك، تفتقر هذه المقاربات إلى العمومية، حيث لا يمكن نقل التمثيل بسهولة من مشكلة توليفية إلى أخرى. على الرغم من أن بعض المحاولات قد أُجريت لسد هذه الفجوة، إلا أنها لا تزال تقدم عمومية جزئية فقط. استجابة لهذا التحدي، يدعو هذا البحث إلى التقدم نحو تمثيل عام كامل لمشكلات التوليف للمقاربات المبنية على التعلم. النهج الذي نقترحه يتضمن بناء رسم بياني عن طريق تحليل أي قيد من مشكلة التوليف إلى شجرة تحليل نحوي مجردة والتعبير عن العلاقات (مثل متغير مشترك في قيد) من خلال الحواف. علاوة على ذلك، نقدم بنية شبكة عصبية بيانية قادرة على التعلم بكفاءة من هذا التمثيل. الأداة المقدمة تعمل على مشكلات التوليف المعبر عنها بتنسيق XCSP3، معالجة جميع القيود المتاحة في مسابقة المسار المصغر لعام 2023. تظهر النتائج التجريبية على أربع مشكلات توليفية أن بنيتنا تحقق أداءً مماثلاً للهندسات المخصصة مع الحفاظ على العمومية. تتوفر شيفرتنا ونماذجنا المدربة للجمهور على https://github.com/corail-research/learning-generic-csp.

مُقَدِّمَة

لقد جذبت التحسين التوافقي انتباه علماء الحاسوب منذ نشأة هذا المجال. وقد كانت المشكلات التوافقية، مثل مشكلة البائع المتجول أو الإشباع البولياني، محور عقود من البحث في مجتمع علوم الحاسوب. يمكننا الآن حل مشكلات كبيرة من هذه الأنواع بكفاءة باستخدام الطرق الدقيقة (Applegate2009) والإجراءات التقريبية (36b9628e7a874d208624584d8a470985). الإجراءات التقريبية هي إجراءات مصممة يدويًا تجسد معرفة وحدس الخبراء حول بنية المشكلات التي يتم تطبيقها عليها. بينما حققت الإجراءات التقريبية نجاحًا وتطبيقات في حل المشكلات التوافقية إما كعملية حل مباشرة أو مدمجة في إجراء بحث، فقد جذب ارتفاع التعلم العميق في العديد من المجالات المختلفة (Bahdanau_Cho_Bengio_2016, brown2020language, Krizhevsky_Sutskever_Hinton_2012, mnih2015human) انتباه الباحثين (Prouvost_2020). من بين هياكل التعلم العميق، الشبكات العصبية البيانية (GNNs) (Scarselli_Gori_Tsoi_Hagenbuchner_Monfardini_2009) أثبتت أنها أداة قوية ومرنة لحل المشكلات التوافقية. ومع ذلك، كما حدد Cappart et al. (2023) (cappart2021combinatorial), لا يزال من الصعب دمج GNN والتعلم الآلي في عمليات الحل القائمة للممارسين. أحد الأسباب هو أنه يجب تصميم وتدريب بنية مخصصة لكل مشكلة توافقية. بالإضافة إلى الموارد الحاسوبية المكلفة المحتملة للتدريب، هذا يتطلب أيضًا وجود مجموعة تدريب كبيرة وموصوفة.

كان بناء تمثيل بياني محدد للمشكلة هو الخيار المفضل لمعظم النهج ذات الصلة، مثل NeuroSAT (Selsam2018) الذي يستفيد من ترميز لصيغ SAT، أو النهج المرتبطة ارتباطًا وثيقًا بـمشكلة البائع المتجول (Prates_Avelar_Lemos_Lamb_Vardi_2018, joshi2022learning). تعاني هذه النهج من نقص في العمومية حيث لا يمكن تصدير البنية ببساطة من مشكلة توافقية إلى أخرى (على سبيل المثال، لا يمكن استخدام التمثيل في NeuroSAT لترميز حالة من مشكلة البائع المتجول). تم تحقيق بعض المحاولات لسد هذه الفجوة، ولكنها لا تزال توفر فقط عمومية جزئية. على سبيل المثال، اقترح Gasse et al. (2019) (Gasse_Chetelat_Ferroni_Charlin_Lodi_2019) رسمًا بيانيًا ثنائي الأطراف يربط بين المتغيرات والقيود عندما يكون المتغير مشاركًا في قيد معين. ومع ذلك، فإن هذا النهج يشفر فقط البرامج الصحيحة المختلطة الثنائية. لاحقًا، قدم Chalumeau et al. (2021) (chalumeau2021seapearl) رسمًا بيانيًا ثلاثي الأطراف حيث المتغيرات والقيم والقيود هي أنواع محددة من الرؤوس. يفتقر هذا النهج أيضًا إلى العمومية حيث يتطلب إعادة التدريب عندما يتغير عدد المتغيرات. حتى حد علمنا، تم تحقيق محاولة أخرى في هذا الاتجاه بواسطة Marty et al. (2023) (Marty_François_Tessier_Gauthier_Rousseau_Cappart_2023) الذين استفادوا من رسم بياني ثلاثي الأطراف يسمح بتزيين كل نوع رأس بميزات مخصصة. على الرغم من أن أي مشكلة توافقية يمكن نظريًا أن تُشفر بهذا الإطار، فإن بعض المعلومات تضيع مع الترميز. على سبيل المثال، لم يكن من الواضح كيف يمكن التمييز بين القيد \(3x_1 \leq 4x_2\)، والقيد \(2x_1 \leq 5x_2\). من ناحية، يمكن تمثيل كلا القيدين كـعدم مساواة، ولكننا نفقد معلومات حول معاملات المتغيرات. من ناحية أخرى، يمكن تشفير كلا القيدين كعلاقتين متميزتين، ولكن في هذه الحالة، نفقد حقيقة أن لدينا عدم مساواة في كلتا الحالتين. بشكل أكثر رسمية، كانت وظيفة التشفير الخاصة بهم ليست حقنية. يمكن أن يكون لحالات مختلفة نفس التشفير دون خيار للتمييز بينها. بالإضافة إلى ذلك، استهدفت التجارب المقترحة فقط مشكلات نسبياً نقية (المجموعة المستقلة القصوى، القطع الأقصى، وتلوين الرسم). تلاحظ قيود مماثلة في نهج Tönshoff et al. (2022) (Tönshoff_Kisin_Lindner_Grohe_2022).

استنادًا إلى هذا السياق، يتقدم هذا البحث نحو تمثيل عام تمامًا للمشكلات التوافقية للنهج المستندة إلى التعلم. فكرتنا الأساسية هي تفكيك أي قيد من حالة المشكلة كـشجرة بناء نحوي مجردة وربط العناصر المماثلة (على سبيل المثال، نفس المتغيرات أو القيود) من خلال حافة. ثم، نقدم بنية GNN قادرة على استغلال هذا الرسم. لإظهار العمومية لهذا النهج، تعمل بنيتنا مباشرة على الحالات المعبر عنها بتنسيق XCSP3 (Boussemart_Lecoutre_Audemard_Piette_2022) ويمكنها التعامل مع جميع القيود المتاحة في مسابقة المسار المصغر لعام 2023. تُجرى التجارب على أربع مشكلات (تتميز بالقيود القياسية والعالمية مثل allDifferent (regin1994filtering), table (demeulenaere2016compact), negativeTable (verhaeghe2017extending), element وsum) وتهدف إلى التنبؤ بالإشباع لنسخ القرار من المشكلات التوافقية. تظهر النتائج أن بنيتنا العامة تقدم أداءً قريبًا من هندسات المشكلات المحددة وتتفوّق على الرسم البياني الثلاثي الأطراف لـMarty et al. (2023) (Marty_François_Tessier_Gauthier_Rousseau_Cappart_2023).

ترميز مثيلات المشكلات التوافقية كرسم بياني

رسمياً، يُعرّف مثيل المشكلة التوافقية \(\mathcal{P}\) على أنه رباعي \(\langle X, D(X), C, O \rangle\)، حيث \(X\) هي مجموعة المتغيرات، \(D(X)\) هي مجموعة النطاقات، \(C\) هي مجموعة القيود، و\(O\) (\(X \to \mathbb{R}\)) هي دالة الهدف. الحل الصالح هو تعيين كل متغير إلى قيمة من نطاقه بحيث يتم تلبية كل قيد. الحل الأمثل هو حل صالح بحيث لا يوجد حل آخر يحقق قيمة أفضل للهدف. هدفنا هو بناء دالة \(\Phi: \langle X, D(X), C, O \rangle \mapsto \mathcal{G}(V,f,E)\)، حيث \(\mathcal{G}\) هو رسم بياني و\(V\)، \(f\)، \(E\) هي مجموعات الرؤوس، ميزات الرؤوس ومجموعات الحواف، على التوالي. نريد أن تكون هذه الدالة حقنية، أي أن الترميز يشير إلى مثيل مشكلة توافقية واحدة فقط. نقترح القيام بذلك من خلال تقديم ترميز يتكون من رسم بياني متجانس وغير موجه يتميز بخمسة أنواع من الرؤوس: المتغيرات (\(\textsc{var}\)القيود (\(\textsc{cst}\)القيم (\(\textsc{val}\)العوامل (\(\textsc{ope}\))، والنموذج (\(\textsc{mod}\)). الفكرة هي تقسيم كل قيد إلى سلسلة من العمليات الأولية، لدمج الرؤوس التي تمثل نفس المتغير أو القيمة، وربط جميع العلاقات معًا. هذه العملية تشبه بناء شجرة التحليل النحوي المجردة لبرنامج. من الناحية الرسمية، يعطي الترميز رسمًا بيانيًا \(\mathcal{G}(V, f, E)\) حيث \(V = V_\textsc{var} \cup V_\textsc{cst} \cup V_\textsc{val} \cup V_\textsc{ope} \cup V_\textsc{mod}\) هي مجموعة تحتوي على الأنواع الخمسة من الرؤوس، \(f = f_\textsc{var} \cup f_\textsc{cst} \cup f_\textsc{val} \cup f_\textsc{ope} \cup f_\textsc{mod}\) هي مجموعة الميزات المحددة المرتبطة بكل رأس، و\(E\) هي مجموعة الحواف التي تربط الرؤوس. يُعرّف كل نوع على النحو التالي.

ترميز المشكلة

يمثل الترميز مثيلًا لمشكلة توافقية كمثال تشغيلي. هناك 3 رؤوس قيمة موضحة (باللون الأخضر) و2 رؤوس متغيرة (باللون الأحمر). بما أن \(x_1\) يحتوي على القيم 1 و2 في نطاقه، فهي متصلة بحافة، وكذلك نطاق \(x_2\). هناك 2 رؤوس قيد (باللون الأزرق)، واحدة لعدم المساواة (\(\leq\)) وواحدة لقيد الجدول (\(\textsf{ext}\)). توضح المنطقة الرمادية في الشكل القيد \(3x_1 \leq 4x_2\)، المميز بالمشغلين (باللون البرتقالي) وتظهر عملية الضرب (\(\times\)، بميزة 3) لـ\(x_1\) على الجانب الأيمن (\(\textsf{rhs}\)) وآخر (\(\times\)، بميزة 4) لـ\(x_2\) على الجانب الأيسر (\(\textsf{lhs}\)). يوضح المشغلان \(\textsf{rhs}\) و\(\textsf{lhs}\) جانبي المعادلة، وهو أمر ضروري للتمييز بين \(3x_1 \leq 4x_2\) و\(3x_1 \geq 4x_2\)، ويرتبط بالقيد المناسب (على سبيل المثال، عدم المساواة \(\leq\)). يتم التعبير عن قيد الجدول \(\textsc{table}([x_1,x_2],[(1,2),(2,3)])\) بطريقة مماثلة. يتضمن ذلك زوجين \(t_1\) و\(t_2\). أخيرًا، يتصل رأس النموذج (باللون الأصفر) بالقيدين، وبالمتغير \(x_1\)، حيث إنه جزء من دالة الهدف.

كملاحظة ختامية، يمكن استخدام هذا الترميز لتمثيل أي مثيل لمشكلة توافقية بطريقة فريدة. للقيام بذلك، يجب تنفيذ محلل لكل قيد، يصف كيفية تقسيم القيد مع المشغلين والمتغيرات المعنية. نحن ندعم حاليًا جميع القيود الموضحة في تنسيق نمذجة XCSP3-core (Boussemart_Lecoutre_Audemard_Piette_2022) والمستخدمة في مسارات الحل الصغيرة لمسابقة XCSP-2023: المساواة الثنائية، الجدول، الجدول السلبي، الجدول القصير، العنصر والمجموع. يحتوي مستودعنا على الوثائق المطلوبة لبناء رسم بياني من مثيل في تنسيق XCSP3-core مع وصف لجميع الميزات المعتمدة.

التعلم من الترميز باستخدام شبكة عصبية بيانية

لتحقيق الخطوة التالية والتعلم من هذا التمثيل، قمنا بتصميم بنية شبكة عصبية بيانية مخصصة للاستفادة من هذا الترميز. شبكة عصبية بيانية هي بنية عصبية متخصصة مصممة لحساب تمثيل كامن (يعرف بـالتضمين) لكل عقدة من الرسم البياني المعطى (Scarselli_Gori_Tsoi_Hagenbuchner_Monfardini_2009). تتضمن هذه العملية تجميع المعلومات من العقد المجاورة بشكل تكراري. يُشار إلى كل خطوة تجميع بـطبقة من شبكة عصبية بيانية وتتضمن أوزانًا قابلة للتعلم. هناك طرق مختلفة لأداء هذا التجميع، مما يؤدي إلى متغيرات مختلفة من الشبكات العصبية البيانية موثقة في الأدبيات (li2016gated, monti2017geometric, velivckovicgraph). النموذج قابل للتفاضل ويمكن بعد ذلك تدريبه باستخدام طرق الانحدار التدريجي.

لنفترض أن \(\mathcal{G}(V, f, E)\) هو الترميز البياني الذي تم الحصول عليه مسبقًا، وليكن \(h^{[i]}_{t,v} \in \mathbb{R}^{p}\) تمثيلاً متجهيًا بأبعاد \(p\) لرأس \(v \in V_t\) (\(t\) يشير إلى نوع رأس من \(\mathcal{T} : \{\textsc{var},\textsc{val},\textsc{cst},\textsc{ope},\textsc{mod}\}\)) في التكرار \(i \in \{ 0, \ldots, I\}\). عملية الاستدلال لشبكة عصبية بيانية تتمثل في حساب التمثيلات التالية (\(h^{[i+1]}_{t,v}\)) من التمثيلات السابقة لكل رأس. يُشار إلى هذه العملية عادةً بـتمرير الرسالة. أولاً، نضع \(h^{[0]}_{t,v} = f_{t,v}\) لكل نوع، حيث \(f_{t,v}\) هو متجه الميزات المتعلقة برأس \(v \in V_{t}\). ثم يتم الحصول على التمثيلات في كل تكرار باستخدام \(\textsc{LayerNorm}\) (ba2016layer) وطبقات LSTM (Hochreiter_Schmidhuber_1997). يتم توضيح العملية بالكامل في الخوارزمية [algo:inference]. أولاً، يتم تعيين التضمين الأولي لكل رأس إلى ميزته (السطر [eql:1]) ويتم تهيئة حالات LSTM الخفية إلى 0 (السطر [eql:2])، كما هو شائع. ثم يتم إجراء \(I\) خطوات من تمرير الرسالة (الحلقة الرئيسية). في كل تكرار \(i\)، يتم الحصول على رسالة (\(\mu^{[i]}_{t_1,v}\)) لكل رأس. يتم الحساب في ثلاث خطوات (السطر [eql:4]): (1) يتم جمع التضمين لكل جار من نوع معين، (2) يتم إدخال القيمة الناتجة إلى شبكة الإدراك المتعدد الطبقات القياسية (\(\mathsf{MLP}^{\mathsf{in}}_{t_1,t_2}\))، لاحظ أن هناك وحدة محددة لكل نوع حافة، (3) يتم دمج الرسائل المتعلقة بكل نوع معًا (\(\bigoplus\)) للحصول على الرسالة العامة لكل رأس. الرمز \(\mathcal{N}_{t_2}(v)\) يشير إلى مجموعة الجيران لرأس \(v\) من النوع \(t_2\). ثم يتم إعطاء النتيجة كمدخلات إلى خلية LSTM (السطر [eql:5]، خلية واحدة لكل نوع) ويتم استخدامها للحصول على التضمين في الطبقة التالية. نلاحظ أن كل LSTM لها حالتها الداخلية (\(\gamma^{[i]}_{t,v}\)) محدثة. في نهاية الحلقة، لكل رأس تضمين محدد (\(h^{[I]}_{t,v}\)). بعد التكرار الأخير، نحسب الإخراج المعتمد على نوع الرأس من خلال تمرير \(h^{[I]}_{t,v}\) من خلال شبكة الإدراك المتعدد الطبقات القياسية \(\mathsf{MLP}^{\mathsf{out}}_{t}\) (السطر [eql:6]). ثم يتم توسيط التضمينات الناتجة لجميع العقد (السطر [eql:7]). أخيرًا، يتم استخدام دالة السيجمويد (\(\sigma\)) للحصول على إخراج بين 0 و1.

\(\triangleright\) Pre: \(\mathcal{G}(V_{\textsc{var}, \textsc{cst},\textsc{val}, \textsc{ope},\textsc{mod}}, f_{\textsc{var}, \textsc{cst},\textsc{val}, \textsc{ope},\textsc{mod}}, E)\) هو الترميز البياني.

\(\triangleright\) Pre: \( \mathcal{T} : \{\textsc{var},\textsc{val},\textsc{cst},\textsc{ope},\textsc{mod}\}\) هي مجموعة أنواع الرؤوس.

\(\triangleright\) Pre: \(I\) هو عدد تكرارات شبكة العصبية البيانية.

 

\(h^{[0]}_{t,v} := f_{t,v} ~ ~ ~ \forall v \in V_t, \forall t \in \mathcal{T} \) [eql:1]

\(\gamma^{[0]}_{t,v} := 0 ~ ~ ~ ~ ~ ~ ~ ~ \forall v \in V_t, \forall t \in \mathcal{T} \) [eql:2]

\( \nu_{t,v} := \mathsf{MLP}^{\mathsf{out}}_{t} \Big(h^{[I]}_{t,v} \Big) ~ ~ ~ \forall v \in V_t, \forall t \in \mathcal{T}\) [eql:6]

\(\hat{y} := \sigma\Big( \frac{1}{|\mathcal{T}|\times |V|} \sum\limits_{t \in \mathcal{T}} \sum\limits_{v \in V_t} \nu_{t,v} \Big)\) [eql:7]

\(\hat{y}\) [eql:8]

التجارب

يقيم هذا القسم منهجيتنا على المهام التوافقية، مع التركيز على أربعة مشكلات: مشكلة الإشباع البولياني (SAT)، تلوين الرسم البياني (COL)، مشكلة الحقيبة (Knap)، ومشكلة البائع المتجول (TSP) مع نماذج TSP-Ext (قيد الجدول) وTSP-Elem (قيد العنصر). قمنا بتدريب النماذج على النسخة القرارية من المشكلات، متسائلين إذا كانت هناك حلول موجودة بتكاليف أقل من هدف \(k\). عندما لا توجد دالة هدف، لدينا مشكلة إشباع مقيدة بسيطة (مثل SAT). الهدف ليس إيجاد الحل ولكن تحديد وجوده، تماشيًا مع الدراسات الحديثة (Selsam2018, Prates_Avelar_Lemos_Lamb_Vardi_2018, lemos2019graph, Liu_Zhang_Huang_Niu_Ma_Zhang_2020). قارنا منهجيتنا مع الهياكل المعمارية المحددة بالمشكلة والرسم البياني الثلاثي لمارتي وآخرين. (2023) (Marty_François_Tessier_Gauthier_Rousseau_Cappart_2023). للأخير، استخرجنا تمثيل الرسم البياني الخاص بهم واستخدمناه في شبكتنا العصبية البيانية. المقياس التقييمي المعتمد هو الدقة في التنبؤ الصحيح بالإجابة على المشكلة القرارية. تتبع التفاصيل حول البروتوكولات التجريبية وتفاصيل التنفيذ.

مشكلة الإشباع البولياني.

تم إنشاء النماذج باستخدام المولد العشوائي لسيلسام وآخرين. (2018) (Selsam2018). باختصار، يبني المولد أزواجًا عشوائية من نماذج SAT من \(n\) متغيرات بإضافة شروط عشوائية جديدة حتى تصبح المشكلة غير قابلة للإشباع. بمجرد أن تصبح المشكلة غير قابلة للإشباع، يتم تغيير إشارة الحرف الأول من المشكلة، مما يجعلها قابلة للإشباع. في المتوسط، تحتوي الشروط على 8 حدود. تم تضمين كل من النماذج القابلة للإشباع وغير القابلة للإشباع في مجموعة البيانات. لا يزال باتباع سيلسام وآخرين. (2018)، قمنا ببناء مجموعة بيانات تحتوي على ملايين النماذج التي تحتوي على 10 إلى 40 حرفًا. تم أيضًا تقديم الهيكل المعماري المعتمد على SAT في نفس الورقة. استخدمنا مجموعة تدريب بحجم 3,980,000 ومجموعة تحقق بحجم 20,000.

مشكلة البائع المتجول.

تم إنشاء النماذج باستخدام المولد العشوائي لبراتس وآخرين. (2018) (Prates_Avelar_Lemos_Lamb_Vardi_2018). يتكون الإنشاء من (1) إنشاء \(n\) نقاط في مربع \((\sqrt{2}/2 \times \sqrt{2}/2)\)، (2) بناء مصفوفة المسافات باستخدام المسافة الإقليدية، و(3) حلها باستخدام محلل كونكورد (applegate2006concorde) للحصول على تكلفة الجولة المثلى \(C^*\). ثم يتم إنشاء نموذجين: واحد قابل للتحقيق وآخر غير قابل للتحقيق بتكاليف هدف 1.02 \(C^*\) و0.98 \(C^*\)، على التوالي. نبني نموذجين TSP: الأول حيث يتم التعبير عن قيود المسافة بقيد التمديد (TSP-Ext)، والثاني بقيد العنصر (TSP-Elem). الدافع هو تحليل تأثير النموذج على الترميز البياني الناتج والأداء. لا يزال باتباع براتس وآخرين. (2018)، قمنا ببناء مجموعة البيانات بعدد مدن \(n\) مأخوذة عشوائيًا من 20 إلى 40. تم أيضًا تقديم الهيكل المعماري المعتمد على TSP في نفس الورقة. استخدمنا مجموعة تدريب بحجم 850,000 ومجموعة تحقق بحجم 50,000.

تلوين الرسم البياني.

تم إنشاء النماذج باتباع ليموس وآخرين. (2019) (lemos2019graph). يبني هذا المولد رسومات بيانية تحتوي على 40 إلى 60 رأسًا. لكل رسم بياني، يتم إضافة حافة واحدة بحيث يتغير \(k\)-القابلية للتلوين. تتم إنتاج النماذج في أزواج: واحد حيث القيمة المثلى هي \(k\) وآخر حيث هي أعلى. يستفيد ترميزنا من نموذج تلوين الرسم البياني القياسي الذي يتميز بقيود المساواة الثنائية (\(\neq\)). تم أيضًا تقديم الهيكل المعماري المعتمد على Col في نفس الورقة. استخدمنا مجموعة تدريب بحجم 140,000 ومجموعة تحقق بحجم 10,000.

مشكلة الحقيبة.

قمنا ببناء نماذج تحتوي على 20 إلى 40 عنصرًا وحللناها للوصول إلى القيمة المثلى \(V^*\). ثم، أنشأنا نموذجين، واحد قابل للتحقيق وآخر غير قابل للتحقيق بتكلفة هدف 1.02 \(V^*\) و0.98 \(V^*\)، على التوالي. يستفيد ترميزنا من نموذج الحقيبة القياسي الذي يتميز بقيد sum. تم أيضًا تقديم النموذج المحدد للحقيبة بناءً على نموذج ليو وآخرين. (2020) (Liu_Zhang_Huang_Niu_Ma_Zhang_2020). استخدمنا مجموعة تدريب بحجم 950,000 ومجموعة تحقق بحجم 50,000.

تفاصيل التنفيذ.

تم تدريب جميع النماذج باستخدام PyTorch (paszke2019pytorch) وPyTorch-Geometric (fey2019fast) على وحدة معالجة الرسومات Nvidia V100 بسعة 32 GB لمدة تصل إلى 4 أيام أو حتى التقارب. تم اختيار النموذج الذي يتمتع بأفضل أداء على مجموعة التحقق. لجعل المقارنات بين الرسومات البيانية المحددة والعامة عادلة، قمنا بتدريب جميع نماذجنا باستخدام وحدة معالجة رسومات واحدة، وقمنا بضبط كل نموذج من خلال تغيير عدد الوحدات الخفية في طبقات MLP وLSTM. بالنسبة للهياكل المعمارية المحددة بالمشكلة، أعدنا استخدام نفس المعلمات الفائقة كما هو موضح في منشوراتها الأصلية. تم تدريب جميع النماذج باستخدام محسن Adam (KingmaB14) مع جدول معدل التعلم وتحليل الوزن \(10^{-8}\). تم تفصيل المعلمات الفائقة الرئيسية المستخدمة لنماذجنا المختلفة في الكود المصاحب. جميع نماذجنا معبر عنها باستخدام صيغة XCSP3.

قمنا بتنفيذ محلل لبناء الرسم البياني من هذا التمثيل. شيفرتنا ونماذجنا المدربة متاحة للجميع.

النتائج: دقة المناهج

تلخص الجدول [table:main-results] الدقة في التنبؤ بالإجابة الصحيحة على مجموعة التحقق لكل مشكلة وخط أساس. من المثير للاهتمام، نلاحظ أن منهجنا يحقق أداءً مماثلًا أو قريبًا للهياكل المعمارية المحددة للمشكلة لجميع المشكلات. نرى ذلك كنتيجة واعدة، حيث يمكن استخدام منهجنا مباشرة لجميع المشكلات دون الحاجة إلى تصميم هيكل معماري جديد مخصص. من ناحية أخرى، يفشل منهج (Marty_François_Tessier_Gauthier_Rousseau_Cappart_2023) في تحقيق نتائج مماثلة باستثناء تلوين الرسم البياني. وذلك لأن هذا التمثيل لا يحافظ على البنية التركيبية للقيود المعقدة (Col لديه فقط قيود مثل \(x_1 \neq x_2\)).

بينما يحقق TSP-Elem نتائج قريبة من المنهج المحدد لـTSP، يقصر TSP-Ext بشكل كبير. هذا يبرز أهمية استخدام نموذج تركيبي مناسب للترميز. على وجه التحديد، يحتوي الترميز TSP-Elem على حجم يبلغ \(1841\) رأسًا و\(13042\) حافة، بينما ينتج TSP-Ext رسمًا بيانيًا يحتوي على \(5661\) رأسًا و\(28322\) حافة، لنفس مثيل المدينة البالغ عددها 40 مدينة. وهذا يعتبر ترميزًا أكبر، وهو غير مرغوب فيه لأنه يجعل النموذج أصعب في التدريب.

تحليل: التعميم على نماذج أكبر

يظهر الشكل المرجعي fig:generalization قدرة التعميم للنموذج السابق، دون إعادة تدريب، على نماذج جديدة بـ60، 80 و100 متغير (5000 نموذج لكل حجم). نلاحظ أن تمثيلنا العام يوفر تعميمًا أفضل من البنية المحددة للمشكلة لـSAT وTSP. بشكل لافت، TSP-Elem يقدم تعميمًا أفضل بكثير من TSP-Ext، مما يؤكد تأثير نموذج الإدخال وحجم الرسم البياني. من المثير للاهتمام، نلاحظ قدرة تعميم قوية للبنية المحددة لمشكلة الحقيبة. تشير تحليلاتنا الأولية إلى أن هذا يتحقق بفضل دالة تجميع GNN تعتمد على مجموع موزون. فهم الأسباب الجذرية لهذا التعميم بالتفصيل هو جزء من عملنا المستقبلي.

المناقشة: القيود والتحديات

على الرغم من أن النتائج التجريبية تظهر وعد هذه البنية العامة، يجب معالجة بعض القيود. أولاً، الوقت المطلوب للتدريب للحصول على مثل هذه النتائج كبير، على الرغم من أننا اعتبرنا حتى الآن حالات صغيرة نسبيًا. هذا بشكل رئيسي لأن ترميزنا يولد رسومات كبيرة. هذا يفتح الباب لدمج طرق الضغط، المخصصة لتقليص حجم الترميز دون فقدان المعلومات. يمكن العمل بالتوازي مع قيود (smartTable) (mairy2015smart)، والتي ترمز الجداول بشكل أكثر اختصارًا. كما يسلط الضوء على أهمية وجود نموذج إدخال جيد، ينتج تضمينًا صغيرًا (على سبيل المثال، TSP-Elem مقابل TSP-Ext). بالإضافة إلى ذلك، المهمة الحالية مقصورة على حل النسخة القرارية من المشكلات بنهج من البداية إلى النهاية. الخطوة التالية ستكون دمج هذه البنية في حل كامل، كما تم اقتراحه من قبل جاس وآخرين (Gasse_Chetelat_Ferroni_Charlin_Lodi_2019) للبرامج الصحيحة المختلطة الثنائية، ومن قبل كابارت وآخرين (cappart2021combining) للبرمجة بالقيود. أخيرًا، قدرة التعميم لنموذج تم تدريبه لمشكلة محددة (على سبيل المثال، على TSP) لمشكلة مماثلة (على سبيل المثال، TSP مع نوافذ زمنية) هي جانب مثير للاهتمام للتحقيق.

الخلاصة والآفاق

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

الشكر والتقدير

تم تمويل هذا البحث بشكل رئيسي بفضل منحة اكتشاف NSERC (كندا) التي يحملها كوينتن كابارت. تلقى هذا البحث تمويلاً من برنامج الاتحاد الأوروبي للبحث والابتكار Horizon 2020 بموجب اتفاقية منحة رقم 101070149، مشروع Tuples.