基于近似个体协同的进化子结构发现  

Evolutionary Algorithm for Substructure Discovery Based on Approximate Individual Cooperation

作　　者：常新功[1] 李宏 

机构地区：[1]山西财经大学信息管理学院,山西太原030031 [2]山西省电子产品检验所,山西太原030024

出　　处：《计算机技术与发展》2010年第9期106-110,114,共6页Computer Technology and Development

基　　金：山西省自然科学基金项目(2010011022-1);山西省高校科技研究开发项目(20081023)

摘　　要：SUBDUE是一个主流的图数据挖掘算法。为克服其贪婪式查找易陷入局部极值的问题,将进化算法与爬山算法相结合并引入图数据挖掘,较好地权衡了算法的探查和利用能力。另外,针对图数据挖掘中普遍存在的实例易丢失的问题,采用了个体协同的查找方法,该方法与常见的种群间协同进化算法不同,可以使同一种群中的个体进行协同查找,重新找回丢失的实例。同时,还给出了一种具有多项式时间复杂度的近似图匹配算法以改善个体间协同的性能。实验结果表明,以上措施增强了算法的执行效率及寻优能力,能够获得更优的解。SUBDUE is a representative graph-based data mining algorithm.To overcome the limit that the greedy search adopted by SUBDUE may often give sub-optimal solutions,a hybrid evolutionary algorithm,which balances the exploration and exploitation of search by combining the hill-climbing and EA,is developed to perform data mining on graphical databases.In addition,during the searching process,losing instances is common and vital to the algorithm performance.To address this issue,adopt the individual cooperation strategy which is greatly different from the common cooperatively evolutionary approach based on population cooperation.The new strategy enables individuals in the same population to search in a cooperative way and gets back the lost instances.At the same time,an approximate graph matching algorithm with polynomial time complexity is also proposed to improve the performance of the process of individual cooperation.Experimental results show that these measures successfully improve the efficiency and the searching capability of the algorithm and can get better results.

关 键 词：进化算法 协同 图数据挖掘 子结构发现 近似图匹配 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]