Transit sets of two-point crossover. (English) Zbl 1454.05078
Summary: Genetic Algorithms typically invoke crossover operators to produce offsprings that are a “mixture” of two parents \(x\) and \(y\). On strings, \(k\)-point crossover breaks parental genotypes at at most \(k\) corresponding positions and concatenates alternating fragments for the two parents. The transit set \(R_k(x, y)\) comprises all offsprings of this form. It forms the tope set of an uniform oriented matroid with Vapnik-Chervonenkis dimension \(k + 1\). The Topological Representation Theorem for oriented matroids thus implies a representation in terms of pseudosphere arrangements. This makes it possible to study 2-point crossover in detail and to characterize the partial cubes defined by the transit sets of two-point crossover.
MSC:
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 05C75 | Structural characterization of families of graphs |
Keywords:
genetic algorithms; recombination; transit functions; oriented matroids; Vapnik-Chervonenkis dimensionReferences:
| [1] | A. Bj¨orner, M. Las Vergnas, B. Sturmfels, N. White and G. M. Ziegler,Oriented matroids, volume 46 ofEncyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, 2nd edition, 1999, doi:10.1017/CBO9780511586507. · Zbl 0944.52006 |
| [2] | J. Bokowski, S. King, S. Mock and I. Streinu, The topological representation of oriented matroids,Discrete Comput. Geom.33(2005), 645-668, doi:10.1007/s00454-005-1164-4. · Zbl 1077.52016 |
| [3] | M. Changat, P. G. Narasimha-Shenoi, F. Hossein Nezhad, M. Kovˇse, S. Mohandas, A. Ramachandran and P. F. Stadler, Transit sets ofk-point crossover operators,AKCE Int. J. Graphs Comb.17(2020), 519-533, doi:10.1016/j.akcej.2019.03.019. · Zbl 1473.05212 |
| [4] | J. C. Culberson, Mutation-crossover isomorphisms and the construction of discriminating functions,Evol. Comp.2(1995), 279-311, doi:10.1162/evco.1994.2.3.279. |
| [5] | K. DeJong and W. M. Spears, A formal analysis of the role of multi-point crossover in genetic algorithms,Ann. Math. Artif. Intelligence5(1992), 1-26, doi:10.1007/BF01530777. · Zbl 1004.68538 |
| [6] | D. ˇZ. Djokovi´c, Distance-preserving subgraphs of hypercubes,J. Comb. Th. Ser. B14(1973), 263-267, doi:10.1016/0095-8956(73)90010-5. · Zbl 0245.05113 |
| [7] | T. M. English, Some geometric and algebraic results on crossover, in:Evolutionary Programming VI, Springer Verlag, Heidelberg, volume 1213 ofLect. Notes Comp. Sci., 1997 pp. 285- 295, doi:10.1007/BFb0014819. |
| [8] | P. Field, Nonbinary transforms for genetic algorithm problems,Complex Systems9(1995), 11-28,https://www.complex-systems.com/abstracts/v09_i01_a02/. |
| [9] | J. Folkman and J. Lawrence, Oriented matroids,J. Combin. Theory Ser. B25(1978), 199-236, doi:10.1016/0095-8956(78)90039-4. · Zbl 0325.05019 |
| [10] | K. Fukuda and K. Handa, Antipodal graphs and oriented matroids,Discrete Math.111(1993), 245-256, doi:10.1016/0012-365X(93)90159-Q. · Zbl 0782.05069 |
| [11] | M. D. Garc´ıa and A. Moraglio, Bridging elementary landscapes and a geometric theory of evolutionary algorithms: First steps, in: A. Auger, C. Fonseca, N. Lourenc¸o, P. Machado, L. Paquete and D. Whitley (eds.),Parallel Problem Solving from Nature - PPSN XV, Springer, Cham, volume 11102, 2018 pp. 194-206, doi:10.1007/978-3-319-99259-4 16. |
| [12] | M. D. Garc´ıa and A. Moraglio, A unifying view on recombination spaces and abstract convex evolutionary search, in: A. Liefooghe and L. Paquete (eds.),Evolutionary Computation in Combinatorial Optimization. EvoCOP 2019, Springer, Cham, volume 11452, 2019 pp. 179- 195, doi:10.1007/978-3-030-16711-0 12. · Zbl 1525.68211 |
| [13] | B. G¨artner and E. Welzl, Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements,Discrete Comput. Geom.12(1994), 399-432, doi:10.1007/BF02574389. · Zbl 0813.52013 |
| [14] | P. Gitchoff and G. P. Wagner, Recombination induced hypergraphs:A new approach to mutation-recombination isomorphism,Complexity2(1996), 47-43, doi:10.1002/(SICI) 1099-0526(199609/10)2:1h37::AID-CPLX9i3.0.CO;2-C. |
| [15] | D. Goldberg, Genetic algorithms and Walsh functions: a gentle introduction,Complex Systems3(1989), 129-152,https://www.complex-systems.com/abstracts/v03_i02_a02/. · Zbl 0748.68050 |
| [16] | J. Holland,Adaptation in Natural and Artificial Systems, MIT Press, Cambridge, MA, 1975. · Zbl 0317.68006 |
| [17] | K. Knauer and T. Marc, On tope graphs of complexes of oriented matroids,Discrete Comput Geom63(2020), 377-417, doi:10.1007/s00454-019-00111-z. · Zbl 1431.05034 |
| [18] | M. Mitchell,An Introduction to Genetic Algorithms, MIT Press, Cambridge, MA, 1996. · Zbl 0906.68113 |
| [19] | H. M. Mulder, Transit functions on graphs (and posets), in: M. Changat, S. Klavˇzar, H. M. Mulder and A. Vijayakumar (eds.),Convexity in Discrete Structures, RMS Lecture Notes Series, 2008 pp. 117-130. · Zbl 1166.05019 |
| [20] | T. Nishizeki and N. Chiba,Planar graphs: Theory and algorithms, North-Holland, Amsterdam, 1988, doi:10.1002/bimj.4710320616. · Zbl 0647.05001 |
| [21] | N. J. Radcliffe, The algebra of genetic algorithms,Ann. Math. Artif. Intelligence10(1994), 339-384, doi:10.1007/BF01531276. · Zbl 0855.68034 |
| [22] | L. M. Schmitt, Theory of genetic algorithms,Theor. Comp. Sci.259(2001), 1-61, doi:10.1016/ S0304-3975(00)00406-0. · Zbl 0972.68133 |
| [23] | P. F. Stadler, R. Seitz and G. P. Wagner, Evolvability of complex characters: Population dependent Fourier decomposition of fitness landscapes over recombination spaces,Bull. Math. Biol. 62(2000), 399-428, doi:10.1006/bulm.1999.0167. · Zbl 1323.92135 |
| [24] | P. F. Stadler and G. P. Wagner, The algebraic theory of recombination spaces,Evol. Comp.5 (1998), 241-275, doi:10.1162/evco.1997.5.3.241. |
| [25] | A. J. Umbarkar and P. D. Sheth, Crossover operators in genetic algortihms: a review,ICTACT J. Soft Computing6(2015), 1083-1092, doi:10.21917/ijsc.2015.0150. |
| [26] | V. N. Vapnik and A. Y. Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities,Theory Probab. Appl.16(1971), 264-280, doi:10.1137/1116025. · Zbl 0247.60005 |
| [27] | V. Vovk, H. Papadopoulos and A. Gammerman (eds.),Measures of Complexity: Festschrift for Alexey Chervonenkis, Springer, Heidelberg, 2015 · Zbl 1331.68020 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
