Skip to Main content Skip to Navigation
Journal articles

Graph partitioning by multi-objective real-valued metaheuristics: A comparative study

Abstract : The graph partitioning is usually tackled as a single-objective optimization problem. Moreover, various problem-specific versions of different algorithms are proposed for solving this integer-valued problem, thus confusing practitioners in selecting an effective algorithm for their instances. On the other hand, although various metaheuristics are currently in great consideration towards different problem-domains, these are yet to be investigated widely to this problem. In this article, a novel attempt is made to investigate whether some common and established metaheuristics can directly be applied to different search spaces, instead of going through various problem-specific algorithms. For this, some mechanisms are proposed for handling the graph partitioning problem by general multi-objective real-valued genetic algorithm, differential evolution, and particle swarm optimization. Some algorithmic modifications are also proposed for improving the performances of the metaheuristics. Finally, the performances of the metaheuristics are compared in terms of their computer memory requirements, as well as their computational runtime and solution qualities based on some test cases with up to five objectives.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/inria-00602180
Contributor : Jose Rui Figueira <>
Submitted on : Tuesday, June 21, 2011 - 4:46:31 PM
Last modification on : Tuesday, December 18, 2018 - 4:42:06 PM

Identifiers

Collections

Citation

José Rui Figueira, Dilip Datta. Graph partitioning by multi-objective real-valued metaheuristics: A comparative study. Applied Soft Computing, Elsevier, 2011, 11 (5), pp.3976-3087. ⟨10.1016/j.asoc.2011.01.044⟩. ⟨inria-00602180⟩

Share

Metrics

Record views

168