Package org.cicirello.search.problems

Class Porcupine

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

    This class implements the Porcupine landscape (Ackley, 1985), which is a very rugged search landscape, with an exponential number of local optima. The Porcupine problem is a maximization problem to maximize the function: f(x) = 10 * CountOfOneBits(x) - 15 * (CountOfZeroBits(x) mod 2), 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.

    The value method implements the original maximization version of the Porcupine 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). The global optima is still all 1-bits, which has a cost equal to 0.

    The Porcupine 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
      Porcupine()
      Constructs a Porcupine object for use in evaluating candidate solutions to the Porcupine problem.

    • Constructor Detail

      • Porcupine

        public Porcupine()
        Constructs a Porcupine object for use in evaluating candidate solutions to the Porcupine 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,