Module org.cicirello.chips_n_salsa
Package org.cicirello.search.problems

Class Plateaus

java.lang.Object
org.cicirello.search.problems.Plateaus
All Implemented Interfaces:
OptimizationProblem<BitVector>, Problem<BitVector>
public final class Plateaus extends Object implements OptimizationProblem<BitVector>
This class implements Ackley's Plateaus problem, an artificial search landscape over the space of bitstrings that is characterized by large flat regions known as plateaus. This is specifically an implementation of Ackley's 1987 version of the problem (he described a similar problem in an earlier 1985 paper).

The Plateaus problem involves maximizing the following function. Divide the bits of the bit string into four equal sized parts. For each of the four parts, check whether all bits in the segment are equal to a 1, and if so, then that segment contributes 2.5*n to the fitness function, where n is the length of the entire bit string (if there are any 0s in the segment, then that segment doesn't contribute anything to the fitness function). Since there are four segments the optimum occurs when the entire bit string is all 1s, which has a maximum fitness of 10*n. The entire search space only has 5 possible fitness values: 0, 2.5*n, 5*n, 7.5*n, and 10*n.

The value method implements the original maximization version of the Plateaus problem, as described above. The algorithms of the Chips-n-Salsa library are defined for minimization, requiring a cost function. The cost method implements the equivalent as the following minimization problem: minimize cost(x) = 10*n - f(x), where f(x) is the Plateaus function as defined above. The global optima is still all 1-bits, which has a cost equal to 0.

The Plateaus problem was introduced by David Ackley in the following paper:
David H. Ackley. An empirical study of bit vector function optimization. Genetic Algorithms and Simulated Annealing, pages 170-204, 1987.

  • Constructor Summary

    Constructors
    Constructor
    Description
    Plateaus()
    Constructs an instance of Ackley's Plateaus problem.

  • Method Summary

    Modifier and Type
    Method
    Description
    double
    cost(BitVector candidate)
    Computes the cost of a candidate solution to the problem instance.
    boolean
    isMinCost(double cost)
    Checks if a given cost value is equal to the minimum theoretical cost across all possible solutions to the problem instance, where lower cost implies better solution.
    double
    minCost()
    A lower bound on the minimum theoretical cost across all possible solutions to the problem instance, where lower cost implies better solution.
    double
    value(BitVector candidate)
    Computes the value of the candidate solution within the usual constraints and interpretation of the problem.

    Methods inherited from class java.lang.Object

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

    Methods inherited from interface org.cicirello.search.problems.OptimizationProblem

    costAsDouble, getSolutionCostPair

  • Constructor Details

    • Plateaus

      public Plateaus()
      Constructs an instance of Ackley's Plateaus problem.

  • Method Details

    • cost

      public double cost(BitVector candidate)
      Description copied from interface: OptimizationProblem
      Computes the cost of a candidate solution to the problem instance. The lower the cost, the more optimal the candidate solution.
      Specified by:
      cost in interface OptimizationProblem<BitVector>
      Parameters:
      candidate - The candidate solution to evaluate.
      Returns:
      The cost of the candidate solution. Lower cost means better solution.

    • minCost

      public double minCost()
      Description copied from interface: OptimizationProblem
      A lower bound on the minimum theoretical cost across all possible solutions to the problem instance, where lower cost implies better solution. The default implementation returns Double.NEGATIVE_INFINITY.
      Specified by:
      minCost in interface OptimizationProblem<BitVector>
      Returns:
      A lower bound on the minimum theoretical cost of the problem instance.

    • value

      public double value(BitVector candidate)
      Description copied from interface: OptimizationProblem
      Computes the value of the candidate solution within the usual constraints and interpretation of the problem.
      Specified by:
      value in interface OptimizationProblem<BitVector>
      Parameters:
      candidate - The candidate solution to evaluate.
      Returns:
      The actual optimization value of the candidate solution.

    • isMinCost

      public boolean isMinCost(double cost)
      Description copied from interface: OptimizationProblem
      Checks if a given cost value is equal to the minimum theoretical cost across all possible solutions to the problem instance, where lower cost implies better solution.
      Specified by:
      isMinCost in interface OptimizationProblem<BitVector>
      Parameters:
      cost - The cost to check.
      Returns:
      true if cost is equal to the minimum theoretical cost,