{"id":718,"date":"2008-12-19T11:49:44","date_gmt":"2008-12-19T11:49:44","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2008\/12\/19\/fitness-landscapes-evolution-and-smuggling-information\/"},"modified":"2008-12-19T11:49:44","modified_gmt":"2008-12-19T11:49:44","slug":"fitness-landscapes-evolution-and-smuggling-information","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2008\/12\/19\/fitness-landscapes-evolution-and-smuggling-information\/","title":{"rendered":"Fitness Landscapes, Evolution, and Smuggling Information"},"content":{"rendered":"

Since my post a couple of weeks ago about NASA and the antenna evolution experiment,
\nI’ve been meaning to write a followup. In both comments and private emails, I’ve gotten
\na number of interesting questions about the idea of fitness landscapes, and some of the things
\nI mentioned in brief throwaway comments. I’m finally finding the time to write about
\nit now.<\/p>\n

<\/p>\n

Fitness Landscapes<\/h3>\n

First, let me review what a fitness landscape is.<\/p>\n

Suppose you’re searching for something. There are N parameters that define the thing you’re searching for. Then we can say that you’re doing a search for a target within N dimensions<\/em>. The N-dimensional space containing all of the possible values for all of the dimensions is called the search space<\/em>.<\/p>\n

You can model that search as an iterative function, F, which takes
\nas parameters a tuple of N values defining a current position in the search space,
\nand returns a new position in the search space.<\/p>\n

So you start at some arbitrary position in your search space, and that’s
\nthe first argument to F. Then each time you call F, it returns a new position in
\nthe search space, which is hopefully closer to the target of the search.<\/p>\n

How do you evaluate the quality of a position in the search space?<\/p>\n

You define an evaluation function, E. E takes a position in the search space,
\nand returns a real number which describes the quality of the position in terms
\nof the particular search. The higher the value returned by E for a point, the
\nbetter the quality of the target described by the position in the search space. Expressed using the evaluation, the goal is to find the position p within the space that
\nmaximizes E(p).<\/p>\n

Now, suppose you want a way of visualizing the search. It’s easy: define
\na new space with N+1 dimensions, where the N+1th has the value of
\ncalling E on the first N dimensions. Call this new, N+1th dimension “height”. Now,
\nthe surface produced by doing this is the evaluation landscape. If your search is
\nan evolutionary process, the evaluation landscape is called a fitness landscape<\/em><\/p>\n

As usual, an example makes this easier. Suppose that you’re searching
\nin two dimensions. Then your position at any time is just a position in
\na two-dimensional cartesian graph. To visualize the search space, you create
\na three dimensional graph, where the quality of the search result at (x,y) is
\nthe value of the Z coordinate. <\/p>\n

For example, imagine that the fitness function is something nice and simple, with
\na single obvious maximum: E(x,y) = sin(x) + cos(y). The maximum will naturally be 2, and
\none of the places where it will occur is at (π\/2,0). Then your fitness landscape ends up looking like the graph below.<\/p>\n

\"periodic-landscape.gif\"<\/p>\n

We can also get some much wilder landscapes, like the one below, which is defined by E(x,y)=sin(xy)cos(xy) + (3-xy)\/((xy)2<\/sup> + 1). It’s still structured,
\nbut it’s a lot more complicated.<\/p>\n

\"complex-landscape.gif\"<\/p>\n

And we can get totally unstructured landscapes, where each point is complely random, like this one:<\/p>\n

\"random-landscape.gif\"<\/p>\n

Static Versus Dynamic Landscapes and Adding Dimensions<\/h3>\n

I’ve frequently criticized creationists for talking about a static<\/em> fitness landscape. In a throwaway comment, I mentioned that you can<\/em> use a static landscape by adding dimensions. This comment really confused a lot of people.<\/p>\n

Suppose you’ve got a search of a two-dimensional space. Now, we’re going to make it more
\ncomplex. Instead of the search function always being the same, we’re going to actually have each
\ninvocation of the search function return both a point in the search space, and<\/em> a new
\nfitness function. So we start with an initial search function, f0<\/sub> and some initial
\npoint (x0<\/sub>, y0<\/sub>) in the search space. The first search step evaluates
\nf0<\/sub>(x0<\/sub>, y0<\/sub>), getting (x1<\/sub>,y1<\/sub>) and
\nf1<\/sub>. The second search step evaluates f1<\/sub>(x1<\/sub>, y1<\/sub>),
\ngetting (x2<\/sub>,y2<\/sub>) and f2<\/sub>. So the search function is
\nchanging<\/em> over time.<\/p>\n

Assuming we’re in the world of computable functions, every possible value for
\nfi<\/sub> can be represented by an integer, Fi<\/sub>. So we can re-model this as three-dimensional search, where instead of evaluating fi<\/sub>(xi<\/sub>, yi<\/sub>) getting fi+1<\/sub> and (xi+1<\/sub>, yi+1<\/sub>), we’ll evaluate
\na new three-dimensional search function f'(xi<\/sub>, yi<\/sub>, Fi<\/sub>)
\ngetting back (xi+1<\/sub>, yi+1<\/sub>, Fi+1<\/sub>). So we’ve taken the
\nway that the search function itself can change, and incorporated it into the
\nsearch space, at the cost of making the search space itself more complex.<\/p>\n

For any way that a search space or search process changes over time, we can
\nincorporate that change into the search space by adding dimensions. This can give us
\na fixed fitness landscape – but it does so at the cost of adding lots of dimensions.<\/p>\n

So now we’ve got a measure of the quality of the search result at any particular step. How
\ncan we define the performance<\/em> of a search over time? There are several ways of doing it; the easiest to understand is as the limit of a function P, such that at time T, P(T) = (σi=0,T<\/sub>E(xt<\/sub>, pt<\/sub>))\/T; that is, the mean of
\nthe evaluation result at each step, divided by the number of steps. So take P(T), and
\ncompute its limit as T approaches infinity – that’s one reasonable way of describing the
\nperformance of a search. What it’s really doing is computing the
\naverage fitness result of the search. There are others measures that also take
\nthe rate of convergence on a solution into account, but for simplicity, the simple measure is
\nadequate.<\/p>\n

No Free Lunch<\/h3>\n

Now, to move on to a bit of NFL-related stuff.<\/p>\n

The main fitness-landscape argument used by creationists against evolution is based
\non Dembski’s No Free Lunch work. NFL is a family of theorems which (stated informally) says:
\naveraged over all possible fitness landscapes, no search algorithm can possibly do
\nbetter than a random walk.<\/p>\n

Given a search function and a landscape, you can compute a performance measure. Given a set of multiple landscapes, you can compute the performance of your search function on each landscape separately. Then you can describe the average performance of your search on your set of landscapes. If the set of landscapes is enumerable, then you can (theoretically) compute the average performance of your search function over all possible landscapes. (Even if the the set of landscapes isn’t enumerable, you can still talk theoretically about the average performance over all landscapes; you just can’t compute it.)<\/p>\n

So – given any reasonable performance metric, no search algorithm can possible do better than random guessing over the set of all possible fitness landscapes.<\/p>\n

There are places where this theorem is actually interesting. But they’re not the places
\nthat creationists like Dembski continually invoke it. (The main interesting application
\nif it is in game theory, where you can show things like “There’s no universal
\ngame winning algorithm.”) In something like evolution, it’s silly for one simple reason: the “all possible landscapes” clause.<\/p>\n

Evolution doen’t work over all possible landscapes, and no sane person would argue
\nthat it could.<\/p>\n

When we talk about fitness landscapes, we tend to think of nice, smooth, continuous
\nsurfaces, with clearly defined maxima and minima (hilltops and valley bottoms). But all
\npossible landscapes doesn’t just include smooth landscapes. It includes random ones. In
\nfact, if you work out the set of all possible landscapes, there are a lot<\/em> more
\ndiscontinuous random ones than there are structured, smooth ones.<\/p>\n

So in the NFL scenario, you need to be able to work in a nice smooth landscape, like
\nthis one:<\/p>\n

\"2d-simple-landscape.gif\"<\/p>\n

It’s easy to see how a search function could find the maximum in that one-dimensional
\nseach space – it’s got a very clean fitness landscape. On the other hand, NFL also requires
\nyou to be able to find the maximum in a totally random landscape – like the one below:<\/p>\n

\"2d-random-landscape.gif\"<\/p>\n

It should be obvious that there’s absolutely no meaningful way to search for the maximum value in that seach space. There’s nothing in the fitness landscape that can provide the slightest clue of how to identify a maximum.<\/p>\n

Evolution works in landscapes with structure. Another way of putting that is that
\nevolution works in landscapes where the result of a search step provides feedback about the
\nstructure of the landscape. But the key takeaway here is that NFL doesn’t provide any meaningful rebuttal to information, because we don’t expect evolutionary search to
\nwork in all possible landscapes!<\/p>\n

In terms of evolution, the average performance over all possible landscapes is a strange
\nidea. And it’s obvious on an intuitive level why there’s no way that a single search function
\ncan possibly perform well on all possible landscapes. On some landscapes, it will do really
\nwell. On some (the random ones, which make up the majority of all possible landscapes), it
\nwill be effectively the same as a random walk. And on others, it will perform worse than
\nrandom, because the adversarial landscape is perfectly structured to make the search strategy
\ntravel towards the worst possible places.<\/p>\n

Smuggling Information<\/h3>\n

Lately, Dembski and friends have been taking a new tack, which involves talking about
\n“smuggling information”. They’ve been using the NFL argument for years, but they’ve
\nrun into a rather serious problem: evolution works.<\/p>\n

As evolutionary algorithms have become well known, and have had some astonishing
\nsuccesses, it’s become difficult to make the argument that an evolutionary process
\ncan’t possibly succeed. So it became necessary to come up with an excuse for why
\nevolutionary algorithms work so amazingly well, even though the creationists
\nmathematical argument shows that it should be impossible.<\/p>\n

Their excuse is to basically accuse the experiments that use evolutionary
\nalgorithms of cheating. They argue that the reason that the evolutionary mechanism can
\nsucceed is because information was “smuggled” into the system – that, essentially, the
\nsearch algorithm encodes information about the landscape which allows it to succeed. They
\nargue that this is cheating – that the evolutionary process really has nothing do with the
\nsuccess of the search, because the “solution” is really encoded into the structure
\nof the problem via the smuggled information.<\/p>\n

There are two responses to this.<\/p>\n

The first one is, in a word, “Duh!”. That is, of course<\/em> there’s information
\nabout the landscape in the system. As I discussed above, there’s no such thing as a search
\nalgorithm that works on all landscapes, but for landscapes with particular properties, there
\nare search algorithms that are highly successful. If you look at it from an
\ninformation-theoretic viewpoint, any<\/em> search algorithm which can successfully operate
\nin a particular search space encodes information about the space into its structure. From
\nthe viewpoint of math, this is just totally, blindingly obvious.<\/p>\n

And it’s not a problem for biological evolution. Biological evolution is based
\non mutation, reproduction, and differential success. That is, it’s a process
\nwhere you have a population of reproducing individuals, where the children are
\nslightly different from the parents. Some of the children survive and reproduce,
\nand some don’t. This process clearly only works within a particular kind of search space;
\nthat is, a search space where the survival to reproduction of a subset of the population
\nindicates that that subset of the population has a higher fitness value. <\/p>\n

Evolution, modelled as a search, requires certain properties in its search space
\nfor it to work. The information smuggling argument basically claims that that
\nmeans that it can’t work. But every<\/em> successfull search algorithm
\nhas certain requirements for he search-space in which it operates. By the
\narguments of Demski and friends, there is no such thing as a successful search
\nthat doesn’t cheat.<\/p>\n

The second response to the argument is a bit more subtle.<\/p>\n

If you look at the evolutionary process, it’s most like the iterative search process
\ndescribed towards the beginning of this post. The “search function” isn’t really static over
\ntime; it’s constantly changing. At any point in time, you can loosely think of the search
\nfunction for a given species as exploring some set of mutations, and selecting the ones that
\nallow them to survive. After a step, you’ve got a new population, which is going to have new
\nmutations to explore. So the search function itself is changing. And how is it changing?
\nModelled mathematically, it’s changing by incorporating information about the
\nlandscape<\/em>.<\/p>\n

There’s a really fascinating area of computer science called inductive learning machine
\ntheory. It was invented by a guy named John Case, who’s a friend of mine; he was a member of
\nmy PhD in grad school. John is interested in understanding how learning works on a
\nmechanistic level. What he does is model it as an inductive process.<\/p>\n

You’ve got a target function, T. The goal of the learning machine is
\nto find a program for T. The way that it does that is by continually refining its
\nprogram. So you give it T(0), and it outputs a guess at a program for T. Then you give
\nit T(1), and it outputs a better guess (it should at least<\/em> be correct for
\nT(0) and T(1)!). Then you give it T(2), and it outputs another guess. Each step, it
\ngenerates a new program guessing how to compute T.<\/p>\n

According to Dembski, the process by which the learning machine improves its guesses is
\ncheating<\/em>.<\/p>\n

Evolution is really doing exactly the same thing as John’s inductive learning machines:
\neach step, it’s gaining information from the environment. You can say that the evolutionary
\nsearch at step N has incorporated the results<\/em> of steps 0..N-1. Information about the
\nenvironment has naturally been incorporated. In fact, if you think about it, it’s
\nobvious<\/em> that this is the case – and that this is exactly why<\/em>, on a
\nmathematical level, evolution works.<\/p>\n

Go back to the NASA experiment for a moment. The search space of possible antennas is
\nhuge – but it’s structured and continuous. How does evolution find the best antenna? It tries
\nlots of options – and based on the results of those options, it discovers something about the
\nstructure of the search space – it discovers that some set<\/em> of solutions work better
\nthan others, and it tries to search forward from those. By doing that, it’s pruned out huge
\nareas of the search space – the areas rooted at the least successful tests. Eliminating a
\nlarge part of the search space is a way of incorporating information about the search
\nspace<\/em>: it’s adding the information that “the solution isn’t over there”.<\/p>\n

Pointing out that an evolutionary process works in a particular set of landscapes, and
\nthat it’s got a way of acquiring and integrating information about the landscape that it’s
\nsearching isn’t a critique of evolution – it’s an explanation of how it works. Far from being
\na good argument against evolution, it’s an argument for<\/em> evolution, because it shows
\nthe mechanism by which evolution is capable of finding solutions.<\/p>\n","protected":false},"excerpt":{"rendered":"

Since my post a couple of weeks ago about NASA and the antenna evolution experiment, I’ve been meaning to write a followup. In both comments and private emails, I’ve gotten a number of interesting questions about the idea of fitness landscapes, and some of the things I mentioned in brief throwaway comments. I’m finally finding […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[30,31],"tags":[],"class_list":["post-718","post","type-post","status-publish","format-standard","hentry","category-information-theory","category-intelligent-design"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-bA","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/718","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=718"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/718\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=718"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=718"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=718"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}