Memetic search for the max-bisection problem
Memetic search for the max-bisection problem
复制标题
DOI：
10.1016/j.cor.2012.06.001
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Qinghua Wu;Jin-Kao Hao
中科院分区：
文献类型：
--
作者：
Qinghua Wu;Jin-Kao Hao
给定一个无向图G=（V，E），其边的权值都在G的顶点集上，最大二分问题（MBP）是将顶点集V划分为两个基数相等的子集V1和V2，使得与V1和V2相交的边的权值之和最大化.放松等基数约束，导致最大割问题（MCP）。在这项工作中，我们提出了一个模因算法的MBP，它集成了分组交叉算子和禁忌搜索优化过程。建议的交叉算子保留了最大的共同顶点分组相对于父解决方案，同时控制后代解决方案和它的父母之间的距离。对71个著名的G集基准实例的广泛实验研究表明，我们的模因算法在许多情况下改进了MBP和MCP的当前最知名的解决方案。
Given an undirected graph G=(V,E) with weights on the edges, the max-bisection problem (MBP) is to find a partition of the vertex set V into two subsets V1and V2of equal cardinality such that the sum of the weights of the edges crossing V1and V2is maximized. Relaxing the equal cardinality, constraint leads to the max-cut problem (MCP). In this work, we present a memetic algorithm for MBP which integrates a grouping crossover operator and a tabu search optimization procedure. The proposed crossover operator preserves the largest common vertex groupings with respect to the parent solutions while controlling the distance between the offspring solution and its parents. Extensive experimental studies on 71 well-known G-set benchmark instances demonstrate that our memetic algorithm improves, in many cases, the current best known solutions for both MBP and MCP.