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?"

Fitness The Guide To Staying Healthy

Fitness The Guide To Staying Healthy

If you're wanting to learn about fitness... Then this may be the most important letter you'll ever read! You Are Going To Get An In-Depth Look At One Of The Most Remarkable Fitness Guides There Is Available On The Market Today It doesn't matter if you are just for the first time looking at a healthier choice for your life, this fitness guide will get you on the right track to staying healthy.

Get My Free Ebook


Post a comment