Examining Semantic Diversity and Semantic Locality of Operators in Genetic Programming

Created by W.Langdon from gp-bibliography.bib Revision:1.3973

@PhdThesis{Quang_Uy_Nguyen:thesis,
  author =       "Quang Uy Nguyen",
  title =        "Examining Semantic Diversity and Semantic Locality of
                 Operators in Genetic Programming",
  school =       "University College Dublin",
  year =         "2011",
  address =      "Ireland",
  month =        "18 " # jul,
  email =        "quanguyhn@gmail.com",
  keywords =     "genetic algorithms, genetic programming",
  URL =          "http://ncra.ucd.ie/papers/Thesis_Uy_Corrected.pdf",
  size =         "230 pages",
  abstract =     "Diversity, the ability of a searcher to explore
                 different parts of the search space, and locality, the
                 ability of a searcher to exploit a specific area of the
                 search space, have long been seen as crucial properties
                 for the efficiency of Evolutionary Algorithms in
                 general, and Genetic Programming (GP) in particular. A
                 number of studies investigating the effects of
                 diversity and locality in GP can be found in the
                 literature. However, most previous work on diversity,
                 and all on locality, focus solely on syntactic aspects;
                 semantic diversity and locality of operators have not
                 been thoroughly investigated. This thesis investigates
                 the role of semantic diversity and semantic locality of
                 operators in GP.

                 This thesis proposes a novel way to measure semantics
                 in GP by sampling a number of points from the problem
                 domain. This semantics is called Sampling Semantics.
                 From that, a semantic distance and two semantic
                 relationships between subtrees are defined. Based on
                 these metrics, a number of novel semantic based genetic
                 operators (crossovers and mutations) are introduced.
                 These operators address two main objectives: Promoting
                 semantic diversity and improving semantic locality. The
                 new semantic based crossovers and mutations are tested
                 on a number of real valued symbolic regression problems
                 and the experimental results show the positive impact
                 of promoting semantic diversity and the greater
                 improvement of enhancing semantic locality. Since
                 crossover has long been seen as the primary operator in
                 GP, the thesis places an emphasis on studying semantic
                 based crossovers. These semantic based crossovers are
                 analysed on some important properties of GP. The
                 results show that semantic based crossovers achieve
                 greater semantic diversity and higher semantic locality
                 that leads to more constructive effect (more frequently
                 generate children that are better then their parents)
                 in comparison with standard crossover. This analysis
                 shed some light on the improved performance of semantic
                 based crossovers.

                 Furthermore, a deep analysis of the behaviour of
                 semantic based crossovers are investigated. Aspects
                 under investigation include the generalisation ability
                 of semantic based crossover, the comparison between
                 semantic locality and syntactic locality, the ability
                 of semantic based crossovers to deal with increasingly
                 difficult problems and their impact on the fitness
                 landscape. The experimental results show that the
                 generalisation ability of semantic based crossovers is
                 better than standard crossover, that semantic locality
                 is more important than syntactic locality in improving
                 GP performance, and the ability of GP to generalise.
                 They also show that semantic based crossovers deal well
                 with increasingly difficult problems and that improving
                 semantic locality helps to smooth out the fitness
                 landscape of a problem.

                 Finally, the idea of promoting semantic diversity and
                 enhancing semantic locality are extended to the Boolean
                 domain. For Boolean problems, new semantic based
                 crossovers are proposed. These crossovers are then
                 tested on some well-known Boolean problems and the
                 results again show that promoting semantic diversity is
                 important with Boolean problems and that improving
                 semantic locality even leads to a further improvement
                 of GP performance.

                 In summary, this thesis highlights the important role
                 semantics has to play in managing diversity and
                 locality in GP.",
}

Genetic Programming entries for Quang Uy Nguyen

Citations