《静止目標物の最適探索》のソースを表示

'''【せいしもくひょうぶつのさいてきたんさく (optimal search for a stationary target)】'''

探索活動において重要な役割をはたすのは，探索活動の場としての[[探索空間]](search space)，探索活動の主体である[[探索者]](searcher)，探索の対象である[[目標物]](target)，探索のために利用可能な人・物・時間・費用などの[[探索努力]](searching effort)，それに探索活動の評価尺度としての[[探索基準]](search criterion) である．これら
がどのように設定されるかによって，さまざまな探索モデルが考えられる．本項では存在位置が不変である静止目標物(stationary target) を対象として，探索努力をいつ，どこへ，どれだけ配分すべきかを考える．この探索努力の配分方法を[[探索政策]](search policy) という．用いられる数学的手法としては，探索空間が連続空間なら目的関数が汎関数となり変分法が用いられ，離散空間なら多変数最適化問題となり数理計画法，それも一段階探索なら非線形計画法，多段階探索なら動的計画法が多く用いられる．探索努力の離散性を重視するなら，整数計画問題となり分枝限定法などが用いられる．

基本的な探索努力配分問題は，以下のような発見確率最大化問題(これを[探知探索])(detection search) という) である．静止目標物が一個，探索空間(ユークリッド空間) <math>X\,</math>内の一点に存在する．探索者は事前知識として，目標物は<math>X\,</math> 上の密度関数<math>p(x)\,</math>に従って選ばれた一点に存在していると思っている．目標物が点<math>x (\in X)\,</math>に存在するとき，そこに探索努力<math>z\,</math> を投入して発見する条件付確率<math>b(x,z)\,</math>が与えられており，これを[[探知関数]](detection function) という．問題は任意分割可能な探索努力量<math>E\,</math>を投入して，目標物を発見する確率を最大にするには，各点にいくらの探索努力を投入すべきか，というものである．探索政策は努力配分密度<math>\phi= \left\{ \phi(x) \mid x \in X \right\} \,</math> で表され，問題は制約条件

<center>
<math>
\int_{X}\phi(x)\; \mbox{d}x = E, \ \ \  \phi \ge 0, \ \ \    x \in X
\,
</math>
</center>
	
のもとで，発見確率<math>P\left[ \phi \right] = \int_{X}p(x)b \left[ x, \phi(x) \right]dx \,</math> を最大にする関数 <math>\phi \,</math>を求めよ，という変分問題になる．このモデルは最初Koopman[7] が[[指数型探知関数]](exponential detection function) の場合を解いたので，[[クープマン問題]] (Koopman problem)とも呼ばれている．de Guenin[3] によれば，がある緩かな正則条件を満たすとき，探索政策<math>\phi^{*}\,</math> が最適であるための必要十分条件は，正定数<math>\lambda\,</math> が存在して


<center>
<math>
p(x) b'[x,\phi^*(x)] \left\{ {= \atop \leq} \right\} \lambda~~~~if ~~ \phi^*(x) \left\{ {> \atop =} \right\} 0 
\,
</math>
</center>
が成立することである．ここに<math>b^{'} \left[x,z \right] \,</math> は<math>z \,</math> に関する偏微分である．これは統計学におけるNeyman-Pearson lemma 型の条件式で，最適政策<math>\phi^{*}\,</math> は投入前の限界発見率(marginal detection rate)<math>p(x)b^{'} \left[x, \phi^{*}(x) \right] \,</math> がある水準<math>\lambda\,</math> (<math>\lambda\,</math> は制約条件を満たすように決定される) 以上の場所に努力を投入すべきであり，その投入量は投入後の限界発見率] が水準 にそろうように決定されるべきである，ことを示している．これから解析解が具体的に求められる．さらに[[最適努力配分の加法性]] (the additively of optimal effort allocation)，すなわち「探索努力<math>E\,</math> を任意に<math>E_1 + E_2\,</math> に分割したとき，<math>E\,</math> の最適配分は <math>E_1\,</math>の最適配分と <math>E_2\,</math>の最適配分で発見できなかったとの条件のもとでの<math>E_2\,</math> の最適配分との和である」が示され，最適逐次投入と最適一括投入は同じ結果になることが分る．任意努力量に対して発見確率を最大にする政策を[[一様最適探索政策]](uniformly optimal search policy)というが，これは目標物発見までに要する[[期待努力量の最小化]](minimization of the expected effort) に対しても最適であることが，Dobbie[4] によって示されている．
探索空間が有限個の小領域から成り，各小領域を一回探索するために必要な努力量が決っている場合を考えると，探知探索では基本的にde Guenin のルールが成立する．一方発見までの期待努力量最小化問題は動的計画法で定式化され，各回で目標物の存在分布を改訂した上で，単位努力量当りの発見確率を最大にする小領域を探索するような最適政策の存在が知られている．

探索基準としては，発見確率最大化，期待努力量最小化以外にも，たとえば投入費用から発見時の利得を差し引いた[[期待リスクの最小化]](minimization of the expected risk)，探索終了後に目標物の所在を正しく言い当てる確率を最大化する[[所在探索]](whereabouts search)，目標物の位置に関して得られる期待情報量を最大化する[[情報探索]] (information search) などが知られている．所在探索については，最後に所在地として指示する小領域は探索せず，他の小領域を探知探索における最適政策に従って探索するのが最適であることが，Kadane[6] によって示されている．また指数型探知関数の場合，探知探索の最適政策が目標物の事後存在分布のエントロピーを最大にすること，逆にこのような性質を持つ探知関数は指数型に限ることが，Barker[1] によって示されている．

以上概観したように，静止目標物探索に関する基本的なモデルはほぼ解析されているが，探索活動の特殊性を考慮すると，さまざまなモデルが考えられる．
主なものを列挙してみよう．


(1) 考えている探索空間に目標物が存在しない可能性があるとか，発見時の利得が探索費用より小さい場合には，[[探索の最適停止]](optimal stop of search)が必要となる．前者についてはChew[2] が，後者についてはRoss[8] が，離散モデルにおけるこの種の問題を動的計画問題に定式化し，いくつかの重要な結果を得ている．

(2) 遭難者探索のように，[[寿命のある目標物]](target with lifetime) に対する探索では，目標物が長く生存できない場所は，たとえ探索効率が多少悪くても早く探索すべきである．Stone[9] はこのような場合の発見確率最大化問題を変分法で解いている．

(3) 目標物が複数個存在する場合については，それらが同質で同じ事前存在分布をもつ場合や，異質な目標物を想定する場合，あるいは目標物の個数が未知で確率変数と考えられる場合，さらには目標物を少なくとも一個発見したい場合，全ての目標物を発見したい場合などが解析されている．

(4) 偽目標物が存在する場合には，目標物らしきものと遭遇すれば探索を中断し，その目標物の真・偽を鑑定の上，偽なら除去して探索を再開する，といった探索と識別の[[二段階探索]](2-stage search) を行う．Stone and Stanshine[11]は，探索努力配分問題および識別をいつ打ち切って探索に復帰すべきかという問題を解析している．

(5) 探索場所を変更する際に[[切り換え費用]](switching cost) が必要とすると，一
般の場合の解析は極めて困難となり，得られている結果は完全発見(perfect detection：目標物の存在する場所を探索する場合，確率1 で発見する) の場合など特別なケースに限られている．

その他にも，探知関数が時間的に変化する場合，利用可能な努力を探知関数の改善にも使う場合，目標物がランダムに出現し消滅する場合，二分法探索(dichotomous search) など，さまざまなタイプのモデルが解析されている．文献案内としてはDobbie[5]，成書としてはStone[10] を挙げておく．

----
‘’’参考文献’’’

[1] W. H. Barker, “Information Theory and Optimal Detection Search,” ''Operations Reserch''，'''25''' (1977)，304-314.

[2] M. C. Chew Jr., “Optimal Stopping in a Discrete Search Problem,” ''Operation Research''  '''21''' (1973), 741-747.

[3] J. deGuenin, “Optimum Distribution of Effort：An Extension of the Koopman Basic Theory,” ''Operation Research'', '''9''' (1961), 1-7

[4] J. M. Dobbie, “Search Theory：A Sequential Approach,” ''Naval Research Logistic Quarterly'', '''10''' (1963), 323 334.

[5] J. M. Dobbie, “A Survey of Search Theory,” ''Operations Research'', '''16'''  (1968), 525-537.

[6] J. B. Kadane, “Optimal Whereabouts Search,” ''Operation Research'', '''19'''(1971), 894-904.

[7] B. O. Koopman, “The Theory of Search. The Optimum Distribution of Searching Effort,” ''Operation Research'', '''5''' (1957), 613-626.

[8] S. M. Ross, “A Problem in Optimal Search and Stop,” ''Operation Research'',  '''17''' (1969), 984-992.

[9] L. D. Stone, “Necessary and Su.cient Conditions for Optimal Solutions to a Survivor Search Problem,” ''Mathematical Programming Study'' '''6''' (1976), 227-245.

[10] L. D. Stone, ''Theory of Optimal Search'', Academic Press, 1975.

[11] L. D. Stone and J. A. Stanshine, “Optimal Search Using Uninterrupted Contact Investigation,” ''SIAM Journal of Applied Mathematics'', '''20''' (1971), 241-263.


[[category:探索理論|せいしもくひょうぶつのさいてきたんさく]]