\LargeNeutrality: A Necessity for Self-Adaptation
\normalsize Marc Toussaint\qquad Christian Igel
\abstractsize Institut f\"ur Neuroinformatik
Ruhr-Universit\"at Bochum
\abstractsize 44780 Bochum
Germany
%47 woerter! Self-adaptation is used in all main paradigms of evolutionary computation to increase efficiency. We claim that the basis of self-adaptation is the use of neutrality. In the absence of external control neutrality allows a variation of the search distribution without the risk of fitness loss. % In this view, there is no doubt about the % benefit of neutral encodings.
cec.tex
\documentclass[10pt,twocolumn]{ijcnn}
\usepackage{amsmath}
\usepackage{epsfig}
\usepackage{wrapfig}
\usepackage{bbm}
\usepackage{psfrag}
\usepackage{mymath}
\usepackage{fancyhdr}
\usepackage[mathscr]{eucal}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
%\newtheorem{important}{}
\newtheorem{corollary}{Corollary}
\newtheorem{proposition}{Proposition}
\newtheorem{definition}{Definition}
\newtheorem{remark}{Remark}
\newtheorem{proposal}{Proposal}
\newenvironment{important}[1]{\noindent\itshape#1}{}

\graphicspath{{/home/proj_vs/SONN/TAoEC/IEEE/}{/home/proj_vs/SONN/TAoEC/}}
\newcommand{\op}[1]{\textit{#1}}
\newcommand{\nn}{{\ensuremath{\mathcal N}}}
\newcommand{\prob}{\ensuremath{p}}
\newcommand{\probdist}{\ensuremath{P}}
\newcommand{\buzz}[1]{\emph{#1}}
\newcommand{\todo}[1]{\texttt{\bf[#1]}}

\newcommand{\GG}{{\mathcal G}}
\newcommand{\PP}{{\mathcal P}}
\newcommand{\RRR}{{\mathbbm R}}
\newcommand{\gp}{\phi}
\newcommand{\EE}{P_\PP}
%\renewcommand{\SS}{{\cal S}}
\newcommand{\m}{\mu}
\renewcommand{\l}{\lambda}
\newcommand{\color}[2][1]{} 

\newenvironment{enum}{
\begin{list}{\arabic{enumi}.}{\usecounter{enumi}\leftmargin10pt\topsep1ex\itemsep1ex}
}{
\end{list}
}

\newcommand{\zv}[1]{{\mathcal #1}}
\newcommand{\zz}[1]{{\mathcal #1}}
\newcommand{\geno}{\ensuremath{{\mathcal G}}}
\newcommand{\pheno}{\ensuremath{{\mathcal P}}}


%\pagestyle{fancy}
\lhead{}
\rhead{\it Proceedings of the Congress on Evolutionary Computation (CEC 2002)}
\cfoot{}
\renewcommand{\headrulewidth}{0pt}


\begin{document}

\title{\Large\textbf{Neutrality: A Necessity for Self-Adaptation}}
\author{\normalsize Marc Toussaint\qquad Christian Igel\\
 \abstractsize Institut f\"ur Neuroinformatik, Ruhr-Universit\"at Bochum\\
\abstractsize 44780 Bochum, Germany\\
\textit{\abstractsize \{\,Marc.Toussaint,Christian.Igel\,\}@neuroinformatik.ruhr-uni-bochum.de}
}
\date{}
\maketitle
\thispagestyle{fancy}

{
\begin{abstract}%47 woerter!
  Self-adaptation is used in all main paradigms of evolutionary
  computation to increase efficiency. We claim that the basis of
  self-adaptation is the use of neutrality. In the absence of external
  control neutrality allows a variation of the search distribution
  without the risk of fitness loss.
% In this view, there is no doubt about the
% benefit of neutral encodings.
\end{abstract}
}





\section{Introduction}

It is well known that the genotype-phenotype mapping in natural
evolution is highly redundant (i.e., the mapping is not injective) and
that neutral variations frequently occur. (A variation is called
neutral if it alters the genotype but not the phenotype of an
individual.) The potential positive effects of neutrality have
extensively been discussed
\cite{conrad:90,huynen:96b,kimura:68,schuster:02} and there is growing
interest in investigating how these results from biology carry over to
evolutionary algorithms (EAs)
\cite{barnett:98,ebner:01,igel:01d,newman:98,shackleton:00,shipman:99,weicker:00}.
However, this dissents with the opinion that redundant
encodings are inappropriate for 
%when investigating neutrality in EAs, one has to argue with
%critics over the possible benefits of a redundant encoding for
\emph{real-world} problems---a bijective genotype-phenotype mapping is
often regarded as a design principle for efficient EAs (e.g., see
\cite{radcliffe:91}).

Unlike neutrality, self-adaptation is an established key concept in
evolutionary computation \cite{baeck:98}. We will point out that
neutrality is a necessity for self-adaptation. And since there is no
doubt about the benefits of self-adaptation for a wide range of
problems, this is a strong argument for the usefulness of neutral
encodings. Our point of view is that, in the absence of external
control, neutrality provides a way to vary the search distribution
without the risk of fitness loss.  We propose to term this way of
adapting the search strategy self-adaptation. This approach
generalizes standard definitions and underlines the central role of
neutrality.

We reconsider two instructive examples from the literature: The first
example is from molecular biology, where it is shown how neutrality
can increase the variability of certain regions in the genome and
conserve the information in other regions.  Using our definition, this
is self-adaptation.  The second one deals with self-adaptation in
evolution strategies, a well-known example of successful
self-adaptation in evolutionary computation.  These algorithms rely on
neutrality to adapt the search strategy and are frequently applied for
solving real-world optimization tasks.

Our arguments are based on recent efforts to provide a unifying view
on the search distribution in evolutionary algorithms and its
\mbox{(self-)}adaptation
\cite{toussaint:01}. 
%They result from an approach to evolutionary systems that is inspired
%by information geometry \cite{amari:00}, which is introduced 
We introduce this formalism in the following section. Section
\ref{selfada} describes the relation between self-adaptation and
neutrality and in section \ref{examples} we present the two examples
to illustrate our ideas.












\section{Modeling evolutionary exploration}\label{model}

In this section, we outline that the individuals in the population,
the genotype-phenotype mapping and the variation operators including
their parameters can be regarded as a parameterization of the search
distribution. This is done in the framework of global random search
and evolutionary optimization, although all considerations can be
transfered to adaptation in natural evolution, see Sec.~\ref{neu}.

Evolutionary algorithms can be considered as a certain class of global
random search algorithms.  Let the search problem under consideration
be described by a quality function $\Phi: \PP \rightarrow \RRR$ to be
optimized. The set $\PP$ denotes the search space.  According to
\cite{zhigljavsky:91}, the general scheme of global random search is
given by:\footnote{This scheme does not account for all kinds of
  evolutionary computation. For example, if the evolutionary
  programming scheme is used, where each parent generates exactly one
  offspring \cite{fogel:95}, or recombination is employed, then the EA
  is better described as operating on a search distribution
  $\probdist^{(t)}_{\PP^\lambda}$ on ${\PP^\lambda}$. However, in
  these cases $\probdist^{(t)}_{\PP}$ can still be derived from
  $\probdist^{(t)}_{\PP^\lambda}$.}
% \footnote{This scheme does not account for all kinds of EAs.
%   For example, if the evolutionary programming \cite{fogel:95} scheme
%   is used, where each parent generates exactly one offspring, then a
%   couple of distributions have to be considered. Hence, we substitute
%   steps \ref{sec:step} and \ref{thr:step} by
% \begin{enum}
% \item[2'.] Obtain points $\vec{g}_1^{(t)},\dots,\vec{g}_{\lambda}^{(t)}$ by
%   taking $\lambda$ samples from the distributions
%   $\probdist^{(t)}_{\PP,i}$, $i\in \{1,\dots,\mu\}$ according to a fixed (algorithm dependent) rule.
%   Evaluate $\Phi$ (perhaps with random noise) at these points.
% \item[3'.] According to a fixed (algorithm dependent) rule construct new
%   probability distributions  $\probdist^{(t+1)}_{\PP,i}$, $i\in \{1,\dots,\mu\}$.
% \end{enum}
% %Without loss of generality, 
% For simplicity, we consider only a single distribution in
% the remainder of the article.
% }
\begin{enum}
\item Choose a probability distribution $\probdist^{(t)}_\PP$ on
  $\PP$.
\item Obtain points $\vec{g}_1^{(t)},\dots,\vec{g}_{\lambda}^{(t)}$ by
  taking $\lambda$ samples from the distribution
  $\probdist^{(t)}_\PP$.\label{sec:step}
  Evaluate $\Phi$ (perhaps with random noise) at these points.
\item According to a fixed (algorithm dependent) rule construct a
  probability distribution $\probdist^{(t+1)}_\PP$ on $\PP$.\label{thr:step}
\item Check for some appropriate stopping condition; if the algorithm has
  not terminated, substitute $t:=t+1$ and return to Step \ref{sec:step}.
\end{enum}
\noindent The core ingredient of this search scheme is the search distribution
$\probdist^{(t)}_\PP$, also called exploration distribution, on the
search space.  Random search algorithms can differ fundamentally in
the way they represent and alter the search distribution.  Typically,
the distribution is represented by a semi-parametric model. The choice
of the model determines the exploration distributions the search
algorithm can represent, which is in general only a small subset of
all possible probability distributions on $\PP$.  For example, let
$\PP = \RRR$. Then the class of representable distributions may be
given by the class of normal densities, $p_\PP(x;m,\sigma) =
\frac{1}{\sqrt{2\pi}\sigma} \exp\left\{ -\frac{(x-m)^2}{2\sigma^2}
\right\}$, where $m$ is the expectation and $\sigma^2$ the variance.
This equation defines a \emph{parameterization} of the search
distribution, it maps the parameters $(m,\sigma)\in\RRR^2$ into the
set of probability distributions on $\PP$ (see Fig.~\ref{huete:fig}).
A global random search algorithm alters its exploration distribution
(see Step \ref{thr:step}) by changing such parameters.

We believe that two of the most fundamental questions in evolution
theory can be stated as:
\begin{enum}
\item How is the exploration distribution parameterized?
\item How is the exploration distribution altered?
\end{enum}
%is to analyze the parameterization of the exploration distribution.
%Looking at evolutionary systems, we can ask:
\noindent 
In the framework of evolutionary systems, we identify each element of
$\PP$ with certain phenotypic traits of individuals and call $\PP$ the
phenotype space. Each phenotype $p$, i.e., element of $\PP$, is
encoded by a genotype $\vec{g}$, which is an element of a genotype
space $\GG$. The mapping $\gp:\GG\to\PP$ is called genotype-phenotype
mapping.  If $\gp$ is not injective we speak of a \emph{neutral}
encoding.  A number of genotypes
$\tilde{\vec{g}}^{(t)}_1,\dots,\tilde{\vec{g}}^{(t)}_\mu$, the
parents, are stored in a population. The superscript indicates the
iteration of the algorithm, i.e., the generation.  In each generation,
$\lambda$ offspring $\vec{g}^{(t)}_1,\dots,\vec{g}^{(t)}_\lambda$ are
generated by applying stochastic and\,/\,or deterministic variation
operators.  Let the probability that parents
$\tilde{\vec{g}}_1,\dots,\tilde{\vec{g}}_\mu\in\GG$ generate an
offspring $\vec{g}\in\GG$ be described by the probability distribution
$P_\GG\left(\vec{g} \;|\; \tilde{\vec{g}}_1, \dots,
\tilde{\vec{g}}_\mu; \vec{\theta}\right)$.  This distribution is
additionally parameterized by some \emph{external strategy parameters}
$\vec{\theta}\in\Theta$.  Examples of such externally controlled
parameters include the probabilities that certain variation operators
are applied and parameters that determine the mutation strength.  We
call the probability
\begin{align}
P_\GG^{(t)}(\vec{g})
  := P_{\GG}\left(\vec{g} \;|\; \tilde{\vec{g}}_1^{(t)}, \dots,
   \tilde{\vec{g}}^{(t)}_\mu ; \vec{\theta}^{(t)}\right)
\end{align}
that in generation $t$ an offspring $\vec{g}$ is created
the \emph{exploration distribution} on $\GG$ at generation $t$.
%\cite{rudolph:94} \todo{was ist mit Rudolph??}.

The genotype-phenotype mapping $\gp$ \emph{lifts} $P_{\GG}^{(t)}$ from
the genotype space onto the phenotype space:
\begin{align}\label{neuset}
\forall p\in \PP:~ \EE^{(t)}(p)
 = \sum_{\vec g' \in \gp^{-1}(p)} P_\GG^{(t)}(\vec g') \;,
\end{align}
where $\gp^{-1}(p):=\{\vec g' \in \GG \;|\; \gp(\vec g')=p\}$ is
called the \emph{neutral set} of $p\in \PP$ \cite{schuster:96}. Thus,
the genotype space $\GG$ together with the genotype-phenotype mapping
$\gp$, the variation operators, and external parameters $\vec\theta$
can be regarded as a parameterization of the exploration distribution
on the search space $\PP$.  We refer to \cite{toussaint:01} for more
details on this way of formalizing evolutionary exploration.

Also algorithms recently developed in the field of evolutionary
computing can be captured by this point of view: M\"uhlenbein et
al.~\cite{muehlenbein:99} and Pelikan et al.~\cite{pelikan:00}
parameterize the exploration density by means of a Bayesian dependency
network in order to introduce correlations in the exploration
distribution. The CMA evolution strategy proposed by Hansen and
Ostermeier \cite{hansen:01} adapts a covariance matrix that describes
the dependencies between real-valued variables in the exploration
density. In the remainder of this paper, we focus on a different
approach that might be considered biologically more plausible, namely
to utilize an appropriate genotype-phenotype mapping to parameterize
the exploration density $\EE$. It does not explicitly encode
correlations but models such interactions indirectly via the
genotype-phenotype mapping. What we will ask for in the next section
is the way it allows for self-adaptation of the exploration strategy.


% In an evolutionary algorithm, the update of the search distribution
% in Step \ref{thr:step} is realized by changing the exploration
% distribution in the genotype space.  This distribution changes if

% \smallskip\begin{enumerate}\itemsep1ex
% \item the population varies, or
% \item $P_{\mathcal
% G}^{(t)}$ varies by altering $\vec{\theta}^{(t)}$, or
% \item the genotype-phenotype mapping $\gp$ varies (also by external
%   control).
% \end{enumerate}\smallskip
% \noindent

% In this paper, we are interested in changes of the search distribution
% on a short time-scale and without external control (i.e., a mechanisms
% beside the variation and selection process). Hence, we presume
% that $\vec{\theta}^{(t)}$ and the genotype-phenotype mapping
% are fixed. Trivially, if the genotype-phenotype mapping is injective
% every variation of the genotypes within the population alters 
% the composition of phenotypes in the population. Hence,
% under the assumptions stated above it holds:







\section{Self-adaptation}\label{selfada}

\subsection{Introduction}\label{selfintro}

The ability of an evolutionary algorithm to adapt its search strategy
during the optimization process is a key concept in evolutionary
computation, see the overviews \cite{angeline:95,smith:97,eiben:99}.
Online adaptation of strategy parameters is important, because the
best setting of an EA is usually not known \emph{a priori} for a given
task and a constant search strategy is usually not optimal during the
evolutionary process. One way to adapt the search strategy online is
self-adaptation, see \cite{baeck:98} for an overview.  This method can
be described as follows \cite{eiben:99}: ``The idea of the evolution
of evolution can be used to implement the self-adaptation of
parameters. Here the parameters to be adapted are encoded into the
chromosomes and undergo mutation and recombination. The better values
of these encoded parameters lead to better individuals, which in turn
are more likely to survive and produce offspring and hence propagate
these better parameter values.''  In other words, each individual
not only represents a candidate solution for the problem at hand, but
also certain strategy parameters that are subject to the same
selection process---they hitchhike with the object parameters.
 
Self-adaptation is used in all main paradigms of evolutionary
computation.  The most prominent examples stem from evolution
strategies, where it is used to adapt the covariance matrix of the
mutation operator, see Sec.~\ref{es:sec}.  Self-adaptation is
employed in evolutionary programming for the same purpose, but also in
the original framework of finite-state machines \cite{fogel:95b}.  In
genetic algorithms, the concept of self-adaptation has been used to
adapt mutation probabilities \cite{baeck:92b} and crossover operators
\cite{schaffer:87}.  Self-adaptive crossover operators have also been
investigated in genetic programming \cite{angeline:96b}. In the
following, we will propose an alternative definition of
self-adaptation, which includes these approaches as special cases.





\subsection{Neutrality and self-adaptation}\label{neu}

Following the formalism we developed in the previous section, a
variation of the exploration density $\EE^{(t)}$, corresponding to
Step \ref{thr:step} in the global random search algorithm, occurs if
\begin{enum}
\item the parent population $(\tilde{\vec g}_1^{(t)}, \dots,
  \tilde{\vec g}_\mu^{(t)})$ varies, or
\item the external strategy parameters $\vec\theta^{(t)}$ vary, or
\item the genotype-phenotype mapping $\gp$ varies.
% (by external  control).
\end{enum}
\noindent 
From a biological point of view, one might associate environmental
conditions (like the temperature, etc.) with external parameters that
vary the mutation probabilities or the genotype-phenotype mapping. In
most cases one would not consider them as subject to
evolution.\footnote{Counter-examples that go far beyond the scope of
  our formalism are, for instance, the embryonic environment (uterus)
  and the inherited ovum, or individuals whose behavior have an
  influence on mutations (e.g., sexual behavior influencing crossover)
  or on the embryonic development (e.g., a mother taking drugs). All
  of these influences might be considered as subject to evolution.  In
  particular the interpretation of an ovum is a critical issue.
  Should one regard it as part of the genotype or as an inherited
  ``parameter'' of the genotype-phenotype mapping?} Sometimes
mechanisms that adapt the exploration distribution by genotype
variations are regarded as examples of adaptive genotype-phenotype
mappings. To our minds, this is a misleading point of view.  For
example, \mbox{t-RNA} determines a part of the genotype-phenotype
mapping and it is itself encoded in the genome.  However, the
genotype-phenotype mapping should be understood as a whole---mapping
all the genotype (including the parts that code for the t-RNA) to the
phenotype, such that it becomes inconsistent to speak of genotypic
information parameterizing the genotype-phenotype mapping.

The same arguments also apply in the context of evolutionary
computation and thus we consider only option 1 as a possibility to
vary the exploration distribution in a way that is itself subject to
evolution in the sense of section \ref{selfintro}. However, if the
genotype-phenotype mapping is injective, every variation of genotypes
alters phenotypes and bears the risk of a fitness loss. Hence, we
conclude:

\smallskip \emph{In the absence of external control, only neutral
  genetic variations can allow a self-adaptation of the exploration
  distribution without changing the phenotype, i.e., without the risk of
  loosing fitness.} \smallskip

\noindent A \emph{neutral genetic variation} means that parent and offspring
have the same phenotype. For instance, consider two genotypes
$\tilde{\vec g}_1$, $\tilde{\vec g}_2$ in a neutral set. Neglect
crossover and assume that the probability for an offspring $\vec g$ of
a single parent $\tilde{\vec g}_i$ is given by $P_\GG(\vec g \;|\;
\tilde{\vec g}_i;\vec\theta)$. The two genotypes may induce two
arbitrarily different exploration distributions ``around'' the same
phenotype $p=\gp(\tilde{\vec g}_1)=\gp(\tilde{\vec g}_2)$, see
Fig.~\ref{strategy}. Transitions between these genotypes allow for
switching the exploration strategy. In general, the variety of
exploration densities that can be explored in a neutral set
$\gp^{-1}(p)$ is given by
\begin{align}
\big\{ P_\PP(p \;|\; \tilde{\vec g}_i;\vec\theta) \;\big|\; \tilde{\vec g}_i \in
 \gp^{-1}(p) \big\} \;.
\end{align}

\begin{figure}[t]\center
  \input{strategy}
\caption{
  Two different points $\tilde{\vec g}_1,\tilde{\vec g}_2$ in $\GG$
  are mapped onto the same point in $\PP$. The elliptic ranges around
  the points illustrate the exploration distributions by suggesting
  the range of probable mutants.  Thus, the two points $\tilde{\vec
    g}_1,\tilde{\vec g}_2$ belong to one neutral set but represent two
  different exploration strategies on the search space $\PP$.}
\label{strategy}
\end{figure}




\subsection{Discussion}

It is widely accepted that changing the genotypes without
significantly changing the phenotypes in the population is a key
search strategy in natural evolution
\cite{huynen:96b,kimura:68,schuster:02}. We emphasize that under the
stated assumptions, neutrality is even a necessity for self-adaptation
of the search strategy. Thus, we propose to \emph{define
  {self-adaptation} as the use of neutrality in order to vary the
  exploration strategy}.






% \smallskip
% \begin{enumerate}\topsep3ex\itemsep1ex
% \item Under the stated assumptions, neutrality is a necessity 
% for this kind of search strategy.
% \item 
% \end{enumerate}
% \smallskip





% {
% The core ingredient of any general search algorithm (\emph{global
%   random search} \cite{zhigljavsky:91}), including evolutionary
% algorithms as a special case, is an exploration (probability) density
% $\EE$ on the search space $P$. From this density $\l$ samples (the
% offspring) are drawn and evaluated. And based on this evaluation, the
% exploration density is updated.

% It is highly remarkable that the design evolutionary algorithms as
% described in the literature is often dominated by the question of how
% to choose an appropriate parameterization of the exploration density.
% What exactly do we mean by this? Evolutionary algorithms store a
% variable (traditionally a population vector of phenotypic parents
% $(p_1,..,p_\m) \in P^\m$) to specify the exploration density
% $\EE^{(t)}$ for the new offspring.  When the offspring is drawn we
% assume that the environment (the problem at hand) provides the
% selection density $\SS^{(t)}$ on the set of this offspring. This
% selection density may account for any kind of selection rule
% (fitness-proportional, rank-based, etc.) or any kind of coevolutionary
% interaction. Note that the selection of new parents from the offspring
% according to $\SS^{(t)}$ can be interpreted as a way to approximate
% $\SS^{(t)}$ by $\EE^{(t+1)}$. In fact, what is captured under the
% keyword \emph{stochastic universal sampling} is just this aim to
% minimize the Kullback-Leibler divergence between $\EE^{(t+1)}$ and
% $\SS^{(t)}$. This \emph{natural update rule} where $\EE^{(t+1)}$ is a
% best possible approximation of $\SS^{(t)}$ (or at least a better one
% than $\EE^{(t)}$ was) is a general concept of evolutionary algorithms:
% In \cite{toussaint:01} we showed that also modern sophisticated
% algorithms can be reduced to this point of view. For example, Pelikan
% et al.~\cite{pelikan:00} parameterized the exploration density by
% means of a Bayesian dependency network. The update rule is directly
% given by the goal to minimize the divergence between $\EE^{(t+1)}$ and
% $\SS^{(t)}$.  In \cite{hansen:01}, the exploration density is
% parameterized by means of a center of mass and a covariance matrix.
% The update rule may be interpreted as a step-wise relaxation of
% $\EE^{(t+1)}$ towards $\SS^{(t)}$. Our point is that the choice of the
% parameterization of the exploration density actually becomes the
% central concern when designing an evolutionary algorithm because it
% naturally (assuming some kind of natural update rule) decides on the
% dynamics of the evolutionary search.

% In this paper we are concerned with a special kind of parameterizing
% the exploration density. We consider a genotype-phenotype mapping
% $\gp:\, G \to P$ that is used to lift an exploration density
% $\tilde\EE$ on the genotype space $G$ onto the search space:
% \begin{align}
% \forall p\in P:~ \EE(p) = \sum_{g' \in \gp^{-1}(p)} \tilde \EE(g') \;,
% \end{align}
% where $\gp^{-1}(p):=\{g' \in G | \gp(g')=g\}$ is called the
% \emph{neutral set} of $p\in P$. In a shorter notation we write
% Eq.~(\ref{neuset}) as $\EE=\tilde\EE \circ \gp^{-1}$. Further, the
% exploration density on the genotype space is parameterized by a
% population of genotypic parents $(g_1,..,g_\m) \in G^\m$. For each
% genotype $g_i$, mutation operators (and eventually crossover operators
% depending on the rest of the population) define the individual's
% exploration density $\tilde\EE_{g_i}$ such that
% \begin{align}
% \tilde\EE =& \frac{1}{\m} \sum_i \tilde\EE_{g_i} \;,\quad\text{and}\\
% \EE =& ~\tilde\EE \circ \gp^{-1}=\frac{1}{\m} \sum_i (\tilde\EE_{g_i}\circ \gp^{-1})
% \end{align}
% This approach to parameterize the exploration density $\EE$ is
% different to the ones I mentioned above \cite{pelikan:00,hansen:01}.
% It does not explicitly encode correlations or covariance matrices but
% models such interactions indirectly via the genotype-phenotype mapping.
% It might be considered biologically more plausible. But what we ask is
% if this approach is general enough to model complex exploration
% strategies on the search space and if it allows for mutative
% self-adaptation. Concentrating on a single parent $g_i$, what are---in
% principle---the possibilities for a variation of its exploration
% density $\EE_{g_i}=\tilde\EE_{g_i}\circ \gp^{-1}$?
% \begin{enumerate}
% \item Either the parent $g_i\in G$ itself varies, or,
% \item in case of crossover, the rest of the population varies, or
% \item the mapping $g_i \mapsto \tilde \EE_{g_i}$ varies (by externally
%   controlled variations of mutation operators), or
% \item the genotype phenotype mapping $\gp$ varies (also by external
%   control).
% \end{enumerate}
% The idea of a variable genotype-phenotype mapping has been discussed
% in some places \cite{wagner:96,altenberg:?}. Similarly, the
% formulation proposed by Eiben et al.~\cite{eiben:99} uses the notion
% of ``adaptive codings''. However, we find that these points of view
% are unsatisfactory and formally and biologically not of help (see
% \cite{toussaint:01} for a critique). We interpret the last two options
% as an external variation of the environment which will not be
% considered here. Thus, only options 1 and 2, i.e., genotypic
% variations are of interest here. However, in the case that these
% variations are not neutral, they bear the risk of a fitness loss.
% Consequently, and this is the central and simple statement we argued
% for, \emph{only a neutral genetic variation can cause a variation of
%   the exploration density without changing the phenotype, i.e.,
%   without a risk of loosing fitness. Neutrality is the core ingredient
%   of mutative self-adaptation.}

% This statement is in no way a critique of existing approaches to
% mutative self-adaptation. in evolutionary computation. Rather, we want
% to embed these approaches in this point of view.


Existing approaches to self-adaptation developed in the realm of
evolutionary computation can be embedded in this point of view; only
the \emph{style} in which the notion of self-adaptation was originally
introduced is different. Usually one refers to ``strategy parameters''
that typically control the mutation operators (i.e., the mapping
$\tilde{\vec g}_i \mapsto P_\GG(\vec g \;|\; \tilde{\vec
  g}_i;\theta)$), in contrast to ``object parameters'' describing
fitness relevant traits.  In the case of \emph{self}-adaptation these
strategy parameters are considered as parts of the genotype. In this
view, strategy parameters are neutral, i.e., altering them does not
change the phenotype.  In turn, we regard neutral genotypic variables
as potential strategy parameters. There still is a slight difference:
In case of standard self-adaptation, altering a strategy parameter is
phenotypically neutral and has no other implication than a change of
the exploration strategy. In contrast, two or more genetic variables
may be phenotypically non-neutral but a specific simultaneous mutation
of them might be neutral and induce a change of the exploration
density.  Hence, a neutral set is a general concept for
self-adaptation, which is not bound to the idea of single loci being
responsible for the search strategy. A good example is that also
topological properties of the search space (i.e., neighborhood
relations/the set of most probable mutations of a phenotype) may vary
along such a neutral set if the genotype-phenotype mapping is chosen
similar to grammars \cite{toussaint:01}---which seems hard to realize
by explicit strategy parameters.

We believe that allowing for a self-adaptive exploration strategy is
the main benefit of neutral encodings, as stated in
\cite{shackleton:00}: ``For redundancy to be of use it must allow for
mutations that do not change the current phenotype, thus maintaining
fitness, and which allow for moves to areas where new phenotypes are
accessible''.  Changing the exploration distribution corresponds to
the ability of reaching new phenotypes.\footnote{However, we think
  that there might be at least one additional case where neutrality
  can be useful, namely when it introduces---\emph{by chance}---a bias
  in the search space, such that desired phenotypes are (in global
  average) represented more often than other ones \cite{igel:01d}.}

In this view, neutrality is not necessarily \emph{redundant}:
Different points in a neutral set can encode different exploration
strategies and thus different information; a genotype encodes not only
the information on the phenotype but also information on further
explorations. One might state it like this: Although a non-injective
genotype-phenotype mapping can be called redundant, the corresponding
mapping from genotype to exploration distribution may in general be
non-redundant.


%The following examples will substantiate these concepts.



% \newcommand{\EV}{\FF} \newcommand{\EX}{\EE}

% We start by defining some basic concepts capable to unify all these
% different approaches to self-adaptation. In general we assume that the
% task is to find an element $p$ in a phenotype space $P$ that is
% ``superior'' to all other points in $P$. Here, superiority is defined
% in terms of a fitness distribution given by problem at hand. If $P$ is
% too large to evaluate the quality of all $p \in P$, the strategy is to
% explore only a few points $(p_1,..,p_\l)$, evaluate their quality, and
% then try to extract information on where to perform further
% explorations. We capture this view on evolutionary search in an
% abstract formalism that is capable to unify the different specific
% approaches. Below, we exemplify each step of the scheme by embedding
% the Simple Genetic Algorithm (SGA) \cite{vose:99} in the formalism.
% See also figure \ref{evoalg}.

% \begin{definition}(Evolutionary exploration)
% \vspace{-\topsep}\vspace{-\parskip}
% \begin{enumerate}
% \item The information maintained during evolutionary search is given
%   by a time-dependent variable $q^{(t)} \in Q$ that uniquely defines
%   an \intro{exploration density} $\EE_{q^{(t)}}$ on $P$. Here, we call
%   $\EE$ the \intro{exploration model}, actually a map from $Q$ to the
%   space $\L^P$ of densities over $P$. In general, the variety
%   $\EX_Q=\{\EX_q\, |\, q \in Q \}$ of representable densities is
%   limited.

%   {\rm Typically, the variable $q^{(t)}$ is a population of
%     individuals and probably some extra "`global"' parameters that
%     specify the exploration density. The reason we have not introduced
%     $q^{(t)}$ as a population vector right from start is that in
%     general, in particular in the case of crossover, the exploration
%     density depends on the whole population and cannot be represented
%     as a simple superposition of individual exploration densities.}

% \item Given $q^{(t)}$, exploration starts by choosing $\l$ samples
%   $s^{(t)}_{i=1..\l}$ of the exploration density. We use brackets to
%   indicate this sampling:
% \begin{align}
% s^{(t)}=[\EX_{q^{(t)}}]_\l \in P^\l \;.
%   \end{align}

%   {\rm Here and in the following, we disregard the possibility of
%     elitists.  Taking them into account would require to append
%     selected points $(p_1,..,p_\m)$ of $P$ to $s^{(t)}$,
% \begin{align}
% s^{(t)}=[\EX_{q^{(t)}}]_\l \oplus (p_1,..,p_\m) \in P^{\m+\l} \;.
%   \end{align}
%   }


% \item We require the existence of an \intro{fitness distribution}
%   $\EV:\, P^\l \to \L^P$ that maps the exploration sample
%   $(s_1,..,s_\l)$ to a density over $P$ with support
%   $\{s_1,..,s_\l\}$. This evaluation is applied to our exploration
%   samples:
% \begin{align}
% \EV_{s^{(t)}} = \EV\big( [\EX_{q^{(t)}}]_\l \big) \in \L^P \;.
%   \end{align}

%   {\rm We introduce this generalized notion of a fitness to allow for
%     all kinds of fitness evaluations---also coevolutionary.}


% \item Finally, there exists an \intro{law of adaption}
% \begin{align}
% A:\, q^{(t)} \times \EV_{s^{(t)}} \mapsto q^{(t+1)} \;.
%   \end{align}
%   In general, this operator is supposed to exploit the information in
%   $\EV_{s^{(t)}}$.
% \end{enumerate}
% \end{definition}
% }
%














\section{Examples}\label{examples}

\subsection{Codon Bias in natural evolution}

An intriguing study of the interrelationship between neutrality and
self-adaptation in nature is the one by Stephens and Waelbroeck
\cite{stephens:99}. They empirically analyze the codon bias and its
effect in RNA sequences of the HI virus. In biology, several
nucleotide triplets eventually encode the same amino acid. For
example, there are 9 triplets that are mapped to the amino acid
Arginine. If Arginine is encoded by the triplet CGA, then the chance
that a single point mutation within the triplet is neutral (does not
chance the encoded amino acid) is $4/9$. In contrast, if it is encoded
by AGA, then this \emph{neutral degree} is $2/9$. Now, codon bias
means that, although there exist several codons that code for the same
amino acid (which form a neutral set), HIV sequences exhibit a
preference on which codon is used to code for a specific amino acid.
More precisely, at some places of the sequence codons are preferred
that are ``in the center of this neutral set'' (with high neutral
degree) and at other places codons are biased to be ``on the edge of
this neutral set'' (with low neutral degree).  It is clear that these
two cases induce different exploration densities; the prior case means
low mutability whereas the latter means high mutability. Stephens and
Waelbroeck go further by giving an explanation for these two
(marginal) exploration strategies: Loci with low mutability cause
``more resistance to the potentially destructive effect of mutation'',
whereas loci with high mutability might induce a ``change in a
neutralization epitope which has come to be recognized by the
[host's] immune system'' \cite{stephens:99}.



% Because of the redundancy of the triplet code, genotypes can evolve
% that contain regions where neutral mutations are more likely than in
% other ones.  Let us define $P_{\text{missense}}$ as the probability
% that a single point mutation of a triplet changes the amino acid the triplet
% encodes.  For example, there are 9 triplets that are mapped to the
% amino acid Arginine.  If Arginine is encoded by the sequence CGA, then
% $P_{\text{missense}} = 2/3$. In contrast, if it is encoded by AGA,
% then $P_{\text{missense}} = 8/9$.



\subsection{Self-adaptation in evolution strategies}\label{es:sec}

% \cite{schwefel:77,rechenberg:94,schwefel:95}.
In this section, we describe a rather simple example of
self-adaptation in evolution strategies.\footnote{More sophisticated
  and efficient algorithms exist for dealing with real-world
  optimization tasks, e.g., the derandomized adaptation as proposed
  in \cite{hansen:01,ostermeier:95}.} The candidate solutions for the
problem at hand are represented by real-valued vectors $\vec{x}\in
{\mathcal P}={\mathcal G}\subseteq{\mathbbm R}^n$. These real-valued
object parameters are mutated by adding a realization of a normally
distributed random vector with zero mean
\cite{rechenberg:94,schwefel:95}. The symmetric $n\times n$ covariance
matrix of this random vector is subject to self-adaptation.  To
describe any possible covariance matrix, $n(n+1)/2$ strategy
parameters are needed. However, often a reduced number of parameters
is used. In the following, let the covariance matrix be given by
$(\vec{\sigma} I)^2$, where $I=\operatorname{diag}(1,\dots,1)$ is the
identity matrix and $\vec{\sigma}\in{\mathbbm R}^n$ corresponds to $n$
strategy parameters that describe the standard deviations along the
coordinate axes.

Let $\mu$ denote the size of the parent population.  Each generation,
$\lambda$ offspring $\vec g_i^{(t)}$, $i=1,\dots,\lambda$ are
generated.  $(\mu,\lambda)$-selection is used, i.e., the $\mu$ best
individuals of the offspring form the new parent population.
% $\tilde{\vec{g}}_i^{(t+1)}$, $i=1,\dots,\mu$.  
An individual $\vec g_i^{(t)}
\in {\mathbbm R}^{2n}$ can be divided into two parts, $\vec g_i^{(t)}
= (\vec x_i^{(t)} , \vec \sigma_i^{(t)})$, the object variables $\vec
x_i^{(t)} \in {\mathbbm R}^n$ and the strategy parameters $\vec
\sigma_i^{(t)} \in {\mathbbm R}^n$.

For each offspring $\vec{g}_i^{(t)}$, two indices
$a,b\in\{1,\dots,\mu\}$ are selected randomly, where $a$ determines
the parent and $b$ its mating partner.  For each component
$k=1,\dots,n$ of the offspring, the new standard deviation $\vec
\sigma_i^{(t)}=(\sigma_{i,1}^{(t)},\dots,\sigma_{i,n}^{(t)})$ is
computed as
\begin{equation}\label{sigma:eq}
\sigma_{i,k}^{(t)}
 = \frac{1}{2}\left[\tilde{\sigma}_{a,k}^{(t)}+\tilde{\sigma}_{b,k}^{(t)} \right]
 \cdot \exp\left(\tau' \cdot \xi_i^{(t)} + \tau \cdot \xi_{i,k}^{(t)}\right)
%\quad,\quad{\xi}^{(t)},{\xi}^{(t)}_i\sim\zz{N}({0}, 1)
\enspace.
\end{equation}
Here, $\xi_{i,k}^{(t)} \sim \zz{N}({0}, 1)$ is a realization of a
normally distributed random variable with zero mean and variance one
that is sampled anew for each component $i$ for each individual,
whereas $\xi_i^{(t)} \sim \zz{N}({0}, 1)$ is sampled once per
individual and is the same for each component.  The log-normal
distribution ensures that the standard deviations stay positive. For
the mutation strengths $\tau\propto 1/\sqrt{2\sqrt{n}}$ and
$\tau'\propto 1/\sqrt{2{n}}$ are recommended
\cite{schwefel:95,baeck:98}.  It has been shown that recombination of
the strategy parameters is beneficial (e.g., \cite{kursave:99}).
Equation (\ref{sigma:eq}) realizes an intermediate recombination of
the strategy parameters.

Thereafter the objective parameters 
%$\vec x_i^{(t)} = (x_{i1}^{(t)},\dots,x_{in}^{(t)})$ 
are altered using the new strategy parameters:
\begin{equation}
%x_i^{\text{offspring}} = (x_{i}^{mum}+x_{i}^{dad})+ \textbf{N}_i(0,\sigma_i^{\text{offspring}})
x_{i,k}^{(t)}
 = \tilde{x}_{a,k}^{(t)} + \sigma_{i,k}^{(t)}\, z_{i,k}^{(t)},
\end{equation}
where $z_{i,k}^{(t)}\sim\zz{N}({0}, 1)$.  For simplicity, we do not
employ recombination of the objective parameters.  An example of this
strategy compared to algorithms without self-adaptation is shown in
Fig.~\ref{average:fig}.  The adaptive strategy performs considerably
better than the other methods, as known from many theoretical results
and empirical studies. However, we would like to underline that the
self-adaptive EA uses a highly redundant encoding instead of a
one-to-one genotype-phenotype mapping---the genotype space has twice
the dimensionality of the phenotype space. The neutrality does not
alter the distribution of the fitness values, it just allows the
search strategy to adapt.


% Again, global intermediate
% recombination is used, $\left<\vec x\right>_\mu^{(t)} :=
% \frac{1}{\mu} \sum_{i=1}^\mu \vec x_i^{(t)} $, see \cite{beyer:95b}
% for a theoretical analysis of this mutation operator.
\begin{figure}
\psfrag{Psearch}[r][r]{\small $P_{\mathcal G}=P_{\mathcal P}$}
\psfrag{Pindiv}[r][r]{\small offspring distributions around single individuals}
\psfrag{0.5}[r][r]{\small 0.5}
\psfrag{0.45}[r][r]{\small }
\psfrag{0.4}[r][r]{\small 0.4}
\psfrag{0.35}[r][r]{\small }
\psfrag{0.3}[r][r]{\small 0.3}
\psfrag{0.25}[r][r]{\small }
\psfrag{0.2}[r][r]{\small 0.2}
\psfrag{0.15}[r][r]{\small }
\psfrag{0.1}[r][r]{\small 0.1}
\psfrag{0.05}[r][r]{\small }
\psfrag{-10}[][]{\small -10}
\psfrag{10}[][]{\small 10}
\psfrag{5}[r][r]{\small 5}
\psfrag{-5}[r][r]{\small -5}
\psfrag{0}[r][r]{\small 0}
\centerline{\includegraphics[width=.95\columnwidth]{huete.eps}}
\caption{\label{huete:fig}
  An example for parameterizing the exploration distribution in
  evolution strategies: Consider the search space $\PP=\RRR$, $\mu =
  3$ parent individuals, and no recombination. The parents represent
  the object parameters $-2$, $-0.25$, and $3.5$. The offspring is
  generated in the following manner: First, one randomly chosen parent
  is reproduced.  Second, the reproduced individual is mutated by
  adding a realization of a normally distributed random number with
  variance one and expectation zero.  Hence, the resulting search
  distribution (the joint generating distribution
  \protect\cite{rudolph:94}) is a multimodal mixture of Gaussians. }
\end{figure}





% The examples given demonstrate the benefit of neutrality as the basis
% for self-adaptation.\todo{da muss noch was}
 
% It can be argued that these
% steps are a kind of continuous counterpart of the transitions prominent
% in evolutionary systems where evolution occurs along neutral networks.



\begin{figure}
\small
\input cec.frag
%\begin{center}
\hfill\epsfig{file=ada.eps, width=.9175\columnwidth}\hspace{1ex}

\hfill\epsfig{file=ada_single.eps, width=.95\columnwidth}\hspace{1ex}
%\end{center}

\caption{\label{average:fig}As an example, we compare
  evolution strategies as described in Sec.~\ref{es:sec} with and
  without self-adaptation on a simple test problem: a 100-dimensional
  sphere model, $\Phi(\vec{x})=||\vec{x}||$.  First, the EA is run
  without self-adaptation, each $\sigma_i$ is set to one.  After that,
  we employ self-adaptation as described, where the $\sigma_i$ are
  also initialized to one.  Based on these results, we determine the
  average standard deviation $\sigma^\dagger$ (averaged over all
  parents, all generations, and all trials).  Then we repeat the
  experiments without
  self-adaptation but fix each $\sigma_i=\sigma^\dagger$.
%
  The fitness trajectories of the best individual averaged over 50
  trials are shown in the upper plot ($\sigma^\dagger=0.0125$). 
%
  In case of the self-adaptive EA the fitness curves show steps.  The
  lower plot shows a typical single trial and the corresponding
  average of the standard deviations
  $||\left<\vec{\sigma}\right>_\mu^{(t)}||= \Big(\sum_{j=1}^n\left(
  \frac{1}{\mu}\,\sum_{i=1}^\mu \sigma_{i,j} \right)^2\Big)^{1/2}$.
  It becomes obvious that each step in the fitness trajectory
  corresponds to a change in the search strategy. In general, the
  mutation strength decreases, but sometimes a larger step size takes
  over the population and leads to a high
  fitness gain.
%
  In the continuum, the
  probability that an offspring has exactly the same phenotype, i.e.,
  represents the same object parameters, is not measurable. Further,
  even small changes in the genotype are relevant for selection due to
  the use of a rank-based selection scheme.  Hence, \emph{drifting}
  along a \emph{neutral network}, i.e., traversing the search space by a
  sequence of (\emph{neutral}) mutations that do not alter the
  phenotype, does not occur.
%
 }
\end{figure}









\section{Conclusion}

Neutrality is a necessity for self-adaptation. Actually, the design of
neutral encodings to improve the efficiency of evolutionary algorithms
is a well-established approach: strategy parameters are an example of
neutrality. Hence, there already exists clear evidence for the benefit
of neutrality.

The notion of neutrality provides a unifying formalism for embedding
approaches to self-adaptation in evolutionary computation. But it also
inspires new approaches that are not bound to the idea of only single
genes being responsible for the exploration strategy.  Generally, any
local properties of the phenotypic search space---metric or
topological---may vary along a neutral set. An example are
grammar-based genotype-phenotype mappings, for which different points
in a neutral set represent completely different topologies (and thus
exploration strategies) on the phenotype space.

On the other hand, the benefits of neutrality in {natural}
evolution can be better understood when the simple---but concrete and
well-established---paradigms of self-adaptation and neutrality in
evolutionary computation are taken into account. As we exemplified
with the second example, these computational approaches may serve as a
model to investigate the relation between evolutionary progress,
neutrality, and self-adaptation.

Finally, let us recall that neutrality is not necessarily equivalent
to redundancy: in general, a genotype encodes not only the information
on the phenotype but also information on further explorations.



\subsection*{Acknowledgments}
The authors acknowledge support by the
DFG under grant Solesys SE 251/41-1.



{ \small 
\bibliographystyle{abbrv} 
\bibliography{cec02,phd,mt} 
}
\end{document}


strategy.tex
\includegraphics[bb=0 1 -2 0]{strategy.eps}
\setlength{\unitlength}{2368sp}%
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
\begin{picture}(6002,1888)(-600,-1637)
\put(1201,-1561){\makebox(0,0)[b]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$\GG$}%
}}}
\put(3601,-1561){\makebox(0,0)[b]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$\PP$}%
}}}
\put(2401,-1561){\makebox(0,0)[b]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$\stackrel{\gp}\longrightarrow$}%
}}}
\put(301,-136){\makebox(0,0)[rb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$\tilde{\vec g}_1$}%
}}}
\put(301,-886){\makebox(0,0)[rb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$\tilde{\vec g}_2$}%
}}}
\put(301,-1186){\makebox(0,0)[rb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$P_\GG(\vec g|\tilde{\vec g}_2;\vec\theta)$}%
}}}
\put(301,-436){\makebox(0,0)[rb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$P_\GG(\vec g|\tilde{\vec g}_1;\vec\theta)$}%
}}}
\put(4501, 14){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$\gp(\tilde{\vec g}_1)=\gp(\tilde{\vec g}_2)$}%
}}}
\put(4501,-511){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$P_\PP(p|\tilde{\vec g}_1;\vec\theta)$}%
}}}
\put(4501,-1036){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$P_\PP(p|\tilde{\vec g}_2;\vec\theta)$}%
}}}
\end{picture}
\setlength{\unitlength}{1pt}

cec.bbl
\begin{thebibliography}{10}

\bibitem{angeline:95}
P.~J. Angeline.
\newblock Adaptive and self-adaptive evolutionary computations.
\newblock In M.~Palaniswami, Y.~Attikiouzel, R.~Marks, D.~B. Fogel, and
  T.~Fukuda, editors, {\em Computational Intelligence: A Dynamic Systems
  Perspective}, pages 152--163. IEEE Press, 1995.

\bibitem{angeline:96b}
P.~J. Angeline.
\newblock Two self-adaptive crossover operations for genetic programming.
\newblock In P.~Angeline and K.~Kinnear, editors, {\em Advances in Genetic
  Programming}, volume~2, Cambridge, MA, 1996. MIT Press.

\bibitem{baeck:92b}
T.~B{\"a}ck.
\newblock Self--adaptation in genetic algorithms.
\newblock In F.~J. Varela and P.~Bourgine, editors, {\em Towards a Practice of
  Autonomous Systems: Proceedings of the First European Conference on
  Artificial Life}, pages 263--271. MIT Press, 1992.

\bibitem{baeck:98}
T.~B\"ack.
\newblock An overview of parameter control methods by self-adaptation in
  evolutionary algorithms.
\newblock {\em Fundamenta Informaticae}, 35(1-4):51--66, 1998.

\bibitem{barnett:98}
L.~Barnett.
\newblock Ruggedness and neutrality --{T}he {NKp} family of fitness landscapes.
\newblock In C.~Adami, R.~K. Belew, H.~Kitano, and C.~E. Taylor, editors, {\em
  Alive VI: Sixth International Conference on Articial Life}, pages 18--27. MIT
  Press, 1998.

\bibitem{conrad:90}
M.~Conrad.
\newblock The geometry of evolution.
\newblock {\em Biosystems}, 24:61--81, 1990.

\bibitem{ebner:01}
M.~Ebner, P.~Langguth, J.~Albert, M.~Shackleton, and R.~Shipman.
\newblock On neutral networks and evolvability.
\newblock In {\em Proceedings of the 2001 Congress on Evolutionary
  Computation}, pages 1--8. IEEE Press, 2001.

\bibitem{eiben:99}
A.~E. Eiben, R.~Hinterding, and Z.~Michalewicz.
\newblock Parameter control in evolutionary algorithms.
\newblock {\em IEEE Transactions on Evolutionary Computation}, 3(2):124--141,
  1999.

\bibitem{fogel:95}
D.~B. Fogel.
\newblock {\em Evolutionary Computation: Toward a New Philosophy of Machine
  Intelligence}.
\newblock IEEE Press, 1995.

\bibitem{fogel:95b}
L.~J. Fogel, P.~J. Angeline, and D.~B. Fogel.
\newblock An evolutionary programming approach to self-adaptation on finite
  state machines.
\newblock In J.~R. McDonnell, R.~G. Reynolds, and D.~B. Fogel, editors, {\em
  Proceedings of the Fourth Annual Conference on Evolutionary Programming},
  pages 355--365. MIT Press, 1995.

\bibitem{hansen:01}
N.~Hansen and A.~Ostermeier.
\newblock Completely derandomized self-adaptation in evolution strategies.
\newblock {\em Evolutionary Computation}, 9(2):159--195, 2001.

\bibitem{huynen:96b}
M.~A. Huynen.
\newblock Exploring phenotype space through neutral evolution.
\newblock {\em Journal of Molecular Evolution}, 43:165--169, 1996.

\bibitem{igel:01d}
C.~Igel and P.~Stagge.
\newblock Effects of phenotypic redundancy in structure optimization.
\newblock {\em IEEE Transactions on Evolutionary Computation}.
\newblock In press.

\bibitem{kimura:68}
M.~Kimura.
\newblock Evolutionary rate at the molecular level.
\newblock {\em Nature}, 217:624--626, 1968.

\bibitem{kursave:99}
F.~Kursawe.
\newblock {\em {Grundlegende empirische Untersuchungen der Parameter von
  Evolu\-tions\-strategien --- Metastrategien}}.
\newblock Dissertation, Fachbereich Informatik, Universit{\"a}t Dortmund, 1999.

\bibitem{muehlenbein:99}
H.~M\"uhlenbein, T.~Mahnig, and A.~O. Rodriguez.
\newblock Schemata, distributions and graphical models in evolutionary
  optimization.
\newblock {\em Journal of Heuristics}, 5(2):215--247, 1999.

\bibitem{newman:98}
M.~E.~J. Newman and R.~Engelhardt.
\newblock Effects of neutral selection on the evolution of molecular species.
\newblock {\em Proceedings of the Royal Society of London, Series B: Biological
  Sciences}, 265(1403):1333--1338, 1998.

\bibitem{ostermeier:95}
A.~Ostermeier, A.~Gawelczyk, and N.~Hansen.
\newblock A derandomized approach to self-adaptation of evolution strategies.
\newblock {\em Evolutionary Computation}, 2(4):369--380, 1995.

\bibitem{pelikan:00}
M.~Pelikan, D.~E. Goldberg, and E.~Cant\'u-Paz.
\newblock Linkage problem, distribution estimation, and bayesian networks.
\newblock {\em Evolutionary Computation}, 9:311--340, 2000.

\bibitem{radcliffe:91}
N.~J. Radcliffe.
\newblock Equivalence class analysis of genetic algorithms.
\newblock {\em Complex Systems}, 5:183--205, 1991.

\bibitem{rechenberg:94}
I.~Rechenberg.
\newblock {\em Evolutionsstrategie '94}.
\newblock Werkstatt Bionik und Evolutionstechnik. Frommann-Holzboog, Stuttgart,
  1994.

\bibitem{rudolph:94}
G.~Rudolph.
\newblock Massively parallel simulated annealing and its relation to
  evolutionary algorithms.
\newblock {\em Evolutionary Computation}, 1(4):361--382, 1994.

\bibitem{schaffer:87}
J.~D. Schaffer and A.~Morishima.
\newblock An adaptive crossover distribution mechanism for genetic algorithms.
\newblock In J.~J. Grefenstette, editor, {\em Proceedings of the Second
  International Conference on Genetic Algorithms and Their Applications
  (ICGA'87)}, pages 36--40. Lawrence Erlbaum Associates, 1987.

\bibitem{schuster:02}
P.~Schuster.
\newblock Molecular insights into evolution of phenotypes.
\newblock In J.~P. Crutchfield and P.~Schuster, editors, {\em Evolutionary
  Dynamics---Exploring the Interplay of Accident, Selection, Neutrality and
  Function}, Santa Fe Institute Series in the Science of Complexity. Oxford
  University Press.
\newblock To appear.

\bibitem{schuster:96}
P.~Schuster.
\newblock Landscapes and molecular evolution.
\newblock {\em Physica D}, 107:331--363, 1996.

\bibitem{schwefel:95}
H.-P. Schwefel.
\newblock {\em Evolution and Optimum Seeking}.
\newblock Sixth-Generation Computer Technology Series. John Wiley \& Sons, New
  York, 1995.

\bibitem{shackleton:00}
M.~A. Shackleton, R.~Shipman, and M.~Ebner.
\newblock An investigation of redundant genotype-phenotype mappings and their
  role in evolutionary search.
\newblock In A.~Zalzala, C.~Fonseca, J.-H. Kim, and A.~Smith, editors, {\em
  Proceedings of the International Congress on Evolutionary Computation (CEC
  2000)}, pages 493--500. IEEE Press, 2000.

\bibitem{shipman:99}
R.~Shipman.
\newblock Genetic redundancy: {D}esirable or problematic for evolutionary
  adaptation.
\newblock In M.~A. Bedau, S.~Rasmussen, J.~S. McCaskill, and N.~H. Packard,
  editors, {\em Proceedings of the 4th International Conference on Artificial
  Neural Networks and Genetic Algorithms (ICANNGA)}, pages 337--344.
  Springer-Verlag, 1999.

\bibitem{smith:97}
J.~E. Smith and T.~C. Fogarty.
\newblock Operator and parameter adaptation in genetic algorithms.
\newblock {\em Soft Computing}, 1(2):81--87, 1997.

\bibitem{stephens:99}
C.~R. Stephens and H.~Waelbroeck.
\newblock Codon bias and mutability in {HIV} sequences.
\newblock {\em Journal of Molecular Evolution}, 48:390--397, 1999.

\bibitem{toussaint:01}
M.~Toussaint.
\newblock Self-adaptive exploration in evolutionary search.
\newblock Technical Report IRINI 2001-05, Institut f\"ur Neuroinformatik,
  Lehrstuhl f\"ur Theoretische Biologie, Ruhr-Universit\"at Bochum, 44780
  Bochum, Germany, 2001.

\bibitem{weicker:00}
K.~Weicker and N.~Weicker.
\newblock Burden and benefits of redundancy.
\newblock In {\em Proceedings ot the Sixth Workshop on Foundations of Genetic
  Algorithms}, 2000.

\bibitem{zhigljavsky:91}
A.~A. Zhigljavsky.
\newblock {\em Theory of global random search}.
\newblock Kluwer Academic Publishers, 1991.

\end{thebibliography}
