IlliGAL Blogging

My turn :-) I thought I would contribute with something simple but very useful for running scalability experiments.

As many know, I've worked on the design of better genetic algorithms (GAs) for quite a long time. I focused and still focus on designing GAs that scale up well, that means, their computational complexity should grow as a low order polynomial of the number of problem variables or problem size (whether we use the number of evaluations to compute the complexity or we use the actual time complexity including everything). Yes, I know the No Free Lunch theorem and by no means am I trying to violate it. But, as most of us, I am not interested in solving all problems or all classes problems closed under rather general operators (like permutation), but I want to solve problems that can be expected in the real world. And I believe that the real-world problems should mostly be much simpler than some arbitrary problems with no inherent structure. Here I want to describe the bisection method for determining a reasonable population size suggested to me by Kumara years ago, which I find useful for scalability experiments.

We all know that computational complexity of GAs depends primarily on the population size and the number of generations. Given that we know the optimum, the number of generations can be determined by the GA itself---when the GA finds the optimum or the entire population converges to it (or gets close enough), we've got it. The problem is how to determine an adequate population size for each problem size. A "good" population size should be the one that ensures reliable convergence to the optimum (where "reliable may be defined any way we want, for instance, that the algorithm finds the optimum successfully in 9 out of 10 independent runs).

Right now I use a method based on bisection. The basic idea is to first determine a reasonable initial interval (min,max) of population sizes where min is too small and max is too large. Then, this interval is halved again and again until it is small enough (e.g. until (max-min)/min<0.1). In the end, our "perfect" population size should be somewhere between min and max, so when we choose max we know that we're not too far from the number we were looking for and we know that this population size works. The entire pseudocode of the bisection method follows:

1. Start with some very small N (say, N=10)

2. Double N until GA convergence is sufficiently reliable

3. (min,max)=(N/2,N)

4. repeat until (max-min)/min<0.1 (use your own threshold here)

     N=(min+max)/2

     if N leads to sufficiently reliable convergence 

        then max=N

        else min=N

5. Compute all your statistics for this problem size using 

   pop. size=max

What I like on using the bisection method is that all parameter tweaking will be done automatically (and thus I don't have to do it myself), because the remaining GA parameters do not influence time complexity as much (mostly by some constant factor and that's not so important when we talk about asymptotic upper bounds). To eliminate noise, the bisection can be run several times and the results of all bisection runs can be averaged (right now I use 10 rounds of bisection, each with 10 runs).

Of course, the above thinking is correct only if larger populations lead to better solutions (given enough generations we should all be able to believe this fact) and if smaller populations do not significantly increase the number of generations (in all cases I studied, any sufficiently large population size lead to about the same number of generations, as can be expected for many variants of evolutionary algorithms based primarily on recombination). To determine whether or not the second condition is at least partially satisfied, one can try one problem size (rather larger than smaller) and test whether the overall complexity decreases for larger populations than the one determined by the bisection. Most likely, the complexity increases with the population size and thus the bisection can run the experiments for us.

Scalability plots obtained in this manner should persuade GA sceptics who often think we don't know what computational complexity is.