Domino Convergence

Building blocks with higher marginal fitness contribution – salient building blocks – converge before those with lower marginal fitness. Moreover, there comes a point in time – and fitness scale – when strong convergence runs out of steam, and low salience building blocks drift to substantial convergence at random with a resulting high probability of error. – Thierens 19981

Domino Convergence refers to the observation that elements (“building blocks”) in an encoding string that more significantly affect the measured objective value (“fitness”) converge earlier.

Thierens 19981 concludes, in the absence of other factors, that time complexity to converge in the case of constant selection intensity is linear (O(l)) to exponential (O(2l)) to the encoding length (l) of the encoding. On the other hand, where selection intensity is proportional to the fitness difference, time complexity to convergence is  exponential (O(2l)) to the encoding length (l).

Proportional selection intensity is exhibited, for example, in genetic algorithms that employ “roulette wheel” selection. Acting on Thierens’ conclusion above, we ought to be tempted to prefer the alternative “tournament” selection approach instead.

References

  1. Domino Convergence, Drift, and the Temporal-Salience Structure of Problems – Dirk Thierens, David E. Goldberg, Angela Guimaraes Pereira, 1998