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.
Type de document :
Article dans une revue
Liste complète des métadonnées
Contributeur : Jose Rui Figueira <>
Soumis le : mardi 21 juin 2011 - 16:46:31
Dernière modification le : jeudi 11 janvier 2018 - 06:21:48




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〉



Consultations de la notice