×

Transit sets of \(k\)-point crossover operators. (English) Zbl 1473.05212

Summary: \(k\)-point crossover operators and their recombination sets are studied from different perspectives. We show that transit functions of \(k\)-point crossover generate, for all \(k > 1\), the same convexity as the interval function of the underlying graph. This settles in the negative an open problem by H. M. Mulder [Ramanujan Math. Soc. Lect. Notes Ser. 5, 117–130 (2008; Zbl 1166.05019)] about whether the geodesic convexity of a connected graph \(G\) is uniquely determined by its interval function \(I\). The conjecture of P. Gitchoff and G. P. Wagner [“Recombination induced hypergraphs: a new approach to mutation-recombination isomorphism”, Complexity 2, No. 1, 37–43 (1996)] that for each transit set \(R_k (x,y)\) distinct from a hypercube there is a unique pair of parents from which it is generated is settled affirmatively. Along the way we characterize transit functions whose underlying graphs are Hamming graphs, and those with underlying partial cube graphs. For general values of \(k\) it is shown that the transit sets of \(k\)-point crossover operators are the subsets with maximal Vapnik-Chervonenkis dimension.

MSC:

05C62 Graph representations (geometric and intersection representations, etc.)
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C75 Structural characterization of families of graphs

Citations:

Zbl 1166.05019
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] English, T. M., Some geometric and algebraic results on crossover, Evolutionary Programming VI. Lect. Notes Comp. Sci., vol. 1213, 285-295 (1997), Springer Verlag: Springer Verlag, Heidelberg
[2] Culberson, J. C., Mutation-crossover isomorphisms and the construction of discriminating functions, Evol. Comp., 2, 279-311 (1995)
[3] DeJong, K.; Spears, W. M., A formal analysis of the role of multi-point crossover in genetic algorithms, Ann. Math. Artif. Intell., 5, 1-26 (1992) · Zbl 1004.68538
[4] Schmitt, L. M., Theory of genetic algorithms, Theoret. Comput. Sci., 259, 1-61 (2001) · Zbl 0972.68133
[5] Stadler, P. F.; Seitz, R.; Wagner, G. P., Evolvability of complex characters: population dependent Fourier decomposition of fitness landscapes over recombination spaces, Bull. Math. Biol., 62, 399-428 (2000) · Zbl 1323.92135
[6] Goldberg, D., Genetic algorithms and Walsh functions: a gentle introduction, Complex Syst., 3, 129-152 (1989) · Zbl 0748.68050
[7] Field, P., Nonbinary transforms for genetic algorithm problems, Complex Syst., 9, 11-28 (1995)
[8] Holland, J., Adaptation in Natural and Artificial Systems (1975), MIT Press: MIT Press, Cambridge, MA · Zbl 0317.68006
[9] Radcliffe, N. J., The algebra of genetic algorithms, Ann. Math. Artif. Intell., 10, 339-384 (1994) · Zbl 0855.68034
[10] Gitchoff, P.; Wagner, G. P., Recombination induced hypergraphs: a new approach to mutation-recombination isomorphism, Complexity, 2 (1996)
[11] Mulder, H. M.; Changat, M.; Klavžar, S.; Mulder, H. M.; Vijayakumar, A., Transit functions on graphs (and posets), Convexity in Discrete Structures. RMS Lecture Notes Series, 117-130 (2008) · Zbl 1166.05019
[12] Mulder, H. M., The Interval Function of a Graph. Math. Centre Tracts, vol. 132 (1980), Math. Centre: Math. Centre, Amsterdam, NL · Zbl 0446.05039
[13] Shpak, M.; Wagner, G. P., Asymmetry of configuration space induced by unequal crossover: implications for a mathematical theory of evolutionary innovation, Artif. Life, 6, 25-43 (1999)
[14] Moraglio, A.; Poli, R.; Deb, K.; Poli, R.; Banzhaf, W.; Beyer, H. G.; Burke, E.; Darwen, P.; Dasgupta, D.; Floreano, D.; Foster, J.; Harman, M.; Holland, O.; Lanzi, P. L.; Spector, L.; Tettamanzi, A., Topological interpretation of crossover, Genetic and Evolutionary Computation - GECCO 2004. Lect. Notes Comp. Sci., vol. 3102, 1377-1388 (2004)
[15] Nebeský, L., The interval function of a connected graph and a characterization of geodetic graphs, Math. Bohem., 126, 247-254 (2001) · Zbl 0977.05045
[16] Mulder, H. M.; Nebeský, L., Axiomatic characterization of the interval function of a graph, European J. Combin., 30, 5, 1172-1185 (2009) · Zbl 1205.05074
[17] Changat, M.; Klavžar, S.; Mulder, H. M., The all-paths transit function of a graph, Czechoslovak Math. J., 51, 2, 439-448 (2001) · Zbl 0977.05135
[18] Hammack, R.; Imrich, W.; Klavžar, S., Handbook of Product Graphs (2011), CRC Press: CRC Press, Boca Raton, FL · Zbl 1283.05001
[19] Laborde, J. M.; Rao Hebbare, S. P., Another characterization of hypercubes, Discrete Math., 39, 2, 161-166 (1982) · Zbl 0482.05033
[20] Mollard, M., Two characterizations of generalized hypercube, Discrete Math., 93, 1, 63-74 (1991) · Zbl 0752.05043
[21] van de Vel, M., Matching binary convexities, Topol. Appl., 16, 207-235 (1983) · Zbl 0543.52001
[22] Changat, M.; Mathew, J.; Mulder, H. M., The induced path function, monotonicity and betweenness, Discrete Appl. Math., 156, 426-433 (2010) · Zbl 1225.05146
[23] van de Vel, M., Theory of Convex Structures, vol. 50 (1993), North Holland: North Holland, Amsterdam · Zbl 0785.52001
[24] Nebeský, L., A characterization of the interval function of a connected graph, Czechoslovak Math. J., 44, 173-178 (1994) · Zbl 0808.05046
[25] Ovchinnikov, S., Graphs and Cubes (2011), Springer: Springer, New York, NY · Zbl 1283.05002
[26] Dress, A. W.M.; Feng, J.; Jost, J.; Qian, M., The category of \(####\)-nets, Networks: From Biology to Theory, 3-22 (2007), Springer: Springer, London, UK · Zbl 1268.92048
[27] Dress, A. W.M.; Huber, K. T.; Koolen, J.; Moulton, V.; Spillner, A., Basic Phylogenetic Combinatorics (2012), Cambridge University Press: Cambridge University Press, Cambridge, UK · Zbl 1298.92008
[28] Vapnik, V.; Chervonenkis, A., On the uniform convergence of relative frequencies of events to their probabilities, Theory Probab. Appl., 16, 264-280 (1971) · Zbl 0247.60005
[29] Measures of Complexity: Festschrift for Alexey Chervonenkis (2015), Springer: Springer, Heidelberg · Zbl 1331.68020
[30] Puljić, K.; Manger, R., Comparison of eight evolutionary crossover operators for the vehicle routing problem, Math. Commun., 18, 359-375 (2013) · Zbl 1282.90154
[31] Bala, A.; Sharma, A. K.; Saini, H.; Ghrera, S. P.; Sehgal, V. K., A comparative study of modified crossover operators, Third International Conference on Image Information Processing, ICIIP, 281-284 (2015), IEEE: IEEE, Piscataway, NJ
[32] Bernstein, S., Demonstration mathématique de la loi d’hérédité de Mendel, C. R. Acad. Sci. Paris, 177, 528-531 (1923) · JFM 49.0368.02
[33] Etherington, I. M.H., Genetic algebras, Proc. Roy. Soc. Edinburgh, 59, 242-258 (1939) · JFM 65.1138.05
[34] Wörz-Busekros, A., Algebras in Genetics, vol. 36 (1980), Springer-Verlag: Springer-Verlag, New York · Zbl 0431.92017
[35] Lyubich, Y. I., Mathematical Structures in Population Genetics (1992), Springer-Verlag: Springer-Verlag, New York · Zbl 0747.92019
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.