Data for "Optimal Mutation Rates for the (1+λ) EA on OneMax"

This dataset contains optimal mutation rates for the few variations of the (1+λ) evolutionary algorithm on the OneMax problem. The OneMax problem is a famous benchmark problem which is defined on bit strings, with the maximized function being the number of bits set to 1. The optimal mutation rates depend on the Hamming distance to the optimum (or, put simple, on the current fitness). We study three flavours of the algorithm:

the algorithm with the standard bit mutation - where each bit is flipped independently of others with the probability p, which is the sought mutation rate - nicknamed "sbm" in the file names;

the algorithm with the so-called "shift" bit mutation - which is similar to the one above, except that when none bits were flipped, one randomly chosen bit is forcefully flipped - nicknamed "shf" in the file names;

the algorithm which always flips k bits, which is the mutation rate for this algorithm - nicknamed "rls" in the file names, because it is a generalization of the famous randomized local search (RLS) that always flips one randomly chosen bit.

All these variations have one parent individual, produce λ offspring on each iteration and choose the best of both the parent and the offspring to be the parent in the next iteration (hence the (1+λ) in the notation). As a result, λ is often called the popiulation size. We study the values of λ to be powers of two ranging from 20=1 to 218=262144, and the problem sizes n=1000, 2000, 5000.

For all the variations and all population sizes, we compute the optimal mutation rates (in the corresponding sense) as functions of the distance to the optimum, where "optimal" mean those which minimize the expected running time. For the "rls" variation we also compute the "drift-maximizing" mutation rates, which maximize the expected fitness increase (and which is, in fact, different from minimizing the expected running time).

The files in the dataset are as follows:

data-expectations-.csv: the summary of the expected running times of all these algorithms for all population sizes, where is the value of the problem size.

data-optimal--.csv: the mutation rates optimal for the given algorithm and the given problem size for all population sizes. Note that for "rls" the mutation rate is an integer from 1 to n, whereas for other algorithms the mutation rate is the probability, so a floating-point number from [0;1].

data-drift-optimal-rls-.csv: same thing from drift-optimal mutation rates.

img-optimal---.png: the pictures that display how good each mutation rate is for each distance to the optimum. Please check the exact semantics in the paper, but the overall idea is that yellow is better.