1.6.1. The GRASP method

The GRASP method was proposed by Feo and Resende [FEO 95] and is one of the simplest methods in metaheuristics. This is an iterative method that at each iteration undergoes a step constructing the solution, followed by a step involving a local search to return the best workable solution to the given problem, as described in algorithm 1.5.

The construction step (algorithm 1.6) inserts an element at each iteration in the workable solution. The choice of this element is carried out randomly based on a restrictive list of candidates comprising only the best ones. The quality of a candidate is obtained based on the benefits that it brings to the solution under construction and is updated during the following iterations. Therefore, the result is a solution in which local optimality cannot be guaranteed. A local search method is then applied, which brings us to the second step of the algorithm. Based on the solution obtained during the construction phase, a local search method such as the descent method, simulated annealing or even tabu search is applied in order to improve this solution.

The GRASP method is a simple method that executes with a relatively small computation time and which leads to good results. It can therefore easily be integrated among other metaheuristics.

1.6.2. Variable neighborhood search

Variable neighborhood search [MLA 97] is based on the systematic change in the neighborhood during the search.

We start by selecting a set of neighborhood structures N_k where k = 1, 2, …, k_max and determine an initial solution s. Then, three steps are applied: perturbation, local search and the move or continuation starting from s. Perturbation consists of randomly generating a solution s^′ in the neighborhood of s defined by the kth neighborhood structure. From s^′, a local search method is applied which returns s^′′. The move makes it possible to refocus the search around s^′′. As a matter of fact, if s^′′ improves the best known solution, then s is updated with s^′′ and the algorithm is restarted from the first neighborhood, otherwise the following neighborhood is considered. This method then allows the exploration of several types of neighborhoods until the current solution is improved. Once at this stage, the neighborhoods of the new solution are explored and so on until a stopping criterion is satisfied.

Thus, when the variable neighborhood search is performed, it is necessary to determine the number and type of neighborhood to utilize, the exploration order of the neighborhood during the search (in general, in an increasing manner depending on the size of the neighborhood), the strategy for changing neighborhood, the local search method and the stopping criterion.

Variants of this method have been proposed such as variable neighborhood descent [HAN 01a], variable neighborhood search and decomposition [HAN 01b] and biased variable neighborhood search [HAN 00].

Variable neighborhood descent makes use of the steepest descent method during the local search and we stop if the solution is improved, otherwise the following type of neighborhood is considered.

Search and variable neighborhood decomposition utilize the same steps as the variable neighborhood search except that one selects a neighbor s^′ of s and its neighborhood is generated following the same type of neighborhood such that the intersection of the neighborhoods of s and s^′ be empty and the steepest descent method is applied. As a result, the local optimum s^′′ is obtained. The intersection of the neighborhood of s and s^′ is taken, s^′′ is inserted and once again the steepest descent method is applied. The move is then carried from the last local optimum obtained.

Biased variable neighborhood search is capable of keeping the best solution s_opt found throughout the whole search and in order to encourage the exploration of the search space, the refocusing of the search is done by using a parameter α and a function ρ that calculates the distance between two solutions s and s^′. In effect, based on a solution s, a neighbor s^′ is selected by employing the first type of neighborhood, then the local search method is applied thereto yielding the local optimum s^′′. If s^′′ improves s_opt, then s_opt is updated with s^′′. Then, the search is refocused on s^′′ if f(s^′′) − α ∗ ρ(s, s^′) < f(s), the search is restarted from the first neighborhood with s^′′ as a starting solution; otherwise, the next neighborhood is addressed.

1.6.3. Guided local search

To escape local optima, some methods use several neighborhood structures such as variable neighborhood search while others addtionally employ some memory to avoid revisiting a solution such as tabu search. Introduced by Voudouris, guided local search [VOU 99] utilizes a technique whose solution set and neighborhood structure remains identical throughout the search, but that dynamically modifies the objective function. This technique makes it possible to orientate the search toward another region of the search space, thus encouraging exploration.

In the case of minimization problems, equation [1.1] represents this modification that is reflected in the increase in the objective function with a set of penalizations.

[1.1]

where:

• – g(s) is the objective function of a given problem;
• – λ is the regularization parameter;
• – p_i are the penalization parameters;
• – M is the number of attributes defining the solutions;
• – I_i(s) allows specifying whether the solution s contains the attribute i and therefore takes 1 or 0 as values.

The regularization parameter λ enables us to determine the significance of the variation in the objective function and to control the influence of the information related to the search.

The penalization parameters p_i correspond to the weights of the constraints of each attribute i with respect to the solution. At each iteration, only the attributes trapped in a local optimum that maximize the utility are penalized by incrementing p_i by 1. This utility is calculated according to the expression [1.2] based on the cost of this attribute c_i and its penalization parameter p_i.

[1.2]

1.6.4. Iterated local search

Iterated local search, proposed by Lourenço in 2001 [LOU 01, LOU 03], is the most general model of exploratory algorithms. In effect, from a solution s, an intermediate solution s^′ is selected by applying a perturbation, then a local search is performed culminating in a local optimum (s^′′) that can be kept based on the acceptation criterion.

It should be noted that the perturbation is intended to direct the search toward another basin of attraction. Thus, it significantly impacts the search, it must be neither too small nor too large. A value that is too small will not make it possible to explore more solutions and the algorithm will quickly stagnate. On the other hand, a large value will give the algorithm a character similar to “random-restart” algorithms, which will bias the search. As a result, non-deterministic perturbation is a means to avoid going through the same cycles again. It is characterized by the so-called “perturbation force” that can be fixed or variable, random or adaptive. If the force is adaptive, exploration and exploitation criteria can be controlled. By increasing this force, exploration is preferred and by decreasing it, exploitation is preferred.

The objective of the acceptance criterion is to determine the conditions that the new local optimum must satisfy in order to replace the current solution. This criterion thus enables the implementation of an equilibrium by keeping the newly found local optimum or by restarting from the previously found local optimum.

1.7.1. The Nelder–Mead simplex method

Initially proposed by Spendley in 1962 [SPE 62], then improved by Nelder and Mead in 1965 [NEL 65], the simplex method aims at solving unconstrained optimization problems by utilizing a succession of simplex transformations.

Initially, a set of (n +1)vertices in a n-dimensional space is initialized therefore constituting the current simplex. This initialization can be achieved by generating a point then by defining the other points around it toward each of the directions of the space with an amplitude a:

[1.3]

Until the stopping condition is reached, the simplex is transformed with reflection α, expansion γ and contraction β operators applied to the worst vertex defined by equations [1.5]–[1.8], the goal being to replace the vertex with the highest cost with another having a lower cost.

In the following, vector represents the centroid with respect to all vertices of the simplex except

[1.4]

• – Reflection operator:

The reflection operator is applied on whose cost is f_h in order to obtain with cost f_r. If f_l ≤ f_r < f_s, vertex is replaced by vertex with f_l the cost of the best vertex and f_s the cost of vertex classified in the second position.

[1.5]

• – Expansion operator:

If f_r < f_l, the expansion operator is applied on vertex obtaining vertex of cost f_e. In the case where f_e < f_r, vertex is accepted otherwise vertex is.

[1.6]

1. – Contraction operator:

If f_r ≥ f_s, the contraction operator is applied and vertex of cost f_c is obtained. If f_s ≤ f_r < f_h, vertex is obtained with equation [1.7] and if f_c ≤ f_r, vertex is accepted. On the other hand, if f_r ≥ f_h, vertex is obtained with equation [1.8] and if f_c′ ≤ f_h, vertex is accepted.

[1.7]

[1.8]

If no vertex is accepted during the previous steps, all vertices are updated:

[1.9]

Just like all path-based algorithms, this method leads to a convergence toward a local optimum and in order to overcome this limitation of the conventional method, it is possible to restart it once a local optimum is reached, reinitializing every time.

1.7.2. The noising method

Introduced by Charon in 1993 [CHA 93], the noising method is a single-solution metaheuristic based on the descent approach. From an initial solution and at each iteration, noise is added to the objective function such that the values of the objective function be directed toward a descent. The noise added to the current solution changes from a given initial value and decreases at each iteration until the value is zero or a minimal value. The variation of this noise can be defined in various ways. Algorithm 1.10 summarizes the approach of the noising method.

In this method, two parameters have to be determined, the noise rate and the decreasing rate of this noise. The first consists of defining the values of r_max and r_min with r_min usually set to 0 while the second parameter may follow the geometric decreasing function defined by equation [1.10] or other more advanced methods [CHA 06]. However, the choice of these parameters has a significant impact on the performance of this method.

[1.10]

1.7.3. Smoothing methods

The main goal of smoothing methods is to reduce the number of local optima as well as the depth of the basins of attraction by modifying the objective function yet without changing search space [GLO 86b, JUN 94]. Once this smoothing operation is performed, any path-based method or metaheuristic can generally be utilized.

First, this approach involves subdividing the problem being considered into several successive instances relating to a specific search space. First of all, the simplest instance is dealt with and a local search method is then applied as a second step. The solution obtained is kept as an initial solution of the problem related to the next instance, which becomes increasingly more complex at each iteration and therefore enables this solution to be improved.

The smoothing makes it possible to decrease the likelihood of being trapped in a local optimum. In addition, this technique can reduce the complexity of the algorithm that implements it. Moreover, the computational time of the algorithm can prove considerable.