Speeding up a memetic algorithm   for the max-bisection problem

Wenxing  Zhu; Yanpo  Liu; Geng  Lin

doi:10.3934/naco.2015.5.151

Article Contents

2015, Volume 5, Issue 2: 151-168. Doi: 10.3934/naco.2015.5.151

This issue Previous Article A perturbation-based approach for continuous network design problem with emissions Next Article A wedge trust region method with self-correcting geometry for derivative-free optimization

Speeding up a memetic algorithm for the max-bisection problem

1.
Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, Fuzhou 350108
2.
Department of Mathematics, Minjiang University, Fuzhou, 350108

Received: September 2014

Revised: May 2015

Published: June 2015

Abstract / Introduction Related Papers Cited by

Abstract

Max-bisection of a weighted graph $G = (V, E)$ is to partition the vertex set $V$ into two subsets that have equal cardinality, such that the sum of the weights of the edges connecting vertices in different subsets is maximized. It is an NP-complete problem. Various heuristics have been proposed for solving the max-bisection problem and some of them get very good quality solutions, but are time consuming. In this paper, we propose several techniques to speeding up Lin and Zhu's memetic algorithm for this problem. It consists of a crossover operator with a greedy strategy, a fast modified Kernighan-Lin local search, and a new population updating function. Experiments are performed on 71 well-known G-set benchmark instances. Results show that the memetic algorithm is much faster than Wu and Hao's memetic algorithm, which can get best solutions up to now, on middle-scale and large-scale instances. Specifically, some current best known solutions of the test instances are improved.

Keywords:

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

Citation:

Related Papers

Cited by

References

[1]	C. Ashcraft and J. W. H. Liu, Using domain decomposition to find graph bisectors, BIT Numerical Mathematics, 37 (1997), 506-534.doi: 10.1007/BF02510238.
[2]	P. Austrin, S. Benabbas and K. Georgiou, Better balance by being biased: a 0.8776-approximation for max bisection, in Proceedings of SODA, (2013), 277-294. Full version available as arXiv eprint 1205.0458v2.
[3]	F. Barahona, M. Grötschel, M. Jünger and G. Reinelt, An application of combinatorial optimization to statistical physics and circuit layout design, Operations Research, 36 (1988), 493-513.
[4]	R. Battiti and A. Bertossi, Differential greedy for the 0-1 equicut problem, in Proceeding of the DIMACS Workshop on Network Design: Connectivity and Facilities Location (eds. D. Z. Du and P. M. Pardalos), 1997.
[5]	L. Brunetta, M. Conforti and G. Rinaldi, A branch-and-cut algorithm for the equicut problem, Mathematical Programming, 78 (1997), 243-263.doi: 10.1016/S0025-5610(97)00017-8.
[6]	K. C. Chang and D. H-C. Du, Efficient algorithms for layer assignment problems, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 6 (1987), 67-78.
[7]	P. Chardaire, M. Barake and G. P. McKeown, A PROBE-based heuristic for graph partitioning, IEEE Transactions on Computers, 56 (2007), 1707-1720.doi: 10.1109/TC.2007.70760.
[8]	R. K. F. Chung, Spectral Graph Theory, 92, AMS Bookstore, 1997.
[9]	C. Dang, L. He and I. K. Hui, A deterministic annealing algorithm for approximating a solution of the max-bisection problem, Neural Networks, 15 (2002), 441-458.
[10]	A. Duarte, F. Fernández, Á. Sánchez and A. Sanz, A hierarchical social metaheuristic for the max-cut problem, Lecture Notes in computer Science, 3004 (2004), 84-94.
[11]	U. Feige, M. Karpinski and M. Langberg, A note on approximating max-bisection on regular graphs, Information Processing Letters, 79 (2001), 181-188.doi: 10.1016/S0020-0190(00)00189-7.
[12]	C. M. Fiduccia and R. M. Mattheyses, A linear time heuristic for improving network partitions, in Proceedings of the 19th Design Automation Conference, (1982), 175-181.
[13]	A. Frieze and M. Jerrum, Improved approximation algorithm for max k-cut and max-bisection, Algorithmica, 18 (1997), 67-81.doi: 10.1007/BF02523688.
[14]	M. X. Goemans and D. P. Williamson, Improved approximation algorithms for Max-Cut and satisfiability problems using semidefinite programming, Journal of the ACM, 42 (1995), 1115-1145.doi: 10.1145/227683.227684.
[15]	E. Halperin and U. Zwick, A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems, Random Structures and Algorithms, 20 (2002), 382-402.doi: 10.1002/rsa.10035.
[16]	J. Hastad, Some optimal inapproachability results, in Proceedings of the 29th Annual ACM Symposium on the Theory of Computing, ACM, New York, (1997), 1-10.
[17]	C. Helmberg and F. Rendl, A spectral bundle method for semidefinite programming, SIAM Journal on Optimization, 10 (2000), 673-696.doi: 10.1137/S1052623497328987.
[18]	B. Hendrickson and R. Leland, An improved spectral graph partitioning algorithm for mapping parallel computations, SIAM Journal on Scientific Computing, 16 (1995), 452-469.doi: 10.1137/0916028.
[19]	J. H. Holland, Adaptation in Natural Artificial System, The University of Michigan Press (Second edition; MIT press), 1992.
[20]	K. Jansen, M. Karpinski, A. Lingas and E. Seidel, Polynomial time approximation schemes for Max-Bisection on planar and geometric graphs, SIAM Journal on Computing, 35 (2005), 110-119.doi: 10.1137/S009753970139567X.
[21]	R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations (eds. R. E. Miller and J. W. Thatcher), Plenum Press, (1972), 85-103.
[22]	M. Karpinski, M. Kowaluk and A. Lingas, Approximation algorithms for MAX-BISECTION on low degree regular graphs, Fundamenta Informaticae, 62 (2004), 369-375.
[23]	B. W. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs, The Bell System Technical Journal, 49 (1970), 291-307.
[24]	S. Khot, G. Kindler, E. Mossel and R. O'Donnell, Optimal inapproximability results for MAX-CUT and other 2-variable CSPs, SIAM Journal on Computing, 37 (2007), 319-357.doi: 10.1137/S0097539705447372.
[25]	D. E. Knuth, Seminumerical Algorithms, The Art of Computer Programming, Vol. 2, Addison-Wesley, Reading, MA, 1997.
[26]	K. Krishnan and J. Mitchell, A semidefinite programming based polyhedral cut and price approach for the Max-Cut problem, Computational Optimization and Applications, 33 (2006), 51-71.doi: 10.1007/s10589-005-5958-3.
[27]	R. B. Lin and S. Y. Chen, Conjugate conflict continuation graphs for multilayer constrained via minimization, Information Sciences, 177 (2007), 2436-2447.doi: 10.1016/j.ins.2007.01.013.
[28]	G. Lin and W. Zhu, An efficient memetic algorithm for solving the Max-Bisection problem, IEEE Transactions on Computers, 63 (2014), 1365-1376.doi: 10.1109/TC.2013.7.
[29]	A. F. Ling, C. X. Xu and L. Tang, A modified VNS metaheuristic for max-bisection problems, Journal of Computational and Applied Mathematics, 220 (2008), 413-421.doi: 10.1016/j.cam.2007.08.018.
[30]	R. Marti, A. Duarte and M. Laguna, Advanced scatter search for the max-cut problem, INFORMS Journal on Computing, 21 (2009), 26-38.doi: 10.1287/ijoc.1080.0275.
[31]	P. Moscato and C. Cotta, A gentle introduction to memetic algorithms, in Handbook of Metaheuristics (eds. F. Glover and G. A. Kochenberger), Kluwer, Norwell, Massachusetts, USA, 2003.doi: 10.1007/0-306-48056-5_5.
[32]	K. G. Murty and S. N. Kabadi, Some NP-complete problems in quadratic and nonlinear programming, Mathematical Programming, 39 (1987), 117-129.doi: 10.1007/BF02592948.
[33]	F. Neri, C. Cotta and P. Moscato, Handbook of Memetic Algorithms, Studies in Computational Intelligence, 379, Springer, 2011.doi: 10.1007/978-3-642-23247-3.
[34]	G. Palubeckis and V. Krivickiene, Application of multistart tabu search to the Max Cut problem, Information Technology and Control, 2 (2004), 29-35.
[35]	P. Raghavendra and N. Tan, Approximating CSPs with global cardinality constraints using SDP hierarchies, in Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2012, 373-387.
[36]	V. P. Shylo and O. V. Shylo, Solving the max-cut problem by the global equilibrium search, Cybernetics and Systems Analysis, 46 (2010), 744-754.
[37]	K. Sörensen and M. Sevaux, MA\|PM: memetic algorithms with population management, Computers and Operations Research, 33 (2006), 1214-1225.
[38]	C. C. de Souza, R. Keunings, L. A. Wolsey and O. Zone, A new approach to minimizing the front width in finite element calculations, Computer Methods in Applied Mechanics and Engineering, 111 (1994), 323-334.doi: 10.1016/0045-7825(94)90137-6.
[39]	D. Spielman, Spectral Graph Theory, Lecture Notes, Yale University, 2009.
[40]	E. W. Weisstein, Laplacian Matrix, MathWorld-A Wolfram Web Resource, 1995.
[41]	Q. Wu and J. K. Hao, Memetic search for the max-bisection problem, Computers and Operations Research, 40 (2013), 166-179.doi: 10.1016/j.cor.2012.06.001.
[42]	F. Xu, X. Ma and B. Chen, A new Lagrangian net algorithm for solving max-bisection problems, Journal of Computational and Applied Mathematics, 235 (2011), 3718-3723.doi: 10.1016/j.cam.2011.01.015.
[43]	Y. Y. Ye, A 0.699-approximation algorithm for Max-Bisection, Mathematical Programming, 90 (2001), 101-111.doi: 10.1007/PL00011415.