We propose a new way to self-adjust the mutation rate in population-based evolutionary algorithms. Roughly speaking, it consists of creating half the offspring with a mutation rate that is twice the current mutation rate and the other half with half the current rate. The mutation rate is then updated to the rate used in that subpopulation which contains the best offspring. We analyze how the (1 + λ) evolutionary algorithm with this self-adjusting mutation rate optimizes the OneMax test function. We prove that this dynamic version of the (1 + λ) EA finds the optimum in an expected optimization time (number of fitness evaluations) of O(nλ log λ + n log n). This time is asymptotically smaller than the optimization time of the classic (1 + λ) EA. Previous work shows that this performance is best-possible among all λ-parallel mutation-based unbiased black-box algorithms. This result shows that the new way of adjusting the mutation rate can find optimal dynamic parameter values on the fly. Since our adjustment mechanism is simpler than the ones previously used for adjusting the mutation rate and does not have parameters itself we are optimistic that it will find other applications.
Aside from the optimization behavior on , not too much is known for the , or is at least not made explicit (it is easy to see that waiting times for an improvement which are larger than @math reduce by a factor of @math compared to one-individual offspring populations). Results made explicit are the @math expected runtime (number of generations) on @cite_36 , the worst-case @math expected runtime on linear functions @cite_7 , and the @math runtime estimate for minimum spanning trees valid for @math @cite_43 , where @math denotes the number of vertices of the input graph, @math the number of edges, and @math the maximum of the integral edge weights.
@cite_36 @cite_43 @cite_7
1970101133 2153401898 2015766439
Evolutionary algorithms (EAs) generally come with a large number of parameters that have to be set before the algorithm can be used. Finding appropriate settings is a difficult task. The influence of these parameters on the efficiency of the search performed by an evolutionary algorithm can be very high. But there is still a lack of theoretically justified guidelines to help the practitioner find good values for these parameters. One such parameter is the offspring population size. Using a simplified but still realistic evolutionary algorithm, a thorough analysis of the effects of the offspring population size is presented. The result is a much better understanding of the role of offspring population size in an EA and suggests a simple way to dynamically adapt this parameter when necessary. Randomized search heuristics, among them randomized local search and evolutionary algorithms, are applied to problems whose structure is not well understood, as well as to problems in combinatorial optimization. The analysis of these randomized search heuristics has been started for some well-known problems, and this approach is followed here for the minimum spanning tree problem. After motivating this line of research, it is shown that randomized search heuristics find minimum spanning trees in expected polynomial time without employing the global technique of greedy algorithms. Abstract We analyze how the ( 1 + λ ) evolutionary algorithm (EA) optimizes linear pseudo-Boolean functions. We prove that it finds the optimum of any linear function within an expected number of O ( 1 λ n log ⁡ n + n ) iterations. We also show that this bound is sharp for some linear functions, e.g., the binary value function. Since previous works shows an asymptotically smaller runtime for the special case of OneMax , it follows that for the ( 1 + λ ) EA different linear functions may have run-times of different asymptotic order. The proof of our upper bound heavily relies on a number of classic and recent drift analysis methods. In particular, we show how to analyze a process displaying different types of drifts in different phases. Our work corrects a wrongfully claimed better asymptotic runtime in an earlier work [13] . We also use our methods to analyze the runtime of the ( 1 + λ ) EA on the OneMax test function and obtain a new upper bound of O ( n log ⁡ log ⁡ λ log ⁡ λ ) for the case that λ is larger than O ( log ⁡ n log ⁡ log ⁡ n log ⁡ log ⁡ log ⁡ n ) ; this is the cut-off point where a linear speed-up ceases to exist. While our results are mostly spurred from a theory-driven interest, they also show that choosing the right size of the offspring population can be crucial. For both the binary value and the OneMax test function we observe that once a linear speed-up ceases to exist, in fact, the speed-up from a larger λ reduces to sub-logarithmic (still at the price of a linear increase of the cost of each generation).