L.D. Chiwiacowsky, H.F. de Campos Velho, A.J. Preto, S. Stephany (2002): A Parallel Genetic Algorithm Applied to an Inverse Heat Conduction Problem, Brazilian Congress on Computing and Applied Mathematics (CNMAC-2002), 11-15 September, Brasil.

Abstract: Genetic algorithms are efficient search methods based on natural and genetic selection of population being inherently parallel[1]. It is proposed a parallel implementation of a genetic algorithm to solve the one-dimensional inverse heat conduction problem of determining the initial temperature distribution (time ti) from the transient temperature noisy profile at a given time tf, considering insulated boundary conditions. This ill-posed problem requires the use of a regularization technique for its solution and the Tikhonov 0th order was chosen [2]. The solution is given by the candidate function which minimizes the functional given by the square differences between the experimental and simulated temperatures at time tf, plus the regularization term weighted by a regularization parameter. Therefore, this inverse problem is formulated as an optimization problem, which is solved by a parallel implementation of a specifically developed genetic algorithm method. This proposed method is based on individuals with genotypes formed by a set of real numbers [3]. The parallel code was generated using calls to the message passing communication library MPI (Message Passing Interface) [4]. Usually, parallel genetic algorithms work with sub-populations (demes) which are placed on each processor and it was used the migration policy given by the island model [5], In such model, individuals are free to migrate to any other processor, subjected to specific rules. For instance, in the stepping stones model individuals can only migrate to neighbor processors. The inversions were accomplished for two different population sizes (336 and 1008), being the individuals equally distributed among the processors. Number of processors was 2 to 16, and processing times show efficiencies between 0.9 and 1.14 for the 1008 individuals and between 0.83 and 0.89 for 336 individuals. This was expected as a bigger population causes a larger granularity and thus a better efficiency.

References:

[1] E. Cantu-Paz (1995): A summary of research on parallel genetic algorithms, IlliGAL Report No 95007, University of Illinois.

[2] A.N. Tikhonov, V.Y. Arsenin (1977): Solutions of ill-posed problems, Winston & Sons, Washington, USA.

[3] Z. Michalewicz (1996): Genetic algorithms + data structures = evolution programs, Springer-Verlag, USA.

[4] P. Pacheco, W.C. Ming (1995): Introduction to message passing programming - MPI user guides in FORTRAN and C, Department of Mathematics, University of San Francisco, USA.

[5] M. Nowostawski, R. Poli (1999): Parallel genetic algorithm taxonomy, Proc. of 3rd Int. Conference on Knowledge-based Intelligent Information Engineering Systems (KES'99), Adelaide, Australia.