My group published two new papers recently, here is a brief description of each:
(1) "Cluster-based Framework for Metaheuristic Empirical Similarity"; Jair Pereira Junior, Claus Aranha, Information Sciences (IS)
The first paper encapsulates Jair's Doctoral Thesis, which is (hopefully!) coming to a close next month. It considers the question of how we compare different kinds of meta-heuristics.
If you have followed my work you probably know that there are many, many metaheuristic blackbox optimization algorithms. A lot of effort has been spent in the last decade trying to organize these algorithms, although most of it has been by defining models (components, taxonomies) that researchers can use to classify and compare these algorithms.
Jair tries a different approach, where algorithms are compared based by attributes extracted from their performance on benchmarks. This kind of "empirical" profiling of algorithms is complementary to the "theoretical" analysis: we can learn a lot when the two analysis agree, and when they disagree too!
In his thesis, Jair defines the "empirical profile" of an algorithm as the attributes extracted from a benchmark run. In this paper, he investigates what happens when we use this profile to analyse algorithms with unsupervised clustering. Some findings are quite interesting, such as a visualization of which algorithms are more or less influenced by differences across specific implementations.
(2) "A Constructive Method to Build Many Valid Initial Solutions for the Traveling Tournament Problem"; Guilherme Nakahata, Florian Richoux, Daan van den Berg, Claus Aranha, EvoApps
This paper concerns the Traveling Tournament Problem (TTP), which is a variation of the TSP where several sports teams are traveling to visit each other to play during a tournament. The basic objective is the same - reduce total traveling time - but we have many extra constraints such as the number of times, order, and place that teams play each other. For example, we don't want a team to play too many "away" games in a row.
These extra constraints make the problem much more difficult than traditional TTP, and so in this paper Guilherme and Florian devise a new way to generate multiple solutions that are guaranteed to obey all constraints. The method is rather simple, and quite clever.
This was a fun paper to help write. It came about from Guilherme's part-time job at Florian's lab, which specializes in this sort of problems. I haven't worked in combinatorial optimization in ages, so I was quite rusty, but re-learning this stuff has been nice. Daan joined us to help give us context for the many aspects of the research. Based on his suggestions, last year I read a fascinating book about the combinatory problems associated with sports scheduling.
Based on this paper, we are currently working to figure out how to use all these valid solutions as a way to improve the initialization of optimization algorithms for TTP.