Mutation by imitation in boolean evolution strategies

International audienceAdaptive heuristics have been developed in the Evolution Strategy (ES) frame regarding the mutation of real-valued variables. But these heuristics poorly extend to discrete variables: when the rate or variance of mutation gets too small, mutation has no e ect any more. To overcome this problem, we propose two mutation operators, that use the worst individuals of the current population as beacons indicating the limits of the current promising region: Mutation by di erentiation drives individuals away from the beaconindividuals. Mutation by imitation inversely assumes that beacon-individuals still contain relevant informations, and aims at moving the individual at hand nearer to the beacons. Mutation by imitation produces o spring that share the features of several \parents"; but in contrast with classical crossover, it allows one to control the distance between the o spring and the main parent, by xing the number of bits to mutate. Mutation by imitation thus permits a tunable exchange of informations among individuals. Both operators have been implemented in a boolean (+) ES framework, and experimented on four problems: the Royal Road problem, a GA-deceptive problem, the combinatorial multiple knapsack optimization problem and the Long Path problem. Comparative validation is presented and discussed