Projects per year
Abstract
Natureinspired 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. Singletrajectory search heuristics are natureinspired optimization algorithms that iteratively develop a trajectory of solutions to a problem. They have a straightforward structure which can be seen in many powerful natureinspired 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 natureinspired algorithms. Also, several studies have been conducted to determine how to pick the selection mechanisms in such algorithms. For a singletrajectory 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 selfadjusting 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 wellknown nonelitist algorithms, the Metropolis algorithm and simulated annealing, in specific optimization scenarios.
tuning in natureinspired algorithms. Also, several studies have been conducted to determine how to pick the selection mechanisms in such algorithms. For a singletrajectory 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 selfadjusting 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 wellknown nonelitist algorithms, the Metropolis algorithm and simulated annealing, in specific optimization scenarios.
Original language  English 

Publisher  Technical University of Denmark 

Number of pages  244 
Publication status  Published  2022 
Fingerprint
Dive into the research topics of 'Singletrajectory Search Heuristics on Discrete Multimodal Optimization Problems'. Together they form a unique fingerprint.Projects
 1 Finished

Efficient and Selftuning Natureinspired Algorithms
Rajabi, A., Oliveto, P. S., Bille, P., Lehre, P. K., Witt, C. & Fischer, P.
01/06/2019 → 30/09/2022
Project: PhD