RELATED WORK

The optimization problem considered here has some aspects in common with other problems which have been studied:

•  A potentially large number of constraints. For the simplified problem discussed here, the complexity of the constraints will be minimized but in the “real world” there are diverse constraints.

•  Multiple objectives for the optimization.

The Web-based Genetic Algorithms Digest [2] is helpful as a forum for an informal exchange of ideas and was consulted for this project.

Michalewicz [3] is an excellent book that describes many genetic algorithm issues and problems. Chapter 9 suggests a representation for the transportation problem (quite similar to the problem of this project) which uses a special initialization algorithm (p.145) and a permutation technique which works quite well for the current problem.

Cox et al. [4] consider the problem of designing dynamic routing in communications networks. This work is applicable to the current project in that similar constraint (meeting service needs without using excessive resources) considerations exist. Also, since the problem is to find a dynamic solution, it starts from a given routing and looks for improvements as call traffic fluctuates.

Davis and Coombs [5] apply genetic algorithms with some interesting approaches to constraints. They developed Stochastic constraints (things are “OK” if the constraint is satisfied “most of the time,” defined in the paper), Ice Age constraints (constraints are only applied during “Ice Ages,” i.e., rarely, instead of every generation), and “LaMarck Operators” which handle constraints by fixing them up occasionally. They also applied Object-Oriented programming techniques to genetic algorithms for handling constraints. Their approach to “Ice Age” constraints was used in one of the investigations of this project.

Surry and Radcliffe [6] treat multiple constraints as a Pareto optimization problem, with satisfaction of each constraint taken as another objective function. A special method is developed: COMOGA (Constrained Optimization by Multi-Objective Genetic Algorithms). This entails the calculation of constraint violations, Pareto ranking, fitness evaluation, and selection. The selection operation “compromises” between picking the “best” members (based on fitness) and the “best” members based on constraint satisfaction. The approach for this investigation uses a variation of the Pareto approach for tournament ranking as discussed in the Investigations section below.

Michalewicz [7] is a survey article that outlines many of the popular methods of dealing with constraints. One interesting method, useful in dealing with convex problems, is to avoid constraint violation by considering crossover as a linear combination of (feasible) individuals.

GENETIC ALGORITHM MODEL

Genetic Algorithm Approach for this Problem

The strategy employed here is based on a genetic algorithm approach as described in Goldberg [1] with certain variations. The remainder of this chapter assumes familiarity with the concepts and terminology of genetic algorithms as presented in Goldberg [1]. This section describes the formulation of the chromosomes, the methods of selection, reproduction, mutation, and the fitness functions.

Problem Size

For this approach to be useful commercially, it should be successful on problems using up to 100 resources and 100 services. Here, only small to medium size problems are considered, with up to 10 resources and 10 services.

Chromosome Formulation

Chromosomes are a two-dimensional matrix P (for “provisioning”). The rows of P are the resource pools to be used. The columns of P are the services to be provisioned. P(r,s) represents the amount of service “s” provided through resource “r”. The length of the chromosome is |R| × |S|. Thus, a typical chromosome might be:

( 5 2 0 0 0 3 7 8 1 9 4 2 2 3 0 1 6 8 4 4 3 )

representing the following provisioning:

Allele Formulation

The entries in the chromosomes are taken here to be small integers. As discussed below, alleles will be preserved under crossover.

The approach taken here is a compromise between the traditional genetic algorithm approach and a linear programming approach. Traditionally, a genetic algorithm would encode data into a binary (or small cardinality) alphabet string using discretization of the solution space. This makes the search space more manageable but also requires early commitment to a specific set of possible solutions which is overly restrictive in the current problem domain.

In contrast, a linear programming approach would generally use floating point operations to find a solution (if one exists, if all constraints are linear, etc.) to a high level of precision. This level of precision is unwarranted here, both due to the “softness” of the constraints mentioned above and due to the fact that a provisioning of services is ultimately carried out by people making commitments of resources to provide services. For example, six channels might be committed to service A, but not 6.037429 channels, even though the latter solution might be more optimal in a mathematical sense.