Darvariu, Victor-Alexandru;
(2023)
Learning to Optimise Networked Systems.
Doctoral thesis (Ph.D), UCL (University College London).
Preview |
Text
Darvariu_10169635_thesis.pdf Download (32MB) | Preview |
Abstract
Many systems based on relations between connected entities find a natural representation in graphs, which has led to the development of mathematical and statistical tools for understanding their structure and the phenomena that take place over them. There is comparatively little work on the study of optimising the outcome of processes on graphs with respect to a given objective function. Problems of this nature are combinatorial optimisation tasks, which are challenging for systems beyond a trivial size due to the rapid growth of the solution space. Traditional ways of approaching such problems use either heavily tailored, objective-specific approaches or generic metaheuristics. Machine learning and decision-making algorithms have begun to emerge as an alternative data-driven paradigm for navigating the search space, allowing for generalisation between related problems and effective scaling to larger instances than those seen during training. This thesis contributes problem formulations, solution methods, and learning representations for approximately solving several graph combinatorial optimisation problems. We first address constructing a graph for optimising a structural objective such as resilience or efficiency. We propose a deep reinforcement learning approach that uses graph neural networks as a key component for generalisation and a complementary extension of Monte Carlo Tree Search, which is suitable for spatial networks. Next, we study public goods games over networks, discussing an approach for effective imitation learning of policies mapping graph states to node selection actions. Finally, we focus on data-driven routing of flows over graphs, proposing a novel graph neural network architecture for this family of problems. Our evaluation results show significant advantages for the proposed approaches over prior methods, representing a contribution to the broader area of machine learning for combinatorial optimisation. The research discussed in this thesis may find meaningful applications in domains as diverse as structural engineering, urban planning, operations research, and computer networking.
| Type: | Thesis (Doctoral) |
|---|---|
| Qualification: | Ph.D |
| Title: | Learning to Optimise Networked Systems |
| Open access status: | An open access version is available from UCL Discovery |
| Language: | English |
| Additional information: | Copyright © The Author 2023. Original content in this thesis is licensed under the terms of the Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0) Licence (https://creativecommons.org/licenses/by-nc/4.0/). Any third-party copyright material present remains the property of its respective owner(s) and is licensed under its existing terms. Access may initially be restricted at the author’s request. |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery-pp.ucl.ac.uk/id/eprint/10169635 |
Archive Staff Only
 |
View Item |
