net.sf.cpsolver.ifs.algorithms

## Class HillClimber<V extends Variable<V,T>,T extends Value<V,T>>

- java.lang.Object
- - net.sf.cpsolver.ifs.algorithms.NeighbourSearch<V,T>
  - - net.sf.cpsolver.ifs.algorithms.HillClimber<V,T>

- All Implemented Interfaces:
    NeighbourSelection<V,T>, LazyNeighbour.LazyNeighbourAcceptanceCriterion<V,T>, SolutionListener<V,T>
  Direct Known Subclasses:
    StepCountingHillClimber

      public class HillClimber<V extends Variable<V,T>,T extends Value<V,T>>
      extends NeighbourSearch<V,T>

  Hill climber. In each iteration, one of the given neighbourhoods is selected first, then a neighbour is generated and it is accepted if its value `Neighbour.value()` is below or equal to zero. The search is stopped after a given amount of idle iterations ( can be defined by problem property HillClimber.MaxIdle).
  Custom neighbours can be set using HillClimber.Neighbours property that should contain semicolon separated list of `NeighbourSelection`. By default, each neighbour selection is selected with the same probability (each has 1 point in a roulette wheel selection). It can be changed by adding @n at the end of the name of the class, for example:
  `HillClimber.Neighbours=net.sf.cpsolver.ifs.algorithms.neighbourhoods.RandomMove;net.sf.cpsolver.ifs.algorithms.neighbourhoods.RandomSwapMove@0.1`
  Selector RandomSwapMove is 10× less probable to be selected than other selectors. When HillClimber.Random is true, all selectors are selected with the same probability, ignoring these weights.
  When HillClimber.Update is true, `NeighbourSelector.update(Neighbour, long)` is called after each iteration (on the selector that was used) and roulette wheel selection that is using `NeighbourSelector.getPoints()` is used to pick a selector in each iteration. See `NeighbourSelector` for more details.
  Version:
    IFS 1.2 (Iterative Forward Search)
    Copyright (C) 2014 Tomáš Müller
    muller@unitime.org
    http://muller.unitime.org
    This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.
    This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
    You should have received a copy of the GNU Lesser General Public License along with this library; if not see http://www.gnu.org/licenses/.

- - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `protected double` | `iBestValue`
    `protected int` | `iLastImprovingIter`
    `protected int` | `iMaxIdleIters`
    `protected boolean` | `iSetHCMode`

    - ### Fields inherited from class net.sf.cpsolver.ifs.algorithms.NeighbourSearch

      `iDF2, iIter, iLog, iPhase, iProgress, iT0`

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `HillClimber(DataProperties properties)` Constructor HillClimber.MaxIdle ... maximum number of idle iterations (default is 200000) HillClimber.Neighbours ... semicolon separated list of classes implementing `NeighbourSelection` HillClimber.AdditionalNeighbours ... semicolon separated list of classes implementing `NeighbourSelection` HillClimber.Random ... when true, a neighbour selector is selected randomly HillClimber.Update ... when true, a neighbour selector is selected using `NeighbourSelector.getPoints()` weights (roulette wheel selection)

  - ### Method Summary

    All Methods Instance Methods Concrete Methods
    Modifier and Type | Method and Description
    --- | ---
    `protected boolean` | `accept(Model<V,T> model, Neighbour<V,T> neighbour, double value, boolean lazy)` Accept any move that does not worsen the solution (value <= 0)
    `protected void` | `activate(Solution<V,T> solution)` Reset the idle iterations counter
    `void` | `bestSaved(Solution<V,T> solution)` Memorize the iteration when the last best solution was found.
    `protected boolean` | `canContinue(Solution<V,T> solution)` Stop the search after a given number of idle (not improving) iterations
    `String` | `getParameterBaseName()` All parameters start with HillClimber base name, e.g., HillClimber.MaxIdle
    `protected void` | `incIteration(Solution<V,T> solution)` Increase iteration counter
    `void` | `init(Solver<V,T> solver)` Initialization
    `void` | `setPhase(String phase)` Set progress phase name

    - ### Methods inherited from class net.sf.cpsolver.ifs.algorithms.NeighbourSearch

      `accept, accept, addNeighbourSelection, bestCleared, bestRestored, deactivate, generateMove, getInfo, getInfo, getNeighbours, getTimeMillis, logNeibourStatus, nextNeighbourSelection, selectNeighbour, setHCMode, solutionUpdated`

    - ### Methods inherited from class java.lang.Object

      `clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

- - ### Field Detail

    - #### iMaxIdleIters

          protected int iMaxIdleIters

    - #### iLastImprovingIter

          protected int iLastImprovingIter

    - #### iBestValue

          protected double iBestValue

    - #### iSetHCMode

          protected boolean iSetHCMode

  - ### Constructor Detail

    - #### HillClimber

          public HillClimber(DataProperties properties)

      Constructor
      - HillClimber.MaxIdle ... maximum number of idle iterations (default is 200000)
      - HillClimber.Neighbours ... semicolon separated list of classes implementing `NeighbourSelection`
      - HillClimber.AdditionalNeighbours ... semicolon separated list of classes implementing `NeighbourSelection`
      - HillClimber.Random ... when true, a neighbour selector is selected randomly
      - HillClimber.Update ... when true, a neighbour selector is selected using `NeighbourSelector.getPoints()` weights (roulette wheel selection)

  - ### Method Detail

    - #### setPhase

          public void setPhase(String phase)

      Set progress phase name

    - #### init

          public void init(Solver<V,T> solver)

      Initialization
      Specified by:
        `init` in interface `NeighbourSelection<V extends Variable<V,T>,T extends Value<V,T>>`
      Overrides:
        `init` in class `NeighbourSearch<V extends Variable<V,T>,T extends Value<V,T>>`

    - #### incIteration

          protected void incIteration(Solution<V,T> solution)

      Increase iteration counter
      Overrides:
        `incIteration` in class `NeighbourSearch<V extends Variable<V,T>,T extends Value<V,T>>`

    - #### canContinue

          protected boolean canContinue(Solution<V,T> solution)

      Stop the search after a given number of idle (not improving) iterations
      Overrides:
        `canContinue` in class `NeighbourSearch<V extends Variable<V,T>,T extends Value<V,T>>`

    - #### activate

          protected void activate(Solution<V,T> solution)

      Reset the idle iterations counter
      Overrides:
        `activate` in class `NeighbourSearch<V extends Variable<V,T>,T extends Value<V,T>>`

    - #### bestSaved

          public void bestSaved(Solution<V,T> solution)

      Memorize the iteration when the last best solution was found.
      Specified by:
        `bestSaved` in interface `SolutionListener<V extends Variable<V,T>,T extends Value<V,T>>`
      Overrides:
        `bestSaved` in class `NeighbourSearch<V extends Variable<V,T>,T extends Value<V,T>>`
      Parameters:
        `solution` - source solution

    - #### accept

          protected boolean accept(Model<V,T> model,
                                   Neighbour<V,T> neighbour,
                                   double value,
                                   boolean lazy)

      Accept any move that does not worsen the solution (value <= 0)
      Specified by:
        `accept` in class `NeighbourSearch<V extends Variable<V,T>,T extends Value<V,T>>`

    - #### getParameterBaseName

          public String getParameterBaseName()

      All parameters start with HillClimber base name, e.g., HillClimber.MaxIdle
      Specified by:
        `getParameterBaseName` in class `NeighbourSearch<V extends Variable<V,T>,T extends Value<V,T>>`