導(dǎo)語：如何才能寫好一篇路徑規(guī)劃典型算法，這就需要搜集整理更多的資料和文獻(xiàn)，歡迎閱讀由公務(wù)員之家整理的十篇范文，供你借鑒。

篇1

作者簡介： 朱新平（1983-），男，博士，研究方向?yàn)橄冗M(jìn)機(jī)場場面運(yùn)行控制，電話：13419037831，E-mail：

通訊作者： 韓松臣（1963-），男，教授，博士，研究方向?yàn)榭罩薪煌ò踩?、空域?guī)劃管理，E-mail：

文章編號： 0258-2724（2013）03-0565-09DOI： 10.3969/j.issn.0258-2724.2013.03.027

摘要：

為支持先進(jìn)機(jī)場場面活動引導(dǎo)與控制系統(tǒng)（A-SMGCS，advanced surface movement guidance and control system）實(shí)施航空器滑行的精確引導(dǎo)，將場面分為滑行道交叉口和直線段等典型運(yùn)行單元，利用改進(jìn)的擴(kuò)展賦時(shí)庫所Petri網(wǎng)，建立了場面運(yùn)行模塊化模型；采用該模型進(jìn)行染色體編碼，并考慮場面運(yùn)行管制規(guī)則，提出了染色體合法性檢測與修復(fù)算法，以及染色體交叉和變異算法.基于首都國際機(jī)場01號跑道實(shí)際運(yùn)行數(shù)據(jù)，用本文模型和算法進(jìn)行了多個(gè)航班滑行初始路徑規(guī)劃，研究結(jié)果表明：與節(jié)點(diǎn)-路段類模型相比，本文模型能更充分地描述場面管制規(guī)則約束，可避免生成違反管制規(guī)則的路徑；本文算法的每個(gè)航班初始路徑規(guī)劃耗時(shí)小于10 s，符合A-SMGCS的要求；由于考慮了航空器滑行速度調(diào)整特征，更符合場面運(yùn)行的實(shí)際情況.

關(guān)鍵詞：

空中交通；A-SMGCS；滑行路由規(guī)劃； Petri網(wǎng)；遺傳算法

中圖分類號： V351.11文獻(xiàn)標(biāo)志碼： A

航空器滑行自動路由規(guī)劃可以協(xié)調(diào)進(jìn)離港航班安全有序地滑行，從而減少場面擁堵并提升場面容量.在國際民航組織（International Civil Aviation Organization， ICAO）提出的先進(jìn)機(jī)場場面引導(dǎo)與控制系統(tǒng)（advanced surface movement guidance and control system， A-SMGCS）中，路由規(guī)劃功能是實(shí)現(xiàn)航空器場面滑行精確引導(dǎo)的前提[1].航空器場面滑行具有并發(fā)、資源共享特性，并受多種管制規(guī)則約束. A-SMGCS路由規(guī)劃不同于傳統(tǒng)道路網(wǎng)絡(luò)中的車輛路徑規(guī)劃，文獻(xiàn)[2]提出了A-SMGCS三階段路由規(guī)劃策略：

（1） 初始路徑規(guī)劃，為進(jìn)離港航班確定最優(yōu)滑行路徑和s-1個(gè)次優(yōu)滑行路徑（s值由管制員動態(tài)交互確定）；

（2） 滑行前路由指派，依據(jù)航空器開始滑行前的場面態(tài)勢，為其確定合理路由；

（3） 路由實(shí)時(shí)更新，在航空器滑行過程中實(shí)時(shí)調(diào)整路由，以避免沖突發(fā)生.

本文僅考慮第（1）階段，即初始路徑規(guī)劃問題.

Petri網(wǎng)廣泛用于A-SMGCS場面運(yùn)行過程的建模與沖突監(jiān)控[3-4]，但較少用于航空器滑行路由規(guī)劃.文獻(xiàn)[5]將無向交通網(wǎng)絡(luò)轉(zhuǎn)換為Petri網(wǎng)表示的有向圖，并通過Petri網(wǎng)仿真器求解最短有向路徑.文獻(xiàn)[6]將機(jī)場滑行路徑描述為有向圖，并轉(zhuǎn)換為Petri網(wǎng)圖求解最佳滑行路徑.文獻(xiàn)[2]建立了基于Petri網(wǎng)的場面活動模型，并通過時(shí)間窗調(diào)度來進(jìn)行路由規(guī)劃.上述研究建立的Petri網(wǎng)模型對場面管制規(guī)則約束考慮不全面，在算法設(shè)計(jì)上未充分利用Petri網(wǎng)的數(shù)學(xué)特征，且通常針對某一特定機(jī)場進(jìn)行分析，實(shí)用性和通用性均顯不足.另一方面，將航空器場面滑行速度假設(shè)為恒定值[7-9]，忽略了航空器在場面不同區(qū)域滑行速度的調(diào)整變化，導(dǎo)致所得路由結(jié)果不能支持航空器滑行的精確引導(dǎo).

在文獻(xiàn)[2]的基礎(chǔ)上，本文從以下方面展開研究：

（1） 給出一種擴(kuò)展賦時(shí)庫所Petri網(wǎng)（extended timed place Petri net， ETPPN），以準(zhǔn)確描述場面運(yùn)行管制規(guī)則約束，并提出一種模塊化、面向路由規(guī)劃的場面運(yùn)行ETPPN模型建模方法；

（2） 采用遺傳算法規(guī)劃航空器初始滑行路徑，其染色體編碼采用場面ETPPN模型的變遷激發(fā)序列，且交叉和變異均僅針對模型中的變遷進(jìn)行，避免了以滑行道系統(tǒng)拓?fù)浣Y(jié)構(gòu)中的交叉口或直線段為基因組成染色體，在此基礎(chǔ)上展開的遺傳操作保證了方法的通用性；

（3） 與文獻(xiàn)[7-9]中關(guān)于航空器場面滑行速度恒定的假設(shè)不同，細(xì)化了航空器加減速特性對路段占用時(shí)間的影響，使路由規(guī)劃結(jié)果的精確度更高，實(shí)用性更強(qiáng).

1

航空器場面運(yùn)行過程建模

1.1

面向資源的場面運(yùn)行過程建模

可見，采用ETPPN模型對場面運(yùn)行進(jìn)行建模，可描述航空器對場面各單元的動態(tài)占用與釋放，以及航空器在各單元滑行應(yīng)遵循的管制規(guī)則.場面其它典型單元運(yùn)行過程的Petri網(wǎng)建模也可采用本節(jié)的方法.不同機(jī)場的場面交通系統(tǒng)具有不同構(gòu)型，但基本組成單元類似且有準(zhǔn)確的數(shù)量和明確的運(yùn)行規(guī)則.因此，利用各單元對應(yīng)的ETPPN模型，并采用Petri網(wǎng)同步合成技術(shù)[10]可實(shí)現(xiàn)場面運(yùn)行過程建模.

1.2

航空器滑行特征分析

航空器場面滑行速度具有以下特征：

（1） 當(dāng)航空器先后通過的兩路段均為直線或彎道時(shí)，無須加減速；

（2） 當(dāng)航空器從彎道滑入直線段時(shí)，須啟動加速過程；

（3） 當(dāng)航空器從直線段滑入彎道時(shí)，減速過程通常在進(jìn)入彎道前完成.

2

基于GA的初始路徑規(guī)劃算法

2.1

面向初始路徑規(guī)劃的GA設(shè)計(jì)

遺傳算法（genetic algorithm， GA）在工程優(yōu)化領(lǐng)域已得到廣泛應(yīng)用[11]，并越來越多地應(yīng)用于航空器路由優(yōu)化[12-15].本文提出基于場面ETPPN模型和GA的初始路徑規(guī)劃方法，基本思路為：

（1）

采用第1節(jié)方法，建立場面活動區(qū)中各典型運(yùn)行單元對應(yīng)的ETPPN模型，同時(shí)將場面管制規(guī)則約束集成到Petri網(wǎng)元素中，最終得到場面ETPPN模型；

（2）

以場面ETPPN模型為基礎(chǔ)，采用合適的編碼方式對模型中所含相關(guān)元素進(jìn)行染色體編碼，并設(shè)計(jì)相關(guān)遺傳操作，求解初始滑行路徑集合（包括1個(gè)最優(yōu)和s-1個(gè)次優(yōu)滑行路徑）.

上述思路的優(yōu)勢在于，對任何一個(gè)機(jī)場的航空器初始路徑規(guī)劃，所要解決的問題只需采用第1節(jié)的模塊化建模方法，將場面交通系統(tǒng)映射為對應(yīng)的ETPPN模型并輸入管制規(guī)則約束即可，因而保證了所給算法的實(shí)用性和通用性.

2.2

染色體編碼

染色體應(yīng)滿足以下約束：

（1） 物理約束.指與航空器自身占用物理空間大小或與滑行性能相關(guān)的約束，如翼展對通過某些區(qū)域的限制等.

（2） 管制規(guī)則約束.指管制規(guī)則確定的航空器在某些路段的滑行約束，如滑行速度約束、進(jìn)出某機(jī)坪必經(jīng)的交叉口等.

算法2中，步驟1保證了染色體不會出現(xiàn)重復(fù)基因，即所規(guī)劃滑行路徑不會出現(xiàn)環(huán)路；步驟2保證了航空器在單元內(nèi)部的滑行過程滿足航空器性能要求，例如航空器在同一交叉口滑行時(shí)不能多次轉(zhuǎn)彎；步驟3～5保證了航班按照所規(guī)劃路徑滑行時(shí)能滿足相關(guān)約束.

2.3

選擇算子與遺傳算子

2.3.1選擇算子

2.3.2

交叉算子

2.3.3

變異算子

由于采用變遷激發(fā)序列進(jìn)行染色體編碼，若采取隨機(jī)改變某一基因位變遷進(jìn)行變異，則極有可能產(chǎn)生不滿足可激發(fā)約束的解.以往采取兩種方法解決該問題：第1種方法是隨機(jī)改變?nèi)旧w，當(dāng)生成了不滿足約束的解時(shí)再進(jìn)行改正；第2種方法是在進(jìn)行變異時(shí)保證不產(chǎn)生不可行解[16].

3

仿真試驗(yàn)

3.1

仿真試驗(yàn)設(shè)計(jì)

以首都國際機(jī)場為研究對象，采集T3航站樓東側(cè)飛行區(qū)某日實(shí)際運(yùn)行數(shù)據(jù)，為所有進(jìn)離港航班規(guī)劃初始滑行路徑集.該部分飛行區(qū)的場面交通系統(tǒng)結(jié)構(gòu)如圖6所示，采用北向運(yùn)行模式（使用01號跑道），且假設(shè)所有離港航班均使用全跑道起飛，即從跑道等待區(qū)Q0處（圖中方框所示區(qū)域）進(jìn)入跑道起飛，進(jìn)港航班從快速脫離道Q5、Q6、Q7脫離的比例為0.1∶0.6∶0.3.作為對比，采用文獻(xiàn)[12]的方法為圖6所示飛行區(qū)建立對應(yīng)的節(jié)點(diǎn)-路段類有向圖模型，并采用基于遺傳算法的路徑規(guī)劃方法為航班規(guī)劃滑行路徑.

文獻(xiàn)[12]采取的優(yōu)化目標(biāo)是所有航班滑行的總里程最短，將其修改為與本文算法相同的優(yōu)化目標(biāo)，即滑行時(shí)間較短的s條滑行路徑（設(shè)s=3）.對比的目的是：

（1） 檢驗(yàn)用本文所建場面模型進(jìn)行路徑規(guī)劃是否比節(jié)點(diǎn)-路段類模型能更好地遵循管制規(guī)則；

（2） 檢驗(yàn)本文初始路徑規(guī)劃算法的效率和有效性.

計(jì)算環(huán)境CPU為Interl（R） Pentium Dual 2.2 GHz，內(nèi)存為4 GB.

具體實(shí)施過程為：在基于Anylogic的場面運(yùn)行仿真平臺上建立對應(yīng)的場面ETPPN模型，然后解析得到該模型對應(yīng)的關(guān)聯(lián)矩陣并導(dǎo)入MATLAB2008a中，采用Sheffield大學(xué)的遺傳算法工具箱GATBX求解滑行路徑.在求解過程中，MATLAB可直接調(diào)用Anylogic存儲的相關(guān)庫所屬性數(shù)據(jù)庫，并采用遺傳算法工具箱GATBX進(jìn)行求解.文獻(xiàn)[12]中算法的實(shí)現(xiàn)直接用MATLAB的遺傳算法工具箱GATBX完成.

3.2

仿真試驗(yàn)結(jié)果及分析

為了給每個(gè)航班的進(jìn)離港滑行規(guī)劃s

個(gè)滑行時(shí)間較短的初始滑行路徑，需要設(shè)置合理的遺傳算法參數(shù).但目前在遺傳算法參數(shù)設(shè)定方面缺乏通用理論，一般根據(jù)問題難易程度和染色體編碼形式，由經(jīng)驗(yàn)和反復(fù)試湊來設(shè)定參數(shù)值.

用上述參數(shù)為離港航班SK996（所在機(jī)位511）規(guī)劃初始滑行路徑集（包含3條路徑）.由于遺傳算法具有一定的隨機(jī)性，可進(jìn)行多次試驗(yàn)，每次試驗(yàn)得到的最短滑行時(shí)間均為246 s，因此認(rèn)為對應(yīng)的滑行路徑為最短滑行路徑.

圖8為在1次隨機(jī)試驗(yàn)中不同遺傳代數(shù)所得路徑集的最短滑行時(shí)間和平均滑行時(shí)間變化曲線.由圖8可以看出，每次優(yōu)化均能獲得最短滑行路徑，且隨著進(jìn)化代數(shù)的增加，平均滑行時(shí)間越來越接近最短滑行時(shí)間，表明算法收斂性良好.

最終為該航班確定的初始滑行路徑集如表3所示.對每條路徑進(jìn)行分析可知，在優(yōu)化場面資源使用的同時(shí)，滿足了各類場面運(yùn)行管制規(guī)則約束.

采用文獻(xiàn)[12]的遺傳算法為該航班規(guī)劃初始滑行路徑集，將求出的前3條較短滑行路徑參照圖6轉(zhuǎn)化為對應(yīng)的節(jié)點(diǎn)形式，如表4所示.

由表4可見，路徑1和路徑2分別在滑行道K5和K4上未遵循該路段的運(yùn)行方向約束，這與該算法設(shè)計(jì)僅考慮避免航空器之間的滑行沖突約束但未充分考慮其它約束有關(guān).可見，在節(jié)點(diǎn)-路段類模型中，模型本身對管制規(guī)則約束的描述能力有限，僅在算法實(shí)現(xiàn)過程中考慮各類約束，可能影響路徑規(guī)劃結(jié)果的有效性.

此外，文獻(xiàn)[12]中設(shè)定的航空器具有單一固定滑行速度5 m/s，路徑3的滑行時(shí)間為467 s（表4），用本文方法路徑3的滑行時(shí)間為260 s（表3），二者相差較大.可見，考慮航空器滑行速度的調(diào)整特性，可更精確地計(jì)算航空器的滑行時(shí)間.

4

結(jié)束語

提出了一種面向A-SMGCS的航空器場面滑行初始路徑規(guī)劃方法，該方法具有以下特點(diǎn)：

（1） 定義一種擴(kuò)展賦時(shí)庫所Petri網(wǎng)（ETPPN），可對航空器場面滑行過程進(jìn)行建模，該模型充分體現(xiàn)了管制規(guī)則約束；

（2） 考慮航空器場面滑行速度調(diào)整特性，使規(guī)劃結(jié)果更接近實(shí)際運(yùn)行需要；

（3） 采用場面運(yùn)行ETPPN模型中的變遷激發(fā)序列進(jìn)行GA染色體編碼，結(jié)合場面滑行特征給出交叉與變異設(shè)計(jì)，改變以往研究中對問題空間（場面拓?fù)浣Y(jié)構(gòu)）的直接處理，算法的通用性更好.

在求解初始滑行路徑時(shí)僅以滑行時(shí)間最短作為優(yōu)化目標(biāo)，今后需要考慮更多的優(yōu)化目標(biāo)，例如航空器加減速次數(shù)、轉(zhuǎn)彎次數(shù)等，并與其它路徑規(guī)劃方法進(jìn)行比較.

參考文獻(xiàn)：

[1]International Civil Aviation Organization （ICAO）. Doc.9830-AN/452， Advanced surface movement guidance and control systems （A-SMGCS） manual[S]. 2004.

[2]湯新民，王玉婷，韓松臣. 基于DEDS的A-SMGCS航空器動態(tài)滑行路徑規(guī)劃研究[J]. 系統(tǒng)工程與電子技術(shù)，2010，32（12）： 2669-2675.

TANG Xinmin， WANG Yuting， HAN Songchen. Aircraft dynamic taxiway routes planning for A-SMGCS based on DEDS[J]. Systems Engineering and Electronics， 2010， 32（12）： 2669-2675.

[3]朱新平，湯新民，韓松臣. 基于EHPN的A-SMGCS機(jī)場滑行道運(yùn)行控制建模[J]. 交通運(yùn)輸工程學(xué)報(bào)，2010，10（4）： 103-108.

ZHU Xinping， TANG Xinmin， HAN Songchen. EHPN-based modeling of airport taxiway operation control in A-SMGCS[J]. Journal of Traffic and Transportation Engineering， 2010， 10（4）： 103-108.

[4]朱新平，湯新民，韓松臣. 基于DES監(jiān)控理論的滑行道對頭沖突控制策略[J]. 西南交通大學(xué)學(xué)報(bào)，2011，46（4）： 664-670.

ZHU Xinping， TANG Xinmin， HAN Songchen. Avoidance strategy for head-on conflict on taxiway based on supervisory control theory of DES[J]. Journal of Southwest Jiaotong University， 2011， 46（4）： 664-670.

[5]黃圣國，孫同江，呂兵. 運(yùn)輸網(wǎng)絡(luò)的最短有向路Petri網(wǎng)仿真算法[J]. 南京航空航天大學(xué)學(xué)報(bào)，2002，34（2）： 121-125.

HUANG Shengguo， SUN Tongjiang， LU Bing. Petri net simulation arithmetic of the shortest directional path in transportation net[J]. Journal of Nanjing University of Aeronautics and Astronautics， 2002， 34（2）： 121-125.

[6]張威，謝曉妤，劉曄. 基于Petri網(wǎng)的機(jī)場場面路徑規(guī)劃探討[J]. 現(xiàn)代電子工程，2007，4（1）： 59-61.

ZHANG Wei， XIE Xiaoyu， LIU Ye. Petri-net based airport surface routes planning[J]. Modern Electronic Engineering， 2007， 4（1）： 59-61.

[7]GARCIA J， BERLANGAA A. Optimization of airport ground operations integrating genetic and dynamic flow management algorithms[J]. AI Communications， 2005， 18（2）： 143-164.

[8]KEITH G， RICHARDS A， SHARMA S. Optimization of taxiway routing and runway scheduling[C]∥Proc. of AIAA Guidance， Navigation， and Control Conference and Exhibit. Honolulu： [s. n.]， 2008： 1-11.

[9]MARN G. Airport management： taxi planning[J]. Annals of Operations Research， 2006， 143（1）： 191-202.

[10]王化冰. 一種基于同步合成Petri網(wǎng)的FMS建模方法[J]. 系統(tǒng)工程理論與實(shí)踐，2001，21（2）： 35-42.

WANG Huabing. A Petri net synchronous synthesis method for modeling flexible manufacturing systems[J]. System Engineering： Theory and Practice， 2001， 21（2）： 35-42.

[11]GEN M， CHENG R W. Genetic algorithms and engineering optimization[M]. New York： John Wiley and Sons， 2000： 297-340.

[12]劉長有，叢曉東. 基于遺傳算法的飛機(jī)滑行路徑優(yōu)化[J]. 交通信息與安全，2009，27（3）： 6-8.

LIU Changyou， CONG Xiaodong. Taxing optimization for aircraft based on genetic algorithm[J]. Transportation Information and Safety， 2009， 27（3）： 6-8.

[13]劉兆明，葛宏偉，錢鋒. 基于遺傳算法的機(jī)場調(diào)度優(yōu)化算法[J]. 華東理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2008，34（3）： 392-398.

LIU Zhaoming， GE Hongwei， QIAN Feng. Airport scheduling optimization algorithm based on genetic algorithm[J]. Journal of East China University of Science and Technology： Nature Science Edition， 2008， 34（3）： 392-398.

[14]GOTTELAND J， DURAND N， ALLIOT J M， et al. Aircraft ground traffic optimization[C]∥Proc. of the Genetic and Evolutionary Computation Conference. San Francisco： IEEE Press， 2001： 1-9.

[15]GOTTELAND J， DURAND N. Genetic algorithms applied to airport ground traffic optimization[C]∥Proc. of the 2003 Congress on Evolutionary Computation. Canberra： IEEE Press， 2003： 544-551.

篇2

關(guān)鍵詞：最短路徑；動態(tài)規(guī)劃；C 語言編程

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2013）09-2191-03

1 概述

數(shù)學(xué)源于生活，又服務(wù)于生活.它是一門研究現(xiàn)實(shí)世界中的數(shù)量關(guān)系與空間形式的學(xué)科.當(dāng)今社會，隨著物質(zhì)水平的不斷提高，生活需求的不斷擴(kuò)大，自然資源的不斷開發(fā)利用.像天然氣管道鋪設(shè)問題，廠區(qū)布局問題，旅行費(fèi)用最小問題等都已成為我們平時(shí)經(jīng)濟(jì)生活中的普遍問題.它們其實(shí)都可以化歸為最短路線問題，而最短路問題實(shí)質(zhì)上是一個(gè)組合優(yōu)化問題[1]。

動態(tài)規(guī)劃方法主要是研究與解決多階段決策過程的最優(yōu)化問題，它將求解分成多階段進(jìn)行，不但求出了全過程的解，還能求出后部子過程的一組解，在求解一些生活實(shí)際問題時(shí)，更顯其優(yōu)越性。為了快速、簡單的計(jì)算最短路徑，節(jié)約運(yùn)輸時(shí)間與成本，該文利用動態(tài)規(guī)劃的思想編寫了C語言程序，解決物流運(yùn)輸過程中多地點(diǎn)的最短路徑的選擇問題。

2 最短路徑問題

2.1 最短路徑問題算法的基本思想

在求解網(wǎng)絡(luò)圖上節(jié)點(diǎn)間最短路徑的方法中，目前國內(nèi)外一致公認(rèn)的較好算法有迪杰斯特拉（Dijkstra）及弗羅伊德（Floyd）算法。這兩種算法中，網(wǎng)絡(luò)被抽象為一個(gè)圖論中定義的有向或無向圖，并利用圖的節(jié)點(diǎn)鄰接矩陣記錄點(diǎn)間的關(guān)聯(lián)信息。在進(jìn)行圖的遍歷以搜索最短路徑時(shí)，以該矩陣為基礎(chǔ)不斷進(jìn)行目標(biāo)值的最小性判別，直到獲得最后的優(yōu)化路徑[2]。

Dijkstra算法是圖論中確定最短路的基本方法，也是其它算法的基礎(chǔ)。為了求出賦權(quán)圖中任意兩結(jié)點(diǎn)之間的最短路徑，通常采用兩種方法。一種方法是每次以一個(gè)結(jié)點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行Dijkstra算法n次。另一種方法是由Floyd于1962年提出的Floyd算法，其時(shí)間復(fù)雜度為[On3]，雖然與重復(fù)執(zhí)行Dijkstra算法n次的時(shí)間復(fù)雜度相同，但其形式上略為簡單，且實(shí)際運(yùn)算效果要好于前者。

2.2 最短路徑問題算法的基本步驟[3]

這樣經(jīng)過有限次迭代則可以求出[v1]到[vn]的最短路線。

（2）Floyd算法的基本步驟

（3）動態(tài)規(guī)劃算法基本步驟

我們將具有明顯的階段劃分和狀態(tài)轉(zhuǎn)移方程的規(guī)劃稱為動態(tài)規(guī)劃[1]。在解決多個(gè)階段決策問題時(shí)采用動態(tài)規(guī)劃法是一個(gè)很有效的措施，同時(shí)易于實(shí)現(xiàn)。

根據(jù)動態(tài)規(guī)劃的基本概念，可以得到動態(tài)規(guī)劃的基本步驟：1）確定問題的決策對象。2）對決策過程劃分階段。3）對各階段確定狀態(tài)變量。4）根據(jù)狀態(tài)變量確定費(fèi)用函數(shù)和目標(biāo)函數(shù)。5）建立各階段狀態(tài)變量的轉(zhuǎn)移過程，確定狀態(tài)轉(zhuǎn)移方程。

根據(jù)動態(tài)規(guī)劃的基本模型，確定用動態(tài)規(guī)劃方法解題的基本思路，是將一個(gè)[n]階段決策問題轉(zhuǎn)化為一次求解[n]個(gè)具有遞推關(guān)系的單階段的決策問題，以此來簡化計(jì)算過程.其一般步驟如下：

用于衡量所選決策優(yōu)劣的函數(shù)稱為指標(biāo)函數(shù).指標(biāo)函數(shù)有有階段的指標(biāo)函數(shù)和過程的指標(biāo)函數(shù)之分.階段的指標(biāo)函數(shù)是對應(yīng)某一階段狀態(tài)和從該狀態(tài)出發(fā)的一個(gè)階段的某種效益度量，用[vkxk，uk]表示。在本文里用[dkxk，uk]來表示某一階段的決策的最短路徑。過程的指標(biāo)函數(shù)是指從狀態(tài)[xn（k=1，2，...，n）]出發(fā)至過程最終，當(dāng)采取某種子策略時(shí)，按預(yù)定的標(biāo)準(zhǔn)得到的效益值。這個(gè)值既與[xk]本身的狀態(tài)值有關(guān)，又與[xk]以后所選取的策略有關(guān)，它是兩者的函數(shù)值，記作[dk，nxk，uk，xk+1，uk+1，…xn，un]。過程的指標(biāo)函數(shù)又是它所包含的各階段指標(biāo)函數(shù)的函數(shù)。本文研究的過程的的指標(biāo)函數(shù)是其各階段指標(biāo)函數(shù)的和的形式.當(dāng)[xk]的值確定后，指標(biāo)函數(shù)的值就只同k階段起的子策略有關(guān)。對應(yīng)于從狀態(tài)[xk]出發(fā)的最優(yōu)子策略的效益值記作[fkxk]，于是在最短路問題中，有[fkxk=mindk，n]。動態(tài)規(guī)劃求解最短路徑程序流程圖如圖2所示。

3 最短路徑態(tài)規(guī)劃實(shí)際應(yīng)用舉例

設(shè)某物流配送網(wǎng)絡(luò)圖由12個(gè)配送點(diǎn)組成，點(diǎn)1為配送中心起點(diǎn)，12為終點(diǎn)，試求自終點(diǎn)到圖中任何配送點(diǎn)的最短距離。圖中相鄰兩點(diǎn)的連線上標(biāo)有兩點(diǎn)間的距離[4]。

首先用動態(tài)規(guī)劃法來討論圖3的最短路徑，由圖可知：

1）集合[ξ4]中有點(diǎn)9、10、11，它們在一步之內(nèi)可到達(dá)點(diǎn)12；

2）集合[ξ3]中有點(diǎn)6，7，8，它們不超過兩步就可達(dá)到點(diǎn)12；

3）集合[ξ2]中包括點(diǎn) 2、3、4、5，不超過三步就可到達(dá)點(diǎn)12；

4）集合[ξ1]中包括點(diǎn)1，不超過四步可到達(dá)點(diǎn)12；

按照動態(tài)規(guī)劃法類推，得到最優(yōu)路徑長為16，徑路通過點(diǎn)為1，2，7，10，12和1，3，6，10，12。

根據(jù)動態(tài)規(guī)劃算法編寫C語言計(jì)算程序[5] [6]，計(jì)算得到實(shí)驗(yàn)結(jié)果如下圖4所示：

由圖4可以看出程序得到的結(jié)果與本文推出的結(jié)果一樣。證明了本文編寫的C語言程序是正確的。

4 結(jié)束語

綜上所述，用動態(tài)規(guī)劃解決多階段決策問題效率高，而且思路清晰簡便，同時(shí)易于實(shí)現(xiàn).我們可以看到，動態(tài)規(guī)劃方法的應(yīng)用很廣泛，已成功解決了許多實(shí)際問題，具有一定的實(shí)用性。此種算法我們用動態(tài)規(guī)劃思想來編程，并解決相應(yīng)的問題，其在 VC 環(huán)境下實(shí)現(xiàn)，能方便快速的計(jì)算出到達(dá)目的地的最短距離及路徑，節(jié)省更多的運(yùn)輸時(shí)間與成本。不過，該文只考慮了動態(tài)規(guī)劃算法在生活中的簡單運(yùn)用，在實(shí)際生活中可能存在多個(gè)目的地或者更復(fù)雜的情況.因此我們可以考慮將其進(jìn)行改進(jìn)或者結(jié)合啟發(fā)式算法，使之更好的運(yùn)用在實(shí)際生活中，這有待于以后的繼續(xù)研究。

參考文獻(xiàn)：

[1] 杜彥娟.利用動態(tài)規(guī)劃數(shù)學(xué)模型求解最短路徑[J].煤炭技術(shù)，2005（1）：94-95.

篇3

關(guān)鍵字：最優(yōu)路徑選擇；A-Star算法；貪婪算法；模擬仿真

中圖分類號：TP301.6 文獻(xiàn)標(biāo)識碼：A DOI：10.3969/j.issn.1003-6970.2013.06.012

0 前言

物流與國民經(jīng)濟(jì)及生活的諸多領(lǐng)域密切相關(guān)，越來越多得到重視，甚至被看作是企業(yè)“第三利潤的源泉”，而在物流成本方面，運(yùn)輸費(fèi)用占大約50% ，比重最大[1]。因此，物流配送中最優(yōu)路徑選擇的研究具有巨大的經(jīng)濟(jì)意義。物流配送中的最優(yōu)路徑選擇問題的研究和應(yīng)用都相當(dāng)廣泛，近幾十年，國內(nèi)外均有大量企業(yè)機(jī)構(gòu)、學(xué)者對該問題進(jìn)行了大量而深入的研究，取得豐碩的學(xué)術(shù)成果。如1953年，Bodin，Golden 等人便撰文綜述了該問題的有關(guān)研究進(jìn)展情況，列舉了幾百余篇相關(guān)文獻(xiàn)，這些文獻(xiàn)成為了早期車輛路徑問題研究資料，隨后隨著該問題不斷研究深入，約束模型及條件不斷變化，車輛路徑問題研究的最新進(jìn)展可見Alt- inkerner 和 Oavish，Laporte，Salhi 等人的綜述性文章[2]。圍繞該問題的解決也極大推動了計(jì)算機(jī)學(xué)科的發(fā)展，不斷有新的模型和算法推出。針對物流配送車輛路徑優(yōu)化問題的求解方法很多，根據(jù)算法原理的不同大致可分為兩大類：精確算法和智能式啟發(fā)算法。精確算法是指可以車輛路徑問題的數(shù)學(xué)模型可求出其最優(yōu)解算法，但由于算法存在諸多缺陷，所以在實(shí)際中應(yīng)用并不廣泛。目前，啟發(fā)式算法是解決物流配送中最優(yōu)路徑選擇的主要方法和主向[3]。近年來，隨著科學(xué)的發(fā)展，一些新的啟發(fā)式方法被用在求解物流路徑選擇及優(yōu)化問題上，可以通過使用啟發(fā)式方法獲得較快的收斂速度和較高質(zhì)量的全局解，常用的算法有模擬退火算法、GA 算法等[4]。A*算法是人工智能中一種典型的啟發(fā)式搜索算法，被廣泛應(yīng)用于最優(yōu)路徑求解和一些策略設(shè)計(jì)的問題中[5、6]。本文結(jié)合貪婪算法的思想，深入研究A-Star（A*）算法，在QT Creator平臺上，采用Visual C++編程對物流配送問題進(jìn)行模擬仿真，同時(shí)考慮最短時(shí)間和最短路徑兩個(gè)方面，以此來解決物流配送中最優(yōu)路徑選擇的問題，達(dá)到物流配送最優(yōu)線路規(guī)劃的目的。

1 需求分析

1.1 總體框架

在物流配送時(shí)，物流車裝載當(dāng)日需要配送的貨品從倉庫出發(fā)，按照事先規(guī)劃好的最優(yōu)配送路徑為每一個(gè)客戶進(jìn)行配送，最后返回倉庫。這就涉及在配送時(shí)配送路線的選擇問題，而在配送之前，IT系統(tǒng)需要根據(jù)客戶的配送地址間線路間距和經(jīng)驗(yàn)路況分析計(jì)算出一條最優(yōu)配送路徑。并且在配送過程中，如果某路段發(fā)生堵車狀況，需要?jiǎng)討B(tài)調(diào)整配送路線，以達(dá)到最優(yōu)配送的目的。為此，在QT Creator平臺上，以面向?qū)ο蟮脑O(shè)計(jì)方式來開發(fā)最優(yōu)物流配送的功能軟件。通過再現(xiàn)交通運(yùn)輸環(huán)境，模擬物流運(yùn)輸中的突發(fā)事件，優(yōu)化物流配送的路線，分別根據(jù)需求，設(shè)計(jì)出最短路徑和最少時(shí)間兩種配送方式，并通過二維動畫的效果顯示出來。通過此軟件呆模擬解決物流配送中各種情況，從而降低運(yùn)輸成本。設(shè)計(jì)本軟件的總體思路如圖1所示。

1.2 功能設(shè)計(jì)

設(shè)計(jì)的軟件從功能上來說，主要包括以下幾點(diǎn)：

（1）載入一張已有地圖（*.map的文件）或生成一張空白地圖。用戶可以在這張空白地圖上操作，通過障礙物的增刪來設(shè)置城市的道路。

（2）道路突發(fā)事件設(shè)置。

a.用戶可以根據(jù)實(shí)際情況或主觀意愿對地圖進(jìn)行規(guī)劃。在地圖中添加障礙物，設(shè)置道路前方的暫時(shí)封閉或者道路施工等未知路況。

b.也可以模擬城市人流量大的地方，通過在地圖上，設(shè)置易堵車而導(dǎo)致前行速度下降的未知路況。

（3）設(shè)置倉庫及客戶點(diǎn)。

a.隨機(jī)生成倉庫及客戶點(diǎn)。在地圖中，用戶可隨機(jī)生成若干個(gè)客戶點(diǎn)和倉庫點(diǎn)。

b.指定生成倉庫及客戶點(diǎn)。在已生成或者模擬的地圖上，根據(jù)用戶的不同需求，可在地圖上任意位置生成客戶點(diǎn)和倉庫點(diǎn)。

c.可以對倉庫及客戶點(diǎn)進(jìn)行增刪。

（4）計(jì)算路徑及優(yōu)化。

a.根據(jù)用戶之前模擬的各種情況，計(jì)算其最短路徑。根據(jù)用戶載入或者自己規(guī)劃的地圖，模擬計(jì)算出最短路徑，在界面的左上角顯示其時(shí)間，并在地圖上顯示其路徑。

b.根據(jù)用戶之前模擬的各種情況，計(jì)算其最短時(shí)間。根據(jù)用戶載入或者自己規(guī)劃的地圖，模擬計(jì)算出最短時(shí)間，在界面的左上角顯示其時(shí)間，并在地圖上顯示其對應(yīng)路徑。

軟件的大致功能如下圖2所示。

圖2 功能模塊圖

2 算法描述

2.1 貪婪算法

貪婪算法（Greedy algorithm）又叫登山法，它的根本思想是逐步到達(dá)山頂，即逐步獲得最優(yōu)解，是解決最優(yōu)化問題時(shí)的一種簡單但適用范圍有限的策略[7]。

貪婪算法是基于鄰域的搜索技術(shù)，它在計(jì)算過程中逐步構(gòu)造最優(yōu)解[8]。在構(gòu)造解的過程中，每一步常以當(dāng)前情況為基礎(chǔ)根據(jù)某個(gè)優(yōu)化測度（greedy criterion，貪婪準(zhǔn)則，也稱貪婪因子）作最優(yōu)選擇，而不考慮各種可能的整體情況，選擇一旦做出就不再更改，這省去了為找最優(yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間。它采用自頂向下，以迭代的方法做出相繼的貪心選擇，每做一次貪心選擇就將所求問題簡化為一個(gè)規(guī)模更小的子問題。通過每一步貪心選擇，可得到問題的一個(gè)最優(yōu)解，雖然每一步上都要保證能獲得局部最優(yōu)解，但由此產(chǎn)生的全局解有時(shí)不一定是最優(yōu)的，一般情況下只是近似最優(yōu)解[9]。雖然貪婪法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當(dāng)廣泛的求最優(yōu)解問題來說，它是一種最直接的算法設(shè)計(jì)技術(shù)，通過一系列局部最優(yōu)的選擇，即貪婪選擇可以產(chǎn)生整體最優(yōu)解[10]。

對于一個(gè)給定的問題，往往可能有好幾種量度標(biāo)準(zhǔn)。初看起來，這些量度標(biāo)準(zhǔn)似乎都是可取的，但實(shí)際上，用其中的大多數(shù)量度標(biāo)準(zhǔn)作貪婪處理所得到該量度意義下的最優(yōu)解并不是問題的最優(yōu)解，而是次優(yōu)解。因此，選擇能產(chǎn)生問題最優(yōu)解的最優(yōu)量度標(biāo)準(zhǔn)是使用貪婪算法的核心。一般情況下，要選出最優(yōu)量度標(biāo)準(zhǔn)并不是一件容易的事，但對某問題能選擇出最優(yōu)量度標(biāo)準(zhǔn)后，用貪婪算法求解則特別有效。最優(yōu)解可以通過一系列局部最優(yōu)的選擇（貪婪選擇）來達(dá)到。根據(jù)當(dāng)前狀態(tài)做出在當(dāng)前看來是最好的選擇，即局部最優(yōu)解選擇，然后再去解出這個(gè)選擇后產(chǎn)生的相應(yīng)的子問題。每做一次貪婪選擇就將所求問題簡化為一個(gè)規(guī)模更小的子問題，最終可得到問題的一個(gè)整體最優(yōu)解。它是一種改進(jìn)了的分級處理方法。

2.2 A-Star算法

A*算法是人工智能中一種典型的啟發(fā)式搜索算法，它是一種靜態(tài)路網(wǎng)中求解最短路最優(yōu)算法，其公式可表示為：

（1）

其中，是從初始點(diǎn)經(jīng)由節(jié)點(diǎn)到目標(biāo)點(diǎn)的估價(jià)函數(shù)；是在狀態(tài)空間中從初始節(jié)點(diǎn)到節(jié)點(diǎn)的實(shí)際代價(jià)；是從到目標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)代價(jià)[11、12]。

在A*算法中，找到最短路徑（最優(yōu)解的）的關(guān)鍵在于估價(jià)函數(shù)的選取。當(dāng)估價(jià)值到目標(biāo)節(jié)點(diǎn)的距離實(shí)際值時(shí)，搜索的點(diǎn)數(shù)多，搜索范圍大，效率低，但能得到最優(yōu)解；當(dāng)估價(jià)值到目標(biāo)節(jié)點(diǎn)的距離實(shí)際值時(shí)，搜索的點(diǎn)數(shù)少，搜索范圍小，效率高，但不能保證得到最優(yōu)解[13、14]。

A*算法的難點(diǎn)在于建立一個(gè)合適的估價(jià)函數(shù)，估價(jià)函數(shù)構(gòu)造得越準(zhǔn)確，則A*算法搜索的時(shí)間就越短[15]。A*算法的估價(jià)函數(shù)可表示為：

（2）

這里，是估價(jià)函數(shù)，是起點(diǎn)到節(jié)點(diǎn)的最短路徑值，是到目標(biāo)的最短路徑的啟發(fā)值。由于這個(gè)其實(shí)是無法預(yù)先知道的，所以我們用前面的估價(jià)函數(shù)做近似。當(dāng)時(shí)，可以代替（大多數(shù)情況下都是滿足的，可以不用考慮），但只有在時(shí)，才能代替?？梢宰C明，應(yīng)用這樣的估價(jià)函數(shù)能有效地找到最短路徑。

本文綜合貪婪算法和A*算法的思想來求解決物流配送中最優(yōu)路徑選擇的問題。圖3為綜合算法的流程圖。

3 實(shí)驗(yàn)仿真設(shè)計(jì)

3.1 軟件概述

開發(fā)的軟件要具有實(shí)用性，這就是說，能給企業(yè)帶來效益，這就包了兩方面的內(nèi)容：企業(yè)能獲得的利潤和客戶的滿意程度。也就是說采用所建立的模型要設(shè)計(jì)出合理的物流配送路線，保證在較短的路程或時(shí)間內(nèi)遍歷所有的節(jié)點(diǎn)，從而保證貨物按時(shí)送到。

從算法角度來看，為了保證算法的有效性和高效性，結(jié)合軟件的功能，則該軟件的設(shè)計(jì)目標(biāo)[16]為：①路徑最短或時(shí)間最短， ②滿足實(shí)際中遍歷節(jié)點(diǎn)的要求， ③算法高效性， ④軟件的普度適用性。

軟件操作流程具體步驟如下：

第一步.用戶載入一張已有地圖或生成一張空白地圖。

第二步.設(shè)置相關(guān)參數(shù)及約束條件。

第三步.顯示計(jì)算結(jié)果和最優(yōu)路徑。

該軟件可運(yùn)行于Windows 7操作系統(tǒng)，主要包括3個(gè)部分：地圖文件的讀取部分、算法部分和用戶界面部分。

3.2 軟件模擬實(shí)現(xiàn)

1.初始化

根據(jù)軟件的需求分析，本軟件初始產(chǎn)生一個(gè)空白的二維平面圖，在該模塊用戶可以根據(jù)實(shí)際情況模擬出實(shí)際路況，提供兩種方式來實(shí)現(xiàn)該功能：

（1）通過點(diǎn)擊工具欄上面的初始化按鈕自動初始化。

（2）通過鼠標(biāo)右鍵選擇初始化選項(xiàng)。

圖4 系統(tǒng)初始化界面

2.道路的參數(shù)設(shè)置

在視圖界面中，用戶可以點(diǎn)擊鼠標(biāo)右鍵，選擇生成障礙物或刪除障礙物來模擬現(xiàn)實(shí)生活中城市道路可能發(fā)生的各種情況，如：

（1）用戶可以根據(jù)實(shí)際情況，點(diǎn)擊鼠標(biāo)右鍵，在出現(xiàn)的下拉菜單中，選中添加障礙物，設(shè)置道路前方的暫時(shí)封閉或者道路施工等未知路況。

（2）也可以在地圖上，點(diǎn)擊鼠標(biāo)右鍵來設(shè)置易堵車而導(dǎo)致前行速度下降的未知路況。

在地圖中淺黃色的區(qū)域是模擬人流量大的鬧市區(qū)。深褐色方塊模擬障礙物。

圖5 道路模擬圖

3.倉庫點(diǎn)及客戶點(diǎn)的生成

客戶點(diǎn)和倉庫點(diǎn)的生成包括兩種情況：

（1）隨機(jī)生成客戶點(diǎn)和倉庫點(diǎn)。在視圖界面中，通過頂端的輸入框，輸入生成客戶點(diǎn)或倉庫點(diǎn)的個(gè)數(shù)，點(diǎn)擊生成客戶點(diǎn)或倉庫點(diǎn)按鈕來隨機(jī)生成客戶點(diǎn)或倉庫點(diǎn)。

（2）在指定位置生成客戶點(diǎn)和倉庫點(diǎn)。在已生成或者模擬的地圖上，根據(jù)用戶不同的需求，在地圖指定位置生成客戶點(diǎn)和倉庫點(diǎn)。

在如圖5的道路設(shè)計(jì)下，在地圖上隨機(jī)添加了10個(gè)客戶點(diǎn)和1個(gè)倉庫點(diǎn)，如圖6所示。

圖6 場景界面圖

4.路徑最短和時(shí)間最短的配送路徑

根據(jù)圖6所設(shè)計(jì)的場景，通過貪婪算法和A*算法，分別計(jì)算出路徑最短和時(shí)間最短的配送路徑，并在地圖上顯示其路徑。圖7依據(jù)最短路徑實(shí)現(xiàn)物流配送的最優(yōu)方案，主要從距離這個(gè)方面進(jìn)行考慮；圖8根據(jù)最短時(shí)間實(shí)現(xiàn)物流配送的最優(yōu)方案，主要考慮的是在道路有突發(fā)狀況發(fā)生時(shí)物流配送的時(shí)間最少。

圖7 路徑最短的配送路徑

圖8 時(shí)間最短的配送路徑

4 認(rèn)識與結(jié)論

通過對物流配送中的實(shí)際問題進(jìn)行模擬研究，在QT Creator平臺上采用Visual C++編程開發(fā)出針對物流配送中最優(yōu)路徑選擇問題的軟件，從最短時(shí)間和最短路程兩方面考慮，為物流配送公司提供可靠有效的參考信息，使配送方案符合實(shí)際情況。同時(shí)，深入研究了貪婪算法和A*算法，從算法的角度對物流配送中的時(shí)間和路程進(jìn)行分析，設(shè)計(jì)實(shí)現(xiàn)了物流配送中最優(yōu)數(shù)學(xué)模型，以期達(dá)到最優(yōu)路徑的目的。通過本研究的結(jié)果來看，開發(fā)的模擬軟件能解決物流運(yùn)送過程中的時(shí)間、路徑等實(shí)際問題，同時(shí)實(shí)現(xiàn)了二維圖形的可視化，更加直觀地體現(xiàn)了物流配送中存在的問題和解決方式，對物流配送企業(yè)提高運(yùn)營效率、降低運(yùn)營成本等具有重要意義。

參考文獻(xiàn)

[1]黃中鼎. 現(xiàn)代物流管理學(xué)[M]. 上海： 上海財(cái)經(jīng)大學(xué)出版社， 2004， 1-37.

[2]謝秉磊， 郭耀煌， 郭強(qiáng). 動態(tài)車輛路徑問題：現(xiàn)狀與展望[J]. 系統(tǒng)工程理論方法應(yīng)用， 2002， 11（2）： 116-120.

[3]鄒挺. 基于蟻群和人工魚群混合群智能算法在物流配送路徑優(yōu)化問題中的應(yīng)用研究[D]. 蘇州： 蘇州大學(xué)， 2011， 3-7.

[4]吳云志， 樂毅， 王超， 等. 蟻群算法在物流路徑優(yōu)化中的應(yīng)用及仿真[J]. 合肥工業(yè)大學(xué)學(xué)報(bào)（ 自然科學(xué)版）， 2009， 32（2）：211-214.

[5]王海梅， 周獻(xiàn)中. 直線優(yōu)化A*算法在最短路徑問題中的高效實(shí)現(xiàn)[A]. 全國第計(jì)算機(jī)技術(shù)與應(yīng)用（CACIS）學(xué)術(shù)會議論文集（下冊）[C]， 2008， 932-936.

[6]陳和平， 張前哨. A*算法在游戲地圖尋徑中的應(yīng)用與實(shí)現(xiàn)[J]. 計(jì)算機(jī)應(yīng)用與軟件， 2005， 22（12）：94-96.

[7]晏杰. Matlab 中貪婪算法求解背包問題的研究與應(yīng)用[J]. 赤峰學(xué)院學(xué)報(bào)（自然科學(xué)版）， 2012， 28（9）：23-24.

[8]劉紀(jì)岸， 周康渠， 寧李俊， 等. 基于貪婪算法的摩托車生產(chǎn)物流配送規(guī)則優(yōu)化[J]. 制造業(yè)自動化， 2010， 32（5）：97-99.

[9]蔣建國， 李勇， 夏娜. 一種求解單任務(wù)Agent聯(lián)盟生成的貪婪算法[J]. 系統(tǒng)仿真學(xué)報(bào)， 2008， 20（8）：1961-1964.

[10]江朝勇， 陳子慶， 謝贊福. 基于優(yōu)先級貪婪算法的排課系統(tǒng)排研究與實(shí)現(xiàn)[J]. 信息技術(shù)， 2008， 24（7）：173-176.

[11]徐偉， 孫士兵. 基于A-Star算法警用地圖查詢系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J]. 信息安全與技術(shù)， 2011. 5-2：52-56.

[12]王敬東， 李佳. A*算法在地圖尋徑中的實(shí)用性優(yōu)化[J]. 電腦開發(fā)與應(yīng)用， 2007， 20（7）：24-25.

[13]（美）Stuart Russell，（美）Peter Norvig. 人工智能——一種現(xiàn)代方法[M]. 姜哲，譯. 北京：人民郵電出版社， 2004， 76-83.

[14]王文杰， 葉世偉. 人工智能原理與應(yīng)用[M]. 北京：人民郵電出版社， 2004， 115-121.

篇4

【關(guān)鍵詞】虛擬場景；路經(jīng)規(guī)劃；八叉樹；A*算法

中圖分類號：TP39文獻(xiàn)標(biāo)識碼A文章編號1006-0278（2013）06-172-01

一、引言

隨著虛擬現(xiàn)實(shí)技術(shù)的日益成熟，只有景色、建筑物等一般視景信息的虛擬場景已不能滿足人們的視覺需求，迫切需求一個(gè)有生命的對象引入到虛擬場景中，增加瀏覽者的沉浸感。虛擬場景中虛擬人的路徑規(guī)劃是虛擬現(xiàn)實(shí)研究中的一項(xiàng)關(guān)鍵技術(shù)。目前，研究者們已經(jīng)把研究的重心放在如何為虛擬人規(guī)劃出一條行走的最優(yōu)路徑，使虛擬人的路徑導(dǎo)航更具有真實(shí)感和可信度。

由于虛擬環(huán)境中的模型多由三角面網(wǎng)格組成，通過使用基于空間多層次劃分的八叉樹方法，充分發(fā)揮了其空間劃分的優(yōu)勢，加快了場景的渲染速度，減少了確定對象的處理時(shí)間以及存儲空間①。

文章采用八叉樹和A*算法相結(jié)合的方法，對路徑進(jìn)行規(guī)劃，并對A*算法做了改進(jìn)，以適應(yīng)八叉樹的存儲結(jié)構(gòu)。

二、密集型區(qū)域八叉樹劃分算法

八叉樹是由四叉樹推廣到三維空間而形成的一種三維柵格數(shù)據(jù)結(jié)構(gòu)，它作為一種場景組織方法，廣泛應(yīng)用于虛擬現(xiàn)實(shí)系統(tǒng)，可顯著減少對場景中多邊形進(jìn)行排序的時(shí)間。

由于傳統(tǒng)八叉樹對空間的劃分是均勻的，導(dǎo)致了最終生成一個(gè)結(jié)構(gòu)不平衡的八叉樹，從而增加整個(gè)八叉樹的存儲空間以及各結(jié)點(diǎn)的遍歷時(shí)間。文章采用了對傳統(tǒng)八叉樹算法進(jìn)行改進(jìn)，采用基于密集型區(qū)域八叉樹劃分方法。密集型區(qū)域八叉樹的網(wǎng)格劃分算法是對每一子空間重新建立最小包圍盒，這樣避免了在建立頂點(diǎn)樹時(shí)，由于該部分頂點(diǎn)在空間上分布不均勻而導(dǎo)致樹的深度的增加，進(jìn)而減少了存儲空間，加快了網(wǎng)格模型數(shù)據(jù)的讀取速度。另外，由于建立了頂點(diǎn)的最小包圍盒，在誤差較小時(shí)，只有空間距離比較近的頂點(diǎn)才會聚合在一起；而相距較遠(yuǎn)的頂點(diǎn)只有在深層次簡化時(shí)才會聚合，這些特點(diǎn)在一定程度上保證了簡化時(shí)網(wǎng)格模型的逼真度。

密集型區(qū)域八叉樹劃分方法的算法描述如下：

步驟1使用OBB包圍盒方法建立模型的最小包圍盒。

步驟2以包圍盒的X軸、Y軸、Z軸方向的中分面作為分割基準(zhǔn)，將包圍盒平均劃分為八個(gè)子包圍盒。

步驟3如果每個(gè)子空間內(nèi)存在物體的屬性不相同或未達(dá)到規(guī)定的限差，則重新從步驟1開始進(jìn)行劃分。否則，劃分結(jié)束，并對劃分后的每一個(gè)結(jié)點(diǎn)記錄下結(jié)點(diǎn)編號、劃分標(biāo)志、結(jié)點(diǎn)在頂點(diǎn)樹中的深度以及它所含的景物面片表的入口指針。

三、A*算法

A*算法是建立在典型的Dijkstra算法上的，是由Hart，Nilsson，Raphael等人首先提出的。該算法的創(chuàng)新之處在于選擇下一個(gè)被檢查的節(jié)點(diǎn)時(shí)引入了已知的全局信息，對當(dāng)前節(jié)點(diǎn)距終點(diǎn)的距離做出估計(jì)，作為評價(jià)該節(jié)點(diǎn)處于最優(yōu)路線上的可能性的量度，這樣就可以首先搜索可能性較大的節(jié)點(diǎn)，從而提高了搜索過程的效率。

下面是對A*算法的介紹，我們首先來介紹一下啟發(fā)式搜索中的估計(jì)函數(shù)。因?yàn)樵趩l(fā)式搜索中，對位置的估價(jià)是十分重要的。估價(jià)函數(shù)的表示如下：

其中是節(jié)點(diǎn)的估價(jià)函數(shù)，是已知的，指在狀態(tài)空間中從初始節(jié)點(diǎn)到節(jié)點(diǎn)的實(shí)際代價(jià)；是從結(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)代價(jià)，它體現(xiàn)了搜索的啟發(fā)信息，啟發(fā)信息決定著算法的啟發(fā)能力。啟發(fā)信息越多，估價(jià)函數(shù)就越好，即約束條件越多，則排除的節(jié)點(diǎn)就越多，說明這個(gè)算法越好。這種做法存在一個(gè)平衡的問題，也會使算法的準(zhǔn)確性下降。具體的說，代表了搜索的廣度優(yōu)先趨勢，當(dāng)時(shí)，可以省略，這樣就提高了搜索效率。

A*算法是一個(gè)可采納的最好優(yōu)先算法。A*算法的估價(jià)函數(shù)可表示為：

這里，是估價(jià)函數(shù)，是起點(diǎn)到終點(diǎn)的最短路徑值，是到目標(biāo)的最短路經(jīng)啟發(fā)值。由于這個(gè)其實(shí)是無法預(yù)先知道的，所以我們用前面的估價(jià)函數(shù)做近似。代替，但需要滿足（在大多數(shù)情況下都滿足時(shí)，可以不用考慮）。代替，并滿足?？梢宰C明應(yīng)用這樣的估價(jià)函數(shù)是可以找到最短路徑的。

四、基于密集型區(qū)域八叉樹的A*算法改進(jìn)

由于使用八叉樹存儲結(jié)構(gòu)存儲的環(huán)境地圖擴(kuò)展步長不一致，采用傳統(tǒng)的A*算法效率較低，因此對A*算法做了改進(jìn)，以適應(yīng)八叉樹結(jié)構(gòu)的搜索。改進(jìn)的辦法是從葉節(jié)點(diǎn)開始搜索并為Open表設(shè)置兩個(gè)優(yōu)先隊(duì)列，命名為隊(duì)列1和隊(duì)列2（隊(duì)列1中存放的節(jié)點(diǎn)總是高于隊(duì)列2），在兩個(gè)隊(duì)列中分別存放相鄰層次的全部節(jié)點(diǎn)，層次越高的優(yōu)先級越高。通過這種分層次的搜索，也大大縮小了搜索的空間并縮短了搜索時(shí)間，這樣一來大大提高了搜索效率。

五、結(jié)束語

針對于復(fù)雜的3D環(huán)境，文章根據(jù)八叉樹適合虛擬場景劃分的特點(diǎn)，采用了一種適合密集型區(qū)域的八叉樹劃分方法，進(jìn)行場景劃分。為適合八叉樹的存儲結(jié)構(gòu)，對A*算法做了改進(jìn)，引入優(yōu)先級隊(duì)列并采用了分層結(jié)構(gòu)，采用了從葉節(jié)點(diǎn)到根節(jié)點(diǎn)的搜索方法，規(guī)劃出了虛擬人行走的最優(yōu)路徑。

篇5

關(guān)鍵詞：多智能體；尋路；游戲開發(fā)

中圖分類號：TP312文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2012)13-3159-06

Application of Multi-Agent Pathfinding System in Computer Game

HUANG Jin1, HUANG Zong-Wen1, LING Zi-Yan2

(1.XingJian College of Science and Liberal Arts, Guangxi University, Naning 530004, China; 2.Geomatics Center of Guangxi, Naning 530023, China)

Abstract: This research presents a real-time multi-agent pathfinding system in computer game. In our system, each agent thinks independently, and continues to search and move to reach its destination, so a group behaviors with significant individual characteristic can be better simulated; The concept of soft obstacle is introduced to implement collision avoidance between agents and crowd movement simulation; The pathfinding algorithm is applied and bridged on the 3D games, which provides efficient multi NPC pathfinding function for re? al-time game. The paper expounds the system from overall structure, components detail, core algorithms and practical application, and then obtains the experimental results.

Key words: multi-agent; pathfinding; computer game

路徑搜索，在碰撞避免的條件下對智能體到目的地的路徑規(guī)劃問題，是游戲設(shè)計(jì)中的一個(gè)典型問題。在靜態(tài)網(wǎng)格的條件下，A*算法能夠很好的解決這個(gè)問題。但是，如果需要考慮多智能體之間或者智能體與其他有可能運(yùn)動的障礙物的碰撞避免的話，那么我們就要對A*算法進(jìn)行改進(jìn)，使智能體能夠感知潛在的障礙物碰撞。多智能體尋路系統(tǒng)令系統(tǒng)內(nèi)的每一個(gè)智能體獨(dú)立進(jìn)行思考，使他們能夠通過各自思維實(shí)現(xiàn)從出發(fā)地到目的地的導(dǎo)航。多智能體尋路系統(tǒng)在很多領(lǐng)域得到了應(yīng)用，包括機(jī)器人運(yùn)動規(guī)劃，空中交通控制，車輛路徑規(guī)劃，災(zāi)害救援，以及本文將要討論的電腦游戲[1]。

A*算法由Peter Hart等首次提出，它被用來在靜態(tài)網(wǎng)格地圖中尋找指定起點(diǎn)到目的地的最佳路徑[2]。A*是在Dijkstra算法的基礎(chǔ)上形成的[3]，Dijkstra算法對啟示節(jié)點(diǎn)周圍的所有節(jié)點(diǎn)逐一進(jìn)行搜索，直到找到目標(biāo)節(jié)點(diǎn)，而A*則在此基礎(chǔ)上擴(kuò)展了一個(gè)更直接的啟發(fā)方式，即估計(jì)目標(biāo)節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)的距離，并以此作為移動當(dāng)前點(diǎn)的重要指標(biāo)。

然而，正如前面討論的那樣，A*算法只能在靜態(tài)網(wǎng)格地圖中對單一目標(biāo)路徑規(guī)劃上得到應(yīng)用，為了解決這一問題，Silver提出了一種被廣泛應(yīng)用在電子游戲上的多智能體尋路系統(tǒng)，Local Repair A*（LRA*）[4]。在LRA*里，每一個(gè)智能體獨(dú)立的考慮自己的路徑規(guī)劃，當(dāng)智能體發(fā)現(xiàn)它的下一步路徑將出現(xiàn)障礙物導(dǎo)致的碰撞后，它們將重新規(guī)劃新的路徑，防止碰撞發(fā)生。這種算法的缺點(diǎn)在于經(jīng)常性出現(xiàn)的循環(huán)依賴和死鎖，從而導(dǎo)致在實(shí)際應(yīng)用中智能體始終無法達(dá)到目的地。

Jeremy和Jansen等人則嘗試為網(wǎng)格地圖中智能體所可能占據(jù)的每一個(gè)位置估算一個(gè)移動方向，并且令在該位置上的智能體按照這個(gè)方向移動[5] [6]。在這種算法中，他們也需要利用A*或者Dijkstra算法對網(wǎng)格進(jìn)行遍歷，只不過是將遍歷得出的數(shù)據(jù)轉(zhuǎn)化為對于某一位置的移動方向而不是一條移動路徑。這種算法在群體行為的模擬中非常有效，但是卻無法很好的模擬游戲中經(jīng)常出現(xiàn)的與群體目的相違背的個(gè)體行為。

1系統(tǒng)結(jié)構(gòu)

本文構(gòu)建的多智能體網(wǎng)格地圖尋路系統(tǒng)主要由以下幾個(gè)部分組成（如圖1所示）。

地圖網(wǎng)格：用于標(biāo)記地圖中的靜態(tài)障礙物，這和A*算法中的障礙物一樣，做了障礙標(biāo)記的網(wǎng)格將無法通行。

尋路單元：用于讀取文本形式的地圖網(wǎng)格信息，執(zhí)行網(wǎng)格的初始化和網(wǎng)格信息的更新，為智能體提供路徑搜索功能等。

動作單元：為智能體提供在3D空間內(nèi)的移動及旋轉(zhuǎn)功能。

智能體：系統(tǒng)中執(zhí)行尋路、移動、旋轉(zhuǎn)以及其他一些游戲中必須動作的基本單元。

智能體管理器：負(fù)責(zé)對智能體進(jìn)行管理，包括注冊、移除、獲取以及在適當(dāng)?shù)臅r(shí)刻命令智能體進(jìn)行尋路。

2系統(tǒng)細(xì)節(jié)

2.1尋路單元

尋路單元為我們的整個(gè)系統(tǒng)提供尋路的核心算法，這個(gè)算法由尋路網(wǎng)格初始化和尋找最佳路徑兩部分組成，智能體通過調(diào)用尋路函數(shù)獲得一個(gè)被算法承認(rèn)的最佳路徑。每當(dāng)智能體調(diào)用尋路函數(shù)時(shí)尋路網(wǎng)格初始化都將進(jìn)行一次，這是因?yàn)槲覀兊膶ぢ肪W(wǎng)格不是靜態(tài)的，而是隨著障礙物或者場景內(nèi)游戲單元位置變化而動態(tài)更新的。我們都知道，A*算法用H值來表示當(dāng)前節(jié)點(diǎn)距離終點(diǎn)的距離，而G值用來表示從起始點(diǎn)到當(dāng)前節(jié)點(diǎn)的消耗值。我們在尋路網(wǎng)格初始化中，將保留A*算法H值的計(jì)算方式而對G值，即消耗值，進(jìn)行適當(dāng)調(diào)整，引入一種軟障礙的概念使其更符合游戲要求。此外，我們在A*算法靜態(tài)障礙物的基礎(chǔ)上添加了一個(gè)排除列表，用它來標(biāo)記尋路網(wǎng)格內(nèi)動態(tài)障礙物，和靜態(tài)障礙物一樣，路徑將無法從它們上面通過。總之，這個(gè)算法是在一個(gè)動態(tài)更新的網(wǎng)格地圖上，通過考慮靜態(tài)障礙物、動態(tài)障礙物及軟障礙物的避讓，搜索最佳路徑的過程。下面，我們詳細(xì)介紹網(wǎng)格初始化和尋找最佳路徑這兩部分的實(shí)現(xiàn)過程：

2.1.1尋路網(wǎng)格初始化

尋路網(wǎng)格由網(wǎng)格細(xì)胞的二維數(shù)組構(gòu)成，一個(gè)網(wǎng)格細(xì)胞中記錄了以下幾個(gè)重要的數(shù)值：F值、G值及H值，距離損耗，密度損耗。這里，F(xiàn)值、G值及H值的含義和A*算法中保持一致，而G的具體取值由距離損耗和密度損耗計(jì)算得出。

距離損耗用于存儲智能體通過該網(wǎng)格所需的移動損耗，密度損耗則用于表示智能體在通過該網(wǎng)格時(shí)，由于場景內(nèi)軟障礙所造成的消耗。在游戲中，我們希望人群在空間充裕的條件下保持一定的距離，但是又不希望當(dāng)空間比較狹窄時(shí)造成堵塞，所以我們引入軟障礙的概念。如圖2所示，在左邊的黑色格子，是一個(gè)硬障礙，路徑將無法在黑色區(qū)域的格子通行，而右邊具有灰色圓形圖案的則是一個(gè)軟障礙，對于中心的黑色格子，路徑無法通過，但是對于灰色的圓形范圍，算法將不鼓勵(lì)但不禁止路徑從此通過，并且，越是靠近圓形中心，路徑從此通過受到的阻力越大，即密度損耗的值越大。我們使用軟障礙來表示場景中的NPC和玩家，之所以將存儲軟障礙消耗的變量稱之為密度損耗，正是因?yàn)檫@個(gè)值可以幫助我們控制場景中人群的密度。

在程序中，我們首先創(chuàng)建一個(gè)空的尋路網(wǎng)格，然后從硬盤讀文本形式的靜態(tài)障礙信息，通過靜態(tài)障礙信息修改相應(yīng)網(wǎng)格細(xì)胞類型，對場景內(nèi)每一個(gè)智能體所在位置以及它們下一個(gè)移動目標(biāo)所在位置的網(wǎng)格細(xì)胞設(shè)置為軟障礙，這樣在實(shí)際應(yīng)用中就能極大的降低智能體相互穿越（圖3）、死鎖（圖4）等情況的發(fā)生。

圖4死鎖

2.1.2尋找最佳路徑

一旦網(wǎng)格初始化過程完成，我們便基于這個(gè)最新初始化的網(wǎng)格進(jìn)行路徑搜索。

搜索路徑算法首先將起始節(jié)點(diǎn)放入closed列表里，并檢查它相鄰的8個(gè)子節(jié)點(diǎn)；接著，將這些節(jié)點(diǎn)放入open列表里，并以F值的大小順序排列；算法接下來挑選open列表中F值最小的節(jié)點(diǎn)作為下一個(gè)檢查目標(biāo)，將這個(gè)節(jié)點(diǎn)從open列表中移除并與結(jié)束節(jié)點(diǎn)進(jìn)行比較：

如果它不是結(jié)束節(jié)點(diǎn)，將其放入closed列表里，并且將它相鄰子節(jié)點(diǎn)按照其F值的大小順序放入open列表中，這個(gè)過程一直持續(xù)到我們搜索到結(jié)束節(jié)點(diǎn)，或者open列表中為空。如果它是結(jié)束節(jié)點(diǎn)，路徑搜索完成，我們計(jì)算出路徑上的所有節(jié)點(diǎn)并返回。

下面給出尋找最佳路徑的偽代碼：

Create Start Node with Current Position

Add Start Node to Open List

while Open List NOT Empty do

Update Nodes in Open List

Sort Open List by F Value in Descending

Get First Node from Open List call Node“N”

Remove N from Open List

在循環(huán)搜索的過程中，每一個(gè)節(jié)點(diǎn)都要首先進(jìn)行更新，注意到在執(zhí)行路徑搜索部分之前，網(wǎng)格已經(jīng)被重新初始化，這意味著每一個(gè)節(jié)點(diǎn)的F值都是最新的，同時(shí)，子節(jié)點(diǎn)也已經(jīng)對父節(jié)點(diǎn)的F值進(jìn)行累加，這樣做是為了保證軟障礙能夠起到控制擁擠程度的作用。此外，在將相鄰節(jié)點(diǎn)加入open列表時(shí)，我們還需要對節(jié)點(diǎn)的類型做出判斷，僅當(dāng)節(jié)點(diǎn)不是靜態(tài)障礙物、處于排出列表中（動態(tài)障礙物）或穿越者障礙物轉(zhuǎn)角時(shí)，我們才能繼續(xù)進(jìn)行余下操作。為了防止路徑穿越者障礙物轉(zhuǎn)角，我們對圖5所示的這種情況進(jìn)行測試，根據(jù)實(shí)際情況返回真或者假。

圖5智能體在不進(jìn)行障礙物轉(zhuǎn)角判斷時(shí)的錯(cuò)誤路徑

2.2動作單元

由于本文涉及的游戲是一款3D游戲，我們除了完成在2D網(wǎng)格中的路徑搜索外，還需要命令我們的智能體按照路徑在3D空間中完成旋轉(zhuǎn)和移動。動作單元為智能體提供一個(gè)通用的移動函數(shù)，智能體只要在每次更新的時(shí)候調(diào)用這個(gè)函數(shù)便能完成旋轉(zhuǎn)和移動的動作。下面，我們介紹這個(gè)函數(shù)的細(xì)節(jié)：

下面給出移動函數(shù)偽代碼：

Calculate the Direction from Agent to the Goal Call“Dire”

Calculate the Dot Product of Dire and Agent’s Face Direction Call“Dot”

if Dot is NOT larger than the Angle Threshold than

if is Clockwise than

Rotate Agent Clockwise

else

Rotate Agent Counterclockwise end if end if

Calculate the Distance between Agent and the Goal Call“Dist”

if Dist is NOT larger than the Distance Threshold than

Move Agent to Dire

else

Set Path Target to Null

end if

函數(shù)首先計(jì)算得出智能體目的地所在方向，然后計(jì)算它與智能體自身朝向之間的夾角，如果夾角大于轉(zhuǎn)角閥值，進(jìn)行旋轉(zhuǎn)，否則不進(jìn)行旋轉(zhuǎn)直接移動。在進(jìn)行旋轉(zhuǎn)之前，我們還要通過比較這兩個(gè)方向向量在極坐標(biāo)下的極角，得出正確的旋轉(zhuǎn)方向。接下來，計(jì)算智能體與目的地的距離，如果這個(gè)距離大于距離閥值，令智能體向目的地方向移動，否則不進(jìn)行移動，并將移動目標(biāo)清空。注意到智能體將在每幀渲染前都調(diào)用這個(gè)函數(shù)，我們只需要令其按照計(jì)算得出的移動方向和旋轉(zhuǎn)方向移動和旋轉(zhuǎn)一個(gè)與幀速率相關(guān)的微小量即可得到連續(xù)播放的動作。

2.3智能體及智能體管理器

智能體由兩部分組成，其一是用于尋路的尋路組件，其二是用于在游戲中顯示的3D組件。尋路組件存儲了智能體在網(wǎng)格地圖上的位置，智能體最近一次成功尋路的路徑以及路徑目標(biāo)索引。3D組件則用于存儲智能體在3D世界中的位置、朝向、移動目標(biāo)等信息，它還負(fù)責(zé)在適當(dāng)?shù)臅r(shí)候調(diào)用動作單元的移動函數(shù)，是智能體“真正”的發(fā)生移動。

我們注意到，這里存在兩張地圖，一張是用于尋路的網(wǎng)格地圖，而另一張是3D世界中的真實(shí)地圖，網(wǎng)格地圖是離散的，而真實(shí)地圖是連續(xù)的，所以我們需要分別使用尋路組件和3D組件存儲他們各自的位置和目標(biāo)等信息。并且，在必要的時(shí)候，我們還需要將這其中一套信息換算成另外一套。

智能體管理器負(fù)責(zé)在每一次更新時(shí)遍歷場景內(nèi)的所有智能體，判斷智能體是否已經(jīng)完成了最新路徑的第一步移動，如果已經(jīng)完成，則重新搜索最佳路徑，否則不做任何操作。這里，該文和LRA*算法不同，不是在檢查到下一步路徑上有障礙物時(shí)才對路徑進(jìn)行修正，而是每移動一步就要重新計(jì)算路徑，這是因?yàn)橹挥羞@樣才能讓移動著的軟障礙發(fā)揮作用。假設(shè)我們不是這樣做，一個(gè)智能體在第一次尋路時(shí)搜索得出一條路徑，而在這個(gè)智能體的移動過程中，它路徑周圍的軟障礙變得多起來，而恰好路徑又沒有通過軟障礙的中心，那么就算密度消耗非常的高，智能體還是會沿著路徑一直走，這并不是我們想要的效果。

下面給出智能體管理器更新函數(shù)偽代碼：

for all Agent in Agents of the Scene call“A”do

if A’s Path Movement Finished then

Update Pathfinding Unit

Find new Path for A

Set the First Cell of the new Path A’s next Path Target

end if

end for

3結(jié)果

這套多智能體尋路系統(tǒng)能夠高效的模擬小規(guī)模人群（大約20-40智能體）在中型網(wǎng)格地圖（大約40*40到60*60）上的尋路活動。我們將測試程序在一臺具有3.00GHz Inter Core2 Duo處理器及ATI Radeon 4850顯卡配置的計(jì)算機(jī)上運(yùn)行，得到45FPS以上的幀速率，在智能體數(shù)量達(dá)到100時(shí)，幀速率下降到3-6FPS。由于本文沒有將算法在GPU上實(shí)現(xiàn)，運(yùn)行效率受到了明顯限制，在將來的工作中，可以嘗試將這個(gè)算法在GPU上實(shí)現(xiàn)，這樣便能顯著的提高運(yùn)行效率，滿足大規(guī)模人群在大型網(wǎng)格地圖上的尋路活動。

圖6是一個(gè)20智能體在測試地形上的尋路過程。10個(gè)女性NPC和10個(gè)男性NPC分別在初始化在地圖的兩個(gè)角落，女性NPC和男性NPC都以對方的初始位置為移動目標(biāo)，通過本文實(shí)現(xiàn)的尋路系統(tǒng)，他們成功的繞過墻壁，避開NPC之間的碰撞，到達(dá)了目的地。

圖6多智能體尋路測試

圖7顯示了將本系統(tǒng)應(yīng)用在3D游戲上的運(yùn)行效果。游戲要求每個(gè)NPC在場景中都擁有各自的目的，他們可能移動到場景內(nèi)的任何一個(gè)房間，和主角談話，甚至可能停下來發(fā)一會呆，所以，這些NPC的行為不是一個(gè)群體行為，而本文的尋路系統(tǒng)能夠很好的模擬這一點(diǎn)。

參考文獻(xiàn)：

[1] Ko-Hsin Cindy Wang and Adi Botea.Fast and Memory-Efficient Multi-Agent Pathfinding[C].Proceedings of the Eighteenth International Conference on Automated Planning and Scheduling,2008:380-387.

[2] Peter Hart,Nils Nilsson,Bertram Raphael.A Formal Basis for the Heuristic Determination of Minimum Cost Paths[J].IEEE Transactions on Systems Science and Cybernetics,1968,4(2):100-107.

[3] Ian Millington.Articial Intelligence for Games (The Morgan Kaufmann Series in Interactive 3D Technology)[C].Morgan Kaufmann Publish? ers Inc.,San Francisco, CA, USA,2006.

[4] Silver D.Cooperative pathfinding[J].In Young, R. M.,and Laird, J. E., eds.,AIIDE,AAAI Press,2005:117-122.

篇6

[關(guān)鍵詞]三角形單聯(lián)絡(luò)；中壓配電網(wǎng)；智能規(guī)劃

中圖分類號：TM715；TP18 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-914X（2014）37-0240-02

城市配電網(wǎng)中重要的一部分就是中壓配電網(wǎng)，中壓配電網(wǎng)的“筋骨”是網(wǎng)絡(luò)結(jié)構(gòu)，一個(gè)堅(jiān)強(qiáng)的網(wǎng)架對電網(wǎng)的安全可靠運(yùn)以及經(jīng)濟(jì)的運(yùn)營有重要的意義。國內(nèi)一直以來都將網(wǎng)絡(luò)架構(gòu)的研究重點(diǎn)放在接線模式方面，但是當(dāng)前很多發(fā)達(dá)國家的網(wǎng)架建設(shè)已經(jīng)不再考慮單純的應(yīng)用接線模式，而是利用標(biāo)準(zhǔn)的供電模型來對高水平的中壓配電網(wǎng)進(jìn)行構(gòu)筑，結(jié)合國外的先進(jìn)經(jīng)驗(yàn)，國內(nèi)一些學(xué)者進(jìn)行了有關(guān)供電模型以及其特性的研究，并構(gòu)建了與我國中壓配電網(wǎng)相適應(yīng)的若干種典型的供電模型。

一、配電模型分析

配電模型能夠?qū)╇妳^(qū)域的地形特點(diǎn)、負(fù)荷密度以及電網(wǎng)現(xiàn)狀之間的關(guān)系進(jìn)行反映，它針對某一供電的區(qū)域，以高壓配電的變電站作為源點(diǎn)并以中壓饋線作為網(wǎng)，使供電網(wǎng)絡(luò)單元通過組合優(yōu)選來形成。供電模型的是以供電架構(gòu)為基礎(chǔ)并對中壓配電網(wǎng)的接線模式相配合來完成構(gòu)建的。供電模型主要分為點(diǎn)狀供電模型、鏈?zhǔn)焦╇娔Ｐ鸵约叭枪╇娔Ｐ秃途匦喂╇娔Ｐ退姆N，本文以單聯(lián)絡(luò)三角形供電模型為研究對象，圖1表示的是單聯(lián)絡(luò)三角形供電模型，其中是高壓變電站，是分段開關(guān)，是聯(lián)絡(luò)開關(guān)，線段代表10KV供電線路。

二、配電網(wǎng)規(guī)劃的相關(guān)數(shù)學(xué)模型

本文在配電網(wǎng)絡(luò)的規(guī)劃數(shù)學(xué)模型的選擇上，最小的目標(biāo)函數(shù)是以線路的規(guī)劃年綜合費(fèi)用來充當(dāng)，這其中包含了投資費(fèi)用以及網(wǎng)損費(fèi)用。電網(wǎng)的線路主要有主干線線、聯(lián)絡(luò)線路以及分支線路來組成。如果在進(jìn)行優(yōu)化時(shí)將這三者都考慮到，是非常復(fù)雜的，所以本文主要的優(yōu)化對象是主干線以及聯(lián)絡(luò)線路，只將分支線路做近似考慮，就是說在總費(fèi)用中只將其近似的投資費(fèi)用計(jì)入。目標(biāo)函數(shù)表示為，在該式中表示的是主干以及聯(lián)絡(luò)線路投資，表示的是主干線路的網(wǎng)損，表示的是分支線路的近似投資。在這其中，又可得：（1）其中是變電站低壓側(cè)線路的折舊年限，是貼現(xiàn)率，是單位長度的線路投資費(fèi)用，N是變電站的總數(shù)，是第i座變電站的第j條主要干線長度，是第 個(gè)變電站的所出路線總數(shù)，K是本組模型的聯(lián)絡(luò)線路的總數(shù)，是第條聯(lián)絡(luò)線路的長度。（2），φ，b表示線路的網(wǎng)損折算系數(shù)，表示單位電能損耗折價(jià)系數(shù)，表示線路的單位長度電阻，表示線路年損耗的小時(shí)數(shù)，表示功率因數(shù)，U表示變電的壓低壓側(cè)線路的線電壓，表示第j條主干線帶的負(fù)荷。（3）其中，表示單位長度的分支線路投資，表示分布于第i座變電站第j條主干線路的垂直分支路長度的總和，q表示的是分支線路的曲折系數(shù)。

三、智能規(guī)劃方法

1、基礎(chǔ)數(shù)據(jù)

在供電模型的基礎(chǔ)上進(jìn)行布線規(guī)劃時(shí)，主要需要變電站的位置、容量以及供電范圍和負(fù)荷點(diǎn)的位置以及負(fù)荷值，還有配電網(wǎng)絡(luò)的地理信息等基礎(chǔ)數(shù)據(jù)。

2、構(gòu)建優(yōu)化模型

2.1 構(gòu)建輻射線路

在對輻射線路進(jìn)行構(gòu)建時(shí)，采用的方法是備選路徑集方法。本文采用的是蟻群算法來對備選路徑集進(jìn)行建立，因?yàn)樗男阅芨鼉?yōu)秀。圖2為蟻群算法的流程圖。

2.2 構(gòu)建聯(lián)絡(luò)線路

在將輻射線路進(jìn)行構(gòu)建后，聯(lián)絡(luò)線路包含了站間聯(lián)絡(luò)、站內(nèi)聯(lián)絡(luò)，這些都產(chǎn)生于輻射線路的末端。并且，聯(lián)絡(luò)線路通常都選用的是輻射線路末端節(jié)點(diǎn)間的最小路徑，所以可以應(yīng)用Floyd最短路徑算法的來實(shí)現(xiàn)聯(lián)絡(luò)線路的構(gòu)建。

2.3 主干線路的供電范圍

在形成了變電站的主干線后，就要對每條主干線路的帶負(fù)荷情況進(jìn)行確定，也就是主干線路的供電范圍，在進(jìn)行確定時(shí)的方法是先將每條主干線路的負(fù)載余量進(jìn)行計(jì)算，之后選擇任意一個(gè)負(fù)荷點(diǎn)，從近到遠(yuǎn)的搜索最短的路徑。此方法能夠搜索出所有的負(fù)荷點(diǎn)，就可以對每條線路的主干線的供電范圍進(jìn)行確定。

2.4 構(gòu)建優(yōu)化模型

本文采用的主要優(yōu)化手段是遺傳算法，所以在構(gòu)建優(yōu)化模型時(shí)，主要的工作是對主干以及聯(lián)絡(luò)線路的染色體進(jìn)行建立。生成染色體的初始種群過程為對每個(gè)變電站，以每個(gè)變電站為中心將其供電范圍近似為一個(gè)圓，然后做圓的N等分線，等分線數(shù)目等于主干線路的數(shù)目。接著隨機(jī)選擇來自于等分線末端的任一領(lǐng)域內(nèi)的一個(gè)街道分段點(diǎn)來作為主干線路的末端節(jié)點(diǎn)，這樣就形成了一個(gè)末端節(jié)點(diǎn)的集合，因?yàn)殡S機(jī)選擇所以此集合的組合方式有很多的方式，并且隨著圓的等分線進(jìn)行轉(zhuǎn)動，其對應(yīng)的轉(zhuǎn)動角會有不同的組合方式。

3、適應(yīng)度計(jì)算

一個(gè)染色體代表的是一個(gè)供電模型的規(guī)劃方案，在這里適應(yīng)度就代表的是上述的總目標(biāo)函數(shù)。

4、遺傳模擬退火操作

模擬退火操作的對象是遺傳種群中的所有染色體，隨機(jī)選擇其鄰域的一種狀態(tài)，然后對其進(jìn)行模擬退火的接受概率接受或是拒絕的過程。本文構(gòu)建的染色體代表其中的某一主干線路，對和它有一樣末端節(jié)點(diǎn)進(jìn)行選擇，并且選擇之前的K條最短路以外的備選路徑集中的隨便一條線路來作為領(lǐng)域的狀態(tài)，并按照下文的接受概率進(jìn)行接受或拒絕過程。接受概率公式：，其中代表新狀態(tài)的評價(jià)值，第k代的溫度，代表原狀態(tài)評價(jià)值。通過這個(gè)過程能夠得到新的染色體種群，之后對其做遺傳操作，一直循環(huán)一直到能夠滿足終止的條件。

結(jié)束語

在過去，先進(jìn)行輻射線路的布局，之后進(jìn)行聯(lián)絡(luò)線路的優(yōu)化是帶聯(lián)絡(luò)線路的配電網(wǎng)主要的布線方法，但這種方法具有局限性。本文對基于三角形單聯(lián)絡(luò)模型的中壓配電網(wǎng)進(jìn)行智能規(guī)劃時(shí)，構(gòu)建了主干以及聯(lián)絡(luò)線路的整體優(yōu)化模型，并對其布線的方案進(jìn)行了優(yōu)化，這就使得優(yōu)化的全局性得到了優(yōu)化，優(yōu)化的方法的是以優(yōu)化模型中的染色體的構(gòu)成特點(diǎn)為依據(jù)，并在遺傳算法中引入了模擬退火思想，這樣做的優(yōu)點(diǎn)是可以克服算法過早收斂的問題，能有效的進(jìn)行優(yōu)化。

參考文獻(xiàn)

篇7

關(guān)鍵詞：蟻群算法；物流配送；路徑優(yōu)化；數(shù)學(xué)模型

DOIDOI：10.11907/rjdk.161974

中圖分類號：TP319

文獻(xiàn)標(biāo)識碼：A 文章編號文章編號：16727800（2016）011014004

基金項(xiàng)目基金項(xiàng)目：

作者簡介作者簡介：袁文濤（1993-）男，安徽馬鞍山人，上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院碩士研究生，研究方向?yàn)槟Ｊ阶R別與智能系統(tǒng)；孫紅（1964-）女，上海人，上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院副教授、碩士生導(dǎo)師，研究方向?yàn)槟Ｊ阶R別與智能系統(tǒng)、 控制理論與控制工程、企業(yè)信息化系統(tǒng)與工程。

0 引言

解決組合優(yōu)化問題的最優(yōu)化求解算法有多種現(xiàn)代人工智能算法方案，優(yōu)化算法用來處理問題最優(yōu)解的求解，該問題通常由多個(gè)變量共同決定。當(dāng)前，求解最短路徑問題是圖論研究中的一個(gè)典型求解組合優(yōu)化算法問題，旨在尋找圖表（由節(jié)點(diǎn)和路徑構(gòu)成）中兩節(jié)點(diǎn)或多節(jié)點(diǎn)之間的最短路徑。常用的最優(yōu)化路徑求解方法有Bellman-Ford算法、Dijkstra算法、A*算法和蟻群算法。這些算法都有自身的優(yōu)點(diǎn)和不足。在對不同算法作出比較后，可以得出蟻群算法在解決網(wǎng)絡(luò)路由和城市交通系統(tǒng)的問題中是相對有利的。

就目前研究來看，隨著實(shí)際組合問題的變化，基本的智能算法已經(jīng)不能滿足解決這類組合優(yōu)化問題，同時(shí)其優(yōu)勢也在減弱[1]。本文采取改進(jìn)后的組合優(yōu)化蟻群算法以彌補(bǔ)傳統(tǒng)蟻群算法易陷入局部最優(yōu)解的不足，加快了求全局最優(yōu)解的構(gòu)造速率。

蟻群算法（Ant Colony Optimization， ACO），是一種模擬螞蟻群體智能行為的進(jìn)化仿生類優(yōu)化算法，在求解性能上具有強(qiáng)魯棒性、優(yōu)良的分布式計(jì)算能力、便于與其它算法相結(jié)合等優(yōu)點(diǎn)[2-3]。通常作為一種用來在多變量組合優(yōu)化問題的多候選解中尋找最優(yōu)化路徑的機(jī)率型算法。它由Marco Dorigo于1992年在其博士論文《Ant system： optimization by a colony of cooperating agents》中首先提出，其靈感來源于通過對蟻群社會的長期跟蹤觀察后發(fā)現(xiàn)，雖然單個(gè)螞蟻沒有視力、智慧程度低、工作方式簡單，但它們卻有強(qiáng)大的執(zhí)行能力和協(xié)同工作能力，依靠復(fù)雜群體的自組織協(xié)同能力發(fā)揮出超出單個(gè)個(gè)體累加的智能，是一種超個(gè)體（superorganism，又稱超有機(jī)體）存在現(xiàn)象。蟻群是在這樣的超個(gè)體案例中最有名的例子。雖然蟻群算法的嚴(yán)格理論基礎(chǔ)和實(shí)際應(yīng)用尚未成熟，國內(nèi)外相關(guān)研究暫處于實(shí)驗(yàn)階段，但這并不妨礙人們對蟻群算法的研究已經(jīng)由當(dāng)初單一的解決商旅問題（TSP）發(fā)展到解決調(diào)度問題、網(wǎng)絡(luò)通信等多個(gè)方向的最優(yōu)化求解應(yīng)用。

目前，蟻群優(yōu)化算法已廣泛應(yīng)用于多種求組合最優(yōu)化問題，在面臨路例如作業(yè)安排調(diào)度問題和路由車輛的二次分派問題上表現(xiàn)出了良好的性能，也經(jīng)常被用來求旅行推銷員問題的擬最優(yōu)解。它在圖表動態(tài)變化情況問題的求解上相比螢火蟲算法和遺傳算法具有絕對優(yōu)勢：蟻群算法的最大優(yōu)點(diǎn)在于可以連續(xù)運(yùn)行并適應(yīng)實(shí)時(shí)變化；缺陷是在處理較大規(guī)模和復(fù)雜數(shù)據(jù)問題時(shí)，容易存在運(yùn)算耗時(shí)長、收斂速度慢、得不到全局最優(yōu)解等問題。

在求最優(yōu)解的歷次迭代中，單個(gè)螞蟻會根據(jù)給定的規(guī)則和限定條件選擇從一個(gè)城市（節(jié)點(diǎn)）轉(zhuǎn)移到另一個(gè)城市（節(jié)點(diǎn)）：它必須對所有城市訪問一次，而相對距離越遠(yuǎn)的城市被選中為下一個(gè)訪問點(diǎn)的機(jī)會越少（能見度低）；相反，在兩個(gè)城市（節(jié)點(diǎn)）邊際的一邊形成的信息素越濃烈，則該邊際作為路徑被選擇的概率越大；在較短路程情況下，短時(shí)間內(nèi)更多螞蟻會在所有走過的路徑上留下更多信息素，在每次迭代更新后，信息素軌跡濃度會按百分比揮發(fā)從而反饋給下一只途經(jīng)的螞蟻并影響它作出路徑選擇。

1 車輛路徑問題

傳統(tǒng)的車輛路徑問題也叫VRP（Vehicle Routing Problem）問題，是關(guān)系到現(xiàn)代物聯(lián)網(wǎng)發(fā)展過程中物流配送系統(tǒng)的一個(gè)關(guān)鍵問題，屬于NP難題。一直以來，該問題也是管理科學(xué)和物流運(yùn)輸方面的重要課題[4]，受到國內(nèi)外學(xué)者的廣泛關(guān)注。

VRP問題描述如下：在一些由于經(jīng)濟(jì)或者地理限定的條件約束下，組織一個(gè)車隊(duì)，從一個(gè)或者多個(gè)初始點(diǎn)出發(fā)，規(guī)定達(dá)到多個(gè)不同的地點(diǎn)，設(shè)計(jì)一個(gè)成本最小、路程最短的路線集，使得：① 每個(gè)城市只能被一輛車訪問，只訪問一次；②所有送貨車輛必須從起始點(diǎn)出發(fā)再回到起始點(diǎn)；③某些特定的約束條件需要被滿足。

VRP的數(shù)學(xué)模型表示如下：一共有k個(gè)客戶，第i個(gè)客戶的貨物需求為gi，配送中心派出車輛承擔(dān)運(yùn)輸任務(wù)，其載重為q。設(shè)gi

如果前提有約束條件用于車輛本身，即容量限制和總長限制，則稱為有能力約束的車輛路徑問題（Capacitated Vehicle Routing Problem）。此模型是車輛路徑問題的基本模型，這類VRP問題叫作CVRP問題[5]。

設(shè)每個(gè)客戶點(diǎn)只允許被訪問一次，車輛所訪問的客戶點(diǎn)的需求總和不能超過車輛的負(fù)載能力，且總行駛的路程也不得超過其最大的行駛距離，達(dá)到用最少的車輛最短的路徑完成既定任務(wù)。

。

2 可約束蟻群算法實(shí)現(xiàn)

2.1 算法實(shí)現(xiàn)方式

當(dāng)前蟻群算法領(lǐng)域存在MPDACO局部更新和MPDACO全局更新兩種方式。前者指當(dāng)單個(gè)螞蟻從一個(gè)節(jié)點(diǎn)到達(dá)下一個(gè)節(jié)點(diǎn)完成轉(zhuǎn)移后就立刻更新螞蟻通過路徑時(shí)所留下的的信息素，后者是當(dāng)螞蟻遍歷完所有給定節(jié)點(diǎn)后再更新整條路徑上的信息素，不再是對所有的螞蟻，而是僅對全局最優(yōu)的螞蟻得到的路徑使用。從兩種更新方式得到的結(jié)果作對比可以得出，全局信息素更新方法雖然可以加快收斂速率，但是存在著一定的缺陷和不足，易使路徑更快地集中于單一解，易陷入局部最優(yōu)，這些缺點(diǎn)限制了它的廣泛傳播及應(yīng)用。

本文綜合上述兩種更新方法的優(yōu)點(diǎn)和不足，列出了一種新的組合疊加更新方法：在路徑搜索的前十次循環(huán)中，采用局部最優(yōu)解更新，十次固定循環(huán)結(jié)束后，再采用全局最優(yōu)解進(jìn)行更新，這種更新方式可以有效避免蟻群搜索得到的路徑沉入局部最優(yōu)解中，有利于發(fā)現(xiàn)更多較優(yōu)解。

2.2 算法實(shí)現(xiàn)步驟

根據(jù)改進(jìn)的蟻群算法，將優(yōu)化后的蟻群算法應(yīng)用于CVRP問題的實(shí)現(xiàn)步驟如下：

（1）參數(shù)初始化。設(shè)迭代次數(shù) Nc=0；每條路徑上的信息素濃度Δτij（0）=c（c為常數(shù)），并且Δτij=0；隨機(jī)將m個(gè)螞蟻放置到初始點(diǎn)上。

（2）更新迭代（循環(huán)）次數(shù)，即Nc=Nc+1。

（3）初始化禁忌表，螞蟻禁忌表的索引號k=1。

（4）更新螞蟻數(shù)目k=k+1。

（5）判斷路徑是否在搜索熱區(qū)內(nèi)。按照式（a）～（f）計(jì)算出每只螞蟻應(yīng)當(dāng)轉(zhuǎn)移至下一個(gè)城市（節(jié)點(diǎn)）的概率并完成移動。

（6）當(dāng)螞蟻從i城市（節(jié)點(diǎn)）出發(fā)到達(dá)j城市（節(jié)點(diǎn)）時(shí)，對其所經(jīng)過的路徑上的信息素進(jìn)行更新，并修改禁忌表，將禁忌表指針按照當(dāng)前狀況進(jìn)行修改，即將新城市（節(jié)點(diǎn)）j置于禁忌表tabuk中。

（7）執(zhí)行步驟（b）～（f），直到所有螞蟻都找到了一條包含所有城市（節(jié)點(diǎn)）的可行路徑解。

（8）在新生成的所有可行解中找到一條最短路徑作為本次迭代中的最優(yōu)路徑解。

（9）判斷循環(huán)次數(shù)是否小于十次，若小于十次，則對螞蟻找到的最優(yōu)路徑按照本次迭代最優(yōu)值進(jìn)行信息素更新；若循環(huán)次數(shù)超過十次，則按照全局信息素進(jìn)行更新。

（10）對所有螞蟻經(jīng)過的路徑，按式（1）進(jìn)行一次全局更新。

（11）循環(huán)執(zhí)行（b）～（j），直到連續(xù)多次的迭代中得到的解已收斂或循環(huán)次數(shù)Nc的值已經(jīng)達(dá)到給定的最大迭代次數(shù)的情況下選取當(dāng)前輸出值作為本次最優(yōu)解。

3 實(shí)驗(yàn)仿真

設(shè)存在一個(gè)物流中心有4輛運(yùn)輸車， 單輛車最大載重為1 000kg， 現(xiàn)需要同時(shí)向7個(gè)隨機(jī)分布的客戶點(diǎn)派送貨物， 蟻群算法的初始化參數(shù)為： 螞蟻總數(shù)為20只， 算法的最大迭代數(shù)為100次， α和β分別為1，2， 信息素的揮發(fā)速度為0.75， 實(shí)驗(yàn)重復(fù)運(yùn)行100次， 求得的平均結(jié)果為最終結(jié)果。同時(shí)初始時(shí)刻各邊上的信息痕跡為1，殘留信息的相對重要度為1，設(shè)置預(yù)見度為5。原始數(shù)據(jù)進(jìn)行處理結(jié)果分析如圖3所示。按本文提出的優(yōu)化蟻群算法求解CVRP后的處理仿真結(jié)果如圖4所示。

觀測圖3、圖4的收斂曲線，可以知道蟻群算法優(yōu)化后的結(jié)果相比之前的行車路徑有大幅度優(yōu)化[810]，如圖5所示。針對每個(gè)收斂的點(diǎn)結(jié)合數(shù)據(jù)可以看出，傳統(tǒng)蟻群算法的平均路徑在迭代次數(shù)為45時(shí)可以得到最優(yōu)解，而改進(jìn)后的蟻群算法可以在第5次左右得到最優(yōu)解，相當(dāng)于收斂速度提高了近80%。

4 結(jié)語

在當(dāng)今應(yīng)用數(shù)學(xué)和理論計(jì)算機(jī)科學(xué)的領(lǐng)域中，組合優(yōu)化（Combinatorial Optimization）是在一個(gè)有限的對象集中找出最優(yōu)對象的一類重要課題，屬于運(yùn)籌學(xué)的一個(gè)重要分支。在很多組合優(yōu)化問題中，窮舉搜索/枚舉法是不可行的。組合優(yōu)化問題的特征為可行解的集是離散或者可以簡化到離散的，并且目標(biāo)是找到最優(yōu)解。解決組合優(yōu)化問題一般采用智能算法，而這些算法都有自身的優(yōu)點(diǎn)和缺點(diǎn)。組合優(yōu)化的難處，主要是加進(jìn)來拓?fù)浞治?，在不同的拓?fù)湫螒B(tài)下，算法也需隨著不同部分的約束關(guān)系作出相應(yīng)調(diào)整。從目前研究來看，隨著實(shí)際組合問題的變化，基本的智能算法已不能解決這類組合優(yōu)化問題。

蟻群算法作為一種仿生類進(jìn)化算法在求路徑最優(yōu)化解方面具有很好的效果。本文首先引出蟻群算法可以用于解決這一類問題，然后介紹了約束車輛路徑問題，也即CVRP問題，說明了其約束模型；接著研究了基本的蟻群算法步驟，并對其中信息素更新和改進(jìn)了啟發(fā)因子，解析并改良了蟻群算法應(yīng)用于CVRP問題的實(shí)現(xiàn)步驟和處理方法。

本文提出的組合疊加更新方法可有效克服傳統(tǒng)蟻群算法收斂質(zhì)量低、耗時(shí)長、易陷入局部最優(yōu)解等缺陷，使蟻群算法的全局優(yōu)化能力得到大幅度提高。對比實(shí)驗(yàn)前數(shù)據(jù)可以看出，蟻群算法找到最短路徑的收斂速度比傳統(tǒng)方法快了80%左右，確實(shí)是一種求解最短物流配送路徑的有效算法。

參考文獻(xiàn)：

[1] 陳昌敏.基于蟻群算法的物流配送路徑優(yōu)化研究與應(yīng)用[D].成都：西華大學(xué)，2012（4）：1154.

[2] 宋留勇，王銳，周永旺，等.動態(tài)城市交通網(wǎng)絡(luò)優(yōu)化模型研究及算法設(shè)計(jì)[J].測繪科學(xué)，2011，36（1）：134136.

[3] 鐘石泉，賀國光.有時(shí)間窗約束車輛調(diào)度優(yōu)化的一種禁忌算法[J].系統(tǒng)工程理論方法應(yīng)用，2005，14（6）：523527.

[4] CHAO YIMING.A tabu search method for the truck and trailer routing problem[J].Computer and Operations Research，2002，29（1）：3351.

[5] 楊中秋，張延華.改進(jìn)蟻群算法在交通系統(tǒng)最短路徑問題的研究[J].科學(xué)計(jì)算與信息處理，2009，32（8）：7678.

[6] 李松，劉興，李瑞彩.基于混合禁忌搜索算法的物流配送路徑優(yōu)化問題研究[J].鐵道運(yùn)輸與經(jīng)濟(jì)， 2007， 29（3）：66 69.

[7] 陶波， 朱玉琴.改進(jìn)的7動態(tài)規(guī)劃法在車輛最短路徑問題中的應(yīng)用[J].重慶工學(xué)院學(xué)報(bào)， 2009，23（1）：2427.

[8] 李軍，郭耀煌.物流配送車輛優(yōu)化調(diào)度理論與方法[M].北京：中國物資出版社， 2001：101113.

[9] 張萬旭，林健良，楊曉偉.改進(jìn)的最大最小螞蟻算法在有時(shí)間窗車輛路徑問題中的應(yīng)用[J].計(jì)算機(jī)集成制造系統(tǒng)，2005，11（4）：572576.

[10] 余h，胡宏智.基于改進(jìn)遺傳算法的物流配送路徑求解[J].計(jì)算機(jī)技術(shù)與發(fā)展，2009，19（3）：5255.

[11] 朱慶保，蟻群優(yōu)化算法的收斂性分析[J]. 控制與決策，2006，21（7）：3016.

[12] 鄭松，侯迪波，周澤魁，動態(tài)調(diào)整選擇策略的改進(jìn)蟻群算法[J].控制與決策，2008，23（2）：13.

[13] 夏亞梅，程渤，陳俊亮，等.基于改進(jìn)蟻群算法的服務(wù)組合優(yōu)化[J].計(jì)算機(jī)學(xué)報(bào)，2012，35（2）：311.

篇8

關(guān)鍵詞：群體算法；模糊聚類；預(yù)測模型；預(yù)測

中圖分類號：TP301文獻(xiàn)標(biāo)識碼：A

1前言

電力負(fù)荷預(yù)測是電力系統(tǒng)調(diào)度和計(jì)劃部門安排購電計(jì)劃和制定運(yùn)行方式的基礎(chǔ)，它對于電力系統(tǒng)規(guī)劃、運(yùn)行與控制有著重要的意義。為了提高電網(wǎng)運(yùn)行的安全性和經(jīng)濟(jì)性，改善供電質(zhì)量，負(fù)荷預(yù)測需要盡可能高的預(yù)測精度。隨著分時(shí)電價(jià)的市場化營運(yùn)，精度高、速度快的預(yù)測理論和方法愈顯重要和迫切。

負(fù)荷預(yù)測已有很長的研究歷史。早期的方法以時(shí)間序列法、回歸分析法為主[1]，這類方法計(jì)算量小，速度較快，但由于模型過于簡單而無法模擬復(fù)雜多變的電力負(fù)荷。近年來，隨著人工智能技術(shù)的迅猛發(fā)展，灰色理論法[2]、神經(jīng)網(wǎng)絡(luò)法[3]、相似日聚類[4]，模糊聚類[5]在負(fù)荷預(yù)測領(lǐng)域得到廣泛應(yīng)用。它們較以前的方法更能處理負(fù)荷和影響因素之間的非線形關(guān)系，因而得到了較高的預(yù)測精度。但他們有各自的缺點(diǎn)，灰色預(yù)測模型從理論上講可以適用于任何非線性變化的負(fù)荷指標(biāo)預(yù)測，但其微分方程指數(shù)解比較適合于具有指數(shù)增長趨勢的負(fù)荷指標(biāo)，對于具有其他趨勢的指標(biāo)，則擬合灰度大，精度難以提高。利用神經(jīng)網(wǎng)絡(luò)進(jìn)行電力負(fù)荷預(yù)測時(shí)，神經(jīng)網(wǎng)絡(luò)可以通過學(xué)習(xí)，從復(fù)雜的樣本數(shù)據(jù)中擬合出輸入輸出之間高維、非線性的映射關(guān)系，從而進(jìn)行較高精度的預(yù)測。但是，電力負(fù)荷受到多種因素的影響，電力負(fù)荷曲線的變化形態(tài)差異較大。

目前，針對電力負(fù)荷預(yù)測較好的方法是采用組合式預(yù)測模型-FCBP模型[6]。其原理是這樣的：首先，采用模糊聚類分析方法，以每天的負(fù)荷數(shù)據(jù)、天氣數(shù)據(jù)以及天類別數(shù)據(jù)為指標(biāo)，將歷史數(shù)據(jù)分成若干類別；然后對每一類別建立相應(yīng)的神經(jīng)網(wǎng)絡(luò)預(yù)測模型；預(yù)測時(shí)找出與預(yù)測天相符的預(yù)測類別，利用相應(yīng)的神經(jīng)網(wǎng)絡(luò)預(yù)測模型進(jìn)行電力負(fù)荷預(yù)測，實(shí)踐證明這種方法是有效的。

但是傳統(tǒng)的模糊聚類算法有易陷入局部最優(yōu)解，處理大量、高維的數(shù)據(jù)時(shí)，在時(shí)間性能上難以令人滿意的缺陷。蟻群算法是最近幾年才提出的一種新型的模擬進(jìn)化算法，由意大利學(xué)者Dorigo,M[7]等人首先提出，用蟻群在搜索食物源的過程中所體現(xiàn)出來的尋優(yōu)能力來解決一些離散系統(tǒng)優(yōu)化中困難問題。已經(jīng)用該方法求解了旅行商問題、指派問題、調(diào)度問題等，取得了一系列較好的實(shí)驗(yàn)結(jié)果。本文將蟻群算法引入此模型，用蟻群算法改進(jìn)模糊聚類，并和神經(jīng)網(wǎng)絡(luò)組合，得到新型預(yù)測模型-AFCBP模型，經(jīng)實(shí)驗(yàn)證明得到良好效果。

2理論分析

2.1蟻群算法優(yōu)化理論

經(jīng)過大量研究發(fā)現(xiàn)，螞蟻個(gè)體之間是通過一種稱之為外激素的物質(zhì)進(jìn)行信息傳遞，從而能相互協(xié)作，完成復(fù)雜的任務(wù)。螞蟻在運(yùn)動過程中，能夠在它所經(jīng)過的路徑上留下該種物質(zhì)，而且螞蟻在運(yùn)動過程中能夠感知這種物質(zhì)的存在及其強(qiáng)度，并以此指導(dǎo)自己的運(yùn)動方向，螞蟻傾向于朝著該物質(zhì)強(qiáng)度高的方向移動。因此，由大量螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。螞蟻個(gè)體之間就是通過這種信息的交流達(dá)到搜索食物的目的。

以TSP問題為例說明基本蟻群算法的框架，設(shè)有m個(gè)城市，dij(i,j=1,2,…,n)表示城市i和j間的距離，τij(t)表示在t時(shí)刻城市i和j之間的信息量，用它模擬實(shí)際螞蟻的外激素。設(shè)共有m只螞蟻，用 表示在t時(shí)刻螞蟻k由城市i轉(zhuǎn)移到城市j的概率：

其中，U為螞蟻已經(jīng)搜索過的部分路徑，S表示螞蟻k下一步允許走過的城市的集合，a表示路徑上的信息量對螞蟻選擇路徑所起的作用大小， 表示為由城市i轉(zhuǎn)移到城市j的期望程度，例如，可以取 。當(dāng)a=0時(shí)，算法就是傳統(tǒng)的貪心算法；而當(dāng)b=0時(shí)，就成了純粹的正反饋的啟發(fā)式算法。經(jīng)過n個(gè)時(shí)刻，螞蟻可走完所有的城市，完成一次循環(huán)。每只螞蟻所走過的路徑就是一個(gè)解，此時(shí)，要根據(jù)下式對各路徑上信息量作更新：

其中，Q為常數(shù)，Lk為螞蟻k在本次循環(huán)中所走路徑的長度。在經(jīng)過若干次循環(huán)以后，可以根據(jù)適當(dāng)?shù)耐Ｖ箺l件來結(jié)束計(jì)算。

由上述可知，蟻群算法的優(yōu)化過程的本質(zhì)在于：1) 選擇機(jī)制，信息量越大的路徑，被選擇的概率越大；2) 更新機(jī)制，路徑上面的信息量會隨螞蟻的經(jīng)過而增長，而且同時(shí)也隨時(shí)間的推移逐漸減小；3) 協(xié)調(diào)機(jī)制，螞蟻之間實(shí)際上是通過信息量來互相通訊、協(xié)同工作的，這樣的機(jī)制使得蟻群算法具有很強(qiáng)的發(fā)現(xiàn)較好解能力。

2.2模糊聚類基本原理

聚類分析算法可以描述為：給定m維空間R中的n個(gè)向量，把每個(gè)向量歸屬到m個(gè)聚類中的某一個(gè)，使得每一個(gè)向量與其聚類中心的距離最小。經(jīng)常用的基于劃分的聚類算法是c-均值算法，它把n個(gè)向量 (i= 1，2,…,n)分成m個(gè)類 (i=1,2,…,m)，并求每類的聚類中心，使得非相似性（或距離）指標(biāo)的目標(biāo)函數(shù)達(dá)到最小。當(dāng)選擇第i個(gè)類 中向量 與相應(yīng)的聚類中心 間的度量為歐基里德距離時(shí)，目標(biāo)函數(shù)定義為：

這里p是循環(huán)計(jì)算的次數(shù)， 是類 內(nèi)的目標(biāo)函數(shù)， 表明參數(shù)確定屬于哪個(gè)簇團(tuán)。顯然 的大小取決于聚類中心 和 的形狀， 越小，表明聚類的效果越好。

c-均值算法的隸屬度要么是1，要么是0，這種硬性的劃分?jǐn)?shù)據(jù)點(diǎn)屬于某一類團(tuán)不能反映數(shù)據(jù)點(diǎn)與簇團(tuán)中心的實(shí)際關(guān)系。為了處理這個(gè)問題，人們引入了模糊集的概念。自1969年Ruspini首先提出第一個(gè)解析的模糊聚類算法以來，已經(jīng)有很多人提出了許多的模糊聚類算法?；谀：齽澐值哪：垲愃惴?，其主要思想是將經(jīng)典劃分的定義模糊化，可以認(rèn)為數(shù)據(jù)點(diǎn)以某種隸屬度屬于一個(gè)簇團(tuán)，又以某種隸屬度屬于其它簇團(tuán)。

在眾多的模糊聚類算法中，應(yīng)用最廣泛而且較成功的是1974年由Dunn提出并由Bezdek加以推廣的模糊C-均值(fuzzy C-means，簡稱FCM)算法。同樣，F(xiàn)CM算法是把n個(gè)向量 (I=1,2,…,n)分成m個(gè)模糊簇團(tuán) ，并求得每個(gè)簇團(tuán)的聚類中心,使目標(biāo)函數(shù)達(dá)到最小，F(xiàn)CM的目標(biāo)函數(shù)定義為：

由于多約束優(yōu)化問題的求解是一個(gè)NPC問題，常用的求解方法是分別對U和C進(jìn)行偏優(yōu)化的Fk-prototypes 算法[8]，主要思想是：（1）先選擇C的一個(gè)初始值，找到使 最小的U值；（2）然后固定U找到使 最小的C；（3）優(yōu)化過程交替進(jìn)行，直到前后目標(biāo)函數(shù)的差值與目標(biāo)函數(shù)的比小于ε為止。

這一算法的缺陷在于需要賦予不同的c值進(jìn)行多次重復(fù)計(jì)算，且結(jié)果通常是局部最優(yōu)解，同時(shí)運(yùn)算時(shí)間是很大的，因?yàn)橐淮尉仃嚦朔ㄋ枰臅r(shí)間為O(n3)，實(shí)現(xiàn)算法的第一步的時(shí)間復(fù)雜度就達(dá)到O(n4logn)。

2.3用蟻群算法改進(jìn)模糊聚類

提高模糊聚類計(jì)算速度的關(guān)鍵之一是隸屬度矩陣的初始點(diǎn)的選取，如果能開始就得到每個(gè)參數(shù)點(diǎn)歸于每個(gè)簇團(tuán)的隸屬度近似結(jié)果，那么將較大的改進(jìn)模糊聚算法的速度，蟻群算法就可以實(shí)現(xiàn)這以功能。

其基本思想是將數(shù)據(jù)視為具有不同屬性的螞蟻，聚類中心看作是螞蟻所要尋找的“食物源”[9]，所以數(shù)據(jù)聚類就看作是螞蟻尋找食物源的過程。具體過程如下：每只螞蟻從各個(gè)聚類中心出發(fā)，在整個(gè)解空間中搜索到下一個(gè)樣本點(diǎn)后；再從聚類中心出發(fā)，在整個(gè)解空間中搜索到另一個(gè)樣本點(diǎn)，當(dāng)搜索到樣本點(diǎn)達(dá)到該聚類原來的樣本點(diǎn)總數(shù)后，就認(rèn)為螞蟻完成了一個(gè)路徑的搜索。為使螞蟻在同一路徑的搜索中不重復(fù)搜索同一個(gè)樣本點(diǎn)，給每只螞蟻設(shè)置禁忌表tabu(N)。規(guī)定：如果tabu(j)為1，則結(jié)點(diǎn)j是可以選擇的搜索樣本點(diǎn)，當(dāng)螞蟻選擇了結(jié)點(diǎn)j后，就將tabu(j)置為0，此時(shí)螞蟻就不能選擇結(jié)點(diǎn)。

設(shè) 是待進(jìn)行聚類分析的數(shù)據(jù)集合，τij(t)表示在t時(shí)刻數(shù)據(jù) 和 之間的信息量。當(dāng)所有螞蟻都完成了一次路徑搜索后，稱算法進(jìn)行了一個(gè)搜索周期。第t個(gè)搜索周期內(nèi)，路徑選擇概率：

其中 ，其他參數(shù)和上面說明一致。在i值確定下，從j=1到m，分析 ，找到最大值后，則 歸并到到 領(lǐng)域。令 ， 表示所有歸并到 的數(shù)據(jù)集合，求出聚類中心當(dāng)蟻群完成一個(gè)搜索周期后，根據(jù) 就得到了每個(gè)參數(shù)點(diǎn)歸于某簇團(tuán)的可能性，從而得到了模糊聚類隸屬度矩陣的大體準(zhǔn)確的初始值，并用 作為模糊聚類的初始中心。

由于蟻群算法本身也有一定的計(jì)算量，不宜在每次模糊聚類循環(huán)中使用蟻群算法，選用蟻群算法的策略是這樣的：首先在步驟1的初始幾個(gè)循環(huán)選用蟻群算法和確定初始值 （本文設(shè)為4個(gè)）和聚類的中心 ，然后根據(jù)公式4和5，模糊聚類自己循環(huán)迭代，當(dāng)優(yōu)化過程趨緩時(shí)，再采用一到兩次蟻群算法進(jìn)行優(yōu)化，一直得到小于ε的結(jié)果為止。

2.4根據(jù)聚類結(jié)果建立神經(jīng)網(wǎng)絡(luò)預(yù)測模型

由于電力系統(tǒng)由各種因素強(qiáng)烈影響，存在著大量的非線性關(guān)系。其發(fā)展規(guī)律很難用一個(gè)顯式的數(shù)學(xué)公式表示，許多文獻(xiàn)利用神經(jīng)網(wǎng)絡(luò)對復(fù)雜非線性擬合能力的優(yōu)點(diǎn)，構(gòu)造預(yù)測模型。文獻(xiàn)[6]采用了3層BP網(wǎng)絡(luò)建立預(yù)測模型，文獻(xiàn)[10]采用了徑向基函數(shù)神經(jīng)網(wǎng)絡(luò)對電力負(fù)荷進(jìn)行預(yù)測。本文經(jīng)過比較和分析，發(fā)現(xiàn)采用MATLAB提供的動量BP神經(jīng)網(wǎng)絡(luò)計(jì)算結(jié)果比較好。由此，將歷史數(shù)據(jù)聚成簇團(tuán)以后，采用動量BP神經(jīng)網(wǎng)絡(luò)構(gòu)造預(yù)測模型，此組合模型也稱之為AFCBP模型。進(jìn)行預(yù)測時(shí)，首先逐一計(jì)算預(yù)測天與各聚類中心的歐基里德距離，以距離最短的類別作為預(yù)測天的類別，再利用相應(yīng)AFCBP模型進(jìn)行預(yù)測。

3實(shí)際應(yīng)用

3.1聚類分析

本文以某地區(qū)一年的電力負(fù)荷變化數(shù)據(jù)為對象進(jìn)行實(shí)例分析, 把全年的366條負(fù)荷曲線的樣本的負(fù)荷曲線作為測試樣本以后，進(jìn)行聚類分析。每一樣本 由29個(gè)數(shù)據(jù)組成即為第i天最高溫度和最低溫度為對第i+1天的最高溫度和最低溫度的預(yù)報(bào)值為第i+1天的天類別值。

在采用蟻群算法優(yōu)化（用 表示）的模糊聚類算法時(shí)，計(jì)算 的參數(shù)設(shè)為：ρ=0.7，a=1，b=1,η=1,ε=0.01, τij(0)=0。

3.2預(yù)測實(shí)例

采用上述方法建立預(yù)測模型以后，首先對負(fù)荷進(jìn)行負(fù)荷預(yù)測。并與基于單一神經(jīng)網(wǎng)絡(luò)的預(yù)測模型和僅用模糊聚類的組合模型進(jìn)行比較。這里用于對比的基于單一神經(jīng)網(wǎng)絡(luò)的預(yù)測模型采用MATLAB提供的動量BP神經(jīng)網(wǎng)絡(luò)，網(wǎng)絡(luò)的樣本簡單地選取了預(yù)測天前4星期的負(fù)荷數(shù)據(jù)，統(tǒng)計(jì)誤差結(jié)果如表1 所示。結(jié)果表明：預(yù)測任何種類的日負(fù)荷，采用AFCBP模型和FCBP模型要遠(yuǎn)遠(yuǎn)好于僅采用動量BP神經(jīng)網(wǎng)絡(luò)的預(yù)測模型，這充分說明了采用組合式神經(jīng)網(wǎng)絡(luò)預(yù)測模型的優(yōu)勢；AFCBP模型和FCBP模型在預(yù)測普通工作日的負(fù)荷都比較穩(wěn)定，AFCBP模型僅比FCBP模型略好一些，這是因?yàn)榫垲惔貓F(tuán)中普通工作日樣本數(shù)據(jù)較多，兩種模型預(yù)測都比較好；在預(yù)測雙休日和節(jié)假日時(shí)，AFCBP模型具有更好的預(yù)測精度，這是因?yàn)锳FCBP模型聚類的效果更細(xì)致、更準(zhǔn)確的結(jié)果。

然后分析兩種模型對夏季典型日負(fù)荷預(yù)測的結(jié)果。如圖1所示，可以發(fā)現(xiàn)采用AFCBP預(yù)測模型整體上要比FCBP預(yù)測模型效果要好，尤其在邊緣點(diǎn)和變化劇烈區(qū)域預(yù)測結(jié)果較好。平均絕對百分誤差 和最大絕對百分誤差 的數(shù)值也反映了這一點(diǎn)。

圖1：典型負(fù)荷預(yù)測結(jié)果比較

4結(jié)論

本文把蟻群算法和c-means算法相結(jié)合，把螞蟻k由城市i轉(zhuǎn)移到城市j的概率 作為隸屬度矩陣的初值，計(jì)算出的中心作為FCM的初始中心，對模糊聚類進(jìn)行改進(jìn)，得到較好結(jié)果，并以每天的24 點(diǎn)負(fù)荷數(shù)據(jù)、天氣數(shù)據(jù)以及天類別數(shù)據(jù)為指標(biāo)，用改進(jìn)后模糊聚類把歷史數(shù)據(jù)聚分成若干簇團(tuán)；然后，采用動量BP神經(jīng)網(wǎng)絡(luò)針對每一簇團(tuán)建立相應(yīng)的預(yù)測模型。對山東地區(qū)1年的實(shí)際負(fù)荷變化數(shù)據(jù)進(jìn)行預(yù)測分析的結(jié)果表明，該模型不僅對普通工作日有較高的預(yù)測精度，對雙休日、節(jié)假日和一些特殊情況（夏季典型日負(fù)荷）也有較好的預(yù)測精度。

參考文獻(xiàn)：

[1] 周繼薌. 實(shí)用回歸分析[M]. 上海: 上?？茖W(xué)技術(shù)出版社,1990.

[2] Burke J J , et al . Power quality-two different perspectives [J]. IEEE Transaction on Power Delivery, 1990,(3).

[3] Verdelho P , et al . An active filter and unbalanced current compensator [J]. IEEE Transaction on Power Electronics , 1997(3).

[4] Gerbec D，Gasperic S，Smon I et al． An approach to customers daily load profile determination [C]. IEEE Power Engineering Society Summer Meeting，Chicago，IL USA，2002(1).

[5] Papadakis S E，Theocharis J B，Bakirtzis A G．A load curve based fuzzy modeling technique for short-term load forecasting.[J] Fuzzy Sets and Systems, 2003(2).

[6] 陳耀武, 汪樂宇, 龍洪玉等. 基于組合式神經(jīng)網(wǎng)絡(luò)的電力負(fù)荷預(yù)測模型[J]. 中國電機(jī)工程學(xué)報(bào),2001(4).

[7] Dorigo, M., Maniezzo, V., Colorni, A., 1996. Ant system: optimizationby a colony of cooperating agents. IEEE Trans. Syst. Man Cybernet. B (1).

[8] 陳寧, 陳安, 周龍?bào)J. 數(shù)值型和分類型混合數(shù)據(jù)的模糊K-Prototypes聚類算法[J]. 軟件學(xué)報(bào), 2001(8).

篇9

【關(guān)鍵詞】 TSP問題 數(shù)學(xué)模型 智能優(yōu)化算法

隨著我國經(jīng)濟(jì)的持續(xù)快速發(fā)展，人們對交通運(yùn)輸?shù)母鞣N需求也顯著增長。從1999年到2010年，我國公路總長度從130萬公里上升到370萬公里，增長幅度為185%，同期我國注冊的車輛數(shù)量由1500萬輛上升到8000萬輛，增長幅度為433%，明顯高于中國公路總長的增長幅度。由于車輛數(shù)量的激增，導(dǎo)致城市交通擁堵嚴(yán)重，交通事故頻發(fā)，物流成本居高不下，物流時(shí)效性也無法得到保證。我國物流成本占GDP的比重持續(xù)偏高，約為20%，遠(yuǎn)高于發(fā)達(dá)國家物流成本占GDP的比重10%，以及中等發(fā)達(dá)國家的16%。而城市閑置土地資源的緊缺，導(dǎo)致修建和拓寬道路的成本越來越高，且修建和拓寬道路的速度遠(yuǎn)遠(yuǎn)趕不上城市車輛的增長速度，此時(shí)提高城市道路的利用率、安全性和舒適性以及降低城市物流成本就成為我們急需解決的問題。

物流配送調(diào)度系統(tǒng)就是針對以上問題提出的，它能提供可靠的交通信息、高效快速的應(yīng)急服務(wù)，在降低物流成本方面有著顯著的成效，能滿足現(xiàn)代物流經(jīng)濟(jì)性、準(zhǔn)時(shí)性和靈活性的多種需求。迄今為止，國外研究物流配送調(diào)度系統(tǒng)的理論和算法已經(jīng)不少，并且在實(shí)際應(yīng)用方面取得顯著的成果，如美國IBM基于最短路徑法和啟發(fā)式算法研究出來的VSPX系統(tǒng)，日本富士通以節(jié)約法為核心研發(fā)出來的VSS系統(tǒng)，以及美國美孚以掃描法為核心研究出來的HPCAD系統(tǒng)。但是國內(nèi)在這方面的研究僅停滯于初步理論階段，在開發(fā)實(shí)用的物流配送調(diào)度系統(tǒng)方面還是一片空白。造成這種現(xiàn)象的根本原因在于大部分算法只考慮了TSP（Traveling salesman problem）問題的部分約束條件，且設(shè)置了許多假設(shè)條件，限制了他們的應(yīng)用范圍，在實(shí)際應(yīng)用中缺乏靈活性。由于研發(fā)物流配送調(diào)度系統(tǒng)的核心在于解決貼合實(shí)際的TSP問題，因此研究可以妥善解決TSP問題的算法，并在此基礎(chǔ)上開發(fā)出智能的物流配送調(diào)度系統(tǒng)具有現(xiàn)實(shí)的理論意義和實(shí)踐意義。

一、TSP問題

1、TSP問題的簡介

TSP問題也稱旅行推銷員問題、貨郎擔(dān)問題，是經(jīng)典的組合優(yōu)化問題，最早的記錄來自于1759年歐拉研究的騎士周游問題，即對象棋中的64個(gè)方格，走訪每個(gè)方格有且僅有一次。TSP問題的歷史可以分成以下幾個(gè)階段：1800―1900年，首次描述TSP問題；1920―1930年，TSP問題得到較好的定義；1940―1950年，研究人員意識到TSP問題是個(gè)難題；1954年，42個(gè)城市的TSP問題求得最優(yōu)解；1980年，Crowder和Padberg求解了318個(gè)城市的問題；1987年，Padberg和Rinaldi求解了2392個(gè)城市的問題；1992年，美國Rice大學(xué)的CRPC研究小組解決了3038個(gè)城市的問題；1994年，Applegate、Bixby和Chvatal等人解決了7393個(gè)城市的問題；1998年，CRPC研究解決了美國13509個(gè)城市組成的TSP問題；2003年，Hisao Tamaki發(fā)現(xiàn)了TSPLIB中pla33810的一個(gè)次優(yōu)解；2004年，Keld Helsguan 發(fā)現(xiàn)了pla85900問題的一個(gè)次優(yōu)解。

2、TSP問題的數(shù)學(xué)模型

二、求解TSP問題的各種解法

目前求解TSP問題的主要方法主要分兩類：精確求解算法和近似求解算法。

精確求解算法通過搜索整個(gè)問題的全部解空間，在所有解集中求得最優(yōu)解。精確求解算法包括整數(shù)規(guī)劃法、動態(tài)規(guī)劃法、分支定界算法等，這類算法雖然可以得到精確解，但由于過大的搜索空間范圍導(dǎo)致計(jì)算時(shí)間過長，計(jì)算效率非常低下，很少用于實(shí)際應(yīng)用。最早用于解決TSP問題的精確求解算法是窮舉法，思路簡單，可以直觀快速地求出少量城市點(diǎn)數(shù)的最優(yōu)解，但是求解大規(guī)模數(shù)據(jù)集時(shí)運(yùn)算量太大，運(yùn)算效率不高，時(shí)間上難以承受。

近似求解法又可稱為啟發(fā)式求解算法，部分近似求解算法又被稱為智能優(yōu)化算法。典型的近似算法有插入算法、r-opt算法和最近鄰算法等，這類算法雖然可以較快的計(jì)算出可行解，但是其接近最優(yōu)解的程度不夠令人滿意。智能優(yōu)化算法主要包括神經(jīng)網(wǎng)絡(luò)算法、遺傳算法、禁忌搜索算法、模擬退火法、粒子群算法和蟻群算法等，是近幾年來非?；钴S的研究領(lǐng)域，它是利用仿生學(xué)的原理，讓算法在計(jì)算過程中不斷自我調(diào)整，使之具備自適應(yīng)能力。智能優(yōu)化算法雖然不能在有限的時(shí)間內(nèi)獲得最優(yōu)解，但其接近最優(yōu)解的程度是非?？上驳摹?/p>

求解TSP問題的算法很多，要評價(jià)和比較各種算法的優(yōu)劣，必須有一個(gè)綜合的性能評價(jià)標(biāo)準(zhǔn)，TSP算法的綜合性能評價(jià)標(biāo)準(zhǔn)包括：算法求解的精確程度，即接近最優(yōu)解的程度；求解算法的復(fù)雜度，包括時(shí)間的復(fù)雜度和空間的復(fù)雜度；求解算法的適應(yīng)性，即算法在各個(gè)領(lǐng)域的通用程度；求解算法的嚴(yán)密性，即保證求解算法充分的理論基礎(chǔ)。

綜合比較，智能優(yōu)化算法是一類綜合性能比較強(qiáng)的TSP算法，也是目前最適合用于開發(fā)物流配送調(diào)度系統(tǒng)的算法，本文將對幾種智能優(yōu)化算法進(jìn)行詳細(xì)說明。

1、神經(jīng)網(wǎng)絡(luò)算法

人工神經(jīng)網(wǎng)絡(luò)（Artificial Neural Network,簡稱ANN），又名神經(jīng)網(wǎng)絡(luò)（Neural Network,簡稱NN），是一種通過模擬動物神經(jīng)網(wǎng)絡(luò)的特點(diǎn)進(jìn)行數(shù)據(jù)分析的方法。1985年，Hopfield和Tank首次將這種算法應(yīng)用于求解TSP問題。它的主要思想是用能量函數(shù)替代TSP問題中的目標(biāo)函數(shù)，通過能量函數(shù)確定神經(jīng)元之間的相互連接權(quán)限，隨著網(wǎng)絡(luò)狀態(tài)的逐漸變化，當(dāng)能量達(dá)到平衡時(shí)，就可以得到局部最優(yōu)解。

由于神經(jīng)網(wǎng)絡(luò)是一種數(shù)據(jù)驅(qū)動型非線性映射模型，可以實(shí)現(xiàn)任何復(fù)雜的因果關(guān)系映射，能夠從大量的歷史數(shù)據(jù)中進(jìn)行聚類和學(xué)習(xí)，進(jìn)而找到某些行為變化規(guī)律，因此可以用來處理難以用數(shù)學(xué)模型描述的系統(tǒng)，具有很強(qiáng)的并行性、自適應(yīng)、聯(lián)想記憶、容錯(cuò)魯棒以及任意逼近非線性等特性。目前神經(jīng)網(wǎng)絡(luò)技術(shù)在解決TSP問題上取得了一定的成績，但是神經(jīng)網(wǎng)絡(luò)存在嚴(yán)重缺陷，很難確定算法的參數(shù)，必須通過多次反復(fù)的數(shù)據(jù)測試才能獲得一個(gè)相對較好的參數(shù)，因此嚴(yán)重限制了神經(jīng)網(wǎng)絡(luò)的適用范圍。

2、遺傳算法

遺傳算法是Holland于1973年首次提出的，是一種模擬生物界自然選擇和遺傳機(jī)制的隨機(jī)搜索算法。它的基本思想是將TSP問題的求解表示成“染色體”的適者生存的過程，通過“染色體”的一代代的進(jìn)化，即通過選擇、交叉和變異等操作，最終得到“最適應(yīng)環(huán)境”的個(gè)體，從而求得最優(yōu)解或滿意解。

遺傳算法能準(zhǔn)確模擬自然界生物進(jìn)化過程中的染色體，整個(gè)遺傳過程操作簡單，在數(shù)據(jù)優(yōu)化過程中不受外界條件的限制，能用簡單的計(jì)算方法實(shí)現(xiàn)全局解空間的搜索。但是遺傳算法中容易出現(xiàn)“早熟”現(xiàn)象，必須通過設(shè)置變異概率來控制“早熟”，高的變異率擴(kuò)大了搜索空間，有利于誘導(dǎo)產(chǎn)生更加優(yōu)秀的個(gè)體，但是交叉概率和變異概率過大會導(dǎo)致收斂速度過慢，迭代次數(shù)過大。因此實(shí)現(xiàn)收斂速度和最優(yōu)解之間的平衡是遺傳算法的一大難點(diǎn)。

3、禁忌搜索算法

禁忌搜索算法是由Fred Glovert等于1986年首次提出的，是一種全局性逐步尋優(yōu)的鄰域搜索算法，可以模擬人類記憶功能的尋優(yōu)特征，通過局部鄰域搜索機(jī)制和相應(yīng)的禁忌準(zhǔn)則來避免重復(fù)搜索，并通過藐視準(zhǔn)則赦免一些被禁忌的優(yōu)良狀態(tài)，進(jìn)而保證多樣化的有效搜索，最終實(shí)現(xiàn)全局優(yōu)化。

在禁忌搜索算法的搜索過程中，鄰域結(jié)構(gòu)、候選解、禁忌長度、禁忌對象、藐視準(zhǔn)則、終止準(zhǔn)則等都是影響算法性能的關(guān)鍵因素。且禁忌搜索算法對初始解和鄰域結(jié)構(gòu)有較大的依賴性，由于禁忌算法串行的搜索機(jī)制，一個(gè)不理想的初始解將直接影響到搜索質(zhì)量。

4、模擬退火法

現(xiàn)代模擬退火算法是由Kirkpatrick S等于1983年提出，是基于Mente Carlo迭代求解策略的一種隨機(jī)尋優(yōu)算法。它通過模擬物理中固體物質(zhì)的退火過程，結(jié)合具有概率突跳特性的Metropolis抽樣策略，在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，在降溫過程中不斷重復(fù)抽樣，最終實(shí)現(xiàn)問題的最優(yōu)解。

模擬退火算法解的優(yōu)越性依賴初始溫度和退火時(shí)間，當(dāng)初始溫度過低或者退火速度過快，算法將陷入局部最優(yōu)解。但是如果迭代次數(shù)較高，隨著退火速度的降低將極大增加運(yùn)行時(shí)間。

5、蟻群算法

蟻群算法是由意大利學(xué)者Dorigo M于1991年首次提出，是一種模擬自然界螞蟻尋找食物的過程來計(jì)算路徑的算法，通過群體間信息素的交換和相互合作尋求最優(yōu)解的過程。螞蟻獨(dú)立尋找食物，在找尋食物的路程中會釋放信息素，信息素會影響隨后的螞蟻對路徑的選擇，信息素越強(qiáng)的路徑，越可能被螞蟻選擇。對于螞蟻算法來說，各條路徑的初始信息素相同，但是隨著時(shí)間的推移，較優(yōu)路徑上的信息素會越來越多，最后實(shí)現(xiàn)尋求最優(yōu)解或次優(yōu)解的目的。

螞蟻算法中，螞蟻數(shù)量M的設(shè)置是影響算法性能的重要因素，M過小會導(dǎo)致未被所搜索過的路徑信息素趨向于0，全局搜索能力太差，穩(wěn)定性變差。M過大會導(dǎo)致所有路徑上的信息素過于平均，隨機(jī)性太強(qiáng)，收斂速度過慢，信息正反饋能力過弱。有研究表明，M取值范圍在[0.6n,0.9n]（n代表城市規(guī)模），螞蟻算法的收斂速度和接近全局最優(yōu)解的能力最理想。

在螞蟻算法中，總信息量Q表示循環(huán)一周螞蟻釋放的信息素的總和，Q也同樣對螞蟻算法的性能有很大的影響。Q越大信息素增長越快，正反饋效果越好，算法收斂速度越快。研究表明，Q的取值與TSP問題的規(guī)模和路徑長度有關(guān)，在小規(guī)模的TSP問題中，Q一般取100。

螞蟻算法具有正反饋、并發(fā)性、較強(qiáng)的魯棒性、易于其他算法相結(jié)合等優(yōu)點(diǎn)，但是螞蟻算法易出現(xiàn)停滯現(xiàn)象。

【參考文獻(xiàn)】

[1] 國家發(fā)展和改革委員會經(jīng)濟(jì)運(yùn)行調(diào)節(jié)局、南開大學(xué)現(xiàn)代物流研究中心：中國現(xiàn)代物流發(fā)展報(bào)告（2010）[M].中國物資出版社，2010.

[2] 唐納德, J.鮑爾索科斯、戴維J.克勞斯：物流管理[M].機(jī)械工業(yè)出版社，1999.

篇10

【關(guān)鍵詞】計(jì)算機(jī)智能 群體智能 算法

計(jì)算機(jī)技術(shù)不斷發(fā)展，算法技術(shù)也在不斷更新。群體智能（Swarm Intelligent，SI）算法始于20世紀(jì)90年代初，主要是受自然界生物群體智能現(xiàn)象的啟發(fā)，通過模仿社會性動物的行為，而提出的一種隨機(jī)優(yōu)化算法。群體智能是基于種群行為對給定的目標(biāo)進(jìn)行尋優(yōu)的啟發(fā)式搜索算法，其的核心是由眾多簡單個(gè)體組成的群體能夠通過相互之間的簡單合作來實(shí)現(xiàn)某一較復(fù)雜的功能。所以群體智能可以在沒有集中控制并且缺少全局信息和模型的前提下，為尋找復(fù)雜的分布式問題的解決方案提供了基礎(chǔ)。

1 傳統(tǒng)群體智能算法

1.1 蟻群算法（ACO）

1991年意大利學(xué)者Dorigo M等受到自然界中蟻群覓食行為啟發(fā)而提出了蟻群算法（Ant Colony Optimization，ACO）。蟻群算法的基本理念是蟻群生物性的利用最短路徑的根據(jù)局部信息調(diào)整路徑上的信息素找尋的特征，這個(gè)算法的優(yōu)勢非常的明顯，而且具有較為突出的應(yīng)用性，在這個(gè)過程中螞蟻可以逐步地構(gòu)造問題的可行解，在解的構(gòu)造期間，每只螞蟻可以使用概率方式向下一個(gè)節(jié)點(diǎn)跳轉(zhuǎn)，而且由于這個(gè)節(jié)點(diǎn)是具有較強(qiáng)信息素和較高啟發(fā)式因子的方向，直至無法進(jìn)一步移動。此時(shí)，螞蟻所走路徑對應(yīng)于待求解問題的一個(gè)可行解。蟻群算法目前已成功地用于解決旅行商TSP問題、數(shù)據(jù)挖掘、二次指派問題、網(wǎng)絡(luò)路由優(yōu)化、機(jī)器人路徑規(guī)劃、圖著色、物流配送車輛調(diào)度、PID控制參數(shù)優(yōu)化及無線傳感器網(wǎng)絡(luò)等問題。

1.2 人工魚群算法（AFO）

2002年由我國的李曉磊等受魚群運(yùn)動行為的啟發(fā)而提出了人工魚群算法（Artificial Fish-Swarm Algorithm，AFSA）。人工魚群算法的思想主要是利用魚個(gè)體的四種行為（覓食、聚群、追尾和隨機(jī)）的特征，通過技術(shù)應(yīng)用將人工魚隨機(jī)地分布于解空間中，解空間中包含著若干局部最優(yōu)值和一個(gè)全局最優(yōu)值。在進(jìn)行應(yīng)用時(shí)，可以有效的利用相關(guān)特點(diǎn)進(jìn)行，特別是應(yīng)用的尋優(yōu)期間，每次迭代執(zhí)行完，人工魚都將對比自身狀態(tài)和公告板狀態(tài)，如自身具有優(yōu)勢，則更新公告板狀態(tài)，確保公告板為最優(yōu)狀態(tài)。 人工魚群算法已在參數(shù)估計(jì)、組合優(yōu)化、前向神經(jīng)網(wǎng)絡(luò)優(yōu)化、電力系統(tǒng)無功優(yōu)化、輸電網(wǎng)規(guī)劃、邊坡穩(wěn)定、非線性方程求解等方面得到應(yīng)用，且取得了較好的效果。

1.3 蜂群算法（ABC）

人工蜂群算法（ABC）是一種非數(shù)值優(yōu)化計(jì)算方法。人工蜂群算法的思想是：將虛擬蜜蜂群初始時(shí)隨機(jī)分布在解空間中，將食物源的位置抽象成解空間中的點(diǎn)（可行解）。蜂群算法由3個(gè)基本要素構(gòu)成：蜜源、采蜜蜂和待工蜂。在蜜蜂與外部環(huán)境的交流中蜜蜂通過自身的反應(yīng)閥值（threshold）和外界的激勵(lì)信號（stimulation）來自行安排工作。

1.4 粒子群算法（PSO）

PSO（粒子群算法）是一種新興的基于群體智能的啟發(fā)式全局搜索算法，具有易理解、易實(shí)現(xiàn)、全局搜索能力強(qiáng)等特點(diǎn)。粒子群算法模擬鳥群的捕食行為，通過群聚而有效的覓食和逃避追捕。在鳥群的捕食過程中，個(gè)體之間存在著信息的交換與協(xié)作，整個(gè)群體中信息是共享，每個(gè)個(gè)體的行為是建立在群體行為的基礎(chǔ)之上?？梢栽O(shè)想這樣一個(gè)場景：一群鳥在隨機(jī)搜索食物，每只鳥在初始狀態(tài)下處于隨機(jī)位置，且朝各個(gè)方向隨機(jī)飛行，在這個(gè)區(qū)域里只有一塊食物，所有的鳥都不知道食物在那里，但隨著時(shí)間推移，處于隨機(jī)狀態(tài)的鳥通過搜尋目前離食物最近的鳥的周圍區(qū)域，聚集成一個(gè)個(gè)小的群落，并最終將整個(gè)群落聚集在食源的位置。受到這種模型的啟示，在PSO算法中，優(yōu)化問題的解都是被稱為“粒子”。通過類似于鳥群捕食的方式，追隨當(dāng)前的最優(yōu)粒子在解空間中搜索，并最終找到最優(yōu)解。

2 混合群體智能優(yōu)化方法

2.1 基于PSO的混合優(yōu)化算法

傳統(tǒng)的粒子群算法在低維空間上，可以快速高效尋找最優(yōu)解，但隨著函數(shù)維數(shù)的增加，容易陷入局部極值，導(dǎo)致收斂精度低。而混合粒子群算法是在標(biāo)準(zhǔn)粒子群算法中加入進(jìn)化算法，保證了群體的多樣性，快速收斂效果和避免陷入局部極值的能力。混合粒子群算法利用選擇機(jī)制改進(jìn)的算法將每個(gè)個(gè)體的適應(yīng)度，并與幾個(gè)其它個(gè)體進(jìn)行比較，記下最差的一個(gè)點(diǎn)，通過這種方式排序之后，最高的得分出現(xiàn)在群體最前面，逐步淘汰掉較差的區(qū)域，因此可以更加合理地分配有限的資源。在雜交算子改進(jìn)的PSO中，將粒子群算法與雜交算子的結(jié)合，在該種算法運(yùn)行過程中根據(jù)適應(yīng)度的大小，粒子之間可以兩兩雜交，這個(gè)雜交概率是隨機(jī)的。經(jīng)過雜交操作，將隨機(jī)產(chǎn)生粒子的最新位置。這種雜交操作只改變了粒子的方向，而沒有改變粒子的數(shù)量，保證群體的多樣性，避免陷入局部極值。因此應(yīng)用了雜交算子的粒子群算法比傳統(tǒng)粒子群算法效率更高。

2.2 基于BFO的混合優(yōu)化算法

BFO（細(xì)菌覓食算法）來源于細(xì)菌的群體行為特性，是近年來研究提出的一種新的算法。BFO搜索通過群體細(xì)菌之間的競爭和協(xié)作，實(shí)現(xiàn)搜索的優(yōu)化。關(guān)于BFO混合算法目前的研究結(jié)果基本是加入PSO的機(jī)理來解決函數(shù)優(yōu)化問題，通過對分析各種算子的步長以及細(xì)菌的生存期的過濾，從而實(shí)現(xiàn)算法性能的提高。近年來，Kim和Abraham又將遺傳算法引入BFO，該算法結(jié)合了BFO算法中大腸桿菌的覓食機(jī)制菌和PSO算法中的鳥類云集模式。基于BFO和PSO提出一種混合優(yōu)化算法，解決了多模態(tài)高維函數(shù)的優(yōu)化，提高了對高維函數(shù)優(yōu)化的收斂速度和局部搜索能力。

2.3 自適應(yīng)菌群約束優(yōu)化算法

自適應(yīng)菌群約束優(yōu)化算法是基于BFO提出了一種處理約束優(yōu)化問題新方法。該算法引入Tent混沌方法對符合遷徙條件的細(xì)菌進(jìn)行位置初始化，并加入了基于佳點(diǎn)集的交叉算子，使得遷徙后的新菌群具有隨機(jī)性的特點(diǎn)，使群體均勻的分布在搜索空間中，有跳出局部最優(yōu)的可能；同時(shí)選擇精英細(xì)菌作為混沌映射的初始解，趨藥性步長的自適應(yīng)變化使得算法避免了在最優(yōu)值附近的振蕩，并能夠在維持菌群總數(shù)不變的同時(shí)得到質(zhì)量更優(yōu)的細(xì)菌新個(gè)體，擴(kuò)大精英群體的規(guī)模。

3 結(jié)束語

由于科學(xué)技術(shù)不斷進(jìn)步，許多應(yīng)用領(lǐng)域涉及因素、規(guī)模以及難度也越來越高，面對的優(yōu)化問題日益復(fù)雜化，這些常規(guī)的優(yōu)化算法都遠(yuǎn)不能滿足要求。而混合智能優(yōu)化方法，計(jì)算簡單，易于實(shí)現(xiàn)，能夠在復(fù)雜的問題中快速有效的得到最優(yōu)解。鑒于智能算法的混合結(jié)構(gòu)很多，關(guān)于群體智能優(yōu)化算法的混合算法還有待進(jìn)一步研究。

參考文獻(xiàn)

[1]李俊.群體智能融合算法研究及其應(yīng)用[D].南昌航空大學(xué)，2013.

[2]向萬里.混合群體智能優(yōu)化算法及應(yīng)用研究[D].天津大學(xué)，2014.

[3]馮月華，陳州吉.基于群體智能的蟻群算法原理及應(yīng)用研究[J].蘭州文理學(xué)院學(xué)報(bào)（自然科學(xué)版），2014，02期.

作者簡介

劉利波（1983-），男，河南省濟(jì)源市人。碩士學(xué)位?，F(xiàn)為新疆輕工職業(yè)技術(shù)學(xué)院講師。研究方向計(jì)算機(jī)軟件技術(shù)。

作者單位