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.