University of Birmingham > Talks@bham > Lab Lunch > Symmetries of black box algorithms and combinatorial problem classes

Symmetries of black box algorithms and combinatorial problem classes

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Dan Ghica.

The “No Free Lunch” theorem shows that any two black box algorithms have equal performance averaged over a set of functions if and only if that set is closed under permutations (c.u.p.). However, traditional combinatorial problem classes are not c.u.p. If we restrict our attention to some specific algorithms (rather than ALL black box algorithms), then they may have equal average performance over sets of functions which are not c.u.p. (the so-called focussed NFL theorems). This raises the question of when two algorithms may have the same average performance over a traditional combinatorial problem class. By using a duality theorem between algorithms and problem instances, this question reduces to asking when permutations of the search space leave a problem class invariant. For certain types of problem class called “discrete linear subset” problems (which includes MAXSAT , TSP and others) we can characterise these permutations as automorphisms of a corresponding hypergraph. Previous results can then be applied to describe precisely those operators (mutation and crossover) which are invariant with respect to these automorphisms and thereby give rise to algorithms which are robust (in a precisely defined sense) for the corresponding problem class.

This talk is part of the Lab Lunch series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on talks.cam from the University of Cambridge.