Skip to content
بازگشت به نتایج جست‌وجو

برنامه‌ریزی پویا تصادفی — تصمیم‌گیری متوالی در شرایط عدم قطعیت

معرفی‌شده توسط
Bellman, R.; formalized for stochastic settings by Puterman, M. L.
سال
1957
نوع
Sequential optimization under uncertainty
خانواده
Simulation / optimization

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

برنامه‌ریزی پویا تصادفی (SDP) یک چارچوب بهینه‌سازی ریاضی برای مسائل تصمیم‌گیری متوالی است که در آن نتایج تا حدی تصادفی هستند. این روش، اصل بهینگی بلمن را به محیط‌های تصادفی گسترش می‌دهد و مسائل را به عنوان فرآیندهای تصمیم‌گیری مارکوف (MDPs) نمایش می‌دهد و سیاست‌های بهینه را با حل معادلات بازگشتی ارزش بر روی حالت‌ها و دوره‌های زمانی محاسبه می‌کند.

شهود پشت روش

مدیریت یک مخزن آب را در طول چندین ماه تصور کنید: هر ماه شما تصمیم می‌گیرید که چه مقدار آب آزاد کنید، اما میزان بارندگی نامشخص است. SDP این مسئله را به زنجیره‌ای از تصمیمات تک‌دوره‌ای تقسیم می‌کند و می‌پرسد: با توجه به سطح فعلی آب و تمام آینده‌های ممکن، کدام سیاست آزادسازی، کل منفعت مورد انتظار را به حداکثر می‌رساند؟ با کار کردن به عقب از دوره نهایی (یا تکرار تا رسیدن به نقطه ثابت)، SDP اقدام بهینه جهانی را در هر حالت ممکن کشف می‌کند — حتی قبل از اینکه عدم قطعیت برطرف شود. بینش کلیدی این است که ارزش آتی بودن در یک حالت مستقل از نحوه رسیدن به آنجاست (خاصیت مارکوف)، که بازگشت را قابل حل می‌کند.

تاریخ

ریچارد بلمن برنامه‌ریزی پویا را در کتاب خود در سال 1957 معرفی کرد و اصل بهینگی را که زیربنای DP قطعی و تصادفی است، بنا نهاد. فرمالیسم فرآیند تصمیم‌گیری مارکوف تصادفی به طور سیستماتیک در دهه‌های 1960-1970 توسعه یافت و به طور جامع توسط مارتین پوترمن در تک‌نگاری سال 1994 او یکپارچه شد، که همچنان مرجع استاندارد برای نظریه SDP با افق متناهی و بی‌نهایت است.

چه زمانی استفاده شود

از SDP زمانی استفاده کنید که تصمیمات به صورت متوالی در طول زمان یا مراحل اتخاذ می‌شوند، نتایج به انتقال‌های تصادفی که خاصیت مارکوف را برآورده می‌کنند بستگی دارند، و یک مدل احتمال کامل برای آن انتقال‌ها در دسترس است یا می‌توان آن را تخمین زد. محرک‌های معمول: تخصیص منابع با عدم قطعیت تقاضا، کنترل موجودی، جایگزینی تجهیزات، برنامه‌ریزی درمان با پاسخ نامشخص بیمار، یا اعزام سیستم انرژی. زمانی استفاده نکنید که فضای حالت برای شمارش بسیار بزرگ است (نفرین ابعاد، SDP دقیق را بدون تقریب از نظر محاسباتی غیرممکن می‌کند)، زمانی که احتمالات انتقال ناشناخته هستند و نمی‌توان آن‌ها را مدل‌سازی کرد (به جای آن یادگیری تقویتی را در نظر بگیرید)، زمانی که تصمیمات یک‌باره و بدون ساختار متوالی هستند (از بهینه‌سازی ایستا استفاده کنید)، یا زمانی که فرض مارکوف توسط وابستگی قوی به تاریخچه نقض می‌شود.

محدودیت‌ها و ملاحظات

  • از نفرین ابعاد رنج می‌برد: الزامات محاسباتی و حافظه با تعداد متغیرهای حالت به صورت نمایی رشد می‌کند.
  • نیاز به تعیین صریح احتمالات انتقال دارد که ممکن است ناشناخته یا گران‌قیمت برای تخمین باشند.
  • روش‌های دقیق محدود به فضاهای حالت و عمل گسسته (یا گسسته‌شده) هستند؛ فضاهای پیوسته نیاز به تقریب دارند.
  • فرض خاصیت مارکوف را دارد؛ سیستم‌هایی با حافظه بلندمدت یا قابلیت مشاهده جزئی نیاز به گسترش‌های پیچیده‌تر (POMDPs) دارند.

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

  • سیاست‌های بهینه جهانی را برای MDPهای خوش‌تعریف با افق متناهی یا تخفیف‌خورده بی‌نهایت تضمین می‌کند.
  • عدم قطعیت چندمرحله‌ای را به طور طبیعی با کدگذاری تمام آینده‌های ممکن در تابع ارزش مدیریت می‌کند.
  • ساختار مارکوف فضای جستجو را در مقایسه با جستجوی جامع به طور چشمگیری کاهش می‌دهد.
  • الگوریتم‌های تکرار سیاست و تکرار ارزش به خوبی درک شده‌اند و تضمین‌های همگرایی اثبات‌شده‌ای دارند.
  • بدون تغییر خط لوله اصلی، به معیارهای حساس به ریسک (CVaR، میانگین-واریانس) و MDPهای محدود گسترش می‌یابد.

کاربردها

  • مدیریت موجودی: یافتن مقادیر سفارش که حداقل هزینه کل مورد انتظار را تحت تقاضای تصادفی در طول چندین دوره به حداقل می‌رساند.
  • برنامه‌ریزی منابع آب: زمان‌بندی آزادسازی مخزن تحت ورودی‌های نامشخص برای تعادل بین تولید برق آبی و خطر سیل.
  • برنامه‌ریزی درمان مراقبت‌های بهداشتی: انتخاب توالی‌های درمانی بیمار با توجه به احتمالات نامشخص پیشرفت بیماری.
  • سیستم‌های انرژی: اعزام بهینه و استراتژی‌های شارژ ذخیره‌سازی تحت تولید تجدیدپذیر نامشخص و قیمت‌های برق.
  • مالی: متعادل‌سازی مجدد سبد سهام و قیمت‌گذاری اختیار معامله تحت دینامیک تصادفی قیمت دارایی.
  • زمان‌بندی نگهداری: تعیین سیاست‌های بازرسی و جایگزینی برای به حداقل رساندن هزینه طول عمر مورد انتظار تجهیزات تحت خرابی تصادفی.

چگونه کار می‌کند

چگونه کار می‌کند

1

تاپل MDP را تعریف کنید (S, A, P, R, gamma): یک فضای حالت S که تمام پیکربندی‌های مرتبط سیستم را در بر می‌گیرد، یک فضای عمل A(s) از تصمیمات مجاز برای هر حالت، یک احتمال انتقال P(s'|s,a) که چگونگی تکامل تصادفی سیستم تحت عمل a را توصیف می‌کند، یک تابع پاداش R(s,a) که پاداش فوری را اندازه‌گیری می‌کند، و یک عامل تخفیف gamma در [0,1] که پاداش‌های آتی را در مقابل پاداش‌های فعلی وزن‌دهی می‌کند.

2

تابع ارزش بهینه V*(s) را از طریق معادله بهینگی بلمن بیان کنید: V*(s) = max بر روی اعمال از [R(s,a) + gamma * sum بر روی s' از P(s'|s,a)*V*(s')]. این معادله بازگشتی بیان می‌کند که بهترین ارزش در حالت s برابر است با بهترین پاداش فوری به علاوه ارزش مورد انتظار تخفیف‌خورده حالت بعدی تحت سیاست بهینه.

فرمول
V^*(s) = \max_{a \in A(s)} \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a)\, V^*(s') \right]
3

V* را به صورت تکراری حل کنید. V_0 را به صورت دلخواه مقداردهی اولیه کنید (مثلاً همه صفرها)، سپس عملگر بلمن را به طور مکرر اعمال کنید: V_{k+1}(s) = max_a [R(s,a) + gamma * sum_{s'} P(s'|s,a) V_k(s')]. تحت شرایط استاندارد، دنباله به صورت هندسی به V* همگرا می‌شود.

فرمول
V_{k+1}(s) = \max_{a} \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a)\, V_k(s') \right]
4

پس از دستیابی به همگرایی، سیاست بهینه pi*(s) را به عنوان عملی که حداکثر را در معادله بلمن در هر حالت به دست می‌آورد، استخراج کنید. این سیاست حریصانه نسبت به V* برای مسئله تخفیف‌خورده با افق بی‌نهایت، به طور اثبات‌شده‌ای بهینه است.

فرمول
\pi^*(s) = \arg\max_{a} \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a)\, V^*(s') \right]
5

تکرار ارزش را زمانی خاتمه دهید که فاصله نرم سوپ بین توابع ارزش متوالی کمتر از یک تلرانس اپسیلون شود: ||V_{k+1} - V_k||_inf < epsilon. سیاست حاصله pi*، اپسیلون/(1-gamma)-بهینه است.

فرمول
\| V_{k+1} - V_k \|_\infty < \varepsilon

دام‌های رایج

  • گسسته‌سازی بیش از حد خشن حالت‌های پیوسته، خطاهای تقریب بزرگی را ایجاد می‌کند که در تابع ارزش منتشر می‌شوند.
  • انتخاب عامل تخفیف gamma نزدیک به 1، همگرایی را به شدت کند می‌کند؛ تنظیمات نزدیک به 1 نیاز به معیارهای خاتمه دقیق دارند.
  • نادیده گرفتن شرایط مرزی پایانی در مسائل با افق متناهی منجر به تخمین‌های ارزش به طور سیستماتیک نادرست در مراحل نهایی می‌شود.
  • نادیده گرفتن خطای مدل به عنوان ناچیز: اگر احتمالات انتقال فرض‌شده به طور قابل توجهی با واقعیت تفاوت داشته باشند، سیاست محاسبه‌شده ممکن است در عمل عملکرد ضعیفی داشته باشد.
  • اشتباه گرفتن سیاست (نگاشت از حالت‌ها به اعمال) با تابع ارزش؛ گزارش تنها V* بدون استخراج pi*، مسئله تصمیم‌گیری را حل‌نشده باقی می‌گذارد.

پرسش‌های متداول

تفاوت بین برنامه‌ریزی پویا قطعی و تصادفی چیست؟

در DP قطعی، حالت بعدی به طور کامل توسط حالت و عمل فعلی تعیین می‌شود، بنابراین هیچ احتمالی درگیر نیست. در SDP، حالت بعدی از یک توزیع احتمال شرطی P(s'|s,a) نمونه‌برداری می‌شود، که نتیجه را تصادفی می‌کند. معادله بلمن در SDP یک امید ریاضی بر روی این انتقال‌ها می‌گیرد، که تفاوت ساختاری کلیدی است.

چگونه یک فضای حالت که برای شمارش بسیار بزرگ است را مدیریت کنم؟

هنگامی که SDP دقیق از نظر محاسباتی غیرممکن است، از برنامه‌ریزی پویا تقریبی (ADP) یا یادگیری تقویتی استفاده کنید. تکنیک‌ها شامل تقریب تابع خطی تابع ارزش، تقریب‌کننده‌های مبتنی بر شبکه عصبی (یادگیری تقویتی عمیق)، و روش‌های مبتنی بر شبیه‌سازی مانند تکرار سیاست تقریبی هستند که همگی تضمین‌های بهینگی را با مقیاس‌پذیری مبادله می‌کنند.

آیا SDP همان فرآیند تصمیم‌گیری مارکوف است؟

یک MDP مدل ریاضی (تاپل S, A, P, R, gamma) است. برنامه‌ریزی پویا تصادفی به خانواده‌ای از الگوریتم‌ها — تکرار ارزش، تکرار سیاست، و انواع آن‌ها — اشاره دارد که برای حل MDPها استفاده می‌شوند. این اصطلاحات در عمل اغلب به جای یکدیگر استفاده می‌شوند.

چه زمانی باید از تکرار سیاست به جای تکرار ارزش استفاده کنم؟

تکرار سیاست برای بسیاری از مسائل در تعداد تکرارهای کمتری نسبت به تکرار ارزش همگرا می‌شود، اما هر تکرار گران‌تر است زیرا نیاز به حل یک سیستم معادلات خطی دارد. تکرار ارزش ساده‌تر برای پیاده‌سازی است و زمانی که فضای حالت بزرگ است ترجیح داده می‌شود. برای مسائل کوچک تا متوسط، تکرار سیاست اغلب در کل سریع‌تر است.

آیا SDP می‌تواند چندین هدف رقابتی را مدیریت کند؟

بله، از طریق MDPهای محدود (CMDPs)، که در آن هزینه‌های ثانویه تجمعی مورد انتظار باید زیر بودجه‌ها باقی بمانند، یا از طریق MDPهای چندهدفه که مجموعه‌های سیاست بهینه پارتو را تولید می‌کنند. با این حال، فرمول‌بندی استاندارد تک‌هدفه، یک پاداش اسکالر را فرض می‌کند؛ اسکالر کردن اهداف متعدد نیاز به استخراج دقیق وزن دارد.

روش‌های مرتبط

منابع

  1. Bellman, R. (1957). Dynamic Programming. Princeton University Press, Princeton, NJ.

    شابک: 9780486428093
    کپی شد.
  2. Puterman, M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, New York.

    شابک: 9780471619772
    کپی شد.