基于混合算法的導(dǎo)彈部隊(duì)鐵路機(jī)動(dòng)路徑選擇

詹仁超，李應(yīng)岐

(第二炮兵工程大學(xué)，西安 710025)

我國(guó)鐵路網(wǎng)縱橫交錯(cuò)，十分復(fù)雜，平時(shí)導(dǎo)彈列車可以像普通列車一樣在鐵路上運(yùn)行，但戰(zhàn)時(shí)，我們的一舉一動(dòng)都處于敵人的嚴(yán)密監(jiān)視之下。如何選擇合適的機(jī)動(dòng)策略，是完成機(jī)動(dòng)作戰(zhàn)任務(wù)面臨的首要問題。本文主要對(duì)戰(zhàn)略導(dǎo)彈列車機(jī)動(dòng)中的路線選擇進(jìn)行了研究，其意義主要表現(xiàn)在2 個(gè)方面。第一，具有很好的實(shí)用價(jià)值。在未來作戰(zhàn)中，武器的運(yùn)輸都將面臨路線選擇問題且必須快速做出決策。對(duì)于戰(zhàn)略導(dǎo)彈而言，做出的決策是否可行，將直接關(guān)系到戰(zhàn)爭(zhēng)的進(jìn)程甚至戰(zhàn)爭(zhēng)的勝負(fù)。對(duì)這些問題進(jìn)行深入細(xì)致的研究，無疑可以為指揮員做出科學(xué)的決策提供可靠的依據(jù)和支持。同時(shí)，對(duì)提高戰(zhàn)略導(dǎo)彈武器的機(jī)動(dòng)能力和生存能力都有重要意義。第二，機(jī)動(dòng)路線的選擇問題，與生活、商業(yè)活動(dòng)中的對(duì)策問題、車輛路徑問題、最短路徑問題有著諸多不同，但是對(duì)這些問題的研究實(shí)質(zhì)上都是對(duì)算法的研究和改進(jìn)，具有一定的理論意義。

1 戰(zhàn)略導(dǎo)彈鐵路機(jī)動(dòng)路線問題建模

1.1 問題的基本描述

在戰(zhàn)略導(dǎo)彈實(shí)施鐵路機(jī)動(dòng)作戰(zhàn)的過程中，所面臨的一個(gè)重要問題就是根據(jù)各種情報(bào)，選擇合適的機(jī)動(dòng)路線［1-2］，以保證我戰(zhàn)略導(dǎo)彈的生存，并最終完成上級(jí)賦予的任務(wù)。

對(duì)這一問題，進(jìn)行如下抽象描述，以便于建立模型:預(yù)警條件下戰(zhàn)略導(dǎo)彈鐵路機(jī)動(dòng)中的路線選擇，就是在根據(jù)敵對(duì)我的偵查監(jiān)視情況(即導(dǎo)彈列車在不同區(qū)域內(nèi)機(jī)動(dòng)被敵發(fā)現(xiàn)的概率p1)，敵方可能采取的打擊手段和在遭受打擊時(shí)我方的生存概率p2，作戰(zhàn)區(qū)的路網(wǎng)情況(即網(wǎng)絡(luò)圖和邊的權(quán)值)、道路周邊的基礎(chǔ)設(shè)施建設(shè)情況(如橋梁和隧道的數(shù)量、可供導(dǎo)彈隱蔽的場(chǎng)所及其分布)等情報(bào)和數(shù)據(jù)，并根據(jù)一定的判斷準(zhǔn)則，確定出1 條或是幾條合理的路線。其實(shí)質(zhì)是一個(gè)在作戰(zhàn)環(huán)境下的車輛路徑問題。由此，我們可以將戰(zhàn)略導(dǎo)彈鐵路機(jī)動(dòng)中的路線選擇問題做出如下數(shù)學(xué)意義上的描述:給定一個(gè)完全圖(鐵路網(wǎng))G=(V，A)，其中V ={v0，v1，…，vn}為圖的頂點(diǎn)集(站點(diǎn)的集合)，A ={(vi，vj)|i≠j，vi，vj∈V)為邊集。矩陣C= ( cij)n×n中的元素cij表示從vi到vj的距離。列車從v0出發(fā)，經(jīng)過某些站點(diǎn)到達(dá)發(fā)射陣地vk(1≤k≤n)。在滿足某些約束條件下，如何安排列車行程，使到達(dá)列車順利到達(dá)vk并完成作戰(zhàn)任務(wù)。

下面給出問題的約束條件:

1)總里程S 約束，列車一次機(jī)動(dòng)里程不大于技術(shù)條件所允許的最遠(yuǎn)機(jī)動(dòng)距離，以保證導(dǎo)彈到達(dá)發(fā)射陣地后具有最佳的技術(shù)狀態(tài)。

2)時(shí)間T 約束，即導(dǎo)彈列車必須在指定的時(shí)間內(nèi)到達(dá)某陣地，否則將會(huì)貽誤戰(zhàn)機(jī)。

3)生存概率p 約束，所選擇路線必須保證導(dǎo)彈的生存，這是完成任務(wù)的先決條件。

1.2 建立模型與算法步驟

1.2.1 建立模型

在上節(jié)中，給出了問題的基本描述，確定了完全圖(鐵路網(wǎng))G=(V，A)，頂點(diǎn)集(站點(diǎn)的集合)V ={v0，v1，…，vn}，邊集A={(vi，vj)|i≠j，vi，vj∈V)和鄰接矩陣C = ( cij)n×n幾個(gè)主要元素，并給定了總里程S、時(shí)間限制T、生存概率p 幾個(gè)約束條件。

除此之外，還必須確定以下因素:列車在不同路段的實(shí)際機(jī)動(dòng)速度vij和最大機(jī)動(dòng)速度vij0;敵方對(duì)我作戰(zhàn)區(qū)域的監(jiān)視情況，即導(dǎo)彈在不同路段機(jī)動(dòng)時(shí)被發(fā)現(xiàn)的概率pij1;在得到預(yù)警信息后避開敵人打擊的概率，或者說是在預(yù)警條件下敵方采取一定手段對(duì)我實(shí)施打擊后的被擊毀概率pij2。

由于軍事活動(dòng)的特殊性，本文研究的鐵路機(jī)動(dòng)路線的選擇問題，與傳統(tǒng)的VRP 和TSP 問題有許多不同，主要表現(xiàn)在以下幾個(gè)方面:

1)軍事活動(dòng)中，不需要通過圖中所有點(diǎn)，只需要到達(dá)目標(biāo)點(diǎn)。

2)軍事活動(dòng)中，對(duì)同一個(gè)點(diǎn)，在一條路線中可以幾次選擇，也就是說在路線中可以出現(xiàn)回路。

3)軍事活動(dòng)中，機(jī)動(dòng)路線不一定形成回路，也就是說起點(diǎn)與終點(diǎn)很可能不是一個(gè)點(diǎn)。

因此，針對(duì)該問題建模時(shí)，傳統(tǒng)的許多約束條件都可以除去，只考慮與完成作戰(zhàn)任務(wù)相關(guān)的幾個(gè)條件即可。在確定以上所有數(shù)據(jù)之后，便可以得到其數(shù)學(xué)模型:

目標(biāo)函數(shù): maxp

目標(biāo)函數(shù)表示最終確定的機(jī)動(dòng)路線是使得導(dǎo)彈的生存概率最大。這一具體數(shù)值與pij1、pij2、vij、vij0、所選路線的設(shè)施建設(shè)和周圍環(huán)境等因素密切相關(guān)。

1.2.2 算法步驟

GA 具有良好的并行性，TS 則具有很強(qiáng)的“爬山”能力，將兩者結(jié)合，優(yōu)劣互補(bǔ)，將會(huì)有效地提高優(yōu)化算法的效率。本文將遺傳算法和禁忌搜索算法相結(jié)合組成GATS 混合算法［3-5］，即以GA 算法為整個(gè)算法的框架，對(duì)GA 經(jīng)過遺傳操作運(yùn)算后產(chǎn)生的新種群的個(gè)體，用TS 算法進(jìn)行局部搜索［6-7］，改善群體的質(zhì)量，具體步驟如圖1 所示。

需要強(qiáng)調(diào)的是在產(chǎn)生初始群體中，沒有要求列車必須通過每個(gè)站點(diǎn)，也沒有每個(gè)站點(diǎn)只能通過一次的限制，也就是說，染色體的長(zhǎng)度是可變的，而且一條路線中還可能有迂回回路。要產(chǎn)生初始群體，必須確定染色體的長(zhǎng)度，即站點(diǎn)的數(shù)量。

可以通過以下方法確定

對(duì)于具有不同長(zhǎng)度的染色體，本文中將其稱為具有不同的染色體結(jié)構(gòu)。起點(diǎn)和終點(diǎn)是確定的，也就是說染色體最多有m -1 種結(jié)構(gòu)，在起點(diǎn)與終點(diǎn)之間最多有m -1 個(gè)站點(diǎn)。若用M 表示起點(diǎn)與終點(diǎn)之間站點(diǎn)個(gè)數(shù)，則0≤M≤m-1。每一種染色體結(jié)構(gòu)，對(duì)應(yīng)一個(gè)M 值，都可用插入法生成初始群體。用這種方法產(chǎn)生的初始群體也有利于提高算法的性能。

圖1 GATS 混合算法流程

2 算例

假設(shè)我戰(zhàn)略導(dǎo)彈部隊(duì)接到命令，要從當(dāng)前位置機(jī)動(dòng)到某一陣地。首先對(duì)鐵路網(wǎng)中的各站點(diǎn)進(jìn)行編號(hào)。假設(shè)一個(gè)有30 個(gè)站點(diǎn)的鐵路網(wǎng)，將出發(fā)點(diǎn)編號(hào)為1，終點(diǎn)編號(hào)為30，其余各點(diǎn)可隨機(jī)編號(hào)。為了計(jì)算簡(jiǎn)便，假設(shè)各路段的建設(shè)標(biāo)準(zhǔn)相同，也就是說列車在各路段行駛的最大速度相同，記為v。同樣，在一次最大機(jī)動(dòng)里程范圍內(nèi)，列車在行駛中對(duì)導(dǎo)彈儀器設(shè)備的影響相同。

因此，路線選擇主要受到時(shí)間和安全性的限制。時(shí)間主要與路線長(zhǎng)度有關(guān)，要在規(guī)定的時(shí)間內(nèi)到達(dá)指定地點(diǎn);安全性主要與沿線設(shè)施建設(shè)、自然環(huán)境、偽裝防護(hù)和敵方偵察監(jiān)視有關(guān)。對(duì)于不同區(qū)域，敵人偵察監(jiān)視的強(qiáng)度可能不同，算例中為了簡(jiǎn)化計(jì)算過程，設(shè)敵方對(duì)整個(gè)作戰(zhàn)區(qū)域內(nèi)的偵查監(jiān)視強(qiáng)度取為p=0.8，即在未采取任何措施情況下敵方的發(fā)現(xiàn)概率。

相鄰兩站點(diǎn)間的路線長(zhǎng)度矩陣(km)，即鄰接矩陣，記為D

假設(shè)列車最快機(jī)動(dòng)速度是v =100 km/h，完成任務(wù)的時(shí)限是T=3 h，初始種群中個(gè)體的數(shù)目是5。將以上數(shù)據(jù)代入到仿真程序中，得到結(jié)果如表1 所示。

通過仿真結(jié)果可以找到3 條可行路線，分別是M =2 情況下有2 條、M =4 情況下有1 條。按照上表中的順序，第1條路線的生存概率最小、路線最長(zhǎng)(接近了機(jī)動(dòng)時(shí)限內(nèi)的最遠(yuǎn)機(jī)動(dòng)距離300)、有一個(gè)可能影響通行性的點(diǎn)。第二、三條路線的生存概率都為0.7，路線長(zhǎng)度相差不大，第2 條中有一個(gè)可能影響通行性的點(diǎn)，而第3 條中沒有。所以，應(yīng)該選擇第3 條路線作為機(jī)動(dòng)路線。

除M=2、4 以外，其他情況下均為得出可行解。表中仍給出了在M =5、7 情況下各一個(gè)解。從解中可以看到，這2條路線中存在子路徑，分別是17—21—17、17—20—17，而且這2 條路線的生存概率均高于可行路線的生存概率。在實(shí)際作戰(zhàn)中，機(jī)動(dòng)經(jīng)常采用迂回、穿插等戰(zhàn)術(shù)，也就是說，機(jī)動(dòng)路線中會(huì)包含有子路徑。以上2 條路線雖不是可行路線，卻說明了該算法符合軍事作戰(zhàn)中的實(shí)際情況，而且其仿真結(jié)果也表明，機(jī)動(dòng)中采取迂回等戰(zhàn)術(shù)可以有效提高生存概率，符合作戰(zhàn)實(shí)際。這些都說明了該算法是可行有效的。

表1 GATS 程序仿真結(jié)果

3 結(jié)束語(yǔ)

運(yùn)籌學(xué)的目的是為指揮員做出決策提供可靠依據(jù)，而不是直接做出決策，所以最后提供給指揮員的應(yīng)該是盡可能多的可靠信息，而不是某一條單獨(dú)的路線。本算法在結(jié)果中并未直接給出應(yīng)選擇的哪一條路線，而是給出在不同M 值下的k 條(本例中為5，即染色體數(shù)目)路線，由指揮員根據(jù)戰(zhàn)場(chǎng)的實(shí)際情況、作戰(zhàn)經(jīng)驗(yàn)和其他標(biāo)準(zhǔn)選擇最終的機(jī)動(dòng)路線。

［1］郭強(qiáng)，謝秉磊.隨機(jī)旅行時(shí)間車輛路徑問題的模型及算法［J］.系統(tǒng)工程學(xué)報(bào)，2003(18):244-247.

［2］Martins.On a multicriteria shortest path problem［J］.European Journal of Operational Research，1984 (16):236-245.

［3］韓萬林，張幼蒂.遺傳算法的改進(jìn)［J］.中國(guó)礦業(yè)大學(xué)學(xué)報(bào)，2000，29(1):102-105.

［4］Millar J A，Potter W D. An Evaluation of Local Improvements Operators for Genetic Algorithms［J］.IEEE Trans.on SMC，1993，23(5):1340-1351.

［5］張淑榮，蘇兵.談?wù)劷伤阉魉惴ǎ跩］.信息技術(shù)教學(xué)與研究，2008(48):228-229.

［6］王正志，薄濤.進(jìn)化計(jì)算［M］.長(zhǎng)沙:國(guó)防科技大學(xué)出版社，2000:70-75.

［7］吳斌，吳堅(jiān)，涂序彥.快速遺傳算法［J］.電子科技大學(xué)學(xué)報(bào)，1999，28(1):49-53.