| 图着色问题的新遗传算法 |
| |
| 引用本文： | 韩丽霞,王宇平. 图着色问题的新遗传算法[J]. 西安电子科技大学学报(自然科学版), 2008, 35(2): 309-313 |
| |
| 作者姓名： | 韩丽霞 王宇平 |
| |
| 作者单位： | (1. 西安电子科技大学 理学院，陕西 西安 710071; 2. 西安电子科技大学 计算机学院，陕西 西安 710071) |
| |
| 摘 要： | 针对遗传算法求解图着色问题需多次产生初始种群的问题，提出了一种改进算法．该算法采用比较机制，淘汰不可行的基因，然后使用动态的适应度函数，使得有效个体以较大的概率存活到下一代种群中，从而达到无需多次产生初始种群的目的．与传统框架下的算法相比，新算法求得最优解的时间至少缩短了51％，且具有从一个局部最优解快速跳到下一个局部最优解，最终收敛到全局最优解的优点．
|
| 关 键 词： | 图着色问题 遗传算法 局部搜索 全局收敛 |
| 文章编号： | 1001-2400(2008)02-0309-05 |
| 修稿时间： | 2007-06-26 |
Novel genetic algorithm for the graph coloring problem |
| |
| HAN Li-xia,WANG Yu-ping. Novel genetic algorithm for the graph coloring problem[J]. Journal of Xidian University, 2008, 35(2): 309-313 |
| |
| Authors: | HAN Li-xia WANG Yu-ping |
| |
| Affiliation: | (1. School of Science, Xidian Univ., Xi′an 710071， China;2. School of Computer Science and Technology, Xidian Univ., Xi′an 710071， China) ; |
| |
| 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 a... |
| |
| Keywords: | graph coloring problem genetic algorithm local search global convergence |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《西安电子科技大学学报(自然科学版)》浏览原始摘要信息 |
|
点击此处可从《西安电子科技大学学报(自然科学版)》下载全文 |
