List of Conference Contributions

Wolfgang Banzhaf


Older papers (from 1993 back) are represented by abstracts only and are available upon email request
We give titles and links. If you click the underlined words in a title you will see an abstract and source information of the paper. If you click the corresponding filename you will retieve a copy.



List of Abstracts and Sources

TITLE: Relieving Coefficient Learning in Genetic Programming for Symbolic Regression via Correlation and Linear Scaling

AUTHORS: Q. Chen, B. Xue, M. Zhang and W. Banzhaf

SOURCE: Proc. of the Genetic and Evolutionary Computation Conference - GECCO 2023, ( Sara Silva and Luis Paquete et al. (Eds.), ACM Press, New York, pp. 420 - 428

ABSTRACT: The difficulty of learning optimal coefficients in regression models using only genetic operators has long been a challenge in genetic programming for symbolic regression. As a simple but effective remedy it has been proposed to perform linear scaling of model outputs prior to a fitness evaluation. Recently, the use of a correla- tion coefficient-based fitness function with a post-processing linear scaling step for model alignment has been shown to outperform error-based fitness functions in generating symbolic regression models. In this study, we compare the impact of four evaluation strategies on relieving genetic programming (GP) from learning coefficients in symbolic regression and focusing on learning the more crucial model structure. The results from 12 datasets, includ- ing ten real-world tasks and two synthetic datasets, confirm that all these strategies assist GP to varying degrees in learning coefficients. Among the them, correlation fitness with one-time linear scaling as post-processing, due to be the most efficient while bringing notable benefits to the performance, is the recommended strategy to relieve GP from learning coefficients.

FILENAME: Qi_GECCO2023.pdf (1,100 kB)




TITLE: A Double Lexicase Selection Operator for Bloat Control in Evolutionary Feature Construction for Regression

AUTHORS: Hengzhe Zhang, Qi Chen, Bing Xue, Wolfgang Banzhaf, and Mengjie Zhang

SOURCE: Proc. of the Genetic and Evolutionary Computation Conference - GECCO 2023, ( Sara Silva and Luis Paquete et al. (Eds.), ACM Press, New York, pp. 1194 - 1202

ABSTRACT: Evolutionary feature construction is an important technique in the machine learning domain for enhancing learning performance. However, traditional genetic programming-based feature construc- tion methods often suffer from bloat, which means the sizes of constructed features increase excessively without improved perfor- mance. To address this issue, this paper proposes a double-stage lexicase selection operator to control bloat while not damaging search effectiveness. This new operator contains a two-stage se- lection process, where the first stage selects individuals based on fitness values and the second stage selects individuals based on tree sizes. Therefore, the proposed operator can control bloat mean- while leveraging the advantage of the lexicase selection operator. Experimental results on 98 regression datasets show that compared to the traditional bloat control method of having a depth limit, the proposed selection operator not only significantly reduces the sizes of constructed features on all datasets but also keeps a similar level of predictive performance. A comparative experiment with seven bloat control methods shows that the double lexicase selection op- erator achieves the best trade-off between the model performance and the model size.

FILENAME: Double_GECCO2023.pdf (1,100 kB)




TITLE: Active Learning Informs Symbolic Regression Model Development in Genetic Programming

AUTHORS: N. Haut, B. Punch and W. Banzhaf

SOURCE: Proc. of the Genetic and Evolutionary Computation Conference Companion - GECCO 2023, ( Sara Silva and Luis Paquete et al. (Eds.), ACM Press, New York, pp. 587 - 591

ABSTRACT: Active learning for genetic programming using model ensemble uncertainty was explored across a range of uncertainty metrics to determine if active learning can be used with GP to minimize training set sizes by selecting maximally informative samples to guide evolution. The choice of uncertainty metric was found to have a significant impact on the success of active learning to inform model development in genetic programming. Differential evolution was found to be an effective optimizer, likely due to the non-convex nature of the uncertainty space, while differential entropy was found to be an effective uncertainty metric. Uncertainty-based ac- tive learning was compared to two random sampling methods and the results show that active learning successfully identified infor- mative samples and can be used with GP to reduce required training set sizes to arrive at a solution.

FILENAME: Haut_GECCO2023.pdf (829 kB)




TITLE: MOAZ: A Multi-Objective AutoML-Zero Framework

AUTHORS: R. Guha, A. Wei, S. Kelly, V. Boddeti, E. Goodman and W. Banzhaf

SOURCE: Proc. of the Genetic and Evolutionary Computation Conference - GECCO 2023, ( Sara Silva and Luis Paquete et al. (Eds.), ACM Press, New York, pp. 485 - 492

ABSTRACT: Automated machine learning (AutoML) greatly eases human efforts in architecture engineering. However, mainstream AutoML meth- ods like neural architecture search (NAS) are customized for well- designed search spaces wherein promising architectures are densely distributed. In contrast, AutoML-Zero builds machine-learning al- gorithms using basic primitives and can explore novel architectures beyond human knowledge. AutoML-Zero shows the potential to deploy machine learning systems by not taking advantage of ei- ther feature engineering or architectural engineering. In its current form, it only optimizes a single objective like accuracy and has no mechanism to ensure that the constraints of real-world applica- tions are satisfied. We propose a multi-objective variant of AutoML- Zero called MOAZ, that distributes solutions on a Pareto front by trading off accuracy against the computational complexity of the machine learning algorithm. In addition to generating different Pareto-optimal solutions, MOAZ can effectively explore the sparse search space to improve search efficiency. Experimental results on linear regression tasks show MOAZ reduces the median complexity by 87.4% compared to AutoML-Zero while accelerating the median target performance achievement speed by 82%. In addition, our pre- liminary results on non-linear regression tasks show the potential for further improvements in search accuracy and for reducing the need for human intervention in AutoML.

FILENAME: Guha_GECCO2023.pdf (740 kB)




TITLE: MAP-Elites with Cosine-Similarity for Evolutionary Ensemble Learning

AUTHORS: H. Zhang, Q. Chen, A. Tonda, B. Xue, W. Banzhaf and M. Zhang

SOURCE: Proc. European Conference on Genetic Programming (EuroGP-2023), Brno, Cech Republic, G. Pappa, M. Giacobini and Z. Vasicek (Eds.), Springer, LNCS Vol 13986, 2023, pp. 84 - 100

ABSTRACT: Evolutionary ensemble learning methods with Genetic Programming have achieved remarkable results on regression and classification tasks by employing quality-diversity optimization techniques like MAP-Elites and Neuro-MAP-Elites. The MAP-Elites algorithm uses dimensionality reduction methods, such as variational auto-encoders, to reduce the high-dimensional semantic space of genetic programming to a two-dimensional behavioral space. Then, it constructs a grid of high-quality and diverse models to form an ensemble model. In MAP-Elites, however, variational auto-encoders rely on Euclidean space topology, which is not effective at preserving high-quality individuals. To solve this problem, this paper proposes a principal component analysis method based on a cosine-kernel for dimensionality reduction. In order to deal with unbalanced distributions of good individuals, we propose a zero-cost reference points synthesizing method. Experimental results on 108 datasets show that combining principal component analysis using a cosine kernel with reference points significantly improves the performance of the MAP-Elites evolutionary ensemble learning algorithm.

FILENAME: Cosine_EuroGP2023.pdf (1,600 kB)




TITLE: Phenotype Search Trajectory Networks for Linear Genetic Programming

AUTHORS: T. Hu, G. Ochoa and W. Banzhaf

SOURCE: Proc. European Conference on Genetic Programming (EuroGP-2023), Brno, Cech Republic, G. Pappa, M. Giacobini and Z. Vasicek (Eds.), Springer, LNCS Vol 13986, 2023, pp. 52 - 67

ABSTRACT: In this study, we visualise the search trajectories of a genetic programming system as graph-based models, where nodes are genotypes/phenotypes and edges represent their mutational transitions. We also quantitatively measure the characteristics of phenotypes including their genotypic abundance (the requirement for neutrality) and Kolmogorov complexity. We connect these quantified metrics with search trajectory visualisations, and find that more complex phenotypes are under-represented by fewer genotypes and are harder for evolution to discover. Less complex phenotypes, on the other hand, are over-represented by genotypes, are easier to find, and frequently serve as stepping-stones for evolution.

FILENAME: STN_EuroGP2023.pdf (2,900 kB)




TITLE: Spatial Genetic Programming

AUTHORS: I. Miralavy and W. Banzhaf

SOURCE: Proc. European Conference on Genetic Programming (EuroGP-2023), Brno, Cech Republic, G. Pappa, M. Giacobini and Z. Vasicek (Eds.), Springer, LNCS Vol 13986, 2023, pp. 260 - 275

ABSTRACT: An essential characteristic of brains in intelligent organisms is their spatial organization, in which different parts of the brain are responsible for solving different classes of problems. Inspired by this concept, we introduce Spatial Genetic Programming (SGP) - a new GP paradigm in which Linear Genetic Programming (LGP) programs, represented as graph nodes, are spread in a 2D space. Each individual model is represented as a graph and the execution order of these programs is determined by the network of interactions between them. SGP considers space as a first-order effect to optimize which aids with determining the suitable order of execution of LGP programs to solve given problems and causes spatial dynamics to appear in the system. RetCons are internal SGP operators which enhance the evolution of conditional pathways in SGP model structures. To demonstrate the effectiveness of SGP, we have compared its performance and internal dynamics with LGP and TreeGP for a diverse range of problems, most of which require decision making. Our results indicate that SGP, due to its unique spatial organization, outperforms the other methods and solves a wide range of problems. We also carry out an analysis of the spatial properties of SGP individuals.

FILENAME: SGP_EuroGP2023.pdf (1,900 kB)




TITLE: Active Learning Improves Performance on Symbolic Regression Tasks in StackGP

AUTHORS: N. Haut, W. Banzhaf and B. Punch

SOURCE: Proc. of the Genetic and Evolutionary Computation Conference Companion - GECCO 2022, ( J.E. Fielsend and M. Wagner (Eds.), ACM Press, New York, pp. 550 - 553

ABSTRACT: This paper introduces an active learning method for symbolic re- gression using StackGP. The approach begins with a small number of data points for StackGP to model. To improve the model the system incrementally adds the data point characterized by maxi- mizing prediction uncertainty as measured by the model ensemble. Symbolic regression is re-run with the larger data set. This cycle continues until the system satisfies a termination criterion. The Feynman AI benchmark set of equations is used to examine the ability of the method to find appropriate models using as few data points as possible. The approach successfully rediscovered 72 of the 100 Feynman equations without the use of domain expertise or data translation.

FILENAME: StackGP_GECCO2022.pdf (504 kB)




TITLE: Optimizing LLVM Pass Sequences with Shackleton: A Linear Genetic Programming Framework

AUTHORS: H. Peeler, S. Li, A.N. Sloss, K.N. Reid, Y. Yuan and W. Banzhaf

SOURCE: Proc. of the Genetic and Evolutionary Computation Conference Companion - GECCO 2022, ( J.E. Fielsend and M. Wagner (Eds.), ACM Press, New York, pp. 578 - 581

ABSTRACT: In this paper we explore the novel application of a linear genetic programming framework, Shackleton, to optimizing sequences of LLVM optimization passes. The algorithm underpinning Shackleton is discussed, with an emphasis on the effects of different features unique to the framework when applied to LLVM pass sequences. Combined with analysis of different hyperparameter settings, we report the results on automatically optimizing pass sequences with Shackleton for two software applications at differing complexity levels. Finally, we reflect on the advantages and limitations of our current implementation and lay out a path for further improvements. These improvements aim to surpass hand-crafted solutions with an automatic discovery method for an optimal pass sequence.

FILENAME: Shackelton_GECCO2022.pdf (789 kB)




TITLE: NSGANetV2: Evolutionary Multi-Objective Surrogate-Assisted Neural Architecture Search

AUTHORS: Z. Lu, K. Deb, E. Goodman, W. Banzhaf, and V.N. Boddeti

SOURCE: Proc. 16th European Conference on Computer Vision (ECCV-2020), Glasgow, UK, A. Vedaldi, H. Bischof, T. Brox, J.-M. Frahm (Eds.), Springer, LNCS Vol 12346, 2020, pp. 35 - 51

ABSTRACT: In this paper, we propose an efficient NAS algorithm for generating task-specific models that are competitive under multiple competing objectives. It comprises of two surrogates, one at the architecture level to improve sample efficiency and one at the weights level, through a supernet, to improve gradient descent training efficiency. On standard benchmark datasets (C10, C100, ImageNet), the resulting models, dubbed NSGANetV2, either match or outperform models from existing approaches with the search being orders of magnitude more sample efficient. Furthermore, we demonstrate the effectiveness and versatility of the proposed method on six diverse non-standard datasets, e.g. STL-10, Flowers102, Oxford Pets, FGVC Aircrafts etc. In all cases, NSGANetV2s improve the state-of-the-art (under mobile setting), suggesting that NAS can be a viable alternative to conventional transfer learning approaches in handling diverse scenarios such as small-scale or fine-grained datasets. Code is available at https://github.com/mikelzc1990/nsganetv2.

FILENAME: ECCV2020.pdf (2,600 kB)




TITLE: A Modular Memory Framework for Time Series Prediction

AUTHORS: S. Kelly, J. Newsted, W. Banzhaf and C. Gondro

SOURCE: Proc. of the Genetic and Evolutionary Computation - GECCO 2020, Cancun, Mexico, C. Coello Coello and others (Eds.), ACM Press, New York, 2020, pp. 949 - 957

ABSTRACT: Tangled Program Graphs (TPG) is a framework for genetic programming which has shown promise in challenging reinforcement learning problems with discrete action spaces. The approach has recently been extended to incorporate temporal memory mechanisms that enable operation in environments with partial-observability at multiple timescales. Here we propose a highly-modular memory structure that manages temporal properties of a task and enables operation in problems with continuous action spaces. This significantly broadens the scope of real-world applications for TPGs, from continuous-action reinforcement learning to time series forecasting. We begin by testing the new algorithm on a suite of symbolic regression benchmarks. Next, we evaluate the method in 3 challenging time series forecasting problems. Results generally match the quality of state-of-the-art solutions in both domains. In the case of time series prediction, we show that temporal memory eliminates the need to pre-specify a fixed-size sliding window of previous values, or autoregressive state, which is used by all compared methods. This is significant because it implies that no prior model for a time series is necessary, and the forecaster may adapt more easily if the properties of a series change significantly over time.

FILENAME: GECCO-2020.pdf (767 kB)




TITLE: A Study of Severe Disruption in an Artificial Economy

AUTHORS: G. Recio, R. White and W. Banzhaf

SOURCE: Proceedings of the 2020 Artificial Life Conference (ALIFE-2020) , Montreal, Canada, 2020 J. Bongard, J. Lovato, L. Hebert-Dufresne, R. Dasari and L. Soros (Eds.), MIT Press, Cambridge, MA, 2020, pp. 180 - 187

ABSTRACT: We analyze an artificial economy model designed to handle severe non-equilibrium situations. This agent-based model is intended to allow innovation in the form of new technologies, producers and consumers entering (and leaving) the system. Here we examine a disruption of consumption patterns akin to the economic crisis brought about in the real economy through the corona virus and the following Covid-19 pandemic.

FILENAME: ALIFE-2020.pdf (2200 kB)




TITLE: Continuous Long-Term Evolution of Genetic Programming

AUTHORS: W.B. Langdon and W. Banzhaf

SOURCE: Proceedings of ALIFE XVII, 2019, Newcastle, UK, 2019 H. Fellermann, J. Bacardit, A. Goni-Moreno, R.M. Fuechslin (Eds.), MIT Press, Cambridge, MA, 2019, pp. 388 - 395

ABSTRACT: We evolve floating point Sextic polynomial populations of genetic programming binary trees for up to a million generations. Programs with almost 400,000,000 instructions are created by crossover. To support unbounded Long-Term Evolution Experiment LTEE GP we use both SIMD parallel AVX 512 bit instructions and 48 threads to yield performance of up to 149 billion GP operations per second, 149 giga GPops, on a single Intel Xeon Gold 6126 2.60 GHz server.

FILENAME: ALIFE-2019.pdf (668 kB)




TITLE: A Hybrid Evolutionary System for Automatic Software Repair

AUTHORS: Y. Yuan and W. Banzhaf

SOURCE: Proc of the Genetic and Evolutionary Computation - GECCO 2019, Prague, Czech Republic, 2019 A. Auger and T. Stuetzle and others (Eds.), ACM Press, New York, 2019, pp. 1417 - 1427

ABSTRACT: This paper presents an automatic software repair system that combines the characteristic components of several typical evolutionary computation based repair approaches into a unified repair framework so as to take advantage of their respective component strengths. We exploit both the redundancy assumption and repair templates to create a search space of candidate repairs. Then we employ a multi-objective evolutionary algorithm with a lowgranularity patch representation to explore this search space, in order to find simple patches. In order to further reduce the search space and alleviate patch overfitting we introduce replacement similarity and insertion relevance to select more related statements as promising fix ingredients, and we adopt anti-patterns to customize the available operation types for each likely-buggy statement. We evaluate our system on 224 real bugs from the Defects4J dataset in comparison with the state-of-the-art repair approaches. The evaluation results show that the proposed system can fix 111 out of those 224 bugs in terms of passing all test cases, achieving substantial performance improvements over the state-of-the-art. Additionally, we demonstrate the ability of ARJA-e to fix multi-location bugs that are unlikely to be addressed by most of existing repair approaches.

FILENAME: GECCO-2019_Automatic.pdf (919 kB)




TITLE: Batch Tournament Selection for Genetic Programming

AUTHORS: V.V. Melo, D.V. Vargas and W. Banzhaf

SOURCE: Proc of the Genetic and Evolutionary Computation - GECCO 2019, Prague, Czech Republic, 2019 A. Auger and T. Stuetzle and others (Eds.), ACM Press, New York, 2019, pp. 994 - 1002

ABSTRACT: Lexicase selection achieves very good solution quality by introducing ordered test cases. However, the computational complexity of lexicase selection can prohibit its use in many applications. In this paper, we introduce Batch Tournament Selection (BTS), a hybrid of tournament and lexicase selection which is approximately one order of magnitude faster than lexicase selection while achieving a competitive quality of solutions. Tests on a number of regression datasets show that BTS compares well with lexicase selection in terms of mean absolute error while having a speed-up of up to 25 times. Surprisingly, BTS and lexicase selection have almost no difference in both diversity and performance. This reveals that batches and ordered test cases are completely different mechanisms which share the same general principle fostering the specialization of individuals. This work introduces an efficient algorithm that sheds light onto the main principles behind the success of lexicase, potentially opening up a new range of possibilities for algorithms to come.

FILENAME: GECCO-2019_Batch.pdf (982 kB)




TITLE: Complex Network Analysis of a Genetic Programming Phenotype Network

AUTHORS: T. Hu, M. Tomassini and W. Banzhaf

SOURCE: Genetic Programming - Proceedings EuroGP 2019, Leipzig, Germany, 2019 L. Sekanina, T. Hu, N. Lourenco, H. Richter, P. Garca-Sanchez (Eds.), Springer, Cham, 2019, pp. 49 - 63

ABSTRACT: The genotype-to-phenotype mapping plays an essential role in the design of an evolutionary algorithm. Since variation occurs at the genotypic level but fitness is evaluated at the phenotypic level, this mapping determines how variations are effectively translated into quality improvements. We numerically study the redundant genotype-to-phenotype mapping of a simple Boolean linear genetic programming system. In particular, we investigate the resulting phenotypic network using tools of complex network analysis. The analysis yields a number of interesting statistics of this network, considered both as a directed as well as an undirected graph. We show by numerical simulation that less redundant phenotypes are more difficult to find as targets of a search than others that have much more genotypic abundance. We connect this observation with the fact that hard to find phenotypes tend to belong to small and almost isolated clusters in the phenotypic network.

FILENAME: EuroGP-2019.pdf (539 kB)




TITLE: NSGA-Net: Neural Architecture Search using Multi-Objective Genetic Algorithm

AUTHORS: Z. Lu, I. Whalen, V. Bodetti, Y. Dhebar, K. Deb, E. Goodman and W. Banzhaf

SOURCE: Proc of the Genetic and Evolutionary Computation - GECCO 2019, Prague, Czech Republic, 2019 A. Auger and T. Stuetzle and others (Eds.), ACM Press, New York, 2019, pp. 419 - 427

ABSTRACT: This paper introduces NSGA-Net Ğ an evolutionary approach forneural architecture search (NAS). NSGA-Net is designed with three goals in mind: (1) a procedure considering multiple and conflicting objectives, (2) an efficient procedure balancing exploration and exploitation of the space of potential neural network architectures, and (3) a procedure finding a diverse set of trade-off network architectures achieved in a single run. NSGA-Net is a population-based search algorithm that explores a space of potential neural network architectures in three steps, namely, a population initialization step that is based on prior-knowledge from hand-crafted architectures, an exploration step comprising crossover and mutation of architectures, and finally an exploitation step that utilizes the hidden useful knowledge stored in the entire history of evaluated neural architectures in the form of a Bayesian Network. Experimental results suggest that combining the dual objectives of minimizing an error metric and computational complexity, as measured by FLOPs, al-lows NSGA-Net to find competitive neural architectures. Moreover, NSGA-Net achieves error rate on the CIFAR-10 dataset on par with other state-of-the-art NAS methods while using orders of magnitude less computational resources. These results are encouraging and show the promise to further use of EC methods in various deep-learning paradigms.

FILENAME: GECCO-2019_NSGANet.pdf (855 kB)




TITLE: Learning an evolvable genotype-phenotype mapping

AUTHORS: M. Moreno, W. Banzhaf and C. Ofria

SOURCE: Proc of the Genetic and Evolutionary Computation - GECCO 2018, Kyoto, Japan, 2018 H. Aguirre, K. Takamada and others (Eds.), ACM Press, New York, 2018, pp. 983 - 990

ABSTRACT: We present AutoMap, a pair of methods for automatic generation of evolvable genotype-phenotype mappings. Both use an artificial neural network autoencoder trained on phenotypes harvested from fitness peaks as the basis for a genotype-phenotype mapping. In the first, the decoder segment of a bottlenecked autoencoder serves as the genotype-phenotype mapping. In the second, a denoising autoencoder serves as the genotype-phenotype mapping. Automatic generation of evolvable genotype-phenotype mappings are demonstrated on the n-legged table problem, a toy problem that defines a simple rugged fitness landscape, and the Scrabble string problem, a more complicated problem that serves as a rough model for linear genetic programming. For both problems, the automatically generated genotype-phenotype mappings are found to enhance evolvability.

FILENAME: GECCO-2018_Automap.pdf (1600 kB)




TITLE: Evolution of Cooperation through Genetic Collective Learning and Imitation in Multiagent Societies

AUTHORS: H. Bao, Q. Wuyun and W. Banzhaf

SOURCE: Proceedings of ALIFE XVI, 2018, Tokyo, Japan, 2018 T. Ikegami, N. Virgo, O. Witkowski, M. Oka, R. Suzuki, H. Iizuka (Eds.), MIT Press, Cambridge, MA, 2018, pp. 133 - 148

ABSTRACT: How to facilitate the evolution of cooperation is a key question in multi-agent systems and game-theoretical situations. Individual reinforcement learners often fail to learn coordinated behavior. Using an evolutionary approach for selection can produce optimal behavior but may require significant computational efforts. Social imitation of behavior causes weak coordination in a society. Our goal in this paper is to improve the behavior of agents with reduced computational effort by combining evolutionary techniques, collective learning, and social imitation techniques. We designed a genetic algorithm based cooperation framework equipped with these techniques in order to solve particular coordination games in complex multi-agent networks. In this framework, offspring agents inherit more successful behavior selected from gameplaying parent agents, and all agents in the network improve their performance through collective reinforcement learning and social imitation. Experiments are carried out to test the proposed framework and compare the performance with previous work. Experimental results show that the framework is more effective for the evolution of cooperation in complex multi-agent social systems than either evolutionary, reinforcement learning or imitation system on their own.

FILENAME: ALIFE-2018_Cooperation.pdf (1100 kB)




TITLE: Evolving Adaptive Traffic Signal Controllers for a Real Scenario Using Genetic Programming with an Epigenetic Mechanism

AUTHORS: E. Ricalde and W. Banzhaf

SOURCE: Proc. of the 16th IEEE International Conference on Machine Learning and Applications (ICMLA-2017), 2017 IEEE Press, New York, 2017, pp. 897 - 902

ABSTRACT: An important challenge for traffic signal control is adapting to irregular changes in traffic. In recent years, different heuristics have been developed to address this issue. However, most of them are tested in artificial scenarios under controlled circumstances. In this paper, we present the first implementation of Genetic Programming in the evolution of traffic signal controllers for a real-world scenario. The evolved controllers are compared with a static control and an actuated control. The results indicate a significant improvement over traditional methods. Moreover, additional experiments indicate that the evolved controllers have the ability to adapt to unplanned changes in traffic conditions.

FILENAME: ICMLA-2017_Traffic.pdf (223 kB)




TITLE: A hybrid genetic programming decision making system for RoboCup soccer simulation

AUTHORS: A. Tafavi and W. Banzhaf

SOURCE: Proc of the Genetic and Evolutionary Computation - GECCO 2017, Berlin, Germany (Eds.), ACM Press, New York, 2017, pp. 1025 - 1032

ABSTRACT: In this contribution we propose a hybrid genetic programming approach for evolving a decision making system in the domain of RoboCup Soccer (Simulation League). Genetic programming has been rarely used in this domain in the past, due to the difficulties and restrictions of the soccer simulation. The real-time requirements of robot soccer and the lengthy evaluation time even for simulated games provide a formidable obstacle to the application of evolutionary approaches. Our new method uses two evolutionary phases, each of which compensating for restrictions and limitations of the other. The first phase produces some evolved GP individuals applying an off-game evaluation system which can be trained on snapshots of game situations as they actually happened in earlier games, and corresponding decisions tagged as correct or wrong. The second phase uses the best individuals of the first phase as input to run another GP system to evolve players in a real game environment where the quality of decisions is evaluated through winning or losing during real-time runs of the simulator. We benchmark the new system against a baseline system used by most simulation league teams, as well as against winning systems of the 2016 tournament.

FILENAME: GECCO-20017_RoboCup.pdf (2300 kB)




TITLE: Quantitative Analysis of Evolvability using Vertex Centralities in Phenotype Network

AUTHORS: T. Hu and W. Banzhaf

SOURCE: Proc of the Genetic and Evolutionary Computation - GECCO 2016, Denver, CO, USA, T. Friedrich, F. Neumann and others (Eds.), ACM Press, New York, 2016, pp. 733 - 740

ABSTRACT: In an evolutionary system, robustness describes the resilience to mutational and environmental changes, whereas evolvability captures the capability of generating novel and adaptive phenotypes. The research literature has not seen an effective quantification of phenotypic evolvability able to predict the evolutionary potential of the search for novel phenotypes. In this study, we propose to characterize the mutational potential among different phenotypes using the phenotype network, where vertices are phenotypes and edges represent mutational connections between them. In the framework of such a network, we quantitatively analyze the evolvability of phenotypes by exploring a number of vertex centrality measures commonly used in complex networks. In our simulation studies we use a Linear Genetic Programming system and a population of random walkers. Our results suggest that the weighted eigenvector centrality serves as the best estimator of phenotypic evolvability.

FILENAME: GECCO-2016_Robustness.pdf (968 kB)




TITLE: Human recognition through walking styles by multiwavelet transform

AUTHORS: F.M. Kazemi, W. Banzhaf and M. Gong

SOURCE: Proc 8th International Conference on Information and Knowledge Technology (IKT-2016), IEEE Press, New York, 2016, pp. 47 - 53

ABSTRACT: Human recognition through walking styles is among the newest of biometric methods. By using this biometric, individuals can be identified, distantly, even at low visibility. Our aim is to provide such ability for a computer system. In other words, we intend to extract appropriate features through processing video images that can reflect individuals' identity. In order to set up such a system, we have used Fourier, Wavelet, and Multi-wavelet transforms. Using images from the USF dataset version 1.7, the results obtained indicate that SA4 Multi-wavelet transforms prove more efficient in extracting suitable features than Fourier and wavelet transforms, and combined with one-versus-one Support Vector Machine, they can provide a 85.7 % recognition accuracy rate. Our proposed method shows higher accuracy and precision compared to other frequency based methods.

FILENAME: IKT-2016.pdf (324 kB)




TITLE:Artificial Multi-Bee-Colony Algorithm for k-Nearest-Neighbor Fields Search

AUTHORS: Y. Wang, Y. Qian, Y. Li, M. Gong and W. Banzhaf

SOURCE: Proc of the Genetic and Evolutionary Computation - GECCO 2016, Denver, CO, USA, T. Friedrich, F. Neumann and others (Eds.), ACM Press, New York, 2016, pp. 1037 - 1044

ABSTRACT: Searching the k-nearest matching patches for each patch in an input image, i.e., computing the k-nearest-neighbor fields ($k$-NNF), is a core part of various computer vision/graphics algorithms. In this paper, we show that $k$-NNF can be efficiently computed using a novel artificial multi-bee-colony (AMBC) algorithm, where each patch uses a dedicated bee colony to search for its k-nearest matches. As a population-based algorithm, AMBC is capable of escaping local optima. The added communication among different colonies further allows good matches to be quickly propagated across the image. In addition, AMBC makes no assumption about the neighborhood structure or communication direction, making it directly applicable to image sets and suitable for parallel processing. Quantitative evaluations show that AMBC can find solutions that are much closer to the ground truth than the generalized PatchMatch algorithm does. It also outperforms the PatchMatch Graph over image sets.

FILENAME: GECCO-2016_AMBC.pdf (4200 kB)




TITLE:Improving Logistic Regression Classification of Credit Approval with Features Constructed by Kaizen Programming

AUTHORS: V. Veloso de Melo and W. Banzhaf

SOURCE: Genetic and Evolutionary Computation - GECCO 2016, Companion Volume, Denver, CO, USA, T. Friedrich, F. Neumann and others (Eds.), ACM Press, New York, 2016, pp. 61 - 62

ABSTRACT: In this contribution, we employ the recently proposed Kaizen Programming (KP) approach to find high-quality nonlinear combinations of the original features in a dataset. KP constructs many complementary features at the same time, which are selected by their importance, not by model quality. We investigated our approach in a well-known realworld credit scoring dataset. When compared to related approaches, KP reaches similar or better results, but evaluates fewer models.

FILENAME: GECCO2016_Companion_Kaizen_CreditApproval.pdf (795 kB)




TITLE: A Genetic Programming Approach for the Traffic Signal Control Problem with Epigenetic Modifications

AUTHORS: E. Ricalde and W. Banzhaf

SOURCE: Genetic Programming - Proc. of EuroGP 2016, Porto, Portugal, 2016 M.I. Heywood, J. McDermott, M. Castelli, E. Costa, and K. Sim (Eds.), Springer, Berlin, 2016, pp. 133 - 148

ABSTRACT: This paper presents a proof-of-concept for an Epigeneticsbased modification of Genetic Programming (GP). The modification is tested with a traffic signal control problem under dynamic traffic conditions. We describe the new algorithm and show first results. Experiments reveal that GP benefits from properties such as phenotype differentiation, memory consolidation within generations and environmentally-induced change in behavior provided by the epigenetic mechanism. The method can be extended to other dynamic environments.

FILENAME: EuroGP2016_Epigenetic.pdf (383 kB)




TITLE: Modelling Evolvability in Genetic Programming

AUTHORS: B. Fowler and W. Banzhaf

SOURCE: Genetic Programming - Proc. of EuroGP 2016, Porto, Portugal, 2016 M.I. Heywood, J. McDermott, M. Castelli, E. Costa, and K. Sim (Eds.), Springer, Berlin, 2016, pp. 215 - 229

ABSTRACT: We develop a tree-based genetic programming system capable of modelling evolvability during evolution through machine learning algorithms, and exploiting those models to increase the efficiency and final fitness. Existing methods of determining evolvability require too much computational time to be effective in any practical sense. By being able to model evolvability instead, computational time may be reduced. This will be done first by demonstrating the effectiveness of modelling these properties a priori, before expanding the system to show its effectiveness as evolution occurs.

FILENAME: EuroGP2016_Evolvability.pdf (846 kB)




TITLE: Quantitative Analysis of Evolvability using Vertex Centralities in Phenotype Network

AUTHORS: T. Hu and W. Banzhaf

SOURCE: Proc. of the Genetic and Evolutionary Computation - GECCO 2016, Denver, CO, USA, T. Friedrich, F. Neumann et al. (Eds.) ACM Press, New York, 2016, pp. 733 - 740

ABSTRACT: In an evolutionary system, robustness describes the resilience to mutational and environmental changes, whereas evolvability captures the capability of generating novel and adaptive phenotypes. The research literature has not seen an effective quantification of phenotypic evolvability able to predict the evolutionary potential of the search for novel phenotypes. In this study, we propose to characterize the mutational potential among different phenotypes using the phenotype network, where vertices are phenotypes and edges represent mutational connections between them. In the framework of such a network, we quantitatively analyze the evolvability of phenotypes by exploring a number of vertex centrality measures commonly used in complex networks. In our simulation studies we use a Linear Genetic Programming system and a population of random walkers. Our results suggest that the weighted eigenvector centrality serves as the best estimator of phenotypic evolvability.

FILENAME: GECCO2016_Quantitative.pdf (968 kB)




TITLE: Artificial Multi-Bee-Colony Algorithm for k-Nearest-Neighbor Fields Search

AUTHORS: Y. Wang, Y. Qian, Y. Li, M. Gong and W. Banzhaf

SOURCE: Proc. of the Genetic and Evolutionary Computation - GECCO 2016, Denver, CO, USA, T. Friedrich, F. Neumann et al. (Eds.) ACM Press, New York, 2016, pp. 1037 - 1044

ABSTRACT: Searching the k-nearest matching patches for each patch in an input image, i.e., computing the k-nearest-neighbor fields (k-NNF), is a core part of various computer vision/graphics algorithms. In this paper, we show that k-NNF can be efficiently computed using a novel artificial multi-bee-colony (AMBC) algorithm, where each patch uses a dedicated bee colony to search for its k-nearest matches. As a population-based algorithm, AMBC is capable of escaping local optima. The added communication among different colonies further allows good matches to be quickly propagated across the image. In addition, AMBC makes no assumption about the neighborhood structure or communication direction, making it directly applicable to image sets and suitable for parallel processing. Quantitative evaluations show that AMBC can find solutions that are much closer to the ground truth than the generalized PatchMatch algorithm does. It also outperforms the PatchMatch Graph over image sets.

FILENAME: GECCO2016_ABC.pdf (4.2 MB)




TITLE: Machiavellian Agents: Player Modelling to Deceive and be Deceived

AUTHORS: S. Watson, A. Vardy, W. Banzhaf and T. Wareham

SOURCE: Computer Games: AI, Animation, Mobile, Multimedia, Educational and Serious Games (CGAMES 2015), IEEE Press, New York, 2015, pp. 10 - 17

ABSTRACT: This paper explores several augmentations to the previously described Plantagenet model of computer game agents to give agents the deceptic capability to deceive the player and/or be deceived by the player. Augmented finite state machine controllers for agents in a simple role playing game are generated using an evolutionary algorithm. It is demonstrated that the proposed model is a practical option for generating populations of around 30 agents in which constraints on agent behaviour to ensure that actions are consistent with deception can be satisfied in substantial portions of the agent population.

FILENAME: CGAMES2015.pdf (687 kB)




TITLE: Predicting high-performance concrete compressive strength using features constructed by Kaizen Programming

AUTHORS: V.V. de Melo and W. Banzhaf

SOURCE: Proc. Brazilian Conference on Intelligent Systems (BRACIS 2015), IEEE Press, New York, 2015, pp. 80 - 85

ABSTRACT: The compressive strength of high-performance concrete (HPC) can be predicted by a nonlinear function of the proportions of its components. However, HPC is a complex material, and finding that nonlinear function is not trivial. Many distinct techniques such as traditional statistical regression methods and machine learning methods have been used to solve this task, reaching considerably different levels of accuracy. In this paper, we employ the recently proposed Kaizen Programming coupled with classical Ordinary Least Squares (OLS) regression to find high-quality nonlinear combinations of the original features, resulting in new sets of features. Those new features are then tested with various regression techniques to perform prediction. Experimental results show that the features constructed by our technique provide significantly better results than the original ones. Moreover, when compared to similar evolutionary approaches, Kaizen Programming builds only a small fraction of the number of prediction models, but reaches similar or better results.

FILENAME: BRACIS2015_Concrete.pdf (207 kB)




TITLE: Evaluating Methods for Constant Optimization of Symbolic Regression Benchmark Problems

AUTHORS: V.V. de Melo, W. Banzhaf and B. Fowler

SOURCE: Proc. Brazilian Conference on Intelligent Systems (BRACIS 2015), IEEE Press, New York, 2015, pp. 25 - 30

ABSTRACT: Constant optimization in symbolic regression is an important task addressed by several researchers. It has been demonstrated that continuous optimization techniques are adequate to find good values for the constants by minimizing the prediction error. In this paper, we evaluate several continuous optimization methods that can be used to perform constant optimization in symbolic regression. We have selected 14 well-known benchmark problems and tested the performance of diverse optimization methods in finding the expected constant values, assuming that the correct formula has been found. The results show that Levenberg-Marquardt presented the highest success rate among the evaluated methods, followed by Powell's and Nelder-Mead's Simplex. However, two benchmark problems were not solved, and for two other problems the Levenberg-Marquardt was largely outperformed by Nelder-Mead Simplex in terms of success rate. We conclude that even though a symbolic regression technique may find the correct formula, constant optimization may fail, thus, this may also happen during the search for a formula and may guide the method towards the wrong solution. Also, the efficiency of LM in finding high-quality solutions by using only a few function evaluations could serve as inspiration for the development of better symbolic regression methods.

FILENAME: BRACIS2015_Symbolic.pdf (1.1 MB)




TITLE: Human Recognition through Walking Styles by Multiwavelet Transform

AUTHORS: F.M. Kazemi, W. Banzhaf, M. Gong

SOURCE: Proc. 8th International Conference on Information and Knowledge Technology (IKT-2016), Hamedan, Iran IEEE Press, New York, 2016, pp. 47 - 53

ABSTRACT: Human recognition through walking styles is among the newest of biometric methods. By using this biometric, individuals can be identified, distantly, even at low visibility. Our aim is to provide such ability for a computer system. In other words, we intend to extract appropriate features through processing video images that can reflect individuals' identity. In order to set up such a system, we have used Fourier, Wavelet, and Multi-wavelet transforms. Using images from the USF dataset version 1.7, the results obtained indicate that SA4 Multiwavelet transforms prove more efficient in extracting suitable features than Fourier and wavelet transforms, and combined with one-versus-one Support Vector Machine, they can provide a 85.7 % recognition accuracy rate. Our proposed method shows higher accuracy and precision compared to other frequency based methods.

FILENAME: Gait_IEEE2016.pdf (320 kB)




TITLE: Population Exploration on Genotype Networks in Genetic Programming

AUTHORS: T. Hu, W. Banzhaf and J.H. Moore

SOURCE: Proc. of the 13th International Conference on Parallel Problem Solving from Nature (PPSN-XIII), Ljubljana, Slovakia, Springer, Switzerland, 2014, pp. 424 - 433

ABSTRACT: Redundant genotype-to-phenotype mappings are pervasive in evolutionary computation. Such redundancy allows populations to ex- pand in neutral genotypic regions where mutations to a genotype do not alter the phenotypic outcome. Genotype networks have been proposed as a useful framework to characterize the distribution of neutrality among genotypes and phenotypes. In this study, we examine a simple Genetic Programming model that has a finite and compact genotype space by characterizing its genotype networks. We study the topology of indi- vidual genotype networks underlying unique phenotypes, investigate the genotypic properties as vertices in genotype networks, and discuss the correlation of these network properties with robustness and evolvability. Using GP simulations of a population, we demonstrate how an evolu- tionary population diffuses on genotype networks.

FILENAME: PPSN2014.pdf (485 kB)




TITLE: Automated Design for Playability in Computer Game Agents

AUTHORS: S. Watson, W. Banzhaf and A. Vardy

SOURCE: Proc. of the IEEE Computational Intelligence in Games Conference (CIG 2014), Dortmund, Germany, IEEE Press, New York, 2014, pp. 1 - 8 (electronic proceedings)

ABSTRACT: This paper explores whether a novel approach to the creation of agent controllers has potential to overcome some of the drawbacks that have prevented novel controller architectures from being widely implemented. This is done by using an evolutionary algorithm to generate finite state machine controllers for agents in a simple role playing game. The concept of minimally playable games is introduced to serve as the basis of a method of evaluating the fitness of a gameÕs agent controllers.

FILENAME: CIG2014.pdf (348 kB)




TITLE: Parallel Exhaustive Search vs. Evolutionary Computation in a Large Real World Network Search Space

AUTHORS: G. Wilson, S. Harding, O. Hoeber, R. Devillers, and W. Banzhaf

SOURCE: Proc. Congress on Evolutionary Computation (CEC 2012), June 10-15, 2012, Brisbane, Australia, IEEE Press, New York, 2012, pp. 816 - 823

ABSTRACT: This work examines a novel method that provides a parallel search of a very large network space consisting of fisheries management data. The parallel search solution is capable of determining global maxima of the search space using exhaustive search, compared to local optima located by machine learning solutions such as evolutionary computation. The actual solutions from the best machine learning technique, called Probabilistic Adaptive Mapping Developmental Genetic Algorithm, are compared by a fisheries expert to the global max- ima solutions returned by parallel search. The time required for parallel search, for both CPU and GPU-based solutions, are compared to those required for machine learning solutions. The GPU parallel computing solution was found to have a speedup of 12x over a multi-threaded CPU solution. An expert found that overall the machine learning solutions produced more interesting results by locating local optima than global optima determined by parallel processing.

FILENAME: RealWorldNetworkSpace_CEC2012.pdf (1700 kB)




TITLE: Supervised Learning in Robotic Swarms: From Training Samples to Emergent Behaviour

AUTHORS: G. Vorobyev, A. Vardy and W. Banzhaf

SOURCE: Proceedings of the Intl. Symposium on Distributed Robotic (DARS-2012), Baltimore, MD, USA, 2012, A. Hsieh et al (Eds.) Springer, New York, 2014, pp. 435 - 448

ABSTRACT: Emergent behavior in swarm robotic systems is key to obtaining com- plex behavior by a group of relatively simple agents. The question is how to design the individual behaviors of agents in such a way that the desired global behavior emerges. Different approaches have been proposed to solve this problem: from biologically inspired probabilistic behavioural models to evolutionary techniques. In some situations, however, creating a complex probabilistic model of the behavior or developing a proper setup for an evolutionary process can be challenging. In this paper we propose a new method, based on supervised learning on a relatively small number of training samples. We apply our method to the well-known clustering problem and show that this approach yields the desired global clustering behavior.

FILENAME: Vorobyev_DARS.pdf (516 kB)




TITLE: Achieving desirable gameplay objectives by niched evolution of game parameters

AUTHORS: S. Watson, A. Vardy and W. Banzhaf

SOURCE: Proceedings of the 2012 IEEE Intl. Games Innovation Conference,Rochester, NY, USA, 2012, IEEE Press, New York, 2012

ABSTRACT: Setting parameters for video games is important and often difficult. Poor choices can lead to games being too easy or too difficult, too short or too long, too linear or too open-ended. In many cases there is no alternative to making value judgments on what these parameter values should be. This paper explores whether evolutionary computation can be successfully applied to finding values that facilitate desired gameplay objectives in a Tower Defense game. Initial experiments suggest that a two-tier evolutionary method can create strategies to successfully play such games and configurations of game parameters that facilitate gameplay objectives desired by the developer.

FILENAME: IGIC_2012.pdf (76 kB)




TITLE: Conformity and Nonconformity in Collective Robotics: A Case Study

AUTHORS: G. Vorobyev, A. Vardy and W. Banzhaf

SOURCE: Proceedings ECAL 2013, Taormina, Italy, 2013, P. Lio, O. Miglino, G. Nicosia, S. Nolfi and M. Pavone(Eds.), MIT Press, Cambridge, 2013, pp. 981 - 988

ABSTRACT: In this work, we develop a social behavioral model designed for multi-agent systems for solving the collective sorting task. Experiments show that under this model agents are capable of improving their performance significantly and can achieve better results than conventional swarms of agents lacking communication and social abilities.

FILENAME: ecal_2013.pdf (658 kB)




TITLE: Robustness and Evolvability of Recombination in Linear Genetic Programming

AUTHORS: T. Hu, W. Banzhaf and J.H. Moore

SOURCE: Proceedings EuroGP 2013, Vienna, Austria, 2013, K. Krawiec, A. Moraglio, T. Hu, A.S. Etaner-Uyar, B. Hu (Eds.), Springer, Berlin, 2013, pp. 97 - 108

ABSTRACT: The effect of neutrality on evolutionary search is known to be crucially dependent on the distribution of genotypes over phenotypes. Quantitatively characterizing robustness and evolvability in genotype and phenotype spaces greatly helps to understand the influence of neutrality on Genetic Programming. Most existing robustness and evolvability studies focus on mutations with a lack of investigation of recombinational operations. Here, we extend a previously proposed quantitative approach of measuring mutational robustness and evolvability in Linear GP. By considering a simple LGP system that has a compact representation and enumerable genotype and phenotype spaces, we quantitatively characterize the robustness and evolvability of recombination at the phenotypic level. In this simple yet representative LGP system, we show that recombinational properties are correlated with mutational properties. Utilizing a population evolution experiment, we demonstrate that recombination significantly accelerates the evolutionary search process and particularly promotes robust phenotypes that innovative phenotypic explorations.

FILENAME: eurogp_2013.pdf (269 kB)




TITLE: Networks of Transform-Based Evolvable Features for Object Recognition

AUTHORS: T. Kowaliw, W. Banzhaf and R. Doursat

SOURCE: Proc of the Genetic and Evolutionary Computation - GECCO-2013, Amsterdam, The Netherlands, 2013, C. Blum and E. Alba et al. (Eds.), ACM Press, New York, 2013, pp. 1077 - 1084

ABSTRACT: We propose an evolutionary feature creator (EFC) to explore a non-linear and offline method for generating features in image recognition tasks. Our model aims at extracting low-level features automatically when provided with an arbitrary image database. In this work, we are concerned with the addition of algorithmic depth to a genetic programming (GP) system, hypothesizing that it will improve the capacity for solving problems that require high-level, hierarchical reasoning. For this we introduce a network superstructure that co-evolves with our low-level GP representations. Two approaches are described: the first uses our previously used ÒshallowÓ GP system, the second presents a new ÒdeepÓ GP system that involves this network superstructure. We evaluate these models against a benchmark object recognition database. Results show that the deep structure outperforms the shallow one in generating features that support classification, and does so without requiring significant additional computational time. Further, high accuracy is achieved on the standard ETH-80 classification task, also outperforming many existing specialized techniques. We conclude that our EFC is capable of data-driven extraction of useful features from an object recognition database.

FILENAME: kbd_gecco2013.pdf (420 kB)




TITLE: The Unconstrained Automated Generation of Cell Image Features for Medical Diagnosis

AUTHORS: T. Kowaliw and W. Banzhaf

SOURCE: Proc of the Genetic and Evolutionary Computation - GECCO-2012, Philadelphia, PA, USA, 2012, T. Soule and J.H. Moore et al. (Eds.), ACM Press, New York, 2012, pp. 1103 - 1110

ABSTRACT: An extension to a non-linear oine method for generating features for image recognition is introduced. It aims at generating low-level features automatically when provided with some arbitrary image database. First, a general representation of prioritized pixel- neighbourhoods is described. Next, genetic programming is used to specify functions on those representations. The result is a set of transformations on the space of grayscale images. These transforms are utilized as a step in a classi cation process, and evolved in an evolutionary algorithm. The technique is shown to match the eciency of the state-of-the-art on a medical image classi- cation task. Further, the approach is shown to self-select an appropriate solution structure and complexity. Finally, we show that competitive co-evolution is a viable means of combating over- tting. It is concluded that the technique generally shows good promise for the creation of novel image features in situations where pixel-level features are complex or unknown, such as medical images.

FILENAME: kowaliw_banzhaf_gecco2012.pdf (236 kB)




TITLE: Using Sector Information with Linear Genetic Programming for Intraday Equity Price Trend Analysis

AUTHORS: G. Wilson, D. Leblanc and W. Banzhaf

SOURCE: Proc. Congress on Evolutionary Computation (CEC 2012), June 10-15, 2012, Brisbane, Australia, IEEE Press, New York, 2012, pp. 2756 - 2763

ABSTRACT: A number of researchers who apply genetic programming (GP) to the analysis of financial data have had success in using predictability pretests to determine whether the time series under analysis by a GP contains patterns that are actually inherently predictable. However, most studies to date apply no such pretests, or pretests of any kind. Most previous work in this area has attempted to use filters to ensure inherent predictability of the data within a window of a time series, whereas other works have used multiple time frame windows under analysis by the GP to provide one overall GP recommendation. This work, for the first time, analyzes the use of external information about the price trend of a stockÕs market sector. This information is used in a filter to bolster confidence of a GP-based alert regarding formation of a trend for the chosen stock. Our results indicate a significant improvement in trend identification for the majority of stocks analyzed using intraday data.

FILENAME: WilsonLeblancBanzhaf2012.pdf (3,600 kB)




TITLE: Robustness, Evolvability, and Accessibility in Linear Genetic Programming

AUTHORS: T. Hu, J.L. Payne, W. Banzhaf and J.H. Moore

SOURCE: Proceedings EuroGP 2011, Torino, Italy, 2011
S. Silva, J.A. Foster, M. Nicolau, P. Machado, M. Giacobini (Eds.), Springer, LNCS 6621, Heidelberg, 2011, pp. 13 - 24

ABSTRACT: Whether neutrality has positive or negative effects on evolutionary search is a contentious topic, with reported experimental results supporting both sides of the debate. Most existing studies use performance statistics, e.g., success rate or search efficiency, to investigate if neutrality, either embedded or artificially added, can benefit an evolutionary algorithm. Here, we argue that understanding the influence of neutrality on evolutionary optimization requires an understanding of the interplay between robustness and evolvability at the genotypic and phenotypic scales. As a concrete example, we consider a simple linear genetic programming system that is amenable to exhaustive enumeration, and allows for the full characterization of these properties. We adopt statistical measurements from RNA systems to quantify robustness and evolvability at both genotypic and phenotypic levels. Using an ensemble of random walks, we demonstrate that the benefit of neutrality crucially depends upon its phenotypic distribution.

FILENAME: EuroGP2011.pdf (328 kB)




TITLE: Rethinking Multilevel Selection in Genetic Programming

AUTHORS: X. Wu and W. Banzhaf

SOURCE: Proc of the Genetic and Evolutionary Computation - GECCO, Dublin, Ireland, 2011
N. Krasnogor et al. (Eds.), ACM Press, New York, 2011, pp. 1403 - 1410

ABSTRACT: This paper aims to improve the capability of genetic programming to tackle the evolution of cooperation: evolving multiple partial solutions that collaboratively solve structurally and functionally complex problems. A multilevel genetic programming approach is presented based on a new computational multilevel selection framework [19]. This approach considers biological group selection theory to encourage cooperation, and a new cooperation operator to build solutions hierarchically. It extends evolution from individuals to multiple group levels, leading to good performance on both individuals and groups. The applicability of this approach is evaluated on 7 multi-class classification problems with different features, such as non-linearity, skewed data distribution and large feature space. The results, when compared to other cooperative evolutionary algorithms in the literature, demonstrate that this approach improves solution accuracy and consistency, and simplifies solution complexity. In addition, the problem is decomposed as a result of evolution without human interference.

FILENAME: GECCO2011-Wu.pdf ( kB)




TITLE: Stock Trading using LGP with Multiple Time Frames

AUTHORS: G. Wilson, D. Leblanc and W. Banzhaf

SOURCE: Proc of the Genetic and Evolutionary Computation - GECCO, Dublin, Ireland, 2011
N. Krasnogor et al. (Eds.), ACM Press, New York, 2011, pp. 1667 - 1677

ABSTRACT: A number of researchers have attempted to take successful GP trading systems and make them even better through the use of filters. We investigate the use of a linear genetic programming (LGP) system that combines GP signals provided over multiple intraday time frames to produce one trading action. Four combinations of time frames stretching further into the past are examined. Two different decision mechanisms for evaluating the overall signal given the GP signals over all time frames are also examined, one based on majority vote and another based on temporal proximity to the buying decision. Results indicated that majority vote outperformed emphasis on proximity of time frames to the current trading decision. Analyses also indicated that longer time frame combinations were more conservative and outperformed shorter combinations for both overall upward and downward price trends.

FILENAME: Stocks-GECCO2011.pdf ( kB)




TITLE: Large Network Analysis for Fisheries Management using Coevolutionary Genetic Algorithms

AUTHORS: G. Wilson, S. Harding, O. Hoeber, R. Deviller and W. Banzhaf

SOURCE: Proc of the Genetic and Evolutionary Computation - GECCO, Dublin, Ireland, 2011
N. Krasnogor et al. (Eds.), ACM Press, New York, 2011, pp. 1619 - 1626

ABSTRACT: Traditionally, a genetic algorithm is used to analyze networks by maximizing the modularity (Q) measure to create a favorable community. A coevolutionary algorithm is used here to not only find the appropriate community division for a network, but to find interesting networks containing substantial changes in data within a very large network space. The network is one of the largest, if not the largest, analyzed by evolutionary computation techniques to date and is created using a real world data set consisting of fisheries catch data in the north Atlantic Ocean off the coast of Canada. This work examines the quantitative performance of two types of coevolutionary algorithms against both a standard GA that uses a natural (but not necessarily optimal) division of the data set into communities, and simulated annealing. The goal for all search algorithms was to automatically find anomalies (differences in catch) within the data. To measure practical usefulness of the system, a fisheries expert analyzed the best networks located by the search algorithms using an existing visualization software prototype. The expert indicated that a refined version of coevolutionary GA known as PAMDGA was found to most reliably locate subnetworks containing catch differences of biological relevance.

FILENAME: Fisheries-GECCO2011.pdf ( kB)




TITLE: SMCGP2: Self Modifying Cartesian Genetic Programming in Two Dimensions

AUTHORS: S. Harding, J. Miller and W. Banzhaf

SOURCE: Proc of the Genetic and Evolutionary Computation - GECCO, Dublin, Ireland, 2011
N. Krasnogor et al. (Eds.), ACM Press, New York, 2011, pp. 1491 - 1498

ABSTRACT: Self Modifying Cartesian Genetic Programming is a general purpose, graph-based, developmental form of Cartesian Genetic Programming. Using a combination of computational functions and special functions that can modify the phenotype at runtime, it has been employed to find general solutions to certain Boolean circuits and mathematical problems. In the present work, a new version, of SMCGP is proposed and demonstrated. Compared to the original SMCGP both the representation and the function set have been simplified. However, the new representation is also two-dimensional and it allows evolution and development to have more ways to solve a given problem. Under most situations we show that the new method makes the evolution of solutions to even parity and binary addition faster than with previous version of SMCGP.

FILENAME: SMCGP2-2011.pdf ( kB)




TITLE: Bondable Cellular Automata

AUTHORS: M. Hatcher, W. Banzhaf and T. Yu

SOURCE: Advances in Artificial Life Proceedings of the 11th European Conference on Artificial Life (ECAL-2011), Paris, France, 2011
T. Lenaerts, M. Giacobini, H. Bersini, P. Bourgine, M. Dorigo, R. Doursat (Eds.), MIT Press, Cambridge, 2011, pp. 326 - 333

ABSTRACT: We present the Bondable Cellular Automata model, which uses simple 1-dimensional, binary cellular automata as the base atomic elements of an artificial chemistry. Reactions are dependent upon an emergent, resolution independent observable, measurable for individual or composite cellular automata structures. We discuss the rationale behind our choice of observable, mean polarity, and behind the choice of a bonding mechanism based on this observable. From simple experimentation we observe that using cellular automata as the underlying dynamical system coupled with mean polarity as the reaction success criterion shows potential to support sustainable emergent behaviour.

FILENAME: bondable2011.pdf (1000 kB)




TITLE: Evolutionary Transition through a New Multilevel Selection Model

AUTHORS: X. Wu and W. Banzhaf

SOURCE: Advances in Artificial Life Proceedings of the 11th European Conference on Artificial Life (ECAL-2011), Paris, France, 2011
T. Lenaerts, M. Giacobini, H. Bersini, P. Bourgine, M. Dorigo, R. Doursat (Eds.), MIT Press, Cambridge, 2011, pp. 874 - 881

ABSTRACT: Most multilevel selection models in the literature focus on addressing the evolution of cooperation. There is, however, another aspect of multilevel selection theory. It might be able to provide explanations for evolutionary transitions, which involve the creation of higher level complexes out of simpler elements. Here, we propose a multilevel selection model to support evolutionary transitions. This model employs a genetic operator called cooperation to build the hierarchical structure used in multilevel selection theory, and applies two types of multilevel selection to achieve transitions. Our experiments on an extended N-player Prisoners Dilemma game demonstrate that groups with all required skills emerge from a population of independent individuals, no matter whether skills are equally rewarded or not. Our experiments confirm that both types of multilevel selection mentioned are relevant to evolutionary transitions.

FILENAME: multilevel2011.pdf (220 kB)




TITLE: Evolving Reaction-Diffusion Systems on GPU

AUTHORS: L. Yamamoto, P. Collet and W. Banzhaf

SOURCE: Progress in Artificial Intelligence, Proc 15th EPIA-2011, Lisbon, Portugal, 2011
L. Antunes and H. Sofia Pinto (Eds.), Springer, LNCS 7026, Heidelberg, 2011, pp. 208 - 223

ABSTRACT: Reaction-diffusion systems contribute to various morphogenetic processes, and can also be used as computation models in real and artificial chemistries. Evolving reaction-diffusion solutions automatically is interesting because it is otherwise difficult to engineer them to achieve a target pattern or to perform a desired task. However most of the existing work focuses on the optimization of parameters of a fixed reaction network. In this paper we extend this state of the art by also exploring the space of alternative reaction networks, with the help of GPU hardware. We compare parameter optimization and reaction network optimization on the evolution of reaction-diffusion solutions leading to simple spot patterns. Our results indicate that these two optimization modes tend to exhibit qualitatively different evolutionary dynamics: in the former, the fitness tends to improve continuously in gentle slopes, while the latter tends to exhibit large periods of stagnation followed by sudden jumps, a sign of punctuated equilibria.

FILENAME: EPIA-2011.pdf (444 kB)




TITLE: WiMAX Network Planning Using Adaptive-Population-Size Genetic Algorithm

AUTHORS: T. Hu, Y.P. Chen and W. Banzhaf

SOURCE: Proc. EvoApplications 2010, Istanbul, Turkey, April 2010
C. Di Chio, A. Brabazon, G. Di Caro, M. Ebner, M. Farooq, A. Fink, J. Grahl, G. GreenŞeld, P. Machado, M. O'Neill, E. Tarantino, N. Urquhart (Eds.), Springer, LNCS 6025, Heidelberg, 2010, pp. 31 - 40

ABSTRACT: IEEE 802.16, also known as WiMAX, is a new wireless access technology for currently increasing demand of wireless high-speed broadband service. Efficient and effective deployment of such a network to service an area of users with certain traffic demands is an important network planning problem. In this article, we resort to a Genetic Algorithm in order to yield good approximation solutions. In our method, individual representation and genetic variation operations are specifically designed to incorporate the feature of this application problem. Moreover, an adaptive population size approach inspired by neutral theory in molecular biology is applied in our algorithm to enhance its search ability. Simulation results show that our algorithm is fairly effective and robust to different scenarios of the network planning problem. By comparing to a conventional fixed population size scheme, our method is further verified to be able to accelerate the search process.

FILENAME: EvoApps2010.pdf (240 kB)




TITLE: Evolving Genes to Balance a Pole

AUTHORS: M. Nicolau, M. Schoenauer and W. Banzhaf

SOURCE: Proc. 13th Europ. Conference on Genetic Programming, Istanbul, Turkey, April 2010
A. Esparcia-Alcazar, A. Ekart, S. Silva, S. Dignum, and A. Sima Uyar (Eds.), Springer, LNCS 6021, Heidelberg, 2010, pp. 196 - 207

ABSTRACT: We discuss how to use a Genetic Regulatory Network as an evolutionary representation to solve a typical GP reinforcement problem, the pole balancing. The network is a modified version of an Artificial Regulatory Network proposed a few years ago, and the task could be solved only by finding a proper way of connecting inputs and outputs to the network. We show that the representation is able to generalize well over the problem domain, and discuss the performance of different models of this kind.

FILENAME: EuroGP2010.pdf (332 kB)




TITLE: Catalytic Search in Dynamic Environments

AUTHORS: L. Yamamoto and W. Banzhaf

SOURCE: Proceedings of ALIFE XII, Odense, Denmark, 2010 S. Maurer, D. Merkle, P. Monnard, K. Stoy and S. Rasmussen (Eds.), MIT Press, Cambridge, 2010, pp. 277 - 284 (electronic publication)

ABSTRACT: Catalytic Search is an optimization algorithm inspired by random catalytic reaction networks and their pre-evolutionary dynamics. It runs within an Artificial Chemistry in which reactions can be reversible, and replication is not taken for granted. In previous work one of us had shown that although inherently slower than Evolutionary Algorithms, Catalytic Search is able to solve simple problems while naturally maintaining diversity in the population. This is a useful property when the environment may change. In this paper, we compare the performance of Catalytic Search and a Genetic Algorithm in a dynamic environment represented by a periodically changing objective function. We investigate the impact of parameters such as temperature, inflow/outflow rate, and amount of catalysts. We show that Catalytic Search is generally more stable in the face of changes, although still slower in achieving the absolute best fitness. Our results also offer some indications on how catalytic search could either degenerate into random search, or progress towards evolutionary search, although the latter transition has not been fully demonstrated yet.

FILENAME: ALIFE2010.pdf (356 kB)




TITLE: Fast and Effective Predictability Filters for Stock Price Series using Linear Genetic Programming

AUTHORS: G. Wilson and W. Banzhaf

SOURCE: IEEE World Congress on Computational Intelligence, July 2010, Barcelona, Spain IEEE Press, New York, 2010, 05586297, pp. 1-8 (electronic publication)

ABSTRACT: A handful of researchers who apply genetic programming (GP) to the analysis of financial markets have devised predictability pretests to determine whether the time series that is being supplied to GP contains patterns that can be predicted, but most studies apply no such pretests. By applying predictability pretests, researchers can have greater confidence that the GP system is solving a problem which is actually there and that it will be less likely to make questionable investment decisions based on non-existent patterns. Previous work in this area has applied regression to randomized versions of time series training data to create a functional model that is applied over a future window of time. This work presents two types of predictability filters with low computational overhead, namely frequency-based and information theoretic, that complement the previous function-based continuous output predictability models. Results indicate that either filter can be beneficial for particular trend types, but the information-based filter involves a greater chance of missing opportunities for profit. In contrast, the frequency-based filter always outperforms, or is competitive with, the filterless implementation.

FILENAME: WCCI2010.pdf (800 kB)




TITLE: A Hierarchical Cooperative Evolutionary Algorithm

AUTHORS: S. Wu and W. Banzhaf

SOURCE: Proc. of the 12th Genetic and Evolutionary Computation Conference (GECCO-10), Portland, OR, 2010 M. Pelikan et al (Eds.), ACM, New York, 2010, pp. 233 - 240 (electronic publication)

ABSTRACT: To successfully search multiple coadaptive subcomponents in a solution, we developed a novel cooperative evolutionary algorithm based on a new computational multilevel selection framework. This algorithm constructs cooperative solutions hierarchically by implementing the idea of group selection. We show that this simple and straightforward algorithm is able to accelerate evolutionary speed and improve solution accuracy on string covering problems as compared to other EAs used in literature. In addition, the structure of the solution and the roles played by each subcomponent in the solution emerge as a result of evolution without human interference.

FILENAME: GECCO2010p233.pdf (693 kB)




TITLE: Self Modifying Cartesian Genetic Programming: Finding Algorithms that Calculate pi and e to Arbitrary Precision

AUTHORS: S. Harding, J. Miller and W. Banzhaf

SOURCE: Proc. of the 12th Genetic and Evolutionary Computation Conference (GECCO-10), Portland, OR, 2010 M. Pelikan et al (Eds.), ACM, New York, 2010, pp. 579 - 586 (electronic publication)

ABSTRACT: Self Modifying Cartesian Genetic Programming (SMCGP) aims to be a general purpose form of developmental genetic programming. The evolved programs are iterated thus allowing an infinite sequence of phenotypes (programs) to be obtained from a single evolved genotype. In previous work this approach has already shown that it is possible to obtain mathematically provable general solutions to certain problems. We extend this class in this paper by showing how SMCGP can be used to find algorithms that converge to mathematical constants (pi and e). Mathematical proofs are given that show that some evolved formulae converge to pi and e in the limit as the number of iterations increase.

FILENAME: GECCO2010p579.pdf (902 kB)




TITLE: Interday Foreign Exchange Trading using Linear Genetic Programming

AUTHORS: G. Wilson and W. Banzhaf

SOURCE: Proc. of the 12th Genetic and Evolutionary Computation Conference (GECCO-10), Portland, OR, 2010 M. Pelikan et al (Eds.), ACM, New York, 2010, pp. 1139 - 1146 (electronic publication)

ABSTRACT: Foreign exchange (forex) market trading using evolutionary algorithms is an active and controversial area of research. We investigate the use of a linear genetic programming (LGP) system for automated forex trading of four major currency pairs. Fitness functions with varying degrees of conservatism through the incorporation of maximum drawdown are considered. The use of the fitness types in the LGP system for different currency value trends are examined in terms of performance over time, underlying trading strategies, and overall profitability. An analysis of trade profitability shows that the LGP system is very accurate at both buying to achieve profit and selling to prevent loss, with moderate levels of trading activity.

FILENAME: GECCO2010p1139.pdf (655 kB)




TITLE: Elongation Control in an Algorithmic Chemistry

AUTHORS: T. Meyer, L. Yamamoto, W. Banzhaf and C. Tschudin

SOURCE: Proceedings of the 10th European Artificial Life Conference, Sept 13-16, 2009, Budapest, Hungary, 2009 Springer Berlin, Lecture Notes in Computer Science, Vol 5777, 2011, pp. 267 - 274 (electronic publication)

ABSTRACT: Algorithmic chemistries intended as computation models seldom model energy. This could partly explain some undesirable phenomena such as unlimited elongation of strings in these chemistries, in contrast to nature where polymerization tends to be unfavored. In this paper, we show that a simple yet suciently accurate energy model can eciently steer resource usage, in particular for the case of elongation control. A string chemistry is constructed on purpose to make strings grow arbitrarily large. Simulation results show that the addition of energy control alone is able to keep the molecules within reasonable length bounds, even without mass conservation, and without explicit length thresholds. A narrow energy range is detected where the system neither stays inert nor grows unbounded. At this operating point, interesting phenomena often emerge, such as clusters of autocatalytic molecules, which seem to cooperate.

FILENAME: MYBT-ECAL2009.pdf (392 kB)




TITLE: Investigations of Wilson's and Traulsen's Group Selection Models in Evolutionary Computation

AUTHORS: S.X. Wu and W. Banzhaf

SOURCE: Proceedings of the 10th European Artificial Life Conference, Sept 13-16, 2009, Budapest, Hungary, 2009 Springer Berlin, Lecture Notes in Computer Science, Vol 5778, 2011, pp. 1 - 9 (electronic publication)

ABSTRACT: Evolving cooperation by evolutionary algorithms is impossible without introducing extra mechanisms. Group selection theory in biology is a good candidate as it explains the evolution of cooperation in nature. Two biological models, Wilson's trait group selection model and Traulsen's group selection model are investigated and compared in evolutionary computation. Three evolutionary algorithms were designed and tested on an n-player prisoner's dilemma problem; two EAs implement the original Wilson and Traulsen models respectively, and one EA extends Traulsen's model. Experimental results show that the latter model introduces high between-group variance, leading to more robustness than the other two in response to parameter changes such as group size, the fraction of cooperators and selection pressure.

FILENAME: wu-banzhaf-ECAL2009.pdf (212 kB)




TITLE: Discovery of Email Communication Networks from the Enron Corpus with a Genetic Algorithm using Social Network Analysis

AUTHORS: G. Wilson and W. Banzhaf

SOURCE: Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2009), May 18-21, 2009, Trondheim, Norway, 2009 IEEE Press, New York, 2009, pp. 3256 - 3263 (electronic publication)

ABSTRACT: During the legal investigation of Enron Corporation, the U.S. Federal Regulatory Commission (FERC) made public a substantial data set of the companyÕs internal corporate emails. This work presents a genetic algorithm (GA) approach to social network analysis (SNA) using the Enron corpus. Three SNA metrics, degree, density, and proximity prestige, were applied to the detection of networks of high activity and presence of important actors with respect to email transactions. Quantitative analysis revealed that density and proximity prestige captured networks of high activity more so than degree. Subsequent qualitative analysis reveals that there are trade-offs in the selection of SNA metrics. Examination of the discovered social networks revealed that density and proximity prestige isolated networks involving key actors to a greater extent than degree. In particular, density picked out interesting patterns in terms of email volume, while proximity prestige better isolated key actors at Enron. The roles of the particular actors picked out by the networks as reasons for their prominence are also discussed.

FILENAME: Enron_CEC2009_IEEE.pdf (612 kB)




TITLE: Evolution, Development and Learning Using Self-Modifying Cartesian Genetic Programming

AUTHORS: S. Harding, J. Miller and W. Banzhaf

SOURCE: Proc. of the 11th Genetic and Evolutionary Computation Conference (GECCO-09), Montreal, CANADA, 2009 F. Rothlauf et al (Eds.), ACM, New York, 2009, pp. 699 - 706 (electronic publication)

ABSTRACT: Self-Modifying Cartesian Genetic Programming (SMCGP) is a form of genetic programming that integrates developmental (self-modifying) features as a genotype-phenotype mapping. This paper asks: Is it possible to evolve a learning algorithm using SMCGP?

FILENAME: gecco09-3.pdf (2,840 kB)




TITLE: Soft Memory for Stock Market Analysis using Linear and Developmental Genetic Programming

AUTHORS: G. Wilson and W. Banzhaf

SOURCE: Proc. of the 11th Genetic and Evolutionary Computation Conference (GECCO-09), Montreal, CANADA, 2009 F. Rothlauf et al (Eds.), ACM, New York, 2009, pp. 1633 - 1640 (electronic publication)

ABSTRACT: Recently, a form of memory usage was introduced for genetic programming (GP) called "soft memory". Rather than have a new value completely overwrite the old value in a register, soft memory combines the new and old register values. This work examines the performance of a soft memory linear GP and developmental GP implementation for stock trading. Soft memory is known to more slowly adapt solutions compared to traditional GP. Thus, it was expected to perform well on stock data which typically exhibit local turbulence in combination with an overall longer term trend. While soft memory and standard memory were both found to provide similar impressive accuracy in buys that produced profit and sells that prevented losses, the softer memory settings traded more actively. The trading of the softer memory systems produced less substantial cumulative gains than traditional memory settings for the stocks tested with climbing share price trends. However, the trading activity of the softer memory settings had moderate benefits in terms of cumulative profit compared to buy-and-hold strategy for share price trends involving a drop in prices followed later by gains.

FILENAME: gecco09-2.pdf (732 kB)




TITLE: Neutrality and Variability: Two sides of Evolvability in Linear Genetic Programming

AUTHORS: T. Hu and W. Banzhaf

SOURCE: Proc. of the 11th Genetic and Evolutionary Computation Conference (GECCO-09), Montreal, CANADA, 2009 F. Rothlauf et al (Eds.), ACM, New York, 2009, pp. 963 - 970 (electronic publication)

ABSTRACT: The notion of evolvability has been put forward to describe the Òcore mechanismÓof natural and artificial evolution. Recently, studies have revealed the influence of the environment upon a systemÕs evolvability. In this contribution, we study the evolvability of a system in various environmental situations. We consider neutrality and variability as two sides of evolvability. The former makes a system tolerant to mutations and provides a hidden staging ground for future phenotypic changes. The latter produces explorative variations yielding phenotypic improvements. Which of the two dominates is influenced by the environment. We adopt two tools for this study of evolvability: i) the rate of adaptive evolution, which captures the observable adaptive variations driven by evolvability; and ii) the variability of individuals, which measures the potential of an individual to vary functionally. We apply these tools to a Linear Genetic Programming system and observe that evolvability is able to exploit its two sides in different environmental situations.

FILENAME: gecco09-1.pdf (674 kB)




TITLE: Prediction of Interday Stock Prices using Developmental and Linear Genetic Programming

AUTHORS: G. Wilson and W. Banzhaf

SOURCE: Proceedings EvoWorkshops 2009, Tuebingen, Germany, April 2009
M. Giacobini, A. Brabazon, S. Cagnoni, G.A. Di Caro, A. Ekart, A. Esparcia-Alczar, M. Farooq, A. Fink, and P. Machado (Eds.) Springer, LNCS 5484, Heidelberg, 2009, pp. 172 - 181

ABSTRACT: A developmental co-evolutionary genetic programming approach (PAM DGP) is compared to a standard linear genetic programming (LGP) implementation for trading of stocks across market sectors. Both implementations were found to be impressively robust to market fluctuations while reacting efficiently to opportunities for profit, where PAM DGP proved slightly more reactive to market changes than LGP. PAM DGP outperformed, or was competitive with, LGP for all stocks tested. Both implementations had very impressive accuracy in choosing both profitable buy trades and sells that prevented losses, where this occurred in the context of moderately active trading for all stocks. The algorithms also appropriately maintained maximal investment in order to profit from sustained market upswings.

FILENAME: evows2009.pdf (443 kB)




TITLE: Self Modifying Cartesian Genetic Programming: Fibonacci, Squares, Regression and Summing

AUTHORS: S. Harding, J. Miller and W. Banzhaf

SOURCE: Proc. 12th Europ. Conference on Genetic Programming, Tuebingen, Germany, April 2009
L. Vanneschi, S. Gustafson, A. Moraglio, I. De Falco, and M. Ebner (Eds.) Springer, LNCS 5481, Heidelberg, 2009, pp. 133 - 144

ABSTRACT: Self Modifying CGP (SMCGP) is a developmental form of Cartesian Genetic Programming(CGP). It is able to modify its own phenotype during execution of the evolved program. This is done by the inclusion of modification operators in the function set. Here we present the use of the technique on several different sequence generation and regression problems.

FILENAME: eurogp2009-smcgp.pdf (220 kB)




TITLE: The Role of Population Size in Rate of Evolution in Genetic Programming

AUTHORS: T. Hu and W. Banzhaf

SOURCE: Proc. 12th Europ. Conference on Genetic Programming, Tuebingen, Germany, April 2009
L. Vanneschi, S. Gustafson, A. Moraglio, I. De Falco, and M. Ebner (Eds.) Springer, LNCS 5481, Heidelberg, 2009, pp. 85 - 96

ABSTRACT: Population size is a critical parameter that affects the performance of an Evolutionary Computation model. A variable population size scheme is considered potentially beneficial to improve the quality of solutions and to accelerate fitness progression. In this contribution, we discuss the relationship between population size and the rate of evolution in Genetic Programming. We distinguish between the rate of fitness progression and the rate of genetic substitutions, which capture two different aspects of a GP evolutionary process. We suggest a new indicator for population size adjustment during an evolutionary process by measuring the rate of genetic substitutions. This provides a separate feedback channel for evolutionary process control, derived from concepts of population genetics. We observe that such a strategy can stabilize the rate of genetic substitutions and effectively accelerate fitness progression. A test with the Mackey-Glass time series prediction verifies our observations.

FILENAME: eurogp2009.pdf (236 kB)




TITLE: Evolving Novel Image Features using Genetic Programming-based Image Transforms

AUTHORS: T. Kowaliw, W. Banzhaf, N. Kharma and S. Harding

SOURCE: Proc. of CEC 2009, Trondheim, Norway, 2009, IEEE Press, New York, 2009, pp. 2502 - 2507 (electronic publication)

ABSTRACT: In this paper, we use Genetic Programming (GP) to define a set of transforms on the space of greyscale images. The motivation is to allow an evolutionary algorithm means of transforming a set of image patterns into a more classifiable form. To this end, we introduce the notion of a Transform-based Evolvable Feature (TEF), a moment value extracted from a GPtransformed image, used in a classification task. Unlike many previous approaches, the TEF allows the whole image space to be searched and augmented. TEFs are instantiated through Cartesian Genetic Programming, and applied to a medical image classification task, that of detecting OPMD-indicating inclusions in cell images. It is shown that the inclusion of a single TEF allows for significantly superior classification relative to predefined features alone.

FILENAME: cec2009.pdf (336 kB)




TITLE: Self Modifying Cartesian Genetic Programming: Parity

AUTHORS: S. Harding, J. Miller and W. Banzhaf

SOURCE: Proc. of CEC 2009, Trondheim, Norway, 2009, IEEE Press, New York, 2009, pp. 285 - 292 (electronic publication)

ABSTRACT: Self Modifying CGP (SMCGP) is a developmental form of Cartesian Genetic Programming(CGP). It differs from CGP by including primitive functions which modify the program. Beginning with the evolved genotype the self-modifying functions produce a new program (phenotype) at each iteration. In this paper we have applied it to a well known digital circuit building problem: even-parity. We show that it is easier to solve difficult parity problems with SMCGP than either with CGP or Modular CGP, and that the increase in efficiency grows with problem size. More importantly, we prove that SMCGP can evolve general solutions to arbitrary-sized even parity problems.

FILENAME: smcgp-cec1.pdf (724 kB)




TITLE: Linear genetic programming GPGPU on Microsofts Xbox 360

AUTHORS: G. Wilson and W. Banzhaf

SOURCE: Proc. of CEC 2008 (part of IEEE World Congress on Computational Intelligence, WCCI), Hongkong, China, 2008, IEEE Press, New York, 2008, pp. 378 - 385 (electronic publication)

ABSTRACT: We describe how to harness the graphics processing abilities of a consumer video game console (Xbox 360) for general programming on graphics processing unit (GPGPU) purposes. In particular, we implement a linear GP (LGP) system to solve classification and regression problems. We conduct inter- and intra-platform benchmarking of the Xbox 360 and PC, using GPU and CPU implementations on both architectures. Platform benchmarking confirms highly integrated CPU and GPU programming flexibility of the Xbox 360, having the potential to alleviate typical GPGPU decisions of allocating particular functionalities to CPU or GPU.

FILENAME: CEC_2008.pdf (530 kB)




TITLE: Combatting Financial Fraud: A Coevolutionary Anomaly Detection Approach

AUTHORS: X. Wu and W. Banzhaf

SOURCE: Proc. of the 10th Genetic and Evolutionary Computation Conference (GECCO-08), Atlanta, USA, 2008 M. Keijzer et al (Eds.), ACM, New York, 2008, pp. 1673 - 1680 (electronic publication)

ABSTRACT: A major difficulty for anomaly detection lies in discovering boundaries between normal and anomalous behavior, due to the deficiency of abnormal samples in the training phase. In this paper, a novel coevolutionary algorithm which attempts to simulate territory establishment in ecology is conceived to tackle anomaly detection problems. Two species in normal and abnormal behavior pattern space coevolve competitively and cooperatively. Competition prevents individuals in one species from invading the other's territory; cooperation aims to achieve complete pattern coverage by adjusting the evolutionary environment according to the pressure coming from neighbors. In a sense, we extend the definition of cooperative coevolution from coupled fitness to interaction of the evolutionary environment. This coevolutionary algorithm, enhanced with features like niching inside of species, global and local fitness, and fuzzy sets, tries to balance overfitting and overgeneralization. This provides an accurate boundary definition. Experimental results on transactional data from a real financial institution show that this coevolutionary algorithm is more effective than the evolutionary algorithm in evolving normal or abnormal behavior patterns only.

FILENAME: gecco08.pdf (941 kB)




TITLE: An Artificial Chemistry-based Model of Economies

AUTHORS: Bas Straatman, Roger White and Wolfgang Banzhaf

SOURCE: Proceedings of Artificial Life XI (ALIFE-XI), Winchester, UK, 2008
S. Bullock, J. Noble, R. Watson and M. Bedau (Eds.), MIT Press, Cambridge, 2008, pp. 592 - 599

ABSTRACT: Economies can be modelled using Artificial Chemistry approaches. In this contribution we discuss the development of such a model starting from the well-known von Neumann?s technology matrices. Skills and technologies that allow the transformation of raw materials into products are introduced in a form akin to chemical reactions. The dynamic flow of materials in such a system is simulated and connected through an agent-based market mechanism that assigns value to raw materials, labour, and products. Starting from a fixed set of raw materials, energy and labor, we observe the appearance of new products, the use of consumables and the general increase in complexity of such a system. Real evolutionary dynamics including waves of innovation can be demonstrated.

FILENAME: alife08.pdf (211 kB)




TITLE: Genetic Programming on GPUs for Image Processing

AUTHORS: Simon Harding and Wolfgang Banzhaf

SOURCE: Proceedings of the First International Workshop on Parallel and Bioinspired Algorithms (WPABA-2008), Toronto, Canada, 2008
J. Lanchares, F. Fernandez and J.L. Risco-Martin (Eds.), Complutense University of Madrid Press, Madrid, 2008, pp. 65 - 72

ABSTRACT: The evolution of image filters using Genetic Programming is a relatively unexplored task. This is most likely due to the high computational cost of evaluating the evolved programs. We use the parallel processors available on modern graphics cards to greatly increase the speed of evaluation. Previous papers in this area dealt with noise reduction and edge detection. Here we demonstrate that other more complicated processes can also be successfully evolved, and that we can ?reverse engineer? the output from filters used in common graphics manipulation programs.

FILENAME: wpaba08.pdf (385 kB)




TITLE: Nonsynonymous to Synonymous Substitution Ratio ka/ks: Measurement for Rate of Evolution in Evolutionary Computation

AUTHORS: Ting Hu and Wolfgang Banzhaf

SOURCE: Proc. PPSN X, Dortmund, Germany, September 2008
G. Rudolph, et al. (Eds.) Springer, LNCS 5199, Heidelberg, 2008, pp. 448 - 457

ABSTRACT: Measuring fitness progression using numeric quantization in an Evolutionary Computation (EC) system may not be sufficient to cap- ture the rate of evolution precisely. In this paper, we define the rate of evolution Re in an EC system based on the rate of efficient genetic variations being accepted by the EC population. This definition is mo- tivated by the measurement of amino acid to synonymous substitution ratio ka/ks in biology, which has been widely accepted to measure the rate of gene sequence evolution. Experimental applications to investi- gate the effects of four major configuration parameters on our rate of evolution measurement show that Re well reflects how evolution pro- ceeds underneath fitness development and provides some insights into the effectiveness of EC parameters in evolution acceleration.

FILENAME: ppsn08_evorate.pdf (168 kB)




TITLE: A Developmental Approach to the Uncapacitated Examination Timetabling Problem

AUTHORS: Nelishia Pillay and Wolfgang Banzhaf

SOURCE: Proc. PPSN X, Dortmund, Germany, September 2008
G. Rudolph, et al. (Eds.) Springer, LNCS 5199, Heidelberg, 2008, pp. 276 - 285

ABSTRACT: The paper describes a new approach, based on cell biology, to the uncapacitated examination timetabling problem. This approach begins with a single cell which is developed into a fully grown organism through the processes of cell division, cell interaction and cell migration. The mature organism represents a solution to the particular timetabling problem. The paper discusses the performance of this method on the Carter set of benchmark problems. This data set is comprised of real-world timetabling problems. The results obtained using the developmental approach are compared to that obtained by other biologically inspired algorithms applied to the same set of benchmarks and the best results cited in the literature for the Carter data set.

FILENAME: ppsn08_develop.pdf (204 kB)




TITLE: A Comparison of Cartesian Genetic Programming and Linear Genetic Programming

AUTHORS: Garnett Wilson and Wolfgang Banzhaf

SOURCE: Proc. 11th Europ. Conference on Genetic Programming, Naples, Italy, April 2008
M. O'Neill, et al. (Eds.) Springer, LNCS 4971, Heidelberg, 2008, pp. 182 - 193

ABSTRACT: Two prominent genetic programming approaches are the graph-based Cartesian Genetic Programming (CGP) and Linear Genetic Programming (LGP). Recently, a formal algorithm for constructing a directed acyclic graph (DAG) from a classical LGP instruction sequence has been established. Given graphbased LGP and traditional CGP, this paper investigates the similarities and differences between the two implementations, and establishes that the significant difference between them is each algorithmÕs means of restricting interconnectivity of nodes. The work then goes on to compare the performance of two representations each (with varied connectivity) of LGP and CGP to a directed cyclic graph (DCG) GP with no connectivity restrictions on a medical classification and regression benchmark.

FILENAME: eurogp08_clgp.pdf (628 kB)




TITLE: A SIMD Interpreter for Genetic Programming on GPU Graphics Cards

AUTHORS: William B. Langdon and Wolfgang Banzhaf

SOURCE: Proc. 11th Europ. Conference on Genetic Programming, Naples, Italy, April 2008
M. O'Neill, et al. (Eds.) Springer, LNCS 4971, Heidelberg, 2008, pp. 73 - 85

ABSTRACT: Mackey-Glass chaotic time series prediction and nuclear protein classification show the feasibility of evaluating genetic programming populations directly on parallel consumer gaming graphics processing units. Using a Linux KDE computer equipped with an nVidia GeForce 8800 GTX graphics processing unit card the C++ SPMD interpretter evolves programs at Giga GP operations per second (895 million GPops). We use the RapidMind general processing on GPU (GPGPU) framework to evaluate an entire population of a quarter of a million individual programs on a non-trivial problem in 4 seconds. An efficient reverse polish notation (RPN) tree based GP is given.

FILENAME: eurogp08_gpu.pdf (1.1 MB)




TITLE: A Genetic Programming Approach to the Generation of Hyper-Hyristics for the Uncapacitated Examination Timetabling Problem

AUTHORS: Nelishia Pillay and Wolfgang Banzhaf

SOURCE: Proc. of EPIA-07, J. Neves, M. Santos, and J. Machado (Eds.), 2007, pp. 223 --- 234, Springer, LNAI Vol 4874, Heidelberg, 2007

ABSTRACT: Research in the field of examination timetabling has developed in two directions. The first looks at applying various methodologies to induce examination timetables. The second takes an indirect approach to the problem and examines the generation of heuristics or combinations of heuristics, i.e. hyper-heuristics, to be used in the construction of examination timetables. The study presented in this paper focuses on the latter area. This paper presents a first attempt at using genetic programming for the evolution of hyper-heuristics for the uncapacitated examination timetabling problem. The system has been tested on 9 benchmark examination timetabling problems. Clash-free timetables were found for all 9 nine problems. Furthermore, the performance of the genetic programming system is comparable to, and in a number of cases has produced better quality timetables, than other search algorithms used to evolve hyper-heuristics for this set of problems.

FILENAME: epia.pdf (273 kB)




TITLE: Self-Modifying Cartesian Genetic Programming

AUTHORS: Simon Harding, Julian F. Miller and Wolfgang Banzhaf

SOURCE: Proc. of the 9th Genetic and Evolutionary Computation Conference (GECCO-07), London, UK, 7-11 July 2007, D. Thierens et al (Eds.), 2007, pp. 1021 --- 1028, ACM, New York, 2007 (electronic publication)

ABSTRACT: In nature, systems with enormous numbers of components (i.e. cells) are evolved from a relatively small genotype. It has not yet been demonstrated that artificial evolution is sufficient to make such a system evolvable. Consequently researchers have been investigating forms of computational development that may allow more evolvable systems. The approaches taken have largely used re-writing, multi- cellularity, or genetic regulation. In many cases it has been difficult to produce general purpose computation from such systems. In this paper we introduce computational development using a form of Cartesian Genetic Programming that includes self-modification operations. One advantage of this approach is that ab initio the system can be used to solve computational problems. We present results on a number of problems and demonstrate the characteristics and advantages that self-modification brings.

FILENAME: smcgp.pdf (233 kB)




TITLE: Fast Genetic Programming And Artificial Developmental Systems on GPUs

AUTHORS: Simon Harding and Wolfgang Banzhaf

SOURCE: Proc. 21st International Symposium on High Performance Computing Systems, 2007
IEEE Computer Society, New York, 2007, electronic publication

ABSTRACT: In this paper we demonstrate the use of the Graphics Processing Unit (GPU) to accelerate Evolutionary Computation applications, in particular Genetic Programming approaches. We show that it is possible to get speed increases of several hundred times over a typical CPU implementation, catapulting GPU processing for these applications into the realm of HPC. This increase in performance also extends to artificial developmental systems, where evolved programs are used to construct cellular systems. Feasibility of this approach to efficiently evaluate artificial developmental systems based on cellular automata is demonstrated.

FILENAME: HPCS07.pdf (184 kB)




TITLE: Fast Genetic Programming on GPUs

AUTHORS: Simon Harding and Wolfgang Banzhaf

SOURCE: Proc. 10th Europ. Conference on Genetic Programming, Valencia, Spain, April 2007
M. Ebner, M. O'Neill, A. Ekart, L. Vanneschi, A. Esparcia-Alcazar (Eds.) Springer, LNCS 4445, Berlin, 2007, pp. 90 - 101

ABSTRACT: As is typical in evolutionary algorithms, fitness evaluation in GP takes the majority of the computational effort. In this paper we demonstrate the use of the Graphics Processing Unit (GPU) to accelerate the evaluation of individuals. We show that for both binary and floating point based data types, it is possible to get speed increases of several hundred times over a typical CPU implementation. This allows for eval- uation of many thousands of fitness cases, and hence should enable more ambitious solutions to be evolved using GP.

FILENAME: eurogp07.pdf (156 kB)




TITLE: Evolving Noisy Oscillatory Dynamics in Genetic Regulatory Networks

AUTHORS: Andre Leier, P. Dwight Kuo, Wolfgang Banzhaf and Kevin Burrage

SOURCE: Proc. 9th Europ. Conference on Genetic Programming, Budapest, Hungary, April 2006
P. Collet, M. Tomassini, M. Ebner, S. Gustafson, A. Ekárt (Eds.) Springer, LNCS 3905, Berlin, 2006, pp. 290 - 299

ABSTRACT: We introduce a genetic programming (GP) approach for evolving genetic networks that demonstrate desired dynamics when simulated as a discrete stochastic process. Our representation of genetic networks is based on a biochemical reaction model including key elements such as transcription, translation and post-translational modifications. The stochastic, reaction-based GP system is similar but not identical with algorithmic chemistries. We evolved genetic networks with noisy oscillatory dynamics. The results show the practicality of evolving particular dynamics in gene regulatory networks when modelled with intrinsic noise.

FILENAME: eurogp06.pdf (573 kB)




TITLE: An Algorithmic Chemistry for Genetic Programming

AUTHORS: Christian W.G.Lasarczyk and Wolfgang Banzhaf

SOURCE: Proc. 8th Europ. Conference on Genetic Programming, Lausanne, Switzerland, April 2005
M. Keijzer, A. Tettamanzi, P. Collet, M. Tomassini, J. van Hemert (Eds.) Springer, LNCS 3447, Berlin, 2005, pp. 1 - 12

ABSTRACT: Genetic Programming has been slow at realizing other pro- gramming paradigms than conventional, deterministic, sequential von-Neumann type algorithms. In this contribution we discuss a new method of execution of programs introduced recently: Algorithmic Chemistries. Therein,register machine instructions are executed in a non-deterministic order, following a probability distribution. Program behavior is thus highly dependent on frequency of instructions and connectivity between registers. Here we demonstrate the performance of GP on evolving solutions to a parity problem in a system of this type.

FILENAME: eurogp05_AC.pdf (222 kB)




TITLE: Repeated Patterns in Tree Genetic Programming

AUTHORS: William B. Langdon and Wolfgang Banzhaf

SOURCE: Proc. 8th Europ. Conference on Genetic Programming, Lausanne, Switzerland, April 2005
M. Keijzer, A. Tettamanzi, P. Collet, M. Tomassini, J. van Hemert (Eds.) Springer, LNCS 3447, Berlin, 2005, pp. 190 - 202

ABSTRACT: We extend our analysis of repetitive patterns found in genetic programming genomes to tree based GP. As in linear GP, repetitive patterns are present in large numbers. Size fair crossover limits bloat in automatic programming, preventing the evolution of recurring motifs. We examine these complex properties in detail: e.g.using depth v.size Catalan binary tree shape plots, subgraph and subtree matching, information entropy, syntactic and semantic fitness correlations and diffusive introns. We relate this emergent phenomenon to considerations about building blocks in GP and how GP works.

FILENAME: eurogp_repeated05.pdf (694 kB)




TITLE: Evolving Dynamics in an Artificial Regulatory Network Model

AUTHORS: P.D. Kuo, A. Leier and Wolfgang Banzhaf

SOURCE: Proc. of the Parallel Problem Solving from Nature Conference (PPSN-04), Birmingham, UK, September 2004, Yao X., Burke E., Lozano J.A., Smith J., Merelo-Guervós J.J., Bullinaria J.A., Rowe J., Tino P., Kabán A., Schwefel H.-P. (Eds.), Springer, LNCS 3242, Berlin, pp. 571 --- 580

ABSTRACT: In this paper artificial regulatory networks (ARN) are evolved to match the dynamics of test functions. The ARNs are based on a genome representation generated by a duplication / divergence process. By creating a mapping between the protein concentrations created by gene excitation and inhibition to an output function, the network can be evolved to match output functions such as sinusoids, exponentials and sigmoids. This shows that the dynamics of an ARN may be evolved and thus may be suitable as a method for generating arbitrary time series.

FILENAME: ARNOptimizeNew.pdf (256 kB)




TITLE: Small World and Scale-Free Network Topologies in an Artificial Regulatory Network Model

AUTHORS: P.D. Kuo and Wolfgang Banzhaf

SOURCE: Proc. Artificial Life IX, (ALIFE-9), Boston, USA, 2004, J. Pollack, M. Bedau, P. Husbands, T. Ikegami, R. Watson (Eds.), MIT Press, Cambridge, pp. 404 --- 409

ABSTRACT: Small world and scale free network topologies commonly exist in natural and artificial systems. Many mechanisms for producing these topologies have been presented in the literature. We present an artificial regulatory network model generated by a duplication / divergence process on a randomly generated genetic string and show that networks with small world and scale free topologies can be produced with some regularity.

FILENAME: Genome_final.pdf (256 kB)




TITLE: Comparison of Selection Strategies for Evolutionary Quantum Circuit Design

AUTHORS: A. Leier and Wolfgang Banzhaf

SOURCE: Proc. of the Genetic and Evolutionary Computation Conference (GECCO-04), Seattle, USA, 26-30 June 2004, K. Deb, R. Poli, W. Banzhaf, H.-G. Beyer, E. Burke, P. Darwen, D. Dasgupta, D. Floreano, J. Foster, M. Harman, O. Holland, P.L. Lanzi, L. Spector, A. Tettamanzi, D. Thierens, A. Tyrrell (Eds.), 2004, pp. 557 --- 568

ABSTRACT: Evolution of quantum circuits faces two major: Complex and huge search spaces and the high costs of simulating quantum circuits on conventional computers.In this paper we analyze different selection strategies, which are applied to the Deutsch-Josza problem and the 1-SAT problem using our GP system. Furthermore, we show the effects of adding randomnes to the selection mechanism of a (1,10) selection strategy. In can be demonstrated that this boosts the evolution of quantum algorithms on particular problems.

FILENAME: lb04_final.pdf (200 kB)




TITLE: DNASequenceGenerator: A Program for the construction of DNA sequences

AUTHORS: Udo Feldkamp, Sam Sagafi, Wolfgang Banzhaf and Hilmar Rauhe

SOURCE: 7th DIMACS Workshop on DNA Computing, South Florida, 2001, Springer, LNCS 2340, Berlin, 2001, pp. 23 --- 32

ABSTRACT: In DNA Computing and DNA nanotechnology the design of proper DNA sequences turned out to be an elementary problem [1-9]. We here present a software program for the construction of sets ("pools") of DNA sequences. The program can create DNA sequences to meet logical and physical parameters such as uniqueness, melting temperature and GC ratio as required by the user. It can create sequences de novo, complete sequences with gaps and allows import and recycling of sequences that are still in use. The program always creates sequences that are - in terms of uniqueness, GC ratio and melting temperature - "compatible" to those already in the pool, no matter whether those were added manually or created or completed by the program itself. The software comes with a GUI and a Sequence Wizard. In vitro tests of the program's output were done by generating a set of oligomers designed for self-assembly. The software is available for download here.

FILENAME: DNASeqGenDNA7_FINAL.pdf (572 kB)




TITLE: On the Dynamics of an Artificial Regulatory Network

AUTHORS: Wolfgang Banzhaf

SOURCE: Advances in Artificial Life, Proceedings of the 7th European Conference (ECAL-2003), Dortmund, September 15-17, 2003
W. Banzhaf, T. Christaller, P. Dittrich, J. Kim, J. Ziegler (Eds.) Springer, Berlin, Lecture Notes in Artificial Intelligence, LNAI 2801, 2003, pp. 217 --- 227

ABSTRACT: We investigate a simple artificial regulatory networks (ARNs) able to reproduce phenomena found in natural genetic regulatory networks. Notably heterochrony, a variation in timing of expression, is easily achievable by simple mutations of bits in the genome. It is argued that ARNs are useful and important new genetic representations for artificial evolution.

FILENAME: ecal2003_final.pdf (811 kB)




TITLE: You can judge a book by its cover - Evolution of gait controllers based on program code analysis

AUTHORS: J. Ziegler and Wolfgang Banzhaf

SOURCE: Proceedings of the Sixth International Conference on Climbing and Walking Robots, CLAWAR-2003, G. Muscato, D. Longo (Eds.), Professional Engineering Publ., Bury St. Edmunds, U.K., 2003, 205 - 212

ABSTRACT: This paper introduces a Genetic Programming (GP) approach to automatically evolve control programs for walking robots. In contrast to earlier work, in which the evolution of gait control programs depended on the direct measurement of the quality of movements of simulated robots, in this paper a new method is presented that circumvents time consuming evaluations of control programs through the probabilistic evolutionary process.

FILENAME: ZieglerBanzhaf.pdf (234 kB)




TITLE: Evolving Hogg's Quantum Algorithm Using Linear-Tree GP

AUTHORS: Andre Leier and Wolfgang Banzhaf

SOURCE: Proc. of the Genetic and Evolutionary Computation Conference (GECCO-03), Chicago, USA, 12-16 Juli 2003
E. Cantu-Paz, J. Foster, K. Deb, D. Davis, R. Roy, U.-M. O'Reilly, H.-G. Beyer, R. Standish, G. Kendall, S. Wilson, M. Harmann, J. Wegener, D. Dasgupta, M.A. Potter, A.C. Schultz, K. Dowsland, N. Jonoska, J.F. Miller (Eds.), Springer, LNCS 2723, Berlin, 2003, pp. 390 - 400

ABSTRACT: Intermediate measurements in quantum circuits compare to conditional branchings in programming languages. Due to this, quantum circuits have a natural linear-tree structure. In this paper a Genetic Programming system based on linear-tree genome structures developed for the purpose of automatic quantum circuit design is introduced. It was applied to instances of the 1-SAT problem, resulting in evidently and ``visibly'' scalable quantum algorithms, which correspond to Hogg's quantum algorithm.

FILENAME: hogg.pdf (222 kB)




TITLE: Decreasing the Number of Evaluations in Evolutionary Algorithms by using a Meta-Model of the Fitness Function

AUTHORS: Jens Ziegler and Wolfgang Banzhaf

SOURCE: Proc. 6th Europ. Conference on Genetic Programming, Exeter, England, April 2003
C. Ryan, T. Soule, M. Keijzer, E. Tsang, R. Poli, E. Costa (Eds.) Springer, LNCS 2610, Berlin, 2003, pp. 264 - 275

ABSTRACT: In this paper a method is presented that decreases the necessary number of evaluations in Evolutionary Algorithms. A classifier with confidence information is evolved to replace time consuming evaluations during tournament selection. Experimental analysis of a mathematical example and the application of the method to the problem of evolving walking patterns for quadruped robots show the potential of the presented approach.

FILENAME: lncs_decrease.pdf (642 kB)




TITLE: More on Computational Effort Statistics for Genetic Programming

AUTHORS: Jens Niehaus and Wolfgang Banzhaf

SOURCE: Proc. 6th Europ. Conference on Genetic Programming, Exeter, England, April 2003
C. Ryan, T. Soule, M. Keijzer, E. Tsang, R. Poli, E. Costa (Eds.) Springer, LNCS 2610, Berlin, pp. 164 - 172

ABSTRACT: In this contribution we take a look at the computational effort statistics as described by Koza. We transfer the notion from generational genetic programming to tournament-selection (steady-state) GP and show why, in both cases, the measured value of the effort often differs from its theoretical counterpart. It is discussed how systematic estimation errors are introduced by a low number of experiments. Two reasons examined are the number of unsuccessful experiments and the variation in the number of fitness evaluations necessary to find a solution among the successful experiments.

FILENAME: lncs_ce.pdf (168 kB)




TITLE: Neutral Variations Cause Bloat in Linear GP

AUTHORS: Markus Brameier and Wolfgang Banzhaf

SOURCE: Proc. 6th Europ. Conference on Genetic Programming, Exeter, England, April 2003
C. Ryan, T. Soule, M. Keijzer, E. Tsang, R. Poli, E. Costa (Eds.)\\ Springer, LNCS 2610, Berlin, pp. 286 - 296

ABSTRACT: In this contribution we investigate the influence of different variation effects on the growth of code. A mutation-based variant of linear GP is applied that operates with minimum structural step sizes. % on the imperative program structure. Results show that neutral variations are a direct cause for (and not only a result of) the emergence and the growth of intron code. The influence of non-neutral variations % on code growth has been found to be considerably smaller. Neutral variations turned out to be beneficial by solving two classification problems more successfully.

FILENAME: lncs_neutral.pdf (184 kB)




TITLE: Automatic evolution of control programs for a small humanoid walking robot

AUTHORS: Jens Ziegler, Jan Barnholt, Jens Busch and Wolfgang Banzhaf

SOURCE: Proceedings of the Fifth International Conference on Climbing and Walking Robots, CLAWAR-2002
P. Bidaud and F. Ben Amar, (Eds.), Professional Engineering Publishing, 2002, pp. 109 - 116

ABSTRACT:

FILENAME: (n kB)




TITLE: Evolving chess playing programs

AUTHORS: Roderich Gross, Keno Albrecht, Wolfgang Kantschik and Wolfgang Banzhaf

SOURCE: GECCO-02 Proceedings

ABSTRACT: This contribution introduces a hybrid GP/ES system for the evolution of chess playing computer programs. We discuss the basic system and examine its performance in comparison to pre-existing algorithms of the type alpha-beta and its improved variants. We can show that evolution is able to outperform these algorithms both in terms of efficiency and strength.

FILENAME: teams.pdf (185 kB)




TITLE: Explicit Control of Diversity and Effective Variation Distance in Linear Genetic Programming

AUTHORS: Markus Brameier and Wolfgang Banzhaf

SOURCE: Proceedings of the 4th European Conference on Genetic Programming, EuroGP 2002, Kinsale, Ireland, E. Lutton, J. Foster, J. Miller, C. Ryan and A. Tettamanzi (Eds.), Springer LNCS 2278, Berlin, 2002, pp. 38-50

ABSTRACT: We have investigated structural distance metrics for linear genetic programs. Causal connections between changes of the genotype and changes of the phenotype form a necessary condition for analyzing structural differences between genetic programs and for the two objectives of this paper: (i) The distance information between individuals is used to control structural diversity of population individuals actively by a two-level tournament selection. (ii) Variation distance of effective code is controlled for different genetic operators - including a mutation operator that works closely with the applied distance measure. Numerous experiments have been performed for three benchmark problems.

FILENAME: eurogp02_dist.pdf (190 kB)




TITLE: Linear-Graph GP -- A new GP Structure

AUTHORS: Wolfgang Kantschik and Wolfgang Banzhaf

SOURCE: Proceedings of the 4th European Conference on Genetic Programming, EuroGP 2002, Kinsale, Ireland, E. Lutton, J. Foster, J. Miller, C. Ryan and A. Tettamanzi (Eds.), Springer LNCS 2278, Berlin, 2002, pp. 83-92

ABSTRACT: In recent years different genetic programming (GP) structures have emerged. Today, the basic forms of representation for genetic programs are tree, linear and graph structures. In this contribution we introduce a new kind of GP structure which we call linear-graph, it is a further development of the linear-Tree structure. We describe the linear-graph structure, as well as crossover and mutation for this new GP structure in detail. We compare linear-graph programs with linear and tree programs by analyzing their structure and results on different test problems.

FILENAME: eurogp02_lingraph.pdf (227 kB)




TITLE: Automatic Generation of Control Programs for Walking Robots Using Genetic Programming

AUTHORS: J. Busch, J. Ziegler, W. Banzhaf, A. Ross, D. Sawitzki and C. Aue

SOURCE: Proceedings of the 4th European Conference on Genetic Programming, EuroGP 2002, Kinsale, Ireland, E. Lutton, J. Foster, J. Miller, C. Ryan and A. Tettamanzi (Eds.), Springer LNCS 2278, Berlin, 2002, pp. 259-268

ABSTRACT: We present the system SIGEL that combines the simulation and visualization of robots with a Genetic Programming system for the automated evolution of walking. It is designed to automatically generate control programs for arbitrary robots without depending on detailed analytical information of the robots' kinematic structure. Different fitness functions as well as a variety of parameters allow the easy and interactive configuration and adaptation of the evolution process and the simulations.

FILENAME: eurogp02_sigel.pdf (158 kB)




TITLE: Evolution of Robot Leg Movements in a Physical Simulation

AUTHORS: Jens Ziegler and Wolfgang Banzhaf

SOURCE: Proceedings of the Fourth International Conference on Climbing and Walking Robots, CLAWAR , 2001, K. Berns and R. Dillmann, (Eds.), Professional Engineering Publishing

ABSTRACT: This paper introduces a Genetic Programming approach to creating patterns of movements for legs of walking robots. It uses a physics-based simulation system to evaluate the fitness of movement patterns, which are emerging from the interpret ation of the individuals of the population. Different methods are shown that increase the speed of the evolution by several orders of magnitude.

FILENAME: ZBCLAWAR01.pdf (283 kB)




TITLE: Constructing a Small Humanoid Walking Robot as a Platform for the Genetic Evolution of Walking

AUTHORS: Jens Ziegler, Krister Wolff, Peter Nordin and Wolfgang Banzhaf

SOURCE: Autonomous Minirobots for Research and Edutainment, AMiRE2001, Proceedings of the 5th International Heinz Nixdorf Symposium , 2001, U. Rückert (Ed.),HNI-Verlagsschriftenreihe, Vol. 97, ISBN 3-935433-06-9, Paderborn, 2001

ABSTRACT: Walking robots from the next challenge in the field of autonomous robots. This paper describes the construction of a fully autonomous humanoid walking robot as a platform for machine learning algorithms like, e.g., Genetic Programming. Built from off-the-shelf components, the described humanoids are cheap, robust and easy to program, which make them an ideal test platform for several experimental approaches in machine learning, sensor fusion or adaptive control. In addition to these research related topics, the walking robots are an ideal tool for educational purposes.

FILENAME: ZWNB_AMIRE2001.pdf (344 kB)




TITLE: Survival of the Unfittest? - The Seceder Model and its Fitness Landscape

AUTHORS: Peter Dittrich and Wolfgang Banzhaf

SOURCE: Advances in Artificial Life, Proc. of the 6th European Conference ECAL 2001, Prague, September 2001, J. Kemelen and P. Sosik (Eds.) pp. 100 - 109

ABSTRACT: The seceder model is an extremely simple individual based model which shows how the local tendency to be dierent gives rise to the formation of hierarchically structured groups, called the seceder eect. The model consists of a population of simple entities which reproduce and die. In a single reproduction event three individuals are chosen ran- domly and the individual which possesses the largest distance to their mean is reproduced by creating a mutated copy (ospring). The o- spring replaces a randomly chosen individual of the population. In this contribution we investigate the eective tness landscape of the seceder model. Fitness is measured as reproductive success. The investigation of the tness landscape revealed an on the rst view counterintuitive phe- nomena: The individuals of the basic seceder model are always located in the worst regions of the tness landscape where the replication rate is relatively low.

FILENAME: ecal01_survival.pdf (1.209 kB)




TITLE: Stability of Metabolic and Balanced Organizations

AUTHORS: Pietro Speroni di Fenizio and Wolfgang Banzhaf

SOURCE: Advances in Artificial Life, Proc. of the 6th European Conference ECAL 2001, Prague, September 2001, J. Kemelen and P. Sosik (Eds.) pp. 196 - 205

ABSTRACT: We investigate the possible organisations emerging from an artificial chemistry (AC) of colliding molecules in a well stirred reactor. The molecules are generated from 7 basic components (atoms), each with a different behavior. After discovering two main types of organisations (metabolic o. and balanced o.), we deepen our analysis by studying their behavior over time. The phases they pass through and their stability with respect to an external influx of random information are examined. We notice that no organisation seems to be totally stable over time, yet metabolic organisations pass through a growth phase with a much higher stability. Lastly we observe how the different phases are triggered by the presence or absence of particular atoms.

FILENAME: ecal01_stab.pdf (372 kB)




<

TITLE: Spontaneous Formation of Proto-Cells in a Universal Artificial Chemistry on a Planar Graph

AUTHORS: Pietro Speroni di Fenizio, Peter Dittrich and Wolfgang Banzhaf

SOURCE: Advances in Artificial Life, Proc. of the 6th European Conference ECAL 2001, Prague, September 2001, J. Kemelen and P. Sosik (Eds.) pp. 206 - 215

ABSTRACT: An artificial chemistry is embedded in a triangular planar graph, that allows the molecules to act only locally along the edges. We observe the formation of e ectively separated components in the graph structure. Those components are kept separated by elastic reactions from molecules generated inside the component itself. We interpret those components as self-maintaining proto-cells and the elastic nodes as their proto-membrane. The possibility for these cells to be autopoietic is discussed.

FILENAME: ecal01_spont.pdf (479 kB)




TITLE: Evolution of Genetic Code on a Hard Problem

AUTHORS: R. Keller and W. Banzhaf

SOURCE: Proceedings of the 3rd annual international Conference on Genetic and Evolutionary Computation (GECCO-2001) Morgan Kaufmann, San Francisco, 2001, pp. 50 -- 56

EDITORS: Spector, L. and Goodman, E.D. and Wu, A. and Langdon, W. B. and Voigt, H.M. and Gen, M. and Sen, S. and Dorigo, M. and Pezeshk, S. and Garzon, M. and Burke, E. ABSTRACT: In most Genetic Programming (GP) approaches, the space of genotypes, that is the search space, is identical to the space of phenotypes, that is the solution space. Developmental approaches, like Developmental Genetic Programming (DGP), distinguish between genotypes and phenotypes and use a genotype-phenotype mapping prior to fitness evaluation of the phenotype. To perform this mapping, DGP uses a genetic code, that is, a mapping from genotype components to phenotype components. The genotype-phenotype mapping is critical for the performance of the underlying search process which is why adapting the mapping to a given problem is of interest. Previous work shows, on an easy synthetic problem, the feasibility of code evolution to the effect of a problem-specific self-adaptation of the mapping. The present empirical work delivers a demonstration of this effect on a hard synthetic problem, showing the real-world potential of code evolution which increases the occurrence of relevant phenotypic components and reduces the occurrence of components that represent noise.

FILENAME: KB_gecco2001.pdf (208 kB)




TITLE: Linear-Tree GP and its comparison with other GP structures

AUTHORS: W. Kantschik and W. Banzhaf

SOURCE: Proceedings of 4th EuroGP Conference, Como 2001, Springer, Berlin, 2001, pp. 302 -- 312

EDITORS: J. Miller, M. Tomassini, P.-L. Lanzi, C. Ryan, A. Tettamanzi and W. B. Langdon ABSTRACT: In recent years different genetic programming (GP) structures have emerged. Today, the basic forms of representation for genetic programs are tree, linear and graph structures. In this contribution we introduce a new kind of GP structure which we call linear-tree. We describe the linear-tree-structure, as well as crossover and mutation for this new GP structure in detail. We compare linear-tree programs with linear and tree programs by analyzing their structure and results on different test problems.

FILENAME: eurogp01-1.pdf (208 kB)




TITLE: Adaption of Operator Probabilities in Genetic Programming

AUTHORS: J. Niehaus und W. Banzhaf

SOURCE: Proceedings of 4th EuroGP Conference, Como 2001, Springer, Berlin, 2001, pp. 325 -- 336

EDITORS: J. Miller, M. Tomassini, P.-L. Lanzi, C. Ryan, A. Tettamanzi and W. B. Langdon

ABSTRACT: In this work we tried to reduce the number of free parameters within Genetic Programming without reducing the quality of the results. We developed three new methods to adapt the probabilities, different genetic operators are applied with. Using two problems from the areas of symbolic regression and classification we showed that the results in these cases were better than randomly chosen parameter sets and could compete with parameter sets chosen with empirical knowledge.

FILENAME: eurogp01-2.pdf (212 kB)




TITLE: Genetic Programming Bloat without Semantics

AUTHORS: W. B. Langdon and W. Banzhaf

SOURCE: Proceedings of 6th International Conference on Parallel Problem Solving from Nature - PPSN VI, Paris 2000, Springer, Berlin, 2000, pp. 201 -- 210

EDITORS: M. Schoenauer, K. Deb, G. Rudolph, X. Yao, E. Lutton, J.J. Merelo and H.-P. Schwefel

ABSTRACT: To investigate the fundamental causes of bloat, six artificial random binary tree search spaces are presented. Fitness is given by program syntax (the genetic programming genotype). GP populations are evolved on both random problems and problems with ``building blocks''. These are compared to problems with explicit ineffective code (introns, junk code, inviable code). Our results suggest the entropy random walk explanation of bloat remains viable. The hard building block problem might be used in further studies, e.g. of standard subtree crossover.

FILENAME: ppsn00.pdf (245 kB)




TITLE: Private and public key DNA steganography

AUTHORS: Andre Leier, Christoph Richter, Wolfgang Banzhaf and Hilmar Rauhe

SOURCE: Extended Manuscript from 6th DIMACS Workshop on DNA Computing, Leiden, 2000

ABSTRACT: In this paper steganographic approaches to DNA cryptography are presented. The first approach shows how digital DNA strands can be used for steganography to provide rapid encryption and decryption. The second approach is based on a method of graphical subtraction of gel-images. It can be used to constitute a molecular checksum and can be combined with the rst approach to support encryption. The second part of this paper explains a public key steganographic system. It is based on the usage of a certain double stranded DNA ring molecule which can be constructed by means of grammar rule molecules.

FILENAME: PubKey.pdf (221 kB)




TITLE: Towards a Theory of Organizations

AUTHORS: Pietro Speroni di Fenizio, Peter Dittrich, Wolfgang Banzhaf and Jens Ziegler

SOURCE: Proc. German Workshop on Artificial Life, Bayreuth, Germany, 2000

ABSTRACT: In this paper we develop an algebra to describe organizations. Its application is demonstrated with five examples. We start from definitions given by Fontana (1992) of an organization as a closed and self-maintaining set of interacting objects. We develop a formal framework to describe the inner structure of an organization and a relationship between different organizations. The definitions of intersection and union of organizations are developed. Those definitions naturally give rise to a lattice (an algebraic structure over a partially ordered set) which provides a precise basis to study the hierarchical nature of organizations. Some fundamental properties are described and the usefulness of the mathematical concepts demonstrated by application.

FILENAME: gwal2000.pdf (395 kB)




TITLE: A DNA Sequence Compiler

AUTHORS: Udo Feldkamp, Wolfgang Banzhaf and Hilmar Rauhe

SOURCE: Extended Manuscript from 6th DIMACS Workshop on DNA Computing, Leiden, 2000

ABSTRACT: Various approaches to the self-assembly of molecules have been introduced already. A step further toward flexible design and construction of precisely defined molecules are approaches to programmable self-assembly . In order to allow arbitrary programming, a sufficient solution of the negative design problem is needed. We present a computer program which translates formal grammars directly into DNA molecules. It allows the construction of DNA molecules with defined logical structure and physical properties. Applications of the compiler are DNA-computing algorithms, nano-frameworks and the construction of biochips.

FILENAME: DNASeqComp.pdf (72 kB)




TITLE: Digital DNA molecules

AUTHORS: Hilmar Rauhe, Gaby Vopper, Udo Feldkamp, Wolfgang Banzhaf and Jonathan Howard

SOURCE: Extended Manuscript from 6th DIMACS Workshop on DNA Computing, Leiden, 2000

ABSTRACT: An approach based on programmable self-assembly of DNA oligonucleotides was used to create digital DNA molecules representing binary datastructures which are equivalent to those used in computers. Utilizing plasmids as a kind of computer memory, the digital molecules could be isolated, amplified and read out using common genetic techniques. Programmability allowed several applications to be realized in vitro such as a fast physical random number generator and digital DNA-"barcodes".

FILENAME: DigDNAMol.pdf (85 kB)




TITLE: Empirical Analysis of Different Levels of Meta-Evolution

AUTHORS: W. Kantschik, P. Dittrich, M. Brameier, and W. Banzhaf

SOURCE: Proceedings of Congress on Evolutionary Computation, Washington, 1999, IEEE Press, Piscataway, NJ, pp. 1059 -- 1066

EDITORS: NN ABSTRACT: In this contribution we analyze different levels of meta-evolution using a graph-based GP system. The system allows to represent individuals of the search space and genetic variation operators in a coherent way as graph-programs differing only in the operator set. Seven variants of meta-evolution are tested on three real-world classification problems. The most complex variant consists of three meh-levels where graph-programs on meta-level 1 recombine individuals of the search space (base level), graph-programs on meta-level 2 recombine programs on meta-level 1, and programs on meta-level3 recombine programs on meta-level2 and themselves. The emperical results shows that the use of meta levels is advantageous.

FILENAME: KDBB_CEC99.pdf (693 kB)




TITLE: AIM-GP and Parallelism

AUTHORS: P. Nordin, M. Brameier, F. Hoffmann, F. Francone, and W. Banzhaf

SOURCE: Proceedings of Congress on Evolutionary Computation, Washington, 1999, IEEE Press, Piscataway, NJ, pp. 1059 -- 1066

EDITORS: NN ABSTRACT: Many machine learning tasks are just too hard to be solved with a single processor machine, no matter how efficient algorithms we use and how fast our hardware is. Luckily genetic programming is well suited for parallelization compared to standard serial algorithms. This paper describes the first parallel implementation of an AIM-GP system creating the potential for an extremely fast system. The system is tested on three problems and several variants of demes and migration are evaluated. Most of the results are applicable to both linear and tree based systems.

FILENAME: cec_parallel.pdf (595 kB)




TITLE: Decreasing the Number of Evaluations in Evolutionary Algorithms by usaing a Meta-Model of the Fitness Function

AUTHORS: Jens Ziegler and Wolfgang Banzhaf

SOURCE: Proc. 2nd European Workshop on Genetic Programming, Lecture Notes in Computer Science, LNCS, Vol. 1598, Springer, Berlin, 1999, pp. 256 -- 264

EDITORS: R. Poli, P. Nordin, W.B. Langdon and T. Fogarty

ABSTRACT: In this paper a method is presented that decreases the necessary number of evaluations in Evolutionary Algorithms. A classifier with confidence information is evolved to replace time consuming evaluations during tournament selection. Experimental analysis of a mathematical example and the application of the method to the problem of evolving walking patterns for quadruped robots show the potential of the presented approach.

FILENAME: lncs_decrease.pdf (516 kB)




TITLE: Meta-Evolution in Graph GP

AUTHORS: Wolfgang Kantschik, Peter Dittrich, Markus Brameier and Wolfgang Banzhaf

SOURCE: Proc. 2nd European Workshop on Genetic Programming, Lecture Notes in Computer Science, LNCS, Vol. 1598, Springer, Berlin, 1999, pp. 15 -- 28

EDITORS: R. Poli, P. Nordin, W.B. Langdon and T. Fogarty

ABSTRACT: In this contribution we investigate the evolution of operators for Genetic Programming by means of Genetic Programming. Metaevolution of recombination operators in graph-based GP is applied and compared to other methods for the variation of recombination operators in graph-based GP. We demonstrate that a straightforward application of recombination operators onto themselves does not work well. After introducing an additional level of recombination operators (the meta level) which are recombining a pool of recombination operators, even self-recombination on the additional level becomes feasible.We show that the overall performance of this system is better than in other variants of graph GP. As a test problem we use speaker recognition.

FILENAME: eurogp1999.pdf (516 kB)




TITLE: The Evolution of Genetic Code in Genetic Programming

AUTHORS: R. Keller and W. Banzhaf

SOURCE: Proceedings of first GECCO conference, Orlando 1999, Morgan Kaufmann, San Francisco, 1999, pp. 1077 -- 1082

EDITORS: W. Banzhaf, J. Daida, A. Eiben, M. Garzon, V. Honavar, M. Jakiela and R. Smith

ABSTRACT: In most Genetic Programming (GP) approaches, the space of genotypes, that is the search space, is identical to the space of phenotypes, that is the solution space. Developmental approaches, like Developmental Genetic Programming (DGP), distinguish between genotypes and phenotypes and use a genotype-phenotype mapping prior to fitness evaluation of a phenotype. To perform this mapping, DGP uses a problem-specific manually designed genetic code, that is a mapping from genotype components to phenotype components. The employed genetic code is critical for the performance of the underlying search process. Here, the evolution of genetic code is introduced as a novel approach for enhancing the search process. It is hypothesized that code evolution improves the performance of developmental approaches by enabling them to beneficially adapt the fitness landscape during search. As the first step of investigation, this article empirically shows the operativeness of code evolution.

FILENAME: t.pdf (89 kB)




TITLE: Speech Sound Discrimination With Genetic Programming

AUTHORS: Markus Conrads, Peter Nordin and Wolfgang Banzhaf

SOURCE: Proc. 1st European Workshop on Genetic Programming, Lecture Notes in Computer Science, LNCS, Vol. 1391, Springer, Berlin, 1998, pp. 113 -- 129

EDITORS: W. Banzhaf, R. Poli, M. Schoenauer and T. Fogarty

ABSTRACT: The question that we investigate in this paper is, whether it is possible for Genetic Programming to extract certain regularities from raw time series data of human speech. We examine whether a genetic programming algorithm can find programs that are able to discriminate certain spoken vowels and consonants. We present evidence that this can indeed be achieved with a surprisingly simple approach that does not need preprocessing. The data we have collected on the system's behavior show that even speaker-independent discrimination is possible with GP. 

FILENAME: evogp.pdf (224 kB)




TITLE: Learning to Move a Robot with Random Morphology

AUTHORS: Peter Dittrich, Andreas Buergel and Wolfgang Banzhaf

SOURCE: Proc. 1st European Workshop on Evolutionary Robotics, Lecture Notes in Computer Science, LNCS, Vol. , Springer, Berlin, 1998, 165 - 178

EDITORS: P. Husbands and J.-A. Meyer

ABSTRACT: Complex robots inspired by biological systems usually consist of many dependent actuators and are difficult to control. If no model is available automatic learning and adaptation methods have to be applied. The aim of this contribution is twofold: (1) To present an easy to maintain and cheap test platform, which fulfils the requirements of a complex control problem. (2) To discuss the application of Genetic Programming for evolution of control programs in real time. An extensive number of experiments with two real robots has been carried out. 

FILENAME: evorobot_final.pdf (367 kB)




TITLE: Mesoscopic Analysis of Self-Evolution in an Artificial Chemistry

AUTHORS: Peter Dittrich, Jens Ziegler and Wolfgang Banzhaf

SOURCE: Proc. on the 6th Int. Conf. on Artificial Life, Los Angeles, 1998, MIT Press, Cambridge, MA, 95 - 103

EDITORS: C. Adami, R.K. Belew, H. Kitano and C.E. Taylor (Eds.) ABSTRACT: In an algorithmic artificial chemistry the objects (molecules) are data structures and the interactions (reactions) among them are defined by an algorithm. The same object can appear in two forms: (1) as an active machine (operator), (2) as passive data (operand). Thus, the same object can act on other objects or it can be processed by others. This dualism allows the implicit definition of constructive artificial chemical systems, which exhibit quite complex behaviors. In our case even evolutionary behavior has been observed which is notable, because no explicit mutation, recombination or fitness function is involved. Every variation is exclusively performed by the objects (molecules) in their machine form. In addition to microscopic methods (e.g. monitoring the actions of single molecules) and macroscopic measurements (e.g. diversity, complexity) we developed a stepwise mesoscopic analysis method based on classification and dynamic clustering. Knowledge about the system is accumulated in a cyclic process, where measuring tools (classifiers) extract information, which is again used to create new classifiers. 

FILENAME: alife6.pdf (256 kB)




TITLE: Macroscopic and Microscopic Computation in an Artificial Chemistry

AUTHORS: Peter Dittrich, Wolfgang Banzhaf, Hilmar Rauhe, and Jens Ziegler

SOURCE: 2nd German Workshop on Artificial Life, University of Dortmund, April 1997

ABSTRACT: Chemical and biochemical systems as part of living organisms have been shown to possess interesting computational properties. Example: the information flow in the chemotaxis system of Escherichia Coli. In a parallel development, the chemical computation metaphor is becoming more and more frequently used as part of the emergent computation paradigm in Computer Science. In this contribution we will discuss two ways of how information can be processed by a collection of molecules floating around in well-stirred tank reactor. In the first case the information is stored as a concentration of a substances and computation is carried out by increase and decrease of concentration levels. We will refer to this as macroscopic computation. In the second case -- microscopic computation -- the result of a computation is represented by single molecules. The dynamics is stochastic, in contrast to macroscopic computation where the dynamics can be described with ordinary differential equations. In both cases the result emerges from many simple and parallel interactions. In order to show the abilities of such systems we will use artificial chemistries which are simulated reaction systems of mathematical or algorithmic objects. 

FILENAME: gwal97.pdf (182 kB)




TITLE: Towards a metabolic robot control system

AUTHORS: Jens Ziegler, Peter Dittrich and Wolfgang Banzhaf

SOURCE: Proceedings International Workshop on Information Processing in Cells and Tissues (IPCAT'97) Sheffield, UK, September 1-4, 1997, Plenum Press, New York, 1998, 305 - 317 

EDITORS: W.M.L. Holcombe, R. Paton (Eds.)

ABSTRACT: The signal processing system of a cell is very robust in its dependence upon the observation of central metabolites and, on the other hand, on the hierarchical division into functional blocks. Therefore it can act as a model for the construction of robust, highly parallel and distributed control systems. We have used the metabolic paradigm as a guideline to develop a robot architecture for simple navigation tasks. Results on obstacle avoidance and light searching behavior are reported here. 

FILENAME: ipcat_final.pdf (337 kB)




TITLE: Introns in Nature and in Simulated Structure Evolution

AUTHORS: Peter Nordin, Wolfgang Banzhaf and Frank D. Francone

SOURCE: Biocomputing and Emergent Computation, Proc. of BCEC97 Skovde, Sweden, September 1-2, 1997 , D. Lundh, B. Olsson and A. Narayanan (Eds.) World Scientific, Singapore, 1997,  22 - 35

ABSTRACT: In this study we measure the compression of information in a simulated evolutionary system. We do the investigation taking introns in the genome into account. We mainly investigate evolution of linear computer code but also present results from evolution of three-structures as well as messy-genetic algorithms. The size of solutions is an important property of any system trying to learn or adapt to its environment. The results show significant compression or constant size of exons during evolution---in contrast to the rapid growth of overall size. Our conclusion is that an inbuild pressure towards low-complexity solutions are measurable in several simulated evolutionary systems which may account for the robust adaption showed by these systems. 

FILENAME: skovde_final.pdf (305 kB)




TITLE: A Topological Structure Based on Hashing - Emergence of a ''Spatial'' Organisation

AUTHORS: Peter Dittrich and Wolfgang Banzhaf

SOURCE: Online papers at 4th European Conference on Artificial Life (ECAL97), Brighton, UK

ABSTRACT: A topological structure based on hashing for an algorithmic reaction system is introduced. Hashing, as a very efficient storage method for certain problems, uses an important property of the computer: Its ability to accurately access a specific address in memory space. It is shown, how a self-organising system can be built with this method. We discuss experiments with a reaction system based on the resulting hash topology. 

FILENAME: ECAL97_final.pdf (265 kB)




TITLE: Genetic Programming - An Introduction On the automatic evolution of computer programs and its application

TITLE: Generating Adaptive Behavior for a Real Robot using Function Regression within Genetic Programming

AUTHORS:Wolfgang Banzhaf, Peter Nordin, Markus Olmer

SOURCE: 2nd International Conference on Genetic Programming, Stanford, 1997, J. Koza, K. Deb, M. Dorigo, D. Fogel. M. Garzon, H. Iba, R. Riolo (Eds), Morgan Kaufmann Publisher, San Francisco, 1997, 35 -- 43

ABSTRACT: We discuss the generation of adaptive behavior for an autonomous robot within the framework of a special kind of function regression used in compiling Genetic Programming (GP). The control strategy for the robot is derived, using an evolutionary algorithm, from a continuous improvement of machine language programs which are varied and selected against each other. We give an overview of our recent work on several fundamental behaviors like obstacle avoidance and object following adapted from programs that were originally random sequences of commands. It is argued that the method is generally applicable where there is a need for quick adaptation within real-time problem domains. 

FILENAME: robot_over.pdf (267 kB)




TITLE: Genetic Reasoning --- Evolving Proofs with Genetic Search

AUTHORS:Peter Nordin, Wolfgang Banzhaf

SOURCE: 2nd International Conference on Genetic Programming, Stanford, 1997, J. Koza, K. Deb, M. Dorigo, D. Fogel. M. Garzon, H. Iba, R. Riolo (Eds), Morgan Kaufmann Publisher, San Francisco, 1997, 255 -- 260

ABSTRACT: Most automated reasoning systems relies on human knowledge or heuristics to guide the reasoning or search for proofs. We have evaluated the use of a powerful general search algorithm to search in the space of mathematical proofs. In our approach automated reasoning is seen as an instance of automated programming where the proof is seen as a program (of functions corresponding to rules of inference) that transforms a statement into an axiom. Genetic programming is a technique for automated programming that evolves programs with a genetic algorithm. We show that such a system can be used to evolve mathematical proofs in complex domains i.e. arithmetics and program verification. The system is not restricted to evaluations of classical two-valued logic but can be used with for instance Kleene's three valued logic in order to detect paradoxes that can occur in real life reasoning applications. 

FILENAME: gen_reas.pdf (170 kB)




TITLE: Evolving real-time behavioral modules for a robot with GP

AUTHORS Markus Olmer, Peter Nordin, Wolfgang Banzhaf

SOURCE: Proc. 6th International Symposium on Robotics And Manufacturing (ISRAM-96), Montpellier, France, 1996, in: Robotics and Manufacturing, M. Jamshidi, F. Pin, P. Dauchez (Eds.), Asme Press, New York, 1996, 675 --- 680

ABSTRACT: In this paper we demonstrate an efficient method which divides a control task into smaller sub--tasks. We use a Genetic Programming system that first learns the sub-tasks and then evolves a higher--level action selection strategy for deciding which of the evolved lower--level algorithms should be in control. The Swiss miniature robot Khepera is employed as the experimental platform. Results are presented which show that the robot is indeed able to evolve both the control algorithms for the different lower--level tasks and the strategy for the selection of tasks. The evolved solutions also show robust performance even if the robot is lifted and placed in a completely different environment or if obstacles are moved around. 

FILENAME: isram96.pdf (154 kB)




TITLE: Programmatic Compression of Images and Sound

AUTHORS Peter Nordin, Wolfgang Banzhaf

SOURCE: Proc. 1st annual Conf. on Genetic Programming (GP-96), Stanford, 1996, J. Koza, D. Goldberg, D. Fogel, R. Riolo (Eds.), MIT Press, Cambridge, MA, 1996, pp. 72 --- 81

ABSTRACT: The importance of digital data compression in the future media arena cannot be overestimated. A novel approach to data compression is built on Genetic Programming. This technique has been referred to as "programmatic compression". In this paper we apply a variant of programmatic compression to the compression of bitmap images and sampled digital sound. The work presented here constitutes the first successful result of genetic programming applied to compression of real full size images and sound. A compiling genetic programming system is used for efficiency reasons. Different related issues are discussed, such as the handling of very large fitness case sets. 

FILENAME: gp96.pdf (236 kB)




TITLE: The Effect of Extensive Use of the Mutation Operator on Generalization in Genetic Programming using Sparse Data Sets

AUTHORS: Wolfgang Banzhaf, Frank D. Francone, Peter Nordin

SOURCE: 4th Int. Conf. on Parallel Problem Solving from Nature (PPSN96), W. Ebeling, I. Rechenberg, H.P. Schwefel, H.M. Voigt (Eds.), Springer, Berlin, 1996, 300 --- 309

ABSTRACT: Ordinarily, Genetic Programming uses little or no mutation. Crossover is the predominant operator. This study tests the effect of a very aggressive use of the mutation operator on the generalization performance of our Compiling Genetic Programming System ('CPGS'). We ran our tests on two benchmark classification problems on very sparse training sets. In all, we performed 240 complete runs of population 3000 for each of the problems, varying mutation rate between 5\% and 80\%. We found that increasing the mutation rate can significantly improve the generalization capabilities of GP. The mechanism by which mutation affects the generalization capability of GP is not entirely clear. What is clear is that changing the balance between mutation and crossover effects the course of GP training substantially --- for example, increasing mutation greatly extends the number of generations for which the GP system can train before the population converges. 

FILENAME: ppsn96_mut.pdf (154 kB)




TITLE: Genetic Programming using Mutation, Reproduction and Genotype-Phenotype Mapping from linear binary Genomes into linear LALR(1) Phenotypes

AUTHORS:Robert Keller, Wolfgang Banzhaf

SOURCE: Proc. 1st annual Conf. on Genetic Programming (GP-96), Stanford, 1996, J. Koza, D. Goldberg, D. Fogel, R. Riolo (Eds.), MIT Press, Cambridge, MA, 1996, pp. 116 --- 122

ABSTRACT: In common GP approaches, the space of genotypes (search space) is identical to the space of phenotypes (solution space). Facts and theories from molecular biology suggest the introduction of non-identical genospaces and phenospaces, and a generic genotype-phenotype mapping (GPM) which maps unconstrained genotypes into syntactically correct phenotypes. Neutral variants come into effect due to GPM. They enhance genetic diversity and allow for escaping local optima in phenospace via high-dimensional saddle surfaces in genospace. We propose a concrete GPM which maps linear binary genotypes into linear phenotypes of an arbitrary LALR(1) programming language. Empirical results are presented which show that the GPM improves the performance of GP under mutation and reproduction. 

FILENAME: lalr_gp96.pdf (164 kB)




TITLE: Self-organization in a system of binary strings

AUTHORS: Wolfgang Banzhaf

SOURCE: Proceedings ARTIFICIAL LIFE IV, R. Brooks and P. Maes (Eds.), MIT Press, Cambridge, MA, 1994, pp. 109 --- 118

ABSTRACT: We discuss a system of autocatalytic sequences of binary numbers. Sequences come in two forms, a 1-dimensional form (operands) and a 2-dimensional form (operators) that are able to react with each other. The resulting reaction network shows signs of emerging metabolisms. We discuss the general framework and examine specific interactions for a system with strings of length 4 bits. A self-maintaining network of string types and parasitic interactions are shown to exist. 

FILENAME: alife94.pdf (412 kB)

TITLE: Interactive Evolution in Simulated Natural Evolution

AUTHORS:Jeanine Graf, Wolfgang Banzhaf

SOURCE: Evolution Artificielle, M. Schoenauer (ed.), Brest, France, September 4--6, 1995 In: Artificial Evolution, J.-M. Alliot, E. Lutton, E. Ronald, M. Schoenauer, D. Snyers (eds.), Springer, LNCS 1063, Berlin, 259 --- 272

ABSTRACT: This paper demonstrates how interactive evolution can be applied to natural evolution. Evolutionary algorithms of selection and variation by recombination and / or mutation can be used to simulate biological evolution in a computer. Interactive evolution can be used to direct the development of graphical models that are simulations of their counterparts in nature. Interactive evolution thus can be used to evolve models of animals and plants. We shouw that interactivity of artificial evolution can serve as a useful tool for achieving progress in the ontogenesis of simulated models and might help paleontologists to solve problems in identifying missing links. 

FILENAME: evol_artif95.pdf (347 kB)




TITLE: An Expansion Operator for Interactive Evolution

AUTHORS:Jeanine Graf, Wolfgang Banzhaf

SOURCE: Proc. IEEE Int. Conf. on Evolutionary Computation, Perth/Australia, IEEE Press, Piscataway, 1995, pp. 798 --- 802

ABSTRACT: This paper demonstrates how interactive evolution can be applied to the extrapolation and growth of graphical models. A new operator called expansion is introduced which plays a significant role in interactive evolution. The expansion operator is based on time series analysis of evolutionary processes. We describe and demonstrate the function of the new operator. 

FILENAME: icec95.pdf (282 kB)




TITLE: Interactive Evolution

AUTHORS:Wolfgang Banzhaf

SOURCE: Handbook of Evolutionary Computation, IOP Press, Oxford, 1997

ABSTRACT: We present a different approach to directing the evolutionary process through interactive selection of solutions by the human user. First the general context of Interactive Evolution (IE) is set, then the standard IE algorithm is discussed together with more complicated variants. Finally, several application areas are discussed and uses for the new method are exemplified using design from the literature. 

FILENAME: handbk_ie.ps.gz (200 kB)




TITLE: Evolving Turing-complete programs for a register machine with self-modifying code

AUTHORS:Peter Nordin, Wolfgang Banzhaf

SOURCE: Proc. of Int. Conference on Genetic Algorithms, Pittsburgh, 1995

ABSTRACT: The majority of commercial computers today are register machines of von Neumann type. We have developed a method to evolve Turing-complete programs for a register machine. The described implementation enables the use of most program constructs, such as arithmetic operators, large indexed memory, automatic decomposition into subfunctions and subroutines (ADFs), conditional constructs i.e. if-then-else, jumps, loop structures, recursion, protected functions, string and list functions. Any C-function can be compiled and linked into the function set of the system. The use of register machine language allows us to work at the lowest level of binary machine code without any interpreting steps. In a von Neumann machine, programs and data reside in the same memory and the genetic operators can thus directly manipulate the binary machine code in memory. The genetic operators themselves are written in C-language but they modify individuals in binary representation. The result is an execution speed enhancement of up to 100 times compared to an interpreting C-language implementation, and up to 2000 times compared to a LISP implementation. The use of binary machine code demands a very compact coding of about one byte per node in the individual. The resulting evolved programs are disassembled into C-modules and can be incorporated into a conventional software development environment. The low memory requirements and the significant speed enhancement of this technique could be of use when applying genetic programming to new application areas, platforms and research domains. 

FILENAME: icga95-2.pdf (168 kB)




TITLE: Complexity Compression and Evolution

AUTHORS:Peter Nordin, Wolfgang Banzhaf

SOURCE: Proc. of Int. Conference on Genetic Algorithms, Pittsburgh, 1995

ABSTRACT: Compression of information is an important concept in the theory of learning. We argue for the hypothesis that there is an inherent compression pressure towards short, elegant and general solutions in a genetic programming system and other variable length evolutionary algorithms. This pressure becomes visible if the size or complexity of solutions are measured without non-effective code segments called introns. The built in parsimony pressure effects complex fitness functions, crossover probability, generality, maximum depth or length of solutions, explicit parsimony, granularity of fitness function, initialization depth or length, and modularization. Some of these effects are positive and some are negative. In this work we provide a basis for an analysis of these effects and suggestions to overcome the negative implications in order to obtain the balance needed for successful evolution. An empirical investigation that supports our hypothesis is also presented. 

FILENAME: icga95-1.pdf (205 kB)




TITLE: Interactive Evolution of Images

AUTHORS: Jeanine Graf, Wolfgang Banzhaf

SOURCE: Proc. of Int. Conference on Evolutionary Programming, San Diego, 1995

ABSTRACT: Systems of selection and variation by recombination and/or mutation can be used to evolve images for computer graphics and animation. Interactive evolution can be used to direct the development of favorite designs in various application areas. Examples of the application of evolutionary algorithms to two-dimensional (2-D) bitmap images and the methods for three-dimensional (3-D) voxel images are indicated. We show that artificial evolution can serve as a useful tool for achieving flexibility and complexity in image design with only a moderate amount of user-input and detailed knowledge. 

FILENAME: ep95gb.pdf (691 kB)




TITLE: Genotype-Phenotype-Mapping and Neutral Variation --- A case study in Genetic Programming

AUTHORS: Wolfgang Banzhaf

SOURCE: Proceedings PARALLEL PROBLEM SOLVING FROM NATURE III, Y. Davidor, H.-P. Schwefel and R. Männer (Eds.), Springer, Berlin, 1994, pp. 322 --- 332

ABSTRACT: We propose the application of a genotype-phenotype mapping to the solution of constrained optimization problems. The method consists of strictly separating the search space of genotypes from the solution space of phenotypes. A mapping from genotypes into phenotypes provides for the appropriate expression of information represented by the genotypes. The mapping is constructed as to guarantee feasibility of phenotypic solutions for the problem under study. This enforcing of constraints causes multiple genotypes to result in one and the same phenotype. Neutral variants are therefore frequent and play an important role in maintaining genetic diversity. As a specific example, we discuss Binary Genetic Programming (BGP), a variant of Genetic Programming that uses binary strings as genotypes and program trees as phenotypes. 

FILENAME: ppsn94.pdf (164 kB)




TITLE: A Dynamical Implementation of Self-organizing Maps

AUTHORS: Wolfgang Banzhaf

SOURCE: Proceedings 1st. Int. Conf. on Applied Synergetics and Synergetic Engineering (ICASSE-94), Erlangen, F.G. B\"obel, T. Wagner (Eds.), Fraunhofer Institut IIE, 1994, pp. 66 --- 73

ABSTRACT: The standard learning algorithm for self-organizing maps (SOM) involves the two steps of a search for the best matching neuron and of an update of its weight vectors in the neighborhood of this neuron. In the dynamical implementation discussed here, a competitive dynamics of laterally coupled neurons with diffusive interaction is used to find the best-matching neuron. The resulting neuronal excitation bubbles are used to drive a Hebbian learning algorithm that is similar to the one Kohonen uses. Convergence of the SOM is achieved here by relating time (or number of training steps) to the strength of the diffusive coupling. A standard application of the SOM is used to demonstrate the feasibility of the approach. 

FILENAME: ica94.pdf (205 kB)




TITLE: Artificial Selection in a System of Self-Replicating Strings

AUTHORS: Wolfgang Banzhaf

SOURCE: Proceedings of 1st IEEE Conference on Evolutionary Computation (World Congress on Computational Intelligence (WCCI-94)), Orlando, FL, USA, 1994, IEEE Press, Piscataway, Vol. II, pp. 651 --- 655

ABSTRACT: We investigate the use of external selection pressure in a system of self-replicating binary strings. As it turns out, these systems are remarkably flexible in responding to external selection pressure evolving in arbitrarily chosen directions. We introduce different kinds of selection pressure and illustrate their use. 

FILENAME: ci94.pdf (214 kB)




TITLE: Competition as an organizational principle for massively parallel computers?

AUTHORS: Wolfgang Banzhaf

SOURCE: Proceedings of the Workshop on, Physics and Computation, Dallas, TX, 1992, IEEE Computer Society Press, Los Alamitos, pp. 229 --- 231

ABSTRACT: We discuss the idea of using competition as a guiding principle for organizing a parallel computer. We argue that competitive interactions are ubiquous in many systems and deserve to be looked at in parallel computing. We outline some relevant questions which have to be answered in this context. 

FILENAME: dallas92.pdf (91 kB)




Wolfgang Banzhaf
Last updated: Aug 10, 2023