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

## Symmetries of black box algorithms and combinatorial problem classesAdd 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. ## This talk is included in these lists:- CS 124
- Computer Science Departmental Series
- Computer Science Distinguished Seminars
- Lab Lunch
- Theoretical computer science seminar
Note that ex-directory lists are not shown. |
## Other listsDinner Table Terrorism - Achieving Food Security Nanoscale Physics Seminars Computer Science Distinguished Seminar## Other talks |