A couple of hill climbing heuristic algorithms are provided in GAUL for local searches and for comparision to GAs. This section of the tutorial presents these heuristic optimisation functions.

Brief Hill Climbing Primer

The basic concept of all hill climbing algorithms is very simple. Individual alleles are modified in such a way that the overall fitness is maximised. Hill climbing algorithms are typically very efficient at locating local maxima although this leads to their major deficiency; they tend to get stuck at local maxima rather than continuing to the proper global maxima.

Hill Climbing Implemented in GAUL

A couple of hill climbing algorithms are implemented in GAUL. These are demonstrated in pingpong_nahc.c and pingpong_rahc.c. These may be used to compare against the simple GA search procedure used in pingpong.c.

The two hill climbing heuristics are, respectively, "next ascent hill climbing" and "random mutation hill climbing". In both cases an allele is modified in both directions, that is an alelle with a value of, say, 10 will be tested as 9 and 11. Whichever value of that allele maximises the fitness will become the current solution and another allele will be tested. In next ascent hill climbing the alleles are tested sequentially, while random ascent hill climbing randomly selects the next allele to examine.