We wish to explore the contribution that asocial and social learning might play as a mechanism for self-adaptation in the search for variable-length structures by an evolutionary algorithm. An extremely challenging, yet simple to understand problem landscape is adopted where the probability of randomly finding a solution is approximately one in a trillion. A number of learning mechanisms operating on variable-length structures are implemented and their performance analysed. The social learning setup, which combines forms of both social and asocial learning in combination with evolution is found to be most performant, while the setups exclusively adopting evolution are incapable of finding solutions.

Grammar-Guided Genetic Programming is already outperforming humans at creating efficient transmission schedulers for large heterogeneous communications networks. We have previously proposed a multi-level grammar approach which achieved significantly better results than the canonical Grammar-Guided Genetic Programming approach. Initially, a restricted `small' grammar is utilised in order to discover suitable structures. A full grammar is then adopted after this initial phase. Hence, evolution can focus on maximising performance, by fine-tuning the well-structured models. In this work, we propose to use a hierarchical approach by employing multiple small grammars instead of a unique small grammar at the lower level, in conjunction with the full grammar at the upper level. To use multiple small grammars while maintaining the same computational budget, we have to use either (i) reduce the number of generations, or (ii) reduce the size of the population for the evolution with each of the small grammars. In this work, we confirm that the hierarchical grammar approach using the division of number of generations strategy achieves significantly better results than the multi-level approach, but requires defining an ideal number of small grammars to achieve the best performance. We also show that the hierarchical grammar approach using the division of population size strategy achieves significantly better results than the multi-level approach. However the division of population size strategy is less sensitive to the number of small grammars.

The accurate localisation and tracking of objects is crucial in many domains. In this paper, we focus on location tracking in wireless networks. Reliable localisation will be essential for self-driving, future factories, and beamforming in 5G deployments. Time-of-arrival (TOA) based localisation systems use synchronised nodes to receive radio signals sent by transmitters at the object to be located. The time it takes for the signal to propagate in a straight line to the receiver is used to trilaterate the position of the transmitter. However, the correct TOA can be difficult to identify due to multiple reflected copies of the same signal arriving at different times. This paper presents a bidirectional recurrent neural network (BiRNN) for estimating the TOA from the channel impulse response (CIR) of the signal, and a multilayer perceptron (MLP) to trilaterate the position of the transmitter from the TOA. The BiRNN and MLP are trained using measured CIR data, and outperform the conventional approaches for TOA estimation and trilateration.

A recent study in Artificial Life found that the need for mutational robustness can give rise to simpler structures in an evolving population. This begs the question, do we observe a similar phenomenon in Genetic Programming? Genetic Programming requires the search of structural space of solutions, usually requiring code growth to find fitter solutions. Typically Genetic Programming algorithms then suffer from code bloat, which is code growth in the absence of fitness gains. In this study we ask a simple question. Would the necessity for mutational robustness under selection pressure drive the evolution of less complex solution structures in Genetic Programming, with the potential to counteract code bloat?

We present a novel approach to generating seasonal training plans for elite athletes using the grammatical evolution approach to genetic programming. A grammatical encoding of a team sport training plan dictates the plan structure. The quality of the training plan is calculated using the widely adopted fitness-fatigue model, which in this study incorporates four performance metrics, namely distance covered at low to medium speed, distance covered at high speed, distance covered accelerating, and distance covered decelerating. We compare performance of the evolved training plans to a control setup which generates plans using a pseudo-random search process, and baseline against the training plan adopted by an elite team of Gaelic Football Players. Significant potential performance gains are achieved over the control setup and baseline elite team plan.

Learning as a form of adaptation has been shown to benefit the evolutionary process through the Baldwin Effect, promoting the adaptivity of an evolving population. Learning generally can be classified into two types: asocial learning, e.g., trial-and-error; and social learning, e.g., imitation learning. Recent research has shown that a learning strategy (or learning rule) - which combines social and asocial learning in a strategic way - can be more adaptive than either type of learning functioning alone. However, this general finding leaves open the important question as to how best to combine these forms of learning in differing environmental conditions. This paper investigates this question under a variety of environmental dynamics and also provides some indications for future work.

Learning has been shown to be beneficial to an evolutionary process through the Baldwin Effect. Moreover, learning can be classified into two categories: asocial learning, e.g. trial-and-error; and social learning, e.g. imitation learning. A learning strategy, or learning rule - a combination of individual and social learning --- has been suggested by recent research can be more adaptive than both social and individual learning alone. However, this also leaves open an important question as to how best to combine these forms of learning in different environments. This paper investigates this question under a dynamic rugged landscape (i.e. dynamic NK-landscape). Experimental results show that a learning strategy is able to promote an evolving population better, resulting in higher average fitness, over a series of changing environments than asocial learning alone. The results also show that the population of strategic learners maintains a higher proportion of plasticity --- the ability to change the phenotype in response to environmental challenges --- than the population of individual learners alone.

Wireless communications networks are operating at breaking point during an era of relentless traffic growth. Network operators must utilize scarce and expensive wireless spectrum efficiently in order to satisfy demand. Spectrum on the links between cells and user equipments ('users': smartphones, tablets, etc.) frequently becomes congested. Capacity can be increased by transmitting data packets via multiple links. Packets can be routed through multiple Long Term Evolution (LTE) links in existing fourth generation (4G) networks. In future 5G deployments, users will be equipped to receive packets over LTE, WiFi, and millimetre wave links simultaneously.

Evolutionary computation is used to automatically evolve small cell schedulers on a realistic simulation of a 4G-LTE heterogeneous cellular network. Evolved schedulers are then further augmented by human design to improve robustness. Extensive analysis of evolved solutions and their performance across a wide range of metrics reveals evolution has uncovered a new human-competitive scheduling technique which generalises well across cells of varying sizes. Furthermore, evolved methods are shown to conform to accepted scheduling frameworks without the evolutionary process being explicitly told the form of the desired solution. Evolved solutions are shown to out-perform a human-engineered state-of-the-art benchmark by up to 50%. Finally, the approach is shown to be flexible in that tailored algorithms can be evolved for specific scenarios and corner cases, allowing network operators to create unique algorithms for different deployments, and to postpone the need for costly hardware upgrades.

Modern genetic programming (GP) operates within the statistical machine learning (SML) framework. In this framework, evolution needs to balance between approximation of an unknown target function on the training data and generalization, which is the ability to predict well on new data. This paper provides a survey and critical discussion of SML methods that enable GP to generalize.

Traditional single-tiered wireless communications networks cannot scale to satisfy exponentially rising demand. Operators are increasing capacity by densifying their existing macro cell deployments with co-channel small cells. However, cross-tier interference and load balancing issues present new optimization challenges in channel sharing heterogeneous networks (HetNets). One-size-fits-all heuristics for allocating resources are highly suboptimal, but designingad hoccontrollers requires significant human expertise and manual fine-tuning. In this paper, a unified, flexible, and fully automated approach for end-to-end optimization in multi-layer HetNets is presented. A hill climbing algorithm is developed for reconfiguring cells in real time in order to track dynamic traffic patterns. Schedulers for allocating spectrum to user equipment are automatically synthesized using grammar-based genetic programming. The proposed methods for configuring the HetNet and scheduling in the time–frequency domain can addressad hocobjective functions. Thus, the operator can flexibly tune the tradeoff between peak rates and fairness. Far cell edge downlink rates are increased by up to 250% compared with non-adaptive baselines. Alternatively, peak rates are increased by up to 340%. The experiments illustrate the utility and future potential of natural computing techniques in software-defined wireless communications networks.

Program synthesis is a complex problem domain tackled by many communities via different methods. In the last few years, a lot of progress has been made with Genetic Programming (GP) on solving a variety of general program synthesis problems for which a benchmark suite has been introduced. While Genetic Programming is capable of finding correct solutions for many problems contained in a general program synthesis problems benchmark suite, the actual success rate per problem is low in most cases. In this paper, we analyse certain aspects of the benchmark suite and the computational effort required to solve its problems. A subset of problems on which GP performs poorly is identified. This subset is analysed to find measures to increase success rates for similar problems. The paper concludes with suggestions to refine performance on program synthesis problems.

Learning, through the Baldwin effect, has showed to successfully guide evolutionary process in a number of research. More interestingly, learning can be classified into two categories. The first one is asocial (individual) learning when learners learn by directly interacting with their environment, e.g. trial-and-error. The other is social learning when learners learn from others, e.g. imitation learning. There has been a large body of research on this topic concerning the former. Drawing on a rich literature concerning social learning in animals, this paper reconsiders the Baldwin effect under the eye of social learning. The paper provides an introduction of social learning and related concepts. We also propose our own algorithm combining evolution and social learning and test on a compact simulation. The results obtained are encouraging and indicative. Social learning in combination with asocial learning has showed to be useful to guide the evolutionary search. Experimental results also indicate that social learning makes the Baldwin effect happens more quickly, as well as increase the average fitness of the population. The level of information fidelity is also investigated with respect to its influence on the effect of social learning by a series of comparative experiments. The relationship between social learning and asocial learning in nature is also discussed as an indication for future works.

Small Cells are being deployed alongside pre-existing Macro Cells in order to satisfy demand during the current era of exponential growth in mobile traffic. Heterogeneous networks are economical because both cell tiers share the same scarce and expensive spectrum. However, customers at cell edges experience severe cross-tier interference in channel sharing Het-Nets, resulting in poor service quality. Techniques for improving fairness globally have been developed in previous works. In this paper, a novel method for service differentiation at the level of individual customers is proposed. The proposed algorithm redistributes spectrum on a millisecond timescale, so that premium customers experience minimum downlink rates exceeding a target threshold. System level simulations indicate that downlink rate targets of at least 1 [Mbps] are always satisfied under the proposed scheme. By contrast, naive scheduling achieves the 1 [Mbps] target only 83% of the time. Quality of service can be improved for premium customers without significantly impacting global fairness metrics. Flexible service differentiation will be key to effectively monetizing the next generation of 5G wireless communications networks.

Testing is crucial to ensure the quality of software systems-but testing is an expensive process, so test managers try to minimise the set of tests to run to save computing resources and speed up the testing process and analysis. One problem is that there are different perspectives on what is a good test and it is usually not possible to compare these dimensions. This is a perfect example of a multi-objective optimisation problem, which is hard-especially given the scale of the search space here. In this paper, we propose a novel hybrid algorithm to address this problem. Our method is composed of three steps: a greedy algorithm to find quickly some good solutions, a genetic algorithm to increase the search space covered and a local search algorithm to refine the solutions. We demonstrate through a large scale empirical evaluation that our method is more reliable (better whatever the time budget) and more robust (better whatever the number of dimensions considered)-in the scenario with 4 objectives and a default execution time, we are 178% better in hypervolume on average than the state-of-the-art algorithms.

The use of semantic information in genetic programming operators has shown major improvements in recent years, especially in the regression and boolean domain. As semantic information is domain specific, using it in other areas poses certain problems. Semantic operators require being adapted for the problem domain they are applied to. An attempt to create a semantic crossover for program synthesis has been made with rather limited success, but the results have provided insights about using semantics in program synthesis. Based on this initial attempt, this paper presents an improved version of semantic operators for program synthesis, which contains a small but significant change to the overall functionality, as well as a novel measure for the comparison of the semantics of subtrees. The results show that the improved semantic crossover is superior to the previous semantic operator in the program synthesis domain.

Drawing on a rich literature concerning social learning in animals, this paper presents a variation of Grammatical Evolution (GE) which incorporates one of the most powerful forms of social learning, namely imitation learning. This replaces the traditional method of `communication' between individuals in GE - crossover - which is drawn from an evolutionary metaphor. The paper provides an introduction to social learning, describes the proposed variant of GE, and tests on a series of benchmark symbolic regression problems. The results obtained are encouraging, being very competitive when compared with canonical GE. It is noted that the literature on social learning provides a number of useful meta-frameworks which can be used in the design of new search algorithms and to allow us to better understand the strengths and weaknesses of existing algorithms. Future work is indicated in this area.

This paper presents gems, a novel method to accelerate fitness improvement in Evolutionary Algorithms (EAs). The paper develops the models, describes an experimental implementation, comments on characteristics of problem-domains that indicate where gems may be used, and suggests an explanation of the observed behavior. Experimental results show that gems accelerate the rate of fitness increase, and that the larger the problem instance, the larger the benefit. Runtime analysis shows that the method's fitness boost far outweighs its performance costs.

The primary aim of automated performance improvement is to reduce the running time of programs while maintaining (or improving on) functionality. In this paper, Genetic Programming is used to find performance improvements in regular expressions for an array of target programs, representing the first application of automated software improvement for run-time performance in the Regular Expression language. This particular problem is interesting as there may be many possible alternative regular expressions which perform the same task while exhibiting subtle differences in performance. A benchmark suite of candidate regular expressions is proposed for improvement. We show that the application of Genetic Programming techniques can result in performance improvements in all cases.

Genetic Algorithms (GAs) have been shown to be a very effective optimisation tool on a wide variety of problems. However, they are not without their drawbacks. GAs require time to run, and evolve a bespoke solution to the desired problem in real time. This requirement can prove to be prohibitive in a high-frequency dynamic environment where on-line training time is limited. Neural Networks (NNs) on the other hand can be trained at length off-line, before being deployed on-line, allowing for fast generation of solutions on demand. This study presents a hybrid approach to time-frame scheduling in a high frequency domain. A GA approach is used to generate a dataset of optimised human-competitive solutions. Deep Learning is then deployed to extract the underlying model within the GA, enabling fast optimisation on unseen data. This hybrid approach allows for NNs to generate GA-quality schedules on-line, almost 100 times faster than running the GA.

Computer games are highly dynamic environments, where players are faced with a multitude of potentially unseen scenarios. In this paper, AI controllers are applied to the Mario AI benchmark platform, by using the grammatical evolution system to evolve behavior tree structures. These controllers are either evolved to both deal with navigation and reactiveness to elements of the game or used in conjunction with a dynamic A* approach. The results obtained highlight the applicability of behavior trees as representations for evolutionary computation and their flexibility for incorporation of diverse algorithms to deal with specific aspects of bot control in game environments.

Heterogeneous cellular networks are composed of macro cells (MCs) and small cells (SCs) in which all cells occupy the same bandwidth. Provision has been made under the third generation partnership project-long term evolution framework for enhanced intercell interference coordination (eICIC) between cell tiers. Expanding on previous works, this paper instruments grammatical genetic programming to evolve control heuristics for heterogeneous networks. Three aspects of the eICIC framework are addressed including setting SC powers and selection biases, MC duty cycles, and scheduling of user equipments (UEs) at SCs. The evolved heuristics yield minimum downlink rates three times higher than a baseline method, and twice that of a state-of-the-art benchmark. Furthermore, a greater number of UEs receive transmissions under the proposed scheme than in either the baseline or benchmark cases.

Initialisation in Grammatical Evolution (GE) is a topic that remains open to debate on many fronts. The literature falls between two mainstay approaches: random and sensible initialisation. These methods are not without their drawbacks with the type of trees generated. This paper tackles this problem by extending these traditional operators to incorporate position independence in the initialisation process in GE. This new approach to initialisation is shown to provide a viable alternative to the commonly used approaches, whilst avoiding the common pitfalls of traditional approaches to initialisation.

We explore the application of grammar-based Genetic Programming, specifically Grammatical Evolution, to the problem of modeling the outcome of Six Nations Rugby matches. A series of grammars are developed in attempts to generate different forms of predictive rules, which might be useful in pre-match and mid-match scenarios. A number of interesting models are generated and their utility discussed.

Network operators are struggling to cope with exponentially increasing demand. Capacity can be increased by densifying existing Macro Cell deployments with Small Cells. The resulting two-tiered architecture is known as a Heterogeneous Network or 'HetNet'. Significant inter-tier interference in channel sharing HetNets is managed by resource interleaving in the time domain. A key task in this regard is scheduling User Equipment to receive data at Small Cells. Grammar-based Genetic Programming (GBGP) is employed to evolve models that map measurement reports to schedules on a millisecond timescale. Two different fitness functions based on evaluative and instructive feedback are compared. The former expresses an industry standard utility of downlink rates. Instructive feedback is obtained by computing highly optimised schedules offline using a Genetic Algorithm, which then act as target semantics for evolving models. This paper also compares two schemes for mapping the GBGP parse trees to Boolean schedules. Simulations show that the proposed system outperforms a state of the art benchmark and is within 17% of the estimated theoretical optimum. The impressive performance of GBGP illustrates an opportunity for the further use of evolutionary techniques in software-defined wireless communications networks.

The majority of existing discrete truss optimization methods focus primarily on optimizing global truss topology using a ground structure approach, in which all possible node and beam locations are specifieda priori. The ground structure discrete optimization method has been shown to be restrictive as it limits derivable solutions to what is explicitly defined. Greater representational freedom can improve performance. In this paper, grammatical evolution is applied. It can represent a variable number of nodes and their locations on a continuum. A novel method of connecting evolved nodes using a Delaunay triangulation algorithm shows that fully triangulated, kinematically stable structures can be generated. Discrete beam-truss structures can be optimized without the need for any information about the desired form of the solution other than the design envelope. Our technique is compared to existing discrete optimization techniques, and notable savings in structure self-weight are demonstrated. In particular, our new method can produce results superior to those reported in the literature in cases in which the problem is ill-defined and the structure of the solution is not knowna priori.

A training protocol for learning deep neural networks, called greedy layer-wise training, is applied to the evolution of a hierarchical, feed-forward Genetic Programming based system for feature construction and object recognition. Results on a popular handwritten digit recognition benchmark clearly demonstrate that two layers of feature transformations improves generalisation compared to a single layer. In addition, we show that the proposed system outperforms several standard Genetic Programming systems, which are based on hand-designed features, and use different program representations and fitness functions.

Grammatical Evolution (GE) is applied to the problem of load balancing in heterogeneous cellular network deployments (HetNets). HetNets are multi-tiered cellular networks for which load balancing is a scalable means to maximise network capacity, assuming similar traffic from all users. This paper describes a proof of concept study in which GE is used in a genetic algorithm-like way to evolve constants which represent cell power and selection bias in order to achieve load balancing in HetNets. A fitness metric is derived to achieve load balancing both locally in sectors and globally across tiers. Initial results show promise for GE as a heuristic for load balancing. This finding motivates a more sophisticated grammar to bring enhanced Inter-Cell Interference Coordination optimisation into an evolutionary framework.

We present a novel method of creating piano melodies with Grammatical Evolution (GE). The system employs a context free grammar in combination with a tonality-driven fitness function to create a population of piano melodies. The grammar is designed to create a variety of styles of musical events within each melody such as runs, arpeggios, turns and chords without any a priori musical information in regards to key or time signature. The fitness of the individuals is calculated as a measure of their tonality defined by a statistical distribution of the pitches in each piece. A number of short compositions are presented demonstrating that our system is capable of creating music that is interesting and unpredictable.

The field of Genetic Programming has recently seen a surge of attention to the fact that benchmarking and comparison of approaches is often done in non-standard ways, using poorly designed comparison problems. We raise some issues concerning the design of benchmarks, within the domain of symbolic regression, through experimental evidence. A set of guidelines is provided, aiming towards careful definition and use of artificial functions as symbolic regression benchmarks.

Effective hedging of derivative securities is of paramount importance to derivatives investors and to market makers. The standard approach used to hedge derivative instruments is delta hedging. In a Black-Scholes setting, a continuously rebalanced delta hedged portfolio will result in a perfect hedge with no associated hedging error. In reality, continuous rehedging is impossible and this raises the important practical question such as when should a portfolio manager rebalance the portfolio? In practice, many portfolio managers employ relatively simple deterministic rebalancing strategies, such as rebalancing at uniform time intervals, or rehedging when the underlying asset moves by a fixed number of ticks. While such strategies are easy to implement they will expose the portfolio to hedging risk, both in terms of timing and also as the strategies do not adequately consider market conditions. In this study we propose a rebalancing trigger based on the output from a GP-evolved hedging strategy that rebalances the portfolio based on dynamic nonlinear factors related to the condition of the market, derived from the theoretical literature, including a number of liquidity and volatility factors. The developed GP-evolved hedging strategy outperforms the deterministic time based hedging methods when tested on FTSE 100 call options. This paper represents the first such application of GP for this important application.

Forecasting daily returns volatility is crucial in finance. Traditionally, volatility is modelled using a time-series of lagged information only, an approach which is in essence a theoretical. Although the relationship of market conditions and volatility has been studied for decades, we still lack a clear theoretical framework to allow us to forecast volatility, despite having many plausible explanatory variables. This setting of a data-rich but theory-poor environment suggests a useful role for powerful model induction methodologies such as Genetic Programming. This study forecasts one-day ahead realised volatility (RV) using a GP methodology that incorporates information on market conditions including trading volume, number of transactions, bid-ask spread, average trading duration and implied volatility. The forecasting result from GP is found to be significantly better than that of the benchmark model from the traditional finance literature, the heterogeneous autoregressive model (HAR).

This paper considers the general problem of function estimation via Genetic Programming (GP). Data analysts typically select a model from a population of models, and then proceed as if the selected model had generated the data. This approach ignores the uncertainty in model selection, leading to over-confident inferences and lack of generalisation. We adopt a coherent method for accounting for this uncertainty through a weighted averaging of all models competing in a population of GP. It is a principled statistical method for postprocessing a population of programs into an ensemble, which is based on Bayesian Model Averaging (BMA). Under two different formulations of BMA, the predictive probability density function (PDF) of a response variable is a weighted average of PDFs centered around the individual predictions of component models that take the form of either standalone programs or ensembles of programs. The weights are equal to the posterior probabilities of the models generating the predictions, and reflect the models' skill on the training dataset. The method was applied to a number of synthetic symbolic regression problems, and results demonstrate that it generalises better than standard methods for model selection, as well as methods for ensemble construction in GP.

An Artificial Genetic Regulatory Network (GRN) is a model of the gene expression regulation mechanism in biological organisms. It is a dynamical system that is capable of mimicking non-linear time series. The GRN was adapted to allow for input and output so that the system's rich dynamics could be used for dynamic problem solving. In order for the GRN to be embedded in the environment, the time scale of the physical system has to be mapped to that of the GRN and so a synchronisation process was introduced. This work examines the impact of different synchronisation intervals and how they effect the overall performance of the GRN. A variable synchronisation step that stops once the system has stabilised is also explored as a mechanism for automatically choosing the interval size.

Accurate, real time, continuous ocean wave height measurements are required for the initialisation of ocean wave forecast models, model hindcasting, and climate studies. These measurements are usually obtained using in situ ocean buoys or by satellite altimetry, but are sometimes incomplete due to instrument failure or routine network upgrades. In such situations, a reliable gap filling technique is desirable to provide a continuous and accurate ocean wave field record. Recorded on a land based seismic network are continuous seismic signals known as microseisms. These microseisms are generated by the interactions of ocean waves and will be used in the estimation of ocean wave heights. Grammatical Evolution is applied in this study to generate symbolic models that best estimate ocean wave height from terrestrial seismic data, and the best model is validated against an Artificial Neural Network. Both models are tested over a five month period of 2013, and an analysis of the results obtained indicates that the approach is robust and that it is possible to estimate ocean wave heights from land based seismic data.

We present the results of a series of investigations where we apply a form of grammar-based genetic programming to the problem of program synthesis in an attempt to evolve an Integer Sorting algorithm. The results confirm earlier research in the field on the difficulty of the problem given a primitive set of functions and terminals. The inclusion of a swap(i, j) function in combination with a nested for loop in the grammar enabled a successful solution to be found in every run. We suggest some future research directions to overcome the challenge of evolving sorting algorithms from primitive functions and terminals.

The concept of semantics (in the sense of input-output behavior of solutions on training data) has been the subject of a noteworthy interest in the genetic programming (GP) research community over the past few years. In this paper, we present a new GP system that uses the concept of semantics to improve search effectiveness. It maintains a distribution of different semantic behaviors and biases the search toward solutions that have similar semantics to the best solutions that have been found so far. We present experimental evidence of the fact that the new semantics-based GP system outperforms the standard GP and the well-known bacterial GP on a set of test functions, showing particularly interesting results for noncontinuous (i.e., generally harder to optimize) test functions. We also observe that the solutions generated by the proposed GP system often have a larger size than the ones returned by standard GP and bacterial GP and contain an elevated number of introns, i.e., parts of code that do not have any effect on the semantics. Nevertheless, we show that the deletion of introns during the evolution does not affect the performance of the proposed method.

Although significant attention is given to the study of intellectual property rights (IPR) in economic and other literatures our understanding of the impact of these rights on the process of technological advance is surprisingly incomplete. In this paper we focus on one form of IPR, namely patents. An important and open question faced by policy-makers is what form of patent regime will encourage the fastest rate of technological progress in a society. It is difficult to address this question using historical empirical data as the legal, cultural and technological environments (to name but a few of the factors which could impact on the effect of a given patent regime) do not remain constant over time. Consequently, in this study we novelly employ an agent-based methodology in order to isolate and examine the rate of technological advance that different patent regimes produce. The simulation results indicate that, perhaps counter intuitively, patent policy may not in fact be an effective means of driving societal technological advance.

This paper explores the issues with mapping termination in Grammatical Evolution, and examines approaches that can be used to minimise them. It analyses the traditional approach of reusing the same genetic material, known as wrapping, and shows why this is inefficient with some grammars used in the literature. It suggests the appending of non-coding genetic material to genotype strings, at the start of the run, and shows the benefits of this approach: higher probability of creating terminated individuals, better or similar experimental performance, and a tendency to generate smaller solutions, when compared to the use of wrapping.

Modularity has been an important vein of research in evolutionary algorithms. Past research in evolutionary computation has shown that techniques able to decompose the benchmark problems examined in this work into smaller, more easily solved, sub-problems have an advantage over those which do not. This work describes and analyzes a number of approaches to discover sub-solutions (modules) in the grammatical evolution algorithm. Data from the experiments carried out show that particular approaches to identifying modules are better suited to certain problem types, at varying levels of difficulty. The results presented here show that some of these approaches are able to significantly outperform standard grammatical evolution and grammatical evolution using automatically defined functions on a subset of the problems tested. The results also point to a number of possibilities for extending this work to further enhance approaches to modularity.

The lack of study of genetic programming in dynamic environments is recognised as a known issue in the field of genetic programming. This study compares the performance of two forms of genetic programming, grammatical evolution and a variation of grammatical evolution which uses tree-adjunct grammars, on a series of dynamic problems. Mean best fitness plots for the two representations are analysed and compared.

This paper examines how the semantic locality of a search operator affects the fitness landscape of Genetic Programming (GP). We compare the fitness landscapes of GP search when standard subtree mutation and arecently proposed semantic-based mutation, Semantic Similarity-based Mutation (SSM), are used. The comparison is based on two well-studied fitness landscape measures, namely, the autocorrelation function and information content. The experiments were conducted on a family of symbolic regression problems with increasing degrees of difficulty. The results show that SSM helps to significantly smooth out the fitness landscape of GP compared to standard subtree mutation. This gives an explanation for the better performance of SSM over standard subtree mutation operator.

Modularity has proven to be an important aspect of evolutionary computation. This work is concerned with discovering and using modules in one form of grammar-based genetic programming, grammatical evolution (GE). Previous work has shown that simply adding modules to GE's grammar has the potential to disrupt fit individuals developed by evolution up to that point. This paper presents a solution to prevent the disturbance in fitness that can come with modifying GE's grammar with previously discovered modules. The results show an increase in performance from a previously examined grammar modification approach and also an increase in performance when compared to standard GE.

Designing a suitable objective function is an essential step in successfully applying an evolutionary algorithm to a problem. In this study we apply a grammar-based Genetic Programming algorithm called Grammatical Evolution to the problem of trading model induction. A number of experiments were performed to assess the effect of objective function design on the trading characteristics of the evolved trading strategies. Empirical results suggest that the choice of objective function has a significant impact. The paper concludes with in and out-of-sample results, and indicates a number of avenues of future work.

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.

Trade execution is concerned with the actual mechanics of buying or selling the desired amount of a financial instrument of interest. A practical problem in trade execution is how to trade a large order as efficiently as possible. A trade execution strategy is designed for this task to minimize total trade cost. Grammatical Evolution (GE) is an evolutionary automatic programming methodology which can be used to evolve rule sets. It has been proved successfully to be able to evolve quality trade execution strategies in our previous work. In this paper, the previous work is extended by adopting two different limit order lifetimes and three benchmark limit order strategies. GE is used to evolve efficient limit order strategies which can determine the aggressiveness levels of limit orders. We found that GE evolved limit order strategies were highly competitive against three benchmark strategies and the limit order strategies with long-term lifetime performed better than those with short-term lifetime.

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 Grammatical Evolution (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 three 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.

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.

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.

The use of higher-order functions, as a method of abstraction and re-use in EC encodings, has been the subject of relatively little research. In this paper we introduce and give motivation for the ideas of higher-order functions, and describe their general advantages in EC encodings. We implement grammars using higher-order ideas for two problem domains, music and 3D architectural design, and use these grammars in the grammatical evolution paradigm. We demonstrate four advantages of higher-order functions (patterning of phenotypes, non-entropic mutations, compression of genotypes, and natural expression of artistic knowledge) which lead to beneficial results on our problems.

Interactive interpolating crossover allows a user to quickly see a large number of individuals formed by interactively-controlled interpolation between two or more parents. We study it here for the first time in the context of grammatical evolution (GE). We define methods of quantifying the behaviour of interpolations and use them to compare two methods of performing interpolation and two encodings for GE, one standard and one new. We conclude that a Cartesian interpolation combined with a novel developmental-style GE encoding gives the most usable results. We make connections between our work and broader issues of genotype-phenotype mappings, landscapes, and operators.

A significant problem in the area of stock selection is that of identifying the factors that affect a security's return. While modern portfolio theory suggests a linear multi-factor model in the form of Arbitrage Pricing Theory it does not suggest the identity, or even the number, of risk factors in the model. Candidate factors for inclusion in a fundamental model can include hundreds of data points for each firm and with thousands of firms in the fund manager's selection universe the model specification problem encompasses a large, computationally intense search space. Grammatical Evolution (GE) is a form of evolutionary computing that has been used successfully in model induction problems involving large search spaces. GE is applied to evolve a stock selection model with a customized mapping process developed specifically to enhance the performance of evolutionary operators for this problem. Stock selection models are rated using fitness functions commonly employed in asset management; the information coefficient and the inter-quantile return spread. The findings of the paper indicate that evolutionary computing is an excellent tool for the development of stock picking models.

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 on 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).

This work furthers the understanding of modularity in grammar-based genetic programming approaches by analyzing how different grammars may be capable of producing the same phenotypes, but still display differences in performance on the same problems. This is done by creating four grammars with varying levels of modularity and using them with grammatical evolution to evolve floor plan designs. The results of this experimentation show how increases in modularity, brought about by simple modifications in the grammars, and increases in the quality of solutions go hand in hand. It also demonstrates how more modular grammars explore more individuals even while fitness remains the same or changes in only minor increments.

This paper presents two methods for self-adapting the semantic sensitivities in a recently proposed semantics-based crossover: Semantic Similarity based Crossover (SSC). The first self-adaptation method is inspired by a self-adaptive method for controlling mutation step size in Evolutionary Strategies (1/5 rule). The design of the second takes into account more of our previous experimental observations, that SSC works well only when a certain portion of events successfully exchange semantically similar subtrees. These two proposed methods are then tested on a number of real-valued symbolic regression problems, their performance being compared with SSC using predetermined sensitivities and with standard crossover. The results confirm the benefits of the second self-adaption method.

Locality - how well neighbouring genotypes correspond to neighbouring phenotypes - has been defined as a key element affecting how Evolutionary Computation systems explore and exploit the search space. Locality has been studied empirically using the typical Genetic Algorithm (GA) representation (i.e., bitstrings), and it has been argued that locality plays an important role in EC performance. To our knowledge, there are few explicit studies of locality using the typical Genetic Programming (GP) representation (i.e., tree-like structures). The aim of this paper is to address this important research gap. We extend the genotype-phenotype definition of locality to GP by studying the relationship between genotypes and fitness. We consider a mutation-based GP system applied to two problems which are highly difficult to solve by GP (a multimodal deceptive landscape and a highly neutral landscape). To analyse in detail the locality in these instances, we adopt three popular mutation operators. We analyse the operators' genotypic step sizes in terms of three distance measures taken from the specialised literature and in terms of corresponding fitness values. We also analyse the frequencies of different sizes of fitness change.

This paper investigates the role of semantic diversity and locality of crossover operators in. Genetic Programming (GP) for Boolean problems. We propose methods for measuring and storing semantics of subtrees in Boolean domains using Trace Semantics, and design several new crossovers on this basis. They can be categorised into two classes depending on their purposes: promoting semantic diversity or improving semantic locality. We test the operators on several well-known Boolean problems, comparing them with Standard GP Crossovers and with the Semantic Driven Crossover of Beadle and Johnson. The experimental results show the positive effects both of promoting semantic diversity, and of improving semantic locality, in crossover operators. They also show that the latter has a greater positive effect on GP performance than the former.

Perhaps the biggest limitation of interactive EC is the fitness evaluation bottleneck, caused by slow user evaluation and leading to small populations and user fatigue. In this study these problems are addressed through the proposal of new user interface techniques for interactive EC, which allow faster evaluation of large numbers of individuals and the combination of interactive with noninteractive evaluation. For the first time in the interactive EC literature a set of rigorous usability experiments compares these techniques with existing interactive EC and non-EC interfaces, for the application domain of sound synthesis. The results show that a new user interface for interactive EC improves performance, and further experiments lead to refinement of its design. The experimental protocol shows, again for the first time, that formal usability experiments are useful in the interactive EC setting. Statistically significant results are obtained on clearly-defined performance metrics, and the protocol is general enough to be of potential interest to all interactive EC researchers.

This paper studies the difference between Persistent Random Constants (PRC) and digit concatenation as methods for generating constants. It has been shown that certain problems have different fitness landscapes depending on how they are represented, independent of changes to the combinatorial search space, thus changing problem difficulty. In this case we show that the method for generating the constants can also influence how hard the problem is for genetic programming.

This study focuses on mutation in Grammatical Evolution and divides mutation events into those that are structural in nature and those that are nodal. A structural event being one that alters the length of the phenotype. A nodal event simply alters the value at any node of a derivation tree. We analyse and compare the effect of integer, nodal and structural mutations on fitness for randomly generated individuals before continuing this analysis to their relative problem-solving performance over full runs. The study highlights the importance of understanding how the search operators of an evolutionary algorithm behave. The result in this case being a form of mutation for Grammatical Evolution, node mutation, with a better property of locality than standard integer-based mutation, which does not discriminate between structural and nodal contexts.

We describe the first steps in the adoption of Shape Grammars with Grammatical Evolution for application in Evolutionary Design. Combining the concepts of Shape Grammars and Genetic Programming opens up the exciting possibility of truly generative design assist tools. In this initial study we provide some background on the adoption of grammar-based Genetic Programming for Evolutionary Design, describe Shape Grammars, and give a brief overview of Grammatical Evolution before detailing how Grammatical Evolution used Shape Grammars to successfully rediscover some benchmark target structures.

Following earlier claims that Quantum-inspired Evolutionary Algorithm (QIEA) may offer advantages in high dimensional environments, this paper tests a real-valued QIEA on a series of benchmark functions of varying dimensionality in order to examine its scalability. The results are compared with those from a genetic algorithm using both a binary and real-valued representation. The results show that the QIEA obtains highly competitive results versus the genetic algorithm, while substantially outperforming both versions of the Genetic Algorithm (GA) in terms of running time. This suggests that QIEA may have substantial utility for real-world high dimensional problems.

This paper describes and tests the utility of a meta grammar approach to grammatical evolution (GE). Rather than employing a fixed grammar as is the case with canonical GE, under a meta grammar approach the grammar that is used to specify the construction of a syntactically correct solution is itself allowed to evolve. The ability to evolve a grammar in the context of GE means that useful bias towards specific structures and solutions can be evolved and directly incorporated into the grammar during a run. This approach facilitates the evolution of modularity and reuse both on structural and symbol levels and consequently could enhance both the scalability of GE and its adaptive potential in dynamic environments. In this paper an analysis of the extent that building block structures created in the grammars are used in the solution is undertaken. It is demonstrated that building block structures are incorporated into the evolving grammars and solutions at a rate higher than would be expected by random search. Furthermore, the results indicate that grammar design can be an important factor in performance.

This paper applies a self-organizing particle swarm algorithm, SOSwarm, for the purposes of credit-risk assessment. SoSwarm can be applied for unsupervised clustering and for classification. In the algorithm, input vectors are projected into a lower dimensional map space producing a visual representation of the input data in a manner similar to a self-organizing map (SOM). However, unlike SOM, the nodes (particles) in this map react to input data during the learning process by modifying their velocities using an adaptation of the particle swarm optimization velocity update step. The utility of SoSwarm is tested by applying it to two important credit-risk assessment problems drawn from the domain of finance, namely the prediction of corporate bond ratings and the prediction of corporate failure. The results obtained on the financial benchmark problems are highly-competitive against those of traditional classification methodologies. The paper makes a further contribution showing that the canonical SOM can be explored within the PSO paradigm. This highlights an important linkage between the heretofore distinct literatures of SOM and PSO.

We present an application of grammatical evolution to the exploration of Lindenmayer systems. The resulting L-systems are expressed in the postscript language, and as such a postscript grammar was provided as input to the grammatical evolution algorithm. The system takes the form of an interactive evolutionary algorithm, with a human-in-the-loop acting as the fitness function for the generated L-systems. The motivation for this research was to evolve a logo for the UCD Natural Computing Research & Applications group, and to this end the study was a success.

We investigate the usefulness of a subtree deactivation control mechanism which is open to evolutionary learning. It is hypothesised that this representation confers an adaptive advantage in dynamic environments over the standard sub-tree representation adopted in Genetic Programming. Results presented on benchmark dynamic problem instances provides evidence to support that such an adaptive advantage exists.

Particle swarm has proven to be competitive to other evolutionary algorithms in the field of optimization, and in many cases enables a faster convergence to the ideal solution. However, like any optimization algorithm it seems to have difficulties handling optimization problems of high dimension. Here we first show that dimensionality is really a problem for the classical particle swarm algorithms. We then show that increasing the swarm size can be necessary to handle problem of high dimensions but is not enough. We also show that the issue of scalability occurs more quickly on some functions.

Quantum effects are a natural phenomenon and just like evolution, or immune processes, can serve as an inspiration for the design of computing algorithms. This study illustrates how a real-valued quantum-inspired evolutionary algorithm(QEA) can be constructed and examines the utility of the resulting algorithm on an important real-world problem, namely the calibration of an Option Pricing model. The results from the algorithm are shown to be robust and sensitivity analysis is carried out on the algorithm parameters, suggesting that there is useful potential to apply QEA to this domain.

When dealing with complex optimisations problems, evolutionary computation techniques have proven to be very helpful. Amongst optimisation algorithms driven by evolutionary computation techniques, particle swarm algorithms have proven to be a very good alternative to genetic algorithms because of their faster convergence. However they can still suffer from premature convergence to local optima. Premature convergence occurs when the particles of the swarm are too close to each other to enable further exploration of the space. To put it another way, the dispersion or distribution of the swarm throughout the search space has been localised to a small region with a consequent stagnation of the search process. Many strategies have been used to try to prevent convergence to a local optimum. However little work

This study reports on the performance of an on-line evolutionary automatic programming methodology for uncovering technical trading rules for the S&P 500 and Nikkei 225 indices. The system adopts a variable sized investment strategy based on the strength of the signals produced by the trading rules. Two approaches are explored, one using a single population of rules which is adapted over the lifetime of the data and another whereby a new population is created for each step across the time series. The results show profitable performance for the trading periods explored with clear advantages for an adaptive population of rules.

We present a novel self-organizing Particle Swarm algorithm, SOSwarm, that adopts unsupervised learning. Input vectors are projected onto a lower dimensional map space producing a visual representation of the input data in a manner similar to the Self-Organizing Map (SOM) artificial neural network. Particles in the map react to the input data by modifying their velocities using a standard Particle Swarm Optimization update function, and therefore organize themselves spatially within fixed neighborhoods in response to the input training vectors. SOSwarm is successfully applied to four benchmark classification problems from the UCI Machine Learning repository with the novel SOSwarm algorithm outperforming or equaling the best reported results on all four of the problems analyzed.

A number of natural anticipatory systems employ dual processes of feature definition and feature exploitation. We present a coevolutionary dual process model based on the immune system and consider the effect of coevolving complementary templates to bias feature selection and recombination. This work considers the issue of module exploitation in evolutionary algorithms. Our approach is characterized by the use of rich representations in grammatical evolution.

This study describes a novel simulation model of the process of product invention (InventSim). Invention is conceptualized as search on a landscape of product design possibilities, by a population of profit-seeking agents (inventors). The search process embeds both social and individual learning and is modelled using a memetic-type algorithm. The algorithm includes the search heuristics of thought experiments and election. This study examines the impact of these heuristics on the rate of invention in a society where inventors' estimates of the expected fitness (payoffs) of proposed inventions are noisy. The simulation results indicate that the heuristics are crucial in driving forward the inventive process even when payoff expectations are noisy.

This study describes a novel simulation model of the process of product invention. Invention is conceptualized as a process of directed evolutionary adaptation, on a landscape of product design possibilities, by a population of profit-seeking agents (inventors). The simulation experiments examine the sensitivity of the rate of advance in product fitness to the choice of search heuristics employed by inventors. The key finding of the experiments is that if search heuristics are confined to those which are rooted in past experience, or to heuristics which merely generate variety, limited product advance occurs. Notable product fitness advance only occurs when inventor's expectations as to the relative fitness of potential product inventions are incorporated into the model of invention. The results demonstrate the importance of human direction and expectations in invention. They also support the importance of formal product / project evaluation procedures in organizations, and the importance of market information when inventing new products.

This study examines the utility of meta-grammar constant generation on a series of benchmark problems. The performance of the meta-grammar approach is compared to a grammar which incorporates grammatical ephemeral random constants, digit concatenation, and an expression based approach. It is found that the meta-grammar approach to constant creation is particularly beneficial on the dynamic problem instances in terms of the best fitness values achieved.

The key task of corporate strategists is to uncover and implement viable strategies for their organization. This is a difficult task for several reasons, including uncertainty as to future payoffs, and strategic inertia. This study, using a swarm metaphor, constructs a simulation model to examine the impact of strategic inertia on the adaptation of the strategic fitness of a population of organizations. The results suggest that a degree of strategic inertia, in the presence of an election operator, can assist rather than hamper adaptive efforts of organizations in static and slowly changing environments.

This case study examines the application of grammatical swarm to classification problems, and illustrates the particle swarm algorithms' ability to specify the construction of programs. Each individual particle represents choices of program construction rules, where these rules are specified using a Backus-Naur Form grammar. Two problem instances are tackled, the first a mushroom classification problem, the second a bioinformatics problem that involves the detection of eukaryotic DNA promoter sequences. For the first problem we generate solutions that take the form of conditional statements in a C-like language subset, and for the second problem we generate simple regular expressions. The results demonstrate that it is simple regular expressions. The results demonstrate that it is possible to generate programs using the grammatical swarm technique with a performance similar to the grammatical evolution evolutionary automatic programming approach.

We present grammatical evolution, an evolutionary algorithm that can evolve complete programs in an arbitrary language using a variable-length binary string. The binary genome determines which production rules in a Backus-Naur form grammar definition are used in a genotype-to-phenotype mapping process to a program. We demonstrate how expressions and programs of arbitrary complexity may be evolved and compare its performance to genetic programming.