 All Implemented Interfaces:
IntegerCostOptimizationProblem<BitVector>
,Problem<BitVector>
Implementation of the Royal Road problem of Mitchell, Forrest, and Holland,
both the variation with stepping stones and the one without. The problem was
introduced in the paper:
M. Mitchell, S. Forrest, and J.H. Holland. The Royal Road for Genetic Algorithms:
Fitness Landscapes and GA Performance. In Proceedings of the First European
Conference on Artificial Life, 1992.
Note that if you are looking for Holland's Royal Road problem,
see the HollandRoyalRoad
class.
Mitchell et al. described two versions of the problem. The first is an optimization problem over bit strings of length 64. The fitness function to optimize in the problem breaks the bit string into 8 equal length blocks of length 8. Each block that contains all ones contributes 8 to the fitness of the bit string. And if the bit string itself is all ones, then this contributes an additional 64 to the fitness. The maximum fitness is thus 128 (when all of the bits are ones).
In the second variation of the problem, Mitchell et al. added additional stepping stones to the fitness function. The fitness function includes the above (scores for 8bit blocks of all ones, and a full string of all ones). Additionally, each of the four 16bit quarters contribute 16 to the fitness if it is all ones, and each of the two 32bit halves contribute 32 to the fitness if it is all ones. Thus, the maximum fitness in this case is 256 (when all of the bits are ones).
In our implementation, we generalize the original problem to bit vectors of any length and for different block sizes. The following code block evaluates a random BitVector using the equivalent of Mitchell et al's original RoyalRoad fitness function (without stepping stones):
RoyalRoad problem = new RoyalRoad(8, false);
BitVector b = new BitVector(64, true);
int fitness = problem.value(b);
The following code block evaluates a random BitVector using the equivalent of Mitchell et al's original RoyalRoad fitness function (with stepping stones):
RoyalRoad problem = new RoyalRoad(8, true);
BitVector b = new BitVector(64, true);
int fitness = problem.value(b);
In our generalization, without stepping stones, the maximum fitness (i.e., the maximum
that can be returned by the value
method) is 2*n where n is the
length of the BitVector. With stepping stones, the maximum fitness varies based on
the initial block size. The algorithms
of the ChipsnSalsa library are defined for minimization, requiring
a cost function. The cost
method implements the equivalent
as a minimization problem with minimum cost of 0.

Constructor Summary
ConstructorDescriptionRoyalRoad
(int blockSize, boolean steppingStones) Constructs a RoyalRoad function. 
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

RoyalRoad
public RoyalRoad(int blockSize, boolean steppingStones) Constructs a RoyalRoad function. Parameters:
blockSize
 The size of the blocks, which must be positive.steppingStones
 If true, the version of the problem with stepping stones will be constructed. Throws:
IllegalArgumentException
 if blockSize < 1.


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.

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,

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.
