Convergence to global optima for genetic programming systems with dynamically scaled operators

摘要

This work shows asymptotic convergence to global optima for a family of dynamically scaled genetic programming systems where the underlying population consists of a fixed number of creatures (individuals) each of arbitrary size. The genetic programming systems use common mutation and crossover operators as well as fitness-proportional selection. In addition, the mutation and crossover rates are annealed to zero in predefined fashion over the course of the algorithm, and power-law scaling is used for the (possibly population-dependent) initial fitness function with (unbounded) logarithmic growth in the exponent.We assume that a set of globally optimal creatures for the optimization problem instance exists. In addition, it is assumed that the ratio of the best fitness of globally optimal creatures vs the fitness of other creatures is greater or equal a constant ρ1 in any population they jointly reside in. We discuss how both conditions can usually be satisfied in application settings. Under the above conditions, a selected, traceable sequence of probability distributions over the possible states of the properly scaled genetic programming system converge in time towards the convex set of probability distributions over uniform populations that contain only globally optimal creatures.