The goals of our testing were twofold: show that the evaluation function with incomplete scoring places slopes on previously flat terrain and show that the method provides an overall increase in rate of convergence.
In the BKB for this test only four percent of the potential solutions are complete. The remaining solutions include all possible levels of incompleteness; in this case up to four levels. The topology of this BKB is a chain with five random variables.
During testing, we compared average performance of the GA with and without our incomplete scoring algorithm over both BKBs. The first graph, Figure 2 depicts the average performance of five runs for each evaluation method. Figures 3 and 4 show the results for a typical run; Figure 3 shows the number of complete solutions in a 20 member population, and Figure 4 shows the maximum joint probability for each generation.
Figure 2: Average Performance of Joint Probability vs. Time
Figure 3: Complete Solutions vs. Generation Number
Figure 4: Joint Probability vs. Generation Number
These results show that scoring incomplete solutions greatly improves GA performance by smoothing the slopes in the solution space. This allows the GA to generate better complete solutions earlier, even in this small example. Testing with larger BKBs has shown similar results.
