java.lang.Object
org.cicirello.search.problems.TwoMax
 All Implemented Interfaces:
IntegerCostOptimizationProblem<BitVector>
,Problem<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 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  18*CountOfOneBits(x)  8*n.
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 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 121135, July 1985.

Constructor Summary
ConstructorDescriptionTwoMax()
Constructs a TwoMax object for use in evaluating candidate solutions to the TwoMax problem. 
Method Summary
Modifier and TypeMethodDescriptionint
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
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
costAsDouble, getSolutionCostPair

Constructor Details

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


Method Details

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