On the use of different types of knowledge in metaheuristics based on constructing solutions |
| |
Authors: | Monaldo Mastrolilli Christian Blum |
| |
Affiliation: | 1. IDSIA, Galleria 2, 6928 Manno, Switzerland;2. ALBCOM, LSI, Universitat Politècnica de Catalunya, Barcelona, Spain;1. Department of Electronics and Communication Engineering, NIT Durgapur, West Bengal, India;2. Department of Electrical Engineering, NIT Durgapur, West Bengal, India;3. Department of Electrical Engineering, ISM, Dhanbad, India;1. Department of Electronics and Communication Engg., NIT Durgapur, India;2. Department of Electrical Engg., NIT Durgapur, West Bengal, India;1. INESC-ID – R Alves Redol 9, 1000-029 Lisboa, Portugal;2. IST-UL – Av Rovisco Pais, 1049-001 Lisboa, Portugal;3. LAETA, IDMEC, Instituto Superior Técnico, Universidade de Lisboa – Av. Rovisco Pais, 1049-001 Lisboa, Portugal;1. Federal University of Rio de Janeiro, EPOLI, COPPE, CP 68504, CEP 21945-970, Rio de Janeiro, Brazil;2. CEFET, Nova Iguaçu, and Federal University of Rio de Janeiro, COPPE, Rio de Janeiro, Brazil |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|