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

การโปรแกรมเชิงพลวัตหลายวัตถุประสงค์ — นโยบายที่เหมาะสมที่สุดแบบ Pareto เหนือการตัดสินใจเชิงลำดับ

ผู้เสนอ
Extension of Bellman (1957); formalized by multiple authors from 1970s onward
ปี
1957-1975
ประเภท
Exact optimization — recursive multi-objective decomposition
กลุ่มวิธี
Simulation / optimization

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

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

ใช้ทำอะไร?

การโปรแกรมเชิงพลวัตหลายวัตถุประสงค์ (Multi-Objective Dynamic Programming: MODP) ขยายแนวคิดการโปรแกรมเชิงพลวัตแบบดั้งเดิมของ Bellman ไปสู่สถานการณ์ที่ผู้ตัดสินใจต้องหาค่าที่เหมาะสมที่สุดสำหรับวัตถุประสงค์หลายอย่างที่แข่งขันกันพร้อมกันตลอดลำดับขั้นต่างๆ แทนที่จะได้นโยบายที่เหมาะสมที่สุดเพียงหนึ่งเดียว MODP จะสร้างชุดนโยบายที่เหมาะสมที่สุดแบบ Pareto ซึ่งแต่ละนโยบายแสดงถึงลักษณะการแลกเปลี่ยนที่แตกต่างกัน โดยการส่งผ่านฟังก์ชันค่าแบบเวกเตอร์ย้อนกลับผ่านปริภูมิสถานะ

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

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

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

การโปรแกรมเชิงพลวัตหลายวัตถุประสงค์สร้างขึ้นจากกรอบการโปรแกรมเชิงพลวัตพื้นฐานของ Richard Bellman ที่ตีพิมพ์ในปี 1957 การขยายไปสู่วัตถุประสงค์แบบเวกเตอร์ปรากฏในวรรณกรรมวิจัยการดำเนินงานในช่วงทศวรรษ 1970 และ 1980 โดยได้รับแรงผลักดันจากการประยุกต์ใช้ในการจัดการทรัพยากรน้ำ การวางแผนทางทหาร และนโยบายเศรษฐกิจ สาขาวิชานี้เติบโตควบคู่ไปกับทฤษฎีการหาค่าเหมาะสมที่สุดหลายวัตถุประสงค์ โดยมีผลงานสำคัญที่ทำให้การเรียกซ้ำฟังก์ชันค่า Pareto และอัลกอริทึมการตัดแต่งเป็นทางการ ยังคงเป็นพื้นที่วิจัยที่กระตือรือร้น โดยเฉพาะอย่างยิ่งในบริบทของกระบวนการตัดสินใจแบบ Markov ที่มีสัญญาณรางวัลหลายอย่าง

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

ใช้ MODP เมื่อการตัดสินใจเกิดขึ้นในหลายขั้นตอนต่อเนื่องกัน เมื่อมีวัตถุประสงค์อย่างน้อยสองอย่างขัดแย้งกัน และเมื่อปริภูมิสถานะและปริภูมิการกระทำมีขนาดเล็กพอที่จะแจกแจงหรือทำให้เป็นแบบไม่ต่อเนื่องได้ เหมาะอย่างยิ่งสำหรับการจัดสรรทรัพยากรตามช่วงเวลา การจัดตารางโครงการหลายขั้นตอน และการประเมินนโยบายด้านสุขภาพหรือสิ่งแวดล้อมแบบลำดับที่ต้องการโซลูชันที่สมบูรณ์แบบ Pareto ไม่ควรใช้เมื่อปริภูมิสถานะมีขนาดใหญ่มาก (ปัญหา curse of dimensionality ทำให้การคำนวณ Pareto front ที่แม่นยำเป็นไปไม่ได้) เมื่อวัตถุประสงค์สามารถรวมกันเป็นสเกลาร์เดียวได้ง่ายก่อนการวิเคราะห์ หรือเมื่อโครงสร้างปัญหาไม่ใช่แบบ Markovian (รางวัลในอนาคตขึ้นอยู่กับประวัติที่นอกเหนือจากสถานะปัจจุบัน)

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

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

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

จุดแข็ง

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

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

  • การจัดการอ่างเก็บน้ำแบบหลายขั้นตอนที่รักษาสมดุลระหว่างการควบคุมน้ำท่วม การจัดหาน้ำเพื่อการชลประทาน และการผลิตไฟฟ้าพลังน้ำพร้อมกัน
  • การวางแผนการรักษามะเร็งแบบลำดับที่ปรับปรุงการควบคุมเนื้องอก ความเป็นพิษ และคุณภาพชีวิตตลอดวงจรการรักษา
  • การหาค่าเหมาะสมที่สุดของพอร์ตการลงทุนแบบหลายช่วงเวลาที่รักษาสมดุลระหว่างผลตอบแทน ความเสี่ยง และข้อจำกัดด้านสภาพคล่องตลอดช่วงเวลาการลงทุน
  • การประเมินนโยบายสิ่งแวดล้อมสำหรับนโยบายที่ต้องแลกเปลี่ยนระหว่างต้นทุนทางเศรษฐกิจ การลดคาร์บอน และผลกระทบต่อความหลากหลายทางชีวภาพเมื่อเวลาผ่านไป
  • การกำหนดเส้นทางและการจัดตารางเวลาแบบหลายวัตถุประสงค์ในเครือข่ายโลจิสติกส์ที่มีวัตถุประสงค์ด้านต้นทุน เวลา และความน่าเชื่อถือที่แข่งขันกัน
  • การจัดสรรทรัพยากรแบบลำดับในพอร์ตโครงการ R&D ที่รักษาสมดุลระหว่างประสิทธิภาพงบประมาณ ศักยภาพในการสร้างสรรค์นวัตกรรม และเวลาออกสู่ตลาด

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

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

1

กำหนดปัญหาการตัดสินใจแบบหลายขั้นตอน: ชุดของขั้นตอน t = 1, ..., T, ปริภูมิสถานะ S, ปริภูมิการกระทำ A, ฟังก์ชันการเปลี่ยนสถานะ, และฟังก์ชันรางวัลแบบเวกเตอร์ r(s, a) = (r1, r2, ..., rk) ที่มี k วัตถุประสงค์ ไม่จำเป็นต้องใช้น้ำหนักแบบสเกลาร์ในขั้นตอนนี้

2

แจกแจงหรือทำให้ปริภูมิสถานะเป็นแบบไม่ต่อเนื่อง สำหรับแต่ละสถานะปลายทางที่ขั้นตอน T ให้เริ่มต้นชุด Pareto เป็นซิงเกิลตันที่มีเวกเตอร์รางวัลปลายทาง ค่าขอบเขตเหล่านี้เป็นจุดยึดสำหรับการเรียกซ้ำแบบย้อนหลัง

3

ที่แต่ละสถานะ s และขั้นตอน t ให้กำหนดฟังก์ชันค่าแบบเวกเตอร์ V(s, t) เป็นชุดของเวกเตอร์รางวัลสะสมที่ไม่ถูกครอบงำทั้งหมดที่สามารถเข้าถึงได้จาก (s, t) ไปยังขั้นตอนปลายทาง แทนที่การหาค่าเหมาะสมที่สุดของ Bellman แบบสเกลาร์ด้วยการไม่ถูกครอบงำแบบ Pareto: เวกเตอร์ v ครอบงำ v' หาก v ดีกว่าอย่างน้อยเท่ากันในทุกวัตถุประสงค์และดีกว่าอย่างเคร่งครัดในอย่างน้อยหนึ่งวัตถุประสงค์

4

กวาดถอยหลังตั้งแต่ขั้นตอน T ไปยังขั้นตอน 1 ที่แต่ละ (s, t) ให้คำนวณค่าเวกเตอร์ผู้สมัครสำหรับการกระทำที่เป็นไปได้ทุกอย่าง a โดยการรวมรางวัลทันที r(s, a) กับแต่ละองค์ประกอบใน V(s', t+1) สำหรับสถานะผู้สืบทอด s' นำผลรวมของการกระทำทั้งหมดและตัดแต่งเวกเตอร์ที่ถูกครอบงำออก เพื่อคงไว้เฉพาะ Pareto front สำหรับ V(s, t)

5

ที่สถานะเริ่มต้น V(s0, 1) จะมีชุดเวกเตอร์รางวัลสะสมที่เหมาะสมที่สุดแบบ Pareto ที่สมบูรณ์ แต่ละเวกเตอร์สอดคล้องกับนโยบายที่แตกต่างกัน นำเสนอ Pareto front นี้แก่ผู้ตัดสินใจ ซึ่งสามารถเลือกนโยบายที่ต้องการตามลำดับความสำคัญของตน หรือใช้การปรับเป็นสเกลาร์ (เช่น ผลรวมถ่วงน้ำหนัก) ภายหลัง

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

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

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

การโปรแกรมเชิงพลวัตหลายวัตถุประสงค์แตกต่างจากการรันการโปรแกรมเชิงพลวัตแยกกันสำหรับแต่ละวัตถุประสงค์อย่างไร?

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

เมื่อใดที่ curse of dimensionality ทำให้ MODP ไม่สามารถนำไปใช้ได้จริง?

MODP จะไม่สามารถจัดการได้เมื่อปริภูมิสถานะมีตัวแปรไม่ต่อเนื่องมากกว่าสองสามตัว เมื่อช่วงเวลาการวางแผนยาวนานมาก หรือเมื่อมีวัตถุประสงค์มากกว่าสามหรือสี่อย่าง (ทำให้ Pareto front ในแต่ละสถานะเติบโตแบบทวีคูณ) โดยทั่วไปแล้ววิธีการประมาณค่า เช่น การเรียนรู้แบบเสริมแรงหลายวัตถุประสงค์ หรือการค้นหา Pareto แบบฮิวริสติก จะเป็นที่นิยมในกรณีดังกล่าว

MODP สามารถจัดการกับความไม่แน่นอนในการเปลี่ยนสถานะหรือรางวัลได้หรือไม่?

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

ฉันจำเป็นต้องระบุน้ำหนักวัตถุประสงค์ก่อนที่จะรัน MODP หรือไม่?

ไม่ — นี่คือหนึ่งในข้อได้เปรียบหลักของ MODP ไม่จำเป็นต้องมีน้ำหนักหรือข้อมูลความชอบในระหว่างเฟสการหาค่าเหมาะสมที่สุด อัลกอริทึมจะคำนวณ Pareto front ทั้งหมด และผู้ตัดสินใจจะนำความชอบของตนไปใช้หลังจากนั้นเพื่อเลือกนโยบายที่เฉพาะเจาะจง

MODP สร้างผลลัพธ์อะไร และควรตีความอย่างไร?

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

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

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

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

    ISBN: 9780691079516
    คัดลอกแล้ว
  2. Daellenbach, H. G., & Flood, R. L. (1992). Multi-objective dynamic programming. European Journal of Operational Research, 56(2), 215-225.

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