摘要
针对遗传算法求解图着色问题需多次产生初始种群的问题,提出了一种改进算法.该算法采用比较机制,淘汰不可行的基因,然后使用动态的适应度函数,使得有效个体以较大的概率存活到下一代种群中,从而达到无需多次产生初始种群的目的.与传统框架下的算法相比,新算法求得最优解的时间至少缩短了51%,且具有从一个局部最优解快速跳到下一个局部最优解,最终收敛到全局最优解的优点.
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 traditiona[ architecture, the proposed a[gorithm 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.
出处
《西安电子科技大学学报》
EI
CAS
CSCD
北大核心
2008年第2期309-313,共5页
Journal of Xidian University
基金
国家自然科学基金资助(60374063)
关键词
图着色问题
遗传算法
局部搜索
全局收敛
graph coloring problem
genetic algorithm
local search
global convergence
