I'm glad to see this paper is popular with twitter. Thanks! Since I don't have a SoundCloud to plug, I thought I'd make a tweetstorm summarizing the main results of this paper. There is a lot to go through, so I apologize for the length of the thread. But I hope you enjoy!
-
-
Prikaži ovu nit
-
Evolutionary constrains keep populations away from local optima (peaks) in fitness landscapes. I introduce a division of constraints into 2 types: proximal & ultimate. This is related to computer science distinction between algorithms & problems [1/n]:https://egtheory.wordpress.com/2018/07/24/evolutionary-constraints/ …
Prikaži ovu nit -
Proximal constrains are due to properties of the ‘algorithm’: i.e. strength of various other evolutionary forces (drift, entropic drive, etc), population structure, standing genetic variation, etc. [2/n]
Prikaži ovu nit -
Ultimate constraints are due exclusively to the ‘problem’: i.e. the fitness landscape itself (a combination of natural selection and the notion of ‘proximity’). [3/n]
Prikaži ovu nit -
A local peak stopping evolution from finding a global peak is a classical example of an ultimate constraint. The historicity constraint. But it is only partial: it prevents finding some optima (like the global one) by trapping us at other local optima. [4/n]
Prikaži ovu nit -
Paper's goal is to show full ultimate constraint: one that prevents finding any local optimum -- even the lowest fitness one. Thus, fitter mutants are 'always' available, even though landscape is finite. This would give us a foundational explanation for open-ended evolution [5/n]
Prikaži ovu nit -
To achieve this, I introduce the distinction between: Easy fitness landscapes where evolution can be proved to find a local peak in polynomial time, and Hard fitness landscapes where evolution cannot find _any_ local fitness peak in polynomial time. [6/n]
Prikaži ovu nit -
Epistasis between loci is what can make landscapes hard: https://egtheory.wordpress.com/2013/08/18/empirical-epistasis/ … There are three main kinds (and their rotations by relabeling) of epistasis on two loci: no epistais (or magnitude epistasis), sign epistasis, & reciprocal sign epistasis (RSE). [7/n]pic.twitter.com/4633cPr0n1
Prikaži ovu nit -
Reciprocal sign epistasis is req'd for ruggedness/multi-peak. (1st proved by Poelwijk et al.: https://www.sciencedirect.com/science/article/pii/S0022519310006703 … & diff. proof by me). So I def. landscapes as ‘semi-smooth’ if they have no RSE (but sign epistasis is possible). [8/n] For more, see:https://egtheory.wordpress.com/2013/09/12/semi-smooth-fitness-landscapes-and-the-simplex-algorithm/ …
Prikaži ovu nit -
To connect to
#cstheory, I show that semi-smooth fitness landscapes are equivalent tothe acyclic unique-sink orientations of polytopes (AUSOs) that are used in combinatorial optimization, especially in the analysis of simplex algorithms. [9/n]Prikaži ovu nit -
This allowed me to prove that in semi-smooth fitness landscapes, a minimal-length adaptive path always exists to the unique fitness peak. But this short adaptive path can be hard to spot among the long adaptive paths. [10/n]pic.twitter.com/QowgYi2AlQ
Prikaži ovu nit -
For example, if our model of evolution is the fittest-mutant strong-selection weak-mutation (SSWM) dynamic then I can (recursively) construct an explicit semi-smooth landscapes where the dynamics will take an exponential number of steps (i.e. be trapped on a long path). [11/n]pic.twitter.com/7yYCLpEIcE
Prikaži ovu nit -
If you want to construct your own hard semi-smooth landscapes, just apply the below recursion starting with any smooth fitness landscape. [12/n]pic.twitter.com/SsZ0newXq6
Prikaži ovu nit -
We can also show hardness for random fitter-mutant SSWM dynamics. Construction is more complicated but correspondence to AUSOs lets me use exiting results about simplex algorithms (from Matousek & Szabo: https://www.sciencedirect.com/science/article/pii/S0001870805001738 …) to get an exponential lower bound on length [13/n].pic.twitter.com/Sh9puqQb9k
Prikaži ovu nit -
But real fitness landscapes are believed to be rugged/multi-peaked (e.g. see landscape from https://www.pnas.org/content/106/29/12025 …): more complicated than semi-smooth! For rugged landscapes, we can prove even more surprising results. So I'll continue 2nd half of the paper after sleep [14/n].pic.twitter.com/JtsDDEL9Pe
Prikaži ovu nit -
With new day, let's continue thread with 2nd half of paper & be more concrete. For rugged landscapes, I consider a popular model of fitness landscapes where the amount of epistasis can be tuned: the NK-model introduced in 1987 by Kauffman & Levin [15/n]: https://www.sciencedirect.com/science/article/pii/S0022519387800292 …pic.twitter.com/TNXVZagsaa
Prikaži ovu nit -
I show that the NK-model is PLS-complete for K = 2 or higher: it is as hard to find a local fitness peak in these landscapes as for any polynomial local search problem. This is analogous to NP-completeness; i.e. NP-c to global peaks is as PLS-c to local peaks. [16/n]
Prikaži ovu nit -
This means (because the reduction has a certain form) that there are fitness landscapes and initial genotypes where every single adaptive path to any local peak is of exponential length: i.e. the landscape is hard for all imaginable adaptive dynamics. [17/n]pic.twitter.com/CsCgim3NQM
Prikaži ovu nit -
But this goes beyond adaptive dynamics! Given standard
#cstheory conjectures (PLS != FP): there exists no algorithm that can find a local fitness peak in polynomial time. Even if evolution goes through valleys, jumps around, etc, etc. – it still won’t find any local peak. [18/n]Prikaži ovu nit -
On these hardest fitness landscapes, evolution will be in perpetual maladaptive disequilibrium. The population will always have nearby adaptive mutants available. [19/n]
Prikaži ovu nit -
This transforms transient results like
@s_hammarlund,@evokerr et al.'s Hankshaw effect for cooperation (https://onlinelibrary.wiley.com/doi/abs/10.1111/evo.12928 …) into perpetual results: Hankshaw can maintain cooperation for-effectively-ever on hard landscapes without using just-in-time env. change. [20/n]Prikaži ovu nit -
Similarly w/ Baldwin effect & costly learning. By being away from local fitness peak, learning can remain adaptive even if it carries small start-up fitness cost. So if we're looking for hard landscapes among animals, ones with cooperation & learning are good candidates [21/n].
Prikaži ovu nit -
But why should we care about local peaks? Maybe we just want approximate local peaks. After all, biology is probably too messy for exact peaks anyways.
#cstheory can help us here, too. Through the study of approximation algorithms. [22/n]Prikaži ovu nit -
Evolution can find approximate peaks for moderate approx. factors (time polynomial in 1/s) but not for small factors (impossible for time poly. in ln(1/s)). This lets us reason about the decay in the selection coefficient over evolutionary trajectories & fitness traces. [23/n]pic.twitter.com/2UfWLiw8jn
Prikaži ovu nit -
I show: on hard landscapes, selection coefficients decay as power law, but can’t decay as fast as exponential. Qualitatively matches slow decay in selection coeff. & unbounded fitness growth observed by
@MikeWiser2, Ribeck &@RELenski in the LTEE [24/n]:http://science.sciencemag.org/content/342/6164/1364 …Prikaži ovu nit -
Is there a single simple conclusion from all of this? Probably not. But I would like to leave with one final message. We should not imagine hard fitness landscapes as mountain ranges. Instead, we should imagine them as winding mazes: http://www.genetics.org/content/early/2019/03/04/genetics.119.302000 … [25/25]pic.twitter.com/1gzK6S60IG
Prikaži ovu nit -
If you prefer audio/visual recaps: my presentation of the preliminary version of this work (focused on the CS) at the
@SimonsInstitute in 2014 is available online under the old title of "Complexity of Evolutionary Equilibria in Static Fitness Landscapes":https://www.youtube.com/watch?v=nDNsgDzJOiM …Prikaži ovu nit -
Last week, I gave a broader context for thought on local maxima in fields beyond evo. bio: https://egtheory.wordpress.com/2019/03/29/fallacy-of-fixed-points/ … I tried to find some 'historic' roots in recent debates in economic literature. Or as
@PabloRedux has eloquently summarized the Q: an inefficient-market hypothesis?Prikaži ovu nit -
My post on local maxima and the fallacy of jumping to fixed-points has been pretty well received on /r/philosophy. This is surprising: https://www.reddit.com/r/philosophy/comments/bbyy9i/local_maxima_and_the_fallacy_of_jumping_to/ … There is some interesting discussion in the thread. Some adds important points & some identifies common misreadings. Fun
Prikaži ovu nit -
After a day at the top of /r/philosophy, the post & associated attention has now fallen off. Some enjoyable discussion was had along the way. It seems many view cstheory results about some field X of natural science as part of the 'complexity science' challenge to X. I don't.
Prikaži ovu nit - Još 5 drugih odgovora
Novi razgovor -
Čini se da učitavanje traje već neko vrijeme.
Twitter je možda preopterećen ili ima kratkotrajnih poteškoća u radu. Pokušajte ponovno ili potražite dodatne informacije u odjeljku Status Twittera.