- 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.",
