動的計画法

ここでは、動的計画法とはなにかを整理します。以下の引用では、入力時間の節約のために送り仮名の間違いや句読点の誤りを放置している箇所がありますがご了承ください。以下、””の間の引用は、岩波数学辞典第四版の「動的計画法」からの引用です。

最適化問題のなかには、その過程がいくつもの段階から構成される多段決定問題と見なせる問題が数多く存在する。

動的計画法は、多段決定問題を体系的にとりあつかず研究分野であり、1950年以降にR.Bellmanが発展させた理論手法である。動的計画法は、離散最適化問題や組合せ問題に対しても、アルゴリズム設計のパラダイムとしてしばしば使われる。

岩波数学辞典第4版

ここで重要なのは、動的計画法とはアルゴリズム設計の「パラダイム」であって、特定の計算手順ではない、ということです。したがって、「この問題は動的計画法を使って時刻の早いほうから順番に答えが決まっていきます」、というコメントは、その指している内容があいまいです。具体的なことは何も言ってないことになります。

引用つづき

多段決定問題(multi-stage decision problem)とは与えられた多段決定過程に付随する目的関数を最適(最小または最大)にするように決定の列(各段階における決定変数の値を並べたもの)を求める問題である。与えられた多段決定問題に対し、可能な決定の列を政策(policy)といい、目的関数を最適にする政策を最適政策(optimal policy)という。

岩波数学辞典第4版

policyは、方策とも訳されます。また、多段とは、空間的、時間的の両方の場合があることに注意が要ります。

次が動的計画法の定義です。

動的計画法とは、n段階決定過程をn個の1段階決定過程の列に直すことにより、多段決定問題を系統立てて逐次的に解く方法である。

R.Bellmanにより延べられた最適性の原理(Principle of optimality)は、動的計画法により最適化問題の解を求める場合に基本となる原理であり、’最適政策は最初の状態と最初の決定が何であっても、残りの決定は最初の決定から生じた状態に関して最適方策を構成しなければならない’というものである。すなわちn段階の多段決定問題を考えた時、第一段階における決定をどのように選択しても、最適解を求めるためには、残りの(n-1)段階において最適政策を用いなければならない。そうしたうえで、第一段階での決定を変化させることによってn段階に対する最適政策を決定することができる。

岩波数学辞典第4版

教科書で動的計画法が説明される場合は、数式が使われる場合が多いのですが、日本語だけで明快に定義されていることに感銘を受けます。基本的な数学のトレーニングを受けた読者にはわかりやすいですが、数学のトレーニングを受けたことのない人々は、最初の1文で挫折することは、経験的に感じています。理科のトレーニングを受けたことのない人々に動的計画法を説明するにはどうしたらいいのでしょうか?私は明快な答えをもっていません。

引用続き

多段決定問題を動的計画法による解く手順は、大きく分けて次のステップからなる。

1)相互に関連を持つ一群の問題からなり、解くべき問題を含むような適切な問題群を考える

2)最適性の原理の基づき、問題群に含まれる各問題の間の関係を、最適性方程式と呼ばれる再帰式に表現する。

3)最適性方程式を解いて最適政策を求める

岩波数学辞典第4版

ここから、具体例があります

確定的な多段決定問題の例として、n期間にわたる生産計画を考える。目的は総利益を最大化することである。各期において起こりうる状態の集合を

X、可能な政策の集合をUとする。これらの集合は各期に共通であると仮定する。第一期における初期状態をx_1 ¥in Xとし、第i期の状態をx_i ¥in Xであらわす。また第i期で決定する政策をu_i ¥in Uとあらわす。第i期に得られる利益をr(x_i,u_i)とし、次の第(i+1)期における状態をx_{i+1} = g(x_i,u_i)とする。

 この問題を解くために、第m期に状態xから出発して、第n期までのn-m+1期間にわたって最適政策を施すことにより得られる総利益をf_m(x)とおく。すべての期mと状態xに対して最大利益f_m(x)を考えることは、元の問題を関連する問題群に埋め込むことになる。最大利益f_m(x)はm=nの場合,

により与えられ、1<=m<=n-1の場合は、

となる。これが最適性方程式であり、式(1),(2)を再帰的に解くことにより、f_n(x), f_{n-1}(x),,,,,f_1(x)をすべての状態x ¥in Xについて計算し、その結果を元に最適政策u_1,u_2,,,u_nを順に求めることができる。

岩波数学辞典第4版

最初の式を(1)、2番目の式を(2)とよぶことにします.

1<=m<=n-1の場合をもうすこし観察します。左辺は、m期における最大利益は、そのときの状態x_mによってきまる、といっています。左辺は、{}内を最大化するようにu_mを決めなくては、値が決まりません。

いいかえると, m期の状態がきまると右辺の{}内を最大化するようなu_m が決まらなければ、最適方策はきまらないことになります。確定的な場合はすべての状態を尽くせば、右辺を最大化するようなu_mはきまります。

ここで、n=8の場合に、m=5期の方策を決める例を表にしてみます. ここで,第i期の状態x_iは、x^1,x^2,x^3,x^4のいずれかの状態をとるとします。これは期によらないとします。

さらに、第i期にx^kという状態をとることを、x_i^kで表します。たとえば、第6期に状態x^1をとるときの総利益は、f_6(x_6^1)とあらわすことにします.

各期にとる政策の集合Uは、3つの政策u^1,u^2,u^3からなるとします。これも期によらないとします.さらに、第i期に政策pをとることを、u_i^pで表します。たとえば、第6期に政策u^2をとることは、u_6^2

とあらわします。

まず、第8期でx_8が各状態をとったときの総利益 をそれぞれ計算します. つぎに、第7期の各状態の総利益 を、(2)によって計算します。 あるkについて、f_7(x_7^k)を計算するには,政策u^1,u^2,u^3をとった場合の3つの値

を計算します。 第二項の引数g(x_7^k,u_7^k)は、x^1,x^2,x^3,x^4のいずれの値をとります。どの値をとるかは関数gによって完全に決められています。ですので、 第二項の値は、先程第8期について計算した, のいずれかの値になるわけです。なので、この3つの値は、それぞれ足し算を一回するだけで求まります. 3つの値のうち最大のものを探します。それがたとえば上のうちの2番目だったとすると、第7期に状態x_7^kにいたときにとるべき政策はu^2であるということがわかります。

4とおりの状態について、上の3つの値を計算するわけですので、3x4=12とおりの数値を計算して比較し、その結果の4通りの最適政策およびそのときの総利益f_7(x_7^k)を記録しておきます。これを、第5期まで、くりかえします。いま、第5期の状態がx^1だったとします。このときにとるべき最適な政策は、f_5(x_5^1)を最大にするu_5としてすでにわかっていますので、その政策をとります。状態x_5から政策u_5をとった場合の第6期の状態が決まります。これを仮にx^2、すなわちx_6^2だとします。状態x_6^2のときの最適な政策も、f_6(x_6^2)を最大にするu_6としてすでに表に記録されています。これをくりかえすと、第5期から第7期までとるべき方策の列が決まります。これが第m期から第n期までの方策の決めかたです。

いま、状態が4とおり、すなわちx_tは、x^1,x^2,x^3,x^4のいずれかの値をとるとしました。これが1000とおりだとするとどこの計算がかわるでしょうか? 第8期での各状態での総利益を1000とおり計算する必要があります。つぎに、第7期の各状態の総利益を(2)によって計算するときに、1000とおりのkについて、政策u^1,u^2,u^3の3つの値を計算する必要があります。つまり、1000x3=3000とおりの値を計算する必要があります。1000とおりの状態について、そのときの総利益と最適な方策を覚えておく必要があります。

確定的動的計画の例としては、0-1ナップサック問題も挙げられます。 わかりやすい例は、久保、松井著「組合せ最適化[短編集]」朝倉書店の5章:ナップサック問題に、""クマさんの盗み方問題""にあります。

0-1 ナップサック問題
n個のアイテムからなる有限集合N、各々のi \in Nの重量 と価値 および ナップサックの重量の上限bが与えられたとき、アイテムの重量の合計がbを超えないようなアイテムの詰め合わせの中で、価値の合計が最大のものを求める問題

久保、田村、松井編「応用数理計画ハンドブック」朝倉書店

さらに引用
0-1ナップサック問題は、アイテムi \in をナップサックにつめるとき1、それ以外のとき0になる0-1変数x_iを使うと、以下の0ー1整数計画問題として定式化できる.

ここで、以下の部分問題を導入する.

久保、田村、松井編「応用数理計画ハンドブック」朝倉書店

あとで導入した問題では、和がi \in Nからi=1,...,kに変っていて、最初の条件式の右辺bが\thetaにかわっています。Nがアイテムの集合をあらわしていることに注意すると、 和のとりかたをi \in Nからi=1,\ldots,kに変えるということは、ナップサックにいれるものを1,\ldots,kのものに限定する、ということに対応します。 さらに、最初の条件式の右辺をbから\thetaに変更したということは、入れるアイテムの合計を\thetaにする、ということを表しています. この表記を用いると、もとの問題の最適値はJ(n,b)です.

もとの問題の最適部分問題間の関係より、J(k,\theta)は、以下の再帰方程式によって計算可能である。

久保、田村、松井編「応用数理計画ハンドブック」朝倉書店

  期(時刻)をTから0に向けて後退させることによって再帰方程式を解く動的計画アルゴリズムを特に 後退型動的計画アルゴリズムとよびます。一方で、同じ動的計画アルゴリズムでも、期(時刻)を0から始めてT に向けて前進させるタイプのアルゴリズムも考えられます。 このような動的計画アルゴリズムを特に前進型動的計画アルゴリズムとよびます.

ランダムな要素をふくむ多段決定問題

ここまでは、確定的な多段決定問題を考えました。「確定的」とは、第i期に状態x_iであるとき、政策u_iをとれば、ランダムな要素はなしに第i+1期には必ず状態g(x_i,u_i)に推移する、ということです。 では、ここに不確定な要素を入れようとするとどうなるでしょうか?

状態x_iにいるときに政策u_iをとったとき、ランダムな要素w_tが関与して、第i+1期には状態x_{i+1}に推移する、というモデル化を行います。上で扱った「確定的」な問題では、第i+1期の状態x_{i+1}は、

と書けましたが、 今度はランダムな要素w_tが関与しますので、

と表されます。w_tは、x_tとu_tによって定まる確率密度P_t(\cdot | x_t, u_t)によって特徴付けられます.

このモデル化を採用すると、動的計画問題の目的は、総利益の期待値を最適化することになります。1<=m<=n-1の場合の再帰方程式は、以下のとおりです

確定的な問題に対する方程式との違いは、()の中にw_tが入っていることと、期待値を最大化することです。

不確定な多段決定問題に対する動的計画の例として、最適停止問題と多期間確率的在庫計画問題が、久保、田村、松井編「応用数理計画ハンドブック」の第七章に掲載されています.

動的計画法が有効な最適化問題のひとつに 最短路問題 があります。 Powell著の"Approximate Dynamic Programming"にならって、以下の表記を用います.

v_j = ノードjからノードrへの最小コスト
グラフ上のあるノードjをとりだしても、そのv_jの値はわかりません。しかし、v_r=0であることはわかります. 反復nにおけるv_jの評価値をv_j^nとあらわします。以下に示すアルゴリズムにより、v_jの値を得ることができます. ただし、は、(i,j)となる枝が存在するノードjの集合を, Iはノードの集合を表しています.

  1. 以下のとおりに設定する。ただし、Mは大きな正の値とする.

    n=1とする。
  2. すべてのi \in Iについて、以下を計算する.
  3. すべてのiについて、v_i^n < v_i^{n-1}がなりたつならば、nをn+1にしてステップ1にもどる.そうでなければ終了

W.B.Powell, "Approximate Dynamic Programming"から和訳

これは効率のよくないアルゴリズムですが、最短路問題を解くための動的計画法の原理を簡潔に表しています。より効率のよいアルゴリズムは多数考案されています。

この最短路問題に不確定な要素をいれるとどうなるでしょうか? 最短路問題において、2点間の移動コストがランダムである、というモデル化をします。 枝のコストが実際にどうなるかを知らずに最短路をもとめる、という設定では、 上のアルゴリズムにおけるステップ2の更新式が

となります。ここで、Wはネットワークのなんらかの情報によってきまるランダム変数です.このモデル化を用いる場合は、 c_{ij}=E{ c_{ij}(W) }と、2点間のコストをその期待値に設定することによって、上のアルゴリズムと同じステップで解くことができます. 文献W.B.Powell "Approximate Dynamic Programming"では、ノードiに到着した時点で、(i,j)のコストが判明する、という設定でのモデル化も述べられています。 この場合、更新式は,

となります。この場合は、期待値をとるのが最小化の外に出ています。 "最小化という意思決定"の期待値をとる、ということになります。 つまり、意思決定自体がランダムであることを表しています。
運航・物流系トップページへ
海上技術安全研究所トップページへ