Package org.cicirello.search.problems

Class 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.

    • Constructor Detail

      • TwoMax

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

    • Method Detail

      • 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,