汪孔斌 尹弼民

(銅陵職業(yè)技術(shù)學(xué)院，安徽銅陵244000；南昌大學(xué)軟件學(xué)院，江西南昌330047)

基于博弈論的啟發(fā)式搜索算法的改進研究

汪孔斌 尹弼民

(銅陵職業(yè)技術(shù)學(xué)院，安徽銅陵244000；南昌大學(xué)軟件學(xué)院，江西南昌330047)

基于博弈理論提出了一種路徑搜索問題的優(yōu)化算法。將路徑搜索問題的搜索空間映射為博弈的策略組合空間，而路徑搜索問題的目標(biāo)函數(shù)映射為博弈的效用函數(shù)，通過遍歷博弈支持集搜索納什均衡解，并利用啟發(fā)思想根據(jù)博弈的結(jié)構(gòu)制定搜索策略，以期望用最小的代價減少搜索節(jié)點數(shù)、提高應(yīng)用系統(tǒng)的性能及效率。

路徑搜索；啟發(fā)式；博弈論；納什均衡

1.引言

搜索技術(shù)是人工智能的一個重要研究內(nèi)容，路徑搜索是地理信息系統(tǒng)、導(dǎo)航系統(tǒng)、無線傳感網(wǎng)絡(luò)[1]以及計算機網(wǎng)絡(luò)等系統(tǒng)中的一個典型應(yīng)用，通常需要考慮以下幾個因素：一，路徑搜索頻繁；二，網(wǎng)絡(luò)規(guī)模龐大，節(jié)點數(shù)量多；三，需要近乎實時的響應(yīng)速度。如果系統(tǒng)是應(yīng)用在移動設(shè)備上，還需要考慮設(shè)備的硬件資源(運算、存儲等)有限等因素。

搜索算法可以分為盲目搜索算法和啟發(fā)式搜索算法，二者的區(qū)別在于，啟發(fā)式搜索算法的每一步都試圖向著目標(biāo)狀態(tài)方向進行搜索[1]，而盲目搜索算法的每一步按固定之規(guī)則而搜索，然后判斷是否達到目標(biāo)狀態(tài)。因而，啟發(fā)式搜索算法克服了盲目搜索算法的盲目性問題。

本文以經(jīng)濟學(xué)博弈論為基礎(chǔ)，提出一種改進的啟發(fā)式搜索算法，新算法的基本思路是將問題的搜索空間映射為博弈的策略組合空間[6]，目標(biāo)函數(shù)映射為博弈的效用函數(shù)，通過遍歷博弈支持集搜索納什均衡解，并利用啟發(fā)思想根據(jù)博弈的結(jié)構(gòu)制定搜索策略，以期望用最小的代價減少搜索節(jié)點數(shù)、提高應(yīng)用系統(tǒng)的性能及效率。

最后，在Android平臺上實現(xiàn)其仿真實驗，并將其與深度優(yōu)先搜索算法、廣度優(yōu)先搜索算法，Dijkstra算法，最佳優(yōu)先(best-first search，BFS)搜索算法、Dijkstra A*算法（一種基于Dijkstra的啟發(fā)式算法）的仿真結(jié)果進行比對，以實例數(shù)據(jù)驗證了該算法的靈活性、有效性以及平衡最優(yōu)性。

2.改進博弈算法

定義1設(shè)x為路徑搜索問題中的變量，f為問題中待解目標(biāo)函數(shù)，博弈結(jié)構(gòu)G=[I,S,U]，稱映射Φ：x-＞s為一個決策變換。映射Ψ：f-＞U為一個效用變換。

定義2從某個局勢s開始，所有主體順序選擇(在本文中，博弈主體進行局勢演化的先后順序依照當(dāng)前所選擇的節(jié)點到目標(biāo)點的直線物理距離的升序排列)各自最優(yōu)反應(yīng)的動態(tài)過程稱為一個回合。

關(guān)于定義1的兩個變換，將問題尋找最短路徑的過程變換為博弈主體尋求結(jié)構(gòu)G的最優(yōu)均衡點的演化過程。記改進博弈算法AGA（Advanced Game Algorithm）為一個五元組：

公式注解：

結(jié)構(gòu)G：對于x的每一個分量xi∈{0,1}，用1個博弈主體的策略表示，即為I={1，2，...，n}；n個博弈主體的策略組合s即對應(yīng)于路徑搜索問題中選擇的一條路徑；而同一策略組合之下各主體的效用相等：若s是可行解，ui（s）=f（s），否則回溯到上一步。

初始局勢s0：每個主體從自己的策略空間中隨機地選擇一個策略構(gòu)成初始局勢s0，這是主體進行博弈演化的起點。

主體行為算子α：假設(shè)參與博弈的主體追求自身效用最大化，則主體行為算子α即為主體在演化局勢中的最優(yōu)反應(yīng)對應(yīng)，最優(yōu)反應(yīng)對應(yīng)通過比較該主體所有可能策略在該局勢下的效用求得。

局勢演化算子ζ：各主體通過順序最優(yōu)反應(yīng)動態(tài)達到的納什均衡并不一定是帕累托最優(yōu)的，于是使用局勢演化算子?對均衡狀態(tài)施加隨機擾動，使之偏離原均衡狀態(tài)，接著由各主體的順序最優(yōu)反應(yīng)動態(tài)恢復(fù)到新的均衡狀態(tài)。不斷重復(fù)這樣的擾動恢復(fù)過程直至搜尋到更優(yōu)的均衡狀態(tài)。對于s的第i個分量，即主體i的所取策略s(i)，若均勻隨機數(shù)rand (0,1)小于擾動概率p(實驗中設(shè)定p=0.1)，則用主體i當(dāng)前策略的相反策略替換當(dāng)前策略；否則維持原策略不變。對s的所有分量重復(fù)這樣的選擇方式即得擾動后的局勢s’.

停止準(zhǔn)則τ：稱達到均衡的兩個回合博弈稱為博弈演化的一代.本文的停止準(zhǔn)則取為τ＞T,T為預(yù)設(shè)的演化最大代數(shù)。事實上，T越大，所得到的結(jié)果越接近最優(yōu)解（或就是最優(yōu)解），但是同時消耗的時間也越多。

關(guān)于定義2，經(jīng)過作用主體行為算子的兩個回合，局勢演化序列必定達到納什均衡狀態(tài)。這是因為第一個回合后達到的策略組合必是可行解，第二個回合后達到的策略組合必是均衡狀態(tài)。因為非可行解的效用總是小于可行解的效用，而第二個回合的開始局勢是可行解，所以第二個回合歷經(jīng)的狀態(tài)都是可行解，由反證法可以得到第二回合后到達的策略組為均衡狀態(tài)，具體參考文獻[6]中的證明。

3.算法分析

首先開發(fā)出啟發(fā)因子TempEdge類，該類為現(xiàn)時準(zhǔn)備走的邊，包括邊的開始節(jié)點和目的節(jié)點，為優(yōu)先隊列設(shè)置比較器。對所有邊的目的節(jié)點按照其到target的直線直線物理距離進行排序，產(chǎn)生List＜TempEdge＞edges隊列，然后在void AGA()算法中實現(xiàn)路徑選擇。注意設(shè)置局勢演化算子，使用線程實現(xiàn)每隔3000ms自動演化一次，設(shè)置停止準(zhǔn)則T，并針對不同大小的T值進行實驗，記錄數(shù)據(jù)。摘取兩段代碼如下：

算法1.比較器中重載的比較函數(shù).

@Override

public intcompare(TempEdge o1,TempEdge o2){

//TODO Auto-generatedmethod stub

int[]target=game.target;

//直線物理距離

int a=(o1.gettEnd0()-target[0])*(o1.gettEnd0()-target[0])+(o1.gettEnd1()-target[1])*(o1.gettEnd1()-target[1]);

int b=(o2.gettEnd0()-target[0])*(o2.gettEnd0()-target[0])+(o2.gettEnd1()-target[1])*(o2.gettEnd1()-target[1]);

return a-b;

}

算法2.AGA算法（截取一段）.

double pmark=Math.random();

if(pmark＜P){//P為局勢演化算子，此時發(fā)生隨機擾動

Random r=new Random();

inth=r.nextInt(edges.size());

currentEdge[0][0]=edges.get(h).gettStart0();

currentEdge[0][1]=edges.get(h).gettStart1();

currentEdge[1][0]=edges.get(h).gettEnd0();

currentEdge[1][1]=edges.get(h).gettEnd1();

//取出此邊的目的點

tempTarget[0]=currentEdge[1][0];

tempTarget[1]=currentEdge[1][1];

edges.remove(h);}

else{//當(dāng)隨機數(shù)大于P時，隨機擾動不發(fā)生，

//直接取出優(yōu)先隊列中第一個數(shù)字即可

currentEdge[0][0]=edges.get(0).gettStart0();

currentEdge[0][1]=edges.get(0).gettStart1();

currentEdge[1][0]=edges.get(0).gettEnd0();

currentEdge[1][1]=edges.get(0).gettEnd1();

//取出此邊的目的點

tempTarget[0]=currentEdge[1][0];

tempTarget[1]=currentEdge[1][1];

edges.remove(0);

}

本文算法在Android平臺上的仿真結(jié)果截圖如下：

圖3-1 AGA算法搜索目標(biāo)0的三張例圖

圖3-2 AGA算法停止后目標(biāo)0的路徑解

4.實驗對比

深度優(yōu)先搜索算法是把最近剛產(chǎn)生的結(jié)點優(yōu)先擴展，直到達到一定的深度限制。若未找到目標(biāo)或無法再擴展時，再回溯到另一個結(jié)點繼續(xù)擴展[2]。

廣度優(yōu)先搜索算法（Breadth-First-Search），是一種圖形搜索算法。簡單的說，它的基本思路是站在一個節(jié)點上，先將所有連接到該節(jié)點的節(jié)點訪問到，再繼續(xù)訪問下一層，直到找到目標(biāo)為止。廣度優(yōu)先搜索算法具有完全性。即無論圖形的種類如何，只要目標(biāo)存在，則它一定會找到。

Dijkstra算法其基本原理是：每次新擴展一個距離最短的點，更新與其相鄰點的距離。當(dāng)所有邊權(quán)均為正時，由于不會存在一個距離更短的沒擴展過的點，故這個點的距離永不會再被改變，從而保證算法的正確性。不過依據(jù)此原理，用Dijkstra求最短路的圖不能有負權(quán)邊，因為擴展到負權(quán)邊時會產(chǎn)生更短的距離，有可能會破壞已經(jīng)更新的點距離不會改變的性質(zhì)[3]。

本例中最佳優(yōu)先搜索算法是對廣度優(yōu)先算法的一種優(yōu)化，它的思想為：在所有可能達到的下一個節(jié)點中選擇與目的節(jié)點最接近的節(jié)點。

對Dijkstra算法的優(yōu)化同樣類似，建構(gòu)的是一種基于Dijkstra的啟發(fā)式尋徑方法，在被優(yōu)化的算法中，針對最短距離和現(xiàn)下距離作了一次比較，從而改進原有算法。如此，則為本例中的Dijkstra A*算法[3]。

算法的仿真結(jié)果比對如后表所示：

表1 目標(biāo)0之實驗結(jié)果比對

表2 目標(biāo)1之實驗結(jié)果比對

5.結(jié)論

經(jīng)過仿真實驗的對比，表明這種基于博弈論的改進啟發(fā)式路徑搜索算法相較傳統(tǒng)的搜索算法而言，可以避免重復(fù)無效的搜索，提高搜索效率，同時能夠盡可能地搜索出問題優(yōu)解，并且在應(yīng)用方面，有著靈活性、有效性以及平衡最優(yōu)性。

[1]米志超，周建江，邵海林.一種啟發(fā)式能量優(yōu)化的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集算法[J].武漢大學(xué)學(xué)報(理學(xué)版)，2008，（3）：338-342.

[2]龔建華.深度優(yōu)先搜索算法及其改進[J].現(xiàn)代電子技術(shù)，2007，（22）：90-92.

[3]王景存，張曉彤，陳彬，陳和平.一種基于Dijkstra算法的啟發(fā)式最優(yōu)路徑搜索算法[J].北京科技大學(xué)學(xué)報，2007，（3）：346-350.

[4]周陽，樊建華，王志芹，張潔華.基于節(jié)點度和最小支撐聚類的路徑搜索算法[J].計算機工程與應(yīng)用，2013，（9）：164-167.

[5]孫澤宇,姬曉輝.改進啟發(fā)式蟻群算法求解電網(wǎng)規(guī)劃優(yōu)化問題[J].計算機仿真，2013，（1）：183-187.

[6]葉俊，劉賢德，韓露.基于博弈論的背包問題優(yōu)化算法[J].華中科技大學(xué)學(xué)報(自然科學(xué)版)，2003，（9）：53-55.

[7]王志勇，韓旭，許維勝，楊繼君.基于改進蟻群算法的納什均衡求解[J].計算機工程，2010，（14）：166-168，171.

[8]隗立濤，修乃華.基于啟發(fā)搜索算法的納什均衡計算[J].北京交通大學(xué)學(xué)報，2007，（3）：58-62.

[9]黎萍，楊宜民.基于博弈論的多機器人系統(tǒng)任務(wù)分配算法[J].計算機應(yīng)用研究，2013，（2）：392-395.

（責(zé)任編輯：孟偉東）

TP18

：A

：1671-752X（2013）04-0069-03

2013-07-13

汪孔斌（1970-），男，安徽桐城人，銅陵職業(yè)技術(shù)學(xué)院信息工程系實驗師；尹弼民（1992-），女，安徽桐城人，南昌大學(xué)軟件學(xué)院在讀碩士研究生。