| 解决图着色问题的一种新禁忌搜索算法 |
| |
| 引用本文： | 马艳萍,吴晓军,杨明成.解决图着色问题的一种新禁忌搜索算法[J].计算机应用与软件,2012(2):279-281. |
| |
| 作者姓名： | 马艳萍 吴晓军 杨明成 |
| |
| 作者单位： | 陕西师范大学计算机科学学院;大唐移动西安分公司研发部 |
| |
| 摘 要： | 为了解决典型的组合优化问题——图顶点着色问题,结合增强SEQ算法和禁忌搜索算法的优点与缺点,提出一种基于增强SEQ的新禁忌搜索算法(SEQTS)。该算法利用增强SEQ算法较强的构造较优解的能力来为禁忌搜索算法构造多个较优初始解,然后进行多初始解禁忌搜索以找到全局最优解。计算机实验的结果表明该算法(SEQTS)有较好的寻优能力,增强了该算法的有效性。
|
| 关 键 词： | 禁忌搜索 增强SEQ算法 多初始解 图顶点着色 |
A NEW TABU SEARCH ALGORITHM FOR GRAPH COLOURING |
| |
| Ma Yanping,Wu Xiaojun,Yang Mingcheng.A NEW TABU SEARCH ALGORITHM FOR GRAPH COLOURING[J].Computer Applications and Software,2012(2):279-281. |
| |
| Authors: | Ma Yanping Wu Xiaojun Yang Mingcheng |
| |
| Affiliation: | 1(School of Computer and Science,Shaanxi Normal University,Xi’an 710062,Shaanxi,China)2(R&D Department,Datang Mobile Company,Xi’an 710061,Shaanxi,China) |
| |
| Abstract: | In this paper,in order to find the global optimum of a typical combinatorial optimisation problem,colouring the vertices of a graph,we propose a new Tabu search algorithm,SEQTS,based on enhanced SEQ in combination with the advantages and disadvantages of the enhanced SEQ algorithm and Tabu search algorithm.It uses the strong capability of the enhanced SEQ algorithm in structuring optimal solution to construct multiple initial optimum solutions for Tabu search algorithm at first,and then performs Tabu search on these initial solutions for getting global optimum.It is proved by computer experimental results that this new algorithm(SEQTS) has preferable search ability which strengthens its effectiveness. |
| |
| Keywords: | Tabu search Enhanced SEQ algorithm Multiple initial solutions Colouring vertices of graph |
| 本文献已被 CNKI 等数据库收录！ |
|
