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