تحسين القيود الموزعة

المكونات الرئيسية لمسألة DCOP هي الوكلاء والمتغيرات . ومن المهم أن كل متغير مملوك لوكيل؛ وهذا ما يجعل المسألة موزعة. رسميًا، تُعرَّف مسألة DCOP بأنها مجموعة مرتبة${\displaystyle \langle A,V,{\mathfrak {D}},f,\alpha ,\eta \rangle }$، أين:

• ${\displaystyle A}$هي مجموعة الوكلاء ،​${\displaystyle \{a_{1},\dots ,a_{|A|}\}}$.
• ${\displaystyle V}$هي مجموعة المتغيرات ،${\displaystyle \{v_{1},v_{2},\dots ,v_{|V|}\}}$.
• ${\displaystyle {\mathfrak {D}}}$هي مجموعة مجالات المتغيرات ،${\displaystyle \{D_{1},D_{2},\dots ,D_{|V|}\}}$حيث كل${\displaystyle D_{j}\in {\mathfrak {D}}}$هي مجموعة منتهية تحتوي على القيم الممكنة للمتغير${\displaystyle v_{j}}$.
  • لو${\displaystyle D_{j}\in {\mathfrak {D}}}$إذا احتوى على قيمتين فقط (مثل 0 أو 1)، فـ${\displaystyle v_{j}}$يُطلق عليه اسم متغير ثنائي .
• ${\displaystyle f}$هي دالة التكلفة . وهي دالة ^{[ 1 ]}$${\displaystyle f:\bigcup _{S\subseteq V}\times _{v_{j}\in S}D_{j}\to \mathbb {R} }$$هذا يربط كل تخصيص جزئي ممكن بتكلفة. عادةً، عدد قليل فقط من قيم${\displaystyle f}$تكون قيمها غير صفرية، ويتم تمثيلها كقائمة من الصفوف التي تم تعيين قيمة غير صفرية لها. يُطلق على كل صف من هذه الصفوف اسم قيد . كل قيد${\displaystyle C}$تحتوي هذه المجموعة على دالة${\displaystyle f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R} }$تخصيص قيمة حقيقية لكل قيمة ممكنة للمتغيرات. ومن أنواع القيود الخاصة ما يلي:
  • القيود الأحادية - القيود المفروضة على متغير واحد، أي${\displaystyle f_{C}:D_{j}\to \mathbb {R} }$بالنسبة للبعض${\displaystyle v_{j}\in V}$.
  • القيود الثنائية - قيود على متغيرين، أي${\displaystyle f_{C}:D_{j_{1}}\times D_{j_{2}}\to \mathbb {R} }$بالنسبة للبعض${\displaystyle v_{j_{1}},v_{j_{2}}\in V}$.
• ${\displaystyle \alpha }$هي دالة الملكية . إنها دالة${\displaystyle \alpha :V\to A}$ربط كل متغير بالعامل المرتبط به.${\displaystyle \alpha (v_{j})\mapsto a_{i}}$هذا يعني أن المتغير${\displaystyle v_{j}}$"ينتمي" إلى الوكيل${\displaystyle a_{i}}$وهذا يعني أنه عامل${\displaystyle a_{i}}$تقع على عاتقها مسؤولية تحديد قيمة المتغير${\displaystyle v_{j}}$. لاحظ أن${\displaystyle \alpha }$ليس بالضرورة أن يكون تطبيقًا أحاديًا ، أي أن أحد العوامل قد يمتلك أكثر من متغير واحد. كما أنه ليس بالضرورة تطبيقًا شاملًا ، أي أن بعض العوامل قد لا تمتلك أي متغيرات.
• ${\displaystyle \eta }$هي دالة الهدف . وهي عامل يجمع كل القيم الفردية${\displaystyle f}$تكاليف جميع التعيينات المتغيرة الممكنة. ويتم ذلك عادةً من خلال الجمع:$${\displaystyle \eta (f)\mapsto \sum _{s\in \bigcup _{S\subseteq V}\times _{v_{j}\in S}D_{j}}f(s).}$$

يهدف نموذج DCOP إلى جعل كل عنصر يُسند قيمًا لمتغيراته المرتبطة به بهدف تقليلها أو زيادتها.${\displaystyle \eta (f)}$بالنسبة لتعيين معين للمتغيرات.

تعيين القيمة هو زوج${\displaystyle (v_{j},d_{j})}$أين${\displaystyle d_{j}}$هو عنصر من عناصر المجال${\displaystyle D_{j}}$.

التخصيص الجزئي هو مجموعة من تخصيصات القيم حيث كل${\displaystyle v_{j}}$يظهر مرة واحدة على الأكثر. ويُطلق عليه أيضاً اسم السياق. ويمكن اعتباره دالة تربط المتغيرات في DCOP بقيمها الحالية.$${\displaystyle t:V\to (D\in {\mathfrak {D}})\cup \{\emptyset \}.}$$ لاحظ أن السياق هو في الأساس حل جزئي ولا يشترط أن يحتوي على قيم لكل متغير في المسألة؛ لذلك،${\displaystyle t(v_{i})\mapsto \emptyset }$وهذا يعني أن الوكيل${\displaystyle \alpha (v_{i})}$لم يتم بعد تعيين قيمة للمتغير${\displaystyle v_{i}}$بناءً على هذا التمثيل، يمكن اعتبار " نطاق " الدالة (أي مجموعة قيم الإدخال) fبمثابة مجموعة جميع السياقات الممكنة لـ DCOP. لذلك، في بقية هذه المقالة، قد نستخدم مفهوم السياق (أي${\displaystyle t}$(الدالة) كمدخل لـ${\displaystyle f}$وظيفة.

المهمة الكاملة هي مهمة تتضمن كل${\displaystyle v_{j}}$يظهر هذا الحل مرة واحدة فقط، أي يتم تعيين جميع المتغيرات. ويُطلق عليه أيضاً حل لمسألة تحسين التحسين الديناميكي (DCOP).

الحل الأمثل هو تخصيص كامل تكون فيه دالة الهدف${\displaystyle \eta (f)}$يتم تحسينها (أي تعظيمها أو تصغيرها، اعتمادًا على نوع المشكلة).

تتمثل مشكلة تلوين الرسم البياني فيما يلي: بالنظر إلى رسم بياني${\displaystyle G=\langle N,E\rangle }$ومجموعة من الألوان${\displaystyle C}$قم بتعيين كل رأس ،${\displaystyle n\subset N}$لون،${\displaystyle c\leq C}$، بحيث يتم تقليل عدد الرؤوس المتجاورة ذات اللون نفسه.

في نموذج DCOP، يوجد عامل واحد لكل رأس مُخصص لتحديد اللون المرتبط به. يمتلك كل عامل متغيرًا واحدًا يكون نطاقه المرتبط به من عدد عناصر${\displaystyle |C|}$(توجد قيمة نطاق واحدة لكل لون ممكن). لكل رأس${\displaystyle n_{i}\leq N}$، هناك متغير${\displaystyle v_{i}\in V}$مع النطاق${\displaystyle D_{i}=C}$لكل زوج من الرؤوس المتجاورة${\displaystyle \langle n_{i},n_{j}\rangle \in E}$، هناك قيد على التكلفة يساوي 1 إذا تم تعيين نفس اللون لكلا المتغيرين المرتبطين:$${\displaystyle (\forall c\subseteq C:f(\langle v_{i},c\rangle ,\langle v_{j},c\rangle )\mapsto 1).}$$إذن، الهدف هو تقليل${\displaystyle \eta (f)}$.

تتمثل الصيغة الموزعة المتعددة لمسألة حقيبة الظهر فيما يلي: بالنظر إلى مجموعة من العناصر ذات الأحجام المتفاوتة ومجموعة من حقائب الظهر ذات السعات المتفاوتة، يتم تخصيص كل عنصر لحقيبة ظهر بحيث يتم تقليل مقدار الفائض إلى الحد الأدنى.${\displaystyle I}$لتكن مجموعة العناصر،${\displaystyle K}$مجموعة حقائب الظهر،${\displaystyle s:I\to \mathbb {N} }$أن تكون دالة تربط العناصر بحجمها، و${\displaystyle c:K\to \mathbb {N} }$أن تكون دالة تربط حقائب الظهر بسعاتها.

لترميز هذه المشكلة على أنها مشكلة تحسين متقاطعة (DCOP)، لكل${\displaystyle i\in I}$أنشئ متغيرًا واحدًا${\displaystyle v_{i}\in V}$مع المجال المرتبط${\displaystyle D_{i}=K}$ثم لجميع السياقات الممكنة${\displaystyle t}$:$${\displaystyle f(t)\mapsto \sum _{k\in K}{\begin{cases}0&r(t,k)\leq c(k),\\r(t,k)-c(k)&{\text{otherwise}},\end{cases}}}$$أين${\displaystyle r(t,k)}$يمثل الوزن الإجمالي المخصص حسب السياق${\displaystyle t}$حقيبة ظهر${\displaystyle k}$:$${\displaystyle r(t,k)=\sum _{v_{i}\in t^{-1}(k)}s(i).}$$

تتمثل مشكلة تخصيص العناصر فيما يلي: توجد عدة عناصر يجب تقسيمها بين عدة وكلاء. لكل وكيل تقييم مختلف للعناصر. الهدف هو تحقيق الأمثلية لهدف عام، مثل تعظيم مجموع المنافع أو تقليل الحسد. يمكن صياغة مشكلة تخصيص العناصر كمسألة تحسين مُقيدة (DCOP) كما يلي. ^{[ 2 ]}

• أضف متغيرًا ثنائيًا v_{_ij} لكل وكيل i وعنصر j . تكون قيمة المتغير "1" إذا حصل الوكيل على العنصر، و"0" خلاف ذلك. المتغير مملوك للوكيل i .
• للتعبير عن القيد المتمثل في إعطاء كل عنصر لوكيل واحد على الأكثر، أضف قيودًا ثنائية لكل متغيرين مختلفين مرتبطين بنفس العنصر، بتكلفة لا نهائية إذا كان المتغيران "1" في نفس الوقت، وتكلفة صفرية خلاف ذلك.
• للتعبير عن القيد الذي ينص على وجوب تخصيص جميع العناصر، أضف قيدًا من الرتبة n لكل عنصر (حيث n هو عدد العناصر)، بتكلفة لا نهائية إذا لم يكن أي متغير متعلق بهذا العنصر يساوي "1".

تم تطبيق DCOP على مشاكل أخرى، مثل:

• تنسيق أجهزة الاستشعار المتنقلة؛
• جدولة الاجتماعات والمهام.

تتمثل إحدى الطرق البسيطة لحل مشكلة ADCOP في استبدال كل قيد.${\displaystyle f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R} ^{k}}$مع وجود قيد${\displaystyle f_{C}':D_{1}\times \cdots \times D_{k}\to \mathbb {R} }$، وهو ما يساوي مجموع الدوال${\displaystyle f_{C}^{1}+\cdots +f_{C}^{k}}$ومع ذلك، يتطلب هذا الحل من الجهات الفاعلة الكشف عن دوال التكلفة الخاصة بها. وغالبًا ما يكون هذا غير مرغوب فيه لاعتبارات الخصوصية. ^{[ 14 ] [ 15 ] [ 16 ]}

يُعرف نهج آخر باسم "الأحداث الخاصة كمتغيرات" (PEAV). ^{[ 17 ]} في هذا النهج، يمتلك كل متغير، بالإضافة إلى متغيراته الخاصة، "متغيرات معكوسة" لجميع المتغيرات التي يمتلكها جيرانه في شبكة القيود. توجد قيود إضافية (بتكلفة لا نهائية) تضمن أن تكون المتغيرات المعكوسة مساوية للمتغيرات الأصلية. يتمثل عيب هذه الطريقة في أن عدد المتغيرات والقيود يكون أكبر بكثير من العدد الأصلي، مما يؤدي إلى زيادة وقت التشغيل.

يتمثل النهج الثالث في تكييف الخوارزميات الموجودة، التي طُوّرت لخوارزميات DCOP، مع إطار عمل ADCOP. وقد تم ذلك لكل من خوارزميات البحث الكامل وخوارزميات البحث المحلي. ^{[ 13 ]}

يتشابه هيكل مسألة ADCOP مع مفهوم اللعبة المتزامنة في نظرية الألعاب . ففي كلتا الحالتين، يوجد وكلاء يتحكمون في المتغيرات (في نظرية الألعاب، المتغيرات هي الإجراءات أو الاستراتيجيات الممكنة للوكلاء). وفي كلتا الحالتين، ينتج عن كل اختيار للمتغيرات من قبل الوكلاء المختلفين عائد مختلف لكل وكيل. ومع ذلك، ثمة فرق جوهري: ^{[ 13 ]}

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

توجد بعض النماذج الوسيطة التي يكون فيها الوكلاء متعاونين جزئيًا : فهم على استعداد لتقليل منفعتهم الشخصية للمساهمة في تحقيق الهدف العام، ولكن فقط إذا لم تكن تكلفتهم الشخصية مرتفعة للغاية. ومن أمثلة الوكلاء المتعاونين جزئيًا موظفو الشركة. فمن جهة، يسعى كل موظف إلى تعظيم منفعته الشخصية؛ ومن جهة أخرى، يرغب أيضًا في المساهمة في نجاح الشركة. ولذلك، فهم على استعداد لمساعدة الآخرين أو القيام ببعض المهام التي تستغرق وقتًا طويلاً والتي تفيد الشركة، طالما أنها لا تُشكل عبئًا كبيرًا عليهم. ومن نماذج الوكلاء المتعاونين جزئيًا: ^{[ 18 ]}

• المنفعة الشخصية المضمونة : يوافق الوكلاء على العمل من أجل الصالح العام إذا كانت منفعتهم الخاصة على الأقل بنفس مستوى المنفعة في الوضع غير التعاوني (أي أن النتيجة النهائية يجب أن تكون تحسينًا باريتو للحالة الأصلية).
• التعاون اللامدا : يوجد مُعامل${\displaystyle \lambda \in [0,1]}$يوافق الوكلاء على العمل من أجل الصالح العام إذا كانت منفعتهم الشخصية على الأقل مساوية لـ${\displaystyle (1-\lambda )}$أضعاف فائدتهم غير التعاونية.

يتطلب حل مسائل ADCOP ذات التعاون الجزئي تعديلات على خوارزميات ADCOP. ^{[ 18 ]}