一种求解子图同构问题的改进遗传算法  

Improved Genetic Algorithm for Subgraph Isomorphism Problem

作　　者：项英倬 魏强 游凌 石浩[2] XIANG Ying-zhuo;WEI Qiang;YOU Ling;SHI Hao(National Key Laboratory of Science and Technology on Blind Signal Processing,Chengdu 610041,China;Department of Automation,University of Science and Technology of China,Hefei 230031,China)

机构地区：[1]盲信号处理国家重点实验室,成都610041 [2]中国科学技术大学自动化系,合肥230031

出　　处：《计算机科学》2019年第B06期98-101,共4页Computer Science

基　　金：国家自然科学基金(61174124)资助

摘　　要：子图同构(SubgraphIsomorphism)技术在计算机视觉、人工智能以及生物化学工程等领域具有重要的应用。文章聚焦于子图同构问题的求解算法,提出了一种基于基因遗传算法的改进算法。结合子图同构的特点,针对遗传算法中的杂交过程和进化过程,改进了传统的子代生成算法,提出了一种新的适应度函数来评估子代的适应性。新算法可以指引搜索过程更快地收敛到最优解,并能够以更高的概率求得最优解。通过仿真实验表明,提出的改进算法相较于传统的算法能够更好地处理大规模子图,并取得更好的效果。Subgraph isomorphism plays an important role in computer vision,artificial intelligence and bio-chemical engineering.This paper focused on the subgraph isomorphism(SI)problem and proposed a novel method based on the genetic algorithm to solve it.The sub-generation producing method is improved during the crossover and evolution process.Moreover,a new fitness function was presented to measure the fitness of the population.The new algorithm is more fast to get convergence and can find the optimal solutions with higher probability.Experiments show that the proposed improved algorithm outperforms other traditional methods by processing large graphs.

关 键 词：子图同构 遗传算法 适应度函数 杂交过程 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]