برنامهریزی پویا چندهدفه — سیاستهای بهینه پارتو در تصمیمگیریهای متوالی
- معرفیشده توسط
- Extension of Bellman (1957); formalized by multiple authors from 1970s onward
- سال
- 1957-1975
- نوع
- Exact optimization — recursive multi-objective decomposition
- خانواده
- Simulation / optimization
این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید
چه کاری انجام میدهد؟
برنامهریزی پویا چندهدفه (MODP) برنامهریزی پویای کلاسیک بلمن را به محیطهایی تعمیم میدهد که در آنها تصمیمگیرنده باید چندین هدف رقابتی را به طور همزمان در طول یک دنباله از مراحل بهینه کند. به جای یک سیاست بهینه واحد، مجموعهای از سیاستهای بهینه پارتو را تولید میکند — که هر کدام نمایانگر یک پروفایل مبادله متمایز هستند — با انتشار توابع ارزش برداری در طول فضای حالت به صورت پسرو.
شهود پشت روش
در برنامهریزی پویای تکهدفه، هر حالت یک ارزش بهترین و یک عمل بهترین را حمل میکند. برنامهریزی پویای چندهدفه با ذخیره کردن، در هر حالت، یک جبهه پارتو کامل از بردارهای پاداش تجمعی غیرمغلوب، این را تعمیم میدهد. هنگامی که الگوریتم به صورت پسرو در مراحل تصمیمگیری پیمایش میکند، این مجموعههای پارتو را ادغام و هرس میکند تا فقط سیاستهای واقعاً غیرمغلوب تا مرحله نهایی باقی بمانند. نتیجه یک پاسخ واحد نیست، بلکه یک سطح مبادله کامل است که از آن میتوان یک سیاست را انتخاب کرد که بهترین تطابق را با اولویت تصمیمگیرنده دارد، بدون اینکه نیازی به تعیین وزنها از قبل باشد.
تاریخ
برنامهریزی پویای چندهدفه بر چارچوب برنامهریزی پویای بنیادی ریچارد بلمن که در سال ۱۹۵۷ منتشر شد، بنا شده است. تعمیمها به اهداف برداری در ادبیات تحقیق در عملیات در طول دهههای ۱۹۷۰ و ۱۹۸۰، با هدایت کاربردهایی در مدیریت منابع آب، برنامهریزی نظامی، و سیاست اقتصادی، پدیدار شدند. این حوزه همزمان با نظریه بهینهسازی چندهدفه بالغ شد، با مشارکتهای کلیدی که بازگشت تابع ارزش پارتو و الگوریتمهای هرس را رسمی کردند. این حوزه همچنان یک حوزه تحقیقاتی فعال باقی مانده است، به ویژه در زمینه فرآیندهای تصمیمگیری مارکوف با سیگنالهای پاداش متعدد.
چه زمانی استفاده شود
هنگامی که تصمیمگیریها در طول چندین مرحله متوالی رخ میدهند، زمانی که حداقل دو هدف در تضاد هستند، و زمانی که فضاهای حالت و عمل به اندازه کافی کوچک هستند که بتوان آنها را شمارش یا گسستهسازی کرد، از MODP استفاده کنید. این روش برای تخصیص منابع در طول زمان، زمانبندی پروژههای چندمرحلهای، و ارزیابی سیاستهای بهداشتی یا زیستمحیطی متوالی که در آنها راهحلهای کامل پارتو مورد نیاز است، ایدهآل است. زمانی که فضای حالت بسیار بزرگ است (نفرین ابعاد، محاسبه دقیق جبهه پارتو را غیرممکن میسازد)، زمانی که اهداف به راحتی میتوانند قبل از تجزیه و تحلیل به یک مقیاس واحد ترکیب شوند، یا زمانی که ساختار مسئله غیرمارکوفی است (پاداشهای آینده به تاریخچه فراتر از حالت فعلی بستگی دارند)، از آن استفاده نکنید.
محدودیتها و ملاحظات
- به شدت از نفرین ابعاد رنج میبرد: هزینه محاسباتی و حافظه به صورت نمایی با تعداد متغیرهای حالت و اهداف افزایش مییابد.
- نیاز به فضای حالت گسسته یا گسستهسازی شده دارد، که میتواند خطای تقریب را برای مسائل پیوسته معرفی کند.
- تعداد سیاستهای غیرمغلوب ذخیره شده در هر حالت میتواند بسیار زیاد شود، که روشهای دقیق را برای مسائل با بیش از سه یا چهار هدف غیرعملی میسازد.
- خاصیت مارکوف را فرض میکند — عمل بهینه آینده فقط به حالت فعلی بستگی دارد، نه به تاریخچه تصمیمات گذشته.
- پیادهسازی به طور قابل توجهی پیچیدهتر از برنامهریزی پویای تکهدفه است و نیاز به بررسیهای کارآمد غلبه پارتو و مدیریت مجموعه در هر حالت دارد.
شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.
نقاط قوت
- یک جبهه پارتو کامل از سیاستهای بهینه ارائه میدهد، که به تصمیمگیرندگان دید کاملی از مبادلات اهداف میدهد بدون اینکه مجبور به تعیین وزنها از پیش باشند.
- بهینگی دقیق پارتو را در چارچوب مدل تضمین میکند — هیچ تقریب ابتکاری برای مسائل با اندازه قابل مدیریت وجود ندارد.
- به طور طبیعی ساختارهای تصمیمگیری متوالی و مرحلهای را مدیریت میکند که در آنها اکثر روشهای چندهدفه دیگر نیاز به بازسازی مصنوعی مسئله دارند.
- فاز بهینهسازی را از فاز استخراج ترجیحات جدا میکند، که به اولویتهای ذینفعان اجازه میدهد پس از محاسبه جبهه اعمال شوند.
- به طور طبیعی به محیطهای تصادفی با ذخیره مجموعههای پارتو از مقادیر انتظاری برداری در هر حالت تعمیم مییابد.
کاربردها
- مدیریت مخزن آب چندمرحلهای که کنترل سیل، تامین آبیاری، و تولید برق آبی را به طور همزمان متعادل میکند.
- برنامهریزی درمان سرطان متوالی که کنترل تومور، سمیت، و کیفیت زندگی را در طول چرخههای درمانی بهینه میکند.
- بهینهسازی سبد سهام چنددورهای که بازده، ریسک، و محدودیتهای نقدینگی را در طول افقهای سرمایهگذاری متعادل میکند.
- ارزیابی سیاستهای زیستمحیطی برای سیاستهایی که باید هزینه اقتصادی، کاهش کربن، و تأثیر تنوع زیستی را در طول زمان مبادله کنند.
- مسیریابی و زمانبندی چندهدفه در شبکههای لجستیکی با اهداف رقابتی هزینه، زمان، و قابلیت اطمینان.
- تخصیص منابع متوالی در سبدهای پروژههای تحقیق و توسعه که کارایی بودجه، پتانسیل نوآوری، و زمان ورود به بازار را متعادل میکند.
چگونه کار میکند
چگونه کار میکند
مسئله تصمیمگیری چندمرحلهای را تعریف کنید: مجموعهای از مراحل t = 1, ..., T، فضای حالت S، فضای عمل A، تابع انتقال، و تابع پاداش برداری r(s, a) = (r1, r2, ..., rk) با k هدف. در این مرحله هیچ وزن اسکالری لازم نیست.
فضای حالت را شمارش یا گسستهسازی کنید. برای هر حالت پایانی در مرحله T، مجموعه پارتو را به صورت تکعضوی حاوی بردار پاداش پایانی مقداردهی اولیه کنید. این مقادیر مرزی، بازگشت پسرو را لنگر میاندازند.
در هر حالت s و مرحله t، تابع ارزش برداری V(s, t) را به عنوان مجموعهای از تمام بردارهای پاداش تجمعی غیرمغلوب که از (s, t) تا مرحله پایانی قابل دستیابی هستند، تعریف کنید. بهینگی بلمن اسکالر را با عدم غلبه پارتو جایگزین کنید: یک بردار v بردار v' را مغلوب میکند اگر v حداقل به اندازه v' در هر هدف خوب باشد و حداقل در یکی از آنها به طور قابل توجهی بهتر باشد.
از مرحله T به مرحله 1 به صورت پسرو پیمایش کنید. در هر (s, t)، مقادیر برداری کاندید برای هر عمل ممکن a را با ترکیب پاداش فوری r(s, a) با هر عنصر در V(s', t+1) برای حالت جانشین s' محاسبه کنید. اجتماع را بر روی تمام اعمال بگیرید و بردارهای مغلوب را هرس کنید تا فقط جبهه پارتو برای V(s, t) حفظ شود.
در حالت اولیه، V(s0, 1) حاوی مجموعه کامل بردارهای پاداش تجمعی بهینه پارتو است. هر بردار متناظر با یک سیاست متمایز است. این جبهه پارتو را به تصمیمگیرنده ارائه دهید، که میتواند یک سیاست ترجیحی را بر اساس اولویتهای خود انتخاب کند، یا پس از آن یک مقیاسبندی (مانند مجموع وزنی) را اعمال کند.
دامهای رایج
- برنامهریزی پویای چندهدفه را با اجرای صرف برنامهریزی پویا به طور جداگانه برای هر هدف با وزنهای مختلف اشتباه گرفتن — این رویکرد نواحی غیرمحدب جبهه پارتو را از دست میدهد.
- نادیده گرفتن بررسی اینکه آیا فضای حالت واقعاً مارکوفی است قبل از اعمال روش — متغیرهای حالت پنهان، بازگشت را نامعتبر میسازند.
- دستکم گرفتن اندازه مجموعه پارتو در هر حالت، منجر به اتمام حافظه برای مسائل با اهداف زیاد یا افقهای طولانی میشود.
- اعمال MODP بر روی فضاهای حالت پیوسته یا با ابعاد بالا بدون یک طرح تقریب تضمینکننده همگرایی، نتایج غیرقابل اعتمادی تولید میکند.
- ارائه جبهه پارتو کامل به تصمیمگیرندگان بدون ابزارهای حمایتی برای استخراج ترجیحات، آنها را با گزینههای سیاست بیش از حد، غرق میکند.
پرسشهای متداول
برنامهریزی پویای چندهدفه چگونه با اجرای صرف برنامهریزی پویا به طور جداگانه برای هر هدف متفاوت است؟
اجرای جداگانه DP برای هر هدف، بهینههای تکهدفه فردی را به دست میدهد که عموماً به طور همزمان قابل دستیابی نیستند و ساختار مبادله را به طور کامل از دست میدهند. 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.
باز کردن مرجع انتشارکپی شد.