Re: Measuring Time to Convergence

Richard Marsden wrote:
I'm experimenting with a genetic algorithm at the moment to solve a problem.
For testing, I'm using problems that are small enough to allow a brute force attack. I then stop my genetic program when it gets with 5% of the calculated optimum fitness.

I am wanting to compare lots of different runs. Soon I'll be varying different parameters (mutation crossover, population size,etc).
So I need a way to collect statistics regarding the speed of convergence. For each setup, I run multiple models ("problems") and multiple runs with the same model.

First I tried the mean and standard deviation of the log of the number of required generations.
The reasoning behind the log was that I was seeing runs as low as a few hundred generations, and some over a million generations. With a strong positive skew in the distribution, the Normal distribution cannot be assumed.

Generally one can expect the distribution to be something very much like a Poisson Distribution -- which has the property that the Variance equals the Mean. So yes indeed you should expect the wide variances that you are reporting. There is a close relationship between Poisson Distributions and Binomial Distributions for large sample sizes.

I calculate the standard deviation to use in calculating an approximation of the sample mean's error (approximation because it isn't a normal distribution).

I'm not convinced the log solution represents the long runs correctly.

Therefore I tried without the log, and now I'm worried that they're over-represented! You need a lot of 100 generation runs to counteract a 1000000 generation run! (with a population of 90, I'm seeing a simple mean of about 3000 generations)


So what statistic is usually used to measure and compare generation counts?

Look up statistics related to Poisson Distributions. Because of the high variance, any Mean that you take from a series of runs is highly noisy. There are ways of getting confidence intervals, try Googling for "Poisson distribution confidence intervals".

Inman Harvey
.

Relevant Pages

  • Re: Measuring Turquoise Underwear
    ... that the distribution had to be normal. ... 6/49 game and has stats for about 52 draws. ... he claims the variance for the mean is /12n. ... The revised formula would yield ...
    (rec.gambling.lottery)
  • Re: X+Y | -w<=X-Y<=w
    ... Varhas nothing to do with your conditioning event. ... follows a triangular distribution. ... resulting variance of Z depends on the conditioning event. ... formula / approximation for this? ...
    (sci.stat.math)
  • Re: feedback...
    ... >>>Hi Duncan, ... >>mean (from N sample draws) to fall with 95% confidence. ... The variance of the mean, after N draws, for a given position is ... the variance of the distribution from which a draw is made. ...
    (rec.gambling.lottery)
  • Re: Mean and Variance
    ... each variable x has a normal distribution around a mean value. ... How can I calculate the MEAN and VARIANCE of the polynomial? ... order Taylor series) approximation for your ... Other ways to do this are to use Taguchi ...
    (comp.soft-sys.matlab)
  • Re: Questions about a distribution
    ... Let's say the PDF has the mean = 250 ... The variance tells how ... units as the reaction time measurements, so I would have said that the SD ... lets you know how "wide" the distribution is. ...
    (sci.stat.math)