Hill climbingΒΆ

Another simple predictor is based on an optimization technique called hill climbing (see Wikipedia). As any resolver, it respects the current beam size and always picks the best solution found so far.

The biggest advantages of this predictor are simplicity and speed. It can be easily stuck in a local optima though.

The figure bellow shows hill climbing performed during resolution of a software stack in a state space with random score assigned to packages. x-axis shows resolver iterations and y-axis corresponds to scores computed. As can be seen, the predictor does not learn state space characteristics to resolve software stacks possibly falling into a local optima. The score gradually increases, taking always the top rated state from the beam.

An example of a history during hill climbing in adviser.