![]() |
![]() |
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
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:
Note that ex-directory lists are not shown. |
Other listsTheoretical Physics Seminars SERENE Seminars Algebra Reading Group on Sporadic GroupsOther talksWave turbulence in the Schrödinger-Helmholtz equation Life : it’s out there, but what and why ? TBA Counting cycles in planar graphs Control variates for computing transport coefficients The tragic destiny of Mileva Marić Einstein |