Computational Complexity

The usefulness of constructional selection for genetic algorithms should be measured by the number of points in the search space that need to be evaluated to reach a certain fitness. There are several strategies for spending computational resources: One can take an a priori representation, run numerous adaptive walks from different initial genotypes, and take the fittest peak attained after expenditure of the set amount of computations. Alternately, one can partition one's computations sampling among different genotype-phenotype maps to find that with the fittest peak. Lastly, the approach examined here is to progressively modify simple genotype-phenotype maps to more complex ones with the genome growth algorithm described. The payoff in the level of optimization obtained through constructional selection shows it to be a much more efficient.

As a simple example, consider the class of NK landscapes with the highest expected fitness peaks, the k=1 landscapes (which is K=0 in Kauffman's original definition), in which there is a one-to-one map from each gene to each fitness component, and f=n. Each gene can be optimized individually, so it takes the evaluation of 2n genotypes to find the global peak for the landscape. Each fitness component is i.i.d., where the optimal $\hat{\phi}_i$ is distributed as the maximum of two independent uniform random variables on [0,1]. The probability density of each maximum $\hat{\phi}_i$ is $f(\hat{\phi}) = 2 \hat{\phi}$. So E $(\hat{\phi}) = 2/3$ and Var $(\hat{\phi}) = 1/18$. With n=f=31 genes and fitness components, one obtains:

$$\mbox{E}[w(\hat{\mbox{\boldmath\(x\)\unboldmath }})] = 2/3, \... ...oldmath\(x\)\unboldmath }})] = \frac{1}{18 f} \approx 0.00179.$$

The average fitness attained under constructional selection in the numerical simulations (where the average k is much larger than 1) is about 0.89, which is therefore some 5 standard deviations ( $5\times 0.0423$) above the expected value of peaks obtained from generic k=1 landscapes. The probability of a k=1 landscape having a peak with fitness at least 0.89, under a normal approximation (an overestimate), is $3 \times 10^{-7}$. So a strategy of sampling different random k=1 landscapes would require over $2\times 10^6$ samples to be likely to obtain fitness peaks as high as those obtained through constructional selection, which in the runs here took some 3000 evaluations of the fitness function.

The ability to select on the genotype-phenotype map as it is constructed is the key to finding higher fitness values. To carry out constructional selection in the k=1 case, one could add one gene at a time and for each choice of the fitness component it maps to, examine the fitnesses for both alleles, and keep the allele and map that give the fittest value. The first gene would be evaluated for the f possible genotype-phenotype maps, for a total of 2f evaluations. The second gene would be sampled with the remaining f-1 unmapped fitness components, and so forth, giving a total of f(f+1) evaluations. Each resulting fitness component would be the maximum of 2(f-i+1) uniform i.i.d. values, for the ith gene/gene map pair. So the ith fitness component would be distributed as $F_i(\hat{\phi}) = \hat{\phi}^{2(f-i+1)}$. The fitness components would have expectation

$$\mbox{E}(\hat{\phi}_i) = \frac{2(f+1-i)}{2(f+1-i)+1}.$$

The expected value for the fitness peaks obtained through this constructional selection process would be

$$\mbox{E}[w(\hat{\mbox{\boldmath\(x\)\unboldmath }})] = \frac{1}{f}\sum_{i=1}^{f} \frac{2i}{2i + 1}.$$

For n=f=31, the expected fitness peak would be $\mbox{E}[w(\hat{\mbox{\boldmath\(x\)\unboldmath }})] \approx 0.945$, and would take $31\times32=992$ evaluations to find. This is a much more efficient use of computational resources than randomly searching generic k=1 landscapes for those with the highest peaks.