البرمجة الديناميكية متعددة الأهداف — السياسات المثلى باريتو عبر القرارات المتسلسلة
- قدّمه
- Extension of Bellman (1957); formalized by multiple authors from 1970s onward
- السنة
- 1957-1975
- النوع
- Exact optimization — recursive multi-objective decomposition
- العائلة
- Simulation / optimization
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
توسيع البرمجة الديناميكية متعددة الأهداف (MODP) برمجة بلمان الديناميكية الكلاسيكية إلى حالات حيث يجب على متخذ القرار تحسين عدة أهداف متنافسة في وقت واحد عبر سلسلة من المراحل. بدلاً من سياسة مثلى واحدة، فإنها تنتج مجموعة مثلى باريتو من السياسات — كل منها يمثل ملف تبادل مختلف — من خلال نشر دوال القيمة ذات المتجهات بشكل عكسي عبر فضاء الحالة.
الفكرة الحدسية وراء الطريقة
في البرمجة الديناميكية أحادية الهدف، تحمل كل حالة قيمة واحدة وأفضل إجراء واحد. تعمم البرمجة الديناميكية متعددة الأهداف هذا عن طريق تخزين، في كل حالة، جبهة باريتو كاملة من متجهات المكافآت التراكمية غير المهيمنة. بينما تجتاح الخوارزمية للخلف عبر مراحل القرار، فإنها تدمج وتقلم مجموعات باريتو هذه بحيث لا تبقى سوى السياسات غير المهيمنة حقًا حتى المرحلة النهائية. النتيجة ليست إجابة واحدة بل سطح مقايضة كامل يمكن لصانع القرار منه اختيار السياسة التي تطابق تفضيله بشكل أفضل، دون الحاجة أبدًا إلى تحديد الأوزان مسبقًا.
التاريخ
تبني البرمجة الديناميكية متعددة الأهداف على إطار البرمجة الديناميكية التأسيسي لريتشارد بلمان المنشور في عام 1957. ظهرت التوسعات للأهداف المتجهة في أدبيات بحوث العمليات خلال السبعينيات والثمانينيات، مدفوعة بتطبيقات في إدارة موارد المياه، والتخطيط العسكري، والسياسة الاقتصادية. نضج المجال جنبًا إلى جنب مع نظرية التحسين متعدد الأهداف، مع مساهمات رئيسية في تقنين الاستدعاءات ذات القيم المتجهة لباريتو وخوارزميات التقليم. لا يزال مجال بحث نشطًا، لا سيما في سياق عمليات قرار ماركوف مع إشارات مكافأة متعددة.
متى تُستخدم
استخدم MODP عندما تتكشف القرارات عبر مراحل متسلسلة متعددة، وعندما يتعارض هدفان على الأقل، وعندما تكون مساحات الحالة والإجراء صغيرة بما يكفي لتعدادها أو تقطيعها. إنها مثالية لتخصيص الموارد عبر الزمن، وجدولة المشاريع متعددة المراحل، وتقييم سياسات الصحة أو البيئة المتسلسلة حيث تكون الحلول الكاملة لباريتو مطلوبة. لا تستخدم عندما تكون مساحة الحالة كبيرة جدًا (لعنة الأبعاد تجعل حساب جبهة باريتو الدقيقة غير ممكن)، وعندما يمكن دمج الأهداف بسهولة في مقياس واحد قبل التحليل، أو عندما يكون هيكل المشكلة غير ماركوفي (المكافآت المستقبلية تعتمد على التاريخ بما يتجاوز الحالة الحالية).
الحدود والاعتبارات
- تعاني بشدة من لعنة الأبعاد: تزداد التكلفة الحسابية والذاكرة بشكل أسي مع عدد متغيرات الحالة والأهداف.
- تتطلب مساحة حالة منفصلة أو مقطعة، والتي يمكن أن تقدم خطأ تقريبي للمشاكل المستمرة.
- يمكن أن ينمو عدد السياسات غير المهيمنة المخزنة في كل حالة بشكل كبير جدًا، مما يجعل الطرق الدقيقة غير عملية للمشاكل التي تحتوي على أكثر من ثلاثة أو أربعة أهداف.
- تفترض خاصية ماركوف — يعتمد الإجراء المستقبلي الأمثل فقط على الحالة الحالية، وليس على تاريخ القرارات السابقة.
- التنفيذ أكثر تعقيدًا بشكل كبير من البرمجة الديناميكية أحادية الهدف، ويتطلب فحوصات هيمنة باريتو فعالة وإدارة مجموعات في كل حالة.
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- توفر جبهة باريتو كاملة من السياسات المثلى، مما يمنح صانعي القرار رؤية كاملة لمقايضات الأهداف دون إجبارهم على تحديد الأوزان مسبقًا.
- تضمن الأمثلية الدقيقة لباريتو ضمن النموذج — لا يوجد تقريب استدلالي للمشاكل ذات الحجم القابل للمعالجة.
- تتعامل بشكل طبيعي مع هياكل القرارات المتسلسلة والمتدرجة حيث تتطلب معظم طرق الأهداف المتعددة الأخرى إعادة صياغة اصطناعية للمشكلة.
- تفصل مرحلة التحسين عن مرحلة استخلاص التفضيلات، مما يسمح بتطبيق تفضيلات أصحاب المصلحة بعد حساب الجبهة.
- تتوسع بشكل طبيعي إلى الإعدادات العشوائية عن طريق تخزين مجموعات باريتو من القيم المتوقعة للمتجهات في كل حالة.
التطبيقات
- إدارة خزان المياه متعدد المراحل توازن بين التحكم في الفيضانات، وإمدادات الري، وتوليد الطاقة الكهرومائية في وقت واحد.
- تخطيط علاج السرطان المتسلسل يحسن السيطرة على الورم، والسمية، ونوعية الحياة عبر دورات العلاج.
- تحسين المحفظة متعددة الفترات يوازن بين العائد والمخاطر وقيود السيولة عبر آفاق الاستثمار.
- تقييم السياسات البيئية للسياسات التي يجب أن توازن بين التكلفة الاقتصادية، وتقليل الكربون، وتأثير التنوع البيولوجي بمرور الوقت.
- توجيه وجدولة متعددة الأهداف في شبكات الخدمات اللوجستية مع أهداف متنافسة للتكلفة والوقت والموثوقية.
- تخصيص الموارد المتسلسل في محافظ البحث والتطوير يوازن بين كفاءة الميزانية، وإمكانات الابتكار، والوقت اللازم للتسويق.
كيف يعمل
كيف يعمل
تعريف مشكلة القرار متعدد المراحل: مجموعة من المراحل t = 1, ..., T، وفضاء حالة S، وفضاء إجراء A، ودالة انتقال، ودالة مكافأة متجهة r(s, a) = (r1, r2, ..., rk) مع k أهداف. لا يلزم وجود أوزان قياسية في هذه المرحلة.
تعداد أو تقطيع فضاء الحالة. لكل حالة نهائية في المرحلة T، قم بتهيئة مجموعة باريتو على أنها المجموعة المفردة التي تحتوي على متجه المكافأة النهائي. هذه القيم الحدودية ترسي الاستدعاء العكسي.
في كل حالة s ومرحلة t، عرف دالة القيمة المتجهة V(s, t) كمجموعة جميع متجهات المكافآت التراكمية غير المهيمنة التي يمكن الوصول إليها من (s, t) إلى المرحلة النهائية. استبدل أمثلية بلمان القياسية بعدم هيمنة باريتو: متجه v يهيمن على v' إذا كان v جيدًا على الأقل في كل هدف وأفضل بشكل صارم في هدف واحد على الأقل.
اجتياح للخلف من المرحلة T إلى المرحلة 1. في كل (s, t)، احسب قيم المتجهات المرشحة لكل إجراء ممكن a عن طريق الجمع بين المكافأة الفورية r(s, a) وكل عنصر في V(s', t+1) لحالة الخلف s'. خذ اتحاد جميع الإجراءات وقم بتقليم المتجهات المهيمنة للاحتفاظ بجبهة باريتو فقط لـ V(s, t).
في الحالة الأولية، تحتوي V(s0, 1) على المجموعة الكاملة لمتجهات المكافآت التراكمية المثلى باريتو. يتوافق كل متجه مع سياسة مميزة. قدم جبهة باريتو هذه لصانع القرار، الذي يمكنه اختيار سياسة مفضلة بناءً على أولوياته، أو تطبيق قياس (على سبيل المثال، مجموع مرجح) بعد ذلك.
الأخطاء الشائعة
- الخلط بين البرمجة الديناميكية متعددة الأهداف وتشغيل البرمجة الديناميكية ببساطة بشكل منفصل لكل هدف بأوزان مختلفة — هذا النهج يغفل المناطق غير المحدبة لجبهة باريتو.
- إهمال التحقق من أن فضاء الحالة ماركوفي حقًا قبل تطبيق الطريقة — متغيرات الحالة المخفية ستبطل الاستدعاء.
- التقليل من حجم مجموعة باريتو في كل حالة، مما يؤدي إلى استنفاد الذاكرة للمشاكل ذات الأهداف العديدة أو الآفاق الطويلة.
- تطبيق MODP على مساحات الحالة المستمرة أو عالية الأبعاد دون مخطط تقريبي مضمون التقارب، مما ينتج عنه نتائج غير موثوقة.
- تقديم جبهة باريتو الكاملة لصانعي القرار دون أدوات دعم لاستخلاص التفضيلات، مما يربكهم بالكثير من خيارات السياسات.
الأسئلة الشائعة
كيف تختلف البرمجة الديناميكية متعددة الأهداف عن مجرد تشغيل البرمجة الديناميكية بشكل منفصل لكل هدف؟
يؤدي تشغيل البرمجة الديناميكية بشكل منفصل لكل هدف إلى تحقيق أهداف فردية أحادية الهدف، والتي تكون بشكل عام غير قابلة للتحقيق في وقت واحد وتغفل هيكل المقايضة تمامًا. تقوم MODP بنشر مجموعات باريتو ذات القيم المتجهة عبر فضاء الحالة، وتلتقط جميع التركيبات غير المهيمنة لقيم الأهداف التي يمكن تحقيقها بواسطة أي سياسة فردية — بما في ذلك الحلول في المناطق غير المحدبة لجبهة باريتو التي لا تستطيع طرق المجموع المرجح إيجادها.
متى تجعل لعنة الأبعاد MODP غير عملية؟
تصبح MODP غير قابلة للمعالجة عندما تحتوي مساحة الحالة على أكثر من عدد قليل من المتغيرات المنفصلة، أو عندما يكون أفق التخطيط طويلًا جدًا، أو عندما يكون هناك أكثر من ثلاثة أو أربعة أهداف (مما يتسبب في نمو جبهة باريتو في كل حالة بشكل أسي). عادة ما تُفضل الطرق التقريبية مثل التعلم المعزز متعدد الأهداف أو البحث الاستدلالي لباريتو في مثل هذه الحالات.
هل يمكن لـ MODP التعامل مع عدم اليقين في الانتقالات أو المكافآت؟
نعم. في إعداد عشوائي، تخزن دالة القيمة المتجهة متجهات المكافآت المتوقعة المثلى لباريتو، محسوبة باستخدام المجموع المرجح بالاحتمالات عبر حالات الخلف. يتوسع هذا بشكل طبيعي إلى عمليات قرار ماركوف متعددة الأهداف (MOMDPs)، على الرغم من أن العشوائية تزيد من المتطلبات الحسابية.
هل أحتاج إلى تحديد أوزان الأهداف قبل تشغيل MODP؟
لا — هذه إحدى المزايا الرئيسية لـ MODP. لا يلزم وجود أوزان أو معلومات تفضيلية أثناء مرحلة التحسين. تقوم الخوارزمية بحساب جبهة باريتو الكاملة، ويطبق صانع القرار تفضيلاته بعد ذلك لاختيار سياسة معينة.
ما هو الناتج الذي تنتجه MODP، وكيف يجب تفسيره؟
تنتج MODP مجموعة من السياسات المثلى لباريتو، كل منها مرتبط بمتجه من قيم الأهداف التراكمية. لا تهيمن سياسة واحدة على جميع السياسات الأخرى في كل هدف. يقوم صانع القرار بفحص هذه الجبهة لتحديد السياسات التي تتطابق مع ترتيب أولوياته، غالبًا بمساعدة أدوات التصور مثل مخططات الانتشار أو مخططات الإحداثيات المتوازية لمتجهات الأهداف.
طرق ذات صلة
المصادر
Bellman, R. (1957). Dynamic Programming. Princeton University Press, Princeton, NJ.
ردمك: 9780691079516تم النسخ.Daellenbach, H. G., & Flood, R. L. (1992). Multi-objective dynamic programming. European Journal of Operational Research, 56(2), 215-225.
افتح مرجع المنشورتم النسخ.