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 master-worker 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, Cmx, Cmy), 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  
      > Aviso Legal