Chapter Preview
TopBackground
In the context of this chapter, we will refer to any algorithm which makes use of pseudo-random numbers to perform ‘random’ choices during the exploration of the solution space by the term randomized search method, or simply randomized algorithm. This includes most current metaheurisics and stochastic local-search processes. Thus, since it does not follow a determinist path, even for the same input, a randomized search method can produce different outputs in different runs. Within these type of algorithms we can include, among others, the Genetic and Evolutionary Algorithms (Reeves, 2010), Simulated Annealing (Nikolaev & Jacobson, 2010), Greedy Randomized Adaptive Search Procedure or GRASP (Festa & Resende, 2009a, 2009b), Variable Neighborhood Search (Hansen et al, 2010), Iterated Local Search (Lourenço et al., 2010), Ant Colony Optimization (Dorigo &Stützle, 2010), Probabilistic Tabu Search (Lokketangen & Glover, 1998), or Particle Swarm Optimization (Kennedy & Eberhart, 1995).
Key Terms in this Chapter
MIRHA: Short for Multi-start biased Randomization of classical Heuristics with Adaptive local search; it is a multi-start metaheuristic similar to GRASP but it uses a non-symmetric probability distribution to induce randomness in classical heuristics. Unlike GRASP, it does not use a restricted candidate list.
Fine-Tuning Process: The proper selection of parameters in the methodology to optimize the performance of an algorithm.
HBSS: Short for Heuristic-Biased Stochastic Sampling, it induces a biased randomization process into a heuristic.
Biased Randomization: Randomization obtained throughout a non-symmetric or skewed probability distribution.
Grasp: Short for Greedy randomized adaptive search procedures; it is a multi-start metaheuristic which uses uniform random numbers and a restricted candidate list to explore the solution space. At each iteration, two phases are executed: the construction phase and the local search phase.
Probabilistic Algorithms: Any algorithm which makes use of pseudo-random numbers to perform ‘random’ choices during its execution.
Uniform Randomization: randomization developed throughout a uniform distribution.