[發(fā)明專利]一種基于遺傳算法的包匹配方法

在審

• 申請?zhí)枺?/td>: 201710091852.X
• 申請日: 2017-02-21
• 公開（公告）號: CN106817376A
• 公開（公告）日: 2017-06-09
• 發(fā)明（設(shè)計）人: 程實;王則林;潘建生;王昱;程顯毅
• 申請（專利權(quán)）人: 南通大學(xué);南通先進(jìn)通信技術(shù)研究院有限公司
• 主分類號: H04L29/06
• 分類號: H04L29/06;G06N3/12
• 代理公司: 北京科億知識產(chǎn)權(quán)代理事務(wù)所(普通合伙)11350
• 代理人: 湯東鳳

1.一種基于遺傳算法的包匹配方法，其特征在于，包括如下步驟：

（1）采用遺傳算法來進(jìn)行特征選擇，選出相關(guān)特征位，去除冗余特征位和無關(guān)特征位；

解決如下兩個問題：

（1-1）適應(yīng)值設(shè)置：把包規(guī)則庫中的規(guī)則像染色體一樣映射成一串二進(jìn)制字符串，針對染色體所有基因值為0的位，把二進(jìn)制串的相應(yīng)位去除；

設(shè)：染色體位數(shù)為8，群體中一個染色體為1 0 1 1 1 1 0 1，有三條規(guī)則相應(yīng)的二進(jìn)制串分別為：

1 0 0 0 1 1 1 1

1 0 1 1 0 0 0 1

0 1 0 1 0 0 1 1，

染色體1 0 1 1 1 1 0 1的第二位和第七位為“0”，所以把三條規(guī)則對應(yīng)的二進(jìn)制串的第二位和第七位刪去，結(jié)果如下所示：

1 0 0 1 1 1

1 1 1 0 0 1

0 0 1 0 0 1，

計算處理后的包規(guī)則庫中任何兩條規(guī)則的相異度用它們的海明距離去度量，海明距離H，按下面的公式（2）計算：

（2）,

其中，RN為包規(guī)則庫中的規(guī)則數(shù)，h_ij為包規(guī)則庫中的規(guī)則i和規(guī)則j之間的海明距離；

適應(yīng)值按照公式（1）計算：

（1）,

其中，H為海明距離，S₁為染色體中基因值為1的基因數(shù)目，α、β分別為調(diào)節(jié)兩個因子的權(quán)重，α要遠(yuǎn)大于β，否者會導(dǎo)致局部最優(yōu)；

（1-2）個體編碼：采用二進(jìn)制編碼，染色體長度為296位，NP規(guī)模設(shè)為2000，交叉操作采用掩碼的均勻交叉，每次交叉從種群里隨機(jī)選擇兩個個體，根據(jù)掩碼的設(shè)置產(chǎn)生交叉子個體，設(shè)隨機(jī)選擇的兩父個體為：

父個體1：1 0 0 0 1 1 1 1 0 1 0 0 1 0 1 1

父個體2：1 0 1 1 0 0 0 1 1 1 0 1 0 1 0 0

掩 碼： 0 0 1 1 1 0 0 1 1 1 0 1 1 0 0 1

則均勻交叉產(chǎn)生的子個體為：1 0 0 0 1 0 0 1 0 1 0 0 1 1 0 1；

變異采用隨機(jī)選擇Λ位進(jìn)行變異，Λ隨演化代數(shù)逐漸降低，在每一代演化過程中都把最優(yōu)解保留下來，如果下一代中沒有個體的適應(yīng)值優(yōu)于上一代保留的最優(yōu)解，就用上一代保留的最優(yōu)解隨機(jī)替換下一代中的任一個體；

（2）對包規(guī)則庫中的規(guī)則進(jìn)行分析和處理，精簡規(guī)則庫中的覆蓋規(guī)則和交叉規(guī)則，具體步驟為：設(shè)一個規(guī)則定義為：X{[x¹_min，x¹_max]，... [xⁿ_min, xⁿ_max]}，覆蓋的定義為：規(guī)則X={x¹,x², ... xⁿ}和規(guī)則Y={y¹, y², ... yⁿ}，如果對于任何x^j，都存在y^j被x^j包含，那就定義為X規(guī)則覆蓋Y規(guī)則；處理行為一樣的覆蓋規(guī)則為覆蓋冗余，匹配結(jié)果不一樣的覆蓋規(guī)則為覆蓋矛盾；

交叉的定義為：如果規(guī)則X和規(guī)則Y在一維或多維之間存在范圍重疊的現(xiàn)象，而剩余的別的維都是x^j=y^j，那就定義規(guī)則X和規(guī)則Y重疊；

（3）算法設(shè)計，具體步驟如下：

（3-1）設(shè)定初始值：種群規(guī)模NP=2000，演化代數(shù)I=100，調(diào)節(jié)兩個因子的權(quán)重α=0.9，β=0.1，交叉因子Λ=10；

（3-2）設(shè)置循環(huán)終止條件：演化代數(shù)I達(dá)到100或公式（1）的適應(yīng)值小于0.01；

（3-3）根據(jù)公式（1）對個體進(jìn)行評價，

（1），

其中，H為海明距離，S₁為染色體中基因值為1的基因數(shù)目，α、β分別為調(diào)節(jié)兩個因子的權(quán)重，α要遠(yuǎn)大于β，否則會導(dǎo)致局部最優(yōu)；

（3-4）從NP中選擇兩個個體；

（3-5）對選擇的兩個個體進(jìn)行交叉操作；

（3-6）對選擇的個體進(jìn)行變異操作；

（3-7）循環(huán)執(zhí)行步驟（3-2）~（3-7），直至滿足循環(huán)終止條件，循環(huán)結(jié)束。