摘要
将进化算法与爬山算法的混合进化算法引入图数据挖掘,以克服贪婪式查找易陷入局部极值的问题.针对子图结构发现问题中实例易丢失的特点,提出了一种新的遗传操作——个体协同算子,使得代表同一子结构的不同个体能够以协同的方式进行查找.另外,还提出了一种基于年龄段和个体生成方式的多样性保持方案,以从种群的组成和个体的生成两个方面保持和提高种群的多样性,同时还有助于个体协同算子的执行.在进化过程中随时以新生成的单边子结构替换当前种群中没有潜力的个体的机制在缩小查找空间的同时还使得进化过程成为一个更为完全的查找过程.实验结果表明,以上措施增强了算法的寻优能力,能够获得更优的解.
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.
出处
《系统工程学报》
CSCD
北大核心
2008年第4期472-478,共7页
Journal of Systems Engineering
基金
国家自然科学基金资助项目(70571057)
新世纪优秀人才支持计划资助项目(NCET-05-0253)
关键词
混合进化算法
协同
图数据挖掘
子结构发现
最小描述长度
hybrid evolutionary algorithms
cooperation
graphical data mining
substructure discovery
minimum description length （MDL）
