Greedy Ascent Hill Climber (GAHC)

Introduction

xlOptimizer implements Greedy Ascent Hill Climber (GAHC), a local optimizer that can be applied to a binary chromosome [1]. This local optimizer can be invoked for a prescribed function evaluations at the end of a standard Genetic Algorithms (GA) analysis, in order to obtain the local optimum corresponding to the best solution found by the GA. However, GAHC is also available as a stand-alone algorithm, in which case a random individual is used as starting point.

How does it work?

The algorithm uses a starting point for the analysis, which is a binary chromosome. This chromosome is constantly mutated until a point that no improvement is observed.

Mathematical formulation

Each bit of the chromosome is flipped to the opposite value (0 to 1 and vice versa) at a position which changes in an endless loop along the chromosome length. The objective value of the mutant is compared to the one of the currently best chromosome. If the mutant is better, it becomes the currently best chromosome. The process is ended when a full loop along the chromosome length has been achieved without improvement. At this point, the currently best chromosome is the local optimum [1].

Options in xlOptimizer

The following options are available in xlOptimizer:

Step 1

hill climber xloptimizer options step 1

Enter a short title for the scenario. The log files will be saved to a subfolder with this name.

Step 2

hill climber xloptimizer options step 2

Select other algorithm settings. The options are the following:

  • Gray code: Choose whether the chromosome is encoded using Gray code or not.
  • Maximum hill climbing evaluations: Choose the maximum number of function evaluations. The local optimum may be found in less steps.

Step 3

hill climber xloptimizer options step 3

Select the termination criteria. At least one termination criterion must be active. Usually one selects a maximum number of function evaluations and/or a time limit.

Step 4

hill climber xloptimizer options step 4

Select the action when the analysis is finished:

  • Nothing: The last individual analysed remains.
  • Restore previous solution: The solution that was visible before the analysis is restored.
  • Use best: The best solution that was discovered during the analysis is applied.
  • Use best if better than the previous version (recommended): The best solution that was discovered during the analysis is applied only if it is better than the previous solution. In the opposite case the previous solution is restored.

Step 5

hill climber xloptimizer options step 5

Select whether you want to use random or specific seeds for the random number generator. The seeds must be large negative numbers e.g. -100000. Usually a number of analyses with random seeds is performed. The filename of the log is the seed used in the specific analysis.

Step 6

hill climber xloptimizer options step 6

Select the output path. A subfolder with the name of the scenario will be used. Usually a relative path is used i.e. the absolute path check box is not checked. This results in the output logs being saved in the same path as the project file. 

References

[1] Eiben, A.E., Smith, J.E., 2003. Introduction to Evolutionary Computing. Springer, New York.