最優(yōu)搜索問題的一個模型

葉文敏

【摘 要】研究了離散時間和空間中運動目標最優(yōu)搜索問題，給出了使得成功探測到搜索目標的可能性達到最大值的一個模型及其算法。

【關(guān)鍵詞】最優(yōu)搜索；模型

1.搜索理論簡介

最優(yōu)搜索理論是關(guān)于如何以一種“最佳”的方式尋找某個事先己確定的對象（通常被稱之為“搜索目標”）的理論。通常最優(yōu)搜索問題由下面三個基本的要素 所構(gòu)成：

1.1目標的位置和移動路徑的概率分布函數(shù)

對搜索目標在某個時刻的初始位置以及它在隨后所做的各種運動的可能性大小等信息進行量化即可獲得目標的概率分布函數(shù)。

1.2探測函數(shù)

探測函數(shù)的定義為：設(shè)Z（t）是搜索者在時刻t的位置，則有：

b（x，t，z，v，）Δt=p在（t，t+Δt）中找到目標|X（t）=x，Z（t）=z，V（t）=v+0（Δt）

一般情況下用b（x，t，z）表示探測函數(shù)，第四個變量V不需要寫出來。

探測函數(shù)給出了將投入到某個區(qū)域的搜索資源（如時間）的數(shù)量與給定搜索目標位于該區(qū)域時成功探測到該目標的可能性大小聯(lián)系起來的函數(shù)關(guān)系，它與目標的運動模型緊密相關(guān)。

1.3對可用資源的約束條件

一般情況下搜索者可用于搜索目標的資源（或者能力）是有限的。

給出了探測函數(shù)和目標位置的概率分布函數(shù)之后，我們就可以計算出針對搜索空間的各個區(qū)域中的搜索資源的每一種分配方法，所對應(yīng)的成功探測到搜索目標的概率是多大。所以最優(yōu)搜索問題的解就是找到一種對于搜索資源（比如搜索時間）的最佳分配方法，使得成功探測到搜索目標的可能性達到最大值，或者使得成功探測到目標所需的代價（即資源的消耗）的期望值達到最小值，本文僅僅討論離散時間和空間中使得成功探測到搜索目標的可能性達到最大值的情形。

2.問題的模型

2.1靜止目標的最優(yōu)搜索問題

靜止目標的最優(yōu)搜索問題其實就是求解一個最優(yōu)化問題：

D（f）=b（x，f（x））p（x）dx

約束條件：f（x）dx≤C（f）

即求解使得D（f）最大的f（x）

這里X是搜索空間（比如平面），F(xiàn)表示平面上的全體非負可積函數(shù)的集合，fF為搜索資源分配函數(shù)，p（x）表示目標的概率分布，D（f）是發(fā)現(xiàn)目標的探測概率，C（f）是關(guān)于f的成本函數(shù)。通常b（x，z）=1-e-Rz，R為掃描頻率，表示搜索的實施時間間隔。

2.2運動目標的最優(yōu)搜索問題

假設(shè)目標在m個盒子中運動，把T分為n個時間間隔，目標在每一個時間間隔內(nèi)占據(jù)一個盒子，則令搜索空間為 C=1，2，...，m，T=1，2，...，n，C和T為σ-有限可測集，測度分別為v和τ，目標的運動是一個隨機過程 X=Xt：t≥0，其中一條樣本路徑表示為ω=（ω，ω，...，ω）∈C；p：C→0，1。p（ω）為路徑ω的概率分布，令Ω=ω∈

C：p（ω）>0 （n=1時，這就是一個靜止目標最優(yōu)搜索問題）。假定目標的運動與搜索者的行為之間相互獨立，不同時間間隔內(nèi)搜索相互獨立。

定義=ξ（c，i）：c∈C，i=1，2，...，n為一個搜索策略，并且假定探測函數(shù)b為指數(shù)型函數(shù)[2]，即：

b（c，i，ξ）=1-exp（-W（c，i）ξ（c，i））

b（c，i，ξ）表示按照ξ這種搜索策略i時刻目標在c盒子中能被找到的概率，W（c，i）表示當(dāng)目標在i時刻位于c盒子中時的搜索能力（比如掃描寬度）。一般情況下，搜索資源的投放速度是有限制的，也即存在一個與i有關(guān)的搜索資源上限L（i）

所以在整個搜索過程中沒有搜索到目標的概率為：f（ξ）=E

exp=p（ω）exp

………………………………①

約束條件為：ξ（c，i）≥0，ξ（c，i）≤L（i） ………………………………………②

要求解使得f（ξ）最小的ξ.

3.模型的求解

選擇一個時刻i并且確定除了時刻i以外的其他所有時間的搜索均為失敗的，那么相應(yīng)的最優(yōu)搜索問題就轉(zhuǎn)化成了在這些條件下導(dǎo)致的靜止目標搜索問題。

假設(shè)η：C→[0，∞） 為一個v可測函數(shù)，對∶?c∈C，令

rep（ξ，η，i）=η（c）.........j=i

ξ（c，j）......j≠i

如果選擇一組滿足η（c）≥0（c∈C）和η（c）≤L（i）的η，使得：

prep（ξ，

η

，i）minprep（ξ，η，i）

則稱η是ξ在時間i的再分配函數(shù)[3]。

引入再分配函數(shù)的意義在于溝通隨機運動目標問題與靜止目標問題的關(guān)系。

令p（c，i，ξ）表示在除i時刻以外的任何其它時刻均搜索不到目標，且目標在i時刻位于盒子c中的概率，則：

p（c，i，ξ）=exp

-W（ω

，j）ξ（ω

，j）

這樣①就變成了：

f（rep（ξ，η，i））=E（rep（ξ，η，i））=P（c，i，ξ）exp（-W（c，i）η（c））

………………③

③顯然可以看作是分布函數(shù)為p（?，i，ξ）的靜止目標搜索問題。

由上面的討論可以給出一個迭代算法：

E（ξ）=rep（ξ，η，i）

ξ=E（ξ） i=1，2，...，n j=0，1，2，......

具體的步驟為：

給定充分小的正數(shù)ε；

①j=0；從i=1到i=n

計算 ξ=i（ξ）

②如果f（

ξ）-f（ξ

）<ε，則停止，最優(yōu)分配就是ξ（n+1）j。

③j=j+1，回到步驟①。

這樣就會得到一個迭代序列（ξ，ξ，...） ，可以證明這個序列是收斂的，利用這個算法可編制計算機程序解決實際問題。

【參考文獻】

[1]StoneLD.Theory of OptimalSearch[M].Mathematics in Science and Engineering，New York：Academic Press，1975，118.

[2]朱清新.最優(yōu)搜索理論及其應(yīng)用[J].科學(xué)出版社，2005，27（4）：39-49.

[3]Brown S S.Optimal Search for a Moving Target in Discrete Time and Space[J].Operations Research，1980，28：1275-1289.