Optimisation and Evolution (was Quantum Theory and Control Theory)

[Martin_Taylor2]

[Martin Taylor 2005.03.30.21.37]

[From Bill Powers (2005.03.30.1837 MST)]

Rick Marken (2005.03.30.1700)--

What I don't completely accept is the
Darwinian model of those facts. I prefer an important variant of the
Darwinian model that is based on (what else?) control theory; what we call
the E. coli approach, where mutation rate in a Mendelian population is
proportional to the ambient level of error (deviation of intrinsic variables
from their genetically specified references) in the population.

I agree, of course. What I suspect is that with a truly Darwinian model (random mutations, elimination of unfavorable ones by death) the convergence to specialized forms would be far too slow. Comparing the e. coli method with the random method of selection (in simulation) shows a really huge advantage for the e. coli method -- orders of magnitude faster convergence.

In this context, you may be interested in my recent attempts at optimizing control models to fit the experimental data from the "sleepy teams" tracking studies. I've mentioned the problem here before, and not got much help, so I've been continuing on my own. What follows should not be used as a reason to tell me again that I don't do the right experiments. It's a discussion of fitting models to data using e-coli and Genetic Algorithms.

For a long time I've been trying to fit different five-parameter control models to the tracking data, using variants on the standard e-coli method of optimization in the 5-D space. The results have never been very satisfactory, and I assumed that the reason was that there was substantial correlations among the effects of parameter variation in the different dimensions (there is, but it turns out that wasn't the main problem).

I had all along been assuming that the fitness landscape of the parameter space was reasonably smooth, and would approximate a 5-D ellipsoid near the true optimum. The e-coli method ought to work pretty well in such a fitness space, but there are variants that should do the same job faster (as I discussed in the earlier thread on fitting models to data). After that thread ended, I tried actually fitting a parabola to the fitness along the e-coli trajectory -- the straight path followed in one e-coli move. This was intended to be a quicker way to find the optimum than the way I had been using.

As part of the parabola-fitting debugging, I graphed the fitness at all points tested. That's when I discovered that the fitness landscape is actually very rough, not at all the smooth surface that I had assumed would be true, at least near the optimum.

OK, now here comes the relevance to the Subject line topic.

The next thing I tried was to abandon the e-coli approach entirely, in favour of a Genetic Algorithm approach. Instead of the 5 parameters of the model, I used 5 genes (in one chromosome), each of which potentially might influence all the parameters (the reason being the correlations among the effects of the parameters on the fitness). I used a 5 x 5 set of genes (5 chromosomes) that defined a rotation matrix to determine how each basic gene influenced each parameter. The main diagonal was all unity values (to link each gene primarily with one particular parameter), and there was no attempt to normalize or orthogonalize the matrix. There's an exponential nonlinearity and a set of 5 scaling genes (1 chromosome), to finish the genome. The search space has therefore 30 dimensions, values in which plug into an algorithm that generates the 5 parameter values of the model (creating a phenotype), and a run of the model phenotype generates one fitness value.

You might think this a rather baroque construction, but I think each component has a defensible rationale. (Don't argue

Now the Genetic Algorithm, which is pure natural selection.

I create an initial population of 100 random genotypes (random in that every variable gene has a real number value randomly selected between zero and unity). I evaluate the fitness of these and for those phenotypes that simply go into oscillation (i.e. have a lethal genotype), I generate a new random genotype until I have 100 that actually do track. That's the first generation.

The next generation is created by 200 one-child "matings" within the initial population, creating a population of 300. The fitter a phenotype, the more probably likely it is to be chosen as a mating partner in each of the 200 matings. I also create 20 new random genotypes. From the 320 genotypes, I select the fittest 100. That's the next generation.

Mating consists of splitting each chromosome into two sets, the basic chromosome and the rotation chromosomes being split identically. The child's genes are a proportion that ranges from (-0.5, 1.5) to (1.5, -0.5) mix of the gene values from the parents, the proportions being chosen randomly for the two parts of the split (i.e. one set of genes might have 0.4*gene from father + 0.6* gene from mother, while the other set might have -0.1*gene from father + 1.1*gene from mother).

I also include a small mutation probability that applies to the child's genes. With a probability 0.1, a gene might have added to it a noise value chosen from a normal distribution with a standard deviation of 0.05.

I run the algorithm for only 15 generations, far fewer than are used in most Genetic Algorithm studies.

The result of this procedure is that the optimized set of parameters for each of the 42 tracks is not only fitter, but is usually MUCH fitter than the best optimum I ever got from any of my e-coli optimization attempts.

Given these results (which are, I grant, far from a real ecology), I have my doubts about the claim that: "a truly Darwinian model (random mutations, elimination of unfavorable ones by death) the convergence to specialized forms would be far too slow. Comparing the e. coli method with the random method of selection (in simulation) shows a really huge advantage for the e. coli method -- orders of magnitude faster convergence."

My results are directly contrary. Even without mutation, I still get much better optima with my 30-gene Genetic Algorithm than with any 5-D e-coli-based method I tried over many months.

The problem, I think, is that the fitness landscape for the tracking experiments is quite rough. In such a landscape, e-coli doesn't work very well. It is easily caught in local minima. In a real ecology, the fitness landscape is likely to be even rougher. Not only that, but a real fitness landscape changes as species interact and evolve.

Interestingly, looking at the tracking curves in my study, I sometimes see what I would call "species". Two very different-looking model tracks can have very similar fitness values when compared with what a human subject actually did, and the population can show what looks like punctate evolution, when one "species" emerges and quickly dominates a previously dominant species in the population.

But I haven't tried to examine these kinds of issue. I've been more concerned with the temporal changes in the optimal model parameters over the course of the subjects' sleep loss. When I am satisfied that I have as good a GA method as I can develop, I'll start running the data for all the subjects, and look at the results.

Martin

[Bill_Powers1]

[From Bill Powers (2005.03.31.0026 MST)]

Martin Taylor 2005.03.30.21.37 --

In this context, you may be interested in my recent attempts at optimizing control models to fit the experimental data from the "sleepy teams" tracking studies.

You intrigue me. The roughness of the landscape is especially interesting, because in my program for fitting a model to data it doesn't look very rough. Perhaps this depends on the measure of fitness being used -- my error criterion is simply the RMS error between model output and real output (hand position). The algorithm looks for a minimum rather than a maximum.

I have started trying an exhaustive grid search to look for true minima, but without improving my results yet. I will see what happens from making the initial grid much finer -- with four parameters, dividing each parameter range into 10 parts would produce 10,000 runs, which isn't too much. Even 100,000, wouldn't be too much with a fast computer, so the initial search can have fairly high resolution.

In Vensim (advanced version) there is a facility for doing a "Powell optimization," which as far as I can find out starts with a grid search and then does a systematic refinement of some sort. With my previous approach, which simply optimizes each parameter in turn, once, using a binary search, I get almost identical numbers.

I haven't yet used an E. coli optimization, but you have given me a motive to try. I can see that if the landscape is too rough, local minima could be a problem, but that would depend in part on the gain in the E. coli loop -- how fast the point moves in parameter space. If the movement is fast enough at large errors, fairly major valleys could be escaped from, but as the error gets smaller the movements get smaller, too, so a really deep and narrow pit could be missed.

What I really want to do is investigate for the presence of deep narrow pits. This can only be done with the exhaustive grid search, and with limits to patience can only be carried so far. Considering that the RMS errors my current approach can produce range from 5% downward, any remaining pits can't be very deep, but there could still be very narrow ones that my approach might miss. It would be most interesting if there were parameter values that could yield far smaller final errors! I don't think there are -- looking at the traces of the errors, I don't see anything that seems at all systematic.

"Fitness" is a tricky kind of measure, since like "utility" it's a positive number and you're looking for a maximum. There is no natural maximum but infinity, if that can be called a maximum, so it's hard to know how close you are coming to the best possible result. When you use an error measure (reciprocally related to utility) the natural minimum is zero, so there's a way to judge how close to perfection you are. What looks like a very rough landscape in terms of fitness might be quite smooth in terms of error.

What sorts of final matches between real and model hand positions do you achieve with the GA, in terms of RMS error? I know that the conditions for tracking in your experiments are not as friendly as in mine, so I wouldn't compare results directly, but it would be interesting to know how good a fit can be reached.

I've mentioned the problem here before, and not got much help, so I've been continuing on my own. What follows should not be used as a reason to tell me again that I don't do the right experiments. It's a discussion of fitting models to data using e-coli and Genetic Algorithms.

Yes, I understand that.

For a long time I've been trying to fit different five-parameter control models to the tracking data, using variants on the standard e-coli method of optimization in the 5-D space. The results have never been very satisfactory, and I assumed that the reason was that there was substantial correlations among the effects of parameter variation in the different dimensions (there is, but it turns out that wasn't the main problem).

I had all along been assuming that the fitness landscape of the parameter space was reasonably smooth, and would approximate a 5-D ellipsoid near the true optimum. The e-coli method ought to work pretty well in such a fitness space, but there are variants that should do the same job faster (as I discussed in the earlier thread on fitting models to data).

Yes, the E. coli method is a method of last resort when there is no systematic method known. Systematic gradient descents will always be faster, but of course they require a lot of knowledge about the situation that the E. coli method doesn't need. And they need a relatively smooth -- at least monotonic -- landscape.

After that thread ended, I tried actually fitting a parabola to the fitness along the e-coli trajectory -- the straight path followed in one e-coli move. This was intended to be a quicker way to find the optimum than the way I had been using.

As part of the parabola-fitting debugging, I graphed the fitness at all points tested. That's when I discovered that the fitness landscape is actually very rough, not at all the smooth surface that I had assumed would be true, at least near the optimum.

This may be due in part to poorness of control. A basic assumption of the model is that the control parameters are the same throughout the run. If they aren't -- if, for example, the subject falls asleep for a few seconds and is no longer seeing the target or cursor -- the parameters will be greatly different during that part of the run. The fitting procedure then has to find parameters which best represent the average values over the whole run, with pretty large excursions away from average actually existing. That introduces a lot of error into the determination, especially if tracking is reasonably good over much of the run, but extremely bad during parts of it. In my kinds of experiments, even a single sneeze during the run can double the one-minute RMS error of fit.

OK, now here comes the relevance to the Subject line topic.

The next thing I tried was to abandon the e-coli approach entirely, in favour of a Genetic Algorithm approach.

Would you mind showing me the E. coli approach that you used? I have found that there are different ways of doing it that vary greatly in their effectiveness. I'm sure you did it right -- changing the direction of movement in parameter space on each "tumble" and moving at a speed proportional to the net error -- but I'd like to check your approach against mine.

Instead of the 5 parameters of the model, I used 5 genes (in one chromosome), each of which potentially might influence all the parameters (the reason being the correlations among the effects of the parameters on the fitness). I used a 5 x 5 set of genes (5 chromosomes) that defined a rotation matrix to determine how each basic gene influenced each parameter. The main diagonal was all unity values (to link each gene primarily with one particular parameter), and there was no attempt to normalize or orthogonalize the matrix. There's an exponential nonlinearity and a set of 5 scaling genes (1 chromosome), to finish the genome. The search space has therefore 30 dimensions, values in which plug into an algorithm that generates the 5 parameter values of the model (creating a phenotype), and a run of the model phenotype generates one fitness value.

What fitness criterion do you use? Am I right in assuming you're doing a maximization of a positive measure rather than a minimization of error? Or are you really computing error, and saying that fitness is 1/error?

The main interesting thing is the combining of genes, which of course doesn't happen in the E. coli method. However, all that can result from either method is a set of values of the parameters, so I'm not sure there's any payoff in too complex a method. Nature, however, may know better. I'd like to see just what the difference is. It's possible that E. coli's method of locomotion is a throwback to an earlier stage of development. What would the counterpart of the GA be, if a bacterium had stumbled across it?

You might think this a rather baroque construction, but I think each component has a defensible rationale. (Don't argue

How could I argue that something is indefensible if I can clearly see it being defended?

Now the Genetic Algorithm, which is pure natural selection.

I create an initial population of 100 random genotypes (random in that every variable gene has a real number value randomly selected between zero and unity). I evaluate the fitness of these and for those phenotypes that simply go into oscillation (i.e. have a lethal genotype), I generate a new random genotype until I have 100 that actually do track. That's the first generation.

Are you distinguishing between real and computational oscillations? The computational oscillations arise from not using a small enough dt in the simulation, and can't be considered true behavior of the model if the underlying model is continuous. The best way to tell is to cut dt in half and see if the parameter values where oscillations take place change. If they do, then the oscillations aren't real. When dt is small enough, you can reduce it without any change in the behavior of the model (even if the model oscillates, it will oscillate in the same way with different dt's). Hmm: "dt's" seems to be an example of the one exception to the rule that you don't use apostrophes to indicate plurals. "dts" can be mistaken for a symbol dee-tee-ess, and "dtes" is out of the question, so something has to be done, and the apostophe does it).

The next generation is created by 200 one-child "matings" within the initial population, creating a population of 300. The fitter a phenotype, the more probably likely it is to be chosen as a mating partner in each of the 200 matings. I also create 20 new random genotypes. From the 320 genotypes, I select the fittest 100. That's the next generation.

Mating consists of splitting each chromosome into two sets, the basic chromosome and the rotation chromosomes being split identically. The child's genes are a proportion that ranges from (-0.5, 1.5) to (1.5, -0.5) mix of the gene values from the parents, the proportions being chosen randomly for the two parts of the split (i.e. one set of genes might have 0.4*gene from father + 0.6* gene from mother, while the other set might have -0.1*gene from father + 1.1*gene from mother).

I also include a small mutation probability that applies to the child's genes. With a probability 0.1, a gene might have added to it a noise value chosen from a normal distribution with a standard deviation of 0.05.

I run the algorithm for only 15 generations, far fewer than are used in most Genetic Algorithm studies.

If the population increases by 50% in each generation, you end up with 87000 individuals, which is the equivalent of 87000 tumbles of the E. coli method. And only one gets to the optimum, unless I misunderstand completely (possible).

Notice that you do have a measure of the "distance" between the current state of fitness and some perfect state, or at least a measure of progress toward a better state. This is what I refer to as "external guidance" in the genetic algorithm, for something knows which direction of change is preferred, and in this case that something is the programmer. In the example of the cockroach I saw, the basis for allowing a generation to survive was that the parents got a little closer to the food, or less far away from it. In nature, of course, those parents would not have survived: you have to get all the way to the food to eat it. If that had been the criterion, it would have been a pretty small population of cockroaches in the end, most likely zero after the first generation.

I wonder whether this method really does anything that can't be done with the simpler E. coli approach. Maybe it does. If the final RMS error between model and real behavior is smaller for the GA, there can be no argument with that. I still think we need to try the exhaustive grid search to get the final word on this. What is the actual best achievable fit of model to data? If we knew that, we'd know where we stand, particularly with respect to how much we could gain from continued effort to improve the more efficient method.

The result of this procedure is that the optimized set of parameters for each of the 42 tracks is not only fitter, but is usually MUCH fitter than the best optimum I ever got from any of my e-coli optimization attempts.

Very interesting. I'm willing to be convinced. If I can verify that the E. coli method was applied in the best way possible, and that there is no solution that is far better than either of the approaches can generate, I'll give in.

Given these results (which are, I grant, far from a real ecology), I have my doubts about the claim that: "a truly Darwinian model (random mutations, elimination of unfavorable ones by death) the convergence to specialized forms would be far too slow. Comparing the e. coli method with the random method of selection (in simulation) shows a really huge advantage for the e. coli method -- orders of magnitude faster convergence."

Well, you can't doubt the last sentence because it just reports a fact. The question is whether the GA is better than the E. coli approach when applied in a way that doesn't require external guidance. By that, I mean a way that doesn't rely on somebody knowing whether a given change is in the direction of survival rather than being judged on actual achievement of survival. Your method has a gradient of fitness and a way of determining which is the right way to move along that gradient. So at best it represents a population far greater than the 87000 individuals you end up with, and even fewer successes.

Maybe what I'm saying would be clearer if you applied the GA to the E. coli locomotion case. Then at least we'd be talking about the same thing. I don't see offhand how it would be done, but I'm not familiar with the details of the GA. Perhaps you can see. I know that just eliminating bacteria that don't reach the goal after each random change is monumentally inefficient. Does the GA (without external guidance) introduce some consideration that makes it more efficient?

Best,

Bill P.

[Martin_Taylor2]

[Martin Taylor 2005.03.31.10.19]

[From Bill Powers (2005.03.31.0026 MST)]

Martin Taylor 2005.03.30.21.37 --

In this context, you may be interested in my recent attempts at optimizing control models to fit the experimental data from the "sleepy teams" tracking studies.

You intrigue me. The roughness of the landscape is especially interesting, because in my program for fitting a model to data it doesn't look very rough. Perhaps this depends on the measure of fitness being used -- my error criterion is simply the RMS error between model output and real output (hand position). The algorithm looks for a minimum rather than a maximum.

I'm not going to try to answer you point by point, but I hope my response will cover most of what you ask.

Rougness of the fitness surface.

I think the main difficulty is one you mentioned (not quoted) -- that the tracking is not itself smooth in the way that tracking a moving cursor usually is. The task itself was more "cognitive", which was one point of doing the experiment. The model includes a threshold nonlinearity (no power-law at the moment) as one of the parameters, and changes in that parameter may possibly lead to abrupt changes in the qualitative character of the tracking. I have observed at least three qualitatively different kinds of track (apart from the lethal oscillations, which usually are much too slow to be computational).

One "species" of track is a smooth following track, possibly with squared-off peaks to the quasi-sine-waves. A second form consists of a mix of smooth following and step functions with exponential rise and fall. The third contains higher-frequency oscillations (which do occur at much the same frequency in some parts of some human tracks) around an otherwise smooth following track. Any one of these might wind up being the best in any particular run of the algorithm on one track.

The fitness measure

This deserves a thread of its own, and it is a thread I've tried to get going once or twice.

Before describing the fitness measure I actually use, I have to ask what you would mean by one model being better than another. Let's take two hypothetical cases. In both cases the target is a sine wave, which the subject tracks with a slight delay on which is superimposed an oscillation at a frequency 10 times that of the target sine wave.

Case X: The model tracks as the subject does, but smoothly, without the superimposed high-frequency oscillation.

Case Y: The model tracks as the subject does, with a high-frequency oscillation of the same period, but at the wrong phase.

Case X has the smallest RMS error, but case Y looks as though the model has a better qualitative representation of what the subject does, though it may lack something that fixes the oscillatory phase. We don't know whether the phase of the subject's oscillation is locked to that of the target sine wave, because the next time the subject did the same task, there was no such oscillation (maybe he had a cup of coffee one time but not the other).

I would argue that the model fit better in case Y, despite the larger RMS error. It's with that kind of example in mind that I developed a rather baroque fitness measure. (Though, as it stands, my measure wouldn't do any better than the RMS measure for the example cases).

Backtracking to 1994...in the earlier studies, I generated an algorithm for determining that some data should be eliminated from the analysis on the grounds that he subject clearly was not tracking normally (such as when the cursor didn't move for an extended period). This time, I didn't want that arbitrariness, so I tried to deweight rather than to eliminate data that was really suspect. I won't waste the time of the lurkers with a full description, but the main factors I included in the fitness measure were: (1) similarity of the model data to the human data (essentially like RMS, deweighted for large value-d samples), and (2) ratio between the closeness of the model to the human over closeness of the mode to the target (a model isn't much good if all it does is track the target, but with its errors uncorrelated with the errors the human makes). The fitness measure would be zero if the model tracked the human exactly.

e-coli methods

Over time, I've tried various methods. The best was rather like this. It's by no means "pure" e-coli. "Pure" e-coli was what I started with, and I tried a lot of variants, some of them discussed here.

To start, I take a set of parameter values known not to generate exponentially increasing oscillations. From there, I draw a straight line in the 5-D parameter space, and use succcessive halvings to zero in on the point on that line that has the best fitness value. I store that set of parameters and the corresponding fitness as "the Best yet".

Next, from that point, I jump in a random direction in the space by an amount that declines exponentially during the course of the run, choose another random direction, and find the best fitness value along that new line. The "jump" is analogous to the technique of simulated annealing used in neural networks to avoid getting trapped in local minima.

If the optimum on the new line is better than that of the old one, I save its values as "Best yet". Otherwise I leave the old set of values there.

We now have an issue with where to start the next line. What I do is to take a point between the old "Best yet" and the optimum found on the most recent test line, and make the simulated annealing jump from that point to choose a place from which to try the new line.

After N iterations (I eventually wound up using N = 120) the "Best yet" is reported as the optimum.

Genetic Algorithm population

You misread in some way my description of the algorithm when you said:

If the population increases by 50% in each generation, you end up with 87000 individuals, which is the equivalent of 87000 tumbles of the E. coli method. And only one gets to the optimum, unless I misunderstand completely (possible).

The population doesn't increase. It's always trimmed to 100 individuals, though in each generation 320 individuals are tested. 220 of those individuals die, and although I haven't done the actual test, it looks as though a good proportion of the survivors are left over from the previous generation, becasue they were the best of their year. This seems to be more true the later the generation, which suggests that there may yet be improvements to be found in the algorithm.

So the number of points tested is at most 15*320, but in reality is quite a bit less becasue of the long-time survivors with good fitness.

I don't know how to compare this with the e-coli measure tests, because many points are tested along each line. I should think they are pretty comparable. At least there's not an order of magnitude difference, to judge from the comparable running times of the methods. (GA is longer, but it has more to do between generations).

What I really want to do is investigate for the presence of deep narrow pits. This can only be done with the exhaustive grid search, and with limits to patience can only be carried so far. Considering that the RMS errors my current approach can produce range from 5% downward, any remaining pits can't be very deep, but there could still be very narrow ones that my approach might miss. It would be most interesting if there were parameter values that could yield far smaller final errors! I don't think there are -- looking at the traces of the errors, I don't see anything that seems at all systematic.

I have found suggestion of at least one deep narrow pit. For one track that I use extensively in testing, I must have many hundred "optima". I did one little graph of about 40 consecutive optimum fitness values. Most were pretty close to the same. About half a dozen had values that ranged down to a substantially better optimum. If you graph them as an ordered set, it looks like this:
           > **********************
           > ******
  fitness | ***
           > **
           > *
           >
           >*
           .

···

_____________________________________

And in a trial not included in this set, one of the several hundred optima had a value that would be a couple of lines lower on the graph. I know what the model track looks like for that parameter set. It includes a small high-frequency oscillation that phase matches some jiggles in the real human track.

"Naturalness" of selection

I'm using the same kind of "natural" selection that farmers and herders have used from time immemorial to domesticate plants and animals and enhance their fitness for human companionship and food. It's not directed, and I don't have any knowledge of a gradient in the fitness landscape. I just know that individual A, is fitter than individual B, but I don't know whether a crevasse or a mountain lies between them in gene space.

Enough.

I have to get to work. A whole hour is more time than I thought I would spend on this message.

If you have more questions, I'll try to deal with them later, but I hope this covers most of your issues.

Martin

[Bill_Powers1]

[From Bill Powers (2005.03.31.0959 MST)]

Martin Taylor 2005.03.31.10.19 --

I think perhaps the dividing consideration between your approach and mine is not so much the goodness of fit but the goodness of control. A well-practiced subject controlling something very skillfully will show behavior that can be matched by a model with constant parameters over long periods of time, minutes and maybe hours depending on the level of physical difficulty. But a tired or drugged or bored subject doing something difficult and not doing it very well may not be operating with constant parameters, so modeling the system becomes much more complicated, as reflected in your strategies. I can see that your approach is appropriate for the situation and for the kinds of results you see in the experiments.

I may go back to the exhaustive-search project, though with one thing and another (CSGnet being one) I have a lot of distractions. It seems to me that that will give us some sort of baseline. When I work out a reasonable algorithm I'll pass it on to you.

Best,

Bill P.

[Philip_J_Runkel]

This is Phil Runkel saying thanks to Martin Taylor (2005.03.30.21.37) for his description of his 5x5 genetic algorithm.

Thanks for telling about this. Gives me to think.