A Memetic Approach for the Max-Cut Problem

TitreA Memetic Approach for the Max-Cut Problem
Type de publicationCommunication
TypeCommunication avec actes dans un congrès
Année2012
LangueAnglais
Date du colloque2012
Titre du colloque12th International Conference, PPSN 12
Titre des actes ou de la revueParallel Problem Solving from Nature - PPSN XII
Volume7492
Pagination297 - 306
AuteurWu, Qinghua, Hao, Jin-Kao
PaysItalie
EditeurSpringer Berlin Heidelberg
VilleTaormine
ISBN978-3-642-32963-0 / 978-3-642-32964-7
Mots-clésalgorithm analysis and problem complexity, Artificial Intelligence (incl. Robotics), Computation by Abstract Devices, Computational Biology/Bioinformatics, Discrete Mathematics in Computer Science, graph partitioning, Local search, memetic algorithm, Multi-parent crossover, pattern recognition
Résumé en anglais

The max-cut problem is to partition the vertices of a weighted graph G = (V,E) into two subsets such that the weight sum of the edges crossing the two subsets is maximized. This paper presents a memetic max-cut algorithm (MACUT) that relies on a dedicated multi-parent crossover operator and a perturbation-based tabu search procedure. Experiments on 30 G-set benchmark instances show that MACUT competes favorably with 6 state-of-the-art max-cut algorithms, and for 10 instances improves on the best known results ever reported in the literature.

Notes

Date du colloque : 09/2012

URL de la noticehttp://okina.univ-angers.fr/publications/ua4511
DOI10.1007/978-3-642-32964-7_30
Lien vers le document en ligne

http://dx.doi.org/10.1007/978-3-642-32964-7_30