Discussion for Problem #1

This problem is small (five resources, five services) and simple (all resources and services are interchangeable). The interesting part is that the sum of the resource constraints is equal to the sum of the service constraints. Since the resource constraints are maxima and the service constraints are minima, equality of their sum means that, for a zero penalty solution, all constraints must be met exactly. Since the number of constraints (10: one for each row, one for each column) is far less than the number of variables (25 alleles per chromosome), this problem is, in general, solvable. However, the solution space can be thought of as a “thin” (15-dimensional) hyperplane in 25-dimensional space. This is actually a rather small “target” for the genetic algorithm to hit!

The genetic algorithm was able to find a zero penalty solution in 64 generations. The solution found is shown here:

This problem turns out to be “easy” for the genetic algorithm. It was performed as a feasibility test for the general approach described in this chapter.

Problem #2: Unequal Resources and Services

The parameters file for this problem are shown here:

                         Parameters File

   Population                Fitness
nrow            6         rowsum      30   30   30   30   30   30
ncol            6         rowfact      1    1    1    1    1    1
npop          100         rowexp       1    1    1    1    1    1

   Random Seed            colsum      60   60   60   60   60   60
seed            0         colfact      1    1    1    1    1    1
                          colexp       1    1    1    1    1    1

   Stopping
stopgen      2000              Cost
stopfit         0                      1    1    1    2    2    2
                                       1    1    1    2    2    2
   Mutation                            1    1    1    2    2    2
muprob       0.01                      2    2    2    1    1    1
murng           5                      2    2    2    1    1    1
mugenlarge     10                      2    2    2    1    1    1
muproblarge   0.2
murnglarge      2              Beneft
                                       1    1    1    1    1    1
   Tournament                          2    2    2    2    2    2
dotour          1                      3    3    3    3    3    3
toursize        3                      3    3    3    3    3    3
tourwin         1                      2    2    2    2    2    2
                                       1    1    1    1    1    1
   Crossover
xprob        0.2

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

Discussion for Problem #2

The problem size is almost the same as for Problem #1 (six resources and six services) but, in this problem, it is much more difficult to “see ”a solution by inspection. The genetic algorithm quickly comes near to a solution after about 300 generations (penalty 10) and thereafter, does not find further improvement.

This problem was “rigged” so that both the cost and benefits matrices (shown above) have unequal entries. Examining the cost array for resources, we see that resources #1 … #3 are more efficient for providing services #1 … #3. Similarly, resources #4 … #6 are more efficient for providing services #4 … #6.

The bene (benefits) array is also biased. Services #3 and #4 provide the most benefit per unit of resource with other services diminishing in value per resource used. Putting this together, it makes most sense (to a person!) to provide most of services #1 … #3, with resource #3 and most of services #4 … #6 with resource #4.

The solution found by the genetic algorithm is shown here:

The genetic algorithm has approximately duplicated the “experienced provisioners” solution. This solution is not “ideal” (zero penalty) but there is no obvious (to this author!) way to improve the solution.