遺傳算法在構建犯罪預警積分模型中的應用

閆盼盼,陳丕煒,曹圣山,王 琦,呂可波,高 翔

(中國海洋大學 數學科學學院,山東 青島 266100)

遺傳算法在構建犯罪預警積分模型中的應用

閆盼盼,陳丕煒,曹圣山,王 琦,呂可波,高 翔

(中國海洋大學 數學科學學院,山東 青島 266100)

通過建立線性積分模型，研究犯罪嫌疑人的分類分級問題，實現對犯罪行為的預警。將積分模型參數的確定歸結為目標函數非解析的最佳參數識別問題，并利用遺傳算法得到最佳參數。為了克服傳統遺傳算法的早熟現象和局部收斂問題，文中提出了一種具有改進的交叉算子和變異算子的遺傳算法。改進的遺傳算法可加快算法收斂速度,從而縮短尋找最優解的時間，提高算法的效率。數值實驗結果表明，改進遺傳算法用于犯罪嫌疑人的分類分級問題尋找最佳參數有更高的運行效率，建立的積分模型對犯罪嫌疑人的分類分級具有較好的準確率。

犯罪預警；積分模型；遺傳算法；參數識別

0 引 言

近年來，定量化的犯罪情報分析越來越受到重視,相關部門積累的數據也為此奠定了基礎。90年代犯罪情報分析開始納入警方的日常工作,主要關注犯罪可能發生的時間和地點、數量和模式，讓警方預先布防，有效地減少犯罪[1-2]。劉小娟等采用灰色系統理論開展犯罪總量預測的研究[3-5],秦立強等提出了對我國整體治安狀況進行綜合預警的社會治安預警指標體系[6],這些研究對犯罪嫌疑人的分類分級問題的指導性有限?，F有的積分模型存在以下問題：

(1)選擇積分模型的屬性特征指標時，對犯罪嫌疑人的關聯關系刻畫不夠；

(2)依靠主觀認識給出屬性指標積分分值的大小；

(3)未區分指標本身和指標重要性的差別；

(4)積分模型的本質是確定危險程度的高低順序，原有積分模型的得分僅由個人行為確定，缺乏群體行為間的相互影響度量，易出現個別因素得分過高的不合理現象，影響模型的準確率。

文中研究構建最佳參數的犯罪預警積分模型,提取較好衡量犯罪嫌疑人危險程度的特征信息并將其科學量化，通過構建參數識別模型反映指標重要性的最佳參數，在達到較好準確率的同時實現犯罪嫌疑人的分類分級。

文中用遺傳算法求解參數識別問題，利用其全局搜索能力得到最佳參數。一般遺傳算法包含三個基本算子：繁殖、交叉和變異。交叉是通過交換個體某位基因產生新的基因組合來限制遺傳信息的丟失，變異是防止尋優過程中過早收斂于不成熟期[7-8]。曹道友等采用了改進的交叉算子,根據個體間的相似度決定是否進行交叉操作[9]。劉東平等采用單點迭代式的交叉概率和變異概率來改進遺傳算法[10]。在此基礎上，文中嘗試構建兩點迭代的交叉概率和變異概率,加快算法收斂速度，提高算法的求解質量和效率，從而得到積分模型的最佳參數。實驗結果表明該方法是可行的。

1 犯罪預警的積分模型

1.1 特征提取及數據處理

1.1.1 屬性特征提取

1.1.2 數據處理

數據處理包括對數據缺失、數據異常等問題的處理，針對屬性及屬性含義不同提出不同處理方法。

由于前期數據準備的過程中，數據來自不同的數據庫，各數據庫信息采集不完全相同，從而導致某些屬性的數據缺失；存在部分屬性的數據信息完全沒有錄入和犯罪嫌疑人的靜態信息缺失等情況。除此之外，還存在數據異常和屬性信息數據覆蓋率低、有價值數據較少等情況。

首先，基于現有的數據，對數據進行清洗工作后，最終確定n個屬性的量化方式。

由于屬性及屬性含義不同，各屬性的取值方式也各不相同，包括數值、文字、字典項等多種數據格式。因此文中模型共采用以下5種不同的量化方法處理原始數據：直接量化、正態量化、統計量化、相對統計量化、反比統計量化。

直接量化：針對特征指標值為數值型的屬性，且危險程度與之成正比，則模型中使用原始數據，即yij=xij。

統計量化：根據事件發生占樣本總體的頻數的一種量化方式。首先計算屬性nj樣本x1j,x2j,…,xmj可能的取值g1,g2,…,gs；然后對每個可能取值gk(k=1,2,…,s)計算樣本值x1j,x2j,…,xmj出現的頻數或頻率hk(k=1,2,…,s)；最后對i=1,2,…,m，如果xij=gk，則yij=hk,k=1,2,…,s。

1.2 建立犯罪預警的積分模型

為評估犯罪嫌疑人的危險程度，實現對犯罪嫌疑人的預警工作，建立如下積分模型：

(1)

其中，xij(i=1,2,…,m,j=1,2,…,n)為量化后的屬性指標值；待定參數αj(j=1,2,…,n)表示指標重要性。

對m個犯罪嫌疑人以此積分為依據按照積分由高到低進行排序，排序后的人員編號記為(1),(2),…,(m)。

1.3 建立求解參數αj(j=1,2,…,n)的參數識別模型

為求解滿足積分模型(見式(1))的最佳參數，根據式(1)推送的高危犯罪嫌疑人與近期抓獲人員的比對人數，確定參數識別模型。

記函數：

(2)

表示由(α1,α2,…,αn)確定的積分模型的穩定性，以此作為目標進行優化。

maxI(α1,α2,…,αn)

(3)

2 改進的遺傳算法對參數識別模型的求解

2.1 遺傳算法

文中選擇遺傳算法求解上述目標函數非解析的參數識別模型。遺傳算法[11-12](Genetic Algorithm,GA)是一種全局最優搜索算法,被廣泛應用于優化、系統識別中的參數估計等領域。遺傳算法不需要一定滿足目標函數和約束函數的可解性。遺傳算法在參數優化中的進展[13-14]可用來解決文中的參數優化問題。

2.1.1 遺傳算法的流程圖

通過對上一種群基因的復制、變換和變異，基本的遺傳算法產生新種群。算法的處理流程圖見圖1。

根據“適者生存”“優勝劣汰”的原則，遺傳算法通過編碼產生初始種群,對個體進行遺傳和進化操作。適值函數反映每個個體適應環境的能力，由上代群體中選擇下一代種群。

遺傳包括交叉和變異：交叉是影響算法收斂性及搜索效率的關鍵因素，依據交叉準則對兩個染色體進行操作，組合兩者生成新的后代；變異是染色體自發地產生隨機變化，隨機改變個體的基因值，使個體呈現多樣性。

2.1.2 遺傳算法編碼方式

遺傳算法只能處理以基因碼串形式表示的個體，編碼就是把解的參數形式轉換成基因碼串的表示形式。遺傳算法已有許多種不同形式的編碼方法,主要分為三大類:二進制編碼、浮點數編碼和符號編碼。

文中采用二進制編碼方法。二進制編碼是遺傳算法中最重要的一種編碼方式，具有編碼、解碼簡單易行，易于交叉和變異操作的優點。

2.1.3 選擇初始群體

種群規模影響遺傳算法的收斂速度或計算效率。種群規模一般情況在10～200之間選定。種群生成是隨機產生H個初始數據,一個數據即為一個個體,相當于擬合模型的一個可行解,H個個體構成一個群體。遺傳算法就是以這H個初始數據作為初始點開始迭代。

2.1.4 遺傳算子

遺傳算子包括交叉算子、變異算子等。交叉算子(或重組算子)指的是染色體重組，在新復制的群體中隨機選取兩個個體，隨機選取位置，互換從該位置起兩個個體的末尾部分。交叉概率一般在0.4～0.99間取值。變異算子相當于生物進化過程中個體的基因突變現象，即改變染色體某個(些)位上的基因。變異概率一般在0.000 1～0.1間取值。

2.2 交叉算子和變異算子的改進

(4)

(5)

其中，T為遺傳代數；Tmax為最大遺傳代數；Pc(T)和Pm(T)分別為第T代的交叉概率和變異概率。

案例分析如下：

Shubert函數：

(6)

在定義域內Shubert共有760個局部極小值點,其中18個點是全局最小值點。全局最小值是fmin=-186.731。

傳統遺傳算法參數選擇按照文獻[15]中設定。對Shubert函數，文中分別用傳統遺傳算法、改進遺傳算法各計算100次。算法的性能按照文獻[15]中設定，同樣從質量和效率兩個方面考慮。算法的質量用成功率、最佳值、平均值三個指標來衡量；算法效率用時間指標來衡量。此外，增加另一指標—最佳代數。

其中，時間指標為函數運算100次的平均時間。成功率指計算結果中絕對誤差小于0.001的比例；最佳值是100次結果中最小值；平均值是指100次結果的平均值。最佳代數為100次訓練中最佳值所在代數的平均值(若最佳值只出現一次，則為最佳值出現時的代數)。計算結果和比較內容如表1所示。

表1 Shubert函數在兩種遺傳算法下的實驗結果

從算法成功率、平均值方面看，改進遺傳算法優于傳統遺傳算法，且新添加的指標—最佳代數也可體現，改進遺傳算法收斂更快，更容易搜索到最優解附近。

2.3 改進遺傳算法在參數識別模型中的應用

根據上述案例可以看出，改進遺傳算法在算法效率上有一定的提高。文中應用改進遺傳算法對參數識別模型參數優化的主要步驟如下：

Step2:遺傳算法的參數設定為，初始代數T=1，初始交叉概率Pc(1)=Pc(2)=0.9，初始變異概率Pm(1)=Pm(2)=0.01，最大遺傳代數Tmax=50，交叉概率和變異概率分別由式(4)和式(5)確定。

Step3:初始群體解碼并代入參數識別模型求解，計算個體適應度fk=I(α1,α2,…,α37),k=1,2,…,K。

Step4:把適應度(比對人數)最高的個體保存下來，防止因遺傳算子操作使優秀基因丟失。

Step5:采用輪盤賭選擇方法和單點交叉，經過遺傳算子操作產生新群體，根據適應度選擇，重插入子群到種群，最終產生新的群體并返回Step3進行訓練。

Step6:檢查是否滿足算法終止條件。連續幾代最優個體的適應度相等作為算法終止的條件之一；設定的最大遺傳代數(Tmax)作為算法的另一個終止條件。滿足上述兩個條件中任何一個即可停止算法。

同樣分別用傳統遺傳算法和改進遺傳算法各計算10次(傳統遺傳算法交叉概率和變異概率分別取值0.9和0.001)。

其中，時間指標為函數運算10次的平均時間。最佳值是10次結果中最大值；平均值是指10次結果的平均值。最佳代數為10次訓練中最佳值所在代數的平均值(若最佳值只出現一次，則為最佳值出現時的代數)。結果如表2所示。

表2 模型在兩種遺傳算法下的實驗結果

經過改進遺傳算法的運算，得出該參數識別問題的一組最佳參數：

(0.656 6,0.979 8,1.868 7,1.949 5,0.414 1,0.737 4,2.515 2,1.868 7,2.191 9,1.626 3,0.656 6,1.626 3,2.191 9,0.818 2,2.434 3,2.838 4,0.899 0,1.787 9,2.272 7,1.303 0,2.919 2,1.626 3,0.494 9,0.656 6,1.303 0,1.141 4,0.656 6,1.626 3,2.596 0,2.515 2,0.575 8,2.272 7,0.899 0,2.191 9,0.737 4,1.787 9,0.575 8)

3 結束語

通過對某市在庫犯罪嫌疑人案例分析可以看出，犯罪預警積分模型的建立可以實現對犯罪嫌疑人的分類分級工作，提高預測準確率。文中構建的數學模型，對各屬性指標進行科學定量計算，考慮犯罪嫌疑人之間的關聯關系和指標的重要性，度量群體行為的相互影響、確定模型最佳參數，從而對積分預警模式提供參考依據。文中使用改進的交叉算子和變異算子，加快了算法的收斂速度。實驗表明，改進遺傳算法可提高傳統算法的搜索能力，加快搜索到更優參數值的速度，用來求解積分模型的最佳參數有較高的效率。

[1] 王 欣.治安預測方法與技術比較研究[J].中國人民公安大學學報:自然科學版,2011,17(3):29-35.

[2] 盧曉賓.我國情報研究活動現狀分析[J].情報學報,1994,13(3):185-191.

[3] 劉小娟,高連生.灰色系統理論在犯罪動態預測中的應用[J].中國人民公安大學學報:社會科學版,2005,21(1):44-48.

[4] 王洪革,于子建.基于灰色理論的青少年犯罪預測模型及其應用[J].廣東培正學院學報,2005(2):51-55.

[5] 陳 鵬，胡詩妍，羅萬杰,等.基于灰色-馬爾可夫模型的侵財類警情預測研究[J].中國公共安全:學術版,2014(2)：32-35.

[6] 秦立強，王 光.淺談我國社會治安環境的評價與預警[J]．統計研究，2002(4):28-33.

[7] 陳長征,王 楠.遺傳算法中交叉和變異概率選擇的自適應方法及作用機理[J].控制理論與應用,2002,19(1):41-43.

[8] 焦李成，保 錚.進化計算與遺傳算法-計算智能的新方向[J].系統工程與電子技術，1995,17(6)：20-32.

[9] 曹道友,程家興.基于改進的選擇算子和交叉算子的遺傳算法[J].計算機技術與發展,2010,20(2):44-47.

[10] 劉東平,單甘霖,張岐龍,等.基于改進遺傳算法的支持向量機參數優化[J].微計算機應用,2010,31(5):11-15.

[11]HollandJH.Adaptationinnaturalandartificialsystems[M].USA:MITPress,1992.

[12]GoldbergDE.Geneticalgorithmsinsearch,optimization,andmachinelearning[M].[s.l.]:Addison-WesleyProfessional,1989.

[13]DebK.Anefficientconstrainthandlingmethodforgeneticalgorithms[J].ComputerMethodsinAppliedMechanicsandEngineering, 2003，186(2):311-338.

[14]DebK,AnandA,JoshiD.Acomputationallyefficientevolutionaryalgorithmforreal-parameteroptimization[J].EvolutionaryComputation,2002,10(4):371-395.

[15] 于 洋,查建中,唐曉君.基于學習的遺傳算法及其在布局中的應用[J].計算機學報，2001,24(12):1242-1249.

Application of Genetic Algorithm in Construction of Criminal Early Warning Cumulative Model

YAN Pan-pan,CHEN Pi-wei,CAO Sheng-shan,WANG Qi,Lü Ke-bo，GAO Xiang

(School of Mathematical Science,Ocean University of China,Qingdao 266100,China)

By establishing the linear cumulative model,it studies the classification of the criminal suspects to realize the early warning of criminal activity.The cumulative model parameters determined come down to solving a target function non-analytic of the parameters identification problem,and use genetic algorithm to solve this model getting the optimal parameters.In order to overcome premature and local convergence of traditional genetic algorithm,it puts forward an improved genetic algorithm with a modified crossover operator and mutation operator in this paper.Improved genetic algorithm can speed up the convergence rate,thus shortening the time to find the optimal solutions and improving the efficiency of full instructions.The experimental result shows that improved genetic algorithm applied to criminal suspects has better operating efficiency to solve optimal parameters classification problem,and this cumulative model has good accuracy.

criminal early warning;cumulative model;genetic algorithm;parameters identification

2015-09-24

2015-12-29

時間：2016-05-25

國家自然科學基金資助項目(11071228)

閆盼盼(1989-),女,碩士研究生,研究方向為數學建模及其數值解法研究；曹圣山,通訊作者，教授，研究方向為數學建模及其數值解法研究。

http://www.cnki.net/kcms/detail/61.1450.TP.20160525.1709.060.html

TP391

A

1673-629X(2016)07-0142-05

10.3969/j.issn.1673-629X.2016.07.030