Performance of simulated annealing, tabu search, and evolutionary algorithms for multi-objective network partitioning

Most real optimization problems often involve multiple objectives to optimize. In single-objective optimization there exists a global optimum, while in the multi-objective case no optimal solution is clearly defined but rather a set of solutions, so called Pareto-optimal set. Thus, the goal of multi-objective strategies is to obtain an approximation to this set. However, the majority of this kind of problem cannot be solved exactly as they have very large and highly complex search spaces. In recent years, meta-heuristics have become important tools for solving multi-objective problems encountered in industry as well as in the theoretical field. Thus far, there exist many comparative studies about the performance of evolutionary algorithms, but there are few papers dealing with non-evolutionary strategies. The goal of this paper is to analyze the performance of both paradigms in a realistic problem. In concrete, we have adapted five multi-objective meta-heuristics, based on Simulated Annealing, Tabu Search, and Evolutionary Methods, to solve the Network Partitioning Problem.