| 一种求解最大二等分问题的分散搜索算法 |
| |
| 引用本文： | 林 耿,朱文兴.一种求解最大二等分问题的分散搜索算法[J].福州大学学报(自然科学版),2014,42(6):823-827. |
| |
| 作者姓名： | 林 耿 朱文兴 |
| |
| 作者单位： | 1. 闽江学院数学系,福建福州,350108
2. 福州大学离散数学研究中心,福建福州,350116 |
| |
| 基金项目： | 国家自然科学基金资助项目(11301255,61170308); 福建省中青年教师教育科研项目(JA13246); 福建省教育厅省属高校科研专项(JK2012037). |
| |
| 摘 要： | 最大二等分问题是图论中的一个NP困难问题.本研究提出一种基于分散搜索框架的启发式算法求解最大二等分问题.该分散搜索算法采用Kernighan-Lin算法作为局部搜索算法,利用解的质量和解之间的距离构造参考集,通过两个可行解构造新的可行解.利用一些标准测试例子测试算法,实验结果与现存算法所得结果比较,表明该算法是有效的.
|
| 关 键 词： | 最大二等分问题 分散搜索 局部搜索 启发式算法 |
A scatter search algorithm for solving the max-bisection problem |
| |
| LIN Geng and ZHU Wen-xing.A scatter search algorithm for solving the max-bisection problem[J].Journal of Fuzhou University(Natural Science Edition),2014,42(6):823-827. |
| |
| Authors: | LIN Geng and ZHU Wen-xing |
| |
| Institution: | Department of Mathematics,Minjiang University,Fuzhou Fujian,Center for Discrete Mathematics and Theoretical Computer Science,Fuzhou University,Fuzhou Fujian |
| |
| Abstract: | The max-bisection problem is one of NP-hard problems in graph theory, and has a lot of applications. This paper presents a heuristic method based on the scatter search methodology for solving the max-bisection problem. This scatter search algorithm uses Kernighan-Lin algorithm as a local search procedure, and constructs reference sets by the solution quality and the distance between solutions, and generates a new feasible solution from two feasible solutions. A lot of benchmark instances from the literature are used to test the proposed algorithm, the experimental results and the comparison with existed algorithm show that the proposed algorithm is efficient. |
| |
| Keywords: | max-bisection problem scatter search local search heuristic |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《福州大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《福州大学学报(自然科学版)》下载免费的PDF全文 |
