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

Class TwoMax

java.lang.Object
org.cicirello.search.problems.TwoMax
All Implemented Interfaces:
IntegerCostOptimizationProblem<BitVector>, Problem<BitVector>
public final class TwoMax extends Object implements IntegerCostOptimizationProblem<BitVector>
This class implements the benchmarking problem known as TwoMax. The TwoMax problem is to maximize the following function: f(x) = |18*CountOfOneBits(x) - 8*n|, where x is a vector of bits of length n. The global optimal solution is when x is all ones, which has a maximal value of 10*n. This search landscape also has a local optima when x is all zeros, which has a value of 8*n. Thus, this search landscape has two basins of attraction. The attractions basin for the global optima is larger. As long as x has more than (4/9)n bits equal to a one, a strict hill climber will be pulled into the global optima. However, a search that ends up at the local optima would have a very steep climb to escape.

The value method implements the original maximization version of the TwoMax 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 - |18*CountOfOneBits(x) - 8*n|. The global optima is still all 1-bits, which has a cost equal to 0. The local optima is still all 0-bits, which has a cost equal to 2*n.

The TwoMax problem was introduced by David Ackley in the following paper:
David H. Ackley. A connectionist algorithm for genetic search. Proceedings of the First International Conference on Genetic Algorithms and Their Applications, pages 121-135, July 1985.

  • Constructor Summary

    Constructors
    Constructor
    Description
    TwoMax()
    Constructs a TwoMax object for use in evaluating candidate solutions to the TwoMax problem.

  • Method Summary

    Modifier and Type
    Method
    Description
    int
    cost(BitVector candidate)
    Computes the cost of a candidate solution to the problem instance.
    boolean
    isMinCost(int 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.
    int
    minCost()
    A lower bound on the minimum theoretical cost across all possible solutions to the problem instance, where lower cost implies better solution.
    int
    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.IntegerCostOptimizationProblem

    costAsDouble, getSolutionCostPair

  • Constructor Details

    • TwoMax

      public TwoMax()
      Constructs a TwoMax object for use in evaluating candidate solutions to the TwoMax problem.

  • Method Details

    • cost

      public int cost(BitVector candidate)
      Description copied from interface: IntegerCostOptimizationProblem
      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 IntegerCostOptimizationProblem<BitVector>
      Parameters:
      candidate - The candidate solution to evaluate.
      Returns:
      The cost of the candidate solution. Lower cost means better solution.

    • minCost

      public int minCost()
      Description copied from interface: IntegerCostOptimizationProblem
      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 Integer.MIN_VALUE.
      Specified by:
      minCost in interface IntegerCostOptimizationProblem<BitVector>
      Returns:
      A lower bound on the minimum theoretical cost of the problem instance.

    • value

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

    • isMinCost

      public boolean isMinCost(int cost)
      Description copied from interface: IntegerCostOptimizationProblem
      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 IntegerCostOptimizationProblem<BitVector>
      Parameters:
      cost - The cost to check.
      Returns:
      true if cost is equal to the minimum theoretical cost,