Information Technology Reference
In-Depth Information
5R su s
All four versions of the algorithms were tested on the three Diophantine equa-
tions in 3D. A version of the algorithm which combined anti-elitism with the
second variant of the megamutation was also tested on the fourth equation.
All the algorithms used a population size and clone size of 10. The mutation
rate (probability of flipping each bit in the hotspot) was held fixed at 0.5. Each
experiment was run 100 times with various numbers of maximum iterations,
depending on the equation. The maximum number of iterations was set by ob-
serving the rate of convergence of the algorithms on each equation, and noting
that convergence almost never occurred beyond a certain point.
Table 1. Number of iterations out of 100 in which algorithm converged on the optimum
Problem Iterations BCA Algorithm #1 #2 #3 #4
#2
4,000
53
78 100 100 n/a
#3
100,000
36
90
84 100 n/a
#4
1,000,000
4
5
69
77
77
Table 1 shows the number of runs which converged before the maximum num-
ber of iterations was reached. The algorithms with megamutation found greater
numbers of optimal solutions than the original algorithm for all three equations
in 3D. However, the anti-elitist algorithm equalled or outperformed all the other
algorithms, converging for all the runs for equations 2 and 3, and converging
77% of the time for equation 4. No improvement was found by combining the
megamutation with the anti-elitism.
Table 2. Number of fitness evaluations (mean and standard deviation) for problem #2
Algorithm:
BCA #1 #2 #3
Mean Fitness Evaluations × 10 4
6.3 4.7 2.6 4.4
Standard Deviation × 10 4
10.0 9.3 2.8 4.9
Table 2 shows the average and standard deviations of the number of evalu-
ations which were required to achieve convergence, thus giving an idea of the
amount of computational effort involved. This includes only the runs when the
algorithm did converge to an optimal solution (since it only makes sense to mea-
sure the average evaluations to the convergence when an optimal solution was
actually found). The megamutations reduced the average number of evaluations
required for equations 2 and 3, when compared with the original BCA. How-
ever, the number of evaluations increased with megamutation on equation 4.
The anti-elitism reduced the number of evaluations on all equations. Both the
megamutations and the anti-elitism also reduced the standard deviation of all
three equations. Observe that the standard deviations in table 2 are huge: in
Search WWH ::




Custom Search