机构地区: 深圳大学信息工程学院
出 处: 《深圳大学学报(理工版)》 2015年第3期281-289,共9页
摘 要: 为解决正则表达式匹配问题,提出一种基于正态自适应遗传优化的改进正则表达式分组算法.根据迭代次数的变化,利用正态函数自适应改变交叉概率Pc和变异概率Pm,采取最优保存策略保证最优个体不被数值大的Pc和Pm破坏.结合Becchi算法和局部寻优算法进一步优化.仿真结果表明,该算法能在全局范围内搜索到更好的解,能有效减少状态总数,降低正则表达式匹配的空间复杂度. 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 Pcand 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.