On the use of different types of knowledge in metaheuristics based on constructing solutions

Many metaheuristics are either based on neighborhood search or the construction of solutions. Examples for the latter ones include ant colony optimization and greedy randomized adaptive search procedures. These techniques generally construct solutions probabilistically by sampling a probability distribution over the search space. Solution constructions are generally independent from each other. Recent algorithmic variants include two important features that are inspired by deterministic branch and bound derivatives such as beam search: the use of bounds for evaluating partial solutions, and the parallel and non-independent construction of solutions. In this paper we give a theoretical reason of why these algorithms generally work very well in practice. Second, we confirm our theoretical findings by means of practical examples. After the application to artificial problems, we present experimental results concerning the well-known open shop scheduling problem.