Skip to content
กลับไปยังผลการค้นหา

การโปรแกรมพลวัตแบบกำหนดได้ — การหาค่าเหมาะสมที่สุดแบบลำดับที่แม่นยำภายใต้พารามิเตอร์ที่ทราบ

ผู้เสนอ
Richard E. Bellman
ปี
1957
ประเภท
Exact sequential optimization algorithm
กลุ่มวิธี
Simulation / optimization

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

การโปรแกรมพลวัตแบบกำหนดได้ (DDP) เป็นเทคนิคการหาค่าเหมาะสมที่สุดทางคณิตศาสตร์ที่แยกย่อยปัญหาการตัดสินใจหลายขั้นตอนออกเป็นลำดับของปัญหาย่อยที่ง่ายกว่า โดยแก้ปัญหาเหล่านั้นได้อย่างแม่นยำเมื่อพารามิเตอร์ของระบบทั้งหมด — ฟังก์ชันการเปลี่ยนสถานะ ต้นทุน และรางวัล — เป็นที่ทราบอย่างแน่นอน DDP รับประกันนโยบายที่เหมาะสมที่สุดทั่วโลกผ่านหลักการความเหมาะสมที่สุดของเบลล์แมน

แนวคิดเบื้องหลังวิธีการ

ลองนึกภาพการวางแผนเส้นทางที่ถูกที่สุดผ่านเครือข่ายเมืองที่ทราบต้นทุนถนนทั้งหมดล่วงหน้า แทนที่จะประเมินทุกเส้นทางที่เป็นไปได้ทั้งหมด การโปรแกรมพลวัตจะทำงานย้อนกลับ: ในแต่ละเมือง จะบันทึกต้นทุนที่ถูกที่สุดในการไปถึงปลายทางจากที่นั่น เมื่อทุกเมืองได้รับการติดป้ายแล้ว การติดตามเส้นทางที่เหมาะสมที่สุดไปข้างหน้าจะทำได้ง่าย หลักการให้เหตุผลแบบย้อนกลับนี้ — หลักการความเหมาะสมที่สุดของเบลล์แมน — เป็นหัวใจสำคัญของการโปรแกรมพลวัตแบบกำหนดได้: เส้นทางย่อยใดๆ ของเส้นทางที่เหมาะสมที่สุดจะต้องเหมาะสมที่สุดในตัวเอง

ประวัติศาสตร์

Richard Bellman ได้ทำให้การโปรแกรมพลวัตเป็นรูปธรรมในหนังสือของเขาที่ Princeton ในปี 1957 โดยได้หลักการความเหมาะสมที่สุดที่เป็นพื้นฐานของวิธีการ DP ทั้งหมด กรณีแบบกำหนด — ที่การเปลี่ยนสถานะและรางวัลเป็นที่ทราบ — เป็นสูตรดั้งเดิม มันเติบโตจากงานวิจัยการปฏิบัติการในช่วงสงครามของ Bellman และกลายเป็นรากฐานในทฤษฎีการควบคุม เศรษฐศาสตร์ และการหาค่าเหมาะสมที่สุดเชิงการจัดกลุ่ม ต่อมา Bertsekas ได้ขยายและจัดระบบทฤษฎีในหลายเล่ม

ควรใช้เมื่อใด

ใช้การโปรแกรมพลวัตแบบกำหนดได้เมื่อระบบมีขั้นตอนตามลำดับที่กำหนดไว้อย่างชัดเจน ต้นทุนการเปลี่ยนสถานะและผลลัพธ์ทั้งหมดเป็นที่ทราบอย่างแน่นอน และหลักการความเหมาะสมที่สุดสามารถนำมาใช้ได้ (โครงสร้างย่อยที่เหมาะสมที่สุด) เหมาะอย่างยิ่งสำหรับการจัดการสินค้าคงคลัง การจัดสรรทรัพยากรตามเวลา การกำหนดเส้นทางที่สั้นที่สุด และการจัดตารางการผลิตด้วยพารามิเตอร์คงที่ **ห้าม** ใช้เมื่อพารามิเตอร์ไม่แน่นอนหรือสุ่ม — ให้เปลี่ยนไปใช้การโปรแกรมพลวัตแบบสุ่มแทน นอกจากนี้ ควรหลีกเลี่ยง DDP เมื่อพื้นที่สถานะมีขนาดใหญ่มากหรือต่อเนื่องโดยไม่มีโครงสร้างเชิงวิเคราะห์ เนื่องจากคำสาปของมิติทำให้ไม่สามารถคำนวณได้ ไม่เหมาะสมสำหรับปัญหาที่ไม่มีโครงสร้างตามลำดับหรือโครงสร้างแบบเรียกซ้ำ

ข้อจำกัดและข้อควรพิจารณา

  • ประสบปัญหาอย่างรุนแรงจากคำสาปของมิติ: ข้อกำหนดในการคำนวณและหน่วยความจำเพิ่มขึ้นแบบทวีคูณตามจำนวนตัวแปรสถานะ
  • ต้องการความรู้ที่สมบูรณ์และแม่นยำเกี่ยวกับฟังก์ชันการเปลี่ยนสถานะและโครงสร้างรางวัล ความไม่แน่นอนของพารามิเตอร์ใดๆ จะทำให้แบบจำลองแบบกำหนดใช้ไม่ได้
  • การแบ่งส่วนของพื้นที่สถานะหรือการกระทำแบบต่อเนื่องจะทำให้เกิดข้อผิดพลาดในการประมาณค่าและอาจพลาดค่าที่เหมาะสมที่สุดที่แท้จริง
  • สมมติโครงสร้างแบบมาร์คอฟ — การตัดสินใจที่เหมาะสมที่สุดในแต่ละขั้นตอนขึ้นอยู่กับสถานะปัจจุบันเท่านั้น ไม่ใช่ประวัติวิธีการเข้าถึงสถานะนั้น

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • รับประกันผลลัพธ์ที่เหมาะสมที่สุดทั่วโลกเมื่อปัญหาสอดคล้องกับหลักการความเหมาะสมที่สุดและพารามิเตอร์เป็นที่ทราบ
  • จัดการการตัดสินใจตามลำดับหลายขั้นตอนได้อย่างเป็นธรรมชาติ ซึ่งจะซับซ้อนเกินไปหากเป็นปัญหาการหาค่าเหมาะสมที่สุดขนาดใหญ่เพียงครั้งเดียว
  • เมื่อคำนวณฟังก์ชันค่าแล้ว การตัดสินใจที่เหมาะสมที่สุดสำหรับทุกสถานะจะพร้อมใช้งานพร้อมกัน ทำให้สามารถวิเคราะห์ความไวต่อเงื่อนไขเริ่มต้นได้
  • สามารถนำไปใช้กับพื้นที่สถานะ-การกระทำทั้งแบบไม่ต่อเนื่องและต่อเนื่องได้ (ด้วยการแบ่งส่วนที่เหมาะสมหรือการจัดการเชิงวิเคราะห์)
  • มีความโปร่งใสในเชิงแนวคิด: ขั้นตอนการเหนี่ยวนำย้อนกลับสามารถตรวจสอบและยืนยันได้ง่ายทีละขั้นตอน

การประยุกต์ใช้

  • นโยบายการเติมสินค้าคงคลังที่เหมาะสมที่สุดด้วยตารางความต้องการที่ทราบในช่วงเวลาการวางแผนที่จำกัด
  • ปัญหาเส้นทางที่สั้นที่สุดและการกำหนดเส้นทางเครือข่าย (เช่น อัลกอริทึม Dijkstra เป็นกรณีพิเศษของ DP)
  • การจัดตารางการผลิตและการกำหนดขนาดล็อตในการผลิตด้วยความต้องการและข้อจำกัดด้านกำลังการผลิตที่กำหนดได้
  • การสกัดทรัพยากรและการวางแผนการลงทุนด้านทุนในเศรษฐศาสตร์ภายใต้ความแน่นอน
  • การจัดลำดับลำดับและชีวสารสนเทศ (เช่น อัลกอริทึม Needleman-Wunsch)
  • การวางแผนการเปลี่ยนอุปกรณ์และการบำรุงรักษาด้วยต้นทุนและฟังก์ชันการเสื่อมสภาพที่ทราบ

วิธีการทำงาน

วิธีการทำงาน

1

กำหนดวัตถุประสงค์ของการหาค่าเหมาะสมที่สุด ขอบเขตการวางแผน (จำกัดหรือไม่มีที่สิ้นสุด) และลำดับการตัดสินใจ ระบุว่าอะไรคือขั้นตอน สถานะ การกระทำ รางวัลหรือต้นทุนทันที r(s, a) และฟังก์ชันการเปลี่ยนสถานะแบบกำหนดได้ s' = f(s, a) ที่จับคู่สถานะ-การกระทำกับสถานะถัดไปได้อย่างแน่นอน

2

แจกแจงหรือกำหนดพารามิเตอร์ของสถานะที่เป็นไปได้ทั้งหมด S และการกระทำที่ยอมรับได้ทั้งหมด A(s) สำหรับแต่ละสถานะ สำหรับปัญหาที่ไม่ต่อเนื่อง สิ่งนี้จะสร้างตารางสถานะ-การกระทำที่มีจำกัด สำหรับปัญหาต่อเนื่อง จะใช้การแบ่งส่วนหรือรูปแบบการแก้ปัญหาเชิงวิเคราะห์ ข้อกำหนดหน่วยความจำจะปรับขนาดตามขนาดของพื้นที่นี้ — คอขวดในการคำนวณที่สำคัญ

3

เขียนสมการความเหมาะสมที่สุดของเบลล์แมน: V_t(s) = max เหนือ a ใน A(s) ของ [r(s,a) + V_{t+1}(f(s,a))] สำหรับปัญหาที่มีขอบเขตจำกัด ให้ค่าเริ่มต้น V_T(s) ด้วยค่าสุดท้ายและทำการเรียกซ้ำแบบย้อนกลับจากขั้นตอน T-1 ไปยังขั้นตอน 0 สำหรับขอบเขตที่ไม่มีที่สิ้นสุด ให้ทำการอัปเดตค่าซ้ำจนกว่าจะบรรจบกัน (การวนซ้ำค่า)

สูตร
V_t(s) = \max_{a \in A(s)} \bigl[ r(s, a) + V_{t+1}(f(s, a)) \bigr]
4

แก้สมการซ้ำทีละขั้นตอนจากช่วงสุดท้ายไปยังช่วงเริ่มต้น (การเหนี่ยวนำย้อนกลับ) ในแต่ละขั้นตอน ทุกสถานะจะได้รับค่าที่เหมาะสมที่สุดและจะบันทึกการกระทำที่ทำให้เกิดค่านั้น สิ่งนี้รับประกันว่าผลลัพธ์ของปัญหาย่อยมีความสอดคล้องกันและเหมาะสมที่สุดทั่วโลกภายใต้แบบจำลองการเปลี่ยนสถานะแบบกำหนดได้

5

สร้างนโยบายที่เหมาะสมที่สุดด้วยการส่งผ่านไปข้างหน้า: เริ่มต้นจากสถานะเริ่มต้น s_0 ใช้ pi*(s) = argmax_a [r(s,a) + V*(f(s,a))] ในแต่ละขั้นตอน โดยทำตามการกระทำที่เหมาะสมที่สุดที่บันทึกไว้ ลำดับการตัดสินใจที่ได้คือแผนที่เหมาะสมที่สุดทั่วโลกภายใต้พารามิเตอร์ที่ทราบและคงที่

สูตร
\pi^*(s) = \arg\max_{a \in A(s)} \bigl[ r(s, a) + V^*(f(s, a)) \bigr]

ข้อผิดพลาดที่พบบ่อย

  • การสับสนระหว่าง DP แบบกำหนดได้กับ DP แบบสุ่ม: หากพารามิเตอร์ของระบบใดไม่แน่นอน ผลลัพธ์จากแบบจำลองแบบกำหนดจะมองโลกในแง่ดีเกินไปและอาจทำให้เข้าใจผิดได้
  • การเลือกการแทนค่าสถานะที่หยาบเกินไป (สูญเสียความเหมาะสมที่สุด) หรือละเอียดเกินไป (ทำให้พื้นที่สถานะระเบิด) การออกแบบพื้นที่สถานะอย่างระมัดระวังจึงมีความสำคัญอย่างยิ่ง
  • การละเลยเงื่อนไขขอบเขต: ค่าสุดท้ายของช่วงที่ไม่ถูกต้อง V_T(s) จะแพร่กระจายข้อผิดพลาดไปทั่วการเรียกซ้ำแบบย้อนกลับทั้งหมด
  • การใช้ DP กับปัญหาที่ขาดโครงสร้างย่อยที่เหมาะสมที่สุด ซึ่งความเหมาะสมที่สุดในระดับท้องถิ่นไม่รับประกันความเหมาะสมที่สุดทั่วโลก
  • การสมมติว่ามีขอบเขตจำกัดเมื่อปัญหามีขอบเขตอนันต์อย่างแท้จริง หรือในทางกลับกัน ทำให้เกิดการกำหนดสูตรการเรียกซ้ำที่ไม่เหมาะสม

คำถามที่พบบ่อย

การโปรแกรมพลวัตแบบกำหนดได้แตกต่างจากการโปรแกรมพลวัตแบบสุ่มอย่างไร

ในการโปรแกรมพลวัตแบบกำหนดได้ สถานะถัดไป s' = f(s, a) เป็นฟังก์ชันที่ทราบ — ไม่มีสุ่ม การโปรแกรมพลวัตแบบสุ่มจะแทนที่ f ด้วยการแจกแจงความน่าจะเป็น P(s'|s, a) และหาค่าที่คาดหวังสูงสุด การโปรแกรมพลวัตแบบกำหนดนั้นง่ายกว่าและแม่นยำ การโปรแกรมพลวัตแบบสุ่มนั้นเหมาะสมเมื่อผลลัพธ์ไม่แน่นอน

คำสาปของมิติคืออะไร และเหตุใดจึงมีความสำคัญ

Bellman เป็นผู้บัญญัติศัพท์นี้เพื่ออธิบายว่าพื้นที่สถานะเติบโตแบบทวีคูณตามจำนวนตัวแปรสถานะอย่างไร ตัวอย่างเช่น ตัวแปรสถานะ 10 ตัว แต่ละตัวมี 100 ระดับที่ไม่ต่อเนื่อง ทำให้เกิดสถานะ 10^20 — เกินกว่าหน่วยความจำของคอมพิวเตอร์ใดๆ สิ่งนี้ทำให้ DP ที่แม่นยำไม่สามารถทำได้สำหรับปัญหาที่มีมิติสูง ซึ่งกระตุ้นให้เกิดวิธีการประมาณค่า เช่น DP ประมาณค่า หรือการเรียนรู้แบบเสริมกำลัง

เมื่อใดที่ฉันควรใช้การโปรแกรมเชิงเส้นแทน DP

ใช้การโปรแกรมเชิงเส้นเมื่อปัญหาสามารถแสดงเป็นปัญหาการหาค่าเหมาะสมที่สุดในระยะเวลาเดียวพร้อมข้อจำกัดและวัตถุประสงค์เชิงเส้น DP จะเป็นที่ต้องการเมื่อการตัดสินใจเกิดขึ้นในช่วงหลายขั้นตอนและผลการกระทำที่เหมาะสมที่สุดในแต่ละขั้นตอนขึ้นอยู่กับสถานะของระบบในขณะนั้น

การโปรแกรมพลวัตแบบกำหนดเหมือนกับการเหนี่ยวนำย้อนกลับในทฤษฎีเกมหรือไม่

ทั้งสองมีตรรกะแบบเรียกซ้ำเหมือนกัน — การแก้ปัญหาจากท้ายไปหน้า — แต่การเหนี่ยวนำย้อนกลับในทฤษฎีเกมเกี่ยวข้องกับผู้เล่นหลายคนและการปฏิสัมพันธ์เชิงกลยุทธ์ การโปรแกรมพลวัตแบบกำหนดเป็นปัญหาการหาค่าเหมาะสมที่สุดสำหรับตัวแทนเดี่ยวโดยไม่มีคู่แข่งเชิงกลยุทธ์

การโปรแกรมพลวัตแบบกำหนดสามารถจัดการกับพื้นที่สถานะและการกระทำแบบต่อเนื่องได้หรือไม่

ได้ เมื่อมีผลลัพธ์เชิงวิเคราะห์ (เช่น ปัญหาเชิงเส้น-กำลังสอง) หรือเมื่อฟังก์ชันค่ามีรูปแบบฟังก์ชันที่ทราบ มิฉะนั้น พื้นที่ต่อเนื่องจะต้องถูกแบ่งส่วน ซึ่งจะทำให้เกิดข้อผิดพลาดในการประมาณค่าและเพิ่มภาระในการคำนวณอย่างมาก

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

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

    ISBN: 9780691079516
    คัดลอกแล้ว
  2. Bertsekas, D. P. (2017). Dynamic Programming and Optimal Control (4th ed., Vol. 1). Athena Scientific, Belmont, MA.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว