无向哈密顿图的自适应遗传算法

doi:10.3969/j.issn.1000-565X.2011.02.023

华南理工大学学报（自然科学版） ›› 2011, Vol. 39 ›› Issue (2): 136-140.doi: 10.3969/j.issn.1000-565X.2011.02.023

无向哈密顿图的自适应遗传算法

侯爱民¹郝志峰²陈小莉³沈丹华³

1．华南理工大学计算机科学与工程学院，广东广州 510006；2．广东工业大学计算机学院广东广州 510090；3．东莞理工学院计算机学院，广东东莞 523808

收稿日期:2010-06-02 修回日期:2010-10-28 出版日期:2011-02-25 发布日期:2011-01-02
通信作者: 侯爱民(1963-)，男，在职博士生，东莞理工学院副教授，主要从事组合优化问题的理论研究与算法设计、进化优化算法的设计及应用研究 E-mail:zhham@163.com
作者简介:侯爱民(1963-)，男，在职博士生，东莞理工学院副教授，主要从事组合优化问题的理论研究与算法设计、进化优化算法的设计及应用研究
基金资助:
广东省自然科学基金重点项目(9251009001000005)；广东省科技计划项目(2008B080701005)

Adaptive Genetic Algorithm for Undirected Hamiltonian Graph

Hou Ai-min¹ Hao Zhi-feng² Chen Xiao-li³ Shen Dan-hua³

1. South China university of technology, computer science and engineering college, guangdong guangzhou 510006; 2. Guangdong university computer college of guangdong guangzhou 510090; 3. Dongguan institute of computer college, guangdong dongguan 523808

Received:2010-06-02 Revised:2010-10-28 Online:2011-02-25 Published:2011-01-02
Contact: 侯爱民(1963-)，男，在职博士生，东莞理工学院副教授，主要从事组合优化问题的理论研究与算法设计、进化优化算法的设计及应用研究 E-mail:zhham@163.com
About author:侯爱民(1963-)，男，在职博士生，东莞理工学院副教授，主要从事组合优化问题的理论研究与算法设计、进化优化算法的设计及应用研究
Supported by:
广东省自然科学基金重点项目(9251009001000005)；广东省科技计划项目(2008B080701005)

摘要/Abstract

摘要： 回溯搜索方法和路径扩展方法是判定无向哈密顿图的两种重要途径,其缺点是要么进行路径选择的回溯,从而造成指数阶时间开销,要么由于剪枝技术而遗漏正确答案.任何一个无向哈密顿圈总是可以分解成若干个原子圈,这些原子圈按照某种次序以单条公共边连通.根据这个特征,文中使用原子圈和基本圈作为染色体,设计成可拼接/可分解的遗传编码,提出一种新的自适应遗传算法,用于降低时间开销,保证正确判定.对一些实际案例的测试结果验证了该算法的有效性.

关键词: 无向哈密顿图, 回溯搜索, 路径扩展, 拼接, 分解, 自适应遗传算法

Abstract:

The two important methods of distinguishing undirected Hamiltonian graphs,namely the backtracking search and the path extension,are both of their own disadvantages.Specifically,the former requires some backtracking operations on path selection,which results in exponential time cost.However,the latter may fail in finding correct answers due to the branch trimming.As any undirected Hamiltonian cycle can always be decomposed into several atomic cycles which are connected with one another by one common edge in a certain order,atomic cycles and basic cycles are used as chromosomes to derive a genetic code with the properties of splicing and decomposing,and a new adaptive genetic algorithm based on the genetic code is proposed to reduce the time cost and guarantee the distinguishing.Experimental results on some real cases demonstrate that the proposed algorithm is effective.

Key words: undirected Hamiltonian graph, backtracking search, path extension, splicing, decomposition, adaptive genetic algorithm

侯爱民郝志峰陈小莉沈丹华. 无向哈密顿图的自适应遗传算法[J]. 华南理工大学学报（自然科学版）, 2011, 39(2): 136-140.

Hou Ai-min Hao Zhi-feng Chen Xiao-li Shen Dan-hua. Adaptive Genetic Algorithm for Undirected Hamiltonian Graph[J]. Journal of South China University of Technology (Natural Science Edition), 2011, 39(2): 136-140.

[1]	赵建东, 朱丹, 刘佳欣. 基于时间序列分解与门控循环单元的地铁换乘客流预测 [J]. 华南理工大学学报(自然科学版), 2022, 50(5): 22-31.
[2]	刘慧婷, 李茵捷, 郭玲玲, 等. 基于异构信息网络的紧耦合推荐算法[J]. 华南理工大学学报（自然科学版）, 2021, 49(7): 66-75.
[3]	李静王晨张家旭. 基于UniTire轮胎模型的汽车行驶速度估计[J]. 华南理工大学学报（自然科学版）, 2021, 49(5): 47-55.
[4]	魏彤辉, 孟广伟, 左文杰, 等. 基于单变量函数分解的结构区间静力响应分析[J]. 华南理工大学学报（自然科学版）, 2021, 49(3): 47-54.
[5]	古万荣, 谢贤芬, 张子烨, 等. 面向非随机缺失数据的协同过滤评分方法[J]. 华南理工大学学报（自然科学版）, 2021, 49(1): 47-57.
[6]	王秋红闵锐王清峰. 3 种阻燃粉体抑制锆粉云爆炸强度的效果和机理[J]. 华南理工大学学报（自然科学版）, 2020, 48(8): 72-81,90.
[7]	郭明军, 李伟光, 杨期江, 等. 基于稀疏算法的大型转子多工况轴心轨迹提纯[J]. 华南理工大学学报（自然科学版）, 2020, 48(4): 45-53.
[8]	孙苗, 吴立, 袁青, 等 . 基于 CEEMDAN 的爆破地震波信号时频分析[J]. 华南理工大学学报（自然科学版）, 2020, 48(3): 76-82.
[9]	牛海清, 宋廷汉, 罗新, 等. 基于S 变换与奇异值分解的局部放电信号去噪方法[J]. 华南理工大学学报（自然科学版）, 2020, 48(2): 9-15.
[10]	孙季丰朱雅婷王恺. 基于 DeblurGAN 和低秩分解的去运动模糊[J]. 华南理工大学学报（自然科学版）, 2020, 48(1): 32-41,50.
[11]	郭明军, 李伟光, 杨期江, 等. 基于 SVD 原理的 PCA 特征频率提取算法及其应用[J]. 华南理工大学学报(自然科学版), 2020, 48(1): 1-9.
[12]	孙苗吴立周玉纯马晨阳汪煜烽. 水下钻孔爆破地震波信号的最优降噪光滑模型[J]. 华南理工大学学报（自然科学版）, 2019, 47(8): 31-37.
[13]	冯蕴雯路成薛小锋李永凯. 基于重要度民机备件单级初始库存优化配置[J]. 华南理工大学学报（自然科学版）, 2018, 46(9): 140-148.
[14]	吴建斌贾炎柯刘逸雯. 基于图像编码及拼接的无载体信息隐藏[J]. 华南理工大学学报（自然科学版）, 2018, 46(5): 32-38.
[15]	吕琳陈明海徐凡. 基于边界约束的交互式图案拼接方法[J]. 华南理工大学学报（自然科学版）, 2018, 46(12): 20-25,33.

无向哈密顿图的自适应遗传算法

Adaptive Genetic Algorithm for Undirected Hamiltonian Graph

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价