Optimizing Monotone Functions with Standard Bit Mutations

Add 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
• computer sience

Note that ex-directory lists are not shown.