List of Journal Articles

Wolfgang Banzhaf

Some of the older papers might be represented by abstracts only and are available upon email request
We give titles and links. If you click the first words in a title (if underlined) you will see an abstract and source information of the paper. If you click the corresponding filename you will receive a copy via ftp. Alternatively you might use the ftp-service separately.



List of Abstracts and Sources

TITLE: A Genetic Programming Approach to Engineering MRI Reporter Genes

AUTHORS: A.R. Bricco, I. Miralavy, S. Bo, O. Perlman, D.E. Korenchan, C.T. Farrar, M.T. McMahon, W. Banzhaf and A.A. Gilad

SOURCE: ACS Synthetic Biology, Vol 12 (2023) 1154 - 1163

ABSTRACT: Here we develop a mechanism of protein optimization using a computational approach known as ''genetic programming''. We developed an algorithm called Protein Optimization Engineering Tool (POET). Starting from a small library of literature values, the use of this tool allowed us to develop proteins that produce four times more MRI contrast than what was previously state-of-the-art. Interestingly, many of the peptides produced using POET were dramatically different with respect to their sequence and chemical environment than existing CEST producing peptides, and challenge prior understandings of how those peptides function. While existing algorithms for protein engineering rely on divergent evolution, POET relies on convergent evolution and consequently allows discovery of peptides with completely different sequences that perform the same function with as good or even better efficiency. Thus, this novel approach can be expanded beyond developing imaging agents and can be used widely in protein engineering.

FILENAME: ACS2023.pdf (6,000 kB)




TITLE: Coevolutionary Opinion Dynamics with Sparse Interactions in Open-ended Societies

AUTHORS: H. Bao, Z. Neal and W. Banzhaf

SOURCE: Complex and Intelligent Systems, Vol 9 (2023) 565 - 577

ABSTRACT: Opinion dynamics is a crucial topic in complex social systems. However, existing models rarely study limited information accessibility, sparse interactions, and the coevolution of opinion and an open-ended structure. In this paper, we propose the Sparse COevolutionary Open-Ended (SCOOE) model. We address the sparse interaction limitation through extrinsic collective interaction and intrinsic observation based on incomplete neighborhood information. We also consider the coevolution of opinion and open-ended structure by studying structure-opinion co-dynamics when dissidents are leaving and when newcomers with novel opinions are joining. From an opinion dynamics perspective, we find that the proposed mechanisms effectively form lean and fast decision strategies to reduce conflicts under uncertainty. The model is robust in boosting and enhancing a global consensus with only small odds of extreme results. The structure evolves toward a small-world network. We find that an emergent dialectic relationship exists between community segregation and community cohesion viewed from a structural dynamics perspective. We also study the influence of agent heterogeneity under different cognitive ability distributions.

FILENAME: CoevoDynamics2023.pdf (1,600 kB)




TITLE: Iterative Genetic Improvement: Scaling Stochastic Program Synthesis

AUTHORS: Y. Yuan and W. Banzhaf

SOURCE: Artificial Intelligence, Vol 322 (2023) 103962, 1 - 24

ABSTRACT: Program synthesis aims to automatically find programs from an underlying programming language that satisfy a given specification. While this has the potential to revolutionize computing, how to search over the vast space of programs efficiently is an unsolved challenge in program synthesis. In cases where large programs are required for a solution, it is generally believed that stochastic search has advantages over other classes of search techniques. Unfortunately, existing stochastic program synthesizers do not meet this expectation very well, suffering from the scalability issue. To overcome this problem, we propose a new framework for stochastic program synthesis, called iterative genetic improvement. The key idea is to apply genetic improvement to improve a current reference program, and then iteratively replace the reference program by the best program found. Compared to traditional stochastic synthesis approaches, iterative genetic improvement can build up the complexity of programs incrementally in a more robust way. We evaluate the approach on two program synthesis domains: list manipulation and string transformation, along with a number of general program synthesis problems. Our empirical results indicate that this method has considerable advantages over several representative stochastic program synthesizer techniques, both in terms of scalability and of solution quality.

FILENAME: IGI_AIJournal_2023.pdf (1,900 kB)




TITLE: Using Genetic Programming to Predict and Optimize Protein Function

AUTHORS: I. Miralavy, A.R. Bricco, A.A. Gilad and W. Banzhaf

SOURCE: PeerJ Physical Chemistry, Vol 4 (2022) e24, 1 - 24

ABSTRACT: Protein engineers conventionally use tools such as Directed Evolution to find new proteins with better functionalities and traits. More recently, computational techniques and especially machine learning approaches have been recruited to assist Directed Evolution, showing promising results. In this article, we propose POET, a computational Genetic Programming tool based on evolutionary computation methods to enhance screening and mutagenesis in Directed Evolution and help protein engineers to find proteins that have better functionality. As a proof-of-concept, we use peptides that generate MRI contrast detected by the Chemical Exchange Saturation Transfer contrast mechanism. The evolutionary methods used in POET are described, and the performance of POET in different epochs of our experiments with Chemical Exchange Saturation Transfer contrast are studied. Our results indicate that a computational modeling tool like POET can help to find peptides with 400% better functionality than used before.

FILENAME: peerj-pchem-24.pdf (1,700 kB)




TITLE: From Dynamics to Novelty: An Agent-Based Model of the Economic System

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

SOURCE: Artificial Life, Vol 28 Issue 1 (2022) 58 - 95

ABSTRACT: The modern economy is both a complex self-organizing system and an innovative, evolving one. Contemporary theory, however, treats it essentially as a static equilibrium system. Here we propose a formal framework to capture its complex, evolving nature. We develop an agent-based model of an economic system in which firms interact with each other and with consumers through market transactions. Production functions are represented by a pair of von Neumann technology matrices, and firms implement production plans taking into account current price levels for their inputs and output. Prices are determined by the relation between aggregate demand and supply. In the absence of exogenous perturbations the system fluctuates around its equilibrium state. New firms are introduced when profits are above normal, and are ultimately eliminated when losses persist. The varying number of firms represents a recurrent perturbation. The system thus exhibits dynamics at two levels: the dynamics of prices and output, and the dynamics of system size. The model aims to be realistic in its fundamental structure, but is kept simple in order to be computationally efficient. The ultimate aim is to use it as a platform for modeling the structural evolution of an economic system. Currently the model includes one form of structural evolution, the ability to generate new technologies and new products.

FILENAME: alife-economy-2022.pdf (6,000 kB)




TITLE: Long-Term Evolution Experiment with Genetic Programming

AUTHORS: W.B. Langdon and W. Banzhaf

SOURCE: Artificial Life, Vol 28 Issue 2 (2022) 573 - 605

ABSTRACT: We evolve floating point Sextic polynomial populations of genetic programming binary trees for up to a million generations. We observe continued innovation but this is limited by their depth and suggest deep expressions are resilient to learning as they disperse information, impeding evolvability and the adaptation of highly nested organisms and instead we argue for open complexity. Programs with more than 2 000 000 000 instructions (depth 20 000) are created by crossover. To support unbounded long-term evolution experiments LTEE in GP we use incremental fitness evaluation and both SIMD parallel AVX 512 bit instructions and 16 threads to yield performance equivalent to up to 1.1 trillion GP operations per second, 1.1 tera-GPops, on an Intel Xeon Gold 6136 CPU 3.00GHz server.

FILENAME: alife-lte-2022.pdf (5,800 kB)




TITLE: Evolving hierarchical memory-prediction machines in multi-task reinforcement learning

AUTHORS: S. Kelly, T. Voegerl, W. Banzhaf and C. Gondro

SOURCE: Genetic Programming and Evolvable Machines, Vol 22 Issue 4 (2021) 573 - 605

ABSTRACT: A fundamental aspect of intelligent agent behaviour is the ability to encode salient features of experience in memory and use these memories, in combination with current sensory information, to predict the best action for each situation such that long-term objectives are maximized. The world is highly dynamic, and behavioural agents must generalize across a variety of environments and objectives over time. This scenario can be modeled as a partially-observable multi-task reinforcement learning problem. We use genetic programming to evolve highly-generalized agents capable of operating in six unique environments from the control literature, including OpenAIÕs entire Classic Control suite. This requires the agent to support discrete and continuous actions simultaneously. No task-identification sensor inputs are provided, thus agents must identify tasks from the dynamics of state variables alone and define control policies for each task. We show that emergent hierarchical structure in the evolving programs leads to multi-task agents that succeed by performing a temporal decomposition and encoding of the problem environments in memory. The resulting agents are competitive with task-specific agents in all six environments. Furthermore, the hierarchical structure of programs allows for dynamic run-time complexity, which results in relatively efficient operation.

FILENAME: gpem2021.pdf (4,000 kB)




TITLE: Evolutionary Machine Learning: A Survey

AUTHORS: A. Telikani, A. Tahmassebi, W. Banzhaf and A.H. Gandomi

SOURCE: ACM Computing Surveys (CSUR), Vol 54 Issue 8 (2021) 1 - 35

ABSTRACT: Evolutionary Computation (EC) approaches are inspired by nature and solve optimization problems in a stochastic manner. They can offer a reliable and effective approach to address complex problems in real-world applications. EC algorithms have recently been used to improve the performance of Machine Learning (ML) models and the quality of their results. Evolutionary approaches can be used in all three parts of ML: preprocessing (e.g., feature selection and resampling), learning (e.g., parameter setting, membership functions, and neural network topology), and postprocessing (e.g., rule optimization, decision tree/support vectors pruning, and ensemble learning). This article investigates the role of EC algorithms in solving different ML challenges. We do not provide a comprehensive review of evolutionary ML approaches here; instead, we discuss how EC algorithms can contribute to ML by addressing conventional challenges of the artificial intelligence and ML communities. We look at the contributions of EC to ML in nine sub-fields: feature selection, resampling, classifiers, neural networks, reinforcement learning, clustering, association rule mining, and ensemble methods. For each category, we discuss evolutionary machine learning in terms of three aspects: problem formulation, search mechanisms, and fitness value computation. We also consider open issues and challenges that should be addressed in future work.

FILENAME: Open Access, from ACM site




TITLE: Emergent tangled program graphs in partially observable recursive forecasting and ViZDoom navigation tasks

AUTHORS: S. Kelly, R.J. Smith, M.I. Heywood, and W. Banzhaf

SOURCE: ACM Transactions on Evolutionary Learning and Optimization, Vol 1 Issue 3 (2021) 1 - 41

ABSTRACT: Modularity represents a recurring theme in the attempt to scale evolution to the design of complex systems. However, modularity rarely forms the central theme of an artificial approach to evolution. In this work, we report on progress with the recently proposed Tangled Program Graph (TPG) framework in which programs are modules. The combination of the TPG representation and its variation operators enable both teams of programs and graphs of teams of programs to appear in an emergent process. The original development of TPG was limited to tasks with, for the most part, complete information. This work details two recent approaches for scaling TPG to tasks that are dominated by partially observable sources of information using different formulations of indexed memory. One formulation emphasizes the incremental construction of memory, again as an emergent process, resulting in a distributed view of state. The second formulation assumes a single global instance of memory and develops it as a communication medium, thus a single global view of state. The resulting empirical evaluation demonstrates that TPG equipped with memory is able to solve multi-task recursive time-series forecasting problems and visual navigation tasks expressed in two levels of a commercial first-person shooter environment.

FILENAME: telo2021.pdf (6,300 kB)




TITLE: Expensive Multi-Objective Evolutionary Optimization Assisted by Dominance Prediction

AUTHORS: Y. Yuan and W. Banzhaf

SOURCE: IEEE Transactions on Evolutionary Computation, IEEE Early Access, DOI 10.1109/TEVC.2021.3098257

ABSTRACT: We propose a new surrogate-assisted evolutionary algorithm for expensive multi-objective optimization. Two classification-based surrogate models are used, which can predict the Pareto dominance relation and theta-dominance relation between two solutions, respectively. To make such surrogates as accurate as possible, we formulate dominance prediction as an imbalanced classification problem and address this problem using deep learning techniques. Furthermore, to integrate the surrogates based on dominance prediction with multi-objective evolutionary optimization, we develop a two-stage preselection strategy. This strategy aims to select a promising solution to be evaluated among those produced by genetic operations, taking proper account of the balance between convergence and diversity. We conduct an empirical study on a number of well-known multi-and many-objective benchmark problems, over a relatively small number of function evaluations. Our experimental results demonstrate the superiority of the proposed algorithm compared with several representative surrogate-assisted algorithms.

FILENAME: expensive2021.pdf (4,000 kB)




TITLE: Neural Architecture Transfer

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

SOURCE: IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol 43 (2021) 2171 - 2189

ABSTRACT: Neural architecture search (NAS) has emerged as a promising avenue for automatically designing task-specific neural networks. Existing NAS approaches require one complete search for each deployment specification of hardware or objective. This is a computationally impractical endeavor given the potentially large number of application scenarios. In this paper, we propose Neural Architecture Transfer (NAT) to overcome this limitation. NAT is designed to efficiently generate task-specific custom models that are competitive under multiple conflicting objectives. To realize this goal we learn task-specific supernets from which specialized subnets can be sampled without any additional training. The key to our approach is an integrated online transfer learning and many-objective evolutionary search procedure. A pre-trained supernet is iteratively adapted while simultaneously searching for task-specific subnets. We demonstrate the efficacy of NAT on 11 benchmark image classification tasks ranging from large-scale multi-class to small-scale fine-grained datasets. In all cases, including ImageNet, NATNets improve upon the state-of-the-art under mobile settings (²² 600M Multiply-Adds). Surprisingly, small-scale fine-grained datasets benefit the most from NAT. At the same time, the architecture search and transfer is orders of magnitude more efficient than existing NAS methods. Overall, experimental evaluation indicates that, across diverse image classification tasks and computational objectives, NAT is an appreciably more effective alternative to conventional transfer learning of fine-tuning weights of an existing network architecture learned on standard datasets. Code is available at https://github.com/human-analysis/neural-architecture-transfer.

FILENAME: Neural_Architecture_Transfer2021.pdf (2,400 kB)




TITLE: The effects of taxes on wealth inequality in Artificial Chemistry models of economic activity

AUTHORS: W. Banzhaf

SOURCE: PLoS ONE, Vol 16 Issue 8 (2021) e0255719

ABSTRACT: We consider a number of Artificial Chemistry models for economic activity and what consequences they have for the formation of economic inequality. We are particularly interested in what tax measures are effective in dampening economic inequality. By starting from well-known kinetic exchange models, we examine different scenarios for reducing the tendency of economic activity models to form unequal wealth distribution in equilibrium.


TITLE: Multi-Objective Evolutionary Design of Deep Convolutional Neural Networks for Image Classification

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

SOURCE: IEEE Transactions on Evolutionary Computation, Vol 25 Issue 2 (2020) 277 - 291

ABSTRACT: Convolutional neural networks (CNNs) are the backbones of deep learning paradigms for numerous vision tasks. Early advancements in CNN architectures are primarily driven by human expertise and by elaborate design processes. Recently, neural architecture search was proposed with the aim of automating the network design process and generating task-dependent architectures. While existing approaches have achieved competitive performance in image classification, they are not well suited to problems where the computational budget is limited for two reasons: (1) the obtained architectures are either solely optimized for classification performance, or only for one deployment scenario; (2) the search process requires vast computational resources in most approaches. To overcome these limitations, we propose an evolutionary algorithm for searching neural architectures under multiple objectives, such as classification performance and floating point operations (FLOPs). The proposed method addresses the first shortcoming by populating a set of architectures to approximate the entire Pareto frontier through genetic operations that recombine and modify architectural components progressively. Our approach improves computational efficiency by carefully down-scaling the architectures during the search as well as reinforcing the patterns commonly shared among past successful architectures through Bayesian model learning. The integration of these two main contributions allows an efficient design of architectures that are competitive and in most cases outperform both manually and automatically designed architectures on benchmark image classification datasets: CIFAR, ImageNet and human chest X-ray. The flexibility provided from simultaneously obtaining multiple architecture choices for different compute requirements further differentiates our approach from other methods in the literature.


TITLE: Towards Better Evolutionary Software Repair

AUTHORS: Y. Yuan and W. Banzhaf

SOURCE: ACM Transactions on Software Engineering and Methodology Vol 29 Issue 1 (2020) 5:1-53

ABSTRACT: Bug repair is a major component of software maintenance, which requires a huge amount of manpower. Evolutionary computation, particularly genetic programming (GP), is a class of promising techniques for automating this time-consuming and expensive process. Although recent research in evolutionary program repair has made significant progress, major challenges still remain. In this article, we propose ARJA-e, a new evolutionary repair system for Java code that aims to address challenges for the search space, search algorithm, and patch overfitting. To determine a search space that is more likely to contain correct patches, ARJA-e combines two sources of fix ingredients (i.e., the statement-level redundancy assumption and repair templates) with contextual analysis-based search space reduction, thereby leveraging their complementary strengths. To encode patches in GP more properly, ARJA-e unifies the edits at different granularities into statement-level edits and then uses a lower-granularity patch representation that is characterized by the decoupling of statements for replacement and statements for insertion. ARJA-e also uses a finer-grained fitness function that can make full use of semantic information contained in the test suite, which is expected to better guide the search of GP. To alleviate patch overfitting, ARJA-e further includes a postprocessing tool that can serve the purposes of overfit detection and patch ranking. We evaluate ARJA-e on 224 real Java bugs from Defects4J and compare it with the state-of-the-art repair techniques. The evaluation results show that ARJA-e can correctly fix 39 bugs in terms of the patches ranked first, achieving substantial performance improvements over the state of the art. In addition, we analyze the effect of the components of ARJA-e qualitatively and quantitatively to demonstrate their effectiveness and advantages.


TITLE: A Network Perspective on Genotype-Phenotype Mapping in Genetic Programming

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

SOURCE: Genetic Programming and Evolvable Machines, Vol 21 (2020) 375 - 397

ABSTRACT: Genotype-phenotype mapping plays an essential role in the design of an evolutionary algorithm. Variation occurs at the genotypic level but fitness is evaluated at the phenotypic level, therefore, this mapping determines if and how variations are effectively translated into quality improvements. In evolutionary algorithms, this mapping has often been observed as highly redundant, i.e., multiple genotypes can map to the same phenotype, as well as heterogeneous, i.e., some phenotypes are represented by a large number of genotypes while some phenotypes only have few. We numerically study the redundant genotype-phenotype mapping of a simple Boolean linear genetic programming system and quantify the mutational connections among phenotypes using tools of complex network analysis. The analysis yields several interesting statistics of the phenotype network. We show the evidence and provide explanations for the observation that some phenotypes are much more difficult to find as the target of a search than others. Our study provides a quantitative analysis framework to better understand the genotype-phenotype map, and the results may be utilized to inspire algorithm design that allows the search of a difficult target to be more effective.

FILENAME: gpem2020.pdf (1,300 kB)




TITLE: Time and Individual Duration in Genetic Programming

AUTHORS: F. Fernandez de Vega, G. Olague, D. Lanza, W. Banzhaf, E. Goodman, J. Menendez-Clavijo and A. Martinez

SOURCE: IEEE ACCESS Vol 8 (2020) 38692 - 38713

ABSTRACT: This paper presents a new way of measuring complexity in variable-size-chromosome-based evolutionary algorithms. Dealing with complexity is particularly useful when considering bloat in Genetic Programming. Instead of analyzing size growth, we focus on the time required for individuals' fitness evaluations, which correlates with size. This way, we consider time and space as two sides of a single coin when devising a more natural method for fighting bloat. We thus view the problem from a perspective that departs from traditional methods applied in Genetic Programming. We have analyzed first the behavior of individuals across generations, taking into account their fitness evaluation times, thus providing clues about the general practice of the evolutionary process when modern parallel and distributed computers are used to run the algorithm. This new perspective allows us to understand that new methods for bloat control can be derived. Moreover, we develop from this framework a first proposal to show the usefulness of the idea: to group individuals in classes according to computing time required for evaluation, automatically accomplished by parallel and distributed systems without any change in the underlying algorithm, when they are only allowed to breed within their classes. Experimental data confirms the strength of the approach: using computing time as a measure of individuals' complexity allows control of the natural size growth of genetic programming individuals while preserving the quality of solutions in both the parallel and sequential versions of the algorithm.


TITLE: An Intelligent Model for the Prediction of Bond Strength of FRP Bars in Concrete: A Soft Computing Approach

AUTHORS: H. Bolandi, W. Banzhaf, N. Lajnef, K. Barri, A.H. Alavi

SOURCE: Technologies Vol 7, Issue 2 (2019) 42

ABSTRACT: Accurate prediction of bond behavior of fiber reinforcement polymer (FRP) concrete has a pivotal role in the construction industry. This paper presents a soft computing method called multi-gene genetic programming (MGGP) to develop an intelligent prediction model for the bond strength of FRP bars in concrete. The main advantage of the MGGP method over other similar methods is that it can formulate the bond strength by combining the capabilities of both standard genetic programming and classical regression. A number of parameters affecting the bond strength of FRP bars were identified and fed into the MGGP algorithm. The algorithm was trained using an experimental database including 223 test results collected from the literature. The proposed MGGP model accurately predicts the bond strength of FRP bars in concrete. The newly defined predictor variables were found to be efficient in characterizing the bond strength. The derived equation has better performance than the widely-used American Concrete Institute (ACI) model.


TITLE: ARJA: Automated Repair of Java Programs via Multi-Objective Genetic Programming

AUTHORS: Y. Yuan and W. Banzhaf

SOURCE: IEEE Transactions on Software Engineering, Vol 46 (2020) 1040 - 1067

ABSTRACT: Automated program repair is the problem of automatically fixing bugs in programs in order to significantly reduce the debugging costs and improve the software quality. To address this problem, test-suite based repair techniques regard a given test suite as an oracle and modify the input buggy program to make the entire test suite pass. GenProg is well recognized as a prominent repair approach of this kind, which uses genetic programming (GP) to rearrange the statements already extant in the buggy program. However, recent empirical studies show that the performance of GenProg is not fully satisfactory, particularly for Java. In this paper, we propose ARJA, a new GP based repair approach for automated repair of Java programs. To be specific, we present a novel lower-granularity patch representation that properly decouples the search subspaces of likely-buggy locations, operation types and potential fix ingredients, enabling GP to explore the search space more effectively. Based on this new representation, we formulate automated program repair as a multi-objective search problem and use NSGA-II to look for simpler repairs. To reduce the computational effort and search space, we introduce a test filtering procedure that can speed up the fitness evaluation of GP and three types of rules that can be applied to avoid unnecessary manipulations of the code. Moreover, we also propose a type matching strategy that can create new potential fix ingredients by exploiting the syntactic patterns of existing statements. We conduct a large-scale empirical evaluation of ARJA along with its variants on both seeded bugs and real-world bugs in comparison with several state-of-the-art repair approaches. Our results verify the effectiveness and efficiency of the search mechanisms employed in ARJA and also show its superiority over the other approaches. In particular, compared to jGenProg (an implementation of GenProg for Java), an ARJA version fully following the redundancy assumption can generate a test-suite adequate patch for more than twice the number of bugs (from 27 to 59), and a correct patch for nearly four times of the number (from 5 to 18), on 224 real-world bugs considered in Defects4J. Furthermore, ARJA is able to correctly fix several real multi-location bugs that are hard to be repaired by most of the existing repair approaches.


TITLE: Prediction of normalized signal strength on DNA-sequencing microarrays by n-grams within a neural network model

AUTHORS: C. Chilaka, S. Carr, N. Shalaby and W. Banzhaf

SOURCE: Bioinformation Vol 15 (2019) 388 - 393

ABSTRACT: We have shown previously that a feed-forward, back propagation neural network model based on composite n-grams can predict normalized signal strengths of a microarray based DNA sequencing experiment. The microarray comprises a 4xN set of 25-base single-stranded DNA molecule (ÓoligosÓ), specific for each of the four possible bases (A, C, G, or T) for Ade- nine, Cytosine, Guanine and Thymine respectively at each of N positions in the experimental DNA. Strength of binding between reference oligos and experimental DNA varies according to base complementarity and the strongest signal in any quartet should `call the base` at that position. Variation in base composition of and (or) order within oligos can affect accuracy and (or) confidence of base calls. To evaluate the effect of order, we present oligos as n-gram neural input vectors of degree 3 and measure their performance. Microarray signal intensity data were divided into training, validation and testing sets. Regression values obtained were >99.80% overall with very low mean square errors that transform to high best validation performance values. Pattern recognition results showed high percentage confusion matrix values along the diagonal and receiver operating characteristic curves were clustered in the upper left corner, both indices of good predictive performance. Higher order n-grams are expected to produce even better predictions.


TITLE: Drone Squadron Optimization: a novel self-adaptive algorithm for global numerical optimization

AUTHORS: V. de Melo and W. Banzhaf

SOURCE: Neural Computing and Applications Vol 30 (2018) 3117 - 3144

ABSTRACT: This paper proposes Drone Squadron Optimization (DSO), a new self-adaptive metaheuristic for global numerical optimization which is updated online by a hyper-heuristic. DSO is an artifact-inspired technique, as opposed to many nature-inspired algorithms used today. DSO is very flexible because it is not related to natural behaviors or phenomena. DSO has two core parts: the semiautonomous drones that fly over a landscape to explore, and the command center that processes the retrieved data and updates the dronesÕ firmware whenever necessary. The self-adaptive aspect of DSO in this work is the perturbation/movement scheme, which is the procedure used to generate target coordinates. This procedure is evolved by the command center during the global optimization process in order to adapt DSO to the search landscape. We evaluated DSO on a set of widely employed single-objective benchmark functions. The statistical analysis of the results shows that the proposed method is competitive with the other methods, but we plan several future improvements to make it more powerful and robust.


TITLE: Automatic feature engineering for regression models with machine learning: An evolutionary computation and statistics hybrid

AUTHORS: V. de Melo and W. Banzhaf

SOURCE: Information Sciences Vol 430-431 (2018) 287 - 313

ABSTRACT: Symbolic Regression (SR) is a well-studied task in Evolutionary Computation (EC), where adequate free-form mathematical models must be automatically discovered from observed data. Statisticians, engineers, and general data scientists still prefer traditional regression methods over EC methods because of the solid mathematical foundations, the interpretability of the models, and the lack of randomness, even though such deterministic methods tend to provide lower quality prediction than stochastic EC methods. On the other hand, while EC solutions can be big and uninterpretable, they can be created with less bias, finding high-quality solutions that would be avoided by human researchers. Another interesting possibility is using EC methods to perform automatic feature engineering for a deterministic regression method instead of evolving a single model; this may lead to smaller solutions that can be easy to understand. In this contribution, we evaluate an approach called Kaizen Programming (KP) to develop a hybrid method employing EC and Statistics. While the EC method builds the features, the statistical method efficiently builds the models, which are also used to provide the importance of the features; thus, features are improved over the iterations resulting in better models. Here we examine a large set of benchmark SR problems known from the EC literature. Our experiments show that KP outperforms traditional Genetic Programming - a popular EC method for SR - and also shows improvements over other methods, including other hybrids and well-known statistical and Machine Learning (ML) ones. More in line with ML than EC approaches, KP is able to provide high-quality solutions while requiring only a small number of function evaluations.


TITLE: Artificial Genetic Regulatory Networks - A Review, 2018

AUTHORS: S. Cussat-Blanc, K. Harrington and W. Banzhaf

SOURCE: Artificial Life Vol 24 Issue 4 (2018) 296 - 328 (OPEN ACCESS)

ABSTRACT: In nature, gene regulatory networks are a key mediator between the information stored in the DNA of living organisms (their genotype) and the structural and behavioral expression this finds in their bodies, surviving in the world (their phenotype). They integrate environmental signals, steer development, buffer stochasticity, and allow evolution to proceed. In engineering, modeling and implementations of artificial gene regulatory networks have been an expanding field of research and development over the past few decades. This review discusses the concept of gene regulation, describes the current state of the art in gene regulatory networks, including modeling and simulation, and reviews their use in artificial evolutionary settings. We provide evidence for the benefits of this concept in natural and the engineering domains.


TITLE: Use of a neural network to predict normalized signal strengths from a DNA sequencing microarray

AUTHORS: C. Chilaka, S. Carr, N. Shalaby and W. Banzhaf

SOURCE: Bioinformation Vol 13 (2017) 313 - 317

ABSTRACT: A microarray DNA sequencing experiment for a molecule of N bases produces a 4xN data matrix, where for each of the N positions each quartet comprises the signal strength of binding of an experimental DNA to a reference oligonucleotide affixed to the microarray, for the four possible bases (A, C, G, or T). The strongest signal in each quartet should result from a perfect complementary match between experimental and reference DNA sequence, and therefore indicate the correct base call at that position. The linear series of calls should constitute the DNA sequence. Variation in the absolute and relative signal strengths, due to variable base composition and other factors over the N quartets, can interfere with the accuracy and (or) confidence of base calls in ways that are not fully understood. We used a feed-forward back-propagation neural network model to predict normalized signal intensities of a microarray-derived DNA sequence of N = 15,453 bases. The DNA sequence was encoded as n-gram neural input vectors, where n = 1, 2, and their composite. The data were divided into training, validation, and testing sets. Regression values were >99% overall, and improved with increased number of neurons in the hidden layer, and in the composition n-grams. We also noticed a very low mean square error overall which transforms to a high performance value.


TITLE: Improving the prediction of material properties of concrete using Kaizen Programming with Simulated Annealing

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

SOURCE: Neurocomputing, Vol 246 (2017) 25 - 44

ABSTRACT: Predicting the properties of materials like concrete has been proven a difficult task given the complex interactions among its components. Over the years, researchers have used Statistics, Machine Learning, and Evolutionary Computation to build models in an attempt to accurately predict such properties. High-quality models are often non-linear, justifying the study of nonlinear regression tools. In this paper, we employ a traditional multiple linear regression method by ordinary least squares to solve the task. However, the model is built upon nonlinear features automatically engineered by Kaizen Programming, a recently proposed hybrid method. Experimental results show that Kaizen Programming can find low-correlated features in an acceptable computational time. Such features build high-quality models with better predictive quality than results reported in the literature.

FILENAME: Neurocomputing2017.pdf (3900 kB)




TITLE: Open-Ended Evolution: Perspectives from the OEE1 Workshop in York

AUTHORS: T. Taylor, M. Bedau, A. Channon, D. Ackley, W. Banzhaf, G. Beslon, E. Dolson, T. Froese, S. Hickinbotham, T. Ikegami, B. McMullin, N. Packard, S. Rasmussen, N. Virgo, E. Agmon, E. Clark, S. McGregor, C. Ofria, G. Ropella, L. Spector, K.O. Stanley, A. Stanton, C. Timperley, A. Vostinar, M. Wiser

SOURCE: Artificial Life, Vol 22 (2016) 408 - 423

ABSTRACT: We describe the content and outcomes of the First Workshop on Open-Ended Evolution: Recent Progress and Future Milestones (OEE1), held during the ECAL 2015 conference at the University of York, UK, in July 2015. We briefly summarize the content of the workshop's talks, and identify the main themes that emerged from the open discussions. Two important conclusions from the discussions are: (1) the idea of pluralism about OEE - it seems clear that there is more than one interesting and important kind of OEE; and (2) the importance of distinguishing observable behavioral hallmarks of systems undergoing OEE from hypothesized underlying mechanisms that explain why a system exhibits those hallmarks. We summarize the different hallmarks and mechanisms discussed during the workshop, and list the specific systems that were highlighted with respect to particular hallmarks and mechanisms. We conclude by identifying some of the most important open research questions about OEE that are apparent in light of the discussions. The York workshop provides a foundation for a follow-up OEE2 workshop taking place at the ALIFE XV conference in Cancœn, Mexico, in July 2016. Additional materials from the York workshop, including talk abstracts, presentation slides, and videos of each talk, are available at http://alife.org/ws/oee1.

FILENAME: OEE1_2016.pdf (187 kB)




TITLE: Defining and Simulating Open-Ended Novelty: Requirements, Guidelines, and Challenges

AUTHORS: W. Banzhaf, B. Baumgaertner, G. Beslon, R. Doursat, J.A. Foster, B. McMullin, V.V. de Melo, T. Miconi, L. Spector, S. Stepney and R. White

SOURCE: Theory in Biosciences, Vol 135 (2016) 131 - 161

ABSTRACT: The open-endedness of a system is often defined as a continual production of novelty. Here we pin down this concept more fully by defining several types of novelty that a system may exhibit, classified as variation, innovation, and emergence. We then provide a meta-model for including levels of structure in a system's model. From there, we define an architecture suitable for building simulations of open-ended novelty-generating systems and discuss how previously proposed systems fit into this framework. We discuss the design principles applicable to those systems and close with some challenges for the community.

FILENAME: OEE_2016.pdf (1.3 MB)




TITLE: The Effects of Recombination on Phenotypic Exploration and Robustness in Evolution

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

SOURCE: Artificial Life, Vol 20 (2014) 457 - 470

ABSTRACT: Recombination is a commonly used genetic operator in artificial and computational evolutionary systems. It has been empirically shown to be essential for evolutionary processes. However, little has been done to analyze the effects of recombination on quantitative genotypic and phenotypic properties. The majority of studies only consider mutation, mainly due to the more serious consequences of recombination in reorganizing entire genomes. Here we adopt methods from evolutionary biology to analyze a simple, yet representative, genetic programming method, linear genetic programming. We demonstrate that recombination has less disruptive effects on phenotype than mutation, that it accelerates novel phenotypic exploration, and that it particularly promotes robust phenotypes and evolves genotypic robustness and synergistic epistasis. Our results corroborate an explanation for the prevalence of recombination in complex living organisms, and helps elucidate a better understanding of the evolutionary mechanisms involved in the design of complex artificial evolutionary systems and intelligent algorithms.

FILENAME: ALIFE2014.pdf (480 kB)




TITLE: Cache Consensus: Rapid Object Sorting by a Robotic Swarm

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

SOURCE: Swarm Intelligence, Vol 8 (2014) 61 - 87

ABSTRACT: We present a new method which allows a swarm of robots to sort arbitrarily arranged objects into homogeneous clusters. In the ideal case, a distributed robotic sorting method should establish a single homogeneous cluster for each object type. This can be achieved with existing methods, but the rate of convergence is considered too slow for real-world application. Previous research on distributed robotic sorting is typified by randomised movement with a pick-up/deposit behaviour that is a probabilistic function of local object density. We investigate whether the ability of each robot to localise and return to remembered places can improve distributed sorting performance. In our method, each robot maintains a cache point for each object type. Upon collecting an object, it returns to add this object to the cluster surrounding the cache point. Similar to previous biologically inspired work on distributed sorting, no explicit communication between robots is implemented. However, the robots can still come to a consensus on the best cache for each object type by observing clusters and comparing their sizes with remembered cache sizes. We refer to this method as cache consensus. Our results indicate that incorporating this localisation capability enables a significant improvement in the rate of convergence. We present experimental results using a realistic simulation of our targeted robotic platform. A subset of these experiments is also validated on physical robots.

FILENAME: CacheConsensus.pdf (2600 kB)




TITLE: Response to comments on "Genetic Programming and Emergence"

AUTHORS: W. Banzhaf

SOURCE: Genetic Programming and Evolvable Machines, Vol 15 (2014) 103 - 108

ABSTRACT:

FILENAME: Response_GP_and_Emergence.pdf (95 kB)




TITLE: Genetic Programming and Emergence

AUTHORS: W. Banzhaf

SOURCE: Genetic Programming and Evolvable Machines, Vol 15 (2014) 63 - 73

ABSTRACT: Emergence and its accompanying phenomena are a widespread process in nature. Despite its prominence, there is no agreement in the sciences about the concept and how to define or measure emergence. One of the most contentious issues discussed is that of top-down (or downward) causation as a defining characteristic of systems with emergence. In this contribution we shall argue that emergence happens in Genetic Programming, for all the world to see.

FILENAME: GP_and_Emergence.pdf (304 kB)




TITLE: Recovery Properties of Distributed Cluster Head Election using Reaction Diffusion

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

SOURCE: Swarm Intelligence, Vol 5 (2011) 225 - 255

ABSTRACT: Chemical reactionÐdiffusion is a basic component of morphogenesis, and can be used to obtain interesting and unconventional self-organizing algorithms for swarms of autonomous agents, using natural or artificial chemistries. However, the performance of these algorithms in the face of disruptions has not been sufficiently studied. In this paper we evaluate the use of reactionÐdiffusion for the morphogenetic engineering of distributed coordination algorithms, in particular, cluster head election in a distributed computer system. We consider variants of reactionÐdiffusion systems around the activatorÐinhibitor model, able to produce spot patterns. We evaluate the robustness of these models against the deletion of activator peaks that signal the location of cluster heads, and the destruction of large patches of chemicals. Three models are selected for evaluation: the GiererÐMeinhardt ActivatorÐ Inhibitor model, the ActivatorÐSubstrate Depleted model, and the GrayÐScott model. Our results reveal a trade-off between these models. The GiererÐMeinhardt model is more stable, with rare failures, but is slower to recover from disruptions. The GrayÐScott model is able to recover more quickly, at the expense of more frequent failures. The ActivatorÐSubstrate model lies somewhere in the middle.

FILENAME: SwarmIntelligence2011.pdf (2,500 kB)




TITLE: Evolutionary dynamics on multiple scales: a quantitative analysis of the interplay between genotype, phenotype and fitness in linear genetic programming

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

SOURCE: Genetic Programming and Evolvable Machines, Vol 13 (2012) 305 - 337

ABSTRACT: Redundancy is a ubiquitous feature of genetic programming (GP), with many-to-one mappings commonly observed between genotype and phenotype, and between phenotype and fitness. If a representation is redundant, then neutral mutations are possible. A mutation is phenotypically-neutral if its application to a genotype does not lead to a change in phenotype. A mutation is fitness-neutral if its application to a genotype does not lead to a change in fitness. Whether such neutrality has any benefit for GP remains a contentious topic, with reported experimental results supporting both sides of the debate. Most existing studies use performance statistics, such as success rate or search efficiency, to investigate the utility of neutrality in GP. Here, we take a different tack and use a measure of robustness to quantify the neutrality associated with each genotype, phenotype, and fitness value. We argue that understanding the influence of neutrality on GP requires an understanding of the distributions of robustness at these three levels, and of the interplay between robustness, evolvability, and accessibility amongst genotypes, phenotypes, and fitness values. 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 quantities, which we then relate to the dynamical properties of simple mutation-based evolutionary processes. Our results demonstrate that it is not only the distribution of robustness amongst phenotypes that affects evolutionary search, but also (1) the distributions of robustness at the genotypic and fitness levels and (2) the mutational biases that exist amongst genotypes, phenotypes, and fitness values. Of crucial importance is the relationship between the robustness of a genotype and its mutational bias toward other phenotypes.

FILENAME: GPEM-Multiscale2012.pdf (1,200 kB)




TITLE: Open Issues in Genetic Programming

AUTHORS: M. O'Neill, L. Vanneschi, S. Gustafson and W. Banzhaf

SOURCE: Genetic Programming and Evolvable Machines, Vol 11 (2010) 339 - 363

ABSTRACT: It is approximately 50 years since the first computational experiments were conducted in what has become known today as the field of Genetic Programming (GP), twenty years since John Koza named and popularised the method, and ten years since the first issue appeared of the Genetic Programming & Evolvable Machines journal. In particular, during the past two decades there has been a significant range and volume of development in the theory and application of GP, and in recent years the field has become increasingly applied. There remain a number of significant open issues despite the successful application of GP to a number of challenging real-world problem domains and progress in the development of a theory explaining the behavior and dynamics of GP. These issues must be addressed for GP to realise its full potential and to become a trusted mainstream member of the computational problem solving toolkit. In this paper we outline some of the challenges and open issues that face researchers and practitioners of GP. We hope this overview will stimulate debate, focus the direction of future research to deepen our understanding of GP, and further the development of more powerful problem solving algorithms.

FILENAME: GPEM-OpenIssues2010.pdf (276 kB)




TITLE: Developments in Cartesian Genetic Programming: Self-Modifying CGP

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

SOURCE: Genetic Programming and Evolvable Machines, Vol 11 (2010) 397 - 439

ABSTRACT: Self-modifying Cartesian Genetic Programming (SMCGP) is a general purpose, graph-based, developmental form of Genetic Programming founded on Cartesian Genetic Programming. In addition to the usual computational functions, it includes functions that can modify the program encoded in the genotype. This means that programs can be iterated to produce an infinite sequence of programs (phenotypes) from a single evolved genotype. It also allows programs to acquire more inputs and produce more outputs during this iteration. We discuss how SMCGP can be used and the results obtained in several different problem domains, including digital circuits, generation of patterns and sequences, and mathematical problems. We find that SMCGP can efficiently solve all the problems studied. In addition, we prove mathematically that evolved programs can provide general solutions to a number of problems: n-input even-parity, n-input adder, and sequence approximation to pi.

FILENAME: GPEM-SMCGP2010.pdf (1,100 kB)




TITLE: Variable population size and evolution acceleration: a case study with a parallel evolutionary algorithm

AUTHORS: T. Hu, S. Harding and W. Banzhaf

SOURCE: Genetic Programming and Evolvable Machines, Vol 11 (2010) 205 - 225

ABSTRACT: With current developments of parallel and distributed computing, evolutionary algorithms have benefited considerably from parallelization techniques. Besides improved computation efficiency, parallelization may bring about innovation to many aspects of evolutionary algorithms. In this article, we focus on the effect of variable population size on accelerating evolution in the context of a parallel evolutionary algorithm. In nature it is observed that dramatic variations of population size have considerable impact on evolution. Interestingly, the property of variable population size here arises implicitly and naturally from the algorithm rather than through intentional design. To investigate the effect of variable population size in such a parallel algorithm, evolution dynamics, including fitness progression and population diversity variation, are analyzed. Further, this parallel algorithm is compared to a conventional fixed-population-size genetic algorithm. We observe that the dramatic changes in population size allow evolution to accelerate.

FILENAME: GPEM-VarPop2010.pdf (972 kB)




TITLE: Deployment of parallel linear genetic programming using GPUs on PC and video game console platforms

AUTHORS: G. Wilson and W. Banzhaf

SOURCE: Genetic Programming and Evolvable Machines, Vol 11 (2010) 147 - 184

ABSTRACT: We present a general method for deploying parallel linear genetic programming (LGP) to the PC and Xbox 360 video game console by using a publicly available common framework for the devices called XNA (for "XNA is Not Acronymed"). By constructing the LGP within this framework, we effectively produce an LGP "game" for PC and XBox 360 that displays results as they evolve. We use the GPU of each device to parallelize fitness evaluation and the mutation operator of the LGP algorithm, thus providing a general LGP implementation suitable for parallel computation on heterogeneous devices. While parallel GP implementations on PCs are now common, both the implementation of GP on a video game console using GPU and the construction of a GP around a framework for heterogeneous devices are novel contributions. The objective of this work is to describe how to implement the parallel execution of LGP in order to use the underlying hardware (especially GPU) on the different platforms while still maintaining loyalty to the general methodology of the LGP algorithm built for the common framework. We discuss the implementation of texture-based data structures and the sequential and parallel algorithms built for their use on both CPU and GPU. Following the description of the general algorithm, the particular tailoring of the implementations for each hardware platform is described. Sequential (CPU) and parallel (GPU-based) algorithm performance is compared on both PC and video game platforms using the metrics of GP operations per second, actual time elapsed, speedup of parallel over sequential implementation, and percentage of execution time used by the GPU versus CPU.

FILENAME: GPEM-Xbox2010.pdf (3,000 kB)




TITLE: Evolvability and Speed of Evolutionary Algorithms in Light of Recent Developments in Biology

AUTHORS: T. Hu and W. Banzhaf

SOURCE: Journal of Artificial Evolution and Applications, Vol 2010 (2010) 568375-1 -- 568375-28, available from http://www.hindawi.com/archive/2010/568375/

ABSTRACT: Biological and artificial evolutionary systems exhibit varying degrees of evolvability and different rates of evolution. Such quantities can be affected by various factors. Here, we review some evolutionary mechanisms and discuss new developments in biology that can potentially improve evolvability or accelerate evolution in artificial systems. Biological notions are discussed to the degree they correspond to notions in Evolutionary Computation. We hope that the findings put forward here can be used to design computational models of evolution that produce significant gains in evolvability and evolutionary speed.

FILENAME: JAEA2010.pdf (494 kB)




TITLE: An informed genetic algorithm for the examination timetabling problem

AUTHORS: N. Pillay and W. Banzhaf

SOURCE: Applied Soft Computing, 10 (2010) 457 - 467 available as doi:10.1016/j.asoc.2009.08.011

ABSTRACT: This paper presents the results of a study conducted to investigate the use of genetic algorithms (GAs) as a means of inducing solutions to the examination timetabling problem (ETP). This study differs from previous efforts applying genetic algorithms to this domain in that firstly it takes a two-phased approach to the problem which focuses on producing timetables that meet the hard constraints during the first phase, while improvements are made to these timetables in the second phase so as to reduce the soft constraint costs. Secondly, domain specific knowledge in the form of heuristics is used to guide the evolutionary process. The system was tested on a set of 13 real-world problems, namely, the Carter benchmarks. The performance of the system on the benchmarks is comparable to that of other evolutionary techniques and in some cases the system was found to outperform these techniques. Furthermore, the quality of the examination timetables evolved is within range of the best results produced in the field.

FILENAME: ASOC651.pdf (494 kB)




TITLE: The use of Computational Intelligence in Intrusion Detection Systems: A Review

AUTHORS: S.X. Wu and W. Banzhaf

SOURCE: Applied Soft Computing, 10 (2010) 1 - 35 available as doi:10.1016/j.asoc.2009.06.019

ABSTRACT: Intrusion detection based upon computational intelligence is currently attracting considerable interest from the research community. Characteristics of computational intelligence (CI) systems, such as adaptation, fault tolerance, high computational speed and error resilience in the face of noisy information, fit the requirements of building a good intrusion detection model. Here we want to provide an overview of the research progress in applying CI methods to the problem of intrusion detection. The scope of this review will encompass core methods of CI, including artificial neural networks, fuzzy systems, evolutionary computation, artificial immune systems, swarm intelligence, and soft computing. The research contributions in each field are systematically summarized and compared, allowing us to clearly define existing research challenges, and to highlight promising new research directions. The findings of this review should provide useful insights into the current IDS literature and be a good source for anyone who is interested in the application of CI approaches to IDSs or related fields.

FILENAME: ASOC2010.pdf (1554 kB)




TITLE: A study of heuristic combinations for hyper-heuristic systems for the uncapacitated examination timetabling problem

AUTHORS: N. Pillay and W. Banzhaf

SOURCE: European Journal of Operations Research, 197 (2009) 482 - 491

ABSTRACT: Research in the domain of examination timetabling is moving towards developing methods that generalise well over a range of problems. This is achieved by implementing hyper-heuristic systems to find the best heuristic or heuristic combination to allocate examinations when constructing a timetable for a problem. Heuristic combinations usually take the form of a list of low-level heuristics that are applied sequentially. This study proposes an alternative representation for heuristic combinations, namely, a hierarchical combination of heuristics. Furthermore, the heuristics in each combination are applied simultaneously rather than sequentially. The study also introduces a new low-level heuristic, namely, highest cost. A set of heuristic combinations of this format have been tested on the 13 Carter benchmarks. The quality of the examination timetables induced using these combinations are comparable to, and in some cases better than, those produced by hyper-heuristic systems combining and applying heuristic combinations sequentially.

FILENAME: ejor2008.pdf (254 kB)




TITLE: Genetic Programming on GPUs for Image Processing

AUTHORS: S. Harding and W. Banzhaf

SOURCE: International Journal of High-Performance Systems Architecture, 1 (2008) 231 - 240

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. The parallel processors available on modern graphics cards can be used to greatly increase the speed of evaluation. Previous papers in this area dealt with tasks such as 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: ( kB)




TITLE: Repeated Patterns in Genetic Programming

AUTHORS: W.B. Langdon and W. Banzhaf

SOURCE: Natural Computing, 7 (2008) 589 - 613

ABSTRACT: Evolved genetic programming trees contain many repeated code fragments. Size fair crossover limits bloat in automatic programming, preventing the evolution of recurring motifs. We examine these complex properties in detail using depth vs. size Catalan binary tree shape plots, subgraph and subtree matching, information entropy, sensitivity analysis, syntactic and semantic fitness correlations. Programs evolve in a self-similar fashion, akin to fractal random trees, with diffuse introns. Data mining frequent patterns reveals that as software is progressively improved a large proportion of it is exactly repeated subtrees as well as exactly repeated subgraphs. We relate this emergent phenomenon to building blocks in GP and suggest GP works by jumbling subtrees which already have high fitness on the whole problem to give incremental improvements and create complete solutions with multiple identical components of different importance.

FILENAME: natcomp2008.pdf (1,421 kB)




TITLE: Evolving Blackbox Quantum Algorithms using Genetic Programming, 2008

AUTHORS: R. Stadelhofer, W. Banzhaf and D. Suter

SOURCE: Artificial Intelligence for Engineering Design, Analysis and Manufacturing, 22 (2008) 285 - 297

ABSTRACT: Although it is known that quantum computers can solve certain computational problems exponentially faster than classical computers, only a small number of quantum algorithms have been developed so far. Designing such algorithms is complicated by the rather nonintuitive character of quantum physics. In this paper we present a genetic programming system that uses some new techniques to develop and improve quantum algorithms.We have used this system to develop two formerly unknown quantum algorithms. We also address a potential deficiency of the quantum decision tree model used to prove lower bounds on the query complexity of the parity problem.

FILENAME: jcad2008.pdf (225 kB)




TITLE: An eigen analysis of the GP community, 2008

AUTHORS: W.B. Langdon, R. Poli and W. Banzhaf

SOURCE: Genetic Programming and Evolvable Machines, 9 (2008) 171 - 182

ABSTRACT: The coauthorship and coeditorship relations as recorded in the genetic programming bibliography provide a quantitative view of the GP community. Eigen analysis is used to find the principle components of the community. It shows the major eigenvalues and eigenvectors are responsible for 70% of the connection graph. Top eigen authors are given.

FILENAME: gpem2008.pdf (1,573 kB)




TITLE: Why Complex Systems Engineering Needs Biological Development, 2007

AUTHORS: W. Banzhaf and N. Pillay

SOURCE: Complexity, 13 (2007) 12 - 21

ABSTRACT: Here we shall discuss the need of Complex Systems Engineering to adopt principles from natural development of complex biological organisms?besides principles of natural evolution?to acomplish the type of performance that biology achieves regularly. We shall situate Complex Systems Engineering and discuss an example of how it could be employed.

FILENAME: complexity2007.pdf (130 kB)




TITLE: Analysis of preferential network motif generation in an artificial regulatory network model created by duplication and divergence, 2007

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

SOURCE: Advances in Complex Systems, 10 (2007) 155 - 172

ABSTRACT: Previous studies on network topology of artificial gene regulatory networks created by whole genome duplication and divergence processes show subgraph distributions similar to gene regulatory networks found in nature. In particular, certain network motifs are prominent in both types of networks. In this contribution, we analyze how duplication and divergence processes influence network topology and preferential generation of network motifs. We show that in the artificial model such preference originates from a stronger preservation of protein than regulatory sites by duplication and divergence. If these results can be transferred to regulatory networks in nature, we can infer that after duplication the paralogous transcription factor binding site is less likely to be preserved than the corresponding paralogous protein.

FILENAME: acs2007.pdf (502 kB)

TITLE: Reducing the Number of Fitness Evaluations in Graph Genetic Programming Using a Canonical Graph Indexed Database, 2007

AUTHORS: Jens Niehaus, Christian Igel and Wolfgang Banzhaf

SOURCE: Evolutionary Computation, 15 (2007) 199 - 221

ABSTRACT: We describe the genetic programming systemGGP operating on graphs and introduce the notion of graph isomorphisms to explain how they influence the dynamics of GP. It is shown empirically how fitness databases can improve the performance of GP and how mapping graphs to a canonical form can increase these improvements by saving considerable evaluation time.

FILENAME: ecj2007.pdf (239 kB)




TITLE: Going Back to our Roots: Second Generation Biocomputing, 2006

AUTHORS: J. Timmis, M. Amos, W. Banzhaf and A. Tyrrell

SOURCE: Journal of Unconventional Computing, 2 (2006) 349 - 378

ABSTRACT: Researchers in the field of biocomputing have, for many years, successfully used the natural world as inspiration for developing systems that are robust, adaptable and capable of generating novel and evencreative solutions to human-defined problems. However, in this position paper we argue that the time has now come for a reassessment of how we exploit biology to generate new computational systems. Previous solutions (the first generation of biocomputing techniques), whilst reasonably effective, are crude analogues of actual biological systems. We believe that a new, inherently inter-disciplinary approach is needed for the development of the emerging second generation of bioinspired methods. This new modus operandi will require much closer interaction between the engineering and life sciences communities, as well as a bidirectional flow of concepts, applications and expertise. We support our argument by examining, in this new light, three existing areas of biocomputing (genetic programming, artificial immune systems and evolvable hardware), as well as an emerging area (natural genetic engineering) which may provide useful pointers as to the way forward.

FILENAME: JUC2006.pdf (202 kB)




TITLE: From Artificial Evolution to Computational Evolution: A Research Agenda, 2006

AUTHORS: W. Banzhaf, G. Beslon, S. Christensen, J.A. Foster, F. Képès, V. Lefort, J.F. Miller, M. Radman and J.J. Ramsden

SOURCE: Nature Reviews Genetics, 7 (2006) 729 - 735

ABSTRACT: Computational scientists have developed algorithms inspired by natural evolution for at least 50 years. These algorithms solve optimization and design problems by building solutions that are ‘more fit’ relative to desired properties. However, the basic assumptions of this approach are outdated. We propose a research programme to develop a new field: computational evolution. This approach will produce algorithms that are based on current understanding of molecular and evolutionary biology and could solve previously unimaginable or intractable computational and biological problems.

FILENAME: nrg2006.pdf (366 kB)




TITLE: Network topology and the evolution of dynamics in an artificial genetic regulatory network model created by whole genome duplication and divergence

AUTHORS: P.D. Kuo, W. Banzhaf, A. Leier

SOURCE: Biosystems 85 (2006) 177-200

ABSTRACT: Topological measures of large-scale complex networks are applied to a specific artificial regulatory network model created through a whole genome duplication and divergence mechanism. This class of networks share topological features with natural transcriptional regulatory networks. Specifically, these networks display scale-free and small-world topology and possess subgraph distributions similar to those of natural networks. Thus, the topologies inherent in natural networks may be in part due to their method of creation rather than being exclusively shaped by subsequent evolution under selection. The evolvability of the dynamics of these networks is also examined by evolving networks in simulation to obtain three simple types of output dynamics. The networks obtained from this process show a wide variety of topologies and numbers of genes indicating that it is relatively easy to evolve these classes of dynamics in this model.

FILENAME: biosystems85_2006_177.pdf (1,172 kB)




TITLE: Repeated Sequences in Linear Genetic Programming

AUTHORS: W.B. Langdon and W. Banzhaf

SOURCE: Complex Systems 15 (2005) pp. 285 - 306

ABSTRACT: Biological chromosomes are replete with repetitive sequences, microsatellites, SSR tracts, ALU, and so on, in their DNA base sequences. We started looking for similar phenomena in evolutionary computation. First studies find copious repeated sequences, which can be hierarchically decomposed into shorter sequences, in programs evolved using both homologous and two-point crossover but not with headless chicken crossover or other mutations. In bloated programs the small number of effective or expressed instructions appear in both repeated and nonrepeated code. Hinting that building-blocks or code reuse may evolve in unplanned ways. Mackey-Glass chaotic time series prediction and eukaryotic protein localization (both previously used as artificial intelligence machine learning benchmarks) demonstrate the evolution of Shannon information (entropy) and lead to models capable of lossy Kolmogorov compression. Our findings with diverse benchmarks and genetic programming (GP) systems suggest this emergent phenomenon may be widespread in genetic systems.

FILENAME: cs_repeat_linear.pdf (434 kB)




TITLE: Quantum and classical parallelism in parity algorithms for ensemble quantum computers

AUTHORS: R. Stadelhofer and D. Suter, and W. Banzhaf

SOURCE: Physical Review A, 71 (2005) pp. 032345-1 - 032345-6

ABSTRACT: The determination of the parity of a string of N binary digits is a well-known problem in classical as well as quantum information processing, which can be formulated as an oracle problem. It has been established that quantum algorithms require at least N/2 oracle calls. We present an algorithm that reaches this lower bound and is also optimal in terms of additional gate operations required. We discuss its application to pure and mixed states. Since it can be applied directly to thermal states, it does not suffer from signal loss associated with pseudo-pure-state preparation. For ensemble quantum computers, the number of oracle calls can be further reduced by a factor 2k, with kPh1,2, . . . , log2sN/2dj, provided the signal-to-noise ratio is sufficiently high. This additional speed-up is linked to sclassicald parallelism of the ensemble quantum computer. Experimental realizations are demonstrated on a liquid-state NMR quantum computer.

FILENAME: PRA71.pdf (137 kB)




TITLE: Network motifs in natural and artificial transcriptional regulatory networks

AUTHORS: W. Banzhaf and P.D. Kuo

SOURCE: Journal of Biological Physics and Chemistry, 4 (2004) pp. 85 - 92

ABSTRACT: We show that network motifs found in natural regulatory networks may also be found in an artificial regulatory network model created through a duplication/divergence process. It is shown that these network motifs exist more frequently in a genome created through the aforementioned process than in randomly generated genomes. These results are then compared with a network motif analysis of the gene expression networks of Escherichia coli and Saccharomyces cerevisiae. In addition, it is shown that certain individual network motifs may arise directly from the duplication/divergence mechanism.

FILENAME: JBPC.pdf (351 kB)




TITLE: Microarray-Based in vitro Evaluation of DNA Oligomer Libraries Designed in silico

AUTHORS: U. Feldkamp, R. Wacker, H. Schroeder, W. Banzhaf and C. Niemeyer

SOURCE: ChemPhysChem, 5 (2004) pp. 367 - 372

ABSTRACT: We report on the microarray-based in vitro evaluation of two libraries of DNA oligonucleotide sequences,designed in silico for applications in supramolecular self-assembly,such as DNA com- puting and DNA-based nanosciences. In this first study which is devoted to the comparison of sequence motif properties theoretically predicted with their performance in real-life, the DNA-directed immobilization (DDI)of proteins was used as an example of DNA-based self-assembly. Since DDI technologies, DNA computing, and DNA nanoconstruction essentially depend on similar prerequisites, in particular, large and uniform hybridization efficiencies combined with low nonspecific cross-reactivity between individual sequences, we anticipate that the microarray approach demonstrated here will enable rapid evaluation of other DNA sequence libraries.

FILENAME: chemphyschem5_2004_367.pdf (173 kB)




TITLE: Dynamic Subset Selection Based on a Fitness Case Topology

AUTHORS: C. Lasarczyk, P. Dittrich and W. Banzhaf

SOURCE: Evolutionary Computation, 12 (2004) pp. 223 - 242

ABSTRACT: A large training set of fitness cases can critically slow down genetic programming, if no appropriate subset selection method is applied. Such a method allows to evaluate an individual on a smaller subset of fitness cases. In this paper we suggest a new subset selection method that takes the problem structure into account, while being problem independent at the same time. In order to achieve this, information about the problem structure is acquired during evolutionary search by creating a topology (relationship) on the set of fitness cases. The topology is induced by individuals of the evolving population, through increasing the strength of the relation between two fitness cases, if an individual of the population is able to solve both of them. Our new topology-based subset selection method chooses a subset, such that fitness cases in this subset are as little as possible related with respect to the induced topology. We compare topology-based selection of fitness cases with dynamic subset selection and stochastic subset sampling on four different problems. On average, runs with topology-based selection show faster progress than the others.

FILENAME: topology.pdf (2047 kB)




TITLE: Artificial chemistries - Toward Constructive Dynamical Systems

AUTHORS: W. Banzhaf

SOURCE: Solid State Phenomena, 97/98 (2004) pp. 43 - 50

ABSTRACT: In this contribution we consider constructive dynamical systems, taking one particular Artificial Chemistry as an example. We argue that constructive dynamical systems are in fact widespread in combinatorial spaces of Artificial Chemistries.

FILENAME: selfformation.pdf (251 kB)




TITLE: Software Tools for DNA Sequence Design

AUTHORS: Udo Feldkamp, H. Rauhe und W. Banzhaf

SOURCE: Special Issue on Biomolecular Computation (M.Garzon, guest editor)
Genetic Programming and Evolvable Machines, 4 (2003) pp. 153 - 171

ABSTRACT: The design of DNA sequences is a key problem for implementing molecular self-assembly with nucleic acid molecules. These molecules must meet several physical, chemical and logical requirements, mainly to avoid mishybridization. Since manual selection of proper sequences is too time-consuming for more than a handful of molecules, the aid of computer programs is advisable. In this paper two software tools for designing DNA sequences are presented, the DNASequenceGenerator and the DNA­Sequence­Compiler. Both employ an approach of sequence dissimilarity based on the uniqueness of overlapping subsequences and a graph based algorithm for sequence generation. Other sequence properties like melting temperature or forbidden subsequences are also regarded, but not secondary structure errors or equilibrium chemistry. Fields of application are DNA computing and DNA-based nanotechnology. In the second part of this paper, sequences generated with the DNA­Sequence­Generator are compared to those from several publications of other groups, an example application for the DNASequenceCompiler is presented, and the advantages and disadvantages of the presented approach are discussed.

FILENAME: softwaretools.pdf (523 kB)




TITLE: On the Dynamics of Competition in a simple Artificial Chemistry

AUTHORS: Wolfgang Banzhaf

SOURCE: Nonlinear Phenomena in Complex Systems, 5 (2002) 318 - 324

ABSTRACT: We examine a simple system of competing and cooperating entities in terms of the speed of settling their competition. It turns out that the larger the degree of cooperativity among entities the quicker the competition is decided. This result, derived in a simple artificial chemistry system, demonstrates that cooperativity is a decisive element of a world of entities competing for resources. It also hints at the fact that growth of complexity (in terms of increasing cooperativity) is a native tendency of such a world.

FILENAME: acceleration.pdf (180 kB)




TITLE: On the Scalability of Social Order

AUTHORS: Peter Dittrich, Thomas Kron and Wolfgang Banzhaf

SOURCE: (Electronic) Journal of Artificial Societies and Social Simulation, Vol. 6 (2003) issue 1

ABSTRACT: We investigate an algorithmic model based first of all on Luhmann's description of how social order may originate [N. Luhmann, Soziale Systeme, Frankfurt/Main, Suhrkamp, 1984, pp. 148-179]. In a basic 'dyadic' setting, two agents build up expectations during their interaction process. First, we include only two factors into the decision process of an agent, namely, its expectation about the future and its expectation about the other agent's expectation (called 'expectation-expectation' by Luhmann). Simulation experiments of the model reveal that 'social' order appears in the dyadic situation for a wide range of parameter settings, in accordance with Luhmann. If we move from the dyadic situation of two agents to a population of many interacting agents, we observe that the order usually disappears. In our simulation experiments, scalable order appears only for very specific cases, namely, if agents generate expectation- expectations based on the activity of other agents and if there is a mechanism of 'information proliferation', in our case created by observation of others. In a final demonstration we show that our model allows the transition from a more actor oriented perspective of social interaction to a systems-level perspective. This is achieved by deriving an 'activity system' from the microscopic interactions of the agents. Activity systems allow to describe situations (states) on a macroscopic level independent from the underlying population of agents. They also allow to draw conclusions on the scalability of social order.

FILENAME: http://jasss.soc.surrey.ac.uk/6/1/3.html




TITLE: Some considerations on the reason for bloat

AUTHORS: Wolfgang Banzhaf and William B. Langdon

SOURCE: Genetic Programming and Evolvable Machines, Vol. 3 (2002) pp. 81-91

ABSTRACT: A representation-less model for genetic programming is presented. The model is intended to examine the mechanisms that lead to bloat in genetic programming (GP). We discuss two hypotheses (fitness causes bloat and neutral code is protective) and perform simulations to examine the predictions deduced from these hypotheses. Our observation is that predictions from both hypotheses are realized in the simulated model.

FILENAME: genp_bloat.pdf (177 kB)




TITLE: Evolving Teams of Predictors with Linear Genetic Programming

AUTHORS: Markus Brameier and Wolfgang Banzhaf

SOURCE: Genetic Programming and Evolvable Machines, Vol. 2 (2001) pp. 381-407

ABSTRACT: This paper applies the evolution of GP teams to different classification and regression problems and compares different methods for combining the outputs of the team programs. These include hybrid approaches where (1) a neural network is used to optimize the weights of programs in a team for a common decision and (2) a real-numbered vector (the representation of evolution strategies) of weights is evolved with each team in parallel. The cooperative team approach results in an improved training and generalization performance compared to the standard GP method. The higher computational overhead of team evolution is counteracted by using a fast variant of linear GP.

FILENAME: teams.pdf (203 kB)




TITLE: Artificial Chemistries - A Review

AUTHORS: Peter Dittrich, Jens Ziegler and Wolfgang Banzhaf

SOURCE: Artificial Life, 7 (2001) 225 - 275

ABSTRACT: This article reviews the growing body of scientific work in Artificial Chemistry. First, common motivations and fundamental concepts are introduced. Second, current research activities are discussed along three application dimensions: modeling, information processing and optimization. Finally, common phenomena among the different systems are summarized. It is argued here that Artificial Chemistries are ``the right stuff'' for the study of pre-biotic and bio-chemical evolution, and they provide a productive framework for questions regarding the origin and evolution of organizations in general. Furthermore, Artificial Chemistries have a broad application range to practical problems as shown in this review.

FILENAME: alchemistry_review_MIT.pdf (589 kB)




TITLE: Evolving Control Metabolisms for a Robot

AUTHORS: Jens Ziegler and Wolfgang Banzhaf

SOURCE: Artificial Life, 7 (2001) 161 - 190

ABSTRACT: This paper demonstrates a new method of programming artificial chemistries. It uses the emerging capabilities of the system's dynamics for information processing purposes. By evolution of metabolisms that act as control programs for a small robot one achieves the adaptation of the internal metabolic pathways as well as the selection of the most relevant available exteroreceptors. The underlying artificial chemistry evolves efficient information processing pathways with most benefit for the desired task, robot navigation. The results show certain relations to biological systems like motile bacteria.

FILENAME: ziegler01evolving.pdf (383 kB)




TITLE: Artificial Chemistry (in German)

AUTHORS: Andre Skusa, Wolfgang Banzhaf, Jens Busch, Peter Dittrich and Jens Ziegler

SOURCE: Kuenstliche Intelligenz, 1 / 2000, 12 - 19

ABSTRACT: Unter einer Kuenstlichen Chemie (Artificial Chemistry) versteht man ein System, das mit seinen Komponenten und Interaktionsregeln das Paradigma der natuerlichen Chemie zum Vorbild hat, jedoch von den tatsa3chlichen physikalischen Randbedingungen abstrahiert. Die Dynamik einer Kuenstlichen Chemie, die durch die Interaktionen der Molekuele und den Reaktionsalgorithmus bestimmt wird, ist dabei der anderer komplexer Systeme aehnlich. Somit koennen unterschiedliche komplexe Systeme als Realisierungen der gleichen Organisation verstanden werden. Diese Organisation gilt es, abstrakt und realisierungsunabhaengig zu beschreiben. Von besonderem Interesse sind deshalb solche fuer natuerliche und komplexe Systeme kennzeichnenden Phaenomene wie Selbstorganisation, Strukturbildung, Evolution und Informationsverarbeitung. Die Zielsetzungen bei der Untersuchung Kuenstlicher Chemien lassen sich vereinfachend in Modellbildung, Informationsverarbeitung und Optimierung unterteilen. Dies umfasst sowohl grundlagentheoretische Untersuchungen zur Evolution des Lebens, als auch anwendungsorientierte Ansaetze, die eine Kuenstliche Chemie z.B. zur metabolischen Steuerung von Robotern oder zum automatischen Beweisen einsetzen.

FILENAME: finalversion_journal.pdf (233 kB)




TITLE: Cryptography with DNA binary strands

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

SOURCE: BioSystems, 57 (2000) 13 - 22

ABSTRACT: Biotechnological methods can be used for cryptography. Here two di erent cryptographic approaches based on DNA binary strands are shown. The rst approach shows how DNA binary strands can be used for steganography to provide rapid encryption and decryption. It is shown that DNA steganogra- phy based on DNA binary strands is secure under the assumption that an interceptor has the same technological capabilities as sender and receiver of encrypted messages. The second approach shown here is based on steganography and a method of graphical subtraction of binary gel-images. It can be used to constitute a molecular checksum and can be combined with the rst approach to support encryption.

FILENAME: DNA_Crypt_final.pdf (338 kB)




TITLE: Spontaneous Group Formation in the Seceder Model

AUTHORS: Peter Dittrich, Fredrik Liljeros, Arne Soulier and Wolfgang Banzhaf

SOURCE: Physical Review Letters, 84 (2000) 3205 - 3208

ABSTRACT: The seceder model shows how the local tendency to be dfferent gives rise to the formation of groups. The model consists of a population of simple entities which reproduce and die. In a single reproduction event three individuals are chosen randomly and the individual which possesses the largest distance to their center is reproduced by creating a mutated offspring. The offspring replaces a randomly chosen individual of the population. The paper demonstrates the complex group formation behavior and its dependency on the population size. 

FILENAME: PRL84.pdf (122 kB)




TITLE: Iterated Mutual Observation with Genetic Programming

AUTHORS: Peter Dittrich and Thomas Kron and Christian Kuck and Wolfgang Banzhaf

SOURCE: Sozionik Aktuell, 2 (2001)

ABSTRACT: This paper introduces a simple model of interacting agents that learn to predict each other. For learning to predict the other's intended action we apply genetic programming. The strategy of an agent is rational and fixed. It does not change like in classical iterated prisoners dilemma models. Furthermore the number of actions an agent can choose from is infinite. Preliminary simulation results are presented. They show that by varying the population size of genetic programming, different learning characteristics can easily be achieved, which lead to quite different communication patterns. 

FILENAME: iterated-mutual-observation-with.pdf (705 kB)




TITLE: A Comparison of Linear Genetic Programming and Neural Networks in Medical Data Mining

AUTHORS: Markus Brameier and Wolfgang Banzhaf

SOURCE: IEEE Transactions on Evolutionary Computation, 5 (2001), pp. 17 -- 26

ABSTRACT: We apply linear genetic programming to several diagnosis problems in medicine. An efficient algorithm is presented that eliminates intron code in linear genetic programs. This results in a significant speedup which is especially interesting when operating with complex datasets as they are occuring in real-world applications like medicine. We compare our results to those obtained with neural networks and argue that genetic programming is able to show similar performance in classification and generalization even within a relatively small number of generations. 

FILENAME: IEEETA.pdf (189 kB)




TITLE: Self-Evolution in a Constructive Binary String System

AUTHORS: Peter Dittrich and Wolfgang Banzhaf

SOURCE: Artificial Life, 4 (1998) 203 - 220 ABSTRACT: We examine the qualitative dynamics of a catalytic self-organizing reaction system of binary strings that is inspired by the chemical information processing metaphor. A string is interpreted in two different ways: either (i) as raw data or (ii) as a machine which is able to process another string as data in order to produce a third one. This paper focuses on the phenomena of evolution whose appearance is notable because no explicit mutation, recombination or artificial selection operators are introduced. We call the system self-evolving because every variation is performed by the objects themselves in their machine form. 

FILENAME: dittrichBanzhaf.pdf (426 kB)




TITLE: Evolution of a World Model for a Miniature Robot using Genetic Programming

AUTHORS: Peter Nordin, Wolfgang Banzhaf and Markus Brameier

SOURCE: Robotics and Autonomous Systems, 25 (1998) pp. 105 - 116

ABSTRACT: We have used an automatic programming method called Genetic Programming (GP) for control of a miniature robot. Our earlier work on real-time learning suffered from the drawback of the learning time being limited by the response dynamics of the robot's environment. In order to overcome this problem we have devised a new technique which allows learning from past experiences that are stored in memory. The new method shows its advantage when perfect behavior emerges in experiments quickly and reliably. It is tested on two control tasks, obstacle avoiding and wall following behavior, both in simulation and on the real robot platform Khepera. 

FILENAME: robotics_and_autonomous.pdf (916 kB)




TITLE: Selforganization in a system of binary strings with topological interactions

AUTHORS: Wolfgang Banzhaf, Peter Dittrich and Burkart Eller

SOURCE: Physica D, 125 (1999) 85 - 104

ABSTRACT: We consider an artificial reaction system whose components are binary strings. Upon encounter, two binary strings produce a third string which competes for storage space with the originators. String types or species can only survive when produced in sufficient numbers. Spatial interactions through introduction of a topology and rules for distance-dependent reactions are discussed. We observe three different kinds of survival strategies of binary strings: cooperation of strings, exploitation of niches and parasitic behavior. 

FILENAME: physica_d2.pdf (704 kB)




TITLE: Real Time Control of a Khepera Robot using Genetic Programming

AUTHORS:Peter Nordin, Wolfgang Banzhaf

SOURCE: Cybernetics and Control, Vol. 26 (3) 1997 pp. 533 --- 561

ABSTRACT: A computer language is a very general form of representing and specifying an autonomous agent's behavior. The task of planning feasible actions could then simply be reduced to an instance of automatic programming. We have evaluated the use of an evolutionary technique for automatic programming called Genetic Programming (GP) to directly control a miniature robot. To our knowledge, this is the first attempt to control a real robot with a GP based learning method. Two schemes are presented. The objective of the GP system in our first approach is to evolve real-time obstacle avoiding behavior. This technique enables real-time learning with a real robot using genetic programming. It has, however, the drawback that the learning time is limited by the response dynamics of the environment. To overcome this problems we have devised a second method, learning from past experiences which are stored in memory. This new system allows a speed-up of the algorithm by a factor of more than 2000. Obstacle avoiding behavior emerges much faster, approximately 40 times as fast, allowing learning of this task in 1.5 minutes. This learning time is several orders of magnitudes faster then comparable experiments with other control architectures. Furthermore, the GP algorithm is very compact and can be ported to the micro-controller of the autonomous mobile miniature robot. 

FILENAME: robot12.pdf (386 kB)




TITLE: An On-Line Method to Evolve Behavior and to Control a Miniature Robot in Real Time with Genetic Programming

AUTHORS:Peter Nordin, Wolfgang Banzhaf

SOURCE: Adaptive Behaviour, 5 (2) , 1997, 107 --- 140

ABSTRACT: We present a novel evolutionary approach to robotic control of a real robot based on genetic programming (GP). Our approach uses genetic programming techniques that manipulate machine code to evolve control programs for robots. This variant of GP has several advantages over a conventional GP system, such as higher speed, lower memory requirements and better real time properties. Previous attempts to apply GP in robotics use simulations to evaluate control programs and have difficulties with learning tasks involving a real robot. We present an on-line control method that is evaluated in two different physical environments and applied to two tasks using the Khepera robot platform: obstacle avoidance and object following. The results show fast learning and good generalization. 

FILENAME: adapt_behav.pdf (487 kB)




TITLE: Emergent Computation by Catalytic Reactions

AUTHORS:Wolfgang Banzhaf, Peter Dittrich, Hilmar Rauhe

SOURCE: Nanotechnology, 7 (1996) 307 --- 314

ABSTRACT: Recently, biochemical systems have been shown to possess interesting computational properties. 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. We review in this contribution the idea behind the chemical computational metaphor and outline its relevance for nanotechnology. We set up a simulated reaction system of mathematical objects and examine its dynamics by computer experiments. Typical problems of computer science, like sorting, parity checking or prime number computation are placed within this context. The implications of this approach for nanotechnology, parallel computers based on molecular devices and DNA-RNA-protein information processing are discussed. 

FILENAME: nanotechnology7.pdf (68 kB)




TITLE: Self-replicating Sequences of Binary Numbers --- The Build-up of Complexity

AUTHORS: Wolfgang Banzhaf

SOURCE: Complex Systems, Volume 8 (1994), pp. 205 --- 215

ABSTRACT: A recently introduced system of self-replicating sequences of binary numbers (strings) is generalized. It is extended to include strings of arbitrary length. For this purpose, first, the folding methods of strings into two-dimensional operators are expanded to include strings of arbitrary size. Second, rules of interaction between strings of different lengths are established. As natural consequence of these interactions, changes in string length are observed. Using an effective model of length changes, the build-up of complexity as measured by the average sequence length in a string population is studied. 

FILENAME: CompSys94.pdf (183 kB)




TITLE: Self-replicating Sequences of Binary Numbers

AUTHORS: Wolfgang Banzhaf

SOURCE: Computers and Mathematics with Applications, Vol. 26 issue 7 (1993), pp. 1 --- 8

ABSTRACT: An algorithm is proposed which allows sequences of binary numbers to interact. We introduce a 2-dimensional matrix form of the sequences achieved by a general folding method. Interactions between 1- and 2-dimensional forms of binary sequences generate new sequences, which compete with the original ones due to selection pressure. Starting from random initial populations, replicating and self-replicating sequences are generated in large numbers. We report on results for 4-digit sequences and propose non-linear differential equations modelling the system. 

FILENAME: comp_appl93.pdf (217 kB)




TITLE: Self-replicating sequences of binary numbers --- I. Foundations

AUTHORS: Wolfgang Banzhaf

SOURCE: Biological Cybernetics, Volume 69 (1993), pp. 269 --- 274

ABSTRACT: We propose the general framework of a new algorithm derived from the interactions of chains of RNA which is capable of self-organization. It considers sequences of binary numbers (strings) and their interaction with each other. In analogy to RNA systems, a folding of sequences is introduced to generate alternative 2-dimensional forms of the binary sequences. The 2-dimensional forms of strings can naturally interact with 1-dimensional forms and generate new sequences. These new sequences compete with the original strings due to selection pressure. Populations of initially random strings develop in a stochastic reaction system following the reaction channels between string types. In particular, replicating and self-replicating string types can be observed in such systems. 

FILENAME: BiolCybPart1.pdf (547 kB)




TITLE: Self-replicating sequences of binary numbers --- II. Strings of length N=4

AUTHORS: Wolfgang Banzhaf

SOURCE: Biological Cybernetics, Volume 69 (1993), pp. 275 --- 281

ABSTRACT: We study an algorithm which allows sequences of binary numbers (strings) to interact with each other. The simplest system of this kind with a population of 4-bit-sequences is considered here. Previously proposed folding methods are used to generate alternative 2-dimensional forms of the binary sequences. The interaction of 2-dimensional and 1-dimensional forms of strings is simulated in a serial computer. The reaction network for the N=4 system is established. Development of string populations initially generated randomly is observed. Non-linear rate equations are proposed which provide a model for this simplest system. 

FILENAME: BiolCybPart2.pdf (505 kB)




TITLE: Robust Competitive Networks

AUTHORS: Manfred Schmutz and Wolfgang Banzhaf

SOURCE: Physical Review A, Volume 45 (1992), pp. 4132 --- 4145

ABSTRACT: In the search for networks that implement the winner-take-all function dynamically in a robust way we study in this paper a class of models that includes short-range diffusive interactions. The analysis is based on a combination of numerical simulations and analytic results obtained by the application of field-theoretic methods. An examination of the ground-state properties reveals that the implementation of robust competition in dimensions higher than one requires a non-standard diffusive interaction of at least fourth order.

FILENAME: PhysRevA45.pdf (505 kB)




TITLE: Some Notes on Competition among Cell Assemblies

AUTHORS: Wolfgang Banzhaf and Manfred Schmutz

SOURCE: International Journal on Neural Systems, Volume 2 (1992), pp. 303 --- 313

ABSTRACT: We discuss a family of competitive dynamics useful for pattern recognition purposes. Derived from a physical model of mode competition, they generalize former concepts to include populations of cells working as grandmother cell assemblies. Also the notion of unfair competition is introduced. 

FILENAME: IJNS1992_CompetitionCellAssemblies.pdf (14.8 MB)




TITLE: Learning in a competitive network

AUTHORS: Wolfgang Banzhaf and Hermann Haken

SOURCE: Neural Networks, Volume 3 (1990), pp. 423 --- 435

ABSTRACT: We consider the abilities of a recently published neural network model to recognize and classify arbitrary patterns. We introduce a learning scheme based on Hebb's rule which allows the system's neuronal cells to specialize on different patterns during learning. The rule which was originally introduced by Kohonen is appropriately modified and applied to the competitive network under study. A variant of the learning dynamics is then derived from an energy functional characterizing the specialization state of the network. Simulations are presented to demonstrate the specialization process for different pattern distributions. 

FILENAME: NeuralNetworks1990.pdf (1100 kB)




TITLE: The time-into-intensity-mapping network

AUTHORS: W. Banzhaf and K. Kyuma

SOURCE: Biological Cybernetics, Volume 66 (1991), pp. 115 --- 121

ABSTRACT: We employ a special combination of different networks in order to process (transient) spatio-termporal patterns. In a first layer, feature analyzing cells translate instantaneous spatial patterns into activeities of cells symbolizing the presenscen of certain feature values. A second layer maps the time sequence of symbols into a spatial activity pattern of the so-called TIM-cells. A third layer recognizes predefined activity patterns. We demonstrate the behaviour of the network using gaussian patterns in (1+1) space-time dimensions.

FILENAME: biolcyb66_1991.pdf (451 kB)




TITLE: The Molecular Travelling Salesman

AUTHORS: Wolfgang Banzhaf

SOURCE: Biological Cybernetics, Volume 64 (1990), pp. 7 --- 14

ABSTRACT: We consider a method for optimization of NP-problems motivated by natural evolution. The basic entity is a population of individuals searching in state space defined by the problem. A message exchange mechanism between individuals enables the system to proceed fast and to avoid local optima. We introduce the concept of isolated evolution to maintain a certain degree of variance in the population. The global optimum can be approached to an arbitrary degree. The method is applied to the TSP and its behavior is shown in a couple of simulations.  

FILENAME: MolTravelSalesman.pdf (785 kB)




TITLE: An Energy Function for Specialization

AUTHORS: W. Banzhaf and H. Haken

SOURCE: Physica D, Volume 42 (1990), pp. 257 --- 264

ABSTRACT: We present a model of unsupervised learning based on the minimization of an energy function. The minima of the energy function are related to the degree of specialization of a certain class of artificial neuronal cells - grandmother cells - in the neural network model proposed by Haken. The self-organizing properties of the system are demonstrated by feeding input into a network of such cells with originally randomized synaptic connections. The relation of this learning algorithm to other learning schemes, like e.g. Kohonen's feature maps, is outlined. 

FILENAME: An_Energy_Function_For_Specialization-1990.pdf (1,300 kB)




TITLE: A New Dynamical Approach to the Travelling Salesman Problem

AUTHORS: Wolfgang Banzhaf

SOURCE: Physics Letters A, Volume 136 (1989), pp. 45 --- 51

ABSTRACT:We present a new dynamical method to solve problems of combinatorial optimization. The basis units (artificial neurons) of a network generate a competitive dynamics by their two-dimensional interactions. Based on that specific dynamics the system uses much the same information as human beings to reduce the solution space of the problem. The method is applied to the TSP and compared to conventional approaches.  

FILENAME: A_new_dynamical_approach_to_the_TSP.pdf (578 kB)




TITLE: A New Learning Algorithm for Synergetic Computers

AUTHORS: H. Haken, R. Haas and W. Banzhaf

SOURCE: Biological Cybernetics, Volume 62 (1989), pp. 107 --- 111

ABSTRACT: We introduce a Lyapunov function which allows us to calculate the vectors, by which the synaptic strengths are determined, by means of a gradient dynamics. The approach does not require any back-propagation, nor simulated annealing, nor computations on a freely running (unclamped) network. The approach is applicable to noiseless patterns as well as to sets of noisy patterns defined by their second and fourth order moments.  

FILENAME: ANewLearningAlgorithmForSynergetics-1989.pdf (1,300 kB)




TITLE: A Network of multi-state Units capable of Associative Memory and Pattern Classification

AUTHORS: Wolfgang Banzhaf

SOURCE: Physica D, Volume 34 (1989), pp. 418 --- 426

ABSTRACT: We consider a model of multistable units acting together in a network. We modify the landscape algorithm of spinglass-like neural nets to cope with new conditions. Collective capabilities such as associative memory function or pattern classilication are demonstrated using the simplest possible learning rule of Hebb.  

FILENAME: multi-state-units-1989.pdf (961 kB)




TITLE: Population Processing - a powerful Class of Parallel Algorithms

AUTHORS: Wolfgang Banzhaf

SOURCE: BioSystems, Volume 22 (1989), pp. 163 --- 172

ABSTRACT: We present a model for optimization of cost functions by a population of parallel processors and argue that especially diploid recombination of gene strings is a promising recipe for optimization which nature proliferates. Based on a simulated evolutionary search strategy diploidy is introduced as a means for maintaining variability in computational problems with large numbers of local extrema. A differentiation into genotypes and phenotypes is performed. The applied strategy is compared to some traditional algorithms simulating evolution on the basis of two sample cost functions.

FILENAME: population_processing_1989.pdf (119 kB)




TITLE: On a Simple Stochastic Neuron - Like Unit

AUTHORS: Wolfgang Banzhaf

SOURCE: Biological Cybernetics, Volume 60 (1988), pp. 153 --- 160

ABSTRACT: We consider a simple stochastic unit realized by digital ANDs and ORs. The function of the unit is inspired by nerve cells found in brains of higher organisms. Information is carried by trains of pulses in time. Therefore, time is introduced into the model as an essential variable. Principles of stochastic computing are used to appropriately model weighted summation of inputs. The model unit allows to process analog information as is provided by observables of real environments. The statistical properties of the model are examined. The traditional saturation non-linearity of neurons emerges as a natural consequence of signal gating by "synapses". Different schemes of synaptic modification are indicated. 

FILENAME: StochasticNeuron.pdf (673 kB)




TITLE: Spontaneous Pattern Classification by a Dynamical System

AUTHORS: Wolfgang Banzhaf

SOURCE: Journal de Physique, Paris, Volume 48 (1987), pp. 2027 --- 2037

ABSTRACT: We study features of a recently proposed computer architecture which models a dynamical system. We generalize the model and give some central issues. We apply the basin complexity as a measure and exemplify the use of the system for pattern recognition.  

FILENAME: ajp-jphys_1987_48_12_2027_0.pdf (1,300 kB)




Wolfgang Banzhaf
Last updated: Aug 10, 2023