Back to search

University of Southampton

Deep optimisation: learning and searching in deep representations of combinatorial optimisation problems

Abstract

dc:description.abstract

Evolutionary algorithms are a class of optimisation techniques used to solve problems by emulating evolutionary processes (variation and selection) to search the solution space. In this thesis, we focus on the evolutionary process of Evolutionary Transitions in Individuality (ETI). In this case, evolutionary processes are scaled up via a multi-scale process whereby individuality (and hence variation and selection) is continually revised by forming associations between formerly independent entities. This thesis develops a novel Model-Building Optimisation Algorithm (MBOA) called Deep Optimisation (DO) that exploits deep learning methods to enable multi-scale optimisation. DO uses an autoencoder model to induce a multi-level representation of solutions. Variation and selection are then performed within the induced representations, allowing search to continue in a new and reorganised space. By using a class of configurable problems, we find and understand more precisely the distinct problem characteristics that DO can solve that other MBOAs cannot. Specifically, we observe a polynomial vs exponential scaling distinction where DO is the only algorithm to show polynomial scaling for all problems. We also demonstrate that some problem characteristics need a deep network in DO. Further, for the first time, we show that overlap differentiates the performance between current MBOAs that are considered state-of-the-art. DO is then applied to different optimisation problem domains to demonstrate its potential for exploiting unknown problem structure and overcoming infeasible solution spaces. Here, DO shows impressive performance and does so without using a domain-specific operator. This thesis provides a connection between deep learning models and MBOAs, showing results that outperform existing algorithms can be achieved by utilising the tools available in deep learning. This suggests numerous avenues for further investigation, transferring deep learning methods into the domain of MBOAs.

Degree

thesis:*
Name dc:type.qualificationname
Ph.D.
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of Southampton
Year dc:date.issued
2022

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Caldwell, Jamie, Robert
Advisor dc:contributor.advisor
  • Watson, Richard
ORCID person:identifier.orcid

Rights

Language dc:language
English, eng

Chain of custody

source
Harvested from
University of Southampton
Base URL
eprints.soton.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Caldwell, Jamie, Robert. Deep optimisation: learning and searching in deep representations of combinatorial optimisation problems. doctoral thesis, University of Southampton, 2022.