Now showing 1 - 10 of 10
  • Publication
    Evolving a Ms. PacMan controller using grammatical evolution
    In this paper we propose an evolutionary approach capable of successfully combining rules to play the popular video game, Ms. Pac- Man. In particular we focus our attention on the benefits of using Gram- matical Evolution to combine rules in the form of “if then perform ”. We defined a set of high-level functions that we think are necessary to successufully maneuver Ms. Pac-Man through a maze while trying to get the highest possible score. For comparison purposes, we used four Ms. Pac-Man agents, including a hand-coded agent, and tested them against three different ghosts teams. Our approach shows that the evolved controller achieved the highest score among all the other tested controllers, regardless of the ghost team used.
      828Scopus© Citations 23
  • Publication
    Comparing the performance of the evolvable πgrammatical evolution genotype-phenotype pap to grammatical evolution in the dynamic Ms. Pac-Man environment
    In this work, we examine the capabilities of two forms of mappings by means of Grammatical Evolution (GE) to successfully generate controllers by combining high-level functions in a dynamic environment. In this work we adopted the Ms. Pac-Man game as a benchmark test bed. We show that the standard GE mapping and Position Independent GE (πGE) mapping achieve similar performance in terms of maximising the score. We also show that the controllers produced by both approaches have an overall better performance in terms of maximising the score compared to a hand-coded agent. There are, however, significant differences in the controllers produced by these two approaches: standard GE produces more controllers with invalid code, whereas the opposite is seen with πGE.
      586Scopus© Citations 11
  • Publication
    Defining locality as a problem difficulty measure in genetic programming
    A mapping is local if it preserves neighbourhood. In Evolutionary Computation, locality is generally described as the property that neighbouring genotypes correspond to neighbouring phenotypes. A representation has high locality if most genotypic neighbours are mapped to phenotypic neighbours. Locality is seen as a key element in performing effective evolutionary search. It is believed that a representation that has high locality will perform better in evolutionary search and the contrary is true for a representation that has low locality. When locality was introduced, it was the genotype-phenotype mapping in bitstring-based Genetic Algorithms which was of interest; more recently, it has also been used to study the same mapping in Grammatical Evolution. To our knowledge, there are few explicit studies of locality in Genetic Programming (GP). The goal of this paper is to shed some light on locality in GP and use it as an indicator of problem difficulty. Strictly speaking, in GP the genotype and the phenotype are not distinct. We attempt to extend the standard quantitative definition of genotype-phenotype locality to the genotype-fitness mapping by considering three possible definitions. We consider the effects of these definitions in both continuous- and discrete-valued fitness functions. We compare three different GP representations (two of them induced by using different function sets and the other using a slightly different GP encoding) and six different mutation operators. Results indicate that one definition of locality is better in predicting performance.
      566Scopus© Citations 38
  • Publication
    Semantically-based crossover in genetic programming : application to real-valued symbolic regression
    We investigate the effects of semantically-based crossover operators in Genetic Programming, applied to real-valued symbolic regression problems. We propose two new relations derived from the semantic distance between subtrees, known as Semantic Equivalence and Semantic Similarity. These relations are used to guide variants of the crossover operator, resulting in two new crossover operators – Semantics Aware Crossover (SAC) and Semantic Similarity-based Crossover (SSC). SAC, was introduced and previously studied, is added here for the purpose of comparison and analysis. SSC extends SAC by more closely controlling the semantic distance between subtrees to which crossover may be applied. The new operators were tested on some real-valued symbolic regression problems and compared with Standard Crossover (SC), Context Aware Crossover (CAC), Soft Brood Selection (SBS), and No Same Mate (NSM) selection. The experimental results show on the problems examined that, with computational effort measured by the number of function node evaluations, only SSC and SBS were significantly better than SC, and SSC was often better than SBS. Further experiments were also conducted to analyse the perfomance sensitivity to the parameter settings for SSC. This analysis leads to a conclusion that SSC is more constructive and has higher locality than SAC, NSM and SC; we believe these are the main reasons for the improved performance of SSC.
      1743Scopus© Citations 206
  • Publication
    Tree-adjunct grammatical evolution
    In this paper we investigate the application of Tree-Adjunct Grammars to Grammatical Evolution. The standard type of grammar used by grammatical evolution, context-free grammars, produce a subset of the languages that tree-adjunct grammars can produce, making tree-adjunct grammars, expressively, more powerful. In this study we shed some light on the effects of tree-adjunct grammars in grammatical evolution, or Tree-Adjunct Grammatical Evolution. We perform an analytic comparison of the performance of both setups, i.e., grammatical evolution and tree-adjunct grammatical evolution, across a number of classic genetic programming benchmarking problems. The results firmly indicate that tree-adjunct grammatical evolution has a better overall performance (measured in terms of finding the global optima).
      675Scopus© Citations 17
  • Publication
    Investigating mapping order in πGE
    We present an investigation into the genotype-phenotype map in Position Independent Grammatical Evolution (πGE). Previous studies have shown πGE to exhibit a performance increase over standard GE. The only difference between the two approaches is in how the genotype-phenotype mapping process is performed. GE uses a leftmost non terminal expansion, while πGE evolves the order of mapping as well as the content. In this study, we use the idea of focused search to examine which aspect of the πGE mapping process provides the lift in performance over standard GE by applying our approaches to four benchmark problems taken from specialised literature. We examined the traditional πGE approach and compared it to two setups which examined the extremes of mapping order search and content search, and against setups with varying ratios of content and order search. In all of these tests a purely content focused πGE was shown to exhibit a performance gain over the other setups.
      524Scopus© Citations 3
  • Publication
    Neutrality in evolutionary algorithms... what do we know?
    Over the last years, the effects of neutrality have attracted the attention of many researchers in the Evolutionary Algorithms (EAs) community. A mutation from one gene to another is considered as neutral if this modification does not affect the phenotype. This article provides a general overview on the work carried out on neutrality in EAs. Using as a framework the origin of neutrality and its study in different paradigms of EAs (e.g., Genetic Algorithms, Genetic Programming), we discuss the most significant works and findings on this topic. This work points towards open issues, which the community needs to address.
      621Scopus© Citations 42
  • Publication
    An analysis of genotype-phenotype maps in grammatical evolution
    We present an analysis of the genotype-phenotype map in Grammatical Evolution (GE). The standard map adopted in GE is a depth-first expansion of the non-terminal symbols during the derivation sequence. Earlier studies have indicated that allowing the path of the expansion to be under the guidance of evolution as opposed to a de- terministic process produced significant performance gains on all of the benchmark problems analysed. In this study we extend this analysis to in- clude a breadth-first and random map, investigate additional benchmark problems, and take into consideration the implications of recent results on alternative grammar representations with this new evidence. We con- clude that it is possible to improve the performance of grammar-based Genetic Programming by the manner in which a genotype-phenotype map is performed.
      636Scopus© Citations 30
  • Publication
    Implementing an intuitive mutation operator for interactive evolutionary 3D design
    Locality - how well neighbouring genotypes correspond to neighbouring phenotypes - has been described as a key element in Evolutionary Computation. Grammatical Evolution (GE) is a generative system as it uses grammar rules to derive a program from an integer encoded genome. The genome, upon which the evolutionary process is carried out, goes through several transformations before it produces an output. The aim of this paper is to investigate the impact of locality during the generative process using both qualitative and quantitative techniques. To explore this, we examine the effects of standard GE mutation using distance metrics and conduct a survey of the output designs. There are two different kinds of event that occur during standard GE Mutation. We investigate how each event type affects the locality on different phenotypic stages when applied to the problem of interactive design generation.
      639Scopus© Citations 9
  • Publication
    Defining locality in genetic programming to predict performance
    A key indicator of problem difficulty in evolutionary computation problems is the landscape’s locality, that is whether the genotype-phenotype mapping preserves neighbourhood. In genetic programming the genotype and phenotype are not distinct, but the locality of the genotype- fitness mapping is of interest. In this paper we extend the original standard quantitative definition of locality to cover the genotype-fitness case, considering three possible definitions. By relating the values given by these definitions with the results of evolutionary runs, we investigate which definition is the most useful as a predictor of performance.
      703Scopus© Citations 17