Module org.cicirello.chips_n_salsa
Package org.cicirello.search.problems

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


 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 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)
    Constructs a RoyalRoad function.

  • Method Summary

    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

    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

      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.