J4

• 研究论文 • 上一篇    下一篇

图着色问题的新遗传算法

韩丽霞1;王宇平2
  

  1. (1. 西安电子科技大学 理学院,陕西 西安 710071;
    2. 西安电子科技大学 计算机学院,陕西 西安 710071)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2008-04-20 发布日期:2008-03-28
  • 通讯作者: 韩丽霞

Novel genetic algorithm for the graph coloring problem

HAN Li-xia1;WANG Yu-ping2
  

  1. (1. School of Science, Xidian Univ., Xi′an 710071, China;
    2. School of Computer Science and Technology, Xidian Univ., Xi′an 710071, China)
  • Received:1900-01-01 Revised:1900-01-01 Online:2008-04-20 Published:2008-03-28
  • Contact: HAN Li-xia

摘要: 针对遗传算法求解图着色问题需多次产生初始种群的问题,提出了一种改进算法.该算法采用比较机制,淘汰不可行的基因,然后使用动态的适应度函数,使得有效个体以较大的概率存活到下一代种群中,从而达到无需多次产生初始种群的目的.与传统框架下的算法相比,新算法求得最优解的时间至少缩短了51%,且具有从一个局部最优解快速跳到下一个局部最优解,最终收敛到全局最优解的优点.

关键词: 图着色问题, 遗传算法, 局部搜索, 全局收敛

Abstract: Generic genetic algorithms need generate initial population iteratively for solving the coloring problem. Based on this problem, an improved algorithm is presented. The novel algorithm adopts a comparative mechanism to eliminate the unfeasible genes, and gives the valid individual a greater probability to survive to the next generation by using the dynamic fitness function. Thus, the proposed algorithm avoids the repetitious production of the initial population. Compared with the algorithms under the traditional architecture, the proposed algorithm can shorten the time of finding the optimal solution at least by up to 51 percent. Moreover, the novel algorithm has the advantages of jumping from a local optimal solution to next one quickly and converging to the global optimal solution in the end.

Key words: graph coloring problem, genetic algorithm, local search, global convergence

中图分类号: 

  • TB11