COMPUTER IMPLEMENTATION

The computer code for this investigation is implemented in the “C” language and consists in its current version of about 4,000 lines of code. All experiments were run on a SUN platform running UNIX. All parameters for a run are contained in a parameters file described below.

The initial population is generated by a separate program, randArray, which simply generates a population of arrays of integers within certain bounds. For experiments here, the bounds 0…10 were used.

The principal program operates by reading the initial population from standard input performing the genetic algorithm according the settings in the parameters file (taken as an argument), and writing the final population to the standard output. This design is a standard UNIX approach that permits “chaining” of different variants of the algorithm into an extended algorithm and provides a convenient tool for investigation of time-varying parameters for the program as well.

For each generation, the following steps are performed:

1.  Fitness computation

2.  Tournament selection

3.  Mutation

4.  Crossover

After each step above, the complete population is scanned to see whether any individual has fitness less than the stopping fitness parameter. If so, the genetic algorithm terminates. If not, it continues up to a maximum (parameterized) number of generations.

The Parameters File

The parameters file guides the operation of the genetic algorithm. It contains all problem-specific information as well as all “tuning” parameters. Each of the entries in the parameters file is described here.

Population parameters:

•  nrow - number of rows (resources)

•  ncol - number of columns (services)

•  npop - population size

Random number seed

•  seed - random number seed. “0” is used to request a “current time” based seed.

Stopping parameters

•  stopgen - maximum number of generations to run before stopping the algorithm

•  stopfit - maximum value of “acceptable” fitness. Ideally, this would be “0” but for tightly constrained or overconstrained problems, setting this to a “reasonable” value aids in problem convergence.

Mutation parameters

•  muprob - represents the probability of individual allele mutation.

•  murng - represents the maximum range of mutation value possible. For example, by setting murng=10, a mutation will select a “delta” value uniformly in the range of - 10…+10 and apply it to the allele.

•  mugenlarge - duration (in generations) between “epochal” mutation. Every “muperiodlarge” generations a different set of mutation parameters is put into effect for a single generation.

•  muproblarge - the probability of individual allele mutation during the “epochal” generation. Generally this is larger than muprob.

•  murnglarge - the maximum range of mutation value during the “epochal” generation.

Tournament parameters

•  toursize - number of participants in each tournament.

•  tourwin - number of winners chosen in each tournament.

Fitness Parameters

All fitness parameters here have a default value of “1” unless otherwise specified.

•  rowsum - vector of numbers representing MAXIMUM weighted row sums which can occur without penalty.

•  rowfact - vector of numbers representing multipliers for row penalty values.

•  rowexp - vector of numbers representing exponents applied to row penalty values.

•  colsum - vector of numbers representing MINIMUM weighted column sums which can occur without penalty.

•  colfact - vector of numbers representing multipliers for column penalty values.

•  colexp - vector of numbers representing exponents applied to column penalty values.

•  cost - array of numbers representing unit cost per allele in the chromosome. These are used as multipliers when computing row (resource) penalties.

•  bene - array of numbers representing unit benefits per allele in the chromosome. These are used as multipliers when computing column (service) penalties.

INVESTIGATIONS

The problem examples below are all based on the genetic algorithm formulation above. All examples can be run using the same code formulation with varying values for the problem parameters.

Problem #1: Tight Constraints

The parameters file for this problem is shown here:

   Population                   Fitness
nrow           5             rowsum      25    25   25    25    25
ncol           5             rowfact      1     1    1     1     1
npop         100             rowexp       1     1    1     1     1

   Random Seed               colsum      25    25   25    25    25
seed           0             colfact      1     1    1     1     1
                             colexp       1     1    1     1     1
   Stopping
stopgen      100
stopfit        0

   Mutation
muprob      0.01
murng          5

   Tournament
dotour         1
toursize       5
tourwin        1

   Crossover
xprob        0.2

The best (minimal) fitness for each generation is shown next: