Lexicase parent selection filters the population by considering one random training case at a tim... more Lexicase parent selection filters the population by considering one random training case at a time, eliminating any individuals with errors for the current case that are worse than the best error in the selection pool, until a single individual remains. This process often stops before considering all training cases, meaning that it will ignore the error values on any cases that were not yet considered. Lexicase selection can therefore select specialist individuals that have poor errors on some training cases, if they have great errors on others and those errors come near the start of the random list of cases used for the parent selection event in question. We hypothesize here that selecting these specialists, which may have poor total error, plays an important role in lexicase selection's observed performance advantages over error-aggregating parent selection methods such as tournament selection, which select specialists much less frequently. We conduct experiments examining thi...
Lexicase selection is a parent selection method that considers training cases individually, rathe... more Lexicase selection is a parent selection method that considers training cases individually, rather than in aggregate, when performing parent selection. Whereas previous work has demonstrated the ability of lexicase selection to solve difficult problems in program synthesis and symbolic regression, the central goal of this paper is to develop the theoretical underpinnings that explain its performance. To this end, we derive an analytical formula that gives the expected probabilities of selection under lexicase selection, given a population and its behavior. In addition, we expand upon the relation of lexicase selection to many-objective optimization methods to describe the behavior of lexicase selection, which is to select individuals on the boundaries of Pareto fronts in high-dimensional space. We show analytically why lexicase selection performs more poorly for certain sizes of population and training cases, and show why it has been shown to perform more poorly in continuous error ...
We explore tradeo#s between classical communication and entanglement-generating powers of unitary... more We explore tradeo#s between classical communication and entanglement-generating powers of unitary 2-qubit gates. The exploration is aided by a computational search technique called genetic programming.
Cooperation in evolving populations of agents has been explained as arising from kin selection, r... more Cooperation in evolving populations of agents has been explained as arising from kin selection, reciprocity during repeated interactions, and indirect reciprocity through agent reputations. All of these mechanisms require signican t agent capabilities, but recent research using computational models has shown that arbitrary markers called \tags" can be used to achieve signican t levels of cooperation even in the absence of memory, repeated interactions or knowledge of kin. This is important because it helps to explain the evolution of cooperation in organisms with limited cognitive capabilities, and also because it may help us to engineer cooperative behaviors in multi-agent systems. The computational models used in previous studies, however, have typically been constrained such that cooperation is the only viable strategy for gaining an evolutionary advantage. Here we show that tagmediated recognition can lead to signican t levels of cooperation in a less constrained articial l...
This paper discusses the role of culture in the evolution of cognitive systems. We define “cultur... more This paper discusses the role of culture in the evolution of cognitive systems. We define “culture” as any information transmitted between individuals and between generations by nongenetic means. Experiments are presented that use genetic programming systems that include special mechanisms for cultural transmission of information. These systems evolve computer programs that perform cognitive tasks including mathematical function mapping and action selection in a virtual world. The data show that the presence of culture-supporting mechanisms can have a clear beneficial impact on the evolvability of correct programs. The implications that these results may have for cognitive science are briefly discussed.
We report how breve, a simulation environment with rich 3d graphics, was used to discover signifi... more We report how breve, a simulation environment with rich 3d graphics, was used to discover significant patterns in the dynamics of a system that evolves controllers for swarms of goal-directed agents. These patterns were discovered via visualization in the sense that we had not considered their relevance or thought to look for them initially, but they became obvious upon visually observing the behavior of the system. In this paper we briefly describe breve and the system of evolving swarms that we implemented within it. We then describe two discovered properties of the evolutionary dynamics of the system: transitions to/from genetic drift regimes and the emergence of collective or multicellular organization. We comment more generally on the utility of 3d visualization for the discovery of biologically significant phenomena and briefly describe our ongoing work in this area. Pointers are provided to on-line resources including source code and animations that demonstrate several of the...
This paper discusses the evolution of diversifying reproduction. We measured the average differen... more This paper discusses the evolution of diversifying reproduction. We measured the average difference between mothers and their children, the number of species, and the degree of adaptation in evolving populations of endogenously diversifying digital organisms using the Pushpop system. The data show that the number of species in adaptive populations is higher than in nonadaptive populations, while the variance in the differences between mothers and their children is less for adaptive populations than for non-adaptive populations. In other words, in adaptive populations the species were more numerous and the diversification processes were more reliable.
Genetic programming can be used to automatically discover algorithms for quantum computers that a... more Genetic programming can be used to automatically discover algorithms for quantum computers that are more efficient than any classical computer algorithms for the same problems. In this paper we exhibit the first evolved betterthan-classical quantum algorithm, for Deutsch’s “early promise” problem. We also demonstrate a technique for evolving scalable quantum gate arrays and discuss other issues in the application of genetic programming to quantum computation and vice versa. 1. Quantum Computing Quantum computers are computational devices that use atomic-scale objects, for example 2-state particles, to store and manipulate information (Steane, 1997; for an elementary on-line tutorial see Braunstein, 1995; for an introduction for the general reader see Milburn, 1997). The physics of these devices allows them to do things that common digital (henceforth “classical”) computers cannot. Although quantum computers and classical computers appear to be bound by the same limits of Turing comp...
The growth of program size during evolution (code "bloat") is a well-documented and wel... more The growth of program size during evolution (code "bloat") is a well-documented and well-studied problem in genetic programming. This paper examines the use of "size fair" genetic operators to combat code bloat in the PushGP genetic programming system. Size fair operators are compared to naive operators and to operators that use "node selection" as described by Koza. The effects of the operator choices are assessed in runs on symbolic regression, parity and multiplexor problems (2,700 runs in total). The results show that the size fair operators control bloat well while producing unusually parsimonious solutions. The computational effort required to find a solution using size fair operators is about equal to, or slightly better than, the effort required using the comparison operators.
This paper shows how ontogenetic programming , an enhancement to the genetic programming methodol... more This paper shows how ontogenetic programming , an enhancement to the genetic programming methodology, a l l o ws for the automatic generation of adaptive programs. Programs produced by o n togenetic programming may include calls to self-modiication operators. By permitting runtime program self-modiication, these operators allow e v olved programs to further adapt to their environments. In this paper the onto-genetic programming methodology is described and two examples of its use are presented, one for binary sequence prediction and the other for action selection in a virtual world. In both cases the inclusion of self-modiication operators has a clear positive impact on the ability of genetic programming to produce successful programs.
Lexicase parent selection filters the population by considering one random training case at a tim... more Lexicase parent selection filters the population by considering one random training case at a time, eliminating any individuals with errors for the current case that are worse than the best error in the selection pool, until a single individual remains. This process often stops before considering all training cases, meaning that it will ignore the error values on any cases that were not yet considered. Lexicase selection can therefore select specialist individuals that have poor errors on some training cases, if they have great errors on others and those errors come near the start of the random list of cases used for the parent selection event in question. We hypothesize here that selecting these specialists, which may have poor total error, plays an important role in lexicase selection's observed performance advantages over error-aggregating parent selection methods such as tournament selection, which select specialists much less frequently. We conduct experiments examining thi...
Lexicase selection is a parent selection method that considers training cases individually, rathe... more Lexicase selection is a parent selection method that considers training cases individually, rather than in aggregate, when performing parent selection. Whereas previous work has demonstrated the ability of lexicase selection to solve difficult problems in program synthesis and symbolic regression, the central goal of this paper is to develop the theoretical underpinnings that explain its performance. To this end, we derive an analytical formula that gives the expected probabilities of selection under lexicase selection, given a population and its behavior. In addition, we expand upon the relation of lexicase selection to many-objective optimization methods to describe the behavior of lexicase selection, which is to select individuals on the boundaries of Pareto fronts in high-dimensional space. We show analytically why lexicase selection performs more poorly for certain sizes of population and training cases, and show why it has been shown to perform more poorly in continuous error ...
We explore tradeo#s between classical communication and entanglement-generating powers of unitary... more We explore tradeo#s between classical communication and entanglement-generating powers of unitary 2-qubit gates. The exploration is aided by a computational search technique called genetic programming.
Cooperation in evolving populations of agents has been explained as arising from kin selection, r... more Cooperation in evolving populations of agents has been explained as arising from kin selection, reciprocity during repeated interactions, and indirect reciprocity through agent reputations. All of these mechanisms require signican t agent capabilities, but recent research using computational models has shown that arbitrary markers called \tags" can be used to achieve signican t levels of cooperation even in the absence of memory, repeated interactions or knowledge of kin. This is important because it helps to explain the evolution of cooperation in organisms with limited cognitive capabilities, and also because it may help us to engineer cooperative behaviors in multi-agent systems. The computational models used in previous studies, however, have typically been constrained such that cooperation is the only viable strategy for gaining an evolutionary advantage. Here we show that tagmediated recognition can lead to signican t levels of cooperation in a less constrained articial l...
This paper discusses the role of culture in the evolution of cognitive systems. We define “cultur... more This paper discusses the role of culture in the evolution of cognitive systems. We define “culture” as any information transmitted between individuals and between generations by nongenetic means. Experiments are presented that use genetic programming systems that include special mechanisms for cultural transmission of information. These systems evolve computer programs that perform cognitive tasks including mathematical function mapping and action selection in a virtual world. The data show that the presence of culture-supporting mechanisms can have a clear beneficial impact on the evolvability of correct programs. The implications that these results may have for cognitive science are briefly discussed.
We report how breve, a simulation environment with rich 3d graphics, was used to discover signifi... more We report how breve, a simulation environment with rich 3d graphics, was used to discover significant patterns in the dynamics of a system that evolves controllers for swarms of goal-directed agents. These patterns were discovered via visualization in the sense that we had not considered their relevance or thought to look for them initially, but they became obvious upon visually observing the behavior of the system. In this paper we briefly describe breve and the system of evolving swarms that we implemented within it. We then describe two discovered properties of the evolutionary dynamics of the system: transitions to/from genetic drift regimes and the emergence of collective or multicellular organization. We comment more generally on the utility of 3d visualization for the discovery of biologically significant phenomena and briefly describe our ongoing work in this area. Pointers are provided to on-line resources including source code and animations that demonstrate several of the...
This paper discusses the evolution of diversifying reproduction. We measured the average differen... more This paper discusses the evolution of diversifying reproduction. We measured the average difference between mothers and their children, the number of species, and the degree of adaptation in evolving populations of endogenously diversifying digital organisms using the Pushpop system. The data show that the number of species in adaptive populations is higher than in nonadaptive populations, while the variance in the differences between mothers and their children is less for adaptive populations than for non-adaptive populations. In other words, in adaptive populations the species were more numerous and the diversification processes were more reliable.
Genetic programming can be used to automatically discover algorithms for quantum computers that a... more Genetic programming can be used to automatically discover algorithms for quantum computers that are more efficient than any classical computer algorithms for the same problems. In this paper we exhibit the first evolved betterthan-classical quantum algorithm, for Deutsch’s “early promise” problem. We also demonstrate a technique for evolving scalable quantum gate arrays and discuss other issues in the application of genetic programming to quantum computation and vice versa. 1. Quantum Computing Quantum computers are computational devices that use atomic-scale objects, for example 2-state particles, to store and manipulate information (Steane, 1997; for an elementary on-line tutorial see Braunstein, 1995; for an introduction for the general reader see Milburn, 1997). The physics of these devices allows them to do things that common digital (henceforth “classical”) computers cannot. Although quantum computers and classical computers appear to be bound by the same limits of Turing comp...
The growth of program size during evolution (code "bloat") is a well-documented and wel... more The growth of program size during evolution (code "bloat") is a well-documented and well-studied problem in genetic programming. This paper examines the use of "size fair" genetic operators to combat code bloat in the PushGP genetic programming system. Size fair operators are compared to naive operators and to operators that use "node selection" as described by Koza. The effects of the operator choices are assessed in runs on symbolic regression, parity and multiplexor problems (2,700 runs in total). The results show that the size fair operators control bloat well while producing unusually parsimonious solutions. The computational effort required to find a solution using size fair operators is about equal to, or slightly better than, the effort required using the comparison operators.
This paper shows how ontogenetic programming , an enhancement to the genetic programming methodol... more This paper shows how ontogenetic programming , an enhancement to the genetic programming methodology, a l l o ws for the automatic generation of adaptive programs. Programs produced by o n togenetic programming may include calls to self-modiication operators. By permitting runtime program self-modiication, these operators allow e v olved programs to further adapt to their environments. In this paper the onto-genetic programming methodology is described and two examples of its use are presented, one for binary sequence prediction and the other for action selection in a virtual world. In both cases the inclusion of self-modiication operators has a clear positive impact on the ability of genetic programming to produce successful programs.
Uploads
Papers by Lee Spector