การโปรแกรมพลวัตแบบกำหนดได้ — การหาค่าเหมาะสมที่สุดแบบลำดับที่แม่นยำภายใต้พารามิเตอร์ที่ทราบ
- ผู้เสนอ
- Richard E. Bellman
- ปี
- 1957
- ประเภท
- Exact sequential optimization algorithm
- กลุ่มวิธี
- Simulation / optimization
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
การโปรแกรมพลวัตแบบกำหนดได้ (DDP) เป็นเทคนิคการหาค่าเหมาะสมที่สุดทางคณิตศาสตร์ที่แยกย่อยปัญหาการตัดสินใจหลายขั้นตอนออกเป็นลำดับของปัญหาย่อยที่ง่ายกว่า โดยแก้ปัญหาเหล่านั้นได้อย่างแม่นยำเมื่อพารามิเตอร์ของระบบทั้งหมด — ฟังก์ชันการเปลี่ยนสถานะ ต้นทุน และรางวัล — เป็นที่ทราบอย่างแน่นอน DDP รับประกันนโยบายที่เหมาะสมที่สุดทั่วโลกผ่านหลักการความเหมาะสมที่สุดของเบลล์แมน
แนวคิดเบื้องหลังวิธีการ
ลองนึกภาพการวางแผนเส้นทางที่ถูกที่สุดผ่านเครือข่ายเมืองที่ทราบต้นทุนถนนทั้งหมดล่วงหน้า แทนที่จะประเมินทุกเส้นทางที่เป็นไปได้ทั้งหมด การโปรแกรมพลวัตจะทำงานย้อนกลับ: ในแต่ละเมือง จะบันทึกต้นทุนที่ถูกที่สุดในการไปถึงปลายทางจากที่นั่น เมื่อทุกเมืองได้รับการติดป้ายแล้ว การติดตามเส้นทางที่เหมาะสมที่สุดไปข้างหน้าจะทำได้ง่าย หลักการให้เหตุผลแบบย้อนกลับนี้ — หลักการความเหมาะสมที่สุดของเบลล์แมน — เป็นหัวใจสำคัญของการโปรแกรมพลวัตแบบกำหนดได้: เส้นทางย่อยใดๆ ของเส้นทางที่เหมาะสมที่สุดจะต้องเหมาะสมที่สุดในตัวเอง
ประวัติศาสตร์
Richard Bellman ได้ทำให้การโปรแกรมพลวัตเป็นรูปธรรมในหนังสือของเขาที่ Princeton ในปี 1957 โดยได้หลักการความเหมาะสมที่สุดที่เป็นพื้นฐานของวิธีการ DP ทั้งหมด กรณีแบบกำหนด — ที่การเปลี่ยนสถานะและรางวัลเป็นที่ทราบ — เป็นสูตรดั้งเดิม มันเติบโตจากงานวิจัยการปฏิบัติการในช่วงสงครามของ Bellman และกลายเป็นรากฐานในทฤษฎีการควบคุม เศรษฐศาสตร์ และการหาค่าเหมาะสมที่สุดเชิงการจัดกลุ่ม ต่อมา Bertsekas ได้ขยายและจัดระบบทฤษฎีในหลายเล่ม
ควรใช้เมื่อใด
ใช้การโปรแกรมพลวัตแบบกำหนดได้เมื่อระบบมีขั้นตอนตามลำดับที่กำหนดไว้อย่างชัดเจน ต้นทุนการเปลี่ยนสถานะและผลลัพธ์ทั้งหมดเป็นที่ทราบอย่างแน่นอน และหลักการความเหมาะสมที่สุดสามารถนำมาใช้ได้ (โครงสร้างย่อยที่เหมาะสมที่สุด) เหมาะอย่างยิ่งสำหรับการจัดการสินค้าคงคลัง การจัดสรรทรัพยากรตามเวลา การกำหนดเส้นทางที่สั้นที่สุด และการจัดตารางการผลิตด้วยพารามิเตอร์คงที่ **ห้าม** ใช้เมื่อพารามิเตอร์ไม่แน่นอนหรือสุ่ม — ให้เปลี่ยนไปใช้การโปรแกรมพลวัตแบบสุ่มแทน นอกจากนี้ ควรหลีกเลี่ยง DDP เมื่อพื้นที่สถานะมีขนาดใหญ่มากหรือต่อเนื่องโดยไม่มีโครงสร้างเชิงวิเคราะห์ เนื่องจากคำสาปของมิติทำให้ไม่สามารถคำนวณได้ ไม่เหมาะสมสำหรับปัญหาที่ไม่มีโครงสร้างตามลำดับหรือโครงสร้างแบบเรียกซ้ำ
ข้อจำกัดและข้อควรพิจารณา
- ประสบปัญหาอย่างรุนแรงจากคำสาปของมิติ: ข้อกำหนดในการคำนวณและหน่วยความจำเพิ่มขึ้นแบบทวีคูณตามจำนวนตัวแปรสถานะ
- ต้องการความรู้ที่สมบูรณ์และแม่นยำเกี่ยวกับฟังก์ชันการเปลี่ยนสถานะและโครงสร้างรางวัล ความไม่แน่นอนของพารามิเตอร์ใดๆ จะทำให้แบบจำลองแบบกำหนดใช้ไม่ได้
- การแบ่งส่วนของพื้นที่สถานะหรือการกระทำแบบต่อเนื่องจะทำให้เกิดข้อผิดพลาดในการประมาณค่าและอาจพลาดค่าที่เหมาะสมที่สุดที่แท้จริง
- สมมติโครงสร้างแบบมาร์คอฟ — การตัดสินใจที่เหมาะสมที่สุดในแต่ละขั้นตอนขึ้นอยู่กับสถานะปัจจุบันเท่านั้น ไม่ใช่ประวัติวิธีการเข้าถึงสถานะนั้น
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- รับประกันผลลัพธ์ที่เหมาะสมที่สุดทั่วโลกเมื่อปัญหาสอดคล้องกับหลักการความเหมาะสมที่สุดและพารามิเตอร์เป็นที่ทราบ
- จัดการการตัดสินใจตามลำดับหลายขั้นตอนได้อย่างเป็นธรรมชาติ ซึ่งจะซับซ้อนเกินไปหากเป็นปัญหาการหาค่าเหมาะสมที่สุดขนาดใหญ่เพียงครั้งเดียว
- เมื่อคำนวณฟังก์ชันค่าแล้ว การตัดสินใจที่เหมาะสมที่สุดสำหรับทุกสถานะจะพร้อมใช้งานพร้อมกัน ทำให้สามารถวิเคราะห์ความไวต่อเงื่อนไขเริ่มต้นได้
- สามารถนำไปใช้กับพื้นที่สถานะ-การกระทำทั้งแบบไม่ต่อเนื่องและต่อเนื่องได้ (ด้วยการแบ่งส่วนที่เหมาะสมหรือการจัดการเชิงวิเคราะห์)
- มีความโปร่งใสในเชิงแนวคิด: ขั้นตอนการเหนี่ยวนำย้อนกลับสามารถตรวจสอบและยืนยันได้ง่ายทีละขั้นตอน
การประยุกต์ใช้
- นโยบายการเติมสินค้าคงคลังที่เหมาะสมที่สุดด้วยตารางความต้องการที่ทราบในช่วงเวลาการวางแผนที่จำกัด
- ปัญหาเส้นทางที่สั้นที่สุดและการกำหนดเส้นทางเครือข่าย (เช่น อัลกอริทึม Dijkstra เป็นกรณีพิเศษของ DP)
- การจัดตารางการผลิตและการกำหนดขนาดล็อตในการผลิตด้วยความต้องการและข้อจำกัดด้านกำลังการผลิตที่กำหนดได้
- การสกัดทรัพยากรและการวางแผนการลงทุนด้านทุนในเศรษฐศาสตร์ภายใต้ความแน่นอน
- การจัดลำดับลำดับและชีวสารสนเทศ (เช่น อัลกอริทึม Needleman-Wunsch)
- การวางแผนการเปลี่ยนอุปกรณ์และการบำรุงรักษาด้วยต้นทุนและฟังก์ชันการเสื่อมสภาพที่ทราบ
วิธีการทำงาน
วิธีการทำงาน
กำหนดวัตถุประสงค์ของการหาค่าเหมาะสมที่สุด ขอบเขตการวางแผน (จำกัดหรือไม่มีที่สิ้นสุด) และลำดับการตัดสินใจ ระบุว่าอะไรคือขั้นตอน สถานะ การกระทำ รางวัลหรือต้นทุนทันที r(s, a) และฟังก์ชันการเปลี่ยนสถานะแบบกำหนดได้ s' = f(s, a) ที่จับคู่สถานะ-การกระทำกับสถานะถัดไปได้อย่างแน่นอน
แจกแจงหรือกำหนดพารามิเตอร์ของสถานะที่เป็นไปได้ทั้งหมด S และการกระทำที่ยอมรับได้ทั้งหมด A(s) สำหรับแต่ละสถานะ สำหรับปัญหาที่ไม่ต่อเนื่อง สิ่งนี้จะสร้างตารางสถานะ-การกระทำที่มีจำกัด สำหรับปัญหาต่อเนื่อง จะใช้การแบ่งส่วนหรือรูปแบบการแก้ปัญหาเชิงวิเคราะห์ ข้อกำหนดหน่วยความจำจะปรับขนาดตามขนาดของพื้นที่นี้ — คอขวดในการคำนวณที่สำคัญ
เขียนสมการความเหมาะสมที่สุดของเบลล์แมน: 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]แก้สมการซ้ำทีละขั้นตอนจากช่วงสุดท้ายไปยังช่วงเริ่มต้น (การเหนี่ยวนำย้อนกลับ) ในแต่ละขั้นตอน ทุกสถานะจะได้รับค่าที่เหมาะสมที่สุดและจะบันทึกการกระทำที่ทำให้เกิดค่านั้น สิ่งนี้รับประกันว่าผลลัพธ์ของปัญหาย่อยมีความสอดคล้องกันและเหมาะสมที่สุดทั่วโลกภายใต้แบบจำลองการเปลี่ยนสถานะแบบกำหนดได้
สร้างนโยบายที่เหมาะสมที่สุดด้วยการส่งผ่านไปข้างหน้า: เริ่มต้นจากสถานะเริ่มต้น 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 จะเป็นที่ต้องการเมื่อการตัดสินใจเกิดขึ้นในช่วงหลายขั้นตอนและผลการกระทำที่เหมาะสมที่สุดในแต่ละขั้นตอนขึ้นอยู่กับสถานะของระบบในขณะนั้น
การโปรแกรมพลวัตแบบกำหนดเหมือนกับการเหนี่ยวนำย้อนกลับในทฤษฎีเกมหรือไม่
ทั้งสองมีตรรกะแบบเรียกซ้ำเหมือนกัน — การแก้ปัญหาจากท้ายไปหน้า — แต่การเหนี่ยวนำย้อนกลับในทฤษฎีเกมเกี่ยวข้องกับผู้เล่นหลายคนและการปฏิสัมพันธ์เชิงกลยุทธ์ การโปรแกรมพลวัตแบบกำหนดเป็นปัญหาการหาค่าเหมาะสมที่สุดสำหรับตัวแทนเดี่ยวโดยไม่มีคู่แข่งเชิงกลยุทธ์
การโปรแกรมพลวัตแบบกำหนดสามารถจัดการกับพื้นที่สถานะและการกระทำแบบต่อเนื่องได้หรือไม่
ได้ เมื่อมีผลลัพธ์เชิงวิเคราะห์ (เช่น ปัญหาเชิงเส้น-กำลังสอง) หรือเมื่อฟังก์ชันค่ามีรูปแบบฟังก์ชันที่ทราบ มิฉะนั้น พื้นที่ต่อเนื่องจะต้องถูกแบ่งส่วน ซึ่งจะทำให้เกิดข้อผิดพลาดในการประมาณค่าและเพิ่มภาระในการคำนวณอย่างมาก
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Bellman, R. E. (1957). Dynamic Programming. Princeton University Press, Princeton, NJ.
ISBN: 9780691079516คัดลอกแล้วBertsekas, D. P. (2017). Dynamic Programming and Optimal Control (4th ed., Vol. 1). Athena Scientific, Belmont, MA.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้ว