The crossover bias theory for bloat [18] is a recent result which predicts that bloat is caused by the sampling of short, unfit programs. This theory is clear and simple, but it has some weaknesses: (1) it implicitly assumes that the population is large enough to allow sampling of all relevant program sizes (although it does explain what to expect in the many practical cases where this is not true, e.g., because the population is small); (2) it does not explain what is meant by its assumption that short programs are unfit. In this paper we discuss these weaknesses and propose a refined version of the crossover bias theory that clarifies the relationship between bloat and finite populations, and explains what features of the fitness landscape cause bloat to occur. The theory, in particular, predicts that smaller populations will bloat more slowly than larger ones. Additionally, the theory predicts that bloat will only be observed in problems where short programs are less fit than longer ones when looking at samples created by fitness-based importance sampling, i.e. samplings of the search space in which fitter programs have a higher probability of being sampled (e.g., the Metropolis-Hastings method). Experiments with two classical GP benchmarks fully corroborate the theory. Copyright 2008 ACM.

Poli, R., Mcphee, F., Vanneschi, L. (2008). The impact of population size on code growth in GP: Analysis and empirical validation. In GECCO'08: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation 2008 (pp.1275-1282). ACM Press [10.1145/1389095.1389341].

The impact of population size on code growth in GP: Analysis and empirical validation

VANNESCHI, LEONARDO
2008

Abstract

The crossover bias theory for bloat [18] is a recent result which predicts that bloat is caused by the sampling of short, unfit programs. This theory is clear and simple, but it has some weaknesses: (1) it implicitly assumes that the population is large enough to allow sampling of all relevant program sizes (although it does explain what to expect in the many practical cases where this is not true, e.g., because the population is small); (2) it does not explain what is meant by its assumption that short programs are unfit. In this paper we discuss these weaknesses and propose a refined version of the crossover bias theory that clarifies the relationship between bloat and finite populations, and explains what features of the fitness landscape cause bloat to occur. The theory, in particular, predicts that smaller populations will bloat more slowly than larger ones. Additionally, the theory predicts that bloat will only be observed in problems where short programs are less fit than longer ones when looking at samples created by fitness-based importance sampling, i.e. samplings of the search space in which fitter programs have a higher probability of being sampled (e.g., the Metropolis-Hastings method). Experiments with two classical GP benchmarks fully corroborate the theory. Copyright 2008 ACM.
paper
impact, population, size, code, growth, gp, analysis, empirical, validation
English
10th Annual Genetic and Evolutionary Computation Conference, GECCO 2008
2008
GECCO'08: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation 2008
9781605581309
2008
1275
1282
none
Poli, R., Mcphee, F., Vanneschi, L. (2008). The impact of population size on code growth in GP: Analysis and empirical validation. In GECCO'08: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation 2008 (pp.1275-1282). ACM Press [10.1145/1389095.1389341].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/13584
Citazioni
  • Scopus 23
  • ???jsp.display-item.citation.isi??? ND
Social impact