 java.lang.Object

 org.cicirello.search.problems.HollandRoyalRoad

 All Implemented Interfaces:
OptimizationProblem<BitVector>
,Problem<BitVector>
public final class HollandRoyalRoad extends Object implements OptimizationProblem<BitVector>
Implementation of Holland's Royal Road problem, as described in the following paper:
Terry Jones. A Description of Holland's Royal Road Function. Evolutionary Computation 2(4): 409415, 1995.
Originally described by Holland in:
J.H. Holland. Royal Road Functions. Internet Genetic Algorithms Digest, 7(22), 1993.We suggest that the Jones (1995) paper be consulted for a detailed description and detailed example of Holland's Royal Road function.
Note that if you are looking for the original Royal Road problems of Mitchell, Forrest, and Holland, see the
RoyalRoad
class.The problem is defined with several parameters. Part of the fitness function is calculated over k+1 levels, where there are 2^{k} regions in level 0, and each level i has 2^{ki} regions. Each region at level 0 begins with a block of b bits, which is followed by a gap of g bits. Thus each region at level 0 contains b + g bits. Each region of level 1 is the concatenation of 2 consecutive regions from level 0. Likewise, each region of level 2 is the concatenation of 2 consecutive regions from level 1, and so forth, until level k which is simply the entire bit vector.
Fitness evaluation includes two components. The first is referred to as the Part fitness, in which each level 0 region contributes to the fitness of the bit vector. The gap bits of each region are ignored and don't factor into fitness. If all of the bits in the bbit block are all ones, then the region doesn't factor into the Part calculation (only the Bonus calculation). Otherwise, if there are mStar or less one bits in the block, then each contributes v to the fitness, and otherwise if there are more than mStar bits in the block then the excess bits are each penalized in the fitness by b. For example, suppose the block size b=8, mStar=4, and v=0.02. If there is only a single onebit, then the block contributes 0.02 to the fitness. If there are 2 onebits, then the block contributes 0.04 to the fitness. If there are 3 onebits, then the block contributes 0.06 to the fitness. If there are 4 onebits, then the block contributes 0.08 to the fitness. However, if there are 5, 6, or 7 onebits, then the block causes a reduction in fitness. For example, if there are 6 onebits, then the 2 extra (above the mStar of 4) each incur a penalty of 0.02 (total penalty of 0.04). If all 8 bits are ones, no increase nor decrease in fitness occurs during the Part calculation.
The second phase of fitness is called the Bonus calculation. The Bonus calculation is computed over the k+1 levels. The first complete block (all onebits) at level 0 contributes uStar to the fitness, and each additional complete block at level 0 contributes u to the fitness. For example, if there are 5 complete blocks at level 0, and if uStar is 1.0 and u is 0.3, then the level 0 bonus is 1.0 + 4 * 0.3 = 2.2. Level 1 then consists of half as many regions, each region formed by the concatenation of two consecutive regions of level 0. Note that each each at level 1 will consist of b block bits, followed by g gap bits, followed by b block bits, followed by g gap bits. At level 1, a complete block is when the 2b bits in the 2 block segments are all ones. Just like level 0, the first complete block at level 1 contributes uStar to fitness, and then each additional complete block at level 1 contributes u to the fitness. This then proceeds through levels 2, 3, ..., k.
Holland's Royal Road function is a fitness function, and thus must be maximized. Due to the penalty terms in the Part calculation, it can evaluate to negative values. The
value
method computes the fitness function of this problem. Since the metaheuristics of the ChipsnSalsa library assume minimization problems, thecost
method transforms the problem to minimization. It does this by computing cost = MaxFitness  value. MaxFitness can be computed from the parameters of the problem, k, b, g, mStar, v, uStar, and u. So although thevalue
method may return negative values, thecost
method is guaranteed to never return a negative, and the optimal solution to an instance has a cost of 0. Although note that each instance will have many optimal solutions due to the gap bits which do not affect fitness or cost.The
value
andcost
methods will throw exceptions if you attempt to evaluate a BitVector whose length is inconsistent with the parameters passed to the constructor. ThesupportedBitVectorLength
method returns the length of BitVector supported by an instance of the problem, which is 2^{k}(b + g).


Constructor Summary
Constructors Constructor Description HollandRoyalRoad()
Constructs an instance of Holland's Royal Road fitness function, with Holland's original set of default parameter values: k=4, b=8, g=7, mStar=4, v=0.02, uStar=1.0, and u=0.3.HollandRoyalRoad(int k, int blockSize, int gapSize, int mStar, double v, double uStar, double u)
Constructs an instance of Holland's Royal Road fitness function.

Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description double
cost(BitVector candidate)
Computes the cost of a candidate solution to the problem instance.boolean
isMinCost(double 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.double
minCost()
A lower bound on the minimum theoretical cost across all possible solutions to the problem instance, where lower cost implies better solution.int
supportedBitVectorLength()
The length of BitVectors supported by this instance of HollandRoyalRoad, which is 2^{k}(blockSize + gapSize).double
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.OptimizationProblem
getSolutionCostPair




Constructor Detail

HollandRoyalRoad
public HollandRoyalRoad()
Constructs an instance of Holland's Royal Road fitness function, with Holland's original set of default parameter values: k=4, b=8, g=7, mStar=4, v=0.02, uStar=1.0, and u=0.3.

HollandRoyalRoad
public HollandRoyalRoad(int k, int blockSize, int gapSize, int mStar, double v, double uStar, double u)
Constructs an instance of Holland's Royal Road fitness function. Parameters:
k
 The number of level 0 blocks. There will be 2^{k} level 0 blocks (see the references listed in the class comment for relevant definitions). The number of levels in the function is: k + 1.blockSize
 The number of bits in each block. This parameter was originally simply b in Holland's description as well as Jones's more detailed presentation.gapSize
 The number of bits in the gap following each block. This parameter was originally simply g in Holland's description as well as in Jones's more detailed presentation. The gap bits are ignored by the fitness function.mStar
 This is a parameter used in calculating what Holland called the Part fitness (originally named m* by Holland). It is the number of onebits that a block may have before being penalized for having too many ones. The penalty applies to any blocks that have more than mStar ones, but less than blockSize ones.v
 This parameter is also used in calculating Holland's Part fitness. If there are no more than mStar ones in the block, then v is a reward for each onebit in the block. If there are more than mStar ones in the block but less than blockSize, then v is a penalty per onebit in the block. If the block is complete (all onebits), then the Part fitness is 0.uStar
 This parameter is used in calculating Holland's Bonus fitness. At each level, the first completed (all onebits) block (or block set) received a fitness bonus of uStar.u
 This parameter is used in calculating Holland's Bonus fitness. At each level, each completed (all onebits) block (or block set) after the first contributes an additional u to the fitness. Throws:
IllegalArgumentException
 if k < 0 or blockSize < 1 or gapSize < 0 or mStar < 0 or mStar > blockSize or v < 0.0 or uStar < 0.0 or u < 0.0


Method Detail

supportedBitVectorLength
public int supportedBitVectorLength()
The length of BitVectors supported by this instance of HollandRoyalRoad, which is 2^{k}(blockSize + gapSize). Returns:
 the length BitVector supported by this instance of HollandRoyalRoad.

cost
public double cost(BitVector candidate)
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 interfaceOptimizationProblem<BitVector>
 Parameters:
candidate
 The candidate solution to evaluate. Returns:
 The cost of the candidate solution. Lower cost means better solution.
 Throws:
IllegalArgumentException
 if candidate.length() is not equal to 2^{k}(blockSize + gapSize). See thesupportedBitVectorLength()
method.

minCost
public double minCost()
Description copied from interface:OptimizationProblem
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 Double.NEGATIVE_INFINITY. Specified by:
minCost
in interfaceOptimizationProblem<BitVector>
 Returns:
 A lower bound on the minimum theoretical cost of the problem instance.

isMinCost
public boolean isMinCost(double cost)
Description copied from interface:OptimizationProblem
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 interfaceOptimizationProblem<BitVector>
 Parameters:
cost
 The cost to check. Returns:
 true if cost is equal to the minimum theoretical cost,

value
public double value(BitVector candidate)
Computes the value of the candidate solution within the usual constraints and interpretation of the problem. Specified by:
value
in interfaceOptimizationProblem<BitVector>
 Parameters:
candidate
 The candidate solution to evaluate. Returns:
 The actual optimization value of the candidate solution.
 Throws:
IllegalArgumentException
 if candidate.length() is not equal to 2^{k}(blockSize + gapSize). See thesupportedBitVectorLength()
method.

