A tabu search based hybrid evolutionary algorithm for the max-cut problem

•We design a hybrid evolutionary algorithm (TSHEA) for the max-cut problem.•Results disclose TSHEA discovers new best solutions for 15 out of 91 instances.•Analysis indicates the effectiveness of the designed key components.

This paper presents a tabu search based hybrid evolutionary algorithm (TSHEA) for solving the max-cut problem. The proposed algorithm integrates a distance-and-quality based solution combination operator and a tabu search procedure based on neighborhood combination of one-flip and constrained exchange moves. Comparisons with leading reference algorithms from the literature disclose that the proposed algorithm discovers new best solutions for 15 out of 91 instances, while matching the best known solutions on all but 4 instances. Analysis indicates that the neighborhood combination and the solution combination operator play key roles to the effectiveness of the proposed algorithm.

Graphical abstractFigure optionsDownload full-size imageDownload as PowerPoint slide