Mutation

Mutation of an allele will take place using a “centered” mutation algorithm. Treating each allele as a non-negative integer, a mutation will increment or decrement that integer by a small amount, chosen uniformly over an interval. The length of this interval and the probability of mutation are parameters that can be adjusted. Mutations will always produce non-negative integer values alleles. That is, a mutation which produces a negative value will be adjusted to be “0”. Mutations are not explicitly constrained from growing “too large” but chromosomes with high values will generally have high penalties associated with them. Thus, the problem space is effectively limited to a compact domain.

Crossover

For this problem, crossover is done in a slightly“non-standard”manner. This is dictated by the fact that a chromosome represents a two-dimensional structure, and the crossover method should reflect that structure. The approach here is“quadrantal”(See Figure 6.1).

Figure 6.1  Quadrantal crossover method.

Crossover is implemented by choosing a crossing point in the resource list and a crossing point in the services list. The two parent chromosomes are then “crossed,” creating two children chromosomes by using the quadrants from each parent. The method used here is, for each quadrant, one child, chosen at random, receives one parent’s version, the other child receives the other parent’s version. This decision can be visualized by considering the following example table:

In this example, Child #1 has quadrants A,B,C,D from Parents #1, #2, #2, #1, respectively. Child #2 has quadrants A,B,C,D from Parents #2, #1, #1, #2, respectively. For each crossover operation, the assignment of parent quadrants to children is determined randomly. This approach has the advantage that all genetic material from both parents is preserved in some offspring.

Discussion of Crossover Strategy

Several methods of crossover were considered in this study before the current approach was adopted. One method, creating a single child offspring by taking the best combination of quadrants from each parent, was successful for small problems but tended toward premature convergence with valuable genetic material lost. Another approach with a fixed allocation of parents’ quadrants to offspring preserved genetic material but tended to “lock” large areas together, which then led to insufficient mixing of the population. The current strategy seems to combine a good “mixing ”approach with no loss of genetic material.

Fitness Parameters and Fitness Functions

A fitness value must be given to a chromosome in order to implement the selection process and, finally, to determine whether the genetic algorithm has arrived at a good solution. Generally, the objective is to minimize resource usage while maximizing service availability. This is modeled here by assigning the following parameters:

1.  Unit cost parameter for each allele locus that measures the unit cost of providing service (s) using resource (r).

2.  Unit benefit parameter for each allele locus that measures the unit benefit of providing service (s) using resource (r).

3.  Resource limits are parameters that reflect the limited availability for each resource. Fitness will incur a penalty when the weighted row sum of the chromosome values exceeds the resource limit.

4.  Benefit limits are parameters that reflect the minimum limits of service that should be provided. Fitness will incur a penalty when the weighted column sum of the chromosome values is less than the associated benefit limit.

The chromosome fitness value is the sum of the row and column penalties. Two further parameters are available for row and column fitness evaluation:

1.  Fitness multipliers are used for both rows and columns. These multipliers are needed because the measurement of resource cost and service benefit may be in different units or have different priorities. Use of multipliers allows a weighted sum of these two penalties to be computed.

2.  Fitness exponents are used for both rows and columns. Each row or column penalty may be raised to an exponent (generally 1 or 2) before being combined with other penalties. The introduction of a non-linearity in the penalty function provides a mechanism for enforcing a hard limit (minimum or maximum). For the investigations here, using exponent “2” is the “hard” limit, and using exponent “1” is the “soft” limit. The type of limit for each resource and service level can be set independently.

Selection

Since the approach here uses (positive) penalty functions, the selection criteria uses minimization. Thus, a tournament selection method is appropriate and is used here. The number of participants in each tournament and the number of winners in each tournament are problem instance parameters. For example, tournaments could be set up with five “contestants” selected at random from the population. Then each tournament could designate as “winners” the two contestants with lowest fitness (first place and second place). The numbers “five” and “two” in the example above can be varied in the implementation.

An interesting side effect of this strategy is that the absolute size of the fitness (penalty) of each chromosome is not relevant, only its relative value compared to other chromosomes. This approach may more accurately reflect the uncertainty of the fitness data in real problems.

A variation of this is used in the “multi-objective” experiment #4 described below.