Abstract
This paper assumes a search space of fixed-length strings, where the size of the alphabet can vary from position to position. Structural crossover is mask-based crossover, and thus includes n-point and uniform crossover. Structural mutation is mutation that commutes with a group operation on the search space. This paper shows that structural crossover and mutation project naturally onto competing families of schemata. In other words, the effect of crossover and mutation on a set of string positions can be specified by considering only what happens at those positions and ignoring other positions. However, it is not possible to do this for proportional selection except when fitness is constant on each schema of the family. One can write down an equation which includes selection which generalizes the Holland Schema theorem. However, like the Schema theorem, this equation cannot be applied over multiple time steps without keeping track of the frequency of every string in the search space.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization & Machine Learning. Addison Wesley, Reading, MA.
Holland, J. (1975). Adapdation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, Michigan.
Koehler, Bhattacharyya, and Vose (1997). General cardinality genetic algorithms. Evolutionary Computation, 5(4):439–459.
Lang, S. (1993). Algebra. Addison-Wesley, Reading, MA, third edition.
Rowe, J.E., Vose, M.D., and Wright, A.H. (2002). Group properties of crossover and mutation. Evolutionary Computation, 10(2):151–184.
Stephens, C. and Waelbroeck, H. (1999). Schemata evolution and building blocks. Evolutionary Computation, 7(2).
Vose, M.D. (1999). The Simple Genetic Algorithm: Foundations and Theory. MIT Press, Cambridge, MA.
Vose, M.D. and Wright, A.H. (2001). Form invariance and implicit parallelism. Evolutionary Computation, 9(3):355–370.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wright, A.H., Vose, M.D., Rowe, J.E. (2003). Implicit Parallelism. In: Cantú-Paz, E., et al. Genetic and Evolutionary Computation — GECCO 2003. GECCO 2003. Lecture Notes in Computer Science, vol 2724. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45110-2_22
Download citation
DOI: https://doi.org/10.1007/3-540-45110-2_22
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40603-7
Online ISBN: 978-3-540-45110-5
eBook Packages: Springer Book Archive