Module org.cicirello.chips_n_salsa

Package org.cicirello.search.problems

Class HollandRoyalRoad

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): 409-415, 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^k-i 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 b-bit 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 one-bit, then the block contributes 0.02 to the fitness. If there are 2 one-bits, then the block contributes 0.04 to the fitness. If there are 3 one-bits, then the block contributes 0.06 to the fitness. If there are 4 one-bits, then the block contributes 0.08 to the fitness. However, if there are 5, 6, or 7 one-bits, then the block causes a reduction in fitness. For example, if there are 6 one-bits, 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 one-bits) 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 Chips-n-Salsa library assume minimization problems, the cost 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 the value method may return negative values, the cost 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 and cost methods will throw exceptions if you attempt to evaluate a BitVector whose length is inconsistent with the parameters passed to the constructor. The supportedBitVectorLength 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

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 2k(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

costAsDouble, getSolutionCostPair

Constructor Details

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 one-bits 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 one-bit in the block. If there are more than mStar ones in the block but less than blockSize, then v is a penalty per one-bit in the block. If the block is complete (all one-bits), then the Part fitness is 0.

uStar - This parameter is used in calculating Holland's Bonus fitness. At each level, the first completed (all one-bits) 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 one-bits) 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 Details

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 interface OptimizationProblem<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 the supportedBitVectorLength() 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 interface OptimizationProblem<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 interface OptimizationProblem<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 interface OptimizationProblem<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 the supportedBitVectorLength() method.