基于混合算法的導彈部隊鐵路機動路徑選擇

詹仁超，李應岐

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

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

1 戰(zhàn)略導彈鐵路機動路線問題建模

1.1 問題的基本描述

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

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

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

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

2)時間T 約束，即導彈列車必須在指定的時間內到達某陣地，否則將會貽誤戰(zhàn)機。

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

1.2 建立模型與算法步驟

1.2.1 建立模型

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

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

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

1)軍事活動中，不需要通過圖中所有點，只需要到達目標點。

2)軍事活動中，對同一個點，在一條路線中可以幾次選擇，也就是說在路線中可以出現(xiàn)回路。

3)軍事活動中，機動路線不一定形成回路，也就是說起點與終點很可能不是一個點。

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

目標函數: maxp

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

1.2.2 算法步驟

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

需要強調的是在產生初始群體中，沒有要求列車必須通過每個站點，也沒有每個站點只能通過一次的限制，也就是說，染色體的長度是可變的，而且一條路線中還可能有迂回回路。要產生初始群體，必須確定染色體的長度，即站點的數量。

可以通過以下方法確定

對于具有不同長度的染色體，本文中將其稱為具有不同的染色體結構。起點和終點是確定的，也就是說染色體最多有m -1 種結構，在起點與終點之間最多有m -1 個站點。若用M 表示起點與終點之間站點個數，則0≤M≤m-1。每一種染色體結構，對應一個M 值，都可用插入法生成初始群體。用這種方法產生的初始群體也有利于提高算法的性能。

圖1 GATS 混合算法流程

2 算例

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

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

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

假設列車最快機動速度是v =100 km/h，完成任務的時限是T=3 h，初始種群中個體的數目是5。將以上數據代入到仿真程序中，得到結果如表1 所示。

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

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

表1 GATS 程序仿真結果

3 結束語

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

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

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

［3］韓萬林，張幼蒂.遺傳算法的改進［J］.中國礦業(yè)大學學報，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］張淑榮，蘇兵.談談禁忌搜索算法［J］.信息技術教學與研究，2008(48):228-229.

［6］王正志，薄濤.進化計算［M］.長沙:國防科技大學出版社，2000:70-75.

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