A memetic algorithm for the max–cut problem. (1st January 2015)

• Record Type: Journal Article
• Authors: Lin, Geng; Zhu, Wenxing
• Is Part Of: International journal of computing science and mathematics. Volume 6:Number 1(2015)
• Page Start: 69
• Page End: 77
• Publication Date: 2015-01-01
• Subjects: max–cut problem -- local search -- memetic algorithm -- combinatorial optimisation -- computing science -- memetics; Mathematics -- Periodicals; Computer science -- Periodicals; Mathematics -- Data processing -- Periodicals; 510.285
• DOI: 10.1504/IJCSM.2015.067544
• Languages: English
• ISSNs: 1752-5055

Abstract

Given an undirected graph G = (V, E) with a set V of vertices, and a set E of edges with weights, the max–cut problem consists of partitioning all vertices into two independent sets such that the sum of the weights of the edges between different sets is maximised. The max–cut problem is an NP–hard problem. An efficient memetic algorithm is proposed in this paper for the problem. The proposed memetic algorithm uses a local search procedure and a new crossover operator based on the encoding characteristic of the max–cut problem to generate new offsprings. Then the algorithm uses a function, which takes into account both the solution quality and the diversity of population, to control the population updating. Experiments were performed on three sets of benchmark instances of size up to 10, 000 vertices. Experiment results and comparisons demonstrate the effectiveness of the proposed algorithm in both solution quality and computational time.