《多段確率決定樹表(ツリーテーブル)》のソースを表示

'''【ただんかくりつけっていじゅひょう (multistage stochastic decision tree-table)】'''

　[[多段確率決定樹表]] (ツリーテーブル) は, いわゆる決定樹(ディシジョンツリー), 決定表(ディシジョンテーブル)をそれぞれ進化発展させ, 多段階にわたる確率決定過程の問題記述から最適解構成に至るまでを１枚に統合した図表である. 問題のデータを過程の進行状況に応じて配列し, あらゆる可能な経路とその評価値と確率を図示し, 各段における最適決定の選択を明示している. この意味では[[列挙法]]の解構成を与えている. この樹表ではあらゆる型の評価関数の[[期待値最適化 (多段決定過程における)|期待値最適化]], [[確率最適化 (多段決定過程における)|確率最適化]]が解かれる. 樹表には問題に応じて[[繰り返し法 (動的計画法における)|繰り返し法]], [[直接法 (動的計画法における)|直接法]]などいくつかの型がある[1][2][3].

　ここでは3状態2決定2段(3-2-2)モデルで加法型最適化問題：


<center>
<math>\begin{array}{ll}
\mbox{max.} & \mbox{E}[\,r_{0}(u_{0}) 
+ r_{1}(u_{1}) + r_G(x_2) \,]  \\
\mbox{s. t.} &  
p(\,\cdot \,|x_n,u_n) \sim x_{n+1} ~\, (n = 0, 1, u_{0} \in U),
   \ u_{1} \in U, 
\end{array}</math>
</center>


を考える. ただし, 数値は次の通り：


<center>
<math>r_{0}(a_{1}) = 0.7 \quad r_{0}(a_{2}) = 1.0; \quad r_{1}(a_{1}) = 1.0 \quad  r_{1}(a_{2}) = 0.6</math>

<math>r_G(s_{1}) = 0.3 \quad r_G(s_{2}) = 1.0 \quad r_G(s_{3}) = 0.8</math>
</center>


<center>
表1：状態 <math>s_1\, </math> からの２段確率決定樹表

[[スタイル検討#多段確率決定樹表(ツリーテーブル) (0053-a-e-03-1)|スタイル検討]]


表2：状態 <math>s_1\, </math> からの２段確率決定樹表(続き)

[[スタイル検討#多段確率決定樹表(ツリーテーブル) (0053-a-e-03-2)|スタイル検討]]
</center>


:決定樹表(繰り返し法)では, 次のように簡略化している：

::履歴 = <math>x_0~~r_{0}(u_0)\,</math>／<math>u_0~~p_0~~x_1~~r_{1}(u_1)\,</math>／<math>u_1~~p_1~~x_2~~r_G(x_2)\,</math>

::ただし <math>p_0 = p(x_1 | x_0,u_0), ~p_1 = p(x_2 | x_1,u_1)\,</math>

::加法 <math>=\, </math> 評価値の和 <math>= r_{0}(u_0) + r_{1}(u_1) + r_G(x_2)\,</math>

::経路 <math>=\,</math> 経路確率 <math>= p_0 p_1\, </math>

::積 <math>=\, </math> 加法 <math>\times\,</math> 経路, 　　部期 <math>=\, </math>部分期待値, 　　全期 <math>=\, </math> 全期待値.  


この樹表によって <math>s_{1}\, </math> からの(最適原始決定関数を経て)最適一般決定関数


<center>
<math>\sigma_{0}(s_{1}) = a_{2}; \quad \sigma_{1}(s_{1}, s_{1}) =
 a_{2}, \quad \sigma_{1}(s_{1}, s_{2}) = a_{1}, \quad \sigma_{1}(s_{1}, s_{3}) = a_{1},a_{2}</math>
</center>


および最大値 <math>V_{1}(s_{1}) = \mathbf{2.791}</math> が得られる. さらに, <math>s_{2},\,s_{3}</math> からの樹表(省略)と合わせると, [[マルコフ政策]]<math>\pi = \{\pi_{0}, \pi_{1} \}  : \, </math>


<center>
<math>\pi_{0}(s_{1}) = a_{2}, \quad \pi_{0}(s_{2}) = a_{2}, \quad \pi_{0}(s_{3}) = a_{2}</math>

<math>\pi_{1}(s_{1}) = a_{2}, \quad \pi_{1}(s_{2}) = a_{1}, \quad \pi_{1}(s_{3}) = a_{1}</math>
</center>


が最適になっていることがわかる. これは加法型特有の性質である. 一般に, 任意の評価関数に対しては, [[原始政策]], したがって[[一般政策 (逐次決定過程における)|一般政策]]が最適になる. 



----
'''参考文献'''

[1] S. Iwamoto and T. Fujita, "Stochastic Decision-making in a Fuzzy Environment," ''Journal of the Operations Research Society of Japan'', '''38''' (1995), 467-482.

[2] T. Fujita and K. Tsurusaki, "Stochastic Optimization of Multiplicative Functions with Negative Value," ''Journal of the Operations Research Society of Japan'', '''41''' (1998), 351-373.  

[3] S. Iwamoto, K. Tsurusaki and T. Fujita, "Conditional Decision-making in a Fuzzy Environment," ''Journal of the Operations Research Society of Japan'', '''42''' (1999), 198-218.