2 Evolutionary Algorithms

Darwinian evolution uses the principles of competition, inheritance, and variation within a population. These concepts are used to define a class of iterative improvement metaheuristic search methods. These methods, evolutionary algorithms, use a population of solutions and genetic operators to carry out search. Specifically, the evolutionary algorithm employs the following items:

• A population of candidate solutions called individuals,
• A fitness function that evaluates and assigns each individual a score, or fitness value,
• Transformation operators that produce offspring individuals from parent individuals, implementing the concept of inheritance through stochastic variation, and
• A stochastic selection method for selecting individuals with better fitness to produce offspring.

Given a population $p$ at time $t$, the evolutionary algorithm applies variation operators $v$ on the population. Variations are applied according to a selection method $s$, where individuals compete to be selected according to their fitness. A population $p$ at time $t+1$ is found by:

$$p_{t+1} = v(s(p_t))$$

The transformation operators $v$ provide new solutions by means of variations on existing ones. In evolutionary algorithms, these operators usually consist of reproduction, recombination and mutation operators. The population together with variation operators and competition provide a strategy for searching the space of solutions. Only those solutions which are reachable by the operators could be visited during the evolutionary process or run. Additionally, the use of a population in search, instead of searching with a single solution as in hill-climbing, allows for a parallel search of different areas of the search space representing alternative representations of similar fitness.

Evolutionary algorithms are often categorised into four main branches that are mainly distinguishable by their commonly used representation and operators: genetic algorithms use a bit-string and two-parent crossover, evolutionary strategies use a real-valued vector and Gaussian mutation, evolutionary programming employs a finite-state machine and mutation operators, and genetic programming uses a computer program or executable structure and two-parent crossover. These classifications represent common or initial implementations. Many implementations use components from different branches and make the classifications less accurate.

The genetic algorithm was originally represented by bit-strings in a fixed length genome. The term genome refers to the bit-string. Early work by Fraser (1957), reprinted in [Fogel, 1998], and Bremermann (1962) provided the foundations of genetic algorithms, which were later popularised by Holland (1975) and DeJong (1975). A bit-string requires a mapping to a representation that can be evaluated and assigned a fitness by the heuristic evaluation function. The genetic algorithm traditionally relied on various forms of crossover as the main operator. For instance, in one-point crossover with bit-strings $a$ and $b$ with bit positions indexed from $1\ldots L$, a point $p$ is chosen such that $1\geq p \geq L-1$. Next, the bit-strings exchange the portions of the string delineated by point $p$ so that

$$\begin{array}{l} a = a_1\ldots a_p a_{(p+1)}\ldots a_L \tex... ...(p+1)}\ldots a_L \qquad \textrm{ after crossover.} \end{array}$$

Evolutionary strategies traditionally uses a direct encoding of the candidate solution, typically as a vector of real numbers [Rechenberg, 1965,Bäck et al., 2000a]. The method began using a population consisting of a single individual. Offspring are produced by a Gaussian mutation operator and became the new population if they were better than the parent. Population-based evolutionary strategies uses two main selection schemes, the comma or plus strategy. In the ($\mu$,$\lambda$) version, $\lambda$ offspring replace the $\mu$ parents. In the ($\mu + \lambda$) version, parents and offspring compete to become the new set of $\mu$ parents. Evolutionary programming was originally based on the iterative adaptation of finite-state machines [Fogel et al., 1966]. Finite-state machines are evaluated and assigned a fitness. A mutation operator is usually the only means of variation. In this sense, the population in evolutionary programming is like an ecosystem of species, where each individual is a different species.

Within the evolutionary algorithm framework, specialised methods such as multipopulation models [Cohoon et al., 1987], coevolutionary models [Potter and De Jong, 1994] and memetic models [Moscato, 1989,Krasnogor, 2002] exist to further blend evolutionary algorithms with other local search and heuristic methods. These hybrid algorithms typically combine global search strategies with local strategies, representing the state-of-the-art in optimisation [Davis, 1991,Pardalos and Resende, 2002,Glover and Kochenberger, 2003]. Hybrids allow a general metaheuristic search strategy to be specialised for specific applications. Davis (1991) points out that the two objectives of generalisation and specialisation are conflicting in that increasing the performance of a method for a specific domain is likely to make the same method perform worse on other domains. The ``No Free Lunch Theorems'' by Wolpert and Macready (1997) emphasised this performance trade-off by explicitly stating that the average performance of all methods over all problems will be equal. However, this does not prevent some algorithms from being better than others on particular classes of problems.

Genetic programming is an evolutionary algorithm that represents solutions as programs. The remainder of this thesis will focus specifically on the canonical form of this method and representation.