فِي السَنَواتِ الأَخِيرَةِ، كانَ هُناكَ اِهْتِمامَ مُتَزايِدٍ بِاِسْتِخْدامِ المُقارَباتِ المَبْنِيَّةُ عَلَى التَعَلُّمِ لِحَلِّ مُشْكِلاتِ التوليف، سَواءُ بِطَرِيقَةٍ نِهائِيَّةٍ أَو بِالتَعاوُنِ مَعَ خوارزميات التَحْسِين التَقْلِيدِيَّةِ. فِي كُلّاً السيناريوهين، تَكْمُن التَحَدِّي فِي ترميز المُشْكِلاتِ التوليفيه المُسْتَهْدَفَة إِلَى هَيْكَلِ متوافق مَعَ خوارزميه التَعَلُّمِ. لَقَد اِقْتَرَحَت العَدِيدَ مِن الأَعْمالِ السابِقَةِ تَمْثِيلات مُحَدَّدَةٍ لِلمُشْكِلَةِ، غالِباً عَلَى شَكْلٍ رَسْمِ بَيانَيَّ، لِلاِسْتِفادَةِ مِن مَزايا شَبَكاتِ الأَعْصاب الرسوميه. وَمَعَ ذٰلِكَ، تَفْتَقِر هٰذِهِ المُقارَباتِ إِلَى العُمُومِيَّةِ، حَيْثُ لا يُمْكِن نَقْلِ التَمْثِيلِ بِسُهُولَةٍ مِن مُشْكِلَةِ توليفيه إِلَى أُخْرَى. عَلَى الرَغْمِ مِن أَنَّ بِعَضِّ المُحاوَلاتِ قَد تَمَّت لِسَدِّ هٰذِهِ الفَجْوَةِ، إِلّا أَنَّها لا تَزال تَقَدَّمَ عُمُومِيَّةٍ جُزْئِيَّةٍ فَقَط. رَدّاً عَلَى هٰذا التَحَدِّي، يَدْعُو هٰذا البَحْثِ إِلَى التَقَدُّمِ نَحْوَ تَمْثِيلِ عامَ كامِلٍ لِمُشْكِلاتٍ التوليف لِلمُقارَبات المَبْنِيَّةُ عَلَى التَعَلُّمِ. النَهْجِ الَّذِي نَقْتَرِحه يَتَضَمَّن بِناءَ رَسْمِ بَيانَيَّ عَن طَرِيقِ تَحْلِيلِ أَيّ قَيْدِ مِن مُشْكِلَةِ التوليف إِلَى شَجَرَةَ تَحْلِيلِ نَحْوِي مُجَرَّده وَالتَعْبِيرِ عَن العَلاقاتِ (مِثْلَ مُتَغَيِّر مُشارِكٍ فِي قَيْدِ) مِن خِلالَ الحَوافّ. عِلاوَةً عَلَى ذٰلِكَ، نُقَدِّم هَنْدَسَةُ شَبَكَةِ عَصَبِيَّةُ رسوميه قادِرَةٍ عَلَى التَعَلُّمِ بِكَفاءَة مِن هٰذا التَمْثِيلِ. الأَداة المُقَدَّمَةِ تَعْمَل عَلَى مُشْكِلاتِ التوليف المُعَبَّرِ عَنها بِتَنْسِيق 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\) هِيَ مَجْمُوعاتٍ رُؤُوسه، مِيزاتِ الرُؤُوسِ وَمَجْمُوعاتٍ الأَقْواس، عَلَى التَوالِي. نُرِيد أَنَّ تَكُون هٰذِهِ الدالَّةِ حقنيه، أَيّ أَنَّ الترميز يُشِير إِلَى مِثالٌ مُشْكِلَةِ تُوافِقِيهِ واحِدَةٍ عَلَى الأَكْثَرَ. نَقْتَرِح القِيامِ بِذٰلِكَ مِن خِلالَ تَقْدِيمِ ترميز يَتَكَوَّن مِن رَسْمِ بَيانَيَّ مُتَجانِسٍ وَغَيْرِ مُوَجَّهٍ يَتَمَيَّز ب 5 أَنْواعِ مِن الرُؤُوسِ: المُتَغَيِّراتِ (\(\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.