The Library
Mutation rate matters even when optimizing monotonic functions
Tools
Doerr, Benjamin, Jansen, Thomas, Sudholt, Dirk, Winzen, Carola and Zarges, Christine (2013) Mutation rate matters even when optimizing monotonic functions. Evolutionary Computation, Volume 21 (Number 1). pp. 1-27. doi:10.1162/EVCO_a_00055 ISSN 1063-6560.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1162/EVCO_a_00055
Abstract
Extending previous analyses on function classes like linear functions, we analyze how the simple (1+1) evolutionary algorithm optimizes pseudo-Boolean functions that are strictly monotonic. These functions have the property that whenever only 0-bits are changed to 1, then the objective value strictly increases. Contrary to what one would expect, not all of these functions are easy to optimize. The choice of the constant c in the mutation probability p(n)=c/n can make a decisive difference.
We show that if c<1, then the (1+1) EA finds the optimum of every such function in iterations. For c=1, we can still prove an upper bound of O(n3/2). However, for , we present a strictly monotonic function such that the (1+1) EA with overwhelming probability needs iterations to find the optimum. This is the first time that we observe that a constant factor change of the mutation probability changes the runtime by more than a constant factor.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | Evolutionary Computation | ||||
Publisher: | M I T Press | ||||
ISSN: | 1063-6560 | ||||
Official Date: | 2013 | ||||
Dates: |
|
||||
Volume: | Volume 21 | ||||
Number: | Number 1 | ||||
Page Range: | pp. 1-27 | ||||
DOI: | 10.1162/EVCO_a_00055 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |