7
$\begingroup$

My question deals with how to be able to assert that an "improved" evolutionary algorithm is indeed improved (at least from a statistic point of view) and not just random luck (a concern given the stochastic nature of these algorithms).

Let's assume I am dealing with a standard GA (before) and an "improved" GA (after). And I have a suite of 8 test problems.

I run both both of these algorithms repeatedly, for instance 10 times(?) through each of the 8 test problems and and record how many generations it took to come up with the solution. I would start out with the same initial random population (using same seed).

Would I use a paired t-test for means to verify that any difference (hopefully an improvement) between the averages for each test question would be statistically significant? Should I run these algorithms more than 10 times for each test/pair?

Any pitfalls I should be aware of? I assume I could use this approach for any (evolutionary) algorithm comparison.

Or am I really on the wrong track here? I am basically looking for a way to compare two implementations of an evolutionary algorithm and report on how well one might work compared to the other.

Thanks!

$\endgroup$
  • 1
    $\begingroup$ @levon9 I have reformulated the title to make it fit with current policy (sentence capitalization, etc.); please check if I didn't alter its original meaning. $\endgroup$ – chl Feb 19 '11 at 8:30
  • $\begingroup$ @chl - couldn't find a way to message directly (still learning my way around here) - could you please point me to the policy? I found the part about it not being "just" luck somewhat relevant given that these are stochastic processes and therefore non-deterministic. Thanks. $\endgroup$ – Levon Feb 20 '11 at 2:01
  • 1
    $\begingroup$ @levon9 Ok, I reverted the title back to the original one. About general policy on title and question wording, please refer to meta, Is there a style guide that provides guidelines for question title and question content?. $\endgroup$ – chl Feb 20 '11 at 9:16
  • 1
    $\begingroup$ @levon9 General idea is to make title show what the question is about, preferably using proper words. The sentence capitalization policy is just to establish some level of order (people do spit less on clean floors). $\endgroup$ – user88 Feb 20 '11 at 23:59
4
$\begingroup$

You would not use a paired sample t-test. The reason for this is that a particular random seed cannot be assumed to bias the outcome of both algorithms in the same way, even if that random seed is only used to generate the population and not for later operations such as mutation and selection. In other words, its logically possible that, under one algorithm, a given population will evolve better than the average for that algorithm, but will perform in the opposite way under another. If you have reason to believe that there is a similar connection between seed and performance for both algorithms, you can test this using a Pearson correlation coefficient to compare each seed's performance on both tests. By default, however, I would assume that there is no connection, especially if you have reasonably large populations.

As far as running more than 10 times, of course more samples are always better, though your computational resources obviously may be a limiting factor. It could be a good idea to generate a power curve, which will show you the relationship between the size of difference needed for statistical significance at you're alpha level, and the SD and n. In other words, at a given n and SD, how big does the difference have to be? http://moon.ouhsc.edu/dthompso/CDM/power/hypoth.htm <-- see bottom of page for power curve info.

Finally, if you are running a genetic algorithm that actually has a defined stopping point, as yours does, you can just do a plain unpaired t-test on the number of generations needed to find the solution. Otherwise, quantifying algorithm performance tends to get a bit trickier

As far as pitfalls, and generalizability of algorithm efficiency to other problems, you really cannot take effectiveness of your algorithm for granted when porting it to other problems. In my experience, genetic algorithms usually have to be tweaked quite a bit for each new problem that you apply them to. Having said that, depending on how diverse your set of 8 tests is, they may give you some indication of how generalizable your results are, and within which scope of applications they are generalizable.

$\endgroup$
  • $\begingroup$ Awesome comments, very helpful. No, I agree with you, I wouldn't claim a connection between a given seed and performance. I would have varied the starting seed though for each set of runs. I didn't know about the powercurve, sounds very useful, I'll check out your link and also read up on it some more. I would not generalize the performance of my algorithms beyond the set of problems used which I hope to be varied, i.e., unimodal, multimodal, etc. Re running the algorithms to "completion" should I worry about the starting seed? If so, why couldn't I just use the paired t-test in that case? $\endgroup$ – Levon Feb 26 '11 at 21:57
  • $\begingroup$ .. continued .. I.e., it took so many generations "before" and now so many "after" the changes made to the algorithm. I will have to think about the unpaired t-test approach - my stats knowledge is not very deep (or complete in breadth, so I have found this site to be quite useful). Oh, I also plan to use this approach with PSOs as well down the line. $\endgroup$ – Levon Feb 26 '11 at 21:59
  • $\begingroup$ If running seed X on the same algorithm, but for different durations, you can use the paired t-test. But running seed X on two different algorithms, you cannot. The reason is that seed X might not interact with Alg.1 in the same way that it interacts with Alg.2. Paired t-tests are for when a result from one sample is related to a result from another sample. You cannot assume that seedX(Alg.1) and seedX(Alg.2) are related. But, you can test if they are, using a correlation coefficient, which is really easy to do. $\endgroup$ – Matt Munson Feb 27 '11 at 0:40
5
$\begingroup$

I used paired t-test to compare my algorithm to GA, although I had about 200 test cases. You can use a non-parametric alternative such as the Wilcoxon Ranks Test. Regardless of what you use to test the statistical significance, bear in mind the "real-life" significance. If the performance improvement that your algorithm provides is below measurement limits, or below any practical interest, then even if it is statistically significant (i.e. "good" p-value), it doesn't matter.

$\endgroup$
  • $\begingroup$ what did you test ? Average number of generations as suggested by the OP ? Difference from (if known) optimal solution ? A combination of both ? How do you test whether one algorithm is more likely to get stuck in local optimas ? $\endgroup$ – steffen Mar 4 '11 at 12:18
  • $\begingroup$ I tested difference from known optimal solution using approximately equal number of scoring function calculations. $\endgroup$ – Boris Gorelik Mar 6 '11 at 9:06
4
$\begingroup$

It might not be what you want to hear, but from what I've seen the new algorithm is just compared to the old one on benchmark functions.

E.g. as done here: Efficient Natural Evolution Strategies, (Schaul, Sun Yi, Wierstra, Schmidhuber)

$\endgroup$
  • $\begingroup$ Thanks for the paper reference, I'll check it out. Without having read the paper though, let me restate that I too am going to use benchmark functions (the set I mentioned above) .. I just want to be able to somehow quantify that my (hopefully) better numbers are not just due to "luck" but statistically significant. I.e., I have seen people report just numbers (such as time to execute or number of evaluations), but I am not sure that's sufficient. Be curious about other comments. Thanks. $\endgroup$ – Levon Feb 20 '11 at 2:03
1
$\begingroup$

I used a t-test (non-paired, ie independent) to compare 10 runs of my genetic algorithm with 10 runs of a hill climbing algorithm. I did one t-test to see if there was a significant difference between fitness of best solutions found, and another t-test to see if there was a significant difference between completion times. I used this online calculator to do it. The cut and paste option is very handy.

$\endgroup$
0
$\begingroup$

I suspect that if the specifics of the statistical test you use matter, then the algorithms aren't much different.

Two comments:

  • the tests should be set up so that approximately the same amount of time is used by each algorithm. You might try varying the time allowed -- it is conceivable that the order changes with different time horizons.

  • the test suite should contain problems that are of the type that you care about. Whatever pair of algorithms you have, you can find problems for which one is better than the other.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.