\chapter{The Parallel Selfish Gene Algorithm}
\label{chap:PSG}

In the previous chapters, we have become acquinted with the field of evolutionary algorithms and its extension, parallel evolutionary algorithms (PEA's). We have met the Selfish Gene Algorithm (SG), an unusual evolutionary algorithm based on recent developments in modern evolutionary biology.

In this chapter, we will describe the Parallel Selfish Gene Algorithm (PSG), a new evolutionary algorithm intended as a parallel version of SG. In the first section, the architecture of PSG will be discussed. The second section introduces the concept of self-adaption and shows how it can benefit a genetic algorithm such as PSG.

\section{System architecture}
\label{sec:SystemArchitecture}
PSG is based on the ``island model'' of PEA's. There are two reasons for this choice of architecture; first of all, there is the observation that island model PEA's have the potential to reach solutions of higher quality than may be reached by sequential methods or single-population PEA's. Another reason is the fact that the island model is a more appropriate choice for implementation on a Beowulf-style cluster of PC systems \cite{tomassini99}.

Following the discussion in \autoref{sec:IslandModel}, an asynchronous migration strategy was chosen. It is worth noting that the Selfish Gene Algorithm adjusts only a handful of allele probabilities at each generation, meaning that SG resembles the steady-state reproduction model and should therefore benefit greatly from an asynchronous migration strategy.

Most asynchronous PEA's operate by migrating a certain number of individuals when the deme has reached some level of convergence. In PSG, the communication packet consists of the allele values of converged genes. This corresponds with the philosophy behind the gene-centered view of evolution, namely that it is the genes themselves that are important, not the individuals.

Communication packets are sent once a deme has reached a certain level of convergence. In general, the communication packet can be described as follows:
\begin{quote}
	A communication packet consisting of the allele values of $X$ converged genes is sent when $Y$ genes have converged, where $X \leq Y \leq n$.
\end{quote}
$X$ and $Y$ are called the \emph{epoch thresholds}. For each consecutive communication event these thresholds are slowly increased. The period between two communication events is called an \emph{epoch}. After any epoch $e$, the thresholds are increased according to the following formulas.
\begin{subequations}
	\begin{gather}
		X_{e+1} = X_e + \left\lceil \frac{X_e}{\gamma} \right\rceil \\
		Y_{e+1} = Y_e + \left\lceil \frac{Y_e}{\gamma} \right\rceil
	\end{gather}
\end{subequations}
where $\gamma \geq 1$ is called the \emph{epoch length modifier}. For the first epoch, the thresholds $X_0$ and $Y_0$ are given as parameters of the algorithm. Note that special care must be taken to ensure that $X$ and $Y$ never exceed $n$.

Communicating demes send their communication packets to $\delta$ nearest neighbors, where $\delta$ is the degree of the (simulated) topology. The actual topology does not matter: Cant{\'u}-Paz \cite{cantupaz00} found that topologies of the same degree generally reach the same solutions in the same amount of time.

On the side of the recipient, incoming allele values are used to adjust the recipient's virtual population. For each incoming allele value, the probability of that allele is increased, and the probabilities of all other alleles on the same gene are decreased. Denoting the locus of the incoming allele by $i$ and the specific allele value by $j$, probabilities are adjusted as follows:\footnote{Note that the ``$=$'' symbol in these equations denotes assignment and not equality.}

\begin{subequations}
	\begin{gather}
		P_{i,j} = \frac{P_{i,j}+\mu} {1+\mu} \\
		\forall\,k,\ 1 \leq k \leq a_i, k \neq j,\ \ P_{i,k} = \frac{P_{i,k}} {1+\mu}
	\end{gather}
\end{subequations}
where $\mu>0$ is called the \emph{migrant mixing coefficient}.

\subsection{Pros and cons}
Advantages of this strategy are:
\begin{itemize}
	\item The communication packet is kept small. The size of the communication packet $s_e=O(X_e)=O(n)$.
	\item No random selection: sending only the allele values for converged genes maximizes the information content of the message. By contrast, nonconverged genes are highly stochastic and therefore contain less information.
	\item The ``communication after convergence'' property is maintained.
\end{itemize}
Disadvantages are:
\begin{itemize}
	\item Dependencies between genes may be broken. It is not unthinkable that alleles might thrive only in the presence of other, not yet converged alleles on other genes. If these thriving alleles were to be sent to another deme without the alleles on which they depend, they might cause a degradation of solution quality in the recipient deme. This issue may be addressed by tuning the epoch thresholds $X_0$ and $Y_0$.
	\item If $\mu$ is too small, migrant alleles might not be given a chance to survive in the recipient demes, making the communication futile.
	\item If $\mu$ is too low, migrant alleles might ``kill'' promising alleles in the recipient deme, and information may be lost.
	\item If no further convergence (or worse, divergence) occurs in a deme after it has communicated, the deme will never reach its next epoch threshold and will continue to operate in isolation, only accepting migrants and never sending any. This problem can be alleviated by imposing a limit on the number of generations a deme may execute while waiting for the next epoch; if this limit is reached, the deme will send out migrants regardless of the number of converged genes. In this case, the number of alleles in the communication packet may be (even significantly) lower than $X_e$, since there is no guarantee for the number of converged alleles.
\end{itemize}

\subsection{Parameters of PSG}
The algorithm inherits the following parameters from its sequential version:
\begin{enumerate}\compactlist
	\item Number of genes $n$.
	\item Number of alleles per gene $a_i$, total number of alleles $\Sigma a$.
	\item Tournament reward $\epsilon$
	\item \texttt{convergenceThreshold}, the probability level at which convergence is flagged.
	\item Mutation rate $\rho$.
\end{enumerate}
The parallel implementation introduces the following new parameters:
\begin{enumerate}[resume]\compactlist
	\item Number of processors $p$.
	\item Degree $\delta$.
	\item Epoch thresholds $X_0$ and $Y_0$.
	\item Migrant mixing coefficient $\mu$.
	\item Epoch length modifier $\gamma$.
	\item \texttt{epochGenerationLimit}, the maximal number of generations in one epoch.
	\item Various implementation-specific parameters, such as how often to check for incoming messages, when to terminate execution, etc.
\end{enumerate}

\section{Self-adaption}
\label{sec:SelfAdaption}
One of the drawbacks of heuristic methods such as evolutionary algorithms is the high number of parameters to tune. The principle of self-adaption attempts to reduce this number by providing mechanisms by which the algorithm can set its own parameters without the need for human involvement.

Self-adaption has its roots in the field of evolutionary strategies. Just as an evolutionary strategies algorithm intelligently finds optimal parameters for its problem domain, so too are the parameters of the algorithm itself adapted to maximize the algorithm's utility. In \cite{back92,back96}, Thomas B{\"a}ck examines the ways self-adaption mechanisms can be used for the mutation rate of genetic algorithms.

\subsection{Methods of self-adaption}
All self-adaption mechanism are based on the notion that there is an indirect link between favorable control parameters and the fitness values of individuals. Three distinct methods exist:
\begin{enumerate}\compactlist
	\item Deterministic self-adaption
	\item Dynamic self-adaption
	\item Dynamic self-adaption by genome encoding
\end{enumerate}

\subsubsection*{Deterministic self-adaption}
The simplest way of implementing self-adaption is by introducing a deterministic function $\rho(n,t,T)$ which generates a time-dependent schedule for the mutation rate $\rho$ according the chromosome length $n$, the number of generations $t$, and some predefined generation limit $T$. In \cite{back96}, an example of such a function is given as:
\begin{equation}
	\rho(n,t,T) = \left( 2 + \frac{n-2}{T-1}t \right)^{-1}
	\label{eq:BackSelfAdaption}
\end{equation}
Despite its simplicity, the deterministic schedule was found to give better results than a dynamic self-adaption method.

\subsubsection*{Dynamic self-adaption}
Dynamic self-adaption relies on feedback information from the algorithm to adjust its mutation rate. Generally, the average fitness in the population is tracked, but other runtime metrics are also used. A common practice is to let each individual maintain its own mutation rate. Due to the difficulties of constructing a mapping between individuals and populations on one side and mutatation rates on the other, new parameters have to be introduced that govern this mapping. This of course undermines one of the main reasons for using self-adaption: the reduction in input parameters.

\subsubsection*{Dynamic self-adaption by genome encoding}
A novel approach that has not seen much analysis involves letting the algorithm set its mutation rate using the algorithm's own principles of natural selection. In this method, mutation rates are appended to the problem domain's chromosome and evolved along with the solutions to the problem. The aim of the mechanism is to exploit the correlation between optimal control parameters and individual fitness.

\subsection{Self-adaption in PEA's}
In \cite{skinner04}, Skinner et al.\ describe an island model PEA featuring self-adaption. Their algorithm uses a synchronous migration strategy, migrating individuals between demes when all demes have executed a preset number of generations $E$. Following the observation that deterministic self-adaption gives the best results, they adapted B{\"a}ck's \autoref{eq:BackSelfAdaption}, with $E$ substituted for the generation limit.
\begin{equation}
	\rho(n,t,E,l) = \left( \frac{n \cdot l}{20} +  \frac{2 \cdot n \cdot l}{E-1}t \right)^{-1}
	\label{eq:SkinnerSelfAdaption}
\end{equation}
where $l$ denotes the number of bits used to encode each gene.

Results of their experiment were favorable, although it should be noted that no comparison was made between the algorithm's performance using self-adaption and its performance using other means of setting $\rho$.

\subsection{Self-adaption in PSG}
\label{sec:SelfAdaptionPSG}
In PSG, a deterministic self-adaption mechanism is used, based on equations \ref{eq:BackSelfAdaption} and \ref{eq:SkinnerSelfAdaption}. Since the algorithm resembles the steady-state reproduction model and uses an asynchronous migration strategy, the generation limit was eliminated from the function. Instead, SG's notion of convergence is exploited as a promising source of feedback, using the assumption that there is a correlation between the level of convergence and solution quality. Letting $c \leq n$ denote the number of converged alleles in the deme, the mutation probability may be calculated as follows:
\begin{equation}
	\rho(n,c,t)=\left(2+\frac{n-2}{n}c+\frac{f(t)}{n}\right)^{-1}
\end{equation}
where $f(t)$ is an (as yet unknown) function of $t$. In order to find $f(t)$, experimental analysis was used. It was found that $f(t)=\Theta(t)$ caused the mutation rate to drop too quickly, whereas $f(t)=\Theta(\log t)$ had the opposite effect of the mutation rate showing very little time-dependence. As a compromise, a function $f(t)=\omega(\log t)=o(t)$ was needed, which led to the following final formula for the mutation rate schedule:
\begin{equation}
	\rho(n,c,t)=\left(2+\frac{n-2}{n}c+\frac{\sqrt{t}}{n}\right)^{-1}
	\label{eq:PsgSelfAdaption}
\end{equation}
