Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/109194
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | Fast building block assembly by majority vote crossover |
Author: | Friedrich, T. Kötzing, T. Krejca, M. Nallaperuma, S. Neumann, F. Schirneck, M. |
Citation: | Proceedings of the 2016 Genetic and Evolutionary Computation Conference, 2016 / Friedrich, T., Neumann, F., Sutton, A.M. (ed./s), pp.661-668 |
Publisher: | Association for Computing Machinery |
Issue Date: | 2016 |
ISBN: | 9781450342063 |
Conference Name: | 2016 Genetic and Evolutionary Computation Conference (GECCO 2016) (20 Jul 2016 - 24 Jul 2016 : Denver, Colorado, USA) |
Editor: | Friedrich, T. Neumann, F. Sutton, A.M. |
Statement of Responsibility: | Tobias Friedrich, Timo Kötzing, Martin S. Krejca, Samadhi Nallaperuma, Frank Neumann, Martin Schirneck |
Abstract: | Different works have shown how crossover can help with building block assembly. Typically, crossover might get lucky to select good building blocks from each parent, but these lucky choices are usually rare. In this work we consider a crossover operator which works on three parent individuals. In each component, the offspring inherits the value present in the majority of the parents; thus, we call this crossover operator majority vote. We show that, if good components are sufficiently prevalent in the individuals, majority vote creates an optimal individual with high probability. Furthermore, we show that this process can be amplified: as long as components are good independently and with probability at least 1/2+delta, we require only O(log 1/delta + log log n) successive stages of majority vote to create an optimal individual with high probability! We show how this applies in two scenarios. The first scenario is the Jump test function. With sufficient diversity, we get an optimization time of O(n log n) even for jump sizes as large as O(n(1/2-epsilon)). Our second scenario is a family of vertex cover instances. Majority vote optimizes this family efficiently, while local searches fail and only highly specialized two-parent crossovers are successful. |
Keywords: | Run time analysis, evolutionary algorithm, island model, majority vote crossover, Jump, vertex cover |
Rights: | © 2016 Copyright held by the owner/author(s). Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s). |
DOI: | 10.1145/2908812.2908884 |
Grant ID: | http://purl.org/au-research/grants/arc/DP140103400 |
Published version: | http://dx.doi.org/10.1145/2908812.2908884 |
Appears in Collections: | Aurora harvest 3 Computer Science publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
RA_hdl_109194.pdf Restricted Access | Restricted Access | 928.43 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.