Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/133269
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | Escaping large deceptive basins of attraction with heavy-tailed mutation operators |
Author: | Friedrich, T. Quinzan, F. Wagner, M. |
Citation: | Proceedings of the 2018 Genetic and Evolutionary Computation Conference, as published in ACM Digital Library, 2018 / Aguirre, H. (ed./s), pp.293-300 |
Publisher: | ACM |
Publisher Place: | online |
Issue Date: | 2018 |
ISBN: | 9781450356183 |
Conference Name: | 2018 Genetic and Evolutionary Computation Conference (15 Jul 2018 - 19 Jul 2018 : Kyoto) |
Editor: | Aguirre, H. |
Statement of Responsibility: | Tobias Friedrich, Francesco Quinzan, Markus Wagner |
Abstract: | In many evolutionary algorithms (EAs), a parameter that needs to be tuned is that of the mutation rate, which determines the probability for each decision variable to be mutated. Typically, this rate is set to 1/n for the duration of the optimization, where n is the number of decision variables. This setting has the appeal that the expected number of mutated variables per iteration is one. In a recent theoretical study, it was proposed to sample the number of mutated variables from a power-law distribution. This results in a significantly higher probability on larger numbers of mutations, so that escaping local optima becomes more probable. In this paper, we propose another class of non-uniform mutation rates. We study the benefits of this operator in terms of average case black-box complexity analysis and experimental comparison. We consider both pseudo-Boolean artificial landscapes and combinatorial problems (the Minimum Vertex Cover and the Maximum Cut). We observe that our non-uniform mutation rates significantly outperform the standard choices, when dealing with landscapes that exhibit large deceptive basins of attraction. |
Keywords: | Heavy-tailed Mutation; combinatorial optimization; single-objective optimization |
Rights: | © 2018 Copyright held by the owner/author(s). Publication rights licensed to the Association for Computing Machinery. |
DOI: | 10.1145/3205455.3205515 |
Grant ID: | http://purl.org/au-research/grants/arc/DE160100850 |
Published version: | http://dx.doi.org/10.1145/3205455.3205515 |
Appears in Collections: | Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.