An abstract model of nonrandom, non-Lamarckian mutation in evolution using a multivariate estimation-of-distribution algorithm
Authors: Liudmyla Vasylenko, Adi Livnat
Organizations: Department of Evolutionary and Environmental Biology, University of Haifa, 3103301, Israel · Institute of Evolution, University of Haifa, 3103301, Israel
At the fundamental conceptual level, two alternatives have traditionally been considered for how mutations arise and how evolution happens: 1) random mutation and natural selection, and 2) Lamarckism. Recently, the theory of Interaction-based Evolution (IBE) has been proposed, according to which mutations are neither random nor Lamarckian, but are influenced by information accumulating internally in the genome over generations. Based on the estimation-of-distribution algorithms framework, we present a simulation model that demonstrates nonrandom, non-Lamarckian mutation concretely while capturing indirectly several aspects of IBE: selection, recombination, and nonrandom, non-Lamarckian mutation interact in a complementary fashion; evolution is driven by the interaction of parsimony and fit; and random bits do not directly encode improvement but enable generalization by the manner in which they connect with the rest of the evolutionary process. Connections are drawn to Darwin's observations that changed conditions increase the rate of production of heritable variation; to the causes of bell-shaped distributions of traits and how these distributions respond to selection; and to computational learning theory, where analogizing evolution to learning in accord with IBE casts individuals as examples and places the learned hypothesis at the population level. The model highlights the importance of incorporating internal integration of information through heritable change in both evolutionary theory and evolutionary computation.
Figures & tables
Figure 1: The origination of heritable change is influenced by fan-in of heritable information, according to the theory of interaction-based evolution (image from ref. [ 19 ] ; see also ref. [ 17 ] ). a ) Gene products as well as genetic sequences arising from or residing at multiple recombining loci interact in influencing the origination of a heritable change, whether a DNA mutation or an epigenetic change. In this schematic figure, this coming together of information leads to a new mutation, B*. b ) As a result, even though the genes involved in the interaction may be separated by sexual recombination, the combination that they once were does have a heritable effect on future generations through the heritable change that was derived from it (B*). For simplicity, only three loci are presented, though in reality many loci can be involved in an interaction, directly or indirectly.
Figure 2: The fan-in of information in the generation of heritable change enables a network of information flow across the genome and through the generations (image from ref. [ 17 ] ). Each box represents an individual. The large boxes represent two parents (top) and their offspring. The two dashed lines at the top of each large box represent the individual’s diploid genome (each pair of dashes represents a diploid locus), and the dashed line at the bottom represents the haploid genome of a gamete that is transferred to the next generation. The figure demonstrates schematically that an output of a heritable change event at one generation (e.g., C*) can serve as an input into heritable change events at later generations (D*). This connectedness generates a network of information flow across the genome and through the generations [ 17 ] .
Figure 3: A comparison between basic evolutionary algorithms (EAs) and the RBM-based EDA model described here. a ) A schematic diagram of a basic evolutionary algorithm. At each generation, the top performer is selected and produces the next generation via self-replication and random changes representing mutations. b ) A schematic diagram of the RBM-based EDA model. At each generation, a certain percentage of top performers is selected. Indirectly representing sexual recombination and nonrandom, non-Lamarckian mutation, an RBM is trained on the genomes of these top performers and, following training, is used to produce the next generation. c ) An example of a Restricted Boltzmann Machine (RBM) with three visible units vi , six hidden units hj , 18 weights wi,j between them, and nine biases in total for visible ( ai ) and hidden ( bj ) units. In the simulations to follow, the number of visible units equals the genome length, which can be much larger than three. During training, the genomes of the surviving individuals are fed one by one into the visible units, and the weights and biases are adjusted accordingly (see Section 4 for details).
population size, N→
2
10
100
1000
10000
SRM
μ
1
0.919
0.974
0.986
0.986
0.985
2
0.917
0.966
0.986
0.99
0.989
1
3
0.925
0.957
0.981
0.989
0.991
individual
4
0.925
0.947
0.976
0.987
0.991
5
0.927
0.948
0.973
0.984
0.989
Table 1: Population mean fitness values at generation 500 in the RM model for a MAX-3-SAT example with n=1200 variables. Some cells are blank because, for the corresponding population size and percentage of surviving individuals, either one or no individuals survive (if one individual survives, the results are presented in the top block of the table, and if no individual survives, the simulation cannot be run). In the first two rows, the results are better with μ=2 than with μ=1 for larger population sizes. The reason is that when only one individual survives, only n different individuals can be produced by flipping only a single bit in the genome per offspring. Therefore, increasing N beyond n will not improve the results—it will merely generate duplicate individuals—unless μ is increased as well. This kind of effect applies only when the number of surviving individuals is small relative to the population size, so that the initial variation from which the next generation is produced is small. At the same time, increasing the percentage of surviving individuals is typically detrimental for the RM model.
Parameter
RBM
RM
Problem
3-SAT
3-SAT
Population size, N
100,1000,10000
2,10,100,1000,10000
Percentage of surviving individuals,
5% , 10% , 50%
1 individual, 1% ,
SRBM,SRM
5% , 10% , 50%
Number of hidden nodes, H
1×,2× problem size
N/A
Number of iterations, T
20,100
N/A
Table 2: Parameters used in the RM and RBM models.
Figure 4: a ) wˉ in the RBM (blue), RM (red) and BRG (grey) models for three MAX-3-SAT instances of 150 , 600 and 2400 variables (rows) and three maximum population sizes Nmax (columns). Generations are on the x -axis. The difference between the RBM and RM mean fitnesses increases with the population size as well as with the problem size. The BRG curve, which provides a baseline for comparison, starts higher than the other curves because it represents not the mean fitness but the single highest fitness obtained up to the given generation by pure guessing. b ) Zooming in on the first 50 generations. The RM model performs better during the first few generations, while the RBM model exhibits a rapid transition during the transient.
Figure 5: wˉ over the generations in the genome completion test for even-parity Boolean functions with 2 , 3 , 4 and 5 variables, averaged over 100 independent runs. The known gene values are sampled from the population and the remaining gene value is completed by the RBM. The rows show results for functions of different numbers of variables, from n=2 to n=5 . The columns show results for different population sizes, from N=102 to N=106 . The other parameters are B=10 , T=20 , H=n , η=0.1 , SRBM=50% ; the number of genomes to complete is 100 , and the length of the pattern to be completed is one position shorter than the genome length. The average fitness of the inferred genomes is shown by an orange line, and the average fitness of shuffled genomes is shown by a grey line. In the left column, the population size is generally too small to learn several different solutions, and therefore the shuffled genomes are identical to the inferred genomes. This effect disappears for larger population sizes, showing a gap in wˉ between the inferred and shuffled genomes, which implies that information at one locus is generated based on information at other loci.
Figure 6: wˉ over the generations for two MAX- 3 -SAT instances ( 75 and 1200 variables) averaged over 100 independent runs for three different models: the full model (solid blue line), the weights-only model (dashed orange line) and the biases-only model (dashed green line). Results are shown for three different population sizes: N=100 (left), N=1000 (middle) and N=10,000 (right). The other RBM parameters are B=10 , SRBM=50% , T=20 , H=n for both n values; η=0.01 for n=75 and η=0.001 for n=1200 . In the 75 variables case, for bigger population sizes, both biases and interactions in the generation of information in the genome contribute to fitness. In the 1200 variables case, the importance of interactions entirely dominates that of the biases.
Figure 7: wˉ over time (left, blue) and the average expected heterozygosity, Heˉ over time (right, red) in the RBM model, averaged over 100 independent runs, for MAX-3-SAT instances with n=20 variables. Let He=1−p2−q2 , where p and q are frequencies of the two alleles, 0 and 1 , in a given locus, with p+q=1 , and let Heˉ be the mean He across loci, serving here as a measure of genetic variation. The top two panels show the results of simulations where the same selection pressure is maintained from beginning to end. All other rows show the results of simulations where the selection pressure is changed at generation G from one MAX-3-SAT instance to another ( G=10 , second row; G=30 , third row; and G=50 , bottom row). Other parameters are N=100 , B=10 , T=20 , H=n , η=0.1 , and SRBM=50% .
Figure 8: Distributions of the fitness values in the population at different generations in the RBM model for a MAX-3-SAT instance with n=600 . Fitness values were distributed across 0.005-sized bins and the number of fitness values per bin was normalized by the population size, N . Different panels show results for different population sizes ( N=100 , left; N=1000 , middle; and N=10000 , right), and, in each panel, fitness distributions for different generations between 1 and 100 are shown based on the color chart. The parameters were selected to provide the highest tested wˉ as measured at generation 100 . Specifically, for N=100 : B=10 , SRBM=50% , H=2n , T=20 and η=0.01 . For N=1000 : B=10 , SRBM=50% , H=2n , T=100 and η=0.001 . For N=10000 : B=100 , SRBM=10% , H=n , T=100 and η=0.01 .
Lamarckian inheritance has been shown to be a powerful accelerator in systems where the joint evolution of robot morphologies and controllers is enhanced with individual learning. Its defining advantage lies in the offspring inheriting controllers learned by their parents. The efficacy of this option, however, relies on morphological similarity between parent and offspring. In this study, we examine how Lamarckian inheritance performs when the search process is driven toward high morphological variance, potentially straining the requirement for parent-offspring similarity. Using a system of modular robots that can evolve and learn to solve a locomotion task, we compare Darwinian and Lamarckian evolution to determine how they respond to shifting from pure task-based selection to a multi-objective pressure that also rewards morphological novelty. Our results confirm that Lamarckian evolution outperforms Darwinian evolution when optimizing task-performance alone. However, introducing selection pressure for morphological diversity causes a substantial performance drop, which is much greater in the Lamarckian system. Further analyses show that promoting diversity reduces parent-offspring similarity, which in turn reduces the benefits of inheriting controllers learned by parents. These results reveal the limits of Lamarckian evolution by exposing a fundamental trade-off between inheritance-based exploitation and diversity-driven exploration.
Jed R Muff, Karine Miras, A. E. Eiben
Department of Computer Science Vrije Universiteit Amsterdam, The Netherlands
Evolutionary computation has long promised to deliver both high-performance optimization tools as well as rigorous scientific simulations of Darwinian evolution. However, modern algorithms frequently abandon evolutionary fidelity for physics-inspired heuristics or superficial biological metaphors. This paper derives a suite of advanced gradient-based optimization algorithms directly from evolutionary first principles. We introduce Darwinian Lineage Simulations (DLS) to prove that, in an asexual context, Fisher's and Wright's historically opposed views of evolution are actually formally equivalent; One can partition Fisher's deterministically-evolving total population into Wright's randomly-drifting sub-populations. We prove that proper bookkeeping requires introducing a specific kind of structured noise (the DLS noise relation). Crucially, any bookkeeping choices which satisfy this relation will yield a faithful simulation of evolution. Using this vast representational freedom, we prove that a broad family of battle-tested optimization algorithms are already perfectly compatible with evolutionary dynamics. These include: Stochastic Gradient Descent as well as many regularizations/approximations of Newton's method and Natural Gradient Descent. By simply adding DLS noise (i.e., evolutionarily faithful genetic drift), these algorithms become scientifically valid in silico simulations of Darwinian evolution. Finally, we demonstrate that even the state-of-the-art Adam optimizer can be brought into evolutionary compliance through a minor mathematical surgery.
Daniel Grimmer
Philosophy, Yale University, New Haven, 06511, USA
Baldwinian and Lamarckian evolution have existed for a long time in evolutionary algorithms (EAs) without ever dominating the academic literature or practical applications. In this work, we use modern empirical and theoretical methods to revisit Lamarckian and Baldwinian evolution and rigorously compare them with the generic Darwinian evolution. On the empirical side, we run a comprehensive suite of experiments on graphs from six different datasets from the recent GraphBench benchmark on Maximum Independent Set and Maximum Cut problems. Our results show that Baldwinian and Lamarckian evolution consistently outperform Darwinian evolution, confirming the great potential of local search augmented evolutionary algorithms. Notably, in the great majority of cases, all EAs outperform recent deep learning baselines and approach the performance of highly specialised heuristic and exact solvers. We furthermore report a high-performing set of generalist parameters for all studied evolution types that we hope will be of use to practitioners in future. On the theoretical side, we extend the existing DeceptiveLeadingBlocks benchmark to arbitrary block length k. For all constant k, we then prove asymptotically tight runtime bounds for the (1+1) EA in the three evolution types on this benchmark. For Baldwinian evolution, these are independent of k, whereas for the other two evolution types, the runtimes steeply increase with growing value of k.
Inès Benito, Johannes F. Lutzeyer, Benjamin Doerr
Laboratoire d’Informatique (LIX), CNRS, École Polytechnique, Institut Polytechnique de Paris, France