Portal de Periódicos da CAPES

Heavy-Tailed Mutation Operators in Single-Objective Combinatorial Optimization

2018; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-319-99253-2_11

1611-3349

Tobias Friedrich, Andreas Göbel, Francesco Quinzan, Markus Wagner,

Evolutionary Algorithms and Applications

A core feature of evolutionary algorithms is their mutation operator. Recently, much attention has been devoted to the study of mutation operators with dynamic and non-uniform mutation rates. Following up on this line of work, we propose a new mutation operator and analyze its performance on the (1+1) Evolutionary Algorithm (EA). Our analyses show that this mutation operator competes with pre-existing ones, when used by the (1+1) EA on classes of problems for which results on the other mutation operators are available. We present a "jump" function for which the performance of the (1+1) EA using any static uniform mutation and any restart strategy can be worse than the performance of the (1+1) EA using our mutation operator with no restarts. We show that the (1+1) EA using our mutation operator finds a (1/3)-approximation ratio on any non-negative submodular function in polynomial time. This performance matches that of combinatorial local search algorithms specifically designed to solve this problem. Finally, we evaluate experimentally the performance of the (1+1) EA using our operator, on real-world graphs of different origins with up to $$\sim $$ 37 000 vertices and $$\sim $$ 1.6 million edges. In comparison with uniform mutation and a recently proposed dynamic scheme our operator comes out on top on these instances.