الانتقال إلى المحتوى
العودة إلى نتائج البحث

البرمجة بالقيد

قدّمه
Rossi, van Beek & Walsh
السنة
2006
النوع
Declarative combinatorial optimization
العائلة
Mathematical programming

هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية

حجم الخط

ماذا تفعل؟

البرمجة بالقيد (CP) هي نموذج تحسين تعريفي يُصاغ فيه المشكلة كمجموعة من المتغيرات، ونطاقات محدودة، وقيود، ويبحث المُحلل بشكل منهجي عن تعيينات تلبي جميع القيود. تم تقنين البرمجة بالقيد بشكل شامل من قبل روسي وفان بيك ووالش في دليل البرمجة بالقيد لعام 2006، وهي توحد تقليم الانتشار مع بحث التراجع الذكي لمعالجة المشكلات التوافقية عبر مجالات الجدولة والتخطيط والتكوين.

الفكرة الحدسية وراء الطريقة

فكر في البرمجة بالقيد كملء لغز معقد: كل خلية هي متغير بمجموعة من القيم القانونية، وكل قاعدة من قواعد اللغز هي قيد. بدلاً من التخمين الأعمى، تستخدم البرمجة بالقيد القواعد للقضاء فورًا على القيم المستحيلة من الخلايا المجاورة كلما تم ملء خلية. هذا الانتشار يقلل مساحة البحث بشكل كبير، لذا فإن المُحلل يستكشف فقط التركيبات المعقولة - ويتراجع ويُعدّل فقط عندما يصل إلى طريق مسدود.

التاريخ

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

متى تُستخدم

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

الحدود والاعتبارات

  • قابلية التوسع: البحث الأسي في أسوأ الحالات يجعل البرمجة بالقيد بطيئة على الحالات الكبيرة جدًا ذات الانتشار الضعيف.
  • تتطلب نمذجة جيدة: تؤدي استراتيجيات ترتيب المتغيرات/القيم السيئة أو غياب القيود العالمية إلى أشجار بحث كبيرة بشكل غير ضروري.
  • النطاقات المستمرة: تم تصميم البرمجة بالقيد بشكل أصلي للنطاقات المنفصلة؛ تتطلب المشكلات المستمرة امتدادات متخصصة أو مقاربات هجينة.
  • خبرة المُحلل: يتطلب الاستخدام الفعال الإلمام بتقنيات نمذجة القيود ومكتبات القيود العالمية الخاصة بالمُحلل.

لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.

نقاط القوة

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

التطبيقات

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

كيف يعمل

كيف يعمل

1

تُشفر المشكلة على هيئة ثلاثية لمشكلة إرضاء القيود تتكون من المتغيرات X، ونطاقاتها المحدودة D، ومجموعة من القيود C. يمكن تعيين أي قيمة من نطاقها D_i لكل متغير x_i. تحدد القيود التركيبات المسموح بها للقيم عبر مجموعات فرعية من المتغيرات، مترجمةً القواعد الواقعية - حدود السعة، علاقات الأسبقية، تعارضات الموارد - إلى بنية رياضية يمكن للمُحلل الاستدلال عليها.

الصيغة
\text{CSP} = \langle X, D, C \rangle \quad X = \{x_1, x_2, \ldots, x_n\},\; D = \{D_1, D_2, \ldots, D_n\}
2

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

الصيغة
\text{AC}(x_i, x_j): \forall a \in D_i,\; \exists b \in D_j \text{ s.t. } c_{ij}(a, b) \text{ holds}
3

يختار المُحلل متغيرًا غير معين - عادةً باستخدام استراتيجيات مثل الحد الأدنى من القيم المتبقية أو الدرجة - ويعيّنه مؤقتًا قيمة من نطاقه المُقلم. يعمل الانتشار مرة أخرى؛ إذا تم اكتشاف تناقض (نطاق فارغ)، يتراجع المُحلل إلى أحدث نقطة اختيار ويجرب قيمة بديلة. يمكن أن يؤدي التراجع وتسجيل عدم الصلاحية إلى تسريع الاسترداد من الفشل بشكل أكبر.

الصيغة
x_i \leftarrow a_i \in D_i,\quad \text{propagate},\quad \text{if fail: backtrack and reassign}
4

عندما يتم تعيين قيم لجميع المتغيرات متوافقة مع كل قيد، فإن التعيين الكامل S* يشكل حلاً. بالنسبة لمشاكل التحسين، يوجه دالة الهدف البحث نحو أفضل حل ممكن، وتعمل استراتيجيات الفرع والحد تدريجيًا على تشديد الحد مع العثور على حلول أفضل، حتى يتم التصديق على الأمثل العالمي أو الوصول إلى حد زمني.

الصيغة
S^* = \{(x_1, a_1^*), \ldots, (x_n, a_n^*)\} : \forall c \in C,\; c(a_1^*, \ldots, a_n^*) = \text{true}

الأخطاء الشائعة

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

الأسئلة الشائعة

كيف تختلف البرمجة بالقيد عن البرمجة الخطية الصحيحة؟

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

ما هي القيود العالمية ولماذا هي مهمة؟

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

هل يمكن للبرمجة بالقيد إيجاد حلول مثلى، أم فقط حلول ممكنة؟

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

طرق ذات صلة

المصادر

  1. Rossi, F., van Beek, P., & Walsh, T. (Eds.). (2006). Handbook of Constraint Programming. Elsevier.

    ردمك: 978-0-444-52726-4
    تم النسخ.