A memetic algorithm for the max-cut problem
by Geng Lin; Wenxing Zhu
International Journal of Computing Science and Mathematics (IJCSM), Vol. 6, No. 1, 2015

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.

Online publication date: Thu, 19-Feb-2015

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Computing Science and Mathematics (IJCSM):
Login with your Inderscience username and password:

Username:        Password:          Forgotten your password?

Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com