 All Implemented Interfaces:
OptimizationProblem<BitVector>
,Problem<BitVector>
This class implements Ackley's Trap function, which defines
a fitness landscape with a single global optima, and a single
suboptimal local optima, such that most of the search landscape
is within the attraction basin of the local optima. Thus, the local
optima is a trap for a local search algorithm.
The Trap function is related to the TwoMax
problem,
but in the TwoMax problem, more of the search space
is within the attraction basin of the global optima than within that
of the local optima.
The Trap problem is to maximize the following fitness function, f(x), where x is a vector of n bits. Let z = floor((3/4)n). If CountOfOneBits(x) ≤ z, then f(x) = (8n/z)(zc). Otherwise, f(x) = (10n/(nz))(cz).
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. Only bit vectors with at least 3/4 of the bits equal to a one are within the attraction basin of the global optima.
The value
method implements the original maximization
version of the Trap problem, as described above. The algorithms
of the ChipsnSalsa 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), where f(x) is the Trap function as defined above.
The global optima
is still all 1bits, which has a cost equal to 0. The local optima
is still all 0bits, which has a cost equal to 2*n.
The Trap problem
was introduced by David Ackley in the following paper:
David H. Ackley. An empirical study of bit vector function optimization. Genetic
Algorithms and Simulated Annealing,
pages 170204, 1987.

Constructor Summary

Method Summary
Modifier and TypeMethodDescriptiondouble
Computes the cost of a candidate solution to the problem instance.boolean
isMinCost
(double 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.double
minCost()
A lower bound on the minimum theoretical cost across all possible solutions to the problem instance, where lower cost implies better solution.double
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.OptimizationProblem
costAsDouble, getSolutionCostPair

Constructor Details

Trap
public Trap()Constructs an instance of Ackley's Trap function.


Method Details

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

minCost
public double minCost()Description copied from interface:OptimizationProblem
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 Double.NEGATIVE_INFINITY. Specified by:
minCost
in interfaceOptimizationProblem<BitVector>
 Returns:
 A lower bound on the minimum theoretical cost of the problem instance.

value
Description copied from interface:OptimizationProblem
Computes the value of the candidate solution within the usual constraints and interpretation of the problem. Specified by:
value
in interfaceOptimizationProblem<BitVector>
 Parameters:
candidate
 The candidate solution to evaluate. Returns:
 The actual optimization value of the candidate solution.

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