Hybridization of decomposition and local search for multiobjective optimization

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

98 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Article number6709676
Pages (from-to)1808-1820
Journal / PublicationIEEE Transactions on Cybernetics
Volume44
Issue number10
Online published10 Jan 2014
Publication statusPublished - Oct 2014

Abstract

Combining ideas from evolutionary algorithms, decomposition approaches, and Pareto local search, this paper suggests a simple yet efficient memetic algorithm for combinatorial multiobjective optimization problems: memetic algorithm based on decomposition (MOMAD). It decomposes a combinatorial multiobjective problem into a number of single objective optimization problems using an aggregation method. MOMAD evolves three populations: 1) population PLfor recording the current solution to each subproblem; 2) population PPfor storing starting solutions for Pareto local search; and 3) an external population PEfor maintaining all the nondominated solutions found so far during the search. A problem-specific single objective heuristic can be applied to these subproblems to initialize the three populations. At each generation, a Pareto local search method is first applied to search a neighborhood of each solution in PPto update PLand PE. Then a single objective local search is applied to each perturbed solution in PLfor improving PLand PE, and reinitializing PP. The procedure is repeated until a stopping condition is met. MOMAD provides a generic hybrid multiobjective algorithmic framework in which problem specific knowledge, well developed single objective local search and heuristics and Pareto local search methods can be hybridized. It is a population based iterative method and thus an anytime algorithm. Extensive experiments have been conducted in this paper to study MOMAD and compare it with some other state-of-the-art algorithms on the multiobjective traveling salesman problem and the multiobjective knapsack problem. The experimental results show that our proposed algorithm outperforms or performs similarly to the best so far heuristics on these two problems.

Research Area(s)

  • Decomposition, local search, multiobjective knapsack problem, multiobjective optimization, multiobjective traveling salesman problem

Citation Format(s)

Hybridization of decomposition and local search for multiobjective optimization. / Ke, Liangjun; Zhang, Qingfu; Battiti, Roberto.
In: IEEE Transactions on Cybernetics, Vol. 44, No. 10, 6709676, 10.2014, p. 1808-1820.

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review