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 listsCombinatorics and Probability Seminar Electromagnetic Communications and Sensing Research Seminar Series Computer Science Distinguished Seminar## Other talksWeak universalities for some singular stochastic PDEs Privileged side-channel attacks for enclave adversaries The Griess Algebra and the Monster Subgroups of the Monster Role of Mechanics and Geometry in Cellular Information Processing Combining Organic Synthesis, Isotopes and Synthetic Biology in Natural Products Research |