zbMATH — the first resource for mathematics

On the roles of semantic locality of crossover in genetic programming. (English) Zbl 1284.68530
Summary: Locality has long been seen as a crucial property for the efficiency of evolutionary algorithms in general, and genetic programming (GP) in particular. A number of studies investigating the effects of locality in GP can be found in the literature. The majority of the previous research on locality focuses on syntactic aspects, and operator semantic locality has not been thoroughly tested. In this paper, we investigate the role of semantic locality of crossover in GP. We follow McPhee in measuring the semantics of a subtree using the fitness cases. We use this to define a semantic distance metric. This semantic distance supports the design of some new crossover operators, concentrating on improving semantic locality. We study the impact of these semantically based crossovers on the behaviour of GP. The results show substantial advantages accruing from the use of semantic locality.
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Full Text: DOI
[1] Altenberg, L., The evolution of evolvability in genetic programming, (Advances in Genetic Programming, (1994), MIT Press), 47-74
[2] Beadle, L.; Johnson, C., Semantically driven crossover in genetic programming, (Proceedings of the 2008 I EEE World Congress on Computational Intelligence, (2008), IEEE Press), 111-116
[3] Borjesson, P.; Sundberg, C., Simple approximations of the error function q(x) for communications applications, IEEE Transactions on Communications, 27, 639-643, (1979)
[4] Wedekind, C.; Seebeck, T.; Bettens, F.; Paepke, A., Mhc-dependent mate preferences in humans, Proceedings of Biological Sciences, 260, 245-249, (1995)
[5] Cleary, R.; O’Neill, M., An attribute grammar decoder for the 01 multi-constrained knapsack problem, (Proceedings of the 2005 European Conference on Evolutionary Computation in Combinatorial Optimization, (2005), Springer), 34-45 · Zbl 1119.68431
[6] de la Cruz Echeanda, M.; de la Puente, A. O.; Alfonseca, M., Attribute grammar evolution, (Proceedings of the IWINAC 2005, (2005), Springer Verlag Berlin, Heidelberg), 182-191
[7] Dao, N. P.; Nguyen, Q. U.; Nguyen, X. H.; McKay, R. I.B., Evolving approximations for the Gaussian q-function by genetic programming with semantic based crossover, (Proceedings of the IEEE World Congress on Computational Intelligence, (2012), IEEE Press), 1924-1929
[8] Ekart, A.; Nemeth, S. Z., A metric for genetic programs and fitness sharing, (Poli, R.; Banzhaf, W.; L angdon, W. B.; Miller, J. F.; Nordin, P.; Fogarty, T. C., Genetic Programming, Proceedings of EuroGP’2000, LNCS, vol. 1802, (2000), Springer-Verlag Edinburgh), 259-270
[9] Elliot, M.; Crespi, B., Placental invasiveness mediates the evolution of hybrid inviability in mammals, The American Naturalist, 168, 1, 114, (2006)
[10] Galvan-Lopez, E.; McDermott, J.; O’Neill, M.; Brabazon, A., Defining locality as a problem difficulty measure in genetic programming, Genetic Programming and Evolvable Machines, 12, 4, 365-401, (2011)
[11] Gottlieb, J.; Raidl, G., The effects of locality on the dynamics of decoder-based evolutionary search, (Proceedings of the 2000 Genetic and Evolutionary Computation Conference, (2000), ACM), 283-290
[12] E. Group, Evolutionary and Neural Computation for Time Series Prediction Minisite, Website, 2005. <http://tracer.uc3m.es/tws/TimeSeriesWeb/repo.html>.
[13] Gustafson, S.; Burke, E. K.; Kendall, G., Sampling of unique structures and behaviours in genetic programming, (Proceedings of 7th European Conference on Genetic Programming, LNCS, vol. 3003, (2004), Springer-Verlag), 279-288
[14] Gustafson, S.; Burke, E. K.; Krasnogor, N., On improving genetic programming for symbolic regression, (Proceedings of the 2005 IEEE Congress on Evolutionary Computation, vol. 1, (2005), IEEE Press), 912-919
[15] Harper, R.; Blair, A., A self-selecting crossover operator, (Proceedings of the IEEE Congress on Evolutionary Computation, (2006), IEEE Press), 5569-5576
[16] Hoai, N. X.; McKay, B.; Essam, D., Representation and structural difficulty in genetic programming, IEEE Transactions on Evolutionary Computation, 10, 2, 157-166, (2006)
[17] Hu, T.; Banzhaf, W., The role of population size in rate of evolution in genetic programming, (Proceedings of the EuroGP’2009, LNCS, vol. 5481, (2009), Springer), 85-96
[18] Jabeen, H.; Baig, A. R., Review of classification using genetic programming, International Journal of Engineering Science and Technology, 2, 2, 94-103, (2010)
[19] Johnson, C., Deriving genetic programming fitness properties by static analysis, (Proceedings of the 4th European Conference on Genetic Programming (EuroGP’2002)., LNCS, vol. 2278, (2002), Springer), 299-308
[20] C. Johnson, Genetic programming with guaranteed constraints, in: Proceedings of the 4th International Conference on Recent Advances in Soft Computing (2002), The Nottingham Trent University, 2002b, pp. 134-140.
[21] Johnson, C., Genetic programming with fitness based on model checking, (Proceedings of the 10th European Conference on Genetic Programming (EuroGP2007), LNCS, vol. 4445, (2007), Springer), 114-124
[22] Johnson, C., Genetic programming crossover: does it cross over?, (Proceedings of the 12th European Conference on Genetic Programming (EuroGP2009)., LNCS, vol. 5481, (2009), Springer), 97-108
[23] T. Jones, Evolutionary Algorithms, Fitness Landscapes and Search. Ph.D. thesis, University of New Mexico, Albuquerque, NM, 1995.
[24] Katz, G.; Peled, D., Model checking-based genetic programming with an application to mutual exclusion, Tools and Algorithms for the Construction and Analysis of Systems, 4963, 141-156, (2008) · Zbl 1134.68411
[25] Keijzer, M., Improving symbolic regression with interval arithmetic and linear scaling, (Proceedings of EuroGP’2003, LNCS, vol. 2610, (2003), Springer-Verlag), 70-82 · Zbl 1033.68630
[26] Knuth, D., Semantics of context-free languages, Mathematical Systems Theory, 2, 95, (1968) · Zbl 0219.68035
[27] Koza, J., Genetic programming: on the programming of computers by natural selection, (1992), MIT Press MA · Zbl 0850.68161
[28] Koza, J. R., Genetic programming: on the programming of computers by means of natural selection, (1992), The MIT Press Cambridge, MA · Zbl 0850.68161
[29] K. Krawiec, P. Lichocki, Approximating geometric crossover in semantic space, in: Proceedings of Genetic and Evolutionary Computation Conference, GECCO’2009, ACM, 2009, pp. 987-994.
[30] Langdon, W. B., Size fair and homologous tree genetic programming crossovers, (Proceedings of the 1999 Genetic and Evolutionary Computation Conference, (1999), Morgan Kaufman), 1092-1097
[31] Lin, P. C.; Chen, J. S., Fuzzytree crossover for multi-valued stock valuation, Information Sciences, 177, 5, 1193-1203, (2007)
[32] Mackey, M. C.; Glass, L., Oscillation and chaos in physiological control systems, Science, 197, 287-289, (1977) · Zbl 1383.92036
[33] Majeed, H.; Ryan, C.; destructive, A less, Context-aware crossover operator for gp, (Proceedings of the 9th European Conference on Genetic Programming (EuroGP2006), LNCS, vol. 5, (2006), LNCS), 36-48
[34] McPhee, N.; Ohs, B.; Hutchison, T., Semantic building blocks in genetic programming, (Proceedings of 11th European Conference on Genetic Programming (EuroGP2008), LNCS, vol. 4971, (2008), Springer), 134-145
[35] Moraglio, A.; Krawiec, K.; Johnson, C. G., Geometric semantic genetic programming, (Parallel Problem Solving from Nature, PPSN XII (Part 1), Lecture Notes in Computer Science, vol. 7491, (2012), Springer Taormina, Italy), 21-31
[36] O’Reilly, U. M.; Oppacher, F., Program search with a hierarchical variable length representation: genetic programming, simulated annealing and Hill climbing, (Parallel Problem Solving from Nature, LNCS, vol. 866, (1994), Springer-Verlag), 397-406
[37] Poli, R.; Langdon, W. B., Genetic programming with one-point crossover, (Proceedings 2007 of Soft Computing in Engineering Design and Manufacturing Conference, (1997), Springer-Verlag), 180-189
[38] Poli, R.; Langdon, W. B.; McPhee, N., A field guide to genetic programming, (2008), Lulu Enterprises Ltd. UK
[39] Riley, J.; Ciesielski, V., Fitness landscape analysis for evolutionary non-photorealistic rendering, (IEEE Congress on Evolutionary Computation (CEC 2010), (2010), IEEE Press Barcelona, Spain), 1-9
[40] Rosenlicht, M., Liouville’s theorem on functions with elementary integrals, Pacific Journal of Mathematics, 24, 1, 153-161, (1968) · Zbl 0155.36702
[41] Rothlauf, F., Representations for genetic and evolutionary algorithms, (2006), Springer · Zbl 1030.68083
[42] Rothlauf, F.; Oetzel, M., On the locality of grammatical evolution, (Proceedings of the 9th European Conference on Genetic Programming (EuroGP2006)., LNCS, vol. 3905, (2006), Springer), 320-330
[43] Silva, S.; Dignum, S., Extending operator equalisation: fitness based self adaptive length distribution for bloat free GP, (Proceedings of the 12th European Conference on Genetic Programming, LNCS, vol. 5481, (2009), Springer), 159-170
[44] Simon, M., Probability distributions involving Gaussian random variables: A handbook for engineers and scientists, (2002), Kluwer Academics · Zbl 1135.60005
[45] Uy, N. Q.; Hien, N. T.; Hoai, N. X.; O’Neill, M., Improving the generalisation ability of genetic programming with semantic similarity based crossover, (Proceedings of EuroGP’2010, LNCS, vol. 6021, (2010), Springer), 184-195
[46] Uy, N. Q.; Hoai, N. X.; O’Neill, M., Semantic aware crossover for genetic programming: the case for real-valued function regression, (Proceedings of EuroGP’09, LNCS, vol. 5481, (2009), Springer), 292-302
[47] Uy, N. Q.; Hoai, N. X.; O’Neill, M.; Mckay, B., Semantics based crossover for Boolean problems, (Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2010, (2010), ACM Portland, Oregon), 869-876
[48] N.Q. Uy, M. O’Neill, N.X. Hoai, B. McKay, E.G. Lopez, Semantic similarity based crossover in GP: the case for real-valued function regression, in: Evolution Artificielle, 9th International Conference (EA2009), vol. 5975 of LNCS, 2009b, pp. 170-181.
[49] Uy, N. Q.; O’Neill, M.; Hoai, N. X.; McKay, B.; Lopez, E. G., Semantically-based crossover in genetic programming: application to real-valued symbolic regression, Genetic Programming and Evolvable Machines, 12, 2, 19-91, (2011)
[50] Vanneschi, L.; Tomassini, M.; Collard, P.; Clergue, M., Fitness distance correlation in structural mutation genetic programming, (Ryan, C.; Soule, T.; Keijzer, M.; Tsang, E.; Poli, R.; Costa, E., Genetic Programming, Proceedings of EuroGP’2003. Essex, LNCS, vol. 2610, (2003), Springer-Verlag), 455-464 · Zbl 1033.68652
[51] Weinberger, E. D., Correlated and uncorrelated fitness landscapes and how to tell the difference, Biological Cybernetics, 63, 325-336, (1990) · Zbl 0703.92016
[52] M.L. Wong, K.S. Leung, An induction system that learns programs in different programming languages using genetic programming and logic grammars, in: Proceedings of the 1995 IEEE International Conference on Tools with Artificial Intelligence, 1995, pp. 380-387.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.