Randommutation hill climbing RMHC

Choose a string at random. Call this string best-evaluated

Choose a locus at random to flip. If the flip leads to an equal or higher fitness, then set best-evaluated to the resulting string.

Go to step 2 until an optimum string has been found or until a maximum number of evaluations have been performed.

Return the current value of best-evaluated. (This is similar to a zero-temperature Metropolis method.)

We performed 200 runs of each algorithm, each run starting with a different random-number seed. In each run the algorithm was allowed to continue until the optimum string was discovered, and the total number of function evaluations performed was recorded. The mean and the median number of function evaluations to find the optimum string are

Table 4.1: Mean and median number of function evaluations to find the optimum string over 200 runs of the GA and of various hill-climbing algorithms on R1 The standard error is given in parentheses.

Table 4.1: Mean and median number of function evaluations to find the optimum string over 200 runs of the GA and of various hill-climbing algorithms on R1 The standard error is given in parentheses.

200 runs

GA

SAHC

NAHC

RMHC

Mean

61,334(2304)

> 256,000 (0)

> 256,000 (0)

6179(186)

Median

54,208

> 256,000

> 256,000

5775

given in table 4.1. We compare the mean and the median number of function evaluations to find the optimum string rather than mean and median absolute run time, because in almost all GA applications (e.g., evolving neural-network architectures) the time to perform a function evaluation vastly exceeds the time required to execute other parts of the algorithm. For this reason, we consider all parts of the algorithm other than the function evaluations to take negligible time.

The results of SAHC and NAHC were as expected—whereas the GA found the optimum on R1 in an average of 61,334 function evaluations, neither SAHC nor NAHC ever found the optimum within the maximum of 256,000 function evaluations. However, RMHC found the optimum on R1 in an average of 6179 function evaluations—nearly a factor of 10 faster than the GA. This striking difference on landscapes originally designed to be "royal roads" for the GA underscores the need for a rigorous answer to the question posed earlier: "Under what conditions will a genetic algorithm outperform other search algorithms, such as hill climbing?"

No Fail Fitness

No Fail Fitness

This is a health guide that will teach you all about the fitness industry insider that reveals the 2 secret ingredients that must be in your workout in order for you to lose weight and keep it off.

Get My Free Ebook


Post a comment