Class Porcupine
- java.lang.Object
-
- org.cicirello.search.problems.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. Thecost
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.
-
Method Summary
All Methods Instance Methods Concrete Methods 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
getSolutionCostPair
-
-
-
-
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 interfaceIntegerCostOptimizationProblem<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 interfaceIntegerCostOptimizationProblem<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 interfaceIntegerCostOptimizationProblem<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 interfaceIntegerCostOptimizationProblem<BitVector>
- Parameters:
cost
- The cost to check.- Returns:
- true if cost is equal to the minimum theoretical cost,
-
-