Search

Genetic programming (GP) is an evolutionary computation technique to solve problems in an automated, domain-independent way. Rather than identifying the optimum of a function as in more traditional evolutionary optimization, the aim of GP is to evolve computer programs with a given functionality. While many GP applications have produced human competitive results, the theoretical understanding of what problem characteristics and algorithm properties allow GP to be effective is comparatively limited. Compared with traditional evolutionary algorithms for function optimization, GP applications are further complicated by two additional factors: the variable-length representation of candidate programs, and the difficulty of evaluating their quality efficiently. Such difficulties considerably impact the runtime analysis of GP, where space complexity also comes into play. As a result, initial complexity analyses of GP have focused on restricted settings such as the evolution of trees with given structures or the estimation of solution quality using only a small polynomial number of input/output examples. However, the first computational complexity analyses of GP for evolving proper functions with defined input/output behavior have recently appeared. In this chapter, we present an overview of the state of the art.

This thesis presents new running time analyses of nature-inspired algorithms on various dynamic problems. It aims to identify and analyse the features of algorithms and problem classes which allow efficient optimization to occur in the presence of dynamic behaviour. We consider the following settings:λ-MMAS on Dynamic Shortest Path Problems. We investigate how in-creasing the number of ants simulated per iteration may help an ACO algorithm to track optimum in a dynamic problem. It is shown that while a constant number of ants per-vertex is sufficient to track some oscillations, there also exist more complex oscillations that cannot be tracked with a polynomial-size colony. MMAS and (μ+1) EA on Maze We analyse the behaviour of a (μ + 1) EA with genotype diversity on a dynamic fitness function Maze, extended to a finite-alphabet search space. We prove that the (μ + 1) EA is able to track the dynamic optimum for finite alphabets up to size μ, while MMAS is able to do so for any finite alphabet size.Parallel Evolutionary Algorithms on Maze. We prove that while a (1 + λ) EA is unable to track the optimum of the dynamic fitness function Maze for offspring population size up to λ = O(n1-ε”), a simple island model with Ω(log n) islands is able to do so if the migration interval is chosen appropriately. Migration Topology in Island Models. We investigate the impact of the migration topology on the performance of an island model optimizing a Maze-like dynamic function, demonstrating that in some cases, a less-dense migration topology is preferable to a complete migration topology. (1+1) EA on Generalized Dynamic OneMax. We analyze the (1 + 1) EA on dynamically changing OneMax, re-proving known results on first hitting times using modern drift analysis, and providing a new anytime analysis showing how closely the EA can track the dynamically moving optimum over time. These results are also extended to a finite-alphabet search space.