Quy hoạch động sai phân rời rạc (DDDP-Discrete Differential Dynamic Programming) là một thủ tục quy hoạch động lặp, được đặc biệt thiết kế để khắc phục một số khó khăn của cách tiếp cận quy hoạch động đã được đề cập
đến ở trước. Quy hoạch động sai phân rời rạc sử dụng phương trình đệ quy giống như quy hoạch động để tìm kiếm trong số các trạng thái rời rạc thuộc miền giai đoạn-trạng thái. Thay bằng việc tìm kiếm nghiệm tối ưu trên toàn miền giai đoạn-trạng thái như trong trường hợp quy hoạch động, quy hoạch
động sai phân rời rạc chỉ kiểm tra một phần của miền giai đoạn-trạng thái và do đó tiết kiệm thời gian và bộ nhớ máy tính (Chow et al., 1975). Quy trình tối
ưu hóa này được giải thông qua các bước lặp của các trạng thái và các quyết
định thử nghiệm để tìm kiếm sự tối ưu cho một hệ thống với những ràng buộc là các trạng thái và các quyết định thử nghiệm phải nằm trong miền khả thi tương ứng, đó là, khả thi trong trong các không gian trạng thái và quyết định.
Trong quy hoạch động sai phân rời rạc, bước đầu tiên là giả thiết một chuỗi thử nghiệm của các quyết định có thể chấp nhận được gọi là chính sách thử nghiệm và các vector trạng thái của mỗi giai đoạn được tính tương ứng.
Chuỗi các trạng thái nằm trong miền trạng thái khả thi cho các giai đoạn khác nhau được gọi là quỹ đạo thử nghiệm. Một quy trình khác với thủ tục trên là
đầu tiên đi giả sử một quỹ đạo thử nghiệm và sau đó sử dụng nó để tính ra chính sách thử nghiệm. Một vài trạng thái ở lân cận một quỹ đạo thử nghiệm, có thể được đưa vào hình thành một dải được gọi là hành lang quỹ đạo thử nghiệm (Xem hình 4.2.1).
H×nh 4.2.1
Sự thiết lập hành lang quanh quỹ đạo thử nghiệm cho một bài toán ba giai đoạn.
Trong thực hành thông thường không gian trạng thái được rời rạc hoá thành các số gia đều nhau, gọi là các số gia trạng thái, trong đó tổng số các rời rạc hóa, được xem là các điểm lưới hay các điểm mắt cáo, cho mỗi biến trạng thái là như nhau. Do đó, các quyết định phải được lựa chọn tương ứng với phương pháp rời rạc hóa các biến trạng thái. Khoảng số gia của biến quyết
định phụ thuộc vào khoảng số gia của biến trạng thái tương ứng.
Hướng tiếp cận quy hoạch động truyền thống được áp dụng trong một bài toán quy hoạch động sai phân rời rạc cho các trạng thái trong hành lang đó sử dụng mối quan hệ đệ quy để tìm ra một quỹ đạo tốt hơn. Quỹ đạo này xác
định một chính sách hay tập hợp của các quyết định trong hành lang đã được
đưa ra. Quỹ đạo thử nghiệm này sau đó được sử dụng như một quỹ đạo mới để tạo ra một hành lang mới. Quá trình hình thành và tối ưu hành lang này xét tới các trạng thái nằm trong hành lang đó và qua trình tìm ngược trở lại để nhận
được một quỹ đạo tốt hơn cho toàn bộ hệ thống được gọi là một bước lặp.
Quỹ đạo mới, định nghĩa hệ thống thông qua sự tối ưu của hành lang thử nghiệm, sau đó được sử dụng như quỹ đạo thử nghiệm mới để thiết lập hành lang tốt hơn cho bước lặp tiếp theo. Thủ tục này được lặp tới quá một bước lặp thứ k nào đó mà ở đó cho ra một hành lang. Hành lang này cung cấp một lợi nhuận của hệ thống fk sao cho các bước lặp tiếp theo với cùng kích thước của hành lang này sẽ tạo ra một chênh lệch trong lợi nhuận hệ thống, fk-fk-1 nhỏ hơn một dung sai xác định. Tại điểm này trong thủ tục tối ưu hóa, kích thước của số gia trạng thái có thể được giảm xuống để thiết lập một hành lang mới mà trong đó các trạng thái hay các điểm lưới xít nhau hơn. Một hành lang nhỏ hơn được hình thành quanh quỹ đạo đã được cải thiện từ bước lặp cuối cùng.
Các bước lặp tiếp tục giảm kích thước của số gia trạng thái thông qua hệ thống cho đến khi đạt tới một kích thước hành lang nhỏ nhất xác định.
Tiêu chuẩn được sử dụng để xác định khi nào kích thước số gia trạng thái cần được giảm là dựa trên sự thay đổi tương đối của giá trị hàm mục tiêu tối
ưu của bước lặp trước, đó là:
k1 / k1
k f f
f (4.2.1) trong đó là mức dung sai xác định. hình 4.2.2 là một sơ đồ khối thể hiện thuật giải chung của thủ tục quy hoạch động sai phân rời rạc.
Mặc dù việc sử dụng quy hoạch động sai phân rời rạc phần nào khắc phục vấn đề liên quan tới lời nguyền của số chiều của quy hoạch động thông thường, nó lại gây ra một số vấn đề cần quan tâm khác liên quan đến việc lựa chọn quỹ đạo ban đầu, việc thay đổi điểm lưới hay không gian trạng thái, và sự hội tụ tới một tối ưu địa phương thay vì một tối ưu toàn cục. Các nhân tố chính ảnh hưởng tới việc thực hiện quy hoạch động sai phân rời rạc gồm có:
1. Số các điểm lưới;
2. Số gia trạng thái ban đầu cùng với số điểm lưới xác định độ rộng hành lang;
3. Quỹ đạo thử nghiệm ban đầu được sử dụng để thiết lập vị trí của các hành lang bên trong không gian trạng thái cho bước lặp đầu tiên;
4. Tốc độ giảm của kích thước số gia trạng thái mà xác định độ rộng hành lang cho các bước lặp khác nhau.
Những nhân tố này đôi khi phụ thuộc lẫn nhau trong việc sử dụng thích hợp và hiệu quả quy hoạch động sai phân rời rạc cho các bài toán tài nguyên nước. Sự lựa chọn quỹ đạo thử nghiệm ban đầu và độ rộng hành lang ban đầu là phụ thuộc lẫn nhau. Ví dụ, nếu một độ rộng hành lang nhỏ được chọn cùng với một quỹ đạo thử nghiệm ban đầu cách xa vùng tối ưu, các bước lặp không cần thiết được đòi hỏi để di chuyển quỹ đạo đó vào trong vùng tối ưu hoặc gần tối ưu. Có thể trong một số trường hợp bài toán quy hoạch động sai phân rời rạc sẽ hội tụ tới một nghiệm khá xa nghiệm tối ưu. Số các điểm lưới và số gia trạng thái ban đầu cùng xác định độ rộng của hành lang ban đầu. Sử dụng một sự kết hợp một số lượng nhỏ các điểm lưới và một số gia trạng thái ban đầu nhỏ cũng có thể dẫn tới những lời giải tối ưu địa phương cách xa nghiệm tối
u.
ảnh hưởng của việc chọn một quỹ đạo ban đầu không tốt có thể được giảm đi nếu một số lượng lớn các điểm lưới và/hoặc các số gia trạng thái ban
đầu lớn được sử dụng. Thực chất, quỹ đạo ban đầu càng tốt thì yêu cầu số các
điểm lưới và các số gia trạng thái ban đầu càng nhỏ, hoặc đơn giản, càng có thể sử dụng độ rộng hành lang ban đầu nhỏ. Số gia trạng thái rất nhỏ với các
điểm lưới nhiều hơn cũng có thể được sử dụng để thiết lập một độ rộng hành lang nhỏ. Điều này có thể dẫn tới sự hội tụ tốt hơn; tuy nhiên, việc tăng số
lượng các điểm lưới làm tăng thời gian tính toán và nhu cầu lưu trữ. Thời gian tính toán có thể được cải thiện bằng việc gia tăng tốc độ giảm của số gia trạng thái tại mỗi bước lặp; tuy nhiên, tốc độ suy giảm của số gia trạng thái quá lớn có thể bỏ qua khu vực tối ưu vì vậy không cung cấp lời giải tối ưu. Việc lựa chọn một số gia trạng thái ban đầu lớn và một tốc độ suy giảm kích thước số gia trạng thái lớn có thể là có lợi. Tuy nhiên, khi số gia trạng thái ban đầu quá
lớn, dẫn tới các độ rộng hành lang lớn, những sự tính toán không cần thiết
được thực hiện ở các khu vực không gian trạng thái cách xa vùng tối ưu.
H×NH 4.2.2
Thuật giải tổng quát cho quy hoạch động sai phân rời rạc