\chapter{Evolutionary algorithms}
\label{chap:EAs}

Since the early days of computer science, researchers have had the idea to use the principles of natural selection to solve abstract problems. As time went on, and the field widened to include such research areas as artificial life \cite{langton89}, the term \emph{evolutionary algorithms} was increasingly used as an umbrella term covering all search and optimization algorithms inspired by the principles of natural selection.

In this chapter, we will briefly introduce the many facets of evolutionary algorithms, their common principles and specific varieties. In the second section of the chapter, one particular algorithm of interest to us, the \emph{Selfish Gene Algorithm}, will be closely examined.

\section{Evolutionary and genetic algorithms}

A term like \emph{evolutionary algorithms} does not have one single definition, and over time it has been used to describe a wide variety of algorithms. One kind of algorithm that is widely regarded as the quintessential evolutionary algorithm is the \emph{genetic algorithm}. Genetic algorithms, made popular through the work of John Holland in the 1970s, combine many of the features now seen as cornerstones of evolutionary algorithms: a population of contending individuals that represent (partial) solutions to a problem, and evolutionary operations such as selection and recombination that are applied iteratively to these individuals.

These and other essential features of evolutionary algorithms will be described in the next section, while genetic algorithms will be revisited in \autoref{sec:GeneticAlgorithms}.

\subsection{General principles}
The basis of any evolutionary algorithm is the notion of a population of individuals. The population, as well as the individuals, can be either explicit or implicit. To this population the principle of natural selection is applied. Natural selection is a process by which some individuals produce more offspring than others. The likelihood of an individual passing on its genetic material to the next generation is known as its \emph{fitness}. Quantifying fitness is far from straightforward, as it includes not only internal qualities of the individual itself, but also its environment, its actions, and a large amount of chance.

In nature, it is not always easy to see which individuals are fit and which are not.\footnote{This is the origin of Charles Darwin's phrase ``preservation of favoured races,'' which has sadly been taken out of context by many, to make some political point \cite{dawkins04}.} In most evolutionary algorithms there is a deterministic fitness function, which is essentially a mapping from the set of all individuals to the set of real numbers. Other algorithms opt for a tournament mechanism where, rather than assigning an absolute fitness value to each individual, several individuals are compared head-to-head and a winner is picked. Regardless of the specifics, the selection principle provides the algorithm with the means to rank and order its population by fitness.

The second unifying notion of an evolutionary algorithm is the principle of \emph{variation} and iterative evaluation. In one iteration, or generation, of the algorithm a number of operations are applied to the population. The purpose of these operations is to make some small variations in the composition of the population. The two most popular variation mechanisms are recombination and mutation, which will be described in \autoref{sec:GeneticAlgorithms}; however, many other mechanisms exist and we will meet some of them when we examine the Selfish Gene Algorithm in \autoref{sec:SelfishGeneAlgorithm}.

Summing up, an evolutionary algorithm is characterized by:
\begin{itemize}\compactlist
	\item A population of individuals which represent (partial) solutions to a problem.
	\item A mechanism to order individuals according to their fitness.
	\item A set of operations that are applied to the population every generation.
	\item Variation operations such as recombination, mutation, etc.
\end{itemize}

\subsection{Types of evolutionary algorithms}
In their overview of evolutionary computation \cite{back00}, B{\"a}ck and Fogel recognize three important subsets of evolutionary algorithms: genetic algorithms, genetic programming and evolutionary strategies, although it should be noted that many more classifications and partitionings exist.

\subsubsection*{Genetic algorithms}
\label{sec:GeneticAlgorithms}
The most popular evolutionary algorithm is the genetic algorithm. In a genetic algorithm, a population of (usually) constant size is filled with individuals that represent solutions to an optimization problem. These individuals are traditionally represented by binary strings, although real-valued implementations also exist.

Borrowing biological terminology, the representation of an individual is known as its \emph{genotype} and consists of a string of \emph{genes} called the \emph{chromosome}, with each gene occupying a distinct \emph{locus} on the chromosome.\footnote{It should be noted that in nature, only prokaryotic lifeforms such as bacteria have a genotype consisting of one single chromosome. Other organisms have several; for instance, a human has 46 chromosomes and a goldfish has more than 100. Furthermore, it is important to remember that genetic material is found not only on our chromosomes, and that chromosomes contain more material than just genes.} The number of different genes that can occupy a locus is often finite: in the case of binary strings, a gene can have the value 0 or 1. The different values that can appear at a locus are sometimes called \emph{alleles}.

Selection is usually done using an absolute fitness function, and produces pairs of individuals that are then recombined using a crossover operator. This operator swaps parts of the genotype of the two individuals. Another operator applied to the population is the mutation operator, which randomly alters some genes of some individuals.

At each generation, the operators are used to create a set of offspring from the set of individuals. A mechanism which is sometimes called \emph{elitism} is then used to determine which of the parents and which of the offspring are allowed to propagate to the next generation.

The algorithm continues executing generation upon generation until some stopping condition is met. This may occur when the population has become homogeneous, when an individual with a certain fitness value is found, or simply when some time limit has been reached.

\subsubsection*{Genetic programming}
The goal of genetic programming is not to evolve a specific solution to a problem, but to evolve a system or algorithm capable of solving a given problem. Traditionally, individuals in genetic programming represented finite-state machines; modern methods are capable of evolving complex computer programs.

While the principles of evolutionary computation (selection, variation) are identical to those in genetic algorithms, the actual operations in genetic programming depend heavily on the semantics of the genotype, whereas genetic algorithms are traditionally more oblivious of what the chromosome actually represents.

\subsubsection*{Evolutionary strategies}
In contrast to genetic algorithms which are used to evolve solutions to a (discrete, combinatorial) problem, the purpose of evolutionary strategies is optimization of parameters. A much larger role is given to the mutation operator; since most implementations of evolutionary strategies operate in a real-valued search space, mutation consists of sampling data points from a normal distribution that somehow fits the population.

Other distinguishing features of evolutionary strategies are the clear distinction between a parent population and an offspring population, and the use of self-adaption mechanisms for the algorithm's runtime parameters. For another look at self-adaption, see \autoref{sec:SelfAdaption}.



\section{The Selfish Gene Algorithm}
\label{sec:SelfishGeneAlgorithm}
The \emph{Selfish Gene Algorithm} (SG) is an evolutionary algorithm that was invented in 1998 by Corno et al.\ and is described in their paper ``The Selfish Gene Algorithm: a New Evolutionary Optimization Strategy'' \cite{corno98}. The algorithm breaks away from canonical genetic algorithms by adopting a gene-centered view of evolution, a relatively young and somewhat controversial theory that has gained a following among biologists in recent years. The distinguishing feature of SG is the fact that the population is implicit, and that no operations such as recombination or elitism are necessary.

\subsection{Biological rationale}
The gene-centered view of evolution puts natural selection in a different light by taking the gene as the unit of evolution, rather than the individual. In his book ``The Selfish Gene'' \cite{dawkins89}, from which the algorithm derives its name, English biologist Richard Dawkins outlines the principles behind the gene-centered view: he argues that individual genes compete for survival and strive for appearance in future generations. Individuals exist only as ``survival machines,'' providing the mechanisms by which successful genes can replicate and propagate. A successful gene is one that produces a good characteristic in its host, a characteristic that will increase the host's likelihood of reproducing and thus passing the successful gene on to the next generation.

Shifting the focus from individuals which are mortal and short-lived, to genes which are immortal and may survive indefinitely, the ``slogan'' of evolution---\emph{survival of the fittest}---can be seen to depict a struggle between contending genes. Genes compete for appearance on individuals' chromosomes, while at the same time being forced to cooperate with one another: a gene might produce a good characteristic only in the presence of certain other genes. Dawkins calls this a form of ``blind cooperation.''

It should be noted that genes are in no way conscious entities acting out of some personal interests. Rather, their behavior emerges out of the actions of individuals.


\subsection{The algorithm}
In the Selfish Gene Algorithm, the idea of a population filled with individuals is replaced by a virtual population (VP) that is essentially an implicit, statistical model of a population. For all alleles on all loci, the VP holds information about the allele's frequency in the population.

Individuals are used as survival machines: they are constructed only for fitness evaluation and then destroyed. When an individual is fit, its genes are rewarded: the specific allele values making up the individual's genotype will see their frequency in the VP increase. Vice versa, genes belonging to unfit individuals will be penalized.

Since individuals serve no role other than fitness evaluation, a recombination operation is not needed; rather, recombination is implied by the way individuals are constructed from statistically probable genes in the gene pool. Likewise, elitism is absent. Mutation is kept, but is performed during selection (construction) of individuals.

\subsection{Formal description}
Letting $n$ denote the number of genes (loci) in the genotype, $a_i$ is the number of alleles available at locus $i$, and $\Sigma a$ is the total number of alleles across the genotype. The virtual population is a set of probability values $P_{i,j}$ where $1 \leq i\leq n$ and $1 \leq j \leq a_i$. Since these probabilities reflect the frequency of contending alleles, the probabilities for any locus must add up to 100\%:
\begin{equation}
	\sum_{k=1}^{a_i}{P_{i,k}}=1
\end{equation}

In one generation, the algorithm constructs two ``random'' individuals and compares them in a tournament.\footnote{Note that there is no strict need for an absolute fitness function.} The winner of the tournament will see its genes rewarded: letting $\chi_i$ denote the allele present at locus $i$ on the winner's chromosome, the frequency of that allele is increased:
\begin{equation}
	P_{i,\chi_i} = P_{i,\chi_i} + \epsilon
\end{equation}
All alleles on the winner's chromosome will see their frequencies increased by $\epsilon$. At the same time, alleles on the loser's chromosome will see their frequencies decreased, again by $\epsilon$.
	
Letting $\rho$ denote the mutation probability, a random individual is constructed as follows: for each locus $i$, an allele will be chosen that is either random or proportional. The decision between random and proportional alleles is taken according to $\rho$: if a random number between 0 and 1 is greater than $\rho$, the allele will be proportional; otherwise, a random allele will be chosen.

In case of a proportional allele, the probability values $P_{i,k}\,,1 \leq k \leq a_i$ are used to choose which allele to place on the chromosome. In case of a random allele, an allele is chosen from the range $1,2,\ldots,a_i$ in a completely random way.

The Selfish Gene Algorithm also inctroduces the notion of \emph{convergence}. A gene is said to have converged when one of the alleles at the gene's locus has a significantly higher frequency than all the others. In the algorithm, a gene is flagged as ``converged'' when the probability of one of its alleles exceeds a certain threshold. In the implementation described in \autoref{chap:PSG}, this threshold is denoted by \texttt{convergenceThreshold}.


\subsection{Experimental analysis}
Corno et al.\ implemented the Selfish Gene Algorithm and compared it head-to-head with a canonical genetic algorithm, solving the 0/1~Multiple Knapsack Problem. They found that SG was able to outperform the canonical genetic algorithm under certain conditions, and they conclude that ``SG are easier to implement, have a smaller number of parameters to tune, do not rely on crossover operators, and are able to find more quickly optimal solutions. On the other hand, they tend to explore a smaller region of the search space, so they need to be inserted in some multi-start-like framework.'' \cite{corno98}

Further work by Corno et al.\ is described in \cite{corno00}, where the researchers apply the algorithm to the much more difficult problem of evolving cellular automata. This is analyzed in greater detail in \autoref{sec:PreviousWork}.
