Author: Sergio González Martín
Programme: Doctoral Programme on the Information and Knowledge Society
Language: English
Supervisors: Dr Ángel Alejandro Juan Pérez and Dr Daniel Riera Terrén
Faculty / Institute: Internet Interdisciplinary Institute (IN3)
Subjects: Computer Science, General Theory of Combined Analysis, Graph Theory,
Computation Science and Artificial Intelligence
Key words: Biased randomized heuristics, Optimization, Real applications, Metaheuristics, Simulation
Area of knowledge: Computation Science and Artificial Intelligence

+ Link

Summary

Most metaheuristics contain a randomness component, which is usually based on uniform randomization – ie the use of the uniform probability distribution to make random choices. However, the ulti-start biased randomization of classical heuristics with adaptive local search framework proposes the use of biased (non-uniform) randomization for the design of alternative metaheuristics – ie the use of skewed probability distributions such as the geometric or triangular ones. In some scenarios, this non-biased randomization has shown to provide faster convergence to near-optimal solutions. The MIRHA framework also includes a local search step for improving the incumbent solutions generated during the multi-start process. It also allows the addition of tailored local search components, like cache (memory) or splitting (divide-and-conquer) techniques that allow the generation of competitive (near-optimal) solutions.

The algorithms designed using the MIRHA framework allow the acquisition of "high-quality" solutions to realistic problems in reasonable computing times. Moreover, they tend to use a reduced number of parameters, which makes them simple to implement and configure in most practical applications. This framework has successfully been applied in many routing and scheduling problems. One of the main goals of this thesis is to develop new algorithms, based in the aforementioned framework, for solving some combinatorial optimization problems that can be of interest in the telecommunication industry.