面向最優(yōu)化問題的人工智能搜索算法研究*

王永建，楊建華，郭廣濤，王治東

（中國通信建設集團設計院有限公司，北京 100079）

面向最優(yōu)化問題的人工智能搜索算法研究*

王永建，楊建華，郭廣濤，王治東

（中國通信建設集團設計院有限公司，北京 100079）

搜索是人工智能領域的關鍵技術，隨著信息技術的不斷發(fā)展與成熟，人工智能未來發(fā)展前景寬廣?，F(xiàn)實中，許多問題解決的實質就是最優(yōu)化過程。首先介紹最優(yōu)化的概念，從解答最優(yōu)化問題出發(fā)，分析動態(tài)規(guī)劃算法在解決最優(yōu)化問題的特殊作用。然后，分析基本搜索算法中典型的深度搜索算法和廣度搜索算法的特點以及適用場景。最后，搭建仿真環(huán)境，進行對比測試。結果表明，動態(tài)規(guī)劃算法的時間復雜度遠小于搜索算法，但是其空間復雜度遠大于搜索算法，二者適用于不同的場景。

人工智能；最優(yōu)化；動態(tài)規(guī)劃；深度搜索；廣度搜索

0 引 言

近年來，微電子﹑大數(shù)據(jù)﹑互聯(lián)網(wǎng)+﹑云計算﹑新算法等技術的發(fā)展，極大推動了人工智能技術的發(fā)展。不過，目前人工智能技術還不是非常成熟，在解決某些問題的過程中還不是很完美，但人工智能已在社會上開始廣泛應用。例如，人工坐席中的語音自動識別系統(tǒng)，醫(yī)療衛(wèi)生領域中的影像識別與分析，生命科學領域中的數(shù)據(jù)預測與基因演變預測，新聞出版﹑文獻檢索領域中的自然語言翻譯﹑自動閱讀，工業(yè)領域中的機器人等。

最優(yōu)化原理，即一個問題的最優(yōu)解只取決于其子問題的最優(yōu)解。也就是說，非最優(yōu)解對問題的求解沒有影響[1]。實際中，很多問題解決或者求解的過程，實質上就是最優(yōu)化的過程。一個問題可以分解為多個子問題的最優(yōu)化問題，全部子問題的最優(yōu)解，往往就是整個問題的最優(yōu)解。

搜索是人工智能的基本問題，一個問題的求解過程就是搜索[2]。搜索技術已滲透在各種各樣的人工智能系統(tǒng)中，從某種意義上來講，“沒有搜索就沒有人工智能”。本文面向最優(yōu)化問題，對人工智能搜索算法進行研究。

1 動態(tài)規(guī)劃算法

1.1 動態(tài)規(guī)劃簡析

1.1.1 舉例分析

要理解最優(yōu)化問題，需先理解動態(tài)規(guī)劃算法。要理解動態(tài)規(guī)劃，必須先理解幾個關鍵名詞。本文通過舉例進行分析，如圖1所示。

圖1 動態(tài)規(guī)劃

圖1中，A﹑B﹑C﹑D分別代表一個景區(qū)。假定一旅客從A景區(qū)出發(fā)去往D景區(qū)，下面探討如何選擇一條最短路徑到達D景區(qū)。

將圖中的點分為四類（A﹑B﹑C﹑D），圖中所有的邊都與相鄰的兩類點互聯(lián)，并且都從前一類點指向后一類點，則圖中的邊可分為三類：A→B，B→C和C→D。需要從每一類中選出一條邊來，組成從A1到D1的一條路徑，并且要求這條路徑最短。該問題可分解為多個階段子問題[1]。

1.1.2 動態(tài)規(guī)劃關鍵詞

通常，一個動態(tài)規(guī)劃算法應該包含以下幾種基本關系與屬性。

狀態(tài)（State）：表示事物的性質，是描述動態(tài)規(guī)劃中的“單元”的量。

階段（Stage）：指一些性質相近﹑可以同時處理的狀態(tài)集合。通常，一個問題可以由處理的先后次序劃分為幾個階段。實際上，階段只是標識某些處理方法相同，和處理順序無關的狀態(tài)。一個階段可包含多個狀態(tài)，也可只包含一個狀態(tài)[3]。

狀態(tài)轉移方程：指前一個階段的狀態(tài)轉移到后一個狀態(tài)的演變規(guī)律，是關于兩個相鄰階段狀態(tài)的方程，是動態(tài)規(guī)劃的中心。

決策（Decision）：指每個階段采取的某種選擇性的活動，是系統(tǒng)需要完成的選擇。

動態(tài)規(guī)劃所處理的問題屬于“多階段決策問題”，一般由初始狀態(tài)開始，通過對中間階段決策的選擇，達到結束狀態(tài)。這些決策構成了決策序列，同時確定了完成整個過程的活動路線（通常是求最優(yōu)的活動路線），如圖2所示。

圖2 動態(tài)規(guī)劃

圖2中，決策和狀態(tài)轉移之間的關系可以理解為：決策是狀態(tài)轉移的途徑，狀態(tài)轉移是決策的目的。

各段決策確定后，整個問題的決策序列就構成一個策略，用P1,n={u1(s1),u2(s2),…,un(sn)}表示。對每個實際問題，可供選擇的策略具有一定的范圍，稱為允許策略集合，記作P1,n，而使整個問題達到最優(yōu)效果的策略就是最優(yōu)策略[3]。

因此，運用動態(tài)規(guī)劃的一個前提，即這個過程的最優(yōu)策略應具有這樣的性質：無論初始狀態(tài)及初始決策如何，對于先前決策所形成的狀態(tài)而言，其以后的所有決策應構成最優(yōu)策略。這就是最優(yōu)化原理，可以理解為“最優(yōu)策略的子策略也是最優(yōu)策略”。

1.2 無后效性

無后效性即一個問題被劃分階段后，階段I中的狀態(tài)只能由階段I+1中的狀態(tài)通過狀態(tài)轉移方程獲得，與其他狀態(tài)沒有關系，特別是與未發(fā)生的狀態(tài)沒有關系，這就是無后效性。

在信息學的多階段決策問題中，絕大部分都是能夠滿足最優(yōu)化原理的，但往往會在后效性這一點上設置障礙。

1.3 最優(yōu)指標函數(shù)和規(guī)劃方程

1.3.1 最優(yōu)指標函數(shù)

用于衡量所選定策略優(yōu)劣的數(shù)量指標稱為指標函數(shù)，最優(yōu)指標函數(shù)記為fk(sk)，它表示從第k段狀態(tài)sk采用最優(yōu)策略Pk*(sk)到過程終止時的最佳效益值。

最優(yōu)指標函數(shù)實質是關注問題的解。在上面的例子中，f2(B1)表示從B1點到終點D1點的最短路徑長度，求解的最終目標就是f1(A1)。

1.3.2 規(guī)劃方程

最優(yōu)指標函數(shù)的求法一般是一個從目標狀態(tài)出發(fā)的遞推公式，稱為規(guī)劃方程：

其中sk是第k段的某個狀態(tài)，uk是從sk出發(fā)的允許決策集合Dk(sk)中的一個決策，Tk(sk,uk)是由sk和uk所導出的第k+1段的某個狀態(tài)sk+1，g(x,uk)是定義在數(shù)值x和決策uk上的一個函數(shù)，而函數(shù)opt表示最優(yōu)化，根據(jù)具體問題分別表示為max或min。

fn(sn)=某個初始值，稱為邊界條件。

結合本文的例子分析，規(guī)劃方程即：

邊界條件為f4(D1)=0。

這里是一種從目標狀態(tài)往回推的逆序求法，適用于目標狀態(tài)確定的問題。在信息學問題中，存在很多有著確定的初始狀態(tài)。當然，對于初始狀態(tài)確定的問題，也可以采用從初始狀態(tài)出發(fā)往前推的順序求法[4]。

2 基本搜索算法

2.1 回溯算法

回溯算法是所有搜索算法中最為基本的一種算法，采用“此路不通就回撤”思想作為其控制結構。相當于采用了先根遍歷的方法來構造解答樹，可用于找解﹑所有解以及最優(yōu)解[5]。具體的算法分為遞歸算法和非遞歸算法兩種。

2.1.1 遞歸算法

解決遞歸問題的算法通常稱為遞歸算法，遞歸算法的本質是把一個較復雜問題的處理歸結為較簡單問題的處理[6]。從數(shù)學角度闡述，如果一個函數(shù)在它的函數(shù)體內(nèi)又直接或間接地調(diào)用該函數(shù)本身，那么此函數(shù)稱為遞歸函數(shù)[7]。

遞歸算法描述如下：

2.1.2 非遞歸算法

雖然遞歸算法的結構簡潔﹑可讀性強﹑實現(xiàn)簡單，但是運行效率較低[8]。尤其是遞歸越深，占用?？臻g越多。如果遞歸的深度達到超出?？臻g的程度時，遞歸算法將不再適合[9]。非遞歸算法與遞歸算法是相對的。

非遞歸算法描述如下：

Node(節(jié)點類型)＝Record

Situtation:TSituation（當前節(jié)點狀態(tài)）;

Way-NO:Integer（已使用過的擴展規(guī)則的數(shù)目）;

End

List(回溯表):Array[1..Max(最大深度)] of Node;

pos(當前擴展節(jié)點編號):Integer;

分析總結：回溯算法對空間的消耗較少，當其與分支定界法一起使用時，對于所求解處于解答樹中層次較深時的問題有較好的效果，但應避免在后繼節(jié)點可能與前繼節(jié)點相同的問題中使用，以免產(chǎn)生循環(huán)[10]。

2.2 深度搜索算法

深度搜索算法有廣義和狹義兩種理解。廣義理解是，只要最新產(chǎn)生的結點（即深度最大的結點）先進行擴展的方法，就稱為深度搜索方法。在這種理解情況下，深度搜索算法有全部保留和不全部保留產(chǎn)生的結點的兩種情況。而狹義理解是，僅僅只保留全部產(chǎn)生結點的算法[11]。本文采用廣義理解，不保留全部結點，屬于一般的回溯算法范疇。保留全部結點的算法，實際上是在數(shù)據(jù)庫中產(chǎn)生一個結點之間的搜索樹，屬于圖搜索算法的范疇。

算法實現(xiàn)描述如下：

對上面算法實現(xiàn)描述進行分析，深度搜索算法可總結如下：

（1）深度搜索算法有遞歸以及非遞歸兩種設計方法。一般，當搜索深度較小﹑問題遞歸方式比較明顯時，用遞歸方法設計好，可以使程序結構更簡捷易懂。當搜索深度較大﹑數(shù)據(jù)量較大時，由于系統(tǒng)堆棧容量的限制，遞歸容易產(chǎn)生溢出，此時用非遞歸方法設計比較好[11]。

（2）不保留全部結點的深度搜索算法。將擴展的結點從數(shù)據(jù)庫中彈出刪除，這樣一般在數(shù)據(jù)庫中存儲的結點數(shù)就是深度值。因此，占用的空間較少，所以，當搜索樹的結點較多，用其他方法易產(chǎn)生內(nèi)存溢出時，深度搜索算法不失為一種有效的算法[5]。

（3）如果要求出最優(yōu)解，一種方法將是后面要介紹的動態(tài)規(guī)劃算法；另一種方法是修改原算法，即把原輸出過程的地方改為記錄過程，即記錄達到當前目標的路徑和相應的路程值，并與前面已記錄的值進行比較，保留其中最優(yōu)的。等全部搜索完成后，才把保留的最優(yōu)解輸出[12]。

2.3 廣度搜索算法

廣度搜索算法與深度搜索算法的控制結構和產(chǎn)生系統(tǒng)很相似，唯一的區(qū)別在于對擴展節(jié)點的選取。

這兩種算法每次都擴展一個節(jié)點的所有子節(jié)點，廣度搜索擴展則是本次擴展的節(jié)點的兄弟節(jié)點。與之不同的是，深度搜索下一次擴展的是本次擴展出來的子節(jié)點中的一個。由于深度搜索保留了所有的前繼節(jié)點，所以在產(chǎn)生后繼節(jié)點時可以去掉一部分重復節(jié)點，從而提高搜索效率[13]。在具體實現(xiàn)上，為了提高效率，采用了不同的數(shù)據(jù)結構。

具體的算法描述如下：

Node(節(jié)點類型)＝Record

Situtation:TSituation（當前節(jié)點狀態(tài)）;

Level:Integer(當前節(jié)點深度);

Last :Integer(父節(jié)點);

對上面算法實現(xiàn)描述進行分析，廣度搜索算法可總結如下：

（1）在產(chǎn)生新的子結點時，深度越小的結點越先得到擴展，即先產(chǎn)生它的子結點。為使算法便于實現(xiàn)，存放結點的數(shù)據(jù)庫一般采用隊列結構。

（2）無論問題性質如何不同，利用廣度搜索算法解題的基本算法相同，但數(shù)據(jù)庫中每一結點內(nèi)容﹑產(chǎn)生式規(guī)則，根據(jù)不同的問題有不同的內(nèi)容和結構，即便同一問題也可以有不同的表示方法。

（3）當結點到根結點的耗散值和結點的深度成正比時，特別是當每一結點到根結點的耗散值等于深度時，用廣度搜索算法得到的解是最優(yōu)解；若不成正比，則得到的解不一定是最優(yōu)解。這類問題要求出最優(yōu)解，一種方法是改進前面深度（或廣度）搜索算法。具體的，先找到一個目標后，不是立即退出，而是記錄下目標結點的路徑和耗散值；如果有多個目標結點，就加以比較，留下較優(yōu)的結點；把所有可能的路徑都搜索完后，才輸出記錄的最優(yōu)路徑。

（4）廣度搜索算法，一般需要存儲產(chǎn)生的所有結點，占用的存儲空間要比深度搜索算法大得多。因此，程序設計中，必須考慮溢出和節(jié)省內(nèi)存空間的問題。

（5）比較深度和廣度兩種搜索算法。廣度搜索算法一般無回溯操作，即無入棧和出棧的操作。所以，廣度搜索算法的運行速度比深度搜索算法要快。

2.4 深度與廣度搜索算法對比

廣度搜索算法是求解最優(yōu)解問題的一種較好的方法，而深度搜索算法多用于只要求解的情況。當解答樹中的重復節(jié)點較多且重復判斷較難時使用，但往往可以用回溯算法或者A*算法代替。

一般情況下，深度搜索算法占內(nèi)存少但速度較慢，廣度搜索算法占內(nèi)存多但速度較快。在距離和深度成正比的情況下，兩者都能較快求出最優(yōu)解。因此，在選擇用哪種算法時，要綜合考慮后再決定取舍。

3 對比測試

對比基本搜索算法與動態(tài)規(guī)劃算法，以本文第1節(jié)例子作為測試依據(jù)。測試環(huán)境為：浪潮NF5270M2服 務 器，Windows Sever2012，2×Intel E5-2650v2處理器，32GB DDR3內(nèi)存，2×300GB 15K SAS硬盤；在仿真軟件Matlab 2013a中建立數(shù)學模型。采用搜索算法與采用動態(tài)規(guī)劃算法完成問題解答，消耗時間如表1所示。

表1 搜索算法與動態(tài)規(guī)劃算法消耗時間

從表1可以分析，動態(tài)規(guī)劃算法與搜索算法在實際應用中的運行時間差異是巨大的。從理論上講，搜索算法的時間復雜度為O(N!)，動態(tài)規(guī)劃算法的時間復雜度是O(N2)，兩個時間根本不在一個數(shù)量級。指數(shù)級的時間增長十分可怕，遠遠大于多項式級的算法。所以，經(jīng)常稱多項式級的算法為“較好”的算法，稱指數(shù)級的算法是“較差”的算法。

動態(tài)規(guī)劃算法實質上是一種“以空間代價來換取時間代價”的技術，它在實現(xiàn)過程中不得不存儲產(chǎn)生過程中的各種狀態(tài)，所以空間復雜度要大于其他算法。具體的，動態(tài)規(guī)劃的時間復雜度為O(N2)，搜索算法的時間復雜度為O(N!)。

依據(jù)測試結果分析總結：對于實時性要求不高，資源緊張或者成本敏感的場景，適用于搜索算法；對于實時性要求較高，資源充?；蛘叱杀静幻舾械膱鼍?，適用于動態(tài)規(guī)劃算法。

4 結 語

人工智能是個方興未艾的領域，將對未來人類社會的發(fā)展與生活產(chǎn)生重大影響。隨著人工智能技術的不斷成熟，其商業(yè)價值與社會價值將不可估量。本文分析動態(tài)規(guī)劃算法，對基本搜索算法中的代表算法進行闡述研究，并對搜索算法和動態(tài)規(guī)劃算法進行對比測試，測試結果將為不同場景選擇適合的算法提供參考依據(jù)。隨著信息技術﹑人工智能領域的不斷發(fā)展，將會產(chǎn)生新的算法和技術。因此，該領域的研究任重道遠。

[1] 李剛.動態(tài)規(guī)劃的深入討論[DB/OL].(2011-09-20)[2016-05-22].http://wenku.baidu.com/view/ a17920f57c1cfad6195fa790.htm l.

LI Gang.A Deep Discussion on Dynamic Programming[DB/ OL].(2011-09-20)[2016-05-22].http://wenku.baidu.com/ view/a17920f57c1cfad6195fa790.html.

[2] 陳溪.基于電力市場環(huán)境下江西省購電優(yōu)化及管理研究[D].南昌:南昌大學,2014.

CHEN Xi.Study on the Optimization and Management of Electricity Purchase in Jiangxi Province based on the Electricity Markets[D].Nanchang:Nanchang University,2014.

[3] 胡運權,郭耀煌.運籌學教程[M].北京:清華大學出版社,2012.

HU Yun-quan,GUO Yao-huang.Operational Research Tutorial[M].Beijing:Tsinghua University press,2012.

[4] 魏慶來,宋睿卓,孫秋野.迭代自適應動態(tài)規(guī)劃理論及應用[M].北京:科學出版社,2015.

WEI Qing-lai,SONG Rui-zhuo,SUN Qiu-ye.Theory and App lication of Iterative Adap tive Dynam ic Programming[M].Beijing:Science Press,2015.

[5] 歐陽圣,胡望宇.幾種經(jīng)典搜索算法研究與應用[J].計算機系統(tǒng)應用,2011,20(05):243-247.

OU YANG-sheng,HU W ang-yu.Research and Application of Several Classical Search Algorithms[J]. Computer Systems & Applications,2011,20(05):243-247.

[6] 張國.基于遞歸算法的非遞歸實現(xiàn)研究[J].長江大學學報:自然科學版,2009,6(03):223-225.

ZHANG Guo.Implementation and Research of Non Recursive based on Recursive Algorithm[J].Journal of Yangtze University(Natual Science),2009,6(03):223-225.

[7] 魏斌,馬繼輝,?；?基于遞歸算法的樹型結構圖的設計與實現(xiàn)[J].計算機應用與軟件,2011,28(01):96-98.

WEI Bin,MA Ji-hui,NIU Hu.Design and Implementation of Recursion Algorithm-based Tree Structure Diagram[J]. Computer Applications and Software,2011,28(01):96-98.

[8] 楊春花,姚進,趙培英等.一個遞歸算法非遞歸化的算法框架[J].計算機應用與軟件,2010,27(09):81-84.

YANG Chun-hua,YAO Jin,ZHAO Pei-ying,et al.An Algorithm Frame for Converting Recursive Algorithms to Nonrecursive Ones[J].Computer Applications and Software,2010,27(09):81-84.

[9] 單學廣,楊慶紅,焦莉.遞歸問題的非遞歸實現(xiàn)方法的應用研究[J].計算機與現(xiàn)代化,2011,(01):25-28.

SHAN Xue-guang,YANG Qing-hong,JIAO Li. Application Research on Recursion Question's Nonrecursion Realization Method[J].Computer and Modernization,2011(01):25-28.

[10] 羅斯.搜索算法基礎教程[DB/OL].(2010-03-01) [2016-05-22].http://blog.csdn.net/alsm168/article/ details/6487146..

LUO Si.Basic Course of Search Algorithm[DB/OL]. (2010-03-01)[2016-05-22].http://blog.csdn.net/ alsm168/article/details/6487146.

[11] 張麗娟.自主移動服務機器人路徑規(guī)劃方法研究[D].天津:天津科技大學,2012.

ZHANG Li-juan.The Research of the Autonomous Mobile Service Robot Path Planning Method[D]. Tianjin:Tianjin University of Science&Technology,2012.

[12] 龔兵.基于IP網(wǎng)絡的自動拓撲搜索算法[J].五邑大學學報:自然科學版,2007,20(04):6-12.

GONG Bing.An Au tomatic Topological Search Algorithm based on IP Network[J].Journal of Wuyi University(Natural Science Edition),2007,20(04):6-12.

[13] 陳圣群,滕忠堅,洪親等.四種最短路徑算法實例分析[J].電腦知識與技術:學術交流版,2007,3(16):1030-1032.

CHEN Sheng-qun,TENG Zhong-jian,HONG Qing,et al.The Case Analysis of Four Shortest Path Algorithm[J]. Computer Know ledge and Technology(Academ ic Exchange),2007,3(16):1030-1032.

Artificial-Intelligence Search A lgorithm for Optim ization Problem

WANG Yong-jian, YANG Jian-hua, GUO Guang-tao, WANG Zhi-dong

(China International Telecommunication Construction Group Design Institute Co. Ltd., Beijing 100079, China)

Search is the key technology in the field of artificial intelligence. With the ripid development and mature of information technologies, artificial intelligence would have a broad development prospects in the future. The essence for solving many problems, in fact, is the process of optimization. Firstly, the concept of optimization is described, and then from the solution to optimization problem, the special functions of dynamic programming algorithm in solving optimization probleMare analyzed. And then the typical depth search algorithMand breadth search algorithm in basic search algorithms are discussed, including their applicable environments. Finally, the simulation environment is built up and the contrast test is done, and the results show that the time complexity of dynamic programming algorithm is much less than that of search algorithm, but the space complexity is much larger than that of search algorithm, and these two algorithms are suitable for different scenarios. As the ascendant field, artificial intelligence requires continuous research and exploration.

artificial intelligence; optimization; dynamic programming; depth search; breadth search

TP392

A

1002-0802(2016)-11-1459-07

10.3969/j.issn.1002-0802.2016.11.009

王永建（1981—），男，碩士，高級工程師，主要研究方向為信息安全﹑大數(shù)據(jù)﹑信息編碼；

楊建華（1979—），男，學士，高級工程師，主要研究方向為云計算﹑計算機應用；

郭廣濤（1977—），男，學士，高級工程師，主要研究方向為云計算﹑物聯(lián)網(wǎng)；

王治東（1981—），男，學士，高級工程師，主要研究方向為云計算﹑數(shù)據(jù)通信。

2016-07-16；

2016-10-13 Received date:2016-07-16;Revised date:2016-10-13