Industrial Applications of Genetic Algorithms:Genetic Algorithms for Constrained Service Provisioning

Previous | Table of Contents | Next

Problem #3: Alternate Values

This experiment is designed to investigate the “real world” problem of simultaneously meeting multiple objectives. Consider the utilization of resources as an objective autonomous system with two observers. Each observer independently places weights on the utilization of resources and the values of services provided. The objective of the genetic algorithm is to find a “Provisioning” which satisfies both observers. The experiment is as in Problem #2 above, with two separate sets of weights leading to two separate fitness values. In the parameters file below, these sets are labeled “Primary” and “Alternate.”

The parameters file for this problem is shown on the following page:

                             Parameters File

       Population                            Primary Fitness
    nrow            5         rowsum      76   76   76   76   76
    ncol            5         rowfact      1    1    1    1    1
    npop          100         rowexp       1    1    1    1    1

       Random Seed            colsum      74   74   74   74   74
    seed            0         colfact      1    1    1    1    1
                              colexp       1    1    1    1    1
       Stopping
    stopgen      1000              Cost
    stopfit         0                      1    2    3    4    5
    stopfitalt      0                      1    2    3    4    5
                                           1    2    3    4    5
       Mutation                            1    2    3    4    5
    muprob       0.05                      1    2    3    4    5
    murng           5                      1    2    3    4    5
    mugenlarge     20
    muproblarge   0.2              Benefit
    murnglarge      2                      1    1    1    1    1
       Tournament                          3    3    3    3    3
    dotour          1                      4    4    4    4    4
    toursize        3                      5    5    5    5    5
    tourwin         1

       Crossover                          Alternate Fitness
    xprob        0.2          rowsumalt   76   76   76   76   76
                              rowfactalt   1    1    1    1    1
                              rowexpalt    1    1    1    1    1

                              colsumalt   74   74   74   74   74
                              colfactalt   1    1    1    1    1
                              colexplat    1    1    1    1    1

                                   Cost(alt)
                                           5    4    3    2    1
                                           5    4    3    2    1
                                           5    4    3    2    1
                                           5    4    3    2    1
                                           5    4    3    2    1
                                           5    4    3    2    1

                                  Benefit(alt)
                                           5    5    5    5    5
                                           4    4    4    4    4
                                           3    3    3    3    3
                                           2    2    2    2    2
                                           1    1    1    1    1

The following chart shows the best fitness for each generation.

This sample shows that the algorithm is “trying” to keep both fitnesses minimized simultaneously.

In order to investigate this problem, an alternate implementation was developed. It was based on the original implementation but with fitness parameters and values existing in both primary and alternate form. This required a special stopping criteria and a special decision process to be performed for tournament selection.

The stopping criteria were simply extended: the genetic algorithm is permitted to stop only when both fitness criteria are met (primary and alternate), or when the maximum number of generations has been run.

The tournament selection method was more problematic. Several approaches were investigated here. The one finally adopted is as follows. Let the fitness penalties using the different weightings be P and Q. Then the combined fitness penalty is:

The concept behind this formulation of “total” penalty is designed so that both of the “observers” will not be overly “unhappy.” To see how this works, consider two example scenarios:

  1. Scenario #1: P = 2, Q = 10. In addition to P being “happy” with the fitness and Q being “unhappy” with the fitness, in “real life,” Q would probably also be “unhappy” about the “unfairness” of the solution. (Q: Why should P be happier than I?) So the total penalty of 2 + 10 + 10 = 22 is assessed.
  2. Scenario #2: P = 5, Q = 8. Here P is less “happy” and Q is more “happy” but, since the unhappiness is “shared,” there is less total unhappiness. So the total penalty of 5 + 8 + 8 = 21 is assessed.

Irrespective of the “pop psychology” explanation, using the method outlined here leads to a solution that is able to minimize both fitness penalties simultaneously.

The solution found by the genetic algorithm is shown here:

| Svc #1 | Svc #2 | Svc #3 | Svc #4 | Svc #5
--- | --- | --- | --- | --- | ---
Res #1 | 3 | 6 | 6 | 8 | 2
Res #2 | 6 | 6 | 3 | 2 | 8
Res #3 | 7 | 3 | 6 | 1 | 8
Res #4 | 7 | 1 | 5 | 9 | 3
Res #5 | 2 | 9 | 5 | 5 | 4

Previous | Table of Contents | Next

Copyright © CRC Press LLC