Finite populations choose an optimal language

This paper studies the evolution of a proto-language in a finite population under the frequency-dependent Moran process. A proto-language can be seen as a collection of concept-to-sign mappings. An efficient proto-language is a bijective mapping from objects of communication to used signs and vice versa. Based on the comparison of fixation probabilities, a method for deriving conditions of evolutionary stability in a finite population [Nowak et al., 2004. Emergence of cooperation and evolutionary stability in finite populations. Nature 428, 246-650], it is shown that efficient proto-languages are the only strategies that are protected by selection, which means that no mutant strategy can have a fixation probability that is greater than the inverse population size. In passing, the paper provides interesting results about the comparison of fixation probabilities as well as Maynard Smith's notion of evolutionary stability for finite populations [Maynard Smith, 1988. Can a mixed strategy be stable in a finite population? J. Theor. Biol. 130, 247-251] that are generally true for games with a symmetric payoff function.     

Evolutionary graph theory: breaking the symmetry between interaction and replacement

We study evolutionary dynamics in a population whose structure is given by two graphs: the interaction graph determines who plays with whom in an evolutionary game; the replacement graph specifies the geometry of evolutionary competition and updating. First, we calculate the fixation probabilities of frequency dependent selection between two strategies or phenotypes. We consider three different update mechanisms: birth-death, death-birth and imitation. Then, as a particular example, we explore the evolution of cooperation. Suppose the interaction graph is a regular graph of degree h, the replacement graph is a regular graph of degree g and the overlap between the two graphs is a regular graph of degree l. We show that cooperation is favored by natural selection if b/c>hg/l. Here, b and c denote the benefit and cost of the altruistic act. This result holds for death-birth updating, weak-selection and large population size. Note that the optimum population structure for cooperators is given by maximum overlap between the interaction and the replacement graph (g=h=l), which means that the two graphs are identical. We also prove that a modified replicator equation can describe how the expected values of the frequencies of an arbitrary number of strategies change on replacement and interaction graphs: the two graphs induce a transformation of the payoff matrix.     

Fixation probabilities in evolutionary game dynamics with a two-strategy game in finite diploid populations

Fixation processes in evolutionary game dynamics in finite diploid populations are investigated. Traditionally, frequency dependent evolutionary dynamics is modeled as deterministic replicator dynamics. This implies that the infinite size of the population is assumed implicitly. In nature, however, population sizes are finite. Recently, stochastic processes in finite populations have been introduced in order to study finite size effects in evolutionary game dynamics. One of the most significant studies on evolutionary dynamics in finite populations was carried out by Nowak et al. which describes “one-third law” [Nowak, et al., 2004. Emergence of cooperation and evolutionary stability in finite populations. Nature 428, 646-650]. It states that under weak selection, if the fitness of strategy α is greater than that of strategy β when α has a frequency , strategy α fixates in a β-population with selective advantage. In their study, it is assumed that the inheritance of strategies is asexual, i.e. the population is haploid. In this study, we apply their framework to a diploid population that plays a two-strategy game with two ESSs (a bistable game). The fixation probability of a mutant allele in this diploid population is derived. A “three-tenth law” for a completely recessive mutant allele and a “two-fifth law” for a completely dominant mutant allele are found; other cases are also discussed.     

The evolution of phenotypic traits in a predator-prey system subject to Allee effect

This paper considers the evolution of phenotypic traits in a community comprising the populations of predators and prey subject to Allee effect. The evolutionary model is constructed from a deterministic approximation of the stochastic process of mutation and selection. Firstly, we investigate the ecological and evolutionary conditions that allow for continuously stable strategy and evolutionary branching. We find that the strong Allee effect of prey facilitates the formation of continuously stable strategy in the case that prey population undergoes evolutionary branching if the Allee effect of prey is not strong enough. Secondly, we show that evolutionary suicide is impossible for prey population when the intraspecific competition of prey is symmetric about the origin. However, evolutionary suicide can occur deterministically on prey population if prey individuals undergo strong asymmetric competition and are subject to Allee effect. Thirdly, we show that the evolutionary model with symmetric interactions admits a stable limit cycle if the Allee effect of prey is weak. Evolutionary cycle is a likely outcome of the process, which depends on the strength of Allee effect and the mutation rates of predators and prey.     

Evolution of cooperation under -person snowdrift games

In the animal world, performing a given task which is beneficial to an entire group requires the cooperation of several individuals of that group who often share the workload required to perform the task. The mathematical framework to study the dynamics of collective action is game theory. Here we study the evolutionary dynamics of cooperators and defectors in a population in which groups of individuals engage in N-person, non-excludable public goods games. We explore an N-person generalization of the well-known two-person snowdrift game. We discuss both the case of infinite and finite populations, taking explicitly into consideration the possible existence of a threshold above which collective action is materialized. Whereas in infinite populations, an N-person snowdrift game (NSG) leads to a stable coexistence between cooperators and defectors, the introduction of a threshold leads to the appearance of a new interior fixed point associated with a coordination threshold. The fingerprints of the stable and unstable interior fixed points still affect the evolutionary dynamics in finite populations, despite evolution leading the population inexorably to a monomorphic end-state. However, when the group size and population size become comparable, we find that spite sets in, rendering cooperation unfeasible.     

Toward a theory of evolutionary computation

We outline a theory of evolutionary computation using a formal model of evolutionary computation--the Evolutionary Turing Machine--which is introduced as the extension of the Turing Machine model. Evolutionary Turing Machines provide a better and a more complete model for evolutionary computing than conventional Turing Machines, algorithms, and Markov chains. The convergence and convergence rate are defined and investigated in terms of this new model. The sufficient conditions needed for the completeness and optimality of evolutionary search are investigated. In particular, the notion of the total optimality as an instance of the multiobjective optimization of the Universal Evolutionary Turing Machine is introduced. This provides an automatic way to deal with the intractability of evolutionary search by optimizing the quality of solutions and search costs simultaneously. Based on a new model a very flexible classification of optimization problem hardness for the evolutionary techniques is proposed. The expressiveness of evolutionary computation is investigated. We show that the problem of the best evolutionary algorithm is undecidable independently of whether the fitness function is time dependent or fixed. It is demonstrated that the evolutionary computation paradigm is more expressive than Turing Machines, and thus the conventional computer science based on them. We show that an Evolutionary Turing Machine is able to solve nonalgorithmically the halting problem of the Universal Turing Machine and, asymptotically, the best evolutionary algorithm problem. In other words, the best evolutionary algorithm does not exist, but it can be potentially indefinitely approximated using evolutionary techniques.     

Influence of gene-linkage and recombination of evolutionary algorithms on the rate of evolution, genetic diversity and the response of evolving populations to disturbance

Both biological populations and fault tolerant evolvable hardware systems need to respond rapidly to changes in their dynamic environmental niche. Such changes can be caused by a disturbance event or fault occurring. Here I examine evolutionary algorithms, based on eukaryote sexual selection, which allow different levels of recombination of ‘genes’. The differences in recombination are based on ‘genes’ related to the optimisation process being either linked on a single ‘chromosome’ or being present on separate ‘chromosomes’. When genes are present on separate chromosomes the initial rate of evolution of a randomly generated population is faster than if the genes are linked on the same chromosome. However, when the optimisation problem is changed during the optimisation period, indicating a disturbance or fault occurring, the initial fitness of the linked population is higher and the rate of optimisation immediately after the disturbance is more rapid than for the non-linked populations. The genotypic and phenotypic diversity of the linked populations are also significantly higher immediately prior to the disturbance event. I propose this diversity provides the necessary variation to allow more rapid evolution following a disturbance. The results demonstrate the importance of population diversity in response to change, supporting theory from conservation biology.     

Current developments and future directions of bio-inspired computation and implications for ecoinformatics

Evolutionary and neural computation has been used widely in solving various problems in biological ecosystems. This paper reviews some of the recent work in evolutionary computation and neural network ensembles that could be explored further in the context of ecoinformatics. Although these bio-inspired techniques were not developed specifically for ecoinformatics, their successes in solving complex problems in other fields demonstrate how these techniques could be adapted and used for tackling difficult problems in ecoinformatics. Firstly, we will review our work in modelling and model calibration, which is an important topic in ecoinformatics. Secondly one example will be given to illustrate how coevolutionary algorithms could be used in problem-solving. Thirdly, we will describe our work on neural network ensembles, which can be used for various classification and prediction problems in ecoinformatics. Finally, we will discuss ecosystem-inspired computational models and algorithms that could be explored as directions of future research.     

On evolution under symmetric and asymmetric competitions

This paper considers the coevolution of phenotypic traits in a community comprising two competitive species subject to strong Allee effects. Firstly, we investigate the ecological and evolutionary conditions that allow for continuously stable strategy under symmetric competition. Secondly, we find that evolutionary suicide is impossible when the two species undergo symmetric competition, however, evolutionary suicide can occur in an asymmetric competition model with strong Allee effects. Thirdly, it is found that evolutionary bistability is a likely outcome of the process under both symmetric and asymmetric competitions, which depends on the properties of symmetric and asymmetric competitions. Fourthly, under asymmetric competition, we find that evolutionary cycle is a likely outcome of the process, which depends on the properties of both intraspecific and interspecific competition. When interspecific and intraspecific asymmetries vary continuously, we also find that the evolutionary dynamics may admit a stable equilibrium and two limit cycles or two stable equilibria separated by an unstable limit cycle or a stable equilibrium and a stable limit cycle.     

Ecological public goods games: cooperation and bifurcation

The Public Goods Game is one of the most popular models for studying the origin and maintenance of cooperation. In its simplest form, this evolutionary game has two regimes: defection goes to fixation if the multiplication factor r is smaller than the interaction group size N, whereas cooperation goes to fixation if the multiplication factor r is larger than the interaction group size N. Hauert et al. [Hauert, C., Holmes, M., Doebeli, M., 2006a. Evolutionary games and population dynamics: Maintenance of cooperation in public goods games. Proc. R. Soc. Lond. B 273, 2565-2570] have introduced the Ecological Public Goods Game by viewing the payoffs from the evolutionary game as birth rates in a population dynamic model. This results in a feedback between ecological and evolutionary dynamics: if defectors are prevalent, birth rates are low and population densities decline, which leads to smaller interaction groups for the Public Goods game, and hence to dominance of cooperators, with a concomitant increase in birth rates and population densities. This feedback can lead to stable co-existence between cooperators and defectors. Here we provide a detailed analysis of the dynamics of the Ecological Public Goods Game, showing that the model exhibits various types of bifurcations, including supercritical Hopf bifurcations, which result in stable limit cycles, and hence in oscillatory co-existence of cooperators and defectors. These results show that including population dynamics in evolutionary games can have important consequences for the evolutionary dynamics of cooperation.     

Evolutionary stability for large populations

We present a revision of Maynard Smith's evolutionary stability criteria for populations which are very large (though technically finite) and of unknown size. We call this the large population ESS, as distinct from Maynard Smith's infinite population ESS and Schaffer's finite population ESS. Building on Schaffer's finite population model, we define the large population ESS as a strategy which cannot be invaded by any finite number of mutants, as long as the population size is sufficiently large. The large population ESS is not equivalent to the infinite population ESS: we give examples of games in which a large population ESS exists but an infinite population ESS does not, and vice versa. Our main contribution is a simple set of two criteria for a large population ESS, which are similar (but not identical) to those originally proposed by Maynard Smith for infinite populations.     

Designing convergent cellular automata

Cellular automata (CA) have been used by biologists to study dynamic non-linear systems where the interaction between cell behaviour and end-pattern is investigated. It is difficult to achieve convergence of a CA towards a specific static pattern and a common solution is to use genetic algorithms and evolve a ruleset that describes cell behaviour. This paper presents an alternative means of designing CA to converge to specific static patterns. A matrix model is introduced and analysed then a design algorithm is demonstrated. The algorithm is significantly less computationally intensive than equivalent evolutionary algorithms, and not limited in scale, complexity or number of dimensions.     

Evolutionary dynamics in structured populations

Evolutionary dynamics shape the living world around us. At the centre of every evolutionary process is a population of reproducing individuals. The structure of that population affects evolutionary dynamics. The individuals can be molecules, cells, viruses, multicellular organisms or humans. Whenever the fitness of individuals depends on the relative abundance of phenotypes in the population, we are in the realm of evolutionary game theory. Evolutionary game theory is a general approach that can describe the competition of species in an ecosystem, the interaction between hosts and parasites, between viruses and cells, and also the spread of ideas and behaviours in the human population. In this perspective, we review the recent advances in evolutionary game dynamics with a particular emphasis on stochastic approaches in finite sized and structured populations. We give simple, fundamental laws that determine how natural selection chooses between competing strategies. We study the well-mixed population, evolutionary graph theory, games in phenotype space and evolutionary set theory. We apply these results to the evolution of cooperation. The mechanism that leads to the evolution of cooperation in these settings could be called ‘spatial selection’: cooperators prevail against defectors by clustering in physical or other spaces.     

Darwinian fitness

The term Darwinian fitness refers to the capacity of a variant type to invade and displace the resident population in competition for available resources. Classical models of this dynamical process claim that competitive outcome is a deterministic event which is regulated by the population growth rate, called the Malthusian parameter. Recent analytic studies of the dynamics of competition in terms of diffusion processes show that growth rate predicts invasion success only in populations of infinite size. In populations of finite size, competitive outcome is a stochastic process--contingent on resource constraints--which is determined by the rate at which a population returns to its steady state condition after a random perturbation in the individual birth and death rates. This return rate, a measure of robustness or population stability, is analytically characterized by the demographic parameter, evolutionary entropy, a measure of the uncertainty in the age of the mother of a randomly chosen newborn. This article appeals to computational and numerical methods to contrast the predictive power of the Malthusian and the entropic principles. The computational analysis rejects the Malthusian model and is consistent with of the entropic principle. These studies thus provide support for the general claim that entropy is the appropriate measure of Darwinian fitness and constitutes an evolutionary parameter with broad predictive and explanatory powers.     

Maintenance affects the stability of a two-tiered microbial 'food chain'?

Recent studies have shown that constraints on available resources may play an important role in the evolution of cooperation, especially when individuals do not posses the capacity to recognize other individuals, memory or other developed abilities, as it is the case of most unicellular organisms, algae or even plants. We analyze the evolution of cooperation in the case of a limiting resource, which is necessary for reproduction and survival. We show that, if the strategies determine a prisoner's dilemma, the outcome of the interactions may be modified by the limitation of resources allowing cooperators to invade the entire population. Analytic expressions for the region of cooperation are provided. Furthermore we derive expressions for the connection between fitness, as understood in evolutionary game theory, and resource exchanges, which may be of help to link evolutionary game theoretical results with resource based models.     

Emergence and resilience of cooperation in the spatial prisoner's dilemma via a reward mechanism

We study the problem of the emergence of cooperation in the spatial Prisoner's Dilemma. The pioneering work by Nowak and May [1992. Evolutionary games and spatial chaos. Nature 415, 424-426] showed that large initial populations of cooperators can survive and sustain cooperation in a square lattice with imitate-the-best evolutionary dynamics. We revisit this problem in a cost-benefit formulation suitable for a number of biological applications. We show that if a fixed-amount reward is established for cooperators to share, a single cooperator can invade a population of defectors and form structures that are resilient to re-invasion even if the reward mechanism is turned off. We discuss analytically the case of the invasion by a single cooperator and present agent-based simulations for small initial fractions of cooperators. Large cooperation levels, in the sustainability range, are found. In the conclusions we discuss possible applications of this model as well as its connections with other mechanisms proposed to promote the emergence of cooperation.     

Benchmarking the Clustering Performances of Evolutionary Algorithms: A Case Study on Varying Data Size

Background and objectiveClustering is a widely used popular method for data analysis within many clustering algorithms for years. Today it is used in many predictions, collaborative filtering and automatic segmentation systems on different domains. Also, to be broadly used in practice, such clustering algorithms need to give both better performance and robustness when compared to the ones currently used. In recent years, evolutionary algorithms are used in many domains since they are robust and easy to implement. And many clustering problems can be easily solved with such algorithms if the problem is modeled as an optimization problem. In this paper, we present an optimization approach for clustering by using four well-known evolutionary algorithms which are Biogeography-Based Optimization (BBO), Grey Wolf Optimization (GWO), Genetic Algorithm (GA) and Particle Swarm Optimization (PSO).Methodthe objective function has been specified to minimize the total distance from cluster centers to the data points. Euclidean distance is used for distance calculation. We have applied this objective function to the given algorithms both to find the most efficient clustering algorithm and to compare the clustering performances of algorithms against different data sizes. In order to benchmark the clustering performances of algorithms in the experiments, we have used a number of datasets with different data sizes such as some small scale, medium and big data. The clustering performances have been compared to K-means as it is a widely used clustering algorithm for years in literature. Rand Index, Adjusted Rand Index, Mirkin's Index and Hubert's Index have been considered as parameters for evaluating the clustering performances.ResultAs a result of the clustering experiments of algorithms over different datasets with varying data sizes according to the specified performance criteria, GA and GWO algorithms show better clustering performances among the others.ConclusionsThe results of the study showed that although the algorithms have shown satisfactory clustering results on small and medium scale datasets, the clustering performances on Big data need to be improved.     

Tit-for-tat or win-stay, lose-shift?

The repeated Prisoner's Dilemma is usually known as a story of tit-for-tat (TFT). This remarkable strategy has won both of Robert Axelrod's tournaments. TFT does whatever the opponent has done in the previous round. It will cooperate if the opponent has cooperated, and it will defect if the opponent has defected. But TFT has two weaknesses: (i) it cannot correct mistakes (erroneous moves) and (ii) a population of TFT players is undermined by random drift when mutant strategies appear which play always-cooperate (ALLC). Another equally simple strategy called 'win-stay, lose-shift' (WSLS) has neither of these two disadvantages. WSLS repeats the previous move if the resulting payoff has met its aspiration level and changes otherwise. Here, we use a novel approach of stochastic evolutionary game dynamics in finite populations to study mutation-selection dynamics in the presence of erroneous moves. We compare four strategies: always-defect (ALLD), ALLC, TFT and WSLS. There are two possible outcomes: if the benefit of cooperation is below a critical value then ALLD is selected; if the benefit of cooperation is above this critical value then WSLS is selected. TFT is never selected in this evolutionary process, but lowers the selection threshold for WSLS.     

Evolution with material symbol systems

Pattee's semantic closure principle is used to study the characteristics and requirements of evolving material symbols systems. By contrasting agents that reproduce via genetic variation with agents that reproduce via self-inspection, we reach the conclusion that symbols are necessary to attain open-ended evolution, but only if the phenotypes of agents are the result of a material, self-organization process. This way, a study of the inter-dependencies of symbol and matter is presented. This study is based first on a theoretical treatment of symbolic representations, and secondly on simulations of simple agents with matter-symbol inter-dependencies. The agent-based simulations use evolutionary algorithms with indirectly encoded phenotypes. The indirect encoding is based on Fuzzy Development programs, which are procedures for combining fuzzy sets in such a way as to model self-organizing development processes.