图着色问题的新遗传算法

被引：9

作者：

韩丽霞 ^{[1
]}

王宇平 ^{[2
]}

机构：

[1] 西安电子科技大学理学院

[2] 西安电子科技大学计算机学院

来源：

西安电子科技大学学报 | 2008年 / 02期

关键词：

图着色问题; 遗传算法; 局部搜索; 全局收敛;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

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

引用

页码：309 / 313

页数：5