Simulating Evolution on Fitness Landscapes represented by Valued Constraint Satisfaction Problems
Recent theoretical research proposes that computational complexity can be seen as an ultimate constraint that allows for open-ended biological evolution on finite static fitness landscapes. Whereas on easy fitness landscapes, evolution will quickly converge to a local fitness peaks, on hard fitness landscapes this computational constraints prevents evolution from reaching any local fitness peak in polynomial time. Valued constraint satisfaction problems (VCSPs) can be used to represent both easy and hard fitness landscapes. Thus VCSPS can be seen as a natural way of linking the theory of evolution with notions of computer science to better understand the features that make landscapes hard. However, there are currently no simulators that study VCSP-structured fitness landscapes. This report describes the design and build of an evolution simulator for VCSP-structured fitness landscapes. The platform is used for simulating various instances of easy and hard fitness landscapes. In particular, we look at evolution under more realistic assumptions than fittest mutant strong-selection weak mutation dynamics on the winding semismooth fitness landscape. The results obtained match with the theoretical expectations, while also providing new information about the limits of evolution. The last part of the report introduces a mathematical model for smooth fitness landscapes and uses it to better understand why these landscapes are easy.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Simulating short- and long-term evolutionary dynamics on rugged landscapes
We propose a minimal model to simulate long waiting times followed by evolutionary bursts on rugged landscapes. It combines point and inversions-like mutations as sources of genetic variation. The inversions are intended…
Geometry of fitness landscapes: Peaks, shapes and universal positive epistasis
Darwinian evolution is driven by random mutations, genetic recombination (gene shuffling) and selection that favors genotypes with high fitness. For systems where each genotype can be represented as a bitstring of length…
Codynamic Fitness Landscapes of Coevolutionary Minimal Substrates
Coevolutionary minimal substrates are simple and abstract models that allow studying the relationships and codynamics between objective and subjective fitness. Using these models an approach is presented for defining and…
Computational and Experimental Exploration of Protein Fitness Landscapes: Navigating Smooth and Rugged Terrains
Proteins evolve through complex sequence spaces, with fitness landscapes serving as a conceptual framework that links sequence to function. Fitness landscapes can be smooth, where multiple similarly accessible evolutiona…
Complexity of evolutionary equilibria in static fitness landscapes
A fitness landscape is a genetic space -- with two genotypes adjacent if they differ in a single locus -- and a fitness function. Evolutionary dynamics produce a flow on this landscape from lower fitness to higher; reach…