[1]蔡良伟,程璐,李军,等.基于遗传算法的正则表达式规则分组优化[J].深圳大学学报理工版,2015,32(No.3(221-330)):281-289.[doi:10.3724/SP.J.1249.2015.03281]
 Cai Liangwei,Cheng Lu,Li Jun,et al.Regular expression grouping optimization based on genetic algorithm[J].Journal of Shenzhen University Science and Engineering,2015,32(No.3(221-330)):281-289.[doi:10.3724/SP.J.1249.2015.03281]
点击复制

基于遗传算法的正则表达式规则分组优化()
分享到:

《深圳大学学报理工版》[ISSN:1000-2618/CN:44-1401/N]

卷:
第32卷
期数:
2015年No.3(221-330)
页码:
281-289
栏目:
电子与信息科学
出版日期:
2015-05-20

文章信息/Info

Title:
Regular expression grouping optimization based on genetic algorithm
文章编号:
201503009
作者:
蔡良伟1程璐1李军2李霞1
1) 深圳大学信息工程学院,深圳 518060
2)清华大学信息技术研究院,北京 100084
Author(s):
Cai Liangwei1 Cheng Lu1 Li Jun2 and Li Xia1
1) College of Information Engineering, Shenzhen University, Shenzhen 518060, P.R.China
2) Research Institute of Information Technology, Tsinghua University, Beijing 100084, P.R.China
关键词:
人工智能正态自适应遗传算法深度包检测正则表达式分组算法网络安全
Keywords:
artificial intelligencenormal adaptive genetic algorithm deep packet inspection regular expression grouping algorithm network security
分类号:
TP 391;TP 393
DOI:
10.3724/SP.J.1249.2015.03281
文献标志码:
A
摘要:
为解决正则表达式匹配问题,提出一种基于正态自适应遗传优化的改进正则表达式分组算法.根据迭代次数的变化,利用正态函数自适应改变交叉概率Pc和变异概率Pm, 采取最优保存策略保证最优个体不被数值大的Pc和Pm破坏.结合Becchi算法和局部寻优算法进一步优化.仿真结果表明,该算法能在全局范围内搜索到更好的解,能有效减少状态总数,降低正则表达式匹配的空间复杂度.
Abstract:
An improved optimization method based on normal adaptive genetic algorithm (NAGA) is proposed to solve the matching problem of regular expression grouping (REG), in which the crossover probability and the mutation probability are adaptively changed by a normal function according to the number of iterations. And the optimal preservation strategy is used in REG-NAGA to ensure that the best individual is not destroyed by large Pc and Pm. Additionally, Becchi algorithm and the local optimization algorithm are integrated into REG-NAGA for further optimization. Simulation results show that REG-NAGA can search a better solution in the global scope and reduce the total number of states and the space complexity of regular expression matching effectively.

参考文献/References:

[1] Aho A V,Corasick M J. Efficient string matching: an aid to bibliographic search[J].Communications of the ACM, 1975,18(6): 333-340.
[2] Wu S,Manber U. A fast algorithm for multi-pattern searching[R].TR-94-17.Tucson(USA):University of Arizona,1994.
[3] Allauzen C,Crochemore M,Raffinot M. Factor oracle: a new structure for pattern matching[C]// SOFSEM’99: Theory and Practice of Informatics.Berlin: Springer,1999: 295-310.
[4] Yu F,Chen Z F,Diao Y,et al.Fast and memory-efficient regular expression matching for deep packet inspection[C]// Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communi-cations systems.New York(USA):Association for Computing Machinery,2006:93-102.
[5] Xu Qian,E Yuepeng,Ge Jingguo,et al.Efficient regular expression compression algorithm for deep packet inspection[J].Journal of Software,2009,20(8): 2214-2226.(in Chinese)
徐乾,鄂跃鹏,葛敬国,等.深度包检测中一种高效的正则表达式压缩算法[J].软件学报,2009,20(8): 2214-2226.
[6] Becchi M,Cadambi S.Memory-efficient regular expression search using state merging[C]// The 26th IEEE International Conference on Computer Communications.Anchorage(USA):IEEE Press,2007:1064-1072.
[7] Becchi M, Crowley P. A hybrid finite automaton for practical deep packet inspection[C]// Proceedings of the ACM CoNEXT Conference.New York(USA):Association for Computing Machinery,2007,1:1-12.
[8] Becchi M, Franklin M, Crowley P. A workload for evalu-ating deep packet inspection architectures[C]// IEEE International Symposium on Workload Characterization. Seattle (USA): IEEE Press , 2008: 79-89.
[9] Xiao Wude.An efficient regular expression grouping algorithm[J].Network and Computer Security,2010(4):57-59.(in Chinese)
肖武德.一种正则表达式的高效分组算法[J].计算机安全,2010(4):57-59.
[10] Zhang Shuzhuang,Luo Hao,Fang Binxing,et al.An efficient regular expression matching algorithm for network security inspection[J].Journal of Computers,2010,10: 1976-1986.(in Chinese)
张树壮,罗浩,方滨兴,等.一种面向网络安全检测的高性能正则表达式匹配算法[J]. 计算机学报,2010,10: 1976-1986.
[11] Luo Qinglin.Algorithms to speeding up multiple regular expressions matching for application traffic classification[D]. Beijing:Capital Normal University,2011.(in Chinese)
罗青林.适合应用层协议分类的多正则表达式匹配方法研究[D].北京:首都师范大学,2011.
[12] Yao Tie,Xu Qiang,He Jin.A grouping algorithm based on regular expression similarity for DFA construction[C]// IEEE 13th International Conference on Communication Technology(ICCT).Jinan(China):IEEE Press,2011:671-674.
[13] He Gang, Wang Yang, Wu Xiaochun.A regular expression grouping algorithm based on partitioning method[C]// The 3rd IEEE International Conference on Network Infrastructure and Digital Content (IC-NIDC).Beijing (China):IEEE Press,2012:271-274.
[14] Wei Qiang,Li Yunzhao,Chu Yanjie.Regular expression grouping algorithm based on graph partitioning[J].Computer Engineering,2012,38(18):137-139.(in Chinese)
魏强,李云照,褚衍杰.基于图划分的正则表达式分组算法[J].计算机工程,2012,38(18):137-139.
[15] Liu Tingwen,Sun Yong,Bu Dongbo,et al.1/(1-1/k):optimal algorithm for regular expression grouping[J].Journal of Software,2012,23(9):2261-2272.(in Chinese)
柳厅文,孙永,卜东波,等.正则表达式分组的1/(1-1/k):近似算法[J].软件学报,2012,23(9):2261-2272.
[16] Cai Liangwei,Liu Siqi,Li Xia.Regular expression grouping algorithm based on ant colony optimization[J].Journal of Shenzhen University Science and Engineering,2014,31(3):279-285.(in Chinese)
蔡良伟,刘思麒,李霞,等.基于蚁群优化的正则表达式分组算法 [J].深圳大学学报理工版,2014,31(3):279-285.
[17] Fu Zhe, Wang Kai, Cai Liangwei,et al.Intelligent grouping algorithms for regular expressions in deep inspection[C]// The 23rd International Conference on Computer Communication and Networks (ICCCN).Shanghai (China):IEEE Press,2014:1-8.
[18] Holland J H.Adaptation in natural and artificial systems:An introductory analysis with applications to biology,control,and artificial intelligence[M].Ann Arbor(USA):The University of Michigan Press,1975.
[19] Srinivas M,Patnaik L M.Adaptive probabilities of crossover and mutation in genetic algorithms[J].IEEE Transactions on Systems,Man and Cybernetics,1994,24(4):656-667.
[20] Xing Yingjie, Chen Zhentong, Sun Jing,et al.An improved adaptive genetic algorithm for job-shop scheduling problem[C]// The 3rd International Conference on Natural Computation.Haikou(China):[s.n.],2007,4:287-291.
[21] Sun Zhongyue,Guan Zhongliang, Wang Qin.An improved adaptive genetic algorithm for vehicle routing problem[C]// International Conference on Logistics Systems and Intelligent Management.Harbin(China):Springer,2010,1:116-120.
[22] Wang Fujun,Li Junlan,Liu Shiwei,et al.An improved adaptive genetic algorithm for image segmentation and vision alignment used in microelectronic bonding[J].IEEE/ASME Transactions on Mechatronics,2014,19(3):916-923.
[23] Hu Baofang,Sun Xiuli, Li Ying, et al.An improved adaptive genetic algorithm in cloud computing[C]// The 13th International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT).Beijing:IEEE Press,2012:294-297.
[24] Wang Wanliang,Wu Qidi,Song Yi.Modified adaptive genetic algorithms for solving job-shop scheduling problems[J].System Engineering Theory and Practice,2004,24(2):58-62.(in Chinese)
王万良,吴启迪,宋毅.求解作业车间调度问题的改进自适应遗传算法[J].系统工程理论与实践,2004,24(2):58-62.
[25] Shen Bin,Zhou Yingjun,Wang Jiahai.Research of job-shop scheduling problem based on self-adaptive genetic algorithm[J].Computer Application,2009,29(z2):161-164.(in Chinese)
沈斌,周莹君,王家海.基于自适应遗传算法的job shop调度问题研究[J].计算机应用,2009,29(z2):161-164.
[26] Jin Jing,Su Yong.An improved adaptive genetic algorithm[J].Computer Engineering and Application,2005,41(18):64-69.(in Chinese)
金晶,苏勇. 一种改进的自适应遗传算法[J].计算机工程与应用,2005,41(18):64-69.

相似文献/References:

[1]潘长城,徐晨,李国.解全局优化问题的差分进化策略[J].深圳大学学报理工版,2008,25(2):211.
 PAN Chang-cheng,XU Chen,and LI Guo.Differential evolutionary strategies for global optimization[J].Journal of Shenzhen University Science and Engineering,2008,25(No.3(221-330)):211.
[2]骆剑平,李霞.求解TSP的改进混合蛙跳算法[J].深圳大学学报理工版,2010,27(2):173.
 LUO Jian-ping and LI Xia.Improved shuffled frog leaping algorithm for solving TSP[J].Journal of Shenzhen University Science and Engineering,2010,27(No.3(221-330)):173.
[3]蔡良伟,李霞.基于混合蛙跳算法的作业车间调度优化[J].深圳大学学报理工版,2010,27(4):391.
 CAI Liang-wei and LI Xia.Optimization of job shop scheduling based on shuffled frog leaping algorithm[J].Journal of Shenzhen University Science and Engineering,2010,27(No.3(221-330)):391.
[4]张重毅,刘彦斌,于繁华,等.CDA市场环境模型进化研究[J].深圳大学学报理工版,2010,27(4):413.
 ZHANG Zhong-yi,LIU Yan-bin,YU Fan-hua,et al.Research on the evolution model of CDA market environment[J].Journal of Shenzhen University Science and Engineering,2010,27(No.3(221-330)):413.
[5]姜建国,周佳薇,郑迎春,等.一种双菌群细菌觅食优化算法[J].深圳大学学报理工版,2014,31(No.1(001-110)):43.[doi:10.3724/SP.J.1249.2014.01043]
 Jiang Jianguo,Zhou Jiawei,Zheng Yingchun,et al.A double flora bacteria foraging optimization algorithm[J].Journal of Shenzhen University Science and Engineering,2014,31(No.3(221-330)):43.[doi:10.3724/SP.J.1249.2014.01043]
[6]蔡良伟,刘思麒,李霞,等.基于蚁群优化的正则表达式分组算法[J].深圳大学学报理工版,2014,31(No.3(221-330)):279.[doi:10.3724/SP.J.1249.2014.03279]
 Cai Liangwei,Liu Siqi,Li Xia,et al.Regular expression grouping algorithm based on ant colony optimization[J].Journal of Shenzhen University Science and Engineering,2014,31(No.3(221-330)):279.[doi:10.3724/SP.J.1249.2014.03279]
[7]宁剑平,王冰,李洪儒,等.递减步长果蝇优化算法及应用[J].深圳大学学报理工版,2014,31(No.4(331-440)):367.[doi:10.3724/SP.J.1249.2014.04367]
 Ning Jianping,Wang Bing,Li Hongru,et al.Research on and application of diminishing step fruit fly optimization algorithm[J].Journal of Shenzhen University Science and Engineering,2014,31(No.3(221-330)):367.[doi:10.3724/SP.J.1249.2014.04367]
[8]刘万峰,李霞.车辆路径问题的快速多邻域迭代局部搜索算法[J].深圳大学学报理工版,2015,32(No.2(111-220)):196.[doi:10.3724/SP.J.1249.2015.02000]
 Liu Wanfeng,and Li Xia,A fast multi-neighborhood iterated local search algorithm for vehicle routing problem[J].Journal of Shenzhen University Science and Engineering,2015,32(No.3(221-330)):196.[doi:10.3724/SP.J.1249.2015.02000]
[9]王守觉,鲁华祥,陈向东,等.人工神经网络硬件化途径与神经计算机研究[J].深圳大学学报理工版,1997,14(1):8.
 Wang Shoujue,Lu Huaxiang,Chen Xiangdong and Zeng Yujuan.On the Hardware for Artificial Neural Networks and Neurocomputer[J].Journal of Shenzhen University Science and Engineering,1997,14(No.3(221-330)):8.
[10]陈星宇,周展,黄俊文,等.基于关键词挖掘的客户细分方法[J].深圳大学学报理工版,2017,34(No.3(221-330)):300.[doi:10.3724/SP.J.1249.2017.03300]
 Chen Xingyu,Zhou Zhan,Huang Junwen,et al.A keyword-based mining method for customer segmentation[J].Journal of Shenzhen University Science and Engineering,2017,34(No.3(221-330)):300.[doi:10.3724/SP.J.1249.2017.03300]

备注/Memo

备注/Memo:
Received:2014-12-23;Accepted:2015-03-14
Foundation:National Natural Science Foundation of China (61171124)
Corresponding author:Professor Cai Liangwei.E-mail:cailw@szu.edu.cn
Citation:Cai Liangwei,Cheng Lu,Li Jun,et al.Regular expression grouping optimization based on genetic algorithm[J]. Journal of Shenzhen University Science and Engineering, 2015, 32(3): 281-289.(in Chinese)
基金项目:国家自然科学基金资助项目 (61171124)
作者简介:蔡良伟(1964—),男(汉族),广东省阳江市人,深圳大学教授.E-mail:cailw@szu.edu.cn
引文:蔡良伟,程璐,李军,等.基于遗传算法的正则表达式规则分组优化[J]. 深圳大学学报理工版,2015,32(3):281-289.
更新日期/Last Update: 2015-05-11