Single-trajectory Search Heuristics on Discrete Multimodal Optimization Problems

Nature-inspired optimization algorithms are defined as a class of algorithms that are inspired by natural phenomena, e. g., evolutionary algorithms and simulated annealing. These methods have gained popularity in practice since they are simple to use and quickly provide good results. Single-trajectory search heuristics are nature-inspired optimization algorithms that iteratively develop a trajectory of solutions to a problem.

They have a straightforward structure which can be seen in many powerful nature-inspired algorithms, such as randomized local search, the (1 + 1)-evolutionary algorithm, and simulated annealing. They typically have some parameters (e. g., mutation rate) to be set and need a selection strategy for developing the sequence of solutions.

Runtime analysis of natureinspired algorithms is a line of research that offers suggestions for parameter tuning in nature-inspired algorithms. Also, several studies have been conducted to determine how to pick the selection mechanisms in such algorithms. For a single-trajectory search heuristic, getting out of a local optimum, where all nearby solutions are of lower quality, is difficult, and its mutation and selection mechanism significantly impact the escaping time.

This thesis discusses three main strategies used in the literature to overcome local optima in singletrajectory search heuristics. (1) Global mutations with a proper probability distribution over solutions can always find a strict improvement with positive probability and eventually leave a local optimum. (2) Stagnation detection approaches, as self-adjusting mechanisms, gradually increase the mutation rate when getting stuck in a local optimum. (3) Accepting inferior solutions in nonelitist algorithms has been used in practice to leave local optima.

In this context, we study two well-known non-elitist algorithms, the Metropolis algorithm and simulated annealing, in specific optimization scenarios.