The GA has been tested with real-world circuits.
These are taken from a suite of benchmarks made available for design workshops
in the early 90's, and are mostly cited in the literature as the
MCNC-benchmarks
.
It is still the most referenced benchmark suite for
macro-cell layout generation, and includes partitioned circuits with 10 to 49 cells,
and up to 408 nets.
Figure 4: The effect of the adaptation for a sample optimization run
In fig. 4 the effect of the strategy adaptation for
a sample optimization run is visualized.
The circuit is ami33, which consists of 33 cells and
123 nets.
The results were achieved on a Parsytec GC/PP machine using a 12 processor
network.
Each island held a population of 20 individuals, the migration interval
was 6 generations, and adaptation took place every 30 generations.
An average of all values was taken over the 12 subpopulations except for the
layout area (bottom), which describes the fitness of the best
individual in the whole system.
At the beginning of the optimization process, the crossover rate, i.e.\
the quota of offspring created using crossover rose up to 75%
around the 500th generation.
After that point, with decreasing variation in the population,
mutation replaced crossover as the favourite offspring creation method.
At the end (
after 1500 generations), some strategies were reset,
which yielded in balancing out the crossover/mutation rate.
The part of the figure which represents the frequency of the four
tree-modifying mutation operators shows that the operator, which exchanges two
meta-blocks might be useless, and that the changing of the tree structure
seems to be more important, but this differs on single runs.
Nevertheless, the shown progress of the mutation/crossover rate
is typical for this circuit.
Figure 5 shows the average development of this rate for
circuit ami49 with 49 cells and 408 nets.
The runs were started with the same initial settings like those used
in the other run shown in fig. 4.
It is seen that for this case - in contrast to circuit ami33 - in the early
stages of the optimization, mutation is much
more efficient than crossover for enhancing the progress of the optimization.
While both circuits differ in the number of cells and nets, the main
difference is in the connectivity: each net in circuit ami33
connects an average of 3.7 terminals, whereas in circuit most
nets only connect two terminals (avg. 2.3).
Figure 5: The adaptation of crossover/mutation rate for circuit ami49 (avg. of 10 runs)
Figure 6 presents the effect of the adaptation on the performance, again for circuit ami33. The values are taken from runs on 16 processors with a subpopulation size of 10 individuals, an average of 20 runs is shown. The upper curve describes the performance resulting from experiments with the parameters set to the average values of the initial strategies of the general case. Thus all islands are pursuing the same strategy. The middle curve shows that the performance can be enhanced considerably, if the islands use different strategies. Note that in both cases no adaptation takes place. As it can be gathered from the lowest curve, the best performance is reached if the islands start with different strategies which are adapted during the search.
Figure 6: The performance of the parallel GA
depending on the use of different strategies and adaptation (avg. of 20 runs each)