• 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 8-bit blocks of all ones, and a full string of all ones). Additionally, each of the four 16-bit quarters contribute 16 to the fitness if it is all ones, and each of the two 32-bit 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):

``````
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):

``````
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 Chips-n-Salsa 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

Constructors
Constructor Description
```RoyalRoad​(int blockSize, boolean steppingStones)```
• ### Method Summary

All 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

```public RoyalRoad​(int blockSize,
boolean steppingStones)```
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 interface `IntegerCostOptimizationProblem<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 interface `IntegerCostOptimizationProblem<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 interface `IntegerCostOptimizationProblem<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 interface `IntegerCostOptimizationProblem<BitVector>`
Parameters:
`candidate` - The candidate solution to evaluate.
Returns:
The actual optimization value of the candidate solution.