A memetic algorithm for the max-cut problem

DOI10.1504/IJCSM.2015.067544MaRDI QIDQ2221588zbMATH OpenOpenAlexFDO

Authors Geng Lin, Wenxing Zhu

Publication date 2 February 2021

Published in International Journal of Computing Science and Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1504/ijcsm.2015.067544

zbMATH Keywords

combinatorial optimisationcomputing sciencelocal searchmax-cut problemmemetic algorithmmemetics

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Evolutionary algorithms, genetic algorithms (computational aspects) (68W50) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Review text

Summary: 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.

Recommendations

• Memetic search for the max-bisection problem
• Speeding up a memetic algorithm for the max-bisection problem
• An efficient memetic algorithm for the graph partitioning problem
• Advanced scatter search for the max-cut problem
• A memetic algorithm for graph coloring

Cited in

(12)

• A memetic algorithm for graph coloring
• An effective iterated tabu search for the maximum bisection problem
• A memetic algorithm with bucket elimination for the still life problem
• Greedy differencing edge-contraction heuristic for the max-cut problem
• Speeding up a memetic algorithm for the max-bisection problem
• A memetic algorithm for the minimum sum coloring problem
• Memetic search for the max-bisection problem
• Estimation of distribution algorithm for the max-cut problem
• Evolutionary Computation in Combinatorial Optimization
• Memetic algorithm for the antibandwidth maximization problem
• An efficient memetic algorithm for the graph partitioning problem
• Maximum cut in fuzzy nature: models and algorithms

This page was built for publication: A memetic algorithm for the max-cut problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2221588)