An effective iterated tabu search for the maximum bisection problem
An effective iterated tabu search for the maximum bisection problem
复制标题
最大二分问题的有效迭代禁忌搜索
DOI：
10.1016/j.cor.2016.12.012
复制
发表时间：
2017-05
影响因子：
4.6
通讯作者：
Wang Yang
中科院分区：
文献类型：
--
作者：
Ma Fuda;Hao Jin-Kao;Wang Yang
给定边加权图 G=(V, E)，最大二分问题涉及将 V 的顶点划分为基数相等的两个不相交子集，使得穿过两个子集的边的权重和最大化。在本研究中，我们提出了一种迭代禁忌搜索（ITS）算法来解决该问题。 ITS 采用两个不同的搜索运算符，分为三个搜索阶段，以有效地探索搜索空间。采用桶排序来保证ITS算法较高的计算效率。基于文献中 71 个知名基准实例的实验表明，与最先进的方法相比，ITS 具有很强的竞争力，并发现了 8 个基准实例的改进的最著名结果（新的下限）。还研究了该算法的关键要素。
Given an edge weighted graph G=(V, E), the maximum bisection problem involves partitioning the vertices of V into two disjoint subsets of equal cardinality such that the weight sum of the edges crossing the two subsets is maximized. In this study, we present an Iterated Tabu Search (ITS) algorithm to solve the problem. ITS employs two distinct search operators organized into three search phases to effectively explore the search space. Bucket sorting is used to ensure a high computational efficiency of the ITS algorithm. Experiments based on 71 well-known benchmark instances of the literature demonstrate that ITS is highly competitive compared to state-of-the-art approaches and discovers improved best-known results (new lower bounds) for 8 benchmark instances. The key ingredients of the algorithm are also investigated.
登录
查看更多内容
DOI：
10.1287/ijoc.1080.0275
发表时间：
2009
期刊：
INFORMS J. Comput.
影响因子：
--
作者：
R. Martí;A. Duarte;M. Laguna
通讯作者：
R. Martí;A. Duarte;M. Laguna
DOI：
--
发表时间：
2001
期刊：
--
影响因子：
--
作者：
T. Cormen;C. Leiserson;R. Rivest;C. Stein
通讯作者：
T. Cormen;C. Leiserson;R. Rivest;C. Stein
针对最大二分问题的改进的 VNS 元启发式
影响因子：
2.4
作者：
Tang, Le;Xu, Cheng-xian;Ling, Ai-fan
通讯作者：
Ling, Ai-fan
DOI：
10.1016/j.cor.2012.06.001
发表时间：
2013
期刊：
Comput. Oper. Res.
影响因子：
--
作者：
Qinghua Wu;Jin-Kao Hao
通讯作者：
Qinghua Wu;Jin-Kao Hao
影响因子：
2.2
作者：
S. Burer;R. Monteiro
通讯作者：
S. Burer;R. Monteiro