遺傳算法在構(gòu)建犯罪預(yù)警積分模型中的應(yīng)用

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

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

遺傳算法在構(gòu)建犯罪預(yù)警積分模型中的應(yīng)用

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

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

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

犯罪預(yù)警；積分模型；遺傳算法；參數(shù)識別

0 引 言

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

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

(2)依靠主觀認(rèn)識給出屬性指標(biāo)積分分值的大小；

(3)未區(qū)分指標(biāo)本身和指標(biāo)重要性的差別；

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

文中研究構(gòu)建最佳參數(shù)的犯罪預(yù)警積分模型,提取較好衡量犯罪嫌疑人危險程度的特征信息并將其科學(xué)量化，通過構(gòu)建參數(shù)識別模型反映指標(biāo)重要性的最佳參數(shù)，在達(dá)到較好準(zhǔn)確率的同時實現(xiàn)犯罪嫌疑人的分類分級。

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

1 犯罪預(yù)警的積分模型

1.1 特征提取及數(shù)據(jù)處理

1.1.1 屬性特征提取

1.1.2 數(shù)據(jù)處理

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

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

首先，基于現(xiàn)有的數(shù)據(jù)，對數(shù)據(jù)進(jìn)行清洗工作后，最終確定n個屬性的量化方式。

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

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

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

1.2 建立犯罪預(yù)警的積分模型

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

(1)

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

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

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

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

記函數(shù)：

(2)

表示由(α1,α2,…,αn)確定的積分模型的穩(wěn)定性，以此作為目標(biāo)進(jìn)行優(yōu)化。

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

(3)

2 改進(jìn)的遺傳算法對參數(shù)識別模型的求解

2.1 遺傳算法

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

2.1.1 遺傳算法的流程圖

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

根據(jù)“適者生存”“優(yōu)勝劣汰”的原則，遺傳算法通過編碼產(chǎn)生初始種群,對個體進(jìn)行遺傳和進(jìn)化操作。適值函數(shù)反映每個個體適應(yīng)環(huán)境的能力，由上代群體中選擇下一代種群。

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

2.1.2 遺傳算法編碼方式

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

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

2.1.3 選擇初始群體

種群規(guī)模影響遺傳算法的收斂速度或計算效率。種群規(guī)模一般情況在10～200之間選定。種群生成是隨機(jī)產(chǎn)生H個初始數(shù)據(jù),一個數(shù)據(jù)即為一個個體,相當(dāng)于擬合模型的一個可行解,H個個體構(gòu)成一個群體。遺傳算法就是以這H個初始數(shù)據(jù)作為初始點(diǎn)開始迭代。

2.1.4 遺傳算子

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

2.2 交叉算子和變異算子的改進(jìn)

(4)

(5)

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

案例分析如下：

Shubert函數(shù)：

(6)

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

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

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

表1 Shubert函數(shù)在兩種遺傳算法下的實驗結(jié)果

從算法成功率、平均值方面看，改進(jìn)遺傳算法優(yōu)于傳統(tǒng)遺傳算法，且新添加的指標(biāo)—最佳代數(shù)也可體現(xiàn)，改進(jìn)遺傳算法收斂更快，更容易搜索到最優(yōu)解附近。

2.3 改進(jìn)遺傳算法在參數(shù)識別模型中的應(yīng)用

根據(jù)上述案例可以看出，改進(jìn)遺傳算法在算法效率上有一定的提高。文中應(yīng)用改進(jìn)遺傳算法對參數(shù)識別模型參數(shù)優(yōu)化的主要步驟如下：

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

Step3:初始群體解碼并代入?yún)?shù)識別模型求解，計算個體適應(yīng)度fk=I(α1,α2,…,α37),k=1,2,…,K。

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

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

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

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

其中，時間指標(biāo)為函數(shù)運(yùn)算10次的平均時間。最佳值是10次結(jié)果中最大值；平均值是指10次結(jié)果的平均值。最佳代數(shù)為10次訓(xùn)練中最佳值所在代數(shù)的平均值(若最佳值只出現(xiàn)一次，則為最佳值出現(xiàn)時的代數(shù))。結(jié)果如表2所示。

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

經(jīng)過改進(jìn)遺傳算法的運(yùn)算，得出該參數(shù)識別問題的一組最佳參數(shù)：

(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 結(jié)束語

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

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

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

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

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

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

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

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

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

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

[10] 劉東平,單甘霖,張岐龍,等.基于改進(jìn)遺傳算法的支持向量機(jī)參數(shù)優(yōu)化[J].微計算機(jī)應(yīng)用,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] 于 洋,查建中,唐曉君.基于學(xué)習(xí)的遺傳算法及其在布局中的應(yīng)用[J].計算機(jī)學(xué)報，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

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

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

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