Reference : Learning Optimisation Algorithms over Graphs
Dissertations and theses : Doctoral thesis
Engineering, computing & technology : Computer science
Computational Sciences
Learning Optimisation Algorithms over Graphs
Duflo, Gabriel Valentin mailto [University of Luxembourg > Faculty of Science, Technology and Medecine (FSTM) > >]
University of Luxembourg, ​​Luxembourg
Docteur en Informatique
xii, 96 + 7
Danoy, Grégoire mailto
Bouvry, Pascal mailto
Talbi, El-Ghazali mailto
Bouffanais, Roland mailto
Nowé, Ann mailto
[en] hyper-heuristic ; reinforcement learning ; graph
[en] The paradigm of learning to optimise relies on the following principle: instead of designing an algorithm to solve a problem, we design an algorithm which will automate the design of such a solver. The initial idea was to alleviate the limitations stated by the No Free Lunch Theorem by producing an algorithm which efficiency is less dependent upon known instances of the problem to tackle. Hyper-heuristics constitute the main learning-to-optimise techniques. These rely on a high-level algorithm performing a search process into a space of low-level heuristics to tackle a given problem. Because the latter search space is problem-dependent, the vast majority of hyper-heuristics are designed to tackle a specific problem. Due to this lack of generality, existing works fully redesign hyper-heuristics when tackling a new problem, despite the fact that they may share a similar structure.
In this dissertation, we tackle this challenge by proposing a generic way for learning to optimise any problem. To this end, this thesis introduces three main contributions: (i) an analysis of the formal functioning of learning-to-optimise techniques; (ii) a model of generic hyper-heuristic, named Algorithm Learner for Graph Optimisation problems (ALGO), constituting the central point of this work; (iii) a real-world use case where we use our generic hyper-heuristic to automate the design of behaviours within a swarm of drones.
In the first part, we provide a formalism for optimisation and learning concepts, which we use to describe the large body of knowledge that combines two layers of optimisation and/or learning. We then put an emphasis on approaches using learning to improve an optimisation process, i.e., aiming at learning to optimise. In the second part, we present ALGO, our model of generic hyper-heuristic. We explain how we abstract from a given problem with a graph structure so that it can be used to tackle any optimisation problem. We also detail the steps to follow in order to use ALGO to tackle a given problem. We finally present the modularity of ALGO with inner components that a user can implement. The second part ends with a validation of our model, i.e., using ALGO to tackle a classical optimisation problem. In the third part, we use ALGO to tackle the problem of area surveillance with a swarm of drones. We demonstrate that ALGO constitutes a novel and efficient way
to automate the design of such a distributed and multi-objective problem.
Interdisciplinary Centre for Security, Reliability and Trust (SnT) > PCOG - Parallel Computing & Optimization Group

File(s) associated to this reference

Fulltext file(s):

Open access
duflo_phd_thesis.pdfAuthor postprint3.08 MBView/Open

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.