BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.bham.ac.uk//v3//EN
BEGIN:VEVENT
CATEGORIES:Artificial Intelligence and Natural Computation se
minars
SUMMARY:Optimizing Monotone Functions with Standard Bit Mu
tations - Dr. Thomas Jansen\, Department of Comput
er Science\, University College Cork
DTSTART:20101018T150000Z
DTEND:20101018T160000Z
UID:TALK469AT
URL:/talk/index/469
DESCRIPTION:Randomized local search (RLS) and the most simple
evolutionary\nalgorithm\, the (1+1) EA\, differ on
ly in the variation operators they\nemploy. When o
ptimizing pseudo-Boolean functions RLS flips exact
ly one\nbit that is selected uniformly at random.
The (1+1) EA decides for each\nbit independently i
f the bit is flipped\, each time with a fixed muta
tion\nprobability p(n) where n is the length of th
e bit string. In most cases\nthese so-called stand
ard bit mutations are used with a mutation\nprobab
ility of p(n)=c/n where c is some positive constan
t\, often c=1.\nFor linear functions it is known t
hat RLS and the (1+1) EA both find a\nglobal optim
um on average in O(n log n) steps. For the (1+1) E
A this\nholds regardless of the constant c in the
mutation probability. For\nunimodal functions it i
s known that RLS and the (1+1) EA both need\nexpon
entially long to find a global optimum. For the (1
+1) EA this also\nholds regardless of the constant
c. Strictly monotone functions are a\nproper subs
et of unimodal functions and a proper superset of
linear\nfunctions. RLS needs on average time O(n l
og n) to optimize an arbitrary\nstrictly monotone
function. We investigate the performance of the (1
+1)\nEA on such functions and exhibit a surprising
dependence on c. For c<1\nthe expected optimizati
on time is also O(n log n) but for sufficiently\nl
arge constants c it becomes exponential.
LOCATION:UG40\, School of Computer Science
CONTACT:Leandro Minku
END:VEVENT
END:VCALENDAR