両的計画とは - OR事典 Weblio辞書

Weblio 辞書 > 学問 > OR事典 > 両的計画の意味・解説

OR事典

両的計画

概要

いわゆる動的計画法を2元連立的に考えた逐次最適化法. 単調性「非減少性」に代わって両調性「非減少性または非増加性のいずれか」の下では, 部分最大化問題群と部分最小化問題群の両群を考えて, 両群の相隣る問題間の関係を両帰式としてを導く. これを逐次解いて, 最後に与問題の最適解を求める方法である.負値乗法型, 負値乗加法型などの評価系が両的計画で解ける. 確率系ではマルコフ両決定過程ともいう.

詳説

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

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

さて, 逐次決定過程が次の要素で与えられるとしよう：

$S\,$ は状態空間, $s_{n} \in S\,$ は第 $n\,$ 状態, $A\,$ は決定空間

$A(s_{n})\,$ は $s_{n}\,$ での可能決定空間, $a_{n} \in A(s_{n})\,$ は第 $n\,$ 決定

$r : S \times A \to \mathbf{R}^{1}$ は利得関数, $\beta : S \times A \to (-1,\,1)\,$ は割引き関数

$k : S \to \mathbf{R}^{1}\,$ は終端関数, $T : S \times A \to S\,$ は状態変換

$p = \{p(t|s,a)\}\,$ はマルコフ推移法則, $\sum_{t \in S}p(t|s,a) = 1, p(t|s,a) \ge 0\,$

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

$\begin{array}{lll} {\rm max.~and~min.} & 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 \\ \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}\,$

で表わされる. ただし $r_{n} = r(s_{n},a_{n}),~~\beta_{n}= \beta(s_{n},a_{n})\,$ . このとき, 第 $n\,$ 段の状態 $s_{n}\,$ から始まる部分問題

$\begin{array}{lll} {\rm max.~and~min.} & r_{n} + \beta_{n}r_{n+1} + \beta_{n}\beta_{n+1}r_{n+2} + \cdots \\ & + \beta_{n}\beta_{n+1} \cdots \beta_{N-1}r_{N} + \beta_{n}\beta_{n+1} \cdots \beta_{N}k \\ \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}\,$

の最大値を $U_{n}(s_{n})\,$ , 最小値を $u_{n}(s_{n})\,$ とすると, 両最適値関数は両帰式

$U_{n}(s) = \max_{a:-}T(s,a; u_{n+1}) \vee \max_{a:+}T(s,a; U_{n+1})\,$

$u_{n}(s) = \min_{a:-}T(s,a; U_{n+1}) \wedge \min_{a:+}T(s,a; u_{n+1}) \quad \quad \mbox{(1)}\,$

$U_{N+1}(s) = u_{N+1}(s) = k(s)\,$

を満たす. ここに~ $T(s,a; w) := r(s,a) + \beta(s,a)w(T(s,a)), ~ a:-(+)\,$ は $\beta(s,a) <(\ge)\, 0\,$ なる $a\,$ である.

また, マルコフ推移法則 $p = \{p(t|s,a)\}\,$ 上での期待値最適化問題

$\begin{array}{ll} {\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}\,$

$\mbox{s. t.} \; \; p(\cdot|s_n,a_n) ~ \sim s_{n+1}, ~ a_{n} \in A(s_{n}) \; (n = 1,2, \ldots ), \,$

の両帰式は一次変換

$T(s,a; w) := r(s,a) + \beta(s,a) {\displaystyle \sum_{t \in S}w(t)p(t|s,a)}\,$

を用いて(1)と同じ型で与えられる[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.

「OR事典」の他の用語

動的・確率・多目的計画：

三面鏡理論不変埋没原理両帰式両的計画事前条件付き決定過程事後条件付き決定過程再帰式

索引トップ用語の索引ランキングカテゴリー

>> 「両的計画」を解説文に含む用語の一覧

>> 「両的計画」を含む用語の索引

両的計画のページへのリンク

両的計画のページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

1		井上和子
2		後醍醐天皇
3		クルーゾン症候群
4		TPP
5		被用者
6		捗る
7		美元
8		タカラダニ
9		尾崎紀世彦
10		沓名環希

11		ハクビシン
12		福利厚生
13		赤口
14		未満
15		リツイート
16		ダイバーシティ
17		ご指導ご鞭撻
18		あざとい
19		アセスメント
20		壮行会

21		出不精
22		ジンバック
23		先負
24		言葉
25		井上和子 (女優)
26		整数
27		注意喚起
28		こざとへん
29		尹誠悦
30		レセプション


	Copyright (C) 2012 （社）日本オペレーションズ・リサーチ学会 All rights reserved.

両的計画とは？

OR事典

両的計画

概要

詳説