基于差分進化算法的應(yīng)急指揮堵控算法

基于差分進化算法的應(yīng)急指揮堵控算法

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

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

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

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

模型建立

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

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

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

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

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

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

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

綜上所述，堵控問題的數(shù)學(xué)模型可以表示為：

算法設(shè)計

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

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

變量描述與初始化

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

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

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

變異操作

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

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

交叉操作

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

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

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

其中參數(shù)a=30，b=3

圖1　算法流程圖

選擇操作

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

約束條件處理

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

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

算法流程

算法流程如圖1所示。

仿真實驗

系統(tǒng)環(huán)境

硬件CPU頻率2.4GHz，內(nèi)存16GB，操作系統(tǒng)Centos7.0，仿真軟件平臺Matlab2015。

實驗數(shù)據(jù)及參數(shù)設(shè)置

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

結(jié)語

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

10.3969/j.issn.1001- 8972.2016.18.012