Skip to content

Hill Climbing

Introduction

Hill climbing is a very basic optimization technique, that explores the search space only localy. It starts at an initial point, which is often chosen randomly and continues to move to positions within its neighbourhood with a better solution. It has no method against getting stuck in local optima.

Example

from gradient_free_optimizers import HillClimbingOptimizer

...

opt = HillClimbingOptimizer(search_space, epsilon=0.1)
opt.search(objective_function, n_iter=100)

About the implementation

The hill climbing algorithm is saving the current position from the search space and finds new positions by sampling random positions around it with a gaussian distribution. This is done with a gaussian distribution. So if the position is further away the probability of getting selected is lower, but never zero. This makes the hill climbing more heuristic and a bit more adaptable. The positions found around its current positions are called neighbours. The hill climbing will sample and evaluate n_neighbours before moving its current position to the best of those neighbour. After moving the algorithm restarts sampling neighbours from its distribution around its new current position.

If the distribution is "normal" (default) the hill climbing algorithm will sample its neighbours with the normal distribution:

\[ f(x) = \frac{1}{\sigma\sqrt{2\pi}} \exp^{\left( -\frac{1}{2}\left(\frac{x-\mu}{\sigma}\right)^{\!2}\,\right)} \]

In this equation \(\mu\) is the current position in the search space and \(\sigma\) is calculated with the size of the search space in each dimension and the epsilon.

\[ \sigma = \text{dim-size} * \epsilon \]

So the standard deviation of the gaussian distribution in each dimension is dependend on the size of the search space in the corresponding dimension. This improves the exploration if the sizes of the search space dimensions are differing from each other.

Parameters

epsilon

The step-size of the hill climbing algorithm. Increasing epsilon also increases the average step-size, because its proportional to the standard-deviation of the distribution of the hill-climbing-based algorithm. If epsilon is too large the newly selected positions will be at the edge of the search space. If its value is very low it might not find new positions.

  • type: float
  • default: 0.03
  • typical range: 0.01 ... 0.3

distribution

The mathematical distribution the algorithm draws samples from. All available distributions are taken from the numpy-package.

  • type: string
  • default: "normal"
  • possible values: "normal", "laplace", "logistic", gumbel"

n_neighbours

The number of positions the algorithm explores from its current postion before setting its current position to the best of those neighbour positions. If the value of n_neighbours is large the hill-climbing-based algorithm will take a lot of time to choose the next position to move to, but the choice will probably be a good one. It might be a prudent approach to increase n_neighbours of the search-space has a lot of dimensions, because there are more possible directions to move to.

  • type: int
  • default: 3
  • typical range: 1 ... 10