裝備搶修車多目標(biāo)路徑優(yōu)化

李眾　謝曉東　余選召　吳迪

摘 要：針對戰(zhàn)場搶修工作的特點(diǎn)，建立了考慮安全性、時(shí)間損耗等因素的多目標(biāo)路徑優(yōu)化模型，采用蟻群算法對問題求解，并對蟻群算法進(jìn)行改進(jìn)，提升了算法的收斂速度。

關(guān)鍵詞：搶修車；多目標(biāo)；路徑優(yōu)化；蟻群算法

1 基于功效函數(shù)法[1]的搶修車路徑優(yōu)化模型

⑴優(yōu)化目標(biāo)：1）安全性：安全性表現(xiàn)為安全通過概率。2）道路狀況：道路狀況表現(xiàn)為路面良好程度。3）時(shí)間損耗：時(shí)效性是戰(zhàn)時(shí)主要考慮的因素。4）機(jī)動距離：機(jī)動距離對應(yīng)著機(jī)動費(fèi)用。

⑵利用層次分析法確定指標(biāo)權(quán)重，本文采用1～9標(biāo)度。

⑶設(shè)有m條備選路段，n項(xiàng)評估指標(biāo)，共有L條可選路線，共有p個(gè)節(jié)點(diǎn)。備選路段d的各項(xiàng)評估指標(biāo)數(shù)值為：{cd}={cd（1），cd（2），…cd（e），…cd（n）}，e=1，2…n。

①指標(biāo)無量綱化處理方法

顯然，處理后的指標(biāo)yd（e）越小，表明備選路段d的評估指標(biāo)e評價(jià)越優(yōu)。

②建立目標(biāo)函數(shù)：

Sij、Rij、Tij、Eij分別為路段（i，j）的安全性、道路狀況、時(shí)間損耗、機(jī)動距離；式（5）表示任意路段只通過一次，式（6）表示一系列路段連通性約束。

2 最短路算法[2]

改進(jìn)蟻群算法[3，4]（采用蟻周系統(tǒng)）：

⑴選擇概率改進(jìn)：q和q0都是[0，1]之間的隨機(jī)數(shù)。

⑵懲罰策略：引入懲罰因子pn對路段進(jìn)行懲罰。

式中， 和 分別表示懲罰前后路段（i，j）上的信息素濃度。

3 算法驗(yàn)證與分析

搶修車由V1出發(fā)至V10對戰(zhàn)損裝備進(jìn)行搶修，要求進(jìn)行路徑優(yōu)化，尋找最優(yōu)路徑。

S、R、T、E的權(quán)重分別為：0.1268、0.2612、0.5224、0.0897。對各指標(biāo)值進(jìn)行無量綱化處理，采用功效函數(shù)法得出各路段的綜合分?jǐn)?shù)。

基本和改進(jìn)蟻群算法求最優(yōu)路徑，得出最優(yōu)路徑：1->2->5->8->10，最優(yōu)路徑值：5.6748。參數(shù)設(shè)置：M=30、α=1、β=1、C=100、Q=10、ρ=0.65、pn=0.3、循環(huán)30次。

基本蟻群算法在第8次循環(huán)之后收斂，改進(jìn)蟻群算法第1次循環(huán)即收斂，通過改進(jìn)提高了蟻群算法的收斂速度。

4 結(jié)語

從戰(zhàn)時(shí)角度出發(fā)，建立了基于功效函數(shù)的搶修車路徑優(yōu)化模型，改進(jìn)了基本蟻群算法，通過實(shí)例驗(yàn)證，證明改進(jìn)蟻群算法具有更快的收斂速度，適于求解最優(yōu)路徑問題。

[參考文獻(xiàn)]

[1]百度百科.功效函數(shù)法.http：//baike.baidu.com/view/1796103.htm.

[2]施寅躍.城市道路網(wǎng)中蟻群最短路徑算法研究[D].南京理工大學(xué)，2010.06.

[3]段海濱.蟻群算法原理及其應(yīng)用[M].北京：科學(xué)出版社，2005.12.

[4]Badr A，F(xiàn)ahmy A.A proof of convergence for ant algorithms[J].International journal of Intelligent Computing and Information，2003，3（1）：22-32.