Examining games from a fresh perspective, we present the idea of game-inspired and game-based algorithms, dubbed gamorithms.

We have recently presented SAFE-Solution And Fitness Evolution-a commensalistic coevolutionary algorithm that maintains two coevolving populations: a population of candidate solutions and a population of candidate objective functions. We showed that SAFE was successful at evolving solutions within a robotic maze domain. Herein we present an investigation of SAFE's adaptation and application to multiobjective problems, wherein candidate objective functions explore different weightings of each objective. Though preliminary, the results suggest that SAFE, and the concept of coevolving solutions and objective functions, can identify a similar set of optimal multiobjective solutions without explicitly employing a Pareto front for fitness calculation and parent selection. These findings support our hypothesis that the SAFE algorithm concept can not only solve complex problems, but can adapt to the challenge of problems with multiple objectives.

Motivation: Biclustering algorithms are commonly used for gene expression data analysis. However, accurate identification of meaningful structures is very challenging and state-of-the-art methods are incapable of discovering with high accuracy different patterns of high biological relevance. Results: In this paper, a novel biclustering algorithm based on evolutionary computation, a sub-field of artificial intelligence, is introduced. The method called EBIC aims to detect order-preserving patterns in complex data. EBIC is capable of discovering multiple complex patterns with unprecedented accuracy in real gene expression datasets. It is also one of the very few biclustering methods designed for parallel environments with multiple graphics processing units. We demonstrate that EBIC greatly outperforms state-of-the-art biclustering methods, in terms of recovery and relevance, on both synthetic and genetic datasets. EBIC also yields results over 12 times faster than the most accurate reference algorithms. Availability and implementation: EBIC source code is available on GitHub at https://github.com/EpistasisLab/ebic. Supplementary information: Supplementary data are available at Bioinformatics online.

In this paper, we present the application of genetic programming as a generic game learning approach to zero-sum, deterministic, full-knowledge board games by evolving board-state evaluation functions to be used in conjunction with Monte Carlo tree search (MCTS). Our method involves evolving board-evaluation functions that are then used to guide the MCTS playout strategy. We examine several variants of Reversi, Dodgem, and Hex using strongly typed genetic programming, explicitly defined introns, and a selective directional crossover method. Our results show a proficiency that surpasses that of baseline handcrafted players using equal and in some cases greater amounts of search, with little domain knowledge and no expert domain knowledge. Moreover, our results exhibit scalability.

In this paper, we evolve heuristics to guide staged deepening search for the hard game of FreeCell, obtaining top-notch solvers for this human-challenging puzzle. We first devise several novel heuristic measures using minimal domain knowledge and then use them as building blocks in two evolutionary setups involving a standard genetic algorithm and policy-based, genetic programming. Our evolved solvers outperform the best FreeCell solver to date by three distinct measures: 1) number of search nodes is reduced by over 78%; 2) time to solution is reduced by over 94%; and 3) average solution length is reduced by over 30%. Our top solver is the best published FreeCell player to date, solving 99.65% of the standard Microsoft 32 K problem set. Moreover, it is able to convincingly beat high-ranking human players.

We evolve heuristics to guide staged deepening search for the hard game of FreeCell, obtaining top-notch solvers for this NP-Complete, human-challenging puzzle. We first devise several novel heuristic measures and then employ a Hillis-style coevolutionary genetic algorithm to find efficient combinations of these heuristics. Our results significantly surpass the best published solver to date by three distinct measures: 1) Number of search nodes is reduced by 87%; 2) time to solution is reduced by 93%; and 3) average solution length is reduced by 41%. Our top solver is the best published FreeCell player to date, solving 98% of the standard Microsoft 32K problem set, and also able to beat high-ranking human players.

We use genetic algorithms to evolve highly successful solvers for two puzzles: FreeCell and the Sliding-Tile Puzzle.

We describe Fertile Darwinian Bytecode Harvester (FINCH), a methodology for evolving Java bytecode, enabling the evolution of extant, unrestricted Java programs, or programs in other languages that compile to Java bytecode. Our approach is based upon the notion of compatible crossover, which produces correct programs by performing operand stack-based, local variables-based, and control flow-based compatibility checks on source and destination bytecode sections. This is in contrast to existing work that uses restricted subsets of the Java bytecode instruction set as a representation language for individuals in genetic programming. We demonstrate FINCH's unqualified success at solving a host of problems, including simple and complex regression, trail navigation, image classification, array sum, and tic-tac-toe. FINCH exploits the richness of the Java virtual machine architecture and type system, ultimately evolving human-readable solutions in the form of Java programs. The ability to evolve Java programs will hopefully lead to a valuable new tool in the software engineer's toolkit.

We use genetic programming to evolve highly successful solvers for two puzzles: Rush Hour and FreeCell.

We evolve heuristics to guide IDA* search for the 6x6 and 8x8 versions of the Rush Hour puzzle, a PSPACE-Complete problem, for which no efficient solver has yet been reported. No effective heuristic functions are known for this domain, and--before applying any evolutionary thinking--we first devise several novel heuristic measures, which improve (non-evolutionary) search for some instances, but hinder search substantially for many other instances. We then turn to genetic programming (GP) and find that evolution proves immensely efficacious, managing to combine heuristics of such highly variable utility into composites that are nearly always beneficial, and far better than each separate component. GP is thus able to beat both the human player of the game and also the human designers of heuristics.

Boundary detection constitutes a crucial step in many computer vision tasks. We present a learning approach for automatically constructing high-performance local boundary detectors for natural images via genetic programming (GP). Our GP system is unique in that it combines filter kernels that were inspired by models of processing in the early stages of the primate visual system, but makes no assumptions about what constitutes a boundary, thus avoiding the need to make ad hoc intuitive definitions. By testing our evolved boundary detectors on a highly challenging benchmark set of natural images with associated human-marked boundaries, we show performance that outperforms most existing approaches.

We describe a methodology for evolving Java bytecode, enabling the evolution of extant, unrestricted Java programs, or programs in other languages that compile to Java bytecode. Bytecode is evolved directly, without any intermediate genomic representation. Our approach is based upon the notion of compatible crossover, which produces correct programs by performing operand stack-, local variables-, and control flow-based compatibility checks on source and destination bytecode sections. This is in contrast to existing work that uses restricted subsets of the Java bytecode instruction set as a representation language for individuals in genetic programming. Given the huge universe of unrestricted Java bytecode, as is programs, our work enables the applications of evolution within this realm. We experimentally validate our methodology by both extensively testing the correctness of compatible crossover on arbitrary bytecode, and by running evolution on a program that exploits the richness of the Java virtual machine architecture and type system.

Boundary detection constitutes a crucial step in many computer vision tasks. We present a novel learning approach to automatically construct a boundary detector for natural images via Genetic Programming (GP). Our approach aims to use GP as a learning framework for evolving computer programs that are evaluated against human-marked boundary maps, in order to accurately detect and localize boundaries in natural images. Our GP system is unique in that it combines filter kernels that were inspired by models of processing in the early stages of the primate visual system, but makes no assumption about what constitutes a boundary, thus avoiding the need to make ad-hoc intuitive definitions. By testing the evolved boundary detectors on a benchmark set of natural images with associated human-marked boundaries, we show performance to be quantitatively competitive with existing computer-vision approaches. Moreover, we show that our evolved detector provides insights into the mechanisms underlying boundary detection in the human visual system.

We focus on finding a consensus motif of a set of homologous or functionally related RNA molecules. Recent approaches to this problem have been limited to simple motifs, require sequence alignment, and make prior assumptions concerning the data set. We use genetic programming to predict RNA consensus motifs based solely on the data set. Our system -- dubbed GeRNAMo (Genetic programming of RNA Motifs) -- predicts the most common motifs without sequence alignment and is capable of dealing with any motif size. Our program only requires the maximum number of stems in the motif, and if prior knowledge is available the user can specify other attributes of the motif (e.g., the range of the motif's minimum and maximum sizes), thereby increasing both sensitivity and speed. We describe several experiments using either ferritin iron response element (IRE); signal recognition particle (SRP); or microRNA sequences, showing that the most common motif is found repeatedly, and that our system offers substantial advantages over previous methods.

We have shown that genetically programming game players, after having imbued the evolutionary process with human intelligence, produces human-competitive strategies for three games: backgammon, chess endgames, and robocode (tank-fight simulation). Evolved game players are able to hold their own - and often win - against human or human-based competitors. This paper has a twofold objective: first, to review our results of applying genetic programming in the domain of games; second, to formulate the merits of genetic programming in acting as a tool for developing strategies in general, and to discuss the possible design of a strategizing machine.

January 01 2006 Book Review Kinematic Self-Replicating Machines. Robert A.Freitas, Jr., and Ralph C.Merkle. ( 2004 Landes Bioscience.) $150.00, xxi+341 pp. Moshe Sipper Moshe Sipper Department of Computer Science, Ben-Gurion University P.O. Box 653, Beer-Sheva 84105, Israel [email protected] Search for other works by this author on: This Site Google Scholar Author and Article Information Moshe Sipper Department of Computer Science, Ben-Gurion University P.O. Box 653, Beer-Sheva 84105, Israel [email protected] Online Issn: 1530-9185 Print Issn: 1064-5462 © 2006 Massachusetts Institute of Technology2006 Artificial Life (2006) 12 (1): 187–188. https://doi.org/10.1162/106454606775186473 Cite Icon Cite Permissions Share Icon Share Twitter LinkedIn Views Icon Views Article contents Figures & tables Video Audio Supplementary Data Peer Review Search Site Citation Moshe Sipper; Book Review. Artif Life 2006; 12 (1): 187–188. doi: https://doi.org/10.1162/106454606775186473 Download citation file: Ris (Zotero) Reference Manager EasyBib Bookends Mendeley Papers EndNote RefWorks BibTex toolbar search Search Dropdown Menu toolbar search search input Search input auto suggest filter your search All ContentAll JournalsArtificial Life Search Advanced Search This content is only available as a PDF. © 2006 Massachusetts Institute of Technology2006 Article PDF first page preview Close Modal You do not currently have access to this content.

In a traditional cellular automaton (CA) a cell is implemented by a rule table defining its state at the next time step, given its present state and those of its neighbors. The cell thus deals only with states. We present a novel CA where the cell handles data and signals. The cell is designed as a digital system comprising a processing unit and a control unit. This allows the realization of various growing structures, including self-replicating loops and biomorphs. We also describe the hardware implementation of these structures within our electronic wall for bio-inspired applications, the BioWall.

The shortest common superstring (SCS) problem, known to be NP-complete, seeks the shortest string that contains all strings from a given set. In this paper, we present a novel coevolutionary algorithm-the Puzzle Algorithm-where a population of building blocks coevolves alongside a population of solutions. We show experimentally that our novel algorithm outperforms a standard genetic algorithm (GA) and a benchmark greedy algorithm on instances of the SCS problem inspired by deoxyribonucleic acid (DNA) sequencing. We next compare our previously presented cooperative coevolutionary algorithm with the Co-Puzzle Algorithm-the puzzle algorithm coupled with cooperative coevolution-showing that the latter proves to be top gun. Finally, we discuss the benefits of using our puzzle approach in the general field of evolutionary algorithms.

This letter describes an evolutionary system for creating lifelike three-dimensional plants and flowers, our main goal being the facilitation of producing realistic plant imagery. With these two goals in mind--ease of generation and realism--we designed the plant genotype and the genotype-to-phenotype mapping. Diversity in our system comes about through two distinct processes--evolution and randomization--allowing the creation not only of single plants but of entire gardens and forests. Thus, we are able to readily produce natural-looking artificial scenes.

In this paper we focus on the problem of mammographic interpretation and in the construction of a computerized system to assess physicians in this task. We propose a solution based on fuzzy systems, and apply our fuzzy modeling methodology-Fuzzy CoCo-to find systems exhibiting both good performance and high interpretability. The results presented show the capacity of Fuzzy CoCo to find systems that satisfy different requirements concerning the complexity of the solution, expressed mainly as the number of rules.

Self-replicating loops presented to date are essentially worlds unto themselves, inaccessible to the observer once the replication process is launched. In this article we present the design of an interactive self-replicating loop of arbitrary size, wherein the user can physically control the loop's replication and induce its destruction. After introducing the BioWall, a reconfigurable electronic wall for bio-inspired applications, we describe the design of our novel loop and delineate its hardware implementation in the wall.

Co-evolutionary algorithms have received increased attention in the past few years within the domain of evolutionary computation. In this paper, we combine the search power of co-evolutionary computation with the expressive power of fuzzy systems, and introduce a novel algorithm, called Fuzzy CoCo (fuzzy cooperative coevolution). We demonstrate the efficacy of Fuzzy CoCo by applying it to a hard, real-world problem - breast cancer diagnosis, obtaining the best results to date while expending less computational effort than previous processes. Analyzing our results, we derive guidelines for setting the algorithm parameters given a (hard) problem to solve. We hope Fuzzy CoCo proves to be a powerful tool in the fuzzy modeler toolkit.

Coevolutionary algorithms have received increased attention in the past few years within the domain of evolutionary computation. We combine the search power of coevolutionary computation with the expressive power of fuzzy systems, introducing a novel algorithm, Fuzzy CoCo: Fuzzy Cooperative Coevolution. We demonstrate the efficacy of Fuzzy CoCo by applying it to a hard, real-world problem-breast cancer diagnosis-obtaining the best results to date while expending less computational effort than formerly.

The growth and operation of all living beings are directed by the interpretation, in each of their cells, of a chemical program, the DNA string or genome. This process is the source of inspiration for the Embryonics (embryonic electronics) project, whose final objective is the design of highly robust integrated circuits, endowed with properties usually associated with the living world: self-repair (cicatrization) and self-replication. The Embryonics architecture is based on four hierarchical levels of organization. (1) The basic primitive of our system is the molecule, a multiplexer-based element of a novel programmable circuit. (2) A finite set of molecules makes up a cell, essentially a small processor with an associated memory. (3) A finite set of cells makes up an organism, an application-specific multiprocessor system. (4) The organism can itself replicate, giving rise to a population of identical organisms. We begin by describing in detail the implementation of an artificial cell characterized by a fixed architecture, showing that multicellular arrays can realize a variety of different organisms, all capable of self-replication and self-repair. In order to allow for a wide range of applications, we then introduce a flexible architecture, realized using a new type of fine-grained field-programmable gate array whose basic element, our molecule, is essentially a programmable multiplexer. We describe the implementation of such a molecule, with built-in self-test, and illustrate its use in realizing two applications: a modulo-4 reversible counter (a unicellular organism) and a timer ( a complex multicellular organism). We describe our ongoing research efforts to meet three challenges: a scientific challenge, that of implementing the original specifications formulated by John von Neumann for the conception of a self-replicating automaton; a technical challenge, that of realizing very robust integrated circuits capable of self-repair and self-replication; and a biological challenge, that of attempting to show that the microscopic architectures of artificial and natural organisms, i.e., their genomes, share common properties.

Finding good random number generators (RNGs) is a hard problem that is of crucial import in several fields, ranging from large-scale statistical physics simulations to hardware self-test. In this paper, we employ the cellular programming evolutionary algorithm to automatically generate two-dimensional cellular automata (CA) RNGs. Applying an extensive suite of randomness tests to the evolved CAs, we demonstrate that they rapidly produce high-quality random-number sequences. Moreover, based on observations of the evolved CAs, we are able to handcraft even better RNGs, which not only outperform previously demonstrated high-quality RNGs, but can be potentially tailored to satisfy given hardware constraints.

The field of artificial life (Alife) is replete with documented instances of emergence, though debate still persists as to the meaning of this term. We contend that, in the absence of an acceptable definition, researchers in the field would be well served by adopting an emergence certification mark that would garner approval from the Alife community. Toward this end, we propose an emergence test, namely, criteria by which one can justify conferring the emergence label.

Parallel evolutionary algorithms, over the past few years, have proven empirically worthwhile, but there seems to be a lack of understanding of their workings. In this paper we concentrate on cellular (fine-grained) models, our objectives being: (1) to introduce a suite of statistical measures, both at the genotypic and phenotypic levels, which are useful for analyzing the workings of cellular evolutionary algorithms; and (2) to demonstrate the application and utility of these measures on a specific example-the cellular programming evolutionary algorithm. The latter is used to evolve solutions to three distinct (hard) problems in the cellular-automata domain: density, synchronization, and random number generation. Applying our statistical measures, we are able to identify a number of trends common to all three problems (which may represent intrinsic properties of the algorithm itself), as well as a host of problem-specific features. We find that the evolutionary algorithm tends to undergo a number of phases which we are able to quantitatively delimit. The results obtained lead us to believe that the measures presented herein may prove useful in the general case of analyzing fine-grained evolutionary algorithms.

Field-programmable gate arrays (FPGAs) are large, fast integrated circuits-that can be modified, or configured, almost at any point by the end user. Within the domain of configurable computing, we distinguish between two modes of configurability: static-where the configurable processor's configuration string is loaded once at the outset, after which it does not change during execution of the task at hand, and dynamic-where the processor's configuration may change at any moment. This paper describes four applications in the domain of configurable computing, considering both static and dynamic systems, including: SPYDER (a reconfigurable processor development system), RENCO (a reconfigurable network computer), Firefly (an evolving machine), and the BioWatch (a self-repairing watch). While static configurability mainly aims at attaining the classical computing goal of improving performance, dynamic configurability might bring about an entirely new breed of hardware devices-ones that are able to adapt within dynamic environments.

If one considers life on Earth since its very beginning, three levels of organization can be distinguished: the phylogenetic level concerns the temporal evolution of the genetic programs within individuals and species, the ontogenetic level concerns the developmental process of a single multicellular organism, and the epigenetic level concerns the learning processes during an individual organism's lifetime. In analogy to nature, the space of bio-inspired hardware systems can be partitioned along these three axes, phylogeny, ontogeny, and epigenesis, giving rise to the POE model, recently introduced by M. Sipper et al. (1997). In this short paper we briefly present three FPGA-based systems, each situated along a different axis of the POE model.

The study of self-replicating structures or machines has been taking place now for almost half a century. My goal in this article is to present an overview of research carried out in the domain of self-replication over the past 50 years, starting from von Neumann's work in the late 1940s and continuing to the most recent research efforts. I shall concentrate on computational models, that is, ones that have been studied from a computer science point of view, be it theoretical or experimental. The systems are divided into four major classes, according to the model on which they are based: cellular automata, computer programs, strings (or strands), or an altogether different approach. With the advent of new materials, such as synthetic molecules and nanomachines, it is quite possible that we shall see this somewhat theoretical domain of study producing practical, real-world applications.

In this short article, we argue that von Neumann's quintessential message with respect to self-replicating automata is genotype + ribotype = phenotype. Self-replication occurs in analogy to nature: The description (genotype) written on the input tape is translated via a ribosome (ribotype) so as to create the offspring universal constructor (phenotype).

If one considers life on Earth since its very beginning, three levels of organization can be distinguished: the phylogenetic level concerns the temporal evolution of the genetic programs within individuals and species, the ontogenetic level concerns the developmental process of a single multicellular organism, and the epigenetic level concerns the learning processes during an individual organism's lifetime. In analogy to nature, the space of bio-inspired hardware systems can be partitioned along these three axes-phylogeny, ontogeny and epigenesis (POE)-giving rise to the POE model. This paper is an exposition and examination of bio-inspired systems within the POE framework, with our goals being: (1) to present an overview of current-day research, (2) to demonstrate that the POE model can be used to classify bio-inspired systems, and (3) to identify possible directions for future research, derived from a POE outlook. We discuss each of the three axes separately, considering the systems created to date and plotting directions for continued progress along the axis in question.

We analyze in detail the performance of a Hamming network classifying inputs that are distorted versions of one of its m stored memory patterns, each being a binary vector of length n. It is shown that the activation function of the memory neurons in the original Hamming network may be replaced by a simple threshold function. By judiciously determining the threshold value, the "winner-take-all" subnet of the Hamming network (known to be the essential factor determining the time complexity of the network's computation) may be altogether discarded. For m growing exponentially in n, the resulting threshold Hamming network correctly classifies the input pattern in a single iteration, with probability approaching 1.

Some of the major outstanding problems in biology are related to issues of emergence and evolution. These include: (a) how populations of organisms traverse their adaptive landscapes; (b) what the relation between adaptedness and fitness is; and (c) the formation of multicellular organisms from basic units or cells. In this article we study these issues using a model that is both general and simple. The system, derived from the CA (cellular automata) model, consists of a two-dimensional grid of interacting organisms that may evolve over time. We first present designed multicellular organisms that display several interesting behaviors, including reproduction, growth, and mobility. We then turn our attention to evolution in various environments, including an environment in which competition for space occurs, an IPD (Iterated Prisoner's Dilemma) environment, an environment of spatial niches, and an environment of temporal niches. One of the advantages of artificial life (AL) models is the opportunities they offer in performing in-depth studies of the evolutionary process. This is accomplished in our case by observing not only phenotypic effects but also such measures as fitness, operability, energy and the genescape. Our work sheds light on the problems raised above, and offers a possible path toward the long-term, two-fold goal of ALife research: (a) increasing our understanding of biology, and (b) enhancing our understanding of artificial models, thereby providing us with the ability to improve their performance.

Neural networks consist of simple elements capable of summation and thresholding. The authors define a more general element, the task-oriented neuron or teuron, which can compute higher-order functions. They further define teuron networks and show two such networks that can be used as content addressable memories and as pattern classifiers. The first network is based on the Godel encoding scheme. It uses this scheme in order to memorize sequences of numbers. These sequences are then stored analogically. The second network uses binary encoding, i.e. a binary sequence is translated into its decimal equivalent and then stored analogically. The authors demonstrate the feasibility of implementing such networks. It is concluded that they can be implemented in such a way as to reduce cost, due to a reduction in the number of elements coupled with constancy of link values (synaptic weights).>