Please use this identifier to cite or link to this item:
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 / 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)
Statement of
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).
RMID: 0030055434
DOI: 10.1145/2908812.2908884
Grant ID:
Published version:
Appears in Collections:Computer Science publications

Files in This Item:
File Description SizeFormat 
RA_hdl_109194.pdfRestricted Access928.43 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.