Local Hill Climbing

A technique borrowed from the current image-calibration code is to take a “good” solution, and to try small permutation on the matrix values to get a better solution. This is done to the best performer as it is copied from one generation to the next. A GA parameter is used to set the maximum number of hill-climbing iterations, resulting in small hill-climbing steps per generation. If needed, a recurring best performer can continue to climb the same hill over many generations.

Gray-Code Mapping

Gray-coding is commonly used with GA implementations due to the 1-bit change in neighboring gray-code values. The option to evaluate the matrix value deltas as gray-coded numbers was provided and investigated.

EFFECT OF CHANGING GA PARAMETERS ON THIS PROBLEM

The GA implementation uses various parameters during a matrix-solution run. The effect of these parameters was studied in depth to access the parameters’ influence on the convergence and timeliness of the run. There were some unexpected observations made in this study.

These studies were designed to have the GA run for about 30 seconds maximum. The resulting distance value was tracked as well as the time to run. Five runs at each setting were used to get a statistical spread of the parameter-setting effects. Rather than include pages and pages of multi-line plots, the main points of these studies are summarized. The author can be contacted for access to the detailed analysis.

Maximum Generations (MG) and Population Size (PS)

These two parameters are tightly intertwined in this problem due to the time deadline constraint; an increase in the population size will cause each generation to take longer to run. Population sizes in the range of 10 to 100 individuals were studied. Without accounting for the time factor, larger populations generally had better convergence values for a given number of generations. It was observed that the relation between MG and PS is a linear relation, where PS * MG = 1,000,000 resulted in a maximum-generation stopping time of about 30 seconds. A change in either PS or MG would yield the required value for the other. The population study was re-run with this time-normalized relationship, which showed an advantage in convergence value in a given time period to a population size of about 40 individuals. A PS of 40 requires a MG of 25,000 for 30 seconds. To achieve a 20 second time for a PS of 40, a MG of 25,000 * 2 / 3 = 17,000 (approximately) was used.

Crossover Types

The 1-point, 2-point, and matrix-element crossover types were used with various usage weights. With 100% usage of the 1-point, or 80% or more of the matrix-element crossovers being used, the GA did not converge within the desired time. Various average mixes of these three crossover operators gave good results; there was not a clear mix which outperformed other mixes. The setting of 20%, 40%, 40% for the 1-point, 2-point, and matrix-element crossover operators proved to be a good robust setting.

Number of Bits

The number of bits used (N) for each matrix delta value, and the resulting size of the search space had little effect on the operation of this GA. As expected, small values of N (8 or less) resulted in unacceptable results. Surprisingly, in the range from N=8 to N=64 bits, there was little difference in the performance of the GA in terms of time-to-converge and resulting distance value when finished.

Maintaining the Best Performer

Maintaining the previous generation’s best performer in the current generation proved to be a valuable technique. Without this feature, runs were observed which would be converging, then lose the best performer and jump up a bit, continue to converge, then jump again, and so on, as depicted in Figure 2.9. While the average fitness of the population may have been continually decreasing over this entire period, the fact that the GA may be stopped at any given generation and the current best solution is to be used, made this unacceptable in a time-constrained GA.

Figure 2.9  Effect of losing the best-performer on the best-of-generation solution.

Varying Mutation Rate and Comet-Strike Operator

Observation shows that increasingly introducing new genetic material into the population, and also mass introduction of new genetic material into the population, can revitalize the convergence rate in a stagnate run. Without these two mutation-type operations, runs were observed which would stagnate for many hundreds of generations. Given this tendency to favor mutation, a mutation study was undertaken to study the effect of increasing the basic single-bit mutation occurrence. Figure 2.10 shows the results of a series of runs where this mutation rate was increased, and the resulting average fitness for multiple runs is plotted. There is a trend to favor more and more chance of mutation up to a certain point (about 0.002 percent). Additional increases in mutation have a degrading effect on the GA’s performance as the system is becoming less of a GA engine and more of a random-search algorithm.

Figure 2.10  Effect mutation rates on the best-of-generation solution.

Local Hill Climbing

Observation shows that this technique allowed the best performers to slide into a near-by better solution.

Gray Code Mapping

As expected, the use of gray-code mapping had a positive effect on the generation-to-generation performance of the GA, resulting in a 9.5% better convergence value after a given number of generations. However, this is not the whole story. As discovered in implementing the gray-coding capabilities [8], the mapping from a binary integer to gray-code is a simple 1-line equation. However, the mapping from gray-code to a binary integer uses an iterative algorithm which loops on the number of bits (N). This code proved to be rather expensive to execute as was needed for each individual at each generation, and multiple times for the best performers in the local hill-climbing. While 9.5% better in average final value, the gray-code execution time was 2.2 times longer (49 S vs. 22 S for the settings used). With the emphasis on convergence value within a specific time-frame, the use of gray-coding was detrimental and was thus dropped for this problem.

Use of a Matrix Subset

The technique of identifying a subset of the transformation matrix and only searching with nine of the sixteen matrix values proved to both allow acceptable convergence to be achieved as well as providing a time savings. Comparing using all sixteen matrix values to only using nine resulted in a 33% drop in the time-to-run, and a 23% better convergence value. Reducing the scope of the problem based on observed numerical results was beneficial.