图着色问题禁忌搜索改进算法
图着色问题是一个NP-hard问题,在现实中有广泛的应用,比如寄存器分配、机场调度等.禁忌搜索算法是一种经典的启发式搜索算法,在图着色问题的算法设计中广泛使用.禁忌搜索算法作为一个底层算子,也常被用于诸如混合进化算法(Hybrid Evolutionary Algorithm,HEA)的图染色算法设计中,对算法的性能起到了关键作用.因此,对禁忌搜索算法的改进对于促进图染色算法的研究具有现实意义.针对图着色问题,提出一种改进版禁忌搜索算法Tabucol+以增强搜索的集中性.算法在传统禁忌搜索策略的基础上,引入新的评分策略.实验结果显示,新的算法能够显著减少迭代次数和搜索时间,在个别算例上甚至取得了颜色数改进的效果.
禁忌搜索算法、图着色问题、同分顶点
49
TP301(计算技术、计算机技术)
2023-05-22（万方平台首次上网日期，不代表论文的发表时间）
共5页
82-86
