University of Birmingham > Talks@bham > Artificial Intelligence and Natural Computation seminars > Optimizing Monotone Functions with Standard Bit Mutations

## Optimizing Monotone Functions with Standard Bit MutationsAdd to your list(s) Download to your calendar using vCal - Dr. Thomas Jansen, Department of Computer Science, University College Cork
- Monday 18 October 2010, 16:00-17:00
- UG40, School of Computer Science.
If you have a question about this talk, please contact Leandro Minku. Randomized local search (RLS) and the most simple evolutionary algorithm, the (1+1) EA, differ only in the variation operators they employ. When optimizing pseudo-Boolean functions RLS flips exactly one bit that is selected uniformly at random. The (1+1) EA decides for each bit independently if the bit is flipped, each time with a fixed mutation probability p(n) where n is the length of the bit string. In most cases these so-called standard bit mutations are used with a mutation probability of p(n)=c/n where c is some positive constant, often c=1. For linear functions it is known that RLS and the (1+1) EA both find a global optimum on average in O(n log n) steps. For the (1+1) EA this holds regardless of the constant c in the mutation probability. For unimodal functions it is known that RLS and the (1+1) EA both need exponentially long to find a global optimum. For the (1+1) EA this also holds regardless of the constant c. Strictly monotone functions are a proper subset of unimodal functions and a proper superset of linear functions. RLS needs on average time O(n log n) to optimize an arbitrary strictly monotone function. We investigate the performance of the (1+1) EA on such functions and exhibit a surprising dependence on c. For c This talk is part of the Artificial Intelligence and Natural Computation seminars series. ## This talk is included in these lists:- Artificial Intelligence and Natural Computation seminars
- Computer Science Departmental Series
- Computer Science Distinguished Seminars
- UG40, School of Computer Science
Note that ex-directory lists are not shown. |
## Other listsBiosciences seminars Birmingham and Warwick Algebra Seminar Theoretical Physics Journal Club## Other talksTBA TBA LovĂˇsz' Theorem and Comonads in Finite Model Theory Generalised hydrodynamics and universalities of transport in integrable (and non-integrable) spin chains TBA TBA |