1
Single Solution Based Metaheuristics

1.1. Introduction

In daily life, optimizing is a common activity for both individuals and professionals. For example, the process of optimizing involves minimizing production time and expenditure, and maximizing profit and performance. As a result, optimization has become a discipline in itself to solve various problems, particularly in the economic sector [SAM 69], in the field of biology [GOT 82] and in various industries [YOS 00]. To solve these problems, technology is used to implement algorithms that simulate real problems in order to achieve results that will subsequently be used according to the intended purpose. These simulations can be simple but also very complex. The developed algorithms can be accurate or approximated, leading to the global optimum or to a solution closed to the global optimum. The objective of optimization is to find the global and/or the local optimum or optima. Depending on the optimization problem being addressed, one or more methods can be applied, and one of them may be more suitable than the others.

These methods include the class of path-based methods also called single-solution metaheuristics. These methods are algorithms in which the search for the optimum is achieved by manipulating a single solution throughout the progression of the algorithm. From an initial solution, the latter evolves throughout the algorithm following a certain mechanism until the stopping criterion is reached. Furthermore, the acceptance of a solution instead of another is carried out by means of various ways based on the proposed model. The principal characteristic of pattern-search heuristics is reflected by the fact that they mainly favor the use of exploitation by focusing their search in a given region of the search space.

In this chapter, we are going to introduce a number of path-based methods starting with most common algorithms, notably descent methods, simulated annealing, microcanonical annealing and even tabu search. We will proceed with exploratory local search algorithms that incorporate other path-based methods such as the Greedy Randomized Adaptive Search (GRASP) method, variable neighborhood search, guided local search and iterated local search. We are also going to present other methods such as Nelder and Mead's simplex method, the noising method and smoothing methods.

1.2. The descent method

The descent method (called "hill climbing" in maximization problems) is based on a randomly initialized solution or initialized with a greedy method. It then selects a solution in its neighborhood that strictly improves the current solution. This selection can be done in a number of different ways. The retained solution may be the first feasible solution that improves the objective function or the best feasible solution of the entire neighborhood. Depending on this choice, the method is, respectively, called simple descent method or steepest descent method.

Algorithm 1.1: The steepest descent method

The descent method is one of the simplest methods found in the literature; however, it presents a significant limitation. It may find itself easily trapped in a local minimum and therefore encourages exploitation and not exploration. In order to overcome this problem and be able to visit different regions of the search space, a variant called the restarted descent method has been implemented and involves executing the algorithm several times, thus allowing that various regions of the search space be visited. Nonetheless, another technique can be applied in order to escape from local minima, notably by accepting a degrading solution with a certain probability, a technique that can be found in simulated annealing.

1.3. Simulated annealing

Simulated annealing [KIR 84] is known for being the first metaheuristic to propose a process to escape local optima, and so by implementing the Metropolis algorithm proposed in 1953 [MET 53]. It is a method inspired from the annealing process practiced in metallurgy, which consists of melting metal at high temperature to be then cooled to a stable condition, called thermodynamic equilibrium, is obtained. This stable state may be "good" or "bad", that is with minimal energy or not. Indeed, when the metal is quickly cooled, deformations can arise, whereas a "perfect" metal is achieved if the cooling process is adequate. The temperature corresponds to the control parameter of the metal stability.

By analogy, based on a random solution s, a solution s´ is generated in the neighborhood of s. If this neighbor solution improves the current solution, s is updated. Otherwise, i´ can also be accepted following the probability exp(-?f/T). This probability makes it possible to accept a degrading solution in the case where the solution s´ presents a small degradation ?f with respect to s or when the temperature T is large enough. Therefore, exploration is preferred. However, this probability becomes smaller when knowing that the temperature follows a decreasing function and is updated at each iteration, thereby making exploitation more suitable.

Algorithm 1.2: Simulated annealing

Simulated annealing therefore depends on the temperature and its evolution. If it follows a strongly decreasing function, the algorithm is trapped in a local optimum. This is then referred to as premature convergence. Otherwise, the global optimum can be reached but optimality remains unguaranteed.

On the other hand, simulated annealing implements the Metropolis algorithm proposed in 1953 [MET 53], which may require a quite significant computation time hence microcanonical annealing.

1.4. Microcanonical annealing

Microcanonical annealing was introduced in 1987 by Bernard [BAR 87] and its model is described by algorithm 1.3. This method has similarities with the principles implemented in simulated annealing. Microcanonical annealing involves reducing the total energy based on a total high energy by decreasing the kinetic energy between two levels. This reduction follows a given decreasing function and allows the algorithm to converge toward optimal solutions. This method utilizes the algorithm proposed by Creutz in 1983 [CRE 83] whose objective was to maximize the entropy for a constant total energy by means of a succession of transitions.

Algorithm 1.3: Microcanonical annealing

In general, starting from a randomly drawn initial state s0 with a high energy E0 and a demon energy initialized with a value of 0, an energy reduction with a fixed percentage is applied followed by the Creutz algorithm until it reaches a thermodynamic equilibrium state. These two operations are executed until there is no more improvement.

Microcanonical annealing is known to be similar to simulated annealing. This method is just as effective as its predecessor in terms of results except that it is simpler and faster in terms of computational times [HER 93]. This speed is due to the implementation of the Creutz algorithm. However, it still remains possible to find the same local optimum repeatedly during the search, even if we have escaped from it previously. This is what tabu search tries to take into consideration by making use of the notion of memory.

1.5. Tabu search

Tabu search, introduced by Glover in 1986 [GLO 86a], is based on the principle of human memory. This algorithm makes it possible to memorize previously encountered solutions by storing them in what we call a tabu list.

Tabu search consists of exploring the neighborhood starting from a given position, and selecting the best solution encountered not being included in the tabu list. Consequently, it is possible to keep a degrading solution that therefore allows escaping from local minima and the fact of prohibiting a move to already encountered solutions avoids falling back into these local minima.

Algorithm 1.4: Tabu search

The size of this tabu list thus represents the major parameter of this method. By increasing the size of this list, the exploration mechanism is favored. On the other hand, by decreasing the size of the tabu list, the exploitation mechanism is favored. This list can have a variable size during the search [TAI 91] or be reactive [BAT 94] depending on the solutions obtained; in other words, if the same solution is often obtained, the size of the list is increased or decreased if the current solution is only rarely improved.

1.6. Pattern search algorithms

In this section, we are going to present more recent path-based algorithms, in particular the GRASP method, variable neighborhood search, guided local search and iterated local search.

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.

Algorithm 1.5: The GRASP method

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...