Genetic algorithms (GA's) provide an ideal framework for the parallel solution of discrete optimization problems in which the computation of the fitness function requires significant effort. In the case of large-scale optimization we can expect that evaluating the objective function will provide this kind of coarse granularity. On the other hand, GA research has often focused on small yet hard combinatorial problems for which fitness may be evaluated very rapidly. This presentation will consider a high-level GA approach in which the variables used by the GA correspond to indices of subproblem solutions. The computation of the fitness of an individual in this framework involves the "coordination" of subproblem solutions to create a feasible solution for the original problem. (It can also include a local search started at this feasible solution.) Morevoer, the GA paradigm performs many of these coordination steps in parallel, and hence may be considered as a "multi-coordination" approach. This research is motivated by the observation that many important classes of large-scale optimization problems have a block structure, that is, they may be expressed in terms of groups of constraints and variables linked together by so-called "coupling constraints". When coupling constraints are removed by an approximation such as a Lagrangean relaxation, the resulting relaxed problem may be solved by separately optimizing (or approximately optimizing) subproblems in which each group of variables is subject to its own block of constraints.

Our research has focused on the use of genetic algorithms as multi-coordinators in block-structured discrete optimization problems. In particular, we have applied this approach to the solution of very large graph partitioning problems, utilizing a network of workstations. Computational results for p-way graph equi-partition problems of more than a billion variables are presented to demonstrate that by utilizing these building blocks, an ``island" GA, which performs GA's in parallel, can substantially outperform all conventional approaches for this problem class. Extensions of this multi-coordination GA approach to other classes of non-convex network optimization problems are also considered.

Back to Workshop Schedule

1996-1997 Mathematics in High Performance Computing