1 INTRODUCTION

Many attempts have been made in the last 10 years to answer a question that recurs in using evolutionary algorithms such as GAs to solve optimization problems: which algorithm is best suited to optimize this particular function? It is a natural corollary of the ‘No-Free-Lunch’ (NFL) theorem (Wolpert and Macready, 1997) that there will be differences among algorithms in any specific case, but finding ways of distinguishing between algorithms seems to be problematic.

Some have focused on measures of problem difficulty that we can compute by sampling the Universe of all potential solutions (Davidor, 1990; Davidor, 1991; Aizawa, 1997). These use measures that rely simply on the function itself, which is of uncertain utility if we wish to compare algorithms. The underlying factor in these approaches is the Walsh decomposition of the function, which is captured in a single value known as the ‘epistasis variance’. Reeves provides a recent survey and critique (Reeves, 1999a) of some of these ideas, and shows that there are considerable practical and interpretative problems in using such measures.

Others have tried to take account heuristically of the way that the proposed algorithm works (Jones and Forrest, 1995). More recently Stadler and Wagner have put in place a more rigorous mathematical foundation (Stadler and Wagner, 1997) whereby the ‘amplitude spectrum’ of the landscape induced by a particular operator can be estimated. Interestingly, this measure again depends in a fundamental way on the Walsh decomposition.

However, all of these methods can really only compute a proxy for the properties that make a problem instance difficult. These include the number of local optima, their depth and width, and the size of their basins of attraction. Such concepts can be defined quite straightforwardly in the case of a deterministic neighbourhood search (NS). However, the concept of a local optimum is rather harder to pin down in the case of GAs, since the landscape in any specific generation depends not merely on the operators used (as is solely the case for NS), but also on the nature of the current population, and on the particular pairs of parents selected for mating. Nevertheless, the work of (Vose, 1999) has shown that GAs commonly converge towards fixed points in the sense of stable populations of strings, and that these tend to be near the corner of the population simplex—i.e., where the population is a set of identical strings.

In this paper we shall be interested in estimating the number of these fixed points or ‘attractors’ for a given instance. An important point to realize is that while at least one of the local optima in NS is sure to be the global optimum, we cannot of course be certain that any attractor of a GA is actually the global optimum. Nevertheless, many successful practical applications of GAs are fairly convincing evidence that the set of such attractors has a high probability of including the global optima or at least other very high-quality points.

Clearly, while not the only characteristic of interest, and not the only determinant of solution quality, the number of attractors is one property of the ‘landscape’ that is likely to influence how difficult the problem is. Methods based on Walsh decomposition cannot be certain of measuring this well. As is shown by (Reeves, 2000), it is possible to generate large numbers of functions that have identical epistasis variance measures, or amplitude spectra, and yet the number of NS local optima can vary widely. To have a direct measure of the number of attractors would therefore be very useful.

In this paper we describe a methodology for computing an estimate of the number of attractors using data obtained from repeated sampling. Although we shall couch the argument in terms of attractors for an evolutionary algorithm, it also obviously applies mutatis mutandis to any search algorithm. For example, in the case of deterministic neighbourhood search, for ‘attractors’ we simply read ‘local optima’; for simulated annealing (say) we might be interested in the number of ‘high-quality’ local optima, since it would be assumed that the chance of being trapped in low-quality ones is reduced almost to zero.

Previous work in this direction has been hinted at in (Schaffer et al., 1989), and the technique used there has been reported recently by (Caruana and Mullins, 1999). Ideas similar to those which we consider in the current paper have also been presented by (Kallel and Garnier, 2000), but with a different focus.

In the next section of this paper, the probability model that we shall use is introduced. Questions of estimation, approximations and numerical methods are considered, along with some details on the statistical properties of the estimators derived. A parameter of importance is κ, the proportion of distinct attractors found in repeated sampling. Sections 3 and 4 consider specifically the cases where κ is large (close to 1), and small (below 0.5) respectively. Finally, in section 5 some applications are presented in the context of a GA solving some relatively simple optimization problems.

2 A PROBABILITY MODEL

Suppose there are v attractors, and that when using a GA from an initial random population the chance of encountering each attractor is the same. This may be interpreted as an assumption that all attractors have the same size basin of attraction—a first approximation that is probably not valid, but it is a reasonable starting point for the development of a model. We shall return to this point later.

Suppose the GA is run to convergence—i.e., an attractor is discovered. The process is then repeated many times. When there are many attractors, many repetitions may take place and very few attractors are found more than once. On the other hand, if the number of attractors is few, we will soon encounter previously discovered attractors. We can devise a probability model that describes this behaviour as follows:

Suppose that the GA is repeated r times, and that the trials are independent. The random variable K describes the number of distinct attractors that are found.

Johnson and Kotz further give the mean as

$E\left[K\right]=\nu \left\{1-{\left(1-1/\nu \right)}^r\right\}$

However, in our position, v is an unknown parameter which we wish to estimate. The well-known principle of maximum likelihood (Beaumont, 1980) provides a well-tested pathway to obtain an estimate $\widehat{\nu }$. Maximum likelihood (ML) estimators have certain useful properties, such as asymptotic consistency, that make them generally better to use than simple moment estimators, for example. The first step is to write the log-likelihood as

$l\left(\nu \right)=\mathit{log}P=log\nu !-log\left(\nu -k\right)!+logS\left(r,k\right)-rlog\nu \text{,}$

and then find its maximum by solving

$\mathrm{\Delta }l=l\left(\nu \right)-l\left(\nu -l\right)=0$

since v is a discrete quantity. This is straightforward in principle, since ∆log v! = log v, and we find that the equation reduces to

$rlog\left(\mathrm{l}-1/\nu \right)-log\left(\mathrm{l}-k/\nu \right)=0$

which can be solved by numerical methods. In fact this equation can also be derived from the relationship for the mean above. In other words, the ML estimator and the moment estimator here coincide.

3 FIRST REPETITION WAITING TIME DISTRIBUTION

As remarked above, in many cases v will be a very large number, as will be k—so it might be that every one of the attractors found is distinct unless r itself is quite large. Of course, if we find that k = r there will be no solution to Eq. 2. and all that we can say for certain is that there are at least k attractors. This outcome would be most unlikely, of course. One possibility is to keep sampling the set of all attractors until the first re-occurrence of a previously encountered attractor. Suppose this occurs on iteration T. We will call this the waiting time to the first repetition.

The mean of T is

$E\left[T\right]=\frac{2}{\nu }+{\displaystyle \sum _{t=3}^{\nu +1}\frac{t\left(t-1\right)\nu !}{\left(\nu -t+1\right)!{\nu }^t}}$

which seems to have no obvious closed-form solution. However, this and other statistics can in principle be computed for a given value of N using the obvious recurrence formulae

$P\left[T=t+1\right]=\frac{t}{t-1}\frac{\nu -t+1}{\nu }P\left[T=t\right]$

(with P[T = 2] = 1/v) to calculate the probabilities. For large values of v this may take some time, and it is quicker to evaluate the median. Figure 1 shows the results of computations of median waiting time, and associated upper and lower quartiles, for a range of values of v.

From this diagram it appears that the average waiting time is increasing as something like v^0.5. A linear regression analysis confirmed that this is a plausible model, the actual relationship estimated over the range of values in the diagram being

$t_{med}=0.673+1.25\sqrt{\nu }$

with a coefficient of determination (R²) of almost 100%.

3.1 Maximum likelihood estimation

For a single determination T = t the log-likelihood is

$l\left(\nu \right)=log\nu !+\mathit{log}\left(t-1\right)-log\left(\nu -t+1\right)!-tlog\nu$

and the first difference is

$\mathrm{\Delta }l=log\nu -log\left(\nu -t+1\right)-t\left(log\nu -log\left(\nu -1\right)\right)$

which gives an equation that is clearly a special case of Eq. 2

$log\left(1-\frac{t-1}{\nu }\right)=tlog\left(1-1/\nu \right)$

Thus the numerical methods described in section 2.3 can also be used for this case. If we carry out multiple runs of the algorithm, so that we have m determinations (t₁,…,t_m), the generalization of the above is simply

${\displaystyle \sum _{i=1}^{m}log\left(1-\frac{t_i-1}{\nu }\right)=log\left(1-1/\nu \right){\displaystyle \sum _{i=1}^m{t}_i}}\text{.}$

This can be simplified to

$l\left(\nu \right)={\displaystyle \sum _{i=1}^m\left({\displaystyle \sum _{k=\nu -t_i+2}^{{}^{\nu }}logk-t_{i}log\nu }\right)}+\mathrm{terms}\mathrm{not}\mathrm{involving}\nu$

From this a direct line search algorithm can be devised for finding the maximum of l(v) and hence the maximum likelihood estimator of v. (Note that further algorithmic simplifications can be made by realising that many of the terms in the sum over k are repeated for all values of i—in fact all of them after k = v – t_min + 1 where t_min is the smallest value among the t_t.) The author found that a golden section search based on this approach worked almost as well as the Newton-Raphson method used in section 2.3.

We can also find what appears to be a fairly good approximation, using natural logarithms in Eq. 6, and Stirling’s approximation

$ln\nu !\approx \frac{ln2\mathrm{\pi }}{2}+\left(\nu +\frac{1}{2}\right)\mathit{ln}\nu -\nu$

Setting $\frac{\mathit{dl}\left(\nu \right)}{d\nu }=0$ gives the following, after some algebra:

$\nu =\frac{\frac{x}{2\left(1-x\right)}+t}{ln\left(1-x\right)}$

where x = (t – 1)/v. This can easily be iterated to a solution. (It is very easily handled in a spreadsheet, for example.) Again, if we have multiple determinations of T, the generalization is easy to obtain:

$\nu =-\frac{{\displaystyle {\sum }_{t=1}^m\left[\frac{x_t}{2\left(1-x_t\right)}+t_i\right]}}{{\displaystyle {\sum }_{i=1}^{m}ln\left(1-x_i\right)}}\text{.}$

Note that even when we exhaust our resources, and still we have k = r, we could use the techniques described above on the assumption that iteration r + 1 will provide the first re-occurrence. In this way, we could calculate a conservative estimate of v.

4 ESTIMATING THE NUMBER OF SAMPLES

We might expect that most of the time we will be faced with problems having large values of v (and thus of κ). However, some problem instances may have relatively small values, in which case we have a different but still interesting question: how long should we sample before we can reasonably be sure that all attractors have been found? We can model this situation as follows.

Suppose there are v attractors, and that we have already found k of them. The waiting time W_k for the (k + l)st attractor will have a geometric distribution

$f\left(t|k\right)=\frac{\nu -k}{\nu }{\left(\frac{k}{\nu }\right)}^{t-1}$

with expectation v/(v – k) and variance kv/(v — k)². The overall waiting time will be

$W=1+{\displaystyle \sum _{k=1}^{\nu -1}{W}_k}$

and since these waiting times are independent, we can approximate the expectation and variance as follows:

$\begin{array}{l}E\left[W\right]=1+{\displaystyle \sum _{k=1}^{\nu -1}\frac{\nu }{\nu -k}}\\ \begin{array}{cc}\hfill \begin{array}{cc}\hfill \hfill & \hfill \hfill \end{array}\hfill & \hfill =\hfill \end{array}\nu {\displaystyle \sum _{k=1}^{\nu }\frac{1}{k}}\\ \begin{array}{ccc}\hfill \hfill & \hfill \hfill & \hfill \approx \nu \left(\mathit{ln}\nu +\gamma \right)\hfill \end{array}\end{array}$

where γ = 0.57721.. is Euler’s constant: and

$\begin{array}{l}V\left[W\right]=0+{\displaystyle \sum _{k=1}^{\nu -1}\frac{k\nu }{{\left(\nu -k\right)}^2}}\\ \begin{array}{ccc}\hfill \hfill & \hfill \hfill & \hfill =\hfill \end{array}{\nu }^2{\displaystyle \sum _{k=1}^{\nu -1}\frac{1}{k^2}-\nu {\displaystyle \sum _{k=1}^{\nu -1}\frac{1}{k}}}\\ \begin{array}{cc}\hfill \begin{array}{cc}\hfill \hfill & \hfill \hfill \end{array}\hfill & \hfill ={\nu }^2\zeta \left(2\right)-\nu \left(\mathit{ln}\nu -\gamma -1/\nu \right)\hfill \end{array}\end{array}$

where $\zeta \left(s\right)={\displaystyle {\sum }_1^{\infty }{k}^{-s}}$ is Riemann’s zeta function. The case s = 2 is a special case, for which $\zeta \left(2\right)={\mathrm{\pi }}^2/6$, so finally

$V\left[W\right]\approx \frac{{\left(\nu \mathrm{\pi }\right)}^2}{6}+1-v\left(\mathit{ln}v+\gamma \right)$

Although both expressions are approximations, the errors are fairly small. The error in using Euler’s constant is already below 1% for v = 15, and while larger and slower to fall, the error in the infinite sum approximation drops below 2.5% for v = 25. Further, the errors are in opposite directions—one is a lower and the other an upper bound, so the net effect is likely to be unimportant.

We can use these estimates together with a Normal approximation to establish with probability a that the waiting time will exceed a given value:

$W>\nu \left(\mathit{ln}\nu -\gamma \right)+z_{\alpha }\sqrt{\frac{{\left(\nu \mathrm{\pi }\right)}^2}{6}+1-\nu \left(\mathit{ln}\nu +\gamma \right)\text{.}}$

where z_a is the appropriate standard Normal value. Finally, the right-hand side of the above expression can be inverted (numerically) to find a confidence limit on v. Table 3 gives some representative values, obtained very simply by using a spreadsheet equation solver.

If the actual number of distinct local optima found in r samples is no more than the value given by such calculations, we can be confident (to approximately the degree specified) that we have found all the local optima. As already remarked, while the estimates of both mean and variance have small errors, they are unlikely to have a large influence on the degree of confidence. However, while the assumption of Normality is convenient, it is probably not well-founded: there is clearly a lower bound on the value of W, since it cannot be less than v, while the upper tail of the distribution may be very long. Thus, we should perhaps make do with Chebyshev’s inequality

$\mathit{Pr}\left[\left|\frac{W-E\left[W\right]}{V\left[W\right]}\right|\ge c\right]\le \frac{1}{c^2}$

which gives a less sharp, but still useful, confidence limit.

5 AN APPLICATION

In principle, this approach could be useful in providing some assurance of the quality of solutions obtained in the course of a heuristic search. Not only does it tell us something (although not everything) about the landscape, but at least tentatively, we now have a statistical way of assessing the amount of search that we need in order to find the global optimum with a reasonable probability.

It also gives us a means of comparing different representations and operators. For example, in the case of a GA, we could estimate the number of attractors resulting from the application of a GA, and compare this with what happens using a deterministic neighbourhood search using a bit flip operator, as a way of measuring the ‘improvement’ resulting from using a GA. (Of course, just looking at the numbers is not the only criterion—the quality of the respective solutions should also be taken into account.)

In (Reeves, 2000) it is shown that it is possible to generate sets of equivalent N K- landscapes—as introduced by (Kauffman, 1993); equivalent in the sense that all have the same epistasis variance, while having widely differing numbers of local optima with respect to a bit flip neighbourhood search. (The use of this operator implies that the underlying the landscape is based on the Hamming metric. Thus we shall call it the Hamming landscape.) However, how these landscapes compare with respect to a GA is not clear. Two NK-functions with N = 10,12 and K = 4 were chosen, representing those furthest apart in terms of numbers of Hamming landscape local optima. These are labelled ‘hard’ and ‘easy’ below. Each problem was solved repeatedly using a steady-state GA having the following parameters: population size 32, linear rank-based selection of parents, crossover was always performed (either one or two point), followed by mutation at a rate of either 0.05 or 0.10 per bit. One new offspring was produced at each iteration, and it replaced one of the worst 50% of the existing population. The run was terminated at convergence to an attractor.

At this point, we should explain what is meant by ‘convergence’. In the sense of (Vose, 1999), an attractor is a population, which does not necessarily coincide with a corner point of the simplex—i.e., it may not consist of multiple copies of a single string. Whenever mutation is involved, there is always the possibility of some variation, so detecting that an attractor (in the Vose sense) has been found is somewhat imprecise. As a reasonable heuristic, in these experiments it was defined as the situation when 90% of the population agreed about the allele at each locus. In order to guard against very long convergence times in the computer experiments, a termination criterion was also included in the code: that the run should be ended after 512 strings (a large fraction of the entire search space for these problems) had been evaluated. As a matter of fact, however, this criterion was never needed for the parameters tested, although with higher mutation rates and a softer selection pressure such a criterion might become necessary.

The numbers of attractors found on this basis in a sample of 100 replicate runs were counted and an estimate made using the methodology developed above. The results were as shown in Table 4. The numbers of local optima with respect to the neighbourhood search were obtained by exact counting using a version of Jones’s ‘reverse hill-climbing’ approach (Jones, 1995). However, it is not possible to compute the numbers of attractors exactly for a GA, even when the parameters are fixed, since there is so much randomization involved. What we estimate therefore is in some sense the number of the ‘most common’ attractors, ignoring possible pathological behaviour.

This is merely a small example, but even this demonstrates some interesting differences in the performances of the GAs. The number of GA attractors for the ‘easy’ landscapes is generally smaller (with a notable exception for the N = 12 case with mutation at 0.05) than for the ‘hard’ ones, and there does appear to be a difference between the 1-point and 2-point crossovers. We might also intuit that high mutation rates would imply fewer attractors, and this is evident in most cases (with the N = 12 case again an exception). It is also clear that just examining the NS landscape may not be adequate in predicting the performance of a GA. The number of attractors is clearly more than the number of NS-local optima in the ‘easy’ case, and seems likely to be fewer in the ‘hard’ case.

In some further experiments, a set of 35 equivalent NA’-functions (with N = 15, K = 4) was investigated; for each case a GA was run (as described above, with 1-point crossover and 0.10/bit mutation rate) for 100 independent trials. The number of attractors was estimated and compared with the (known) number of bit-flip local optima for each of the related landscapes. The correlation between the number of GA attractors and the number of Hamming local optima was 0.72, a statistically significant value. When the actual strings were compared, the set of GA attractors was almost always a subset of the Hamming local optima. Thus, although the landscapes are different in general, it seems that their fixed points tend to coincide, and despite the conceptual difference between deterministic point-based NS methods and stochastic population-based GAs, their respective landscapes seem to have similar properties.

Finally, the numbers of GA attractors was re-estimated using 500 independent runs instead of 100. In every case, the initial estimated number of attractors was exceeded, and although the numbers of attractors using 500 runs was well predicted by the numbers estimated using 100 runs (all fell within the initial 95% confidence interval), the correlation with the numbers of Hamming local optima was less strong (0.51 instead of 0.72). Now the set of attractors included points that were not Hamming local optima, so this reduction in correlation was not altogether a surprise. However, the ‘new’ attractors tended to be less fit than those found in the first 100 runs, and obviously they had a smaller attractive basin. This has some implications for the usefulness of the methodology that will be discussed in the next, final, section.

6 CONCLUSIONS AND FURTHER WORK

Several procedures have been presented for an empirical investigation of one aspect of a GA landscape. Previous approaches have not been able directly to answer the question of how many attractors there are, but the approach described here is able to estimate this quantity. Several practical questions of implementation have been reviewed, and an application has been made in order to demonstrate the methodology. The techniques described are not limited to GAs, but can in principle be applied to any heuristic search method.

There are some caveats that we should mention. Firstly, there is clearly a substantial computational burden in such investigations, and the size of the problem instance is clearly a factor in the feasibility of this approach. The number of samples needed may become infeasibly large as the size of the problem space increases.

Secondly, any estimate is useful only as long as the assumptions upon which it is based are valid. The fundamental assumption made above is that the attractors are isotropically distributed in the landscape, which implies that their basins of attraction are of more or less equal size. In fact, this is almost certainly not the case for many instances of NS landscapes. Such landscapes have been investigated empirically for such problems as the TSP, graph bisection and flowshop scheduling (Kauffman, 1993; Boese et al., 1994; Reeves, 1999b), and in many cases it is found that the local optima tend to be clustered in a ‘big valley’—closer to each other (and to the global optima) than a pair of randomly chosen points would be. Furthermore, the better optima tend to be closer to the global optima, and to have larger basins of attraction, than the poorer ones. Thus, optima found by repeated local searches are disproportionately likely to be these ‘more attractive’ (and hopefully fitter) ones. The number of local optima found by assuming an isotropic distribution is therefore likely to be an under-estimate of the true value. Nevertheless, we might hope that the statistical estimates would still be useful, as many of the local optima that we failed to find in a non-isotropic landscape would not (if the big valley conjecture holds) be very important anyway.

We do not know if similar patterns affect GA landscapes and attractors, but we have to recognize the possibility. Certainly, this is suggested by the analysis of the 35 equivalent NK-functions in the previous section. When the number of runs was extended from 100 to 500, several more attractors were found, more than had been estimated by the methods of the previous sections. These attractors seemed to have small basins, and to be less fit, so the remarks above relating to local optima seem to be echoed for the case of GA landscapes too.

In the applications above the effect of a non-isotropic distribution of attractors is probably not acute. When we compare the relative performance of different operators, for example, the effects of a non-isotropic distribution may apply in the same way to all of them. Also, on the empirical evidence of many fairly large studies of NS landscapes, and on the (admittedly much smaller) examples of GA landscapes investigated above, the attractors in the ‘tail’ of the distribution of basin sizes may be relatively unimportant. The assumption of approximate uniformity among the ones that we do care about is much more reasonable, and might mean that the estimates we obtain are fairly accurate, as long as we interpret them as referring to these ‘good’ attractors.

Nevertheless, if we wish to find still better estimates of the number of attractors, the effects of a non-uniform spread of attractors should be taken into account. A second paper that is currently in preparation will both examine the extent of the effect of the assumptions in the above analysis, and also explore stochastic models of non-isotropic landscapes.