


BioIngenium
Group
Centro de Telemedicina
Universidad Nacional de Colombia 





Distributed Genetic Algorithm for Subtraction
Radiography 





3. Genetic Algorithm and Parallelization 


Genetic Algorithms are based on adaptive
stochastic random search (J. H. Holland, "Adaptation in Natural and Artificial Systems"), simulating the natural
selection process where only the fittest individuals survive. The proposed GA is uses real number encoding. Accordingly,
each individual is composed of four floating point numbers representing the parameters used in the affine transformation.
An initial population is created by applying random mutations over an individual that is chosen between the null transformation
and the center of mass transformation. Fit candidates, selected by tournament, are used for crossover in order to produce
a new population. After crossover, a mutation operator is then applied to each individual to guarantee that the probability
of searching a particular subspace of the problem space is never zero (A. Chipperfield and P. Fleming, "Parallel
Genetic Algorithms"). This prevents the algorithm from becoming trapped in local extrema (P. Husband, "Genetic
Algorithms in Optimization and Adaptation"). Crossover is performed applying a variation of the averaging crossover
operator suggested in (L. Davis, "Handbook of genetic algorithms"). The mutation operator used, known as real
number creep, sweeps the individual adding or subtracting a gaussian distributed random noise to each parameter. Each
new generation is then evaluated looking for a solution better than the best obtained so far. If a better solution is
not found, the process is repeated in an inner loop reducing the search range for each iteration until a better offspring
is generated. Otherwise, if a maximum number of iterations is reached, the algorithm stops.
The evaluation of the fitness function implies applying an affine transformation and the computation of the corresponding
correlation ratio. This computational intensive operation is required for each individual of a population. Since this
operation can be computed independently, this part of the algorithm was parallelized and executed on a computational
grid based on the JavaSpaces (JavaSpaces is a trademark of Sun Microsystems) technology, using the well known masterworker
pattern. The grid is composed of forty general purpose workstations, with memory ranging from 256 to 512 Mbytes. Source
code of the GA and additional documentation about the computational grid is available here.
Class diagrams are available here.
A number of 4580 experiments were performed in order to guarantee a complete analysis of the parameter space. An experiment
is the execution of the algorithm with a particular set of parameters, i.e. population size, tournament size and genetic
operators probabilities. In this task the grid became an invaluable tool and allowed us to achieve a second level of
parallelism.
The following diagram (Fig. 1) shows the general approach followed to parallelize a batch of experiments. The experiment
builder class loads and XML configuration file wich specifies the images to use and other algorithm parameters (population
and tournament sizes, crossover and mutation probabilities, etc.), computes the Bezier coefficients, generates the batch
of experiments and puts all in the space. Once in the space, the experiments are fetched by the workers that proceed
to execute them and put back in the space the best individual for each experiment.






Figure 1. 








Figure 2 shows the parallelization of the experiment.
The reference and floating images, as well the Bezier coefficients, are read from the space. Two individuals are then
generated, based on the null transformation (0.0, 1.0, 0.0, 0.0) and the center of mass transformation (0.0, 1.0, C_{mx},
C_{my}), and their correlation ratios computed. The best of these two individuals is then used to generate the
initial population. The individuals that compose this population are put in the space, fetched by the workers, their fitness
computed (image transformation + correlation ratio computation) and put back in the space. These evaluated individuals
are then collected by the experiment class which selects the best ones by means of a tournament scheme. These selected
individuals are used to breed a new population and the process starts again. When the maximum number of iterations is
reached or when the algorithm is not able to find a better individual than the best one found in the previous iteration,
the process stops and the best individual is put in the space. 





Figure 2. 








> results 


< methodology 









