|
SSP Project Summary:
|
 |
Domain Decomposition using Parallel Genetic Algorithms
Introduction
Domain decomposition is a general term for the process of taking a
large set of small connected regions and grouping them together into a
smaller number of large zones. All decompositions have to satisfy
certain hard constraints, but typically we are actually looking for
the "best" decomposition among the huge number of possible solutions.
A simple way to quantify the quality of a solution is to assign a
score to each decomposition based on the value of some fitness
function. If we take the convention of assigning low scores to good
solutions, it is apparent that domain decomposition can be viewed as a
constrained function minimisation problem.
Examples
In a practical example the task might be to take a map of the UK
divided into tens of thousands of electoral wards and decide on the
boundaries for the 651 parliamentary constituencies. The constraints
are that every ward belongs to a unique constituency and that all
wards in a given constituency are physically connected. The
optimisation function could be chosen to favour solutions where all
constituencies are of roughly equal size (in terms of population).
Another example comes from parallel computing. When decomposing a
calculation onto a parallel machine, we want to assign different parts
of the problem to particular processors in a manner that minimises the
computational overheads due to load balancing and communication. The
fitness function would assign weights to these two factors based on
the communication to calculation ratio of the target machine.
Genetic Algorithms
Genetic algorithms are a powerful modern technique for performing
general function minimisation using ideas borrowed from biological
evolution in the real world. Each solution is represented by a gene,
and at any one time we have a large gene pool comprising many
candidate solutions of varying fitness. Genes reproduce according to
their fitness, and hopefully good solutions will survive and multiply,
and eventually come to dominate the population. An element of random
mutation is also incorporated to maintain diversity in the gene pool.
Representations
A crucial question is how to encode a particular solution into a gene.
A naive choice would be to represent a decomposition of N regions into
M zones as an array of N integers, one for each region, containing
integer values from 1...M denoting the zone to which it belongs.
This, however, suffers from many problems. Three major concerns are:
a single solution can be represented by many distinct genes
(degeneracy); most genes do not represent valid solutions and
therefore it is extremely hard to breed parent genes in a manner
guaranteed to produce valid child solutions without destroying
potentially valuable information; for large problems the genes become
huge and unwieldy to manipulate.
A solution to all these problems is to view the GA as simply optimising
the input parameters to a deterministic domain decomposition algorithm.
A straightforward choice would be to implement some greedy algorithm
that simply grows valid decompositions from an input list of M seed
regions. A gene therefore comprises a list of M integers each in the
range 1...N which specify the seed-points. Now almost all genes
represent legal solutions, the only constraint being that all M seeds
must be distinct. This makes the breeding and mutation operations
much more straightforward.
Goals
The student will need to do the following
- Write a simple greedy algorithm that is guaranteed to produce legal
solutions given a valid list of seeds
- Spend a small amount of time tuning the above to ensure solutions
have reasonably good fitnesses (e.g. by simple local optimisations)
- Write a plan in RPL2 to evolve the gene pool
- Produce a library of suitable genetic operators (RPL2 probably
already contains all that is needed)
- Interface RPL2 to the optimisation algorithm
- Investigate the performance of serial and parallel GA's
- (Optional) visualise the solutions
RPL2 has a large amount of built-in support for parallelism, so the
major task will be to write the serial code.
Further Work
If the above goals are achieved, there are many possibilities for
further investigation. I have listed two suggestions below. The
first is perhaps more applicable to the problem of zone design in
geography where the fitness function can be extremely complicated and
non-local. The second is concerned explicitly with domain
decomposition for parallel codes.
Set Representations
It would be interesting to investigate the problem of degeneracy in
the genes. Since the genes are simply lists of seed zones, a large
number of different genes can represent the same collection of seeds.
The only difference is the order in which they appear. It might be
possible to significantly reduce the degeneracy by using a Set
Representation. In this representation the order is irrelevant,
so each set of seed points corresponds to one and only one gene. RPL2
already has support for set representations. However, to assign a
unique fitness value to a gene we must implement a greedy algorithm
that is itself insensitive to the order of the seed points. A simple
solution might be always to sort the seed zones into ascending
numerical order. Perhaps a better approach would be to alter the
greedy algorithm itself.
It is perfectly possible, however, that the restrictions placed on the
greedy algorithm by the use of a set representation severely restrict
the range of solutions that are explored. It might prove more efficient
to take advantage of the degeneracy by employiong a greedy algorithm that is
positively designed to be sensitive to the order of seeds. A simple
example would be to take each seed point in turn and grow it until it
exceeds some maximum size before going on to the next seed.
Which of these two approaches is better will depend on the problem. If
the optimal zoning is very regular, one might expect the first approach
to be better. However, if the best solution is highly irregular
containing regions of widely varying size and shape, the second approach
might prove more successful.
Performance Optimisation of Parallel Codes
Several large codes that run on the T3D are Finite Element codes which
have very irregular meshes. The performance of these codes is
sensitive to the assignment of elements to processors, and unlike
regular meshes there is no immediate obvious choice. It would be
extremely interesting to see whether the GA developed in this project
was able to speed up a real code by choosing a better domain
decomposition than currently used. If the application were portable
to other parallel platforms, it would also be possible to study the
effect to which the optimal zoning is affected by the performance
characteristics of the target machine.
Expertise
I do not think that an enormous amount of background knowledge is
required. A small amount of C expertise is needed to link RPL2 with
user codes, but this could easily be provided. Understanding exactly
how this interface works is irrelevant to the project. The student
would be required to attend EPCC's Genetic Algorithms course as early
as possible.
Resources Required
The whole project could easily be developed on the EPCC cluster. It
would be nice, however, to run large problems on the T3D if the
cluster version proves successful. I believe that an MPP version of
RPL2 exists.
Resources Supplied
Test data sets and, if required, stubs to link RPL2 to the students code.
Chris Wendl worked on this project.
Compressed PostScript of the project's final report will be
available here
(189 kbytes) .
Webpage maintained by
mario@epcc.ed.ac.uk