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

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

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

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

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

模型建立

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

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

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

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

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

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

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

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

算法設(shè)計(jì)

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

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

變量描述與初始化

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

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

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

變異操作

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

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

交叉操作

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

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

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

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

圖1　算法流程圖

選擇操作

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

約束條件處理

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

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

算法流程

算法流程如圖1所示。

仿真實(shí)驗(yàn)

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

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

實(shí)驗(yàn)數(shù)據(jù)及參數(shù)設(shè)置

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

結(jié)語

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

10.3969/j.issn.1001- 8972.2016.18.012