SEABIS Meeting on Real-World Optimisation

The ROLL team was delighted to welcome Dr Bill Langdon from UCL to Edinburgh Napier in September.  Bill spoke to around 25 researchers from across Scotland at a meeting of the SEABIS group, on the theme of Real-World Optimisation. (SEABIS is a sub-group of the SICSA theme on Complex Systems Engineering).

Bill is currently working on two EPSRC funded projects, looking at aspects of Search-Based Software Engineering. He has been using Genetic Programming to show that a machine can be used to optimise human-written code, trading off functional and non-functional properties. Using a 50,000 C++ program called Bowtie2 (a modern DNA look up tool that aligns sequences of DNA against reference data) as an example, Bill showed the GP could be used to evolve 39 patches to the existing code, that when applied produced a 70-fold speed up in performance, in which 98% of the results were better or identical to an existing system.

This is a really nice example of applying optimisation techniques to a common real-world task that on the face of it, seems very difficult for an optimisation technique, given the difficulty of maintaining working code after applying random mutations. Interestingly,  Bill showed that only 74% of evolved programs compile and  a further 6% of these fail at run time … yet despite this, the technique produces excellent results as described above. There is definitely a lesson in there for others wishing to tackle very difficult problems with evolutionary methods who might have been put off..

Some of the speed-up in the code was attributed to simple things such as evolution removing redundant code or simplifying loops. Perhaps there is some mileage in tackling other very constrained optimisation problems in the same manner. Take vehicle routing that has many idiosyncratic constraints. Perhaps an evolutionary method might simplify or ignore constraints,  thus making it easier for a(nother?) problem solver to tackle the problem… more on this in the future..

The meeting concluded with a round table discussion the whether there is a perceived gap between the academic research undertaken in universities and the types of problems people in real businesses worry about. Many people contributed to the discussion and a number of interesting points were raised:

  • Most real-world problems have far more constraints than those included in academic benchmarks – Vehicle Routing is a good example of this, where even the most constrained benchmarks don’t come close to the number of constraints in a real-world problem
  • When working with outside clients, its important to listen carefully to what they actually want and separate this from the research you want to do – the client doesn’t necessarily need a novel technique or complex problem solving…..
  • A possible method of bringing the two communities closer together would be to create a website where people could post problems they would like solving, and inviting the  academic community to tackle them.
  • Competitions have proved to be a useful method of generating interest from a wider audience  –  using real problems in a competition format might go some way towards building links between the two communities.