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