2 May 2014, Theoretical Computer Science Seminar, Rachel Morgan

Abstract

Measuring the similarity between black-box optimization problems is important, but poses numerous practical challenges. This talk proposes using Information Distance - a universal distance - to measure the (dis)similarity between black-box optimization problem instances. In practice, Information Distance can be approximated by Normalised Compression Distance, which utilises standard compression algorithms to measure the similarity between arbitrary binary files. The seminar will discuss a methodology for sampling and representing the problems (as binaries), as well as compression algorithms suitable for the proposed representation. In addition, preliminary results for Traveling Salesman Problems, Circle-Packing problems and problems from the Black-Box Optimization Benchmarking (BBOB) set will be presented.

For more information, please contact Christian Schaffner (c.schaffner at uva.nl).