Journal of South China University of Technology (Natural Science Edition) ›› 2011, Vol. 39 ›› Issue (2): 136-140.doi: 10.3969/j.issn.1000-565X.2011.02.023

• Electronics, Communication & Automation Technology • Previous Articles     Next Articles

Adaptive Genetic Algorithm for Undirected Hamiltonian Graph

Hou Ai-min1  Hao Zhi-feng2  Chen Xiao-li3  Shen Dan-hua3   

  1. 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)

PDF

1282

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