Problem #4: Service Isolation

As discussed above, there are a wide variety of issues which must be considered by the service provisioner. Maximizing service benefits and minimizing resource costs are generally important. However, other issues are also important. Here we consider the problem of service isolation.

In order to model this problem using a genetic algorithm, a modification to the fitness function was made. In addition to the row and column penalties assessed as described above, an additional section was added to the parameters file as the following shows.

                        Parameters File
   Population                         Fitness
nrow           10      rowsum     55  55  55  55  55  55  55  55  55  55
ncol           10      rowfact    10  10  10  10  10  10  10  10  10  10
npop          100      rowexp      1   1   1   1   1   1   1   1   1   1

   Random Seed         colsum     50  50  50  40  40  40  40  40  40  40
seed            0      colfact    50  50  50  10  10  10  10  10  10  10
                       colexp      1   1   1   1   1   1   1   1   1   1
   Stopping
stopgen      4000       Isolation Factor
stopfit         0                  1   1   1   1   1   1   1   1   1   1
stopfitalt      0                  1   1   1   1   1   1   1   1   1   1
   Mutation                        1   1   1   1   1   1   1   1   1   1
muprob       0.05                  0   0   0   0   0   0   0   0   0   0
murng           5                  0   0   0   0   0   0   0   0   0   0
mugenlarge     20                  0   0   0   0   0   0   0   0   0   0
muproblarge   0.2                  0   0   0   0   0   0   0   0   0   0
murnglarge      2                  0   0   0   0   0   0   0   0   0   0
   Tournament                      0   0   0   0   0   0   0   0   0   0
dotour          1
toursize        3
tourwin         1
   Crossover
xprob         0.2

Here, an array, isofact, captures the inter-service isolation factors desired. These factors act as multipliers and are applied whenever two services share a common resource. For the example shown, all factors are “1” for Services #1 .. #3 and “0” otherwise. This causes a penalty to be assessed whenever any of these services share resources with any other services.

This problem is studied here both because it is an important “real world” constraint, and because it adds an interesting epistasis to the problem domain. In addition to “competing” for resources, certain (high priority) services are forced to be separated from each other.

This example took 1,288 generations to arrive a zero penalty solution, shown here.

The solution found by the genetic algorithm shows that the isolation strategy has been achieved: Service #1 uses only Resource #7, Service #2 uses only Resource #10, and Service #3 uses only Resource #9.

CONCLUSION

A genetic algorithm approach to an industrial decision problem, resource provisioning, has been considered. A flexibly parametrized program has been developed to investigate the problem for small-to-medium size examples. The genetic algorithm approach is shown to be feasible and matches human intuition for small examples. The genetic algorithm always found a reasonable solution in a reasonable number of generations. It did not always find an optimal solution in problems where an optimal solution was known to exist.

The algorithm was applied in two basic cases. Two different extensions of the algorithm were also studied. One extension showed that simultaneously considering multiple cost and benefit factors is feasible within the same problem approach. A separate extension showed that adding a highly non-linear component to the fitness (penalty) function could also be handled easily within the same framework.

REFERENCES

1  Goldberg, D. (1989). Genetic algorithms in search, optimization and machine learning. Reading, MA: Addison-Wesley.

2  Genetic Algorithms Digest: http://www.aic.nrl.navy.mil/galist.

3  Michalewicz, Z. (1992). Genetic algorithms + data structures = evolution Programs. New York: Springer-Verlag.

4  Cox, L.A., Davis, L., Qiu, Y. (1991). Dynamic anticipatory routing in circuit-switched telecommunications networks. In Davis, L. (Ed.), Handbook of genetic algorithms.

5  Davis, L., Coombs, S. (1987). Genetic algorithms and communication link speech design: Theoretical considerations, constraints and operators. In Genetic Algorithms and Their Applications, Proceedings of the Second International Conference on Genetic Algorithms, Cambridge, MA: MIT Press.

6  Surry, P., Radcliffe, N. (1995). A Multi-objective approach to constrained optimization of gas supply networks: The COMOGA method. In Fogarty, T. (Ed.), AISB-EC-95.

7  Michalewicz, Z. (1995). A survey of constraint handling techniques in evolutionary computation methods. In McDonnell, J., Reynolds, R., Fogel, D. (Ed.) Evolutionary Programming IV, Cambridge, MA: MIT Press.