The data calculated in Table 2.6 shows the effect of increasing the number of bits used in the delta coding. A simple linear mapping from the minimum to the maximum value for each matrix location is used. The concern here is that if N is too small, then a good T21 cannot be found because, as the delta is incremented from one possible value to the next possible value, the requisite value is bypassed.

To allow the needed value to be approximated to an acceptable degree, the number of bits-per-value can be increased. Increasing N, however, will increase the search-space of the problem. Given nine matrix values to search on, for each 1-bit increase in N, there is a 2⁹, or 512 times increase in the size of the search space. To allow the GA to converge in a reasonable time, the search space should be kept small.

GA OPERATORS AND TECHNIQUES

In additional to the usual reproduction, crossover, and mutation GA operators [6], additional GA operators and techniques were designed and implemented for this specific problem. The entire set of GA operators implemented for this problem follow:

Crossover

A simple 1-point crossover, as shown in Figure 2.5, is used which swaps the alleles (bit-patterns) in two selected parents at a given bit position. This bit position can be chosen anywhere within the strings, within a delta value as well as between delta values.

Figure 2.5  Single point crossover.

Two-Point Crossover

A 2-point crossover, as shown in Figure 2.6, is used which swaps the alleles in two selected parents between two given bit positions. These bit positions can be chosen anywhere within the strings, within a delta value as well as between delta values. For this crossover, the string is considered to wrap back on itself in a ring-like fashion, which results in this 2-point crossover swapping a selection of the ring for two selected parents.

Figure 2.6  Two-point crossover.

Matrix-Element Crossover

Wallet, et al. [3] inspired the use a matrix-element crossover operator, as seen in Figure 2.7. Their technique of selecting a contiguous sub-region of the 4×4 matrix was expanded to select a number of matrix elements which were related for this specific problem. Templates in the code were designed to define different matrix elements to be used for the eight different matrix-element crossovers possibilities desired. When the matrix-element crossover was selected, one of these templates was then selected and used to accomplish the crossover.

Figure 2.7  Matrix-element crossover.

The matrix-element crossover swaps selected matrix elements between two selected parents. These swaps are done on full N-bit matrix elements within the strings and does not mix string values within a given matrix element. Figure 2.8 shows the eight matrix-element templates implemented here. The odd templates fit within the Wallet scheme, while the even-numbered templates show the extension to the Wallet scheme. The templates correspond to transformation operators: (1) Z rotation, (2) Z rotation with homogeneous coordinate scaling, (3) X and Y translation, (4) X and Y translation and perspective, (5) X and Y perspective, (6) X and Y scaling, (7) X and Y perspective with homogeneous coordinate scaling, and (8) X, Y, and Z scaling with homogeneous coordinate scaling.

Figure 2.8  Eight matrix-element crossover templates.

Maintaining the Best Performer

Similar to De Jong’s generation-gap idea, the best performer of each generation is copied as-is to the next generation. This guarantees that the solution as found by the GA will not get worse over time. This approach is known as elitist selection.

Varying Mutation Rate

The classic GA implementation uses a fixed mutation-rate. Being concerned with a timely solution, GA stagnation was studied very closely. GA stagnation is defined as the number of generations in which the best performer remains the same, as guaranteed above. One stagnation related solution was to impose an increasing mutation rate (Ms), which is the product of the no-change generation count (NC) and the mutation rate (MR): Ms = NC * MR. This results in ever-increasing chances for mutation to change the best performer in a positive direction.

Comet-Strike Operator

Another GA stagnation operation is, as coined by Robert Dain [7], the Comet-Strike. The analogy is that of a comet striking the earth, which reeks havoc with the ecosystem and destroys all but the most robust of life. Following the comet-strike, new species evolve. The GA equivalent is to maintain the best performer and re-initialize the remaining population. The comet-strike operator is invoked when the no-change generation count (NC) goes above a set threshold and the average/minimum value is less than M (the bulk of the population consists of similar genetic material).

Total-Comet-Strike Operator

A total-comet-strike operator is a re-initialization of the entire population. For this problem, and possibly other real-time GA problems, this operator allows the GA run to result in a better solution at the end of the imposed time-limit.