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

Previous | Table of Contents | Next

Problem Abstraction

In order to simplify the problem, the following abstraction is used. Let there be given entities of the following types:

  • Resources: Res = { R(1), R(2), … }
  • Services: Svc = { S(1), S(2), … }

A “provisioning” is specified by a function P(r,s). P(r,s) is a real-valued function with domain the Cartesian product: Res x Svc. P(r,s) measures the amount of service “s” to be provided using resource “r”.

In graph theory terms, the problem can be represented using a bi-partite graph:

where there are edges between resources and services. The “provisioning” is an “edge-labeling” using real-valued labels.

An interesting aspect of this problem is the duality between constraints and objectives. In one view, the problem is to minimize the “cost” (resources) needed to provide a given level of service. This view regards the services as providing fixed constraints with the objective function being a measure of the resources used to provide that service.

A complementary viewpoint is to maximize the “service” (strongly correlated with profit hopefully!) which can be provided using a fixed set of resources (cost). In this view, the resources are the fixed constraints and the objective function is a measure of the level of service provided using those resources.

The abstraction investigated here has some interesting properties:

  1. Traditional approaches to this problem (e.g., using linear programming) must commit to one view or the other up front. (i.e., “fixed cost with maximum service” or “fixed service with minimum cost”). This “premature commitment” decreases the utility of the computation. The approach here, using a genetic algorithm, allows complete flexibility by weighing the penalty for NOT achieving each “requirement” separately. As an example, suppose three services, S1, S2, S3 are to be provisioned using two resources R1, R2. Parameters of the genetic algorithm can be adjusted to give S1 and R2 (say) quadratic penalty functions and the other services and resources only linear penalty functions. The effect of this is to say “the solution MUST meet service constraints for S1 and resource constraints for R2 and it’s DESIRABLE to meet the other service and resource constraints.”
  2. Measurement of resource utilization as well as the level of service provided are often “soft.” For example, level of service might include some “customer satisfaction” data gained from a survey. Traditional approaches (e.g., linear programming) do not handle “soft” data well. Our genetic algorithms approach deals (roughly) equally well with underconstrained, tightly constrained, or overconstrained problems. As discussed in the Investigations section below, the genetic algorithm did not always find the optimal solution but did always find a “reasonable” solution. In contrast, linear programming approaches (when all constraints are linear) do well to find feasible and optimal solutions when they exist, but, in general cannot handle overconstrained problems (which often occur in the “real world”).
  3. For a given provisioning, there may be several ways to measure the cost and the service provided. As mentioned above, “service isolation” is a worthwhile goal. “Resource sharing” is another worthwhile goal but generally diminishes service isolation. It is useful to have a model which can take multiple objectives into account. A similar statement can be made about the measurement of resource costs. This is implemented in a business setting by having a proposal reviewed by multiple people or departments. The final plan is generally a compromise between various views. A variation of the basic genetic algorithm was implemented to model this business decision process. Both a “primary” and “alternate” set of constraints were presented. The genetic algorithm was designed to find solutions that are “reasonable” solutions to each set of constraints simultaneously.

Summary

A genetic algorithm approach to an abstraction of the “Provisioning Problem” as described above has been found to be useful. A review of some related work is given in the next section. The actual genetic algorithm formulation of the problem is discussed in the third section. Some detail on the computer implementation is then provided, and results of four different types of problems investigated are provided.

Previous | Table of Contents | Next

Copyright © CRC Press LLC