On dominance-based multiobjective local search: design, implementation and experimental analysis on scheduling and traveling salesman problems.

*(English)*Zbl 1358.90046Summary: This paper discusses simple local search approaches for approximating the efficient set of multiobjective combinatorial optimization problems. We focus on algorithms defined by a neighborhood structure and a dominance relation that iteratively improve an archive of nondominated solutions. Such methods are referred to as dominance-based multiobjective local search. We first provide a concise overview of existing algorithms, and we propose a model trying to unify them through a fine-grained decomposition. The main problem-independent search components of dominance relation, solution selection, neighborhood exploration and archiving are largely discussed. Then, a number of state-of-the-art and original strategies are experimented on solving a permutation flowshop scheduling problem and a traveling salesman problem, both on a two- and a three-objective formulation. Experimental results and a statistical comparison are reported in the paper, and some directions for future research are highlighted.

##### MSC:

90B35 | Deterministic scheduling theory in operations research |

90C27 | Combinatorial optimization |

90C29 | Multi-objective and goal programming |

##### Keywords:

multiobjective optimization; local search; flowshop scheduling problem; traveling salesman problem
PDF
BibTeX
XML
Cite

\textit{A. Liefooghe} et al., J. Heuristics 18, No. 2, 317--352 (2012; Zbl 1358.90046)

Full Text:
DOI

##### References:

[1] | Random bit climbers on multiobjective MNK-landscapes: effects of memory and population climbing, IEICE Trans. Fundam., 1, 88-A, 334-345, (2005) |

[2] | A dynasearch neighborhood for the bicriteria traveling salesman problem, No. 535, 153-176, (2004), Berlin · Zbl 1162.90537 |

[3] | Design of multi-objective evolutionary algorithms: application to the flow shop scheduling problem, CEC 2002, Piscataway |

[4] | PISA—a platform and programming language independent interface for search algorithms, EMO 2003, Faro · Zbl 1037.68743 |

[5] | Do additional objectives make a problem Harder, GECCO 2007, New York |

[6] | Coello Coello, C.A., Lamont, G.B., Van Veldhuizen, D.A.: Evolutionary Algorithms for Solving Multi-Objective Problems, 2nd edn. Genetic and Evolutionary Computation Series. Springer, New York (2007) · Zbl 1142.90029 |

[7] | Job shop scheduling with genetic algorithms, ICGA 1985, Hillsdale |

[8] | Deb, K.: Multi-Objective Optimization using Evolutionary Algorithms. Wiley, Chichester (2001) · Zbl 0970.90091 |

[9] | A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Trans. Evol. Comput., 2, 6, 182-197, (2002) |

[10] | Effective hybrid stochastic local search algorithms for biobjective permutation flowshop scheduling, HM 2009, Berlin |

[11] | Approximative solution methods for multiobjective combinatorial optimization, Top, 1, 12, 1-89, (2004) · Zbl 1148.90300 |

[12] | Hybrid metaheuristics for multi-objective combinatorial optimization, No. 114, 221-259, (2008), Berlin |

[13] | Connectedness of efficient solutions in multiple criteria combinatorial optimization, Eur. J. Oper. Res., 1, 97, 159-166, (1997) · Zbl 0923.90127 |

[14] | A tabu search procedure to solve multiobjective combinatorial optimization problems, No. 455, 291-300, (1997), Berlin |

[15] | On operators and search space topology in multi-objective flow shop scheduling, Eur. J. Oper. Res., 1, 181, 195-206, (2007) · Zbl 1121.90057 |

[16] | Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discrete Math., 5, 287-326, (1979) · Zbl 0411.90044 |

[17] | Tabu search for multiobjective optimisation: MOTS, MCDM 1997, Cape Town |

[18] | A multi-objective genetic local search algorithm and its application to flowshop scheduling, IEEE Trans. Syst. Man Cybern., 28, 392-403, (1998) |

[19] | Genetic local search for multi-objective combinatorial optimization, Eur. J. Oper. Res., 1, 137, 50-71, (2002) · Zbl 1002.90051 |

[20] | Bounded Pareto archiving: theory and practice, No. 535, 39-64, (2004), Berlin · Zbl 1140.90489 |

[21] | Knowles, J., Thiele, L., Zitzler, E.: A tutorial on the performance assessment of stochastic multiobjective optimizers. TIK Report 214, Computer Engineering and Networks Laboratory (TIK), ETH Zurich, Zurich, Switzerland (revised version) (2006) |

[22] | Approximating the nondominated front using the Pareto archived evolution strategy, Evol. Comput., 2, 8, 149-172, (2000) |

[23] | An introduction to multiobjective metaheuristics for scheduling and timetabling, No. 535, 91-129, (2004), Berlin · Zbl 1139.90420 |

[24] | Combining convergence and diversity in evolutionary multi-objective optimization, Evol. Comput., 3, 10, 263-282, (2002) |

[25] | Running time analysis of evolutionary algorithms on a simplified multiobjective knapsack problem, Nat. Comput., 1, 3, 37-51, (2004) · Zbl 1074.68065 |

[26] | Combinatorial optimization of stochastic multi-objective problems: an application to the flow-shop scheduling problem, EMO 2007, Matsushima |

[27] | Paradiseo-MOEO: a software framework for evolutionary multi-objective optimization, No. 272, 87-117, (2010), Berlin · Zbl 1189.90143 |

[28] | A software framework based on a conceptual unified model for evolutionary multiobjective optimization: paradis EO-MOEO, Eur. J. Oper. Res., 2, 209, 104-112, (2011) |

[29] | Speed-up techniques for solving large-scale biobjective TSP, Comput. Oper. Res., 3, 37, 521-533, (2010) · Zbl 1173.90534 |

[30] | Two-phase Pareto local search for the biobjective traveling salesman problem, J. Heuristics, 3, 16, 475-510, (2010) · Zbl 1189.90145 |

[31] | Miettinen, K.: Nonlinear Multiobjective Optimization. International Series in Operations Research and Management Science, vol. 12. Kluwer Academic, Boston (1999) · Zbl 0949.90082 |

[32] | Minimum spanning trees made easier via multi-objective optimization, Nat. Comput., 3, 5, 305-319, (2006) · Zbl 1173.90535 |

[33] | A two-phase local search for the biobjective traveling salesman problem, EMO 2003, Faro · Zbl 1036.90561 |

[34] | A study of stochastic local search algorithms for the biobjective QAP with correlated flow matrices, Eur. J. Oper. Res., 3, 169, 943-959, (2006) · Zbl 1079.90113 |

[35] | Stochastic local search algorithms for multiobjective combinatorial optimization: a review, No. 13, pp., (2007), New York |

[36] | Design and analysis of stochastic local search for the multiobjective traveling salesman problem, Comput. Oper. Res., 9, 36, 2619-2631, (2009) · Zbl 1179.90302 |

[37] | Pareto local optimum sets in the biobjective traveling salesman problem: an experimental study, No. 535, 177-199, (2004), Berlin · Zbl 1070.90102 |

[38] | On local optima in multiobjective combinatorial optimization problems, Ann. Oper. Res., 1, 156, 83-97, (2007) · Zbl 1145.90067 |

[39] | Convergence properties of some multi-objective evolutionary algorithms, CEC 2000, Piscataway |

[40] | Some considerations about computational complexity for multiobjective combinatorial problems, No. 294, 222-231, (1986), Berlin |

[41] | Simulated annealing for multiobjective optimization problems, MCDM 1992, Taipei, Taiwan |

[42] | Benchmarks for basic scheduling problems, Eur. J. Oper. Res., 64, 278-285, (1993) · Zbl 0769.90052 |

[43] | Talbi, E.G.: Metaheuristics: From Design to Implementation. Wiley, New York (2009) · Zbl 1190.90293 |

[44] | A hybrid evolutionary approach for multicriteria optimization problems: application to the fow shop, EMO 2001, Zurich |

[45] | T’Kindt, V., Billaut, J.C.: Multicriteria Scheduling: Theory, Models and Algorithms. Springer, Berlin (2002) · Zbl 1106.90035 |

[46] | MOSA method: a tool for solving multiobjective combinatorial optimization problems, J. Multi-Criteria Decis. Anal., 4, 8, 221-236, (1999) · Zbl 0935.90034 |

[47] | Zitzler, E., Laumanns, M., Thiele, L.: SPEA2: Improving the strength Pareto evolutionary algorithm. TIK Report 103, Computer Engineering and Networks Laboratory (TIK), ETH Zurich, Zurich, Switzerland (2001) |

[48] | Performance assessment of multiobjective optimizers: an analysis and review, IEEE Trans. Evol. Comput., 2, 7, 117-132, (2003) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.