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

برنامه‌ریزی پویا

معرفی‌شده توسط
Richard Bellman
سال
1957
نوع
Exact combinatorial optimization via recursive decomposition
خانواده
Mathematical programming

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

اندازه قلم

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

برنامه‌ریزی پویا (DP) یک تکنیک بهینه‌سازی دقیق است که توسط ریچارد بلمن در سال ۱۹۵۷ برای حل مسائل تصمیم‌گیری چندمرحله‌ای معرفی شد. این روش یک مسئله پیچیده را به زیرمسائل ساده‌تر و همپوشان تجزیه می‌کند، هر زیرمسئله را یک بار حل می‌کند و نتایج را ذخیره می‌کند تا از محاسبات اضافی جلوگیری شود. برنامه‌ریزی پویا که بر پایه اصل بهینگی استوار است، هرگاه مسئله دارای زیرمسائل همپوشان و ساختار زیرین بهینه باشد، راه‌حل‌های بهینه سراسری را تضمین می‌کند.

شهود پشت روش

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

تاریخ

ریچارد بلمن اصطلاح «برنامه‌ریزی پویا» را در سال ۱۹۵۷ در حالی که در شرکت رند کار می‌کرد، ابداع کرد و عمداً کلمه «برنامه‌ریزی» را برای اشاره به برنامه‌ریزی (planning) به جای کدنویسی کامپیوتری انتخاب کرد. اصل بهینگی که او بیان کرد، پایه نظری برای نظریه کنترل، تحقیق در عملیات و بعدها یادگیری تقویتی شد. الگوریتم‌های کلاسیک برنامه‌ریزی پویا — کوتاه‌ترین مسیر دایکسترا، الگوریتم ویتربی و هم‌ترازکننده توالی نیدلمن-وانش — همگی مستقیماً از چارچوب بلمن نشأت می‌گیرند.

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

برنامه‌ریزی پویا زمانی مناسب است که یک مسئله دارای زیرمسائل همپوشان و ساختار زیرین بهینه باشد — ویژگی‌هایی که در تصمیم‌گیری‌های متوالی، تخصیص منابع، زمان‌بندی و وظایف هم‌ترازی رشته‌ای رایج هستند. این روش مستلزم آن است که فضای حالت کاملاً قابل شمارش و با اندازه قابل مدیریت باشد؛ این روش در صورت زیاد بودن یا پیوسته بودن متغیرهای حالت، از نفرین ابعاد رنج می‌برد. برای مسائلی با فضاهای حالت غیرقابل حل، برنامه‌ریزی پویا تقریبی یا یادگیری تقویتی جایگزین‌های ارجح هستند.

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

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

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

نقاط قوت

  • راه‌حل‌های دقیق و بهینه سراسری را برای مسائلی که اصل بهینگی را برآورده می‌کنند، تضمین می‌کند.
  • با استفاده از یادداشت‌برداری (memoization)، محاسبات اضافی را حذف می‌کند و به زمان چندجمله‌ای در تعداد حالات دست می‌یابد.
  • یک سیاست بهینه صریح، نه صرفاً یک ارزش بهینه، تولید می‌کند که امکان پشتیبانی مستقیم از تصمیم‌گیری را فراهم می‌آورد.
  • کاربرد گسترده‌ای در حوزه‌هایی از جمله نظریه کنترل، بیوانفورماتیک، اقتصاد و تحقیق در عملیات دارد.

کاربردها

  • مسائل کوتاه‌ترین مسیر و مسیریابی در شبکه‌ها (بلمن-فورد، انواع دایکسترا).
  • هم‌ترازی توالی در زیست‌شناسی محاسباتی (الگوریتم‌های نیدلمن-وانش، اسمیت-واترمن).
  • تخصیص بهینه منابع و مسائل ترکیبیاتی از نوع کوله‌پشتی در تحقیق در عملیات.
  • تشخیص گفتار و دست‌خط از طریق الگوریتم ویتربی بر روی مدل‌های پنهان مارکوف.
  • کنترل بهینه و بهینه‌سازی سبد سهام چند دوره‌ای در اقتصاد و مهندسی.

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

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

1

مسئله بهینه‌سازی کلی به صورت یک رابطه بازگشتی بیان می‌شود. برای هر حالت s و مرحله تصمیم‌گیری n، تابع ارزش V_n(s) برابر با بهترین پاداش فوری به علاوه ارزش تنزیل‌شده حالت بعدی حاصل است. این معادله بلمن اصل بهینگی را رسمی می‌کند: هر زیرمسیر از یک مسیر بهینه باید خود بهینه باشد.

فرمول
V_n(s) = \max_{a \in A(s)} \left[ r(s,a) + \gamma V_{n-1}(T(s,a)) \right]
2

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

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

ارزش‌های محاسبه‌شده در جدولی که با حالت‌ها فهرست‌بندی شده است، ذخیره می‌شوند. حالت‌های پایانی یک ارزش پایه صفر (یا یک پاداش معلوم) دریافت می‌کنند و تمام ورودی‌های دیگر با حل شدن زیرمسائل پر می‌شوند. یادداشت‌برداری (Memoization) تضمین می‌کند که هر حالت حداکثر یک بار ارزیابی شود و جستجوی بازگشتی نمایی را به زمان چندجمله‌ای در تعداد حالات و مراحل کاهش می‌دهد.

فرمول
\text{Table}[s] = \begin{cases} 0 & \text{if } s \in S_{\text{terminal}} \\ V^*(s) & \text{otherwise} \end{cases}
4

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

فرمول
\pi^*(s) = \arg\max_{a \in A(s)} \left[ r(s,a) + \gamma \, \text{Table}[T(s,a)] \right]

دام‌های رایج

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

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

تفاوت بین برنامه‌ریزی پویا و تقسیم و حل چیست؟

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

چه زمانی باید از یادداشت‌برداری از بالا به پایین در مقابل جدول‌بندی از پایین به بالا استفاده کنم؟

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

برنامه‌ریزی پویا چه ارتباطی با یادگیری تقویتی دارد؟

برنامه‌ریزی پویا کلاسیک به یک مدل فرآیند تصمیم‌گیری مارکوف کاملاً شناخته‌شده (احتمالات انتقال و پاداش‌ها) نیاز دارد. یادگیری تقویتی ایده‌های برنامه‌ریزی پویا را به محیط‌هایی که مدل ناشناخته است، گسترش می‌دهد و به جای آن از تجربه نمونه‌برداری‌شده استفاده می‌کند. الگوریتم‌هایی مانند Q-learning و روش‌های گرادیان سیاست، رویه‌های تقریبی برنامه‌ریزی پویا هستند که توابع ارزش را از تعامل به جای یک مدل صریح یاد می‌گیرند.

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

منابع

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

    شابک: 978-0-691-07951-6
    کپی شد.