The performance of each GA depends on a set of control parameters like population size, crossover and mutation rates, and on the selection strategy. While there was a lot of work done in determining a globally optimal set of control parameters for a wide range of applications, in the nearer past some work on self-adapting GAs has been published. Here no static parameter set is determined, but an adaptation of the parameters during the optimization process takes place. This can be done by externally changing the mutation-rate in a predefined manner like Fogarty describes [8], or controlling the parameters of the GA by a simulated annealing like `cooling-schedule', which is done by Esbensen and Mazumder in their GA for macro-cell placement [7]. Adaptation can be controlled by the evolution process itself by using a (meta-) GA for the optimization of the parameters like Bäck [1] or Freisleben and Härtfeler [9] have done. Wang et al. [18] introduce a hierarchy of GAs and suggest even to adapt the representation. The concept of competing subpopulations by Schlierkamp-Voosen and Mühlenbein [14] is a self adapting approach, where the sizes of subpopulations, which pursue different strategies, are adapted. Successful strategies are used by larger populations, while the size of less productive populations decreases.
The adaptation in this application also takes place on the subpopulation level, but here the population sizes are fixed, while the strategies are flexible. A strategy is characterized by a parameter set for the GA. The parameter set consists of the mutation rate, the crossover rate and the threshold for the truncation selection. Further a strategy fixes the frequency of the different mutation operators.
Due to the fact that the power of the crossover operator to create new individuals is limited to the combination of two subtrees of both parents, within this application mutation is more important than in common GAs with simple encoding. The crossover operator only combines meta-blocks, but never creates a small meta-block, because in both parents always `real' subtrees (with more than one leaf) are chosen. Hence there are several mutation operators, and every offspring is created either by crossover or by mutation. In all generations the total number of created offspring is constant.
After a fixed interval all strategies are ranked, and the parameters of each strategy are adapted to the values of the next better strategy. The best strategy is expanded, i.e. its characteristical parameters are strengthened. For example, if the best strategy is distinguished by a low crossover rate, then this value will be decreased.
If the optimization on an island gets stuck, i.e. if no progress has been realized since the last adaptation, the strategy of this island is reset. Therefore the parameters are set back to one of the initial settings. This ensures that a strategy which has got lost in the beginning, but might be helpful at this time, is reactivated to boost the optimization.
The most important point in the implementation of an adaptation is to fix the quality criterion, regarding to which the strategies are ranked. In [14], the progress of the islands is measured based on the fitness of the best individuals observed over a period of time. Because of the small subpopulation size in this application, a fitness based quality criterion turned out to be not useful. This value is very much influenced by migrating individuals. A better criterion to describe the progress during the optimization process is the response to selection used in Mühlenbeins BGA [11]. This response is defined by the difference between the average fitness of a (sub-) population in two succeeding generations.