I have recently finished the Master of Engineering in Computer Science program in Imperial College London with First Class honours. The culmination of the degree was the masters thesis, the goal of this was to show what four years of hard study taught me and my research abilities.
I picked my own project, and decided to work on solving combinatorial optimization problems, such as the Travelling Salesman Problem, or N-Queens, using continuous-time dynamical systems instead of normal imperative algorithms.
Abstract:
Optimisation problems, such as finding solutions to the boolean satisfiability problem (k-SAT), or finding valid itineraries in the travelling salesman problem are a very well known and studied class of problems with existing algorithmic solutions. In this report, we look at a different approach to computational opti- misation by using dynamical systems with attractors corresponding to solutions of the optimisation problem - such a representation does not produce solutions faster, but it gives us insight into how combinatorial optimisation can be feasibly done in a neural medium such as the brain. The report concentrates on solving a popular NP-complete problem, boolean k-SAT, by using dynamical systems. We study two previously developed methods, and contribute another alterna- tive system that has the benefit of using bounded variables, and of solving some problems that a different bounded system was not able to solve. We evalu- ate dynamical system SAT solving by developing a SAT encoding for the logic game Bridges and by solving the encodings for different difficulties of Bridges. We come to an interesting conclusion regarding escape rates of the dynami- cal systems and the published difficulty of the game - while “Easy” problems are indeed easier to solve by the dynamical system approach, a “Hard” puzzle is easier to solve than a “Normal” puzzle due to increased constraint density for “Hard” puzzles. In this way, we show that a higher difficulty optimisation problem for humans can actually be easier than a corresponding easier problem when encoded as SAT.
For the interested reader, the final report is available here