2. Second, Variable Neighborhood Search [10], combining multiple neighborhood operators into a single algorithm in order to avoid local optimality in the first place.

In the proposed concept, both paradigms are combined and extended within a search framework handling not only a single but a set of alternatives at once.

The main principle of the algorithm is sketched in Figure 1. Starting from an initial solution x1, an improving, intensifying search is performed until a set **of locally optimal alternatives is**
identified, stored in a set P
approx representing the approximation of the true Pareto set P**. No**
further improvements are possible from this point. In this initial step, a set of neighborhoods ensures that all identified alternatives are locally optimal not only to a single but to a set of neighborhoods.

This principle, known from Variable Neighborhood Search, promises to lead to better results as it is known that all global optima are also locally optimal with **respect to all possible neighborhoods**
while this is not necessarily the case for local optima.

 2009

![0_image_0.png](0_image_0.png)

MIC
After the identification of a locally optimal set, a diversification step is performed on a solution x2 using a perturbation operator, continuing search from the perturbed solution x3**. The perturbation operator has to be significantly different from the neighborhoods used in intensification, as**
otherwise the following search would return to the previous **solution. On the other hand however,**
the perturbation should not entirely destroy the characteristics of the alternative. Doing that would result in a random restart of the search without keeping promising attributes of solutions.

The PILS metaheuristic may be formalized as given in Algorithm 1. The intensification of the algorithm, illustrated in steps (1) and (3) of Figure 1 is between the lines 6 to 21, the description of the diversification, given in step (2) of Figure 1 is between the lines 22 to 26.

It can be seen, that the algorithm computes a set of neighborhoods for each alternative. The sequence in which the neighborhoods are computed is arranged in a random fashion, described in line 13 of Algorithm 1. This introduces an additional element of diversity to the concept, as otherwise the search might be biased by a certain sequence of **neighborhoods.**
Hamburg, Germany, June 13–16, 2009