List of Journal Articles

Wolfgang Banzhaf

Some of the older papers (from 1993 back) are represented by abstracts only and are available upon email request
We give titles and links. If you click the 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: 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: prl.pdf (1836 kB) prl.ps.gz (705 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: To obtain it, please send me an email!




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: To obtain it, please send me an email!




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: 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)




Wolfgang Banzhaf
Last updated: Jul 22, 2010