Class RoyalRoad
 java.lang.Object

 org.cicirello.search.problems.RoyalRoad

 All Implemented Interfaces:
IntegerCostOptimizationProblem<BitVector>
,Problem<BitVector>
public final class RoyalRoad extends Object implements IntegerCostOptimizationProblem<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. Thecost
method implements the equivalent as a minimization problem with minimum cost of 0.


Constructor Summary
Constructors Constructor Description RoyalRoad(int blockSize, boolean steppingStones)
Constructs a RoyalRoad function.

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




Constructor Detail

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 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.

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
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.

