Page 83 - 49A Field Guide to Genetic Programming
P. 83
Chapter 8
Probabilistic Genetic
Programming
Genetic programming typically uses an evolutionary algorithm as its main
search engine. However, this is not the only option. The use of simulated
annealing and hill climbing to search the space of computer programs was
mentioned in Section 5.4. This chapter considers recent work where the ex-
ploration is performed by population-based search algorithms which adapt
and sample probability distributions instead of using traditional genetic op-
erators.
Sampling from a probability distribution means generating random val-
ues whose statistical properties match those of the given distribution. For
example, if one sampled a univariate Gaussian distribution, one would ex-
pect the resulting values to tend to have mean and standard deviation sim-
ilar to the mean and standard deviation of the Gaussian. The notion of
sampling can be extended to much more complex distributions involving
multiple variables. Furthermore, discrete as well as continuous variables are
possible.
8.1 Estimation of Distribution Algorithms
Estimation of distribution algorithms (EDAs) are powerful population-based
searchers where the variation operations traditionally implemented via
crossover and mutation in EAs are replaced by the process of random sam-
pling from a probability distribution. The distribution is modified genera-
tion after generation, using information obtained from the fitter individuals
in the population. The objective of these changes in the distribution is to
increase the probability of generating individuals with high fitness.
69
