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

Optimizing Monotone Functions with Standard Bit Mutations

Add 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.

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 from the University of Cambridge.