基于差分進化算法的應急指揮堵控算法

基于差分進化算法的應急指揮堵控算法

科學合理地調度警力資源處理突發事件是提高公安部門執法能力的重要因素，為了優化調度方案并提高執法信息化水平，建立了以犯罪嫌疑人在逃時間最短的0-1整數規劃模型。為了實現快速高效堵控，采用改進的差分進化算法求解最佳堵控方案。

近年來，隨著我國改革開放的不斷深入和社會經濟的迅速發展，公安機關的執法面臨更多的挑戰。由于警力不足以及管理體制的原因，應急指揮經常呈現反應不及時和處置滯后等弱點。運用現代化的計算工具提高警力合理使用與調度的水平對于進一步提高公安機關的服務水平和實戰能力顯得尤為重要。

隨著城市規模日益擴大，公安機關指揮處理重大突發事件時需要調度警力資源對交通要道進行封鎖。相對于整個城市來說，警力資源肯定是不足的，處理突發事件時需要將平時分散部署的警力資源調度到某些位置實現“堵控”，這是一個受到資源不足約束的調度問題。如何構建合理的模型并利用快速有效的算法求解警力的調度與指揮方案，對公安機關提高處理應急事件的能力具有重要的意義。

本文為研究犯罪嫌疑人的堵控問題，建立以犯罪嫌疑人在逃時間最短為目標的堵控模型，設計基于差分進化算法的全市警力資源調度的算法求解該問題。

模型建立

設某城市有n 個路口｛P1， P2，…Pn｝及m 個警力資源｛S1， S2…，Sm｝，在t0時刻接到報警稱在城市Pk，（k=1，2，…，n）路口發生了重大刑事案件，犯罪嫌疑人乘坐交通工具正在逃跑，為了堵控犯罪嫌疑人，需要搜索堵控路口集合｛P1， P2，…Pq｝以及相應警力資源｛S1， S2…，Sq｝的調度方案，確保將犯罪嫌疑人有效“圍住”。該問題的最優方案需要滿足警力資源｛S1， S2…，Sq｝能在最短時間從原先部署位置調度到堵控路口集合｛P， P…P｝，且

12q犯罪嫌疑人沒有逃出堵控路口集合所形成的包圍圈。

假設各路口交通暢通，案發地點和警力資源的位置在路口節點，每個路口只需要一個警車的警力即可封鎖，罪犯逃跑方向是遠離案發地點，罪犯的逃跑速度僅為60km/h。設xij為0-1變量，xij=1表示從第i 個路口的警力資源向第j個路口節點處調度，xij=0表示不從第i 個路口的警力資源向第j個路口節點處調度。xij是決策變量，也是問題的解。問題的最優方案應該滿足三個要求：（1）犯罪嫌疑人最大堵控時間最小化；（2）警力資源由外向內調度；（3）犯罪嫌疑人到達某路口的時間大于或等于警力資源到達該路口的時間。

（1）堵控方案的最主要目標就是警力資源最短時間內控制犯罪嫌疑人的逃竄，使其可能的在逃時間最小，即警力資源到達所有堵控節點所用時間的最大值最小化，由此建立目標函數：

其中，tij表示第i 個警力資源到達第j個路口節點的最短時間，max（tijxij）表示調度方案中警力部署到指定路口節點的最長時間。

（2）考慮到追捕嫌疑人的策略，警力資源從外向內調度，建立約束條件如下：

（3）為保證第i 個警力資源調度到第j個路口圍住犯罪嫌疑人，則警力資源一定要在犯罪嫌疑人之前到達第j個路口節點，所以警力資源從第i 個到第j個路口所用調度時間一定要小于等于犯罪嫌疑人到達第j個路口節點的時間，建立約束條件如下：

綜上所述，堵控問題的數學模型可以表示為：

算法設計

該模型是一個0-1非線性規劃問題，求解此類問題的傳統方法有共軛梯度法、變尺度法、分支定界法、廣義Benders分解法、外近似法等。由于上述傳統方法計算量隨著變量維數的增加而急劇增大，一般不能用于實時控制，難以滿足本文提出的問題的要求。近年來，隨著人工智能技術的提高，各種智能優化算法如遺傳算法、粒子群優化算法、蟻群算法以及差分進化算法在不同領域得到了廣泛的應用。差分進化算法（DE）是Storn等人于1995年共同提出的一種采用浮點矢量編碼，和其它演化算法一樣，是一種模擬生物進化的隨機模型，在連續空間中進行啟發式隨機搜索的優化算法，具有較強的全局收斂能力和魯棒性。

差分進化算法采用浮點數編碼，要將其用于求解0-1非線性整數規劃問題，必須先對其進行改進，主要是編碼轉為0-1整數。由于DE的基本操作包括變異、交叉，選擇是根據適應值大小進行，這與其他進化算法是類似的。改進主要是進行初始化時對0-1變量先在｛0，1｝實數空間取值，然后根據其特點對變異操作進行改進，即采用四舍五入法進行取整運算，得到對應的0-1變量，就可以將DE用于0-1非線性規劃問題。

變量描述與初始化

DE種群的每個個體是調度優化問題的一個解決方案，由n 個決策變量組成，用矩陣表示（k=1，2，…，n ，其中t 表示第t 代）：

其中，xij為0-1變量，表示從第i個路口的警力資源向第j個路口節點處調度。

按照式子（7）對決策變量X 初始化，其中，XL和XU分別為下限和上限，r為在［0，1］上服從均勻分布的隨機數。首先在｛0，1｝實數空間隨機取值，然后四舍五入取整，得到0-1整數變量：

變異操作

DE算法中，變異個體是由種群內個體的差分向量經過縮放之后與種群內其他相異個體相加得到的。根據變異個體的生成方法不同，對應就有多種不同的差分進化策略。本文對0-1變量進行變異操作并采用四舍五入的方法進行取整的方程為：

其中，r1≠r2≠r3≠s 為互不相同的隨機個體，縮放因子F∈［0，2］。

交叉操作

DE的交叉操作可以保持種群的多樣性，進而保持多個可能全局最優的個體，提高搜索的廣度。DE算法包括二項式交叉和指數交叉兩種交叉方式。本文采用指數交叉。

試驗個體XT由群體中第t 代第k 個個體與變異個體Xs進行交叉操作，可以看成是個體的進化。首先通過隨機選擇使得試驗個體XT至少有一位由變異個體Xs提供，其他位可以根據交叉概率因子CR 決定由Xs還是提供。交叉操作的方程為：

若CRmin和CRmax分別為最小交叉概率和最大交叉概率，Tmax為最大迭代次數，則CR 由下面式子確定：

其中參數a=30，b=3

圖1　算法流程圖

選擇操作

DE采用“貪婪”選擇策略，將變異和交叉操作后生成的試驗個體XT與Xkt進行競爭，根據適應度值f（·）來選擇最優個體，若試驗個體XT適應度值比Xkt更優時，則將其選為子代，否則將Xkt選為子代。選擇操作的方程為：

約束條件處理

由于約束條件通常都是非線性的，一般采用懲罰函數法將帶約束條件的原問題轉為無約束問題。經過懲罰函數轉化后的無約束問題可定義為：

其中αj和βi為大于零的懲罰因子。

算法流程

算法流程如圖1所示。

仿真實驗

系統環境

硬件CPU頻率2.4GHz，內存16GB，操作系統Centos7.0，仿真軟件平臺Matlab2015。

實驗數據及參數設置

以2011年大學生數學建模競賽B題數據為實驗數據，根據算法思想編程求解，得到警力資源的堵控方案如下：

結語

本文針對公安機關在處理突發事件時警力調度問題，建立以犯罪嫌疑人在逃時間最短為目標，警力資源由外而內、警力資源先于犯罪嫌疑人到達路口為約束的調度策略的0-1規劃模型，并就該模型采用差分進化算法進行求解。仿真實驗結果表明，該方法能夠快速有效解決警力調度問題，具有一定的實際意義和應用價值。

10.3969/j.issn.1001- 8972.2016.18.012