基于个体协同的子图结构发现混合进化算法  

Hybrid evolutionary algorithm for substructure discovery based on individual cooperation

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

机构地区：[1]天津大学管理学院,天津300072 [2]山西财经大学信息管理学院,山西太原030006

出　　处：《系统工程学报》2008年第4期472-478,共7页Journal of Systems Engineering

基　　金：国家自然科学基金资助项目(70571057);新世纪优秀人才支持计划资助项目(NCET-05-0253)

摘　　要：将进化算法与爬山算法的混合进化算法引入图数据挖掘,以克服贪婪式查找易陷入局部极值的问题.针对子图结构发现问题中实例易丢失的特点,提出了一种新的遗传操作——个体协同算子,使得代表同一子结构的不同个体能够以协同的方式进行查找.另外,还提出了一种基于年龄段和个体生成方式的多样性保持方案,以从种群的组成和个体的生成两个方面保持和提高种群的多样性,同时还有助于个体协同算子的执行.在进化过程中随时以新生成的单边子结构替换当前种群中没有潜力的个体的机制在缩小查找空间的同时还使得进化过程成为一个更为完全的查找过程.实验结果表明,以上措施增强了算法的寻优能力,能够获得更优的解.To overcome the limit that the greedy search may often give sub-optimal solutions, a hybrid evolutionary algorithm which combines the hill-climbing and evolutionary algorithm is developed to per- form data mining on graphical databases. ~ring the searching process, losing instances is common and vital to the algorithm performance. To address this issue, an individual cooperation operator is proposed, which enables different individuals to search the same substructure in a cooperative way. A new mecha- nism is also proposed to preserve the diversity both from the composition of population and the way of generation of individuals, which is helpful to individual cooperation. In addition, replacing the individu- als not potential in current population with new generated single-edge substructures not only reduces the search space but also makes the searching process more complete. Experimental results show that these measures successfully improve the searching capability of the algorithm and can get better results.

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

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