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

被引:23
作者
Datta, Dilip [1 ]
Figueira, Jose Rui [2 ]
机构
[1] Natl Inst Technol Silchar, Dept Mech Engn, Silchar 788010, India
[2] Ecole Mines, INPL, Dept Genie Ind, Lab LORIA, F-54042 Nancy, France
关键词
Multi-objective optimization; Graph partitioning; Genetic algorithm; Differential evolution; Particle swarm optimization; GENETIC ALGORITHM; OPTIMIZATION; ADAPTATION; SEARCH;
D O I
10.1016/j.asoc.2011.01.044
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
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. (C) 2011 Elsevier B.V. All rights reserved.
引用
收藏
页码:3976 / 3987
页数:12
相关论文
共 39 条
  • [1] Abbass HA, 2002, IEEE C EVOL COMPUTAT, P831, DOI 10.1109/CEC.2002.1007033
  • [2] Balanced graph partitioning
    Andreev, Konstantin
    Raecke, Harald
    [J]. THEORY OF COMPUTING SYSTEMS, 2006, 39 (06) : 929 - 939
  • [3] Baños R, 2003, LECT NOTES COMPUT SC, V2611, P143
  • [4] BANOS R, 2007, J MATH MODELLING ALG, V6, P213, DOI DOI 10.1007/S10852-006-9041-6
  • [5] BARUCH Z, 1999, 5 INT C ENG MOD EL S, P19
  • [6] Bean J. C., 1994, ORSA Journal on Computing, V6, P154, DOI 10.1287/ijoc.6.2.154
  • [7] A tabu search heuristic and adaptive memory procedure for political districting
    Bozkaya, B
    Erkut, E
    Laporte, G
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2003, 144 (01) : 12 - 26
  • [8] Büche D, 2003, LECT NOTES COMPUT SC, V2632, P267
  • [9] Bui TN, 1996, IEEE T COMPUT, V45, P841, DOI 10.1109/12.508322
  • [10] Conover WJ, 1999, Practical nonparametric statistics