A model for parallel operators in genetic algorithms

Abstract:

In this chapter we have presented a model of GA for applying crossover and varying mutation separately and in parallel. We focused on the gains on performance that can be achieved from the concurrent application of variation operators with different and complementary roles. An important conclusion of this work is that appropriate models for the concurrent application of operators, such the one proposed here, should be devised first for the actual parallelization of operators to be meaningful. We analyzed the model using deterministic, adaptive, and self-adaptive mutation rate controls and tested its performance on a broad range of classes of 0/1 multiple knapsack problems by varying the feasible region of the search space, number of constraints, and the size of the search space. We compared the proposed model with the conventional one showing that varying mutation parallel to crossover gives an efficient framework to achieve high performance by keeping the strengths of the individual operators without interfering one with the other. We also showed that the model is superior for online adaptation of parameters and contend that it is a better option for co-adaptation of parameters. In addition, we studied the performance of parallel operators within distributed GAs showing that the inclusion of varying mutation parallel to crossover reduces substantially communication costs due to migration, improves convergence reliability and speed of the algorithm, and can increase considerably the robustness of the algorithm. It was shown that a canonical DGA relies in higher selection intensity introduced by migration to achieve high results at the expense of very high communication cost. The distributed GA with parallel operators even without migration produced very high results compared to a canonical DGA with small migration intervals. In the future we would like to implement this model on a parallel architecture, where in addition to the challenges imposed by the concurrent process shown in this work, we will need to cope with the demands proper of parallel implementations. © Springer-Verlag Berlin Heidelberg 2006.

Año de publicación:

2006

Keywords:

Fuente:

scopus