Package org.cicirello.search.problems

Class TwoMaxEqualPeaks

  • All Implemented Interfaces:
    IntegerCostOptimizationProblem<BitVector>, Problem<BitVector>
    public final class TwoMaxEqualPeaks
extends Object
implements IntegerCostOptimizationProblem<BitVector>

    This class implements a variation of the benchmarking problem known as TwoMax. The original TwoMax problem was defined as a problem with one global optima (the vector of all 1-bits) and a sub-optimal local optima (the vector of all 0-bits). For an implementation of the original TwoMax problem, see the TwoMax class. In the variation that we define here, we instead have two equally desirable global optima (one of these is the vector of all 1-bits, and the other is the vector of all 0-bits). We define it as follows. Maximize the function: f(x) = |20*CountOfOneBits(x) - 10*n|, where x is a vector of bits of length n. The two global optimal solutions have a maximal value of 10*n. This search landscape has two basins of attraction, which meet where the vector has an equal number of ones as zeros.

    The value method implements the maximization version 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 - |20*CountOfOneBits(x) - 10*n|. The global optima are still all 1-bits or all 0-bits, each of which has a cost equal to 0.

    • Constructor Summary

      Constructors 
      Constructor Description
      TwoMaxEqualPeaks()
      Constructs a TwoMaxEqualPeaks object for use in evaluating candidate solutions to the TwoMaxEqualPeaks problem, a variation of the TwoMax problem but with two globally optimal solutions, rather than one global optima and a local optima.

    • Constructor Detail

      • TwoMaxEqualPeaks

        public TwoMaxEqualPeaks()
        Constructs a TwoMaxEqualPeaks object for use in evaluating candidate solutions to the TwoMaxEqualPeaks problem, a variation of the TwoMax problem but with two globally optimal solutions, rather than one global optima and a local optima.

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