Keywords: meta-GAs, coarse-grain GAs, parallel processing, premature convergence, migration, truss-structure design.

In this study, a coarse-grain parallel meta genetic algorithm (GA) with a dynamic connection scheme has been designed. In order to show the efficiency and robustness of this model, it is applied to the problem of finding optimal cross-sectional size, topology and configuration of 2D and 3D trusses to achieve minimum weight. Stress, deflection and kinematic stability are regarded as constraints. The results show that this method finds trusses which have smaller weight and better configuration than those, reported in the literature. Finally, the speed up and performance of a number of coarse-grain GAs with various migration methods and connectivity schemes are investigated and compared to show the capability of this new approach.

The proposed meta-GA model is a SGA with tournament selection, one-point crossover and bitwise mutation operators. Its chromosome includes: 1) Selection type, which includes tournament, roulette wheel and linear ranking selection, 2) Crossover type which includes one-point, two-point, uniform and cyclic crossover, 3) Migration rate which defines the number of individuals passing to other islands during each migration time, 4) Crossover rate and 5) Mutation rate. Parallelizing has been achieved through a Beowulf system which contains a cluster of PCs with distributed memory. The MPI library has been used for passing messages between various nodes. Lower level GAs run in parallel and after a predefined number of generations, a number of individuals, selected upon the proposed migration strategy, are sent to the other islands asynchronously. That is, during the migration time each node sends immigrants to its neighbours and receive individuals from other islands whenever they were passed to it (if no individuals were passed, the node does not wait but continues its GA search). This kind of communication was achieved through the use of Remote Memory Access (RMA) which is supported by MPI2. Due to the fact that sub-GAs have different initial parameter settings imposed by the higher level one, this model can be classified as a heterogonous parallel GA. Consequently, a dynamic connection model is proposed which is mutable with time. According to this method, called distance connection topology, during each migration time the node's neighbours can be determined based on similarity, and therefore sub-populations with closest hamming distance exchange data with each other.

In sizing optimization, the cross section of each member is taken as a variable which can take any value in a specified range. Topology optimization has been implemented by introducing the concepts of ground structure and basic and non-basic nodes [1]. In order to optimize the truss configuration, nodes coordinates must be located in predefined limited range. Thus, the final goal is to find optimal non-basic nodes and their coordinates, required members and their cross-sectional areas to achieve trusses with minimum weight while satisfying the imposed constraints. The NLP nature of the problem and the large number of total variables and constraints results in multimodality of objective function and occurrence of many local optima. However, by using a two level GA and parallelizing it, efficiency of the heuristic model increases and both of the workload and execution time are reduced considerably.

Applying the meta-GA scheme on a number of 2D and 3D trusses, it was observed that the proposed model was both efficient in automating parameter tuning and preventing premature convergence. The results show that this scheme finds trusses with lower weight and better configurations than those reported in the literature. In addition, by using the multi-population model, different high fitness individuals were found in various islands which reveal the capability of parallel processing in finding the local optima in multi-modal functions. The proposed model was compared with a number of coarse-grain GAs with different migration methods and connectivity schemes. It was found that this model outperforms the schemes with synchronous communication and static connection topology. Finally, by defining the speedup as the time-to-solution, high superlinear speedup was observed, indicating the effectiveness of distributed processing in both decreasing the execution time and workload of GAs.

1

K. Deb and S. Gulati, "Design of truss-structures for minimum weight using genetic algorithms", Journal of Finite Elements in Analysis and Design, 2001. doi:10.1016/S0168-874X(00)00057-3

2

K. Sarma and H. Adeli, "Bilevel Parallel Genetic Algorithms for Optimization of Large Steel Structures", Computer-Aided Civil and Infrastructure Engineering, 2001. doi:10.1111/0885-9507.00234

3

S. Lin, W.F. Punch, and E.D. Goodman, "Coarse grain parallel genetic algorithms: Categorization and new approach", The Sixth IEEE Symposium on Parallel and Distributed Processing, 1994, pp. 28-37.

4

E. Goodman, W.F. Punch and V. Uskov, "Optimization of a GA and within a GA for a 2-Dimensional Layout Problem", First International Conference on Evolutionary Computation and its Applications, 1996.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £80 +P&P)