计算机工程

• 人工智能及识别技术 • 上一篇    下一篇

基于量子进化的给定围长图构造算法

冯晓华,孙永奇   

  1. (北京交通大学 计算机与信息技术学院 交通数据分析与挖掘北京市重点实验室,北京 100044)
  • 收稿日期:2016-08-29 出版日期:2017-10-15 发布日期:2017-10-15
  • 作者简介:冯晓华(1991—),女,硕士研究生,主研方向为智能计算、高性能计算;孙永奇(通信作者),教授、博士生导师。
  • 基金项目:
    国家自然科学基金(61572005,61272004)。

Construction Algorithm of Given Girth Graphs Based on Quantum Evolution

FENG Xiaohua,SUN Yongqi   

  1. (Beijing Key Lab of Traffic Data Analysis and Mining,School of Computer and Information Technology, Beijing Jiaotong University,Beijing 100044,China)
  • Received:2016-08-29 Online:2017-10-15 Published:2017-10-15

摘要: 构造给定围长的极图是图论难题之一,特别是在顶点数规模不断增大的情况下会出现组合爆炸的现象。针对该问题,提出一种构造给定围长图的算法,通过在生成个体、调整个体中充分利用极图的特性,使算法达到较高的收敛速度与收敛精度。实验结果表明,通过构造围长为10的图,与粒子群优化算法、遗传算法相比,该算法达到次优解和最优解的准确率最高,构造围长为11的图,可得到相应的极图边数的下界。

关键词: 进化算法, 量子进化算法, 极图, 围长,

Abstract: To construct an extremal graph with a given girth is still a challenging problem of graph theory.Especially when the vertex number increasex combination explosion will appear.Thus,this paper proposes an algorithm for constructing graphs with given girth based on quantum evolution.By making full use of the characteristics of the extremal graphs in producing and adjusting the individuals,it makes the algorithm achieve higher convergence speed and precision.Experimental results show that,by constructing the graphs with the girth of 10,the proposed algorithm is compared with the other algorithms,namely Particle Swarm Optimization(PSO) algorithm and Genetic Algorithm(GA),the algorithm can achieve the optimal solutions and near optimal solutions with the highest accuracy.It uses the proposed algorithm to construct the graphs with the girth of 11,and gives lower bounds of the sizes of extremal graphs with the girth 11.

Key words: evolutionary algorithm, Quantum Evolutionary Algorithm(QEA), extremal graph, girth, cycle

中图分类号: