Stochastic Local Search Algorithms for Multiobjective Combinatorial Optimization: Methods and Analysis, Vol. 295 Book

Multiobjective Combinatorial Optimization Problems (MCOPs) arise in many real-life applications and they are among the hardest optimization problems. Therefore, high-quality approximations that can be obtained in reasonable time are, in practice, preferable to the often infeasible long computation times required for finding the optimum. Stochastic Local Search (SLS) algorithms were shown to give state-of-the-art results for many other problems, but little is known on how to design and analyse them for MCOPs. The main purpose of this book is to fill this gap. We start by defining two search models that correspond to two distinct ways of tackling MCOPs by SLS algorithms. Notions of local optima for MCOPs are formally introduced and related to the typical outcome of SLS algorithms. Moreover, we present a systematic approach for the design of these algorithms based on the notion of SLS components and a general guideline to empirically analyse algorithm performance. Finally, several SLS algorithms and SLS components are tested on the Multiobjective Traveling Salesman Problem and the Multiobjective Quadratic Assignment Problem. The effect of instance features and SLS components on the performance of the SLS algorithms are identified by experimental design techniques. The results obtained clearly indicate that the best performing variants are new state-of-the-art algorithms.