ABSTRACT
Multiobjective combinatorial optimization problems (MCOPs) are combinatorial problems that involve the optimization of several, typically conflicting objectives. When designing a stochastic local search (SLS) algorithm for single-objective problems, one typically starts by implementing some form of an iterative improvement algorithm. In fact, it is relatively straightforward to apply iterative improvement algorithms also to multiobjective problems by modifying the acceptance criterion, making use of the component-wise ordering of solutions, and the use of an archive of nondominated solutions found so far. Many population-based SLS algorithms rely on a mapping of the objective function value vector of each candidate solution in the archive into a single value, a rank, where the lower a candidate solution’s rank is, the higher are its chances of being chosen. In nonproprietary approaches, an SLS algorithm is embedded into a general framework that mainly says how an underlying SLS algorithm is applied to tackle an MCOP.
