基于带状态回溯个体进化的子结构发现  

Evolutionary substructure discovery algorithm based on individuals with state backtracking

作　　者：常新功[1] 寇纪淞[1] 李敏强[1] 

机构地区：[1]天津大学管理学院

出　　处：《计算机应用》2007年第8期1944-1947,1951,共5页journal of Computer Applications

基　　金：国家自然科学基金资助项目(70571057)

摘　　要：将进化算法引入图数据挖掘,以克服贪婪式查找易陷入局部极值的问题。针对图数据挖掘中经常遇到的子图同构问题,提出了带状态回溯个体的概念,从而使遗传算子的设计更为合理。另外,还提出了一种新的多样性保持方案,从种群的组成和个体的生成两个方面提高了种群的多样性。在进化过程中随时去掉当前种群中没有潜力的个体的机制使查找空间缩小了一半。实验结果表明,以上措施增强了算法的寻优能力,提高了算法的效率和解的质量。In order to overcome the limit that the greedy search, which is often used by some prevalent graphical data mining systems, may often end up by providing sub-optimal solutions, an evolutionary algorithm was imported to perform data mining on databases represented as graphs. In order to handle the subgraph isomorphism problem, the concept of individuals with state backtracking was proposed, where the state information of some potential individuals produced during the evolution were preserved, which contributed to the design of genetic operators. A new diversity keeping scheme was also proposed to preserve the diversity both from the composition of population and the way of generation of individuals. In addition, removing the individuals not potential in current population reduced the search space greatly. Experimental results show that these measures enhance the searching capability of the algorithm and hence increase both the efficiency of the algorithm and the quality of solutions.

关 键 词：进化算法 图数据挖掘 子结构发现 最小描述长度 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]