**From:** Iain Strachan (*iain.strachan.asa@ntlworld.com*)

**Date:** Tue May 13 2003 - 18:13:51 EDT

**Previous message:**Josh Bembenek: "RE: pseudogenes and design"**In reply to:**bivalve: "Design, complexity, etc."**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

Hi, David,

I'll try and answer your point below, which is the one I feel best qualified

to answer:

*> >(Irreducibly complex, in my definition, means: "requiring several
*

coordinated changes to make any improvement")<

*>
*

*> I appreciate the definition; it is necessary for a meaningful discussion
*

of irreducible complexity. However, it does raise some further questions:

*> How do you define improvement? How coordinated must the changes be? How
*

many? What counts as separate changes?

*>
*

I must make clear that I am talking specifically here about the use of

Genetic Algorithms as optimizers of some fitness function. I realise at the

outset that in nature in general it's a matter of differential survival,

which is not the same as optimising a specific function. However, all this

is in the context of genetic algorithms being used to justify evolution in

nature, and in particular the Lenski paper on the Evolutionary Origin of

Complex Features, which does indeed optimize a specifically crafted function

(as indeed does the "WEASEL", or the Schneider Ev simulation).

Hence

I would define "improvement" in terms of increasing the value of the fitness

function ( actually minimising a cost function is mathematically the same --

in Schneider's paper, a "mistake count" is to be minimized & hence "cost

function" would be a more appropriate term). In any kind of Genetic

Algorithm, of course, a reduction in the fitness (increase in cost) can come

about (as indeed it does in the Lenski simulation), but the overall

objective is to improve the fitness. One of the "selling points" of GA's,

which attracted my colleagues and myself to study them along time ago at

work was their ability to escape from "local optima" of the fitness surface

by temporarily reducing the fitness via mutation and then homing in on a

hopefully superior optimum. They are regarded as "global optimization"

techniques. It's my opinion that this only really works for low-dimensional

problems, otherwise, if you're stuck in a local optimum in a high

dimensional space, then the probability of a random mutation or crossover

putting you in the basin of attraction of a different optimum becomes

vanishingly small, due to a well-known mathematical phenomenon known as the

"curse of dimensionality" (many hits can be found by typing this phrase

into Google).

As to what I mean by "how coordinated", I'll give an example of an

experiment I ran in the early days (note that at this time I was very keen

to exploit GA's, reasoning that evolution designed us, and so a biologically

inspired algorithm like this must be able to do pretty remarkable things.

I'd worked for some time in the biologically inspired field of Neural

Networks, & know that they are very successful & hence it seemed logical

that if we can exploit brain-architecture, that we should also be able to

exploit evolution).

We used a standard software package, now available on the web as GeNeSyS

4.5; a set of C programs that runs a GA and allows you to define your own

fitness functions. It came with a standard set of test functions regarded

as challenges for optimizers. One such function was called "Shekel's

Foxholes" (again, Google provides many hits if you want to visualize this

function). It is a hard problem for an optimizer because it has many local

minima. It is a function of two variables, x and y, and consists of a

rectangular grid of sharp spikes (hence the "foxholes"), each rising to a

different height & so one of them is the global optimum, and the others are

the local optima. Outside the "spikes" it is pretty flat. The Genetic

Algorithm performs spectacularly well on such a function, invariably finding

the global optimum. However, despite the fact I wanted to be impressed by

it, it occurred to me that with the rectangular array of "spikes", this

problem was (unintentionally) tailor-made for both the crossover and the

mutation operators. The genome is a string of 20 bits, of which the first

10 give the x coordinate and the last 10 give the y coordinate. Since the

mutation rates have to be low, then it is clear that a mutation can either

only change the x or the y value. But since the optma are arranged on a

rectangular grid, with the grid lines parallel to the x and y axes this

allows it to hop from one hole to another quite easily given a _single_

mutation. Equally, the "crossover" is very helpful; you only have to have

one member of the population in the right row and one in the right column,

and a single point crossover at the half way point will produce one that is

in the right row and column. I thought that this might be the reason the GA

worked so well. There was a simple test to perform to see if my conjecture

was true. That was to arrange the "spikes" in the function so they were

placed randomly on the surface instead of neatly in rows and columns. In

this case, to hop from one spike to another would require simultaneous

changes to the x and y values, or two coincident mutations. Equally, the

"crossover" could not be expected to work. The outcome of the experiment

was, alas, as I had expected; the GA now performed little better than a

random search.

Now, obviously that example is simplistic and unrealistic. And furthermore,

it could easily be pointed out that in nature one does not necessarily

expect to reach the global optimum; any of the local ones would do.

However, this illustration is simply to point out what I mean by coordinated

changes. The problem also arises in many more realistic and interesting

optimization problems (such as training a neural network). Many such

problems are characterized by what are described as "ridges" in the fitness

surface (or the cost function surface). In order to stay on the ridge, you

have to simultaneously change several of the parameters under optimization &

this is what you can't do with a genetic algorithm.

I wrote & you replied:

*>The problem is that any mutation is just as likely to be UN-done as it is
*

to occur, while it is waiting for all the others to occur. Imagine that you

were collecting coupon cards (like you used to get in packets of tea or

cigarettes). But suppose you had the rule that if you got a duplicate of

one you already had, that you had to destroy both of them & wait for another

one. Then it's relatively straightforward to show that the expected time

you have to wait to get the whole collection rises exponentially with the

size of the collection.<

However, in biological systems, getting a duplicate usually means you can

start a new collection. The high level of parallelism also means there are

plenty of backup copies.

My reply:

I think we're confusing terms here (Probably my fault). I was not referring

to gene duplication here; just to the possibility of a mutation getting

undone. Perhaps the card collection was a bit misleading. What you'd

normally do with a duplicate card is use it for swaps with other collectors

:-). The situation I was trying to describe was where, to get any benefit,

you have to get the whole collection, but you are just as likely to lose a

card as to get a new one (one such collection I had as a kid was cards with

vintage cars on them. If you got the whole collection, you got a toy model

car for free; no reward for five out of six cards; you needed all six to get

the toy). I used the "duplicate card cancelling out the existing one"

purely as an analogy to model the neutral mutations. The situation being

modelled is perhaps better described as you having a row of, say 20 coins,

and you want to make them all heads. To do this, you continually pick up a

coin at random and toss it, irrespective of whether it is heads or not & you

carry on till you get all 20 to be heads. Clearly the closer you get to

your target, the more likely you are to pick a head and turn it into a tail.

In this case, the length of time taken to get all heads is exponential with

the number of coins. The "mutations" are neutral in the sense that as

collection of 19 heads has no selective advantage over a collection of 1

head. Just as with the coupon cards, there is no advantage till you have

the whole lot.

Regards,

Iain.

**Next message:**Iain Strachan: "Re: Evolutionary rate"**Previous message:**Josh Bembenek: "RE: pseudogenes and design"**In reply to:**bivalve: "Design, complexity, etc."**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

*
This archive was generated by hypermail 2.1.4
: Tue May 13 2003 - 18:14:01 EDT
*