《両的計画》 - 版の履歴

2007年8月6日 (月) 17:19にKuwashimaによる

2007-08-06T17:19:07Z

Orsjwiki: "《両的計画》" を保護しました。 [edit=sysop:move=sysop]

2007-07-19T13:22:35Z

"《両的計画》" を保護しました。 [edit=sysop:move=sysop]

2007年7月16日 (月) 13:21に220.104.197.230による

2007-07-16T13:21:37Z

2007年7月4日 (水) 07:32にOrsjwikiによる

2007-07-04T07:32:24Z

2007年7月4日 (水) 07:31にOrsjwikiによる

2007-07-04T07:31:43Z

2007年7月4日 (水) 02:24にOrsjwikiによる

2007-07-04T02:24:50Z

Orsjwiki: 新しいページ: ''''【りょうてきけいかく (bynamic programming)】''' 　動的計画法は単調性 monotonicity と再帰性 recursiveness (可分性 separability) の下で適用...'

2007-07-03T08:13:03Z

新しいページ: ''''【りょうてきけいかく (bynamic programming)】''' 　動的計画法は単調性 monotonicity と再帰性 recursiveness (可分性 separability) の下で適用...'

新規ページ

'''【りょうてきけいかく (bynamic programming)】'''

　動的計画法は単調性 monotonicity と再帰性 recursiveness (可分性 separability) の下で適用される. この単調性は目的関数の「非減少性」を意味しているが, これを両調性bitonicity「非減少性または非増加性のいずれか」まで拡大解釈すると, より広い逐次決定過程が考えられる. これを[[両的計画]]と呼ぶ. 特に, 確率システム上では[[マルコフ両決定過程]][3]という. これは確率的動的計画法を単にマルコフ決定過程ということに準じている.

　両的計画法によって最大化問題を解く場合, 与問題に対する部分最大化問題群ばかりでなく部分最小化問題群をも考える必要がある. このとき, 最大値関数と最小値関数の間に成り立つ連立再帰式を[[両帰式(動的計画法における)]] という. [[負値乗法型評価系]][1], [[負値乗加法型評価系]] [2] の最適化問題や[[最短最長ルート問題]]などは両帰式で解ける.

　さて, 逐次決定過程が次の要素で与えられるとしよう：
　
　
\begin{eqnarray}
& & S~ \mbox{は状態空間},~~s_{n} \in S~ \mbox{は第}n\mbox{状態},~~A~
\mbox{は決定空間} \nonumber \\
& & A(s_{n})~ \mbox{は}s_{n}\mbox{での可能決定空間},~~a_{n} \in A(s_{n})
\mbox{は第}n\mbox{決定} \nonumber \\
& & r : S \times A \to \mbox{\bf R}^{1}~\mbox{は利得関数},~~\beta : S \times A \to
(-1,\,1)~\mbox{は割引き関数} \nonumber \\
& & k : S \to \mbox{\bf R}^{1}~\mbox{は終端関数},~~ T : S \times A \to
S~\mbox{は状態変換} \nonumber \\
& & p = \{p(t|s,a)\}~\mbox{はマルコフ推移法則},~~\sum_{t \in S}p(t|s,a) = 1,
~p(t|s,a) \ge 0 \nonumber
\end{eqnarray}

このとき, 確定系上の負値乗加法評価系の最大化または最小化は

\begin{eqnarray}
& & {\rm max.~and~min.} \hspace{2mm} r_{1} + \beta_{1}r_{2} +
\beta_{1}\beta_{2}r_{3} + \cdots \nonumber \\[-2.10mm]
& & \hspace*{30mm} + \beta_{1}\beta_{2} \cdots \beta_{N-1}r_{N} +
\beta_{1}\beta_{2} \cdots \beta_{N}k \nonumber \\
& & \mbox{s. t.} \hspace{2mm}
T(s_n,a_n) = s_{n+1}, ~ a_{n} \in A(s_{n}) \hspace{4mm} (n = 1, 2, \ldots, N),
\nonumber
\end{eqnarray}

で表わされる. ただし ~$ r_{n} = r(s_{n},a_{n}),~~\beta_{n} =
\beta(s_{n},a_{n}).$
このとき, 第$n$段の状態 $ s_{n} $ から始まる部分問題
\begin{eqnarray}
& & {\rm max.~and~min.} \hspace{2mm} r_{n} + \beta_{n}r_{n+1} +
\beta_{n}\beta_{n+1}r_{n+2} + \cdots \nonumber \\[-2.10mm]
& & \hspace*{28mm} + \beta_{n}\beta_{n+1} \cdots \beta_{N-1}r_{N} +
\beta_{n}\beta_{n+1} \cdots \beta_{N}k \nonumber \\
& & \mbox{s. t.} \hspace{2mm}
T(s_m,a_m) = s_{m+1}, ~ a_{m} \in A(s_{m}) \hspace{4mm} (m = n, n+1, \ldots, N ), \nonumber
\end{eqnarray}
の最大値を $ U_{n}(s_{n}) $, 最小値を $ u_{n}(s_{n}) $
とすると, 両最適値関数は両帰式
\begin{eqnarray}
&& U_{n}(s) = \mathop{{\rm max}}_{a:-}T(s,a; u_{n+1}) \vee \mathop{{\rm
max}}_{a:+}T(s,a; U_{n+1}) \nonumber \\
&& u_{n}(s) = \mathop{{\rm min}}_{a:-}T(s,a; U_{n+1}) \wedge \mathop{{\rm
min}}_{a:+}T(s,a; u_{n+1}) \label{eqn:A-E-02+dbe00} \\
&& U_{N+1}(s) = u_{N+1}(s) = k(s) \nonumber
\end{eqnarray}
を満たす. ここに~ $ T(s,a; w) := r(s,a) + \beta(s,a)w(T(s,a)), $~ $a:-(+)$
は $ \beta(s,a) <(\ge)\, 0 $ なる $a$ である. \par
%
%
また, マルコフ推移法則 $ p = \{p(t|s,a)\} $ 上での期待値最適化問題

\begin{eqnarray}
& & {\rm max.~and~min.} \hspace{2mm} E[\,r_{1} + \beta_{1}r_{2} +
\beta_{1}\beta_{2}r_{3} + \cdots \nonumber \\[-2.10mm]
& & \hspace*{42mm} + \beta_{1}\beta_{2} \cdots \beta_{N-1}r_{N} +
\beta_{1}\beta_{2} \cdots \beta_{N}k\,] \nonumber \\
& & \mbox{s. t.} \hspace{2mm}
p(\cdot|s_n,a_n) \sim s_{n+1}, ~ a_{n} \in A(s_{n}) \hspace{4mm}
(n = 1,2, \ldots ), \nonumber
\end{eqnarray}

の両帰式は一次変換
$$
T(s,a; w) := r(s,a) + \beta(s,a) {\displaystyle \sum_{t \in S}w(t)p(t|s,a)}
$$
を用いて(\ref{eqn:A-E-02+dbe00})と同じ型で与えられる[4].

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

[1] R. Bellman, ''Dynamic Programming'', Princeton Univ. Press, 1957.

[2] S. Iwamoto, "From Dynamic Programming to Bynamic programming," ''Journal of Mathematical Analysis and Applications'', '''177''' (1993), 56-74.

[3] S. Iwamoto, "On Bidecision Processes," ''Journal of Mathematical Analysis and Applications'', '''187''' (1994), 676-699.

[4] 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.

← 古い版		2007年8月6日 (月) 17:19時点における版
109行目:		109行目:

	[4] 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.		[4] 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.
		+
		+
		+	[[Category:動的・確率・多目的計画\|りょうてきけいかく]]

@@ 23行目: / 23行目: @@
-:<math>\begin{array}{lll}
+<center>
 {\rm max.~and~min.} & r_{1} + \beta_{1}r_{2} +
   \beta_{1}\beta_{2}r_{3} + \cdots   \\
@@ 30行目: / 31行目: @@
 \mbox{s. t.} \; T(s_n,a_n) = &  s_{n+1}, ~ a_{n} \in A(s_{n}) \quad (n = 1, 2, \ldots, N),
 \end{array}\, </math>
@@ 35行目: / 37行目: @@
-:<math>\begin{array}{lll}
+<center>
 {\rm max.~and~min.} & r_{n} + \beta_{n}r_{n+1} +
   \beta_{n}\beta_{n+1}r_{n+2} + \cdots   \\
@@ 42行目: / 45行目: @@
 \mbox{s. t.} \; T(s_m,a_m) = & s_{m+1}, ~ a_{m} \in A(s_{m}) \quad (m = n, n+1, \ldots, N ),
 \end{array}\, </math>
@@ 47行目: / 51行目: @@
-:<math>U_{n}(s) = \max_{a:-}T(s,a; u_{n+1}) \vee \max_{a:+}T(s,a; U_{n+1})\, </math>
+<table align="center">
+<tr>
-:<math>u_{n}(s) = \min_{a:-}T(s,a; U_{n+1}) \wedge \min_{a:+}T(s,a; u_{n+1})
+<td>
 \quad  \quad  \mbox{(1)}\, </math>
+</td>
-:<math>U_{N+1}(s) = u_{N+1}(s) = k(s)\, </math>
+</tr>
@@ 60行目: / 73行目: @@
-:<math>\begin{array}{ll}
+<table align="center">
 {\rm max.~and~min.} & E[\,r_{1} + \beta_{1}r_{2} +
   \beta_{1}\beta_{2}r_{3} + \cdots   \\
 & + \beta_{1}\beta_{2} \cdots \beta_{N-1}r_{N} +
   \beta_{1}\beta_{2} \cdots \beta_{N}k\,]
-\end{array}\, </math>
+\end{array}\, </math></td>
+</tr>
-:<math>\mbox{s. t.} \; p(\cdot|s_n,a_n) ~ \sim s_{n+1}, ~ a_{n} \in A(s_{n}) \;
+<tr>
    (n = 1,2, \ldots ), \, </math>
 の両帰式は一次変換
-:<math>T(s,a; w) := r(s,a) + \beta(s,a) {\displaystyle \sum_{t \in S}w(t)p(t|s,a)}\, </math>
+<center>
 を用いて(1)と同じ型で与えられる[4].

@@ 3行目: / 3行目: @@
 　動的計画法は単調性 monotonicity と再帰性 recursiveness (可分性 separability) の下で適用される. この単調性は目的関数の「非減少性」を意味しているが, これを両調性 bitonicity「非減少性または非増加性のいずれか」まで拡大解釈すると, より広い逐次決定過程が考えられる. これを[[両的計画]]と呼ぶ. 特に, 確率システム上では[[マルコフ両決定過程]][3]という. これは確率的動的計画法を単にマルコフ決定過程ということに準じている.
-　両的計画法によって最大化問題を解く場合, 与問題に対する部分最大化問題群ばかりでなく部分最小化問題群をも考える必要がある. このとき, 最大値関数と最小値関数の間に成り立つ連立再帰式を[[両帰式 (動的計画法における)|両帰式]] という. [[負値乗法型評価系]][1], [[負値乗加法型評価系]] [2] の最適化問題や[[最短最長ルート問題]]などは両帰式で解ける.
+　両的計画法によって最大化問題を解く場合, 与問題に対する部分最大化問題群ばかりでなく部分最小化問題群をも考える必要がある. このとき, 最大値関数と最小値関数の間に成り立つ連立再帰式を[[両帰式 (動的計画法における)|両帰式]]という. [[負値乗法型評価系]][1], [[負値乗加法型評価系]] [2] の最適化問題や[[最短最長ルート問題]]などは両帰式で解ける.
 　さて, 逐次決定過程が次の要素で与えられるとしよう：

@@ 3行目: / 3行目: @@
 　動的計画法は単調性 monotonicity と再帰性 recursiveness (可分性 separability) の下で適用される. この単調性は目的関数の「非減少性」を意味しているが, これを両調性 bitonicity「非減少性または非増加性のいずれか」まで拡大解釈すると, より広い逐次決定過程が考えられる. これを[[両的計画]]と呼ぶ. 特に, 確率システム上では[[マルコフ両決定過程]][3]という. これは確率的動的計画法を単にマルコフ決定過程ということに準じている.
-　両的計画法によって最大化問題を解く場合, 与問題に対する部分最大化問題群ばかりでなく部分最小化問題群をも考える必要がある. このとき, 最大値関数と最小値関数の間に成り立つ連立再帰式を[[両帰式(動的計画法における)]] という. [[負値乗法型評価系]][1], [[負値乗加法型評価系]] [2] の最適化問題や[[最短最長ルート問題]]などは両帰式で解ける.
+　両的計画法によって最大化問題を解く場合, 与問題に対する部分最大化問題群ばかりでなく部分最小化問題群をも考える必要がある. このとき, 最大値関数と最小値関数の間に成り立つ連立再帰式を[[両帰式 (動的計画法における)|両帰式]] という. [[負値乗法型評価系]][1], [[負値乗加法型評価系]] [2] の最適化問題や[[最短最長ルート問題]]などは両帰式で解ける.
 　さて, 逐次決定過程が次の要素で与えられるとしよう：

← 古い版	2007年7月19日 (木) 13:22時点における版
(相違点なし)

@@ 1行目: / 1行目: @@
 '''【りょうてきけいかく (bynamic programming)】'''
-　動的計画法は単調性 monotonicity と再帰性 recursiveness (可分性 separability) の下で適用される. この単調性は目的関数の「非減少性」を意味しているが, これを両調性bitonicity「非減少性または非増加性のいずれか」まで拡大解釈すると, より広い逐次決定過程が考えられる. これを[[両的計画]]と呼ぶ. 特に, 確率システム上では[[マルコフ両決定過程]][3]という. これは確率的動的計画法を単にマルコフ決定過程ということに準じている.
+　動的計画法は単調性 monotonicity と再帰性 recursiveness (可分性 separability) の下で適用される. この単調性は目的関数の「非減少性」を意味しているが, これを両調性 bitonicity「非減少性または非増加性のいずれか」まで拡大解釈すると, より広い逐次決定過程が考えられる. これを[[両的計画]]と呼ぶ. 特に, 確率システム上では[[マルコフ両決定過程]][3]という. これは確率的動的計画法を単にマルコフ決定過程ということに準じている.
 　両的計画法によって最大化問題を解く場合, 与問題に対する部分最大化問題群ばかりでなく部分最小化問題群をも考える必要がある. このとき, 最大値関数と最小値関数の間に成り立つ連立再帰式を[[両帰式(動的計画法における)]] という. [[負値乗法型評価系]][1], [[負値乗加法型評価系]] [2] の最適化問題や[[最短最長ルート問題]]などは両帰式で解ける.
 　さて, 逐次決定過程が次の要素で与えられるとしよう：
-\begin{eqnarray}
+:<math>S\, </math> は状態空間, <math>s_{n} \in S\, </math> は第<math>n\, </math>状態, <math>A\, </math>は決定空間
-& & S~ \mbox{は状態空間},~~s_{n} \in S~ \mbox{は第}n\mbox{状態},~~A~
- \mbox{は決定空間}  \nonumber   \\
+:<math>A(s_{n})\, </math>は<math>s_{n}\, </math>での可能決定空間, <math>a_{n} \in A(s_{n})\, </math>は第<math>n\, </math>決定
-& & A(s_{n})~ \mbox{は}s_{n}\mbox{での可能決定空間},~~a_{n} \in A(s_{n})
- \mbox{は第}n\mbox{決定}  \nonumber \\
+:<math>r : S \times A \to \mathbf{R}^{1}</math>は利得関数, <math>\beta : S \times A \to (-1,\,1)\, </math>は割引き関数
-& & r : S \times A \to \mbox{\bf R}^{1}~\mbox{は利得関数},~~\beta : S \times A \to
- (-1,\,1)~\mbox{は割引き関数} \nonumber \\
+:<math>k : S \to \mathbf{R}^{1}\, </math>は終端関数, <math>T : S \times A \to S\, </math>は状態変換
-& & k : S \to \mbox{\bf R}^{1}~\mbox{は終端関数},~~ T : S \times A \to
- S~\mbox{は状態変換}    \nonumber \\
+:<math>p = \{p(t|s,a)\}\, </math>はマルコフ推移法則, <math>\sum_{t \in S}p(t|s,a) = 1, p(t|s,a) \ge 0\, </math>
@@ 25行目: / 23行目: @@
-\begin{eqnarray}
+:<math>\begin{array}{lll}
-& & {\rm max.~and~min.} \hspace{2mm} r_{1} + \beta_{1}r_{2} +
+{\rm max.~and~min.} & r_{1} + \beta_{1}r_{2} +
-  \beta_{1}\beta_{2}r_{3} + \cdots   \nonumber   \\[-2.10mm]
+  \beta_{1}\beta_{2}r_{3} + \cdots   \\
-& & \hspace*{30mm} + \beta_{1}\beta_{2} \cdots \beta_{N-1}r_{N} +
+& + \beta_{1}\beta_{2} \cdots \beta_{N-1}r_{N} +
-  \beta_{1}\beta_{2} \cdots \beta_{N}k   \nonumber \\
+  \beta_{1}\beta_{2} \cdots \beta_{N}k \\
-& & \mbox{s. t.} \hspace{2mm}
+\mbox{s. t.} \; T(s_n,a_n) = &  s_{n+1}, ~ a_{n} \in A(s_{n}) \quad (n = 1, 2, \ldots, N),
-T(s_n,a_n) = s_{n+1}, ~ a_{n} \in A(s_{n}) \hspace{4mm} (n = 1, 2, \ldots, N),
+\end{array}\, </math>
- \nonumber
-\begin{eqnarray}
-& & {\rm max.~and~min.} \hspace{2mm} E[\,r_{1} + \beta_{1}r_{2} +
+の最大値を <math>U_{n}(s_{n})\, </math>, 最小値を <math>u_{n}(s_{n})\, </math> とすると, 両最適値関数は両帰式
-  \beta_{1}\beta_{2}r_{3} + \cdots   \nonumber   \\[-2.10mm]
-& & \hspace*{42mm} + \beta_{1}\beta_{2} \cdots \beta_{N-1}r_{N} +
-  \beta_{1}\beta_{2} \cdots \beta_{N}k\,]   \nonumber \\
+:<math>U_{n}(s) = \max_{a:-}T(s,a; u_{n+1}) \vee \max_{a:+}T(s,a; U_{n+1})\, </math>
-& & \mbox{s. t.} \hspace{2mm}
-p(\cdot|s_n,a_n) \sim s_{n+1}, ~ a_{n} \in A(s_{n}) \hspace{4mm}
+:<math>u_{n}(s) = \min_{a:-}T(s,a; U_{n+1}) \wedge \min_{a:+}T(s,a; u_{n+1})
-   (n = 1,2, \ldots ),  \nonumber
+\quad  \quad  \mbox{(1)}\, </math>
-\end{eqnarray}
 の両帰式は一次変換
-$$
-T(s,a; w) := r(s,a) + \beta(s,a) {\displaystyle \sum_{t \in S}w(t)p(t|s,a)}
+:<math>T(s,a; w) := r(s,a) + \beta(s,a) {\displaystyle \sum_{t \in S}w(t)p(t|s,a)}\, </math>
-$$
-を用いて(\ref{eqn:A-E-02+dbe00})と同じ型で与えられる[4].
+を用いて(1)と同じ型で与えられる[4].