Output details
11 - Computer Science and Informatics
University of Stirling
A Multilevel Memetic Approach for Improving Graph k-Partitions
<22> This paper presents a highly effective multilevel memetic algorithm for graph partitioning which is specially tailored for the given search landscape. Indeed, the efficiency of the dedicated backbone-based multi-parent crossover and the perturbation-based tabu search procedure, both based on a stronger intensification, is justified by high landscape correlation and the backbone phenomenon within high quality solutions. The innovative approach described here was able to improve on a large number of commonly used graph partitioning instances. These results are included in Walshaw's Graph Partitioning Archive (http://staffweb.cms.gre.ac.uk/~wc06/partition/).