%% LyX 1.6.4.1 created this file. For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[11pt,oneside,english]{amsbook}
\usepackage[T1]{fontenc}
\usepackage[latin9]{inputenc}
\usepackage[letterpaper]{geometry}
\geometry{verbose,tmargin=1in,bmargin=1.5in,lmargin=1.5in,rmargin=1in,headheight=0in,headsep=0in,footskip=0.5in}
\pagestyle{plain}
\usepackage{verbatim}
\usepackage{float}
\usepackage{amsthm}
\usepackage{amsbsy}
\usepackage{amstext}
\usepackage{graphicx}
\usepackage{setspace}
\usepackage{amssymb}
\usepackage{esint}
\usepackage[authoryear]{natbib}
\doublespacing
\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
%% Because html converters don't know tabularnewline
\providecommand{\tabularnewline}{\\}
%% A simple dot to overcome graphicx limitations
\newcommand{\lyxdot}{.}
\floatstyle{ruled}
\newfloat{algorithm}{tbp}{loa}
\floatname{algorithm}{Algorithm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
\numberwithin{section}{chapter}
\numberwithin{equation}{section} %% Comment out for sequentially-numbered
\numberwithin{figure}{section} %% Comment out for sequentially-numbered
\newenvironment{lyxcode}
{\par\begin{list}{}{
\setlength{\rightmargin}{\leftmargin}
\setlength{\listparindent}{0pt}% needed for AMS classes
\raggedright
\setlength{\itemsep}{0pt}
\setlength{\parsep}{0pt}
\normalfont\ttfamily}%
\item[]}
{\end{list}}
\theoremstyle{plain}
\newtheorem{thm}{Theorem}
\theoremstyle{plain}
\newtheorem{lem}[thm]{Lemma}
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\theoremstyle{plain}
\newtheorem{prop}[thm]{Proposition}
\newcounter{casectr}
\newenvironment{caseenv}
{\begin{list}{{\itshape\ Case} \arabic{casectr}.}{%
\setlength{\leftmargin}{\labelwidth}
\addtolength{\leftmargin}{\parskip}
\setlength{\itemindent}{\listparindent}
\setlength{\itemsep}{\medskipamount}
\setlength{\topsep}{\itemsep}}
\setcounter{casectr}{0}
\usecounter{casectr}}
{\end{list}}
\theoremstyle{plain}
\newtheorem{cor}[thm]{Corollary}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\usepackage{amssymb}
\usepackage{graphics}
\usepackage{afterpage}
% Allow empty pages before chapters (i.e. no page numbers)
\makeatletter
\let\origdoublepage\cleardoublepage
\newcommand{\clearemptydoublepage}{%
\clearpage
{\pagestyle{empty}\origdoublepage}%
}
\let\cleardoublepage\clearemptydoublepage
\makeatother
\newcommand{\rtrans}[3][m] { \ensuremath{ \,{}^{\mathcal{#2}}\!\!\rightarrow_{#1}^{\mathcal{#3}} } }
\newcommand{\ltrans}[3][m] { \ensuremath{ \,\,{}_{#1}^{\mathcal{#2}}\!\!\leftarrow^{\mathcal{#3}} } }
\newcommand{\modn}[1] { \ensuremath{ \mathrm{mod}\,#1 } }
\usepackage{subfig}
\makeatother
\usepackage{babel}
\begin{document}
\begin{doublespace}
\noindent \input{approval.tex}
\end{doublespace}
\noindent \begin{center}
\textbf{\Huge \thispagestyle{empty} Biological Simulations and Biologically
Inspired Adaptive Systems \vspace*{2.5in}
}
\par\end{center}{\Huge \par}
\begin{doublespace}
\noindent \begin{center}
{\Large A Dissertation}\\
{\Large Presented for the}\\
{\Large Doctor of Philosophy}\\
{\Large Degree}\\
{\Large The University of Tennessee, Knoxville}
\par\end{center}{\Large \par}
\noindent \begin{center}
\textbf{\Huge \vspace*{2.5in}
}
\par\end{center}{\Huge \par}
\noindent \begin{center}
{\Large Edgar Alfredo Duenez-Guzman}\\
{\Large December, 2009}
\par\end{center}{\Large \par}
\end{doublespace}
\newpage{}
\pagenumbering{roman} \setcounter{page}{1}
\chapter*{Acknowledgments}
I would like to thank everyone who helped me complete my Doctor of
Philosophy degree in Computer Science. I specially wish to thank Dr.
Michael D. Vose for his invaluable guidance, patience and encouragement,
and for always being a cultivating figure for me. My deepest gratitude
to Dr. Sergey Gavrilets for introducing me to theoretical biology
and employing me for most of my degree. Also my gratitude to Dr. Bruce
MacLennan and Dr. Mongi Abidi for serving on my committee.
I would also like to thank the members of the Gavrilets' Lab for all
the engaging science conversations and useful criticisms. Special
thanks to Dr. Suzanne Sadedin, Dr. Francisco \'Ubeda de Torres, Dr.
Aysegul Birand and Ivan Juric for their comments on my dissertation.
\chapter*{Abstract}
Many of the most challenging problems in modern science lie at the
interface of several fields. To study these problems, there is a pressing
need for trans-disciplinary research incorporating computational and
mathematical models. This dissertation presents a selection of new
computational and mathematical techniques applied to biological simulations
and problem solving: (i) The dynamics of alliance formation in primates
are studied using a continuous time individual-based model. It is
observed that increasing the cognitive abilities of individuals stabilizes
alliances in a phase transition-like manner. Moreover, with strong
cultural transmission an egalitarian regime is established in a few
generations. (ii) A putative case of hybrid speciation in three species
of \emph{Heliconius }butterflies is studied using a spatial, genetically
explicit, individual-based simulation. Given the ecological and selective
pressures observed, the hybrid origin of \emph{Heliconius heurippa}
is supported by the model. However, the coexistence of the parental
species and the hybrid species is only transient in the simulation.
(iii) Optimization and computational techniques were developed during
the implementation of a model of adaptive radiation in \emph{Anolis}
lizards. An efficient and accurate numerical integration routine was
developed and a parallel implementation was ran on \emph{Kraken},
Cray's XT5 supercomputer. These procedures improved the simulation's
running time by several orders of magnitude. (iv) Optimizations, both
in execution time and memory usage, are proposed for some genetic
operators extensively used in evolutionary algorithms and biological
simulations. Speed-up ranging from two-fold to several orders of magnitude
is achieved. A statistical analysis was conducted to ensure the reliability
of the methods. (v) \emph{No-Free-Lunch} (NFL) theorems are theoretical
results concerning the performance of heuristic optimization algorithms.
The characterization of function sets for which the \emph{Focused
NFL }theorem holds is shown. A generalization of NFL results to random
algorithms is proven, as well as a new NFL theorem for random algorithms
over arbitrary benchmarks.
\tableofcontents{}
\listoffigures
\pagenumbering{arabic} \setcounter{page}{1}
\chapter{Introduction}
Ongoing advances in science and technology help solve problems of
higher complexity and broader scope than ever before. In particular,
many of the most challenging problems in modern science lie at the
interface of several fields. There is a pressing need for trans-disciplinary
research to tackle these problems. This is especially true at the
interface of computer science, mathematics and biology. Complex interactions
in biological systems occur at many different scales, from temporal
and spatial to hierarchical; understanding their behaviors from the
interactions of agents requires the development of specialized mathematical,
quantitative and computational models. These models assist in better
understanding of the mechanisms that led nature to its present state
and in formulating more accurate predictions on how it may evolve
in the future.
The explosive growth in computer technology opens a window to create
more realistic simulations, both in scale and complexity, in attempting
to answer long-standing questions in all fields of scientific research.
Breakthroughs in science frequently occur through the use of strong
mathematical foundations and ambitious computer models that push the
limits on even the fastest super-computers available. Analytical models
are used to study systems in which direct experimentation is unfeasible
due to constraints, be they logistic, ethical or budgetary \citep{pec04}.
In addition, simulation are frequently used when analytical models
are unable to capture the behaviors observed in a complex system.
However, simulations can also be used to study complex process, like
adaptation, on their own without having to target a specific system
\citep{hol92}. Because of its ability to approximate analytical solutions,
explore statistical properties and capture real-world systems, simulation
has been argued to be the most efficient way to analyze biological
complex systems \citep{pec04,axe06}. Indeed, models have been used
extensively to understand numerous processes in biology, for example
by \citet{axe84,kon86a,dij94,moo94,mcc95,sad03,dug04b,gav07a,gav07b,sad08,thi08}.
Moreover, simulations, in particular agent-based models, have been
suggested as a shared unifying ground among disciplines. \citet{axe06}
argues that not only do agent-based models prove useful in understanding
systems for which mathematical analyses are intractable, but also
provide grounds on which scientists from different fields can collaborate.
and in doing so, parallels among diverse disciplines can be found,
explored and understood.
There is usually a trade-off when faced with the choice of analyzing
a system through simulation or analytical methods. While simulation
usually studies problems through more realistic techniques, results
are more difficult to interpret and a complete understanding of the
dynamics is usually impossible to guarantee. Because of these drawbacks,
it is important to not succumb to the temptation to forfeit analytical
studies \citep{gav03d}. There is still much to learn from both approaches,
but most importantly, it is crucial to not think of problem solving
through modeling with the exclusive view of either analytical or else
numerical modeling. We find ourselves in a time in which simulation
and analytical approaches benefit from each other, and ultimately
together solve challenging problems that would otherwise be intractable.
On one hand, simulations can be used to assess if the behaviors observed
in analytical models generalize to more complex or realistic scenarios.
On the other hand, analytical studies can be used to verify general
patterns observed in numerical simulations \citep{gav03d}.
Biologically inspired computation has been successfully applied to
problems in a wide range of fields like pattern recognition and learning
\citep{sch92,yao98,fog06}, optimization \citep{gol89,hol91,eib03},
image processing \citep{bha99}, structure design \citep{quer98},
and many more. \citet{fog06} makes a case that the path to robust
machine learning or artificially intelligent systems is not through
the traditional approach of expert systems, analytical optimization
algorithms, or other knowledge-based approaches. The original attempts
at creating artificial intelligence sought to leverage general-purpose
problem solving algorithms. Over the course of two decades, and due
primarily to the difficulties faced with developing and integrating
such general algorithms, research in artificial intelligence narrowed
considerably \citep{wat85}.
As an alternative to expert systems, \citet{fog06} argues that since
all learning processes are adaptive, it is only through simulation
of adaptive processes in a computer that one can develop an intelligent
algorithm. Furthermore, he maintains that adaptation achieved by evolution
is analogous to the scientific method, where each individual constitutes
a set of hypotheses about their environment, and only those individuals
with the appropriate set of hypotheses survive. Therefore, for \citet{fog06},
simulating evolution constitutes the first step in the direction of
developing truly adaptive algorithms for problem solving.
This dissertation contributes to science and technology at the interface
of several fields by presenting a selection of new computational and
mathematical techniques applied to biological simulations and problem
solving. The simulations are presented in order of increasing realism
which entails increasing mathematical and computational complexity.
Chapters \ref{cha:allies} and \ref{cha:hybrids} present two case
studies illustrating how simulation leads to better understanding
of biological systems. Chapter \ref{cha:cug} develops mathematical
and computational techniques which enable a complex biological system
to be simulated within realistic time and computing constraints. Increasing
model realism, in particular, involves simulating genetics. Chapter
\ref{cha:crossmut} provides a widely applicable optimized implementation
of genetic operators assisting in the creation of realistic biological
simulations and efficient implementations of evolutionary algorithms.
This optimized implementation is accompanied by a statistical analysis
to ensure qualitative correctness and numerical stability. Finally,
Chapter \ref{cha:nfl} explores abstract properties of heuristic optimization
algorithms, and in particular evolutionary algorithms. Figure \ref{fig:intro}
schematically shows the chapters in this dissertation and their natural
inter-relationships from the perspective of computer science, mathematics
and biology.
%
\begin{figure}[t]
\hfill{}\includegraphics[width=3in]{Figures/intro}\hfill{}
\caption[~~~Representation of the natural inter-relationships of the chapters
in the dissertation]{\label{fig:intro} Representation of the natural inter-relationships
of the chapters in the dissertation. The figure shows schematically
the bearing of the chapters from the perspective of computer science,
mathematics and biology.}
\end{figure}
An overview of Chapters \ref{cha:allies} to \ref{cha:nfl} follow.
\subsubsection*{Dynamics of alliance formation and the egalitarian revolution}
The evolution of humans, and in particular the differences between
humans and other greater primates, has fascinated researchers ever
since Darwin's \emph{The origin of species}, and perhaps even earlier.
Arguably the most influential force in human history is the formation
of social coalitions and alliances (i.e. long-lasting coalitions)
and their impact on individual power \citep{har92,cha95}. Understanding
the dynamics of alliance formation and its consequences for biological,
social, and cultural evolution is a formidable theoretical challenge.
In most great ape species, coalitions occur at individual and group
levels and among both kin and non-kin. Nonetheless, ape societies
remain essentially hierarchical, and coalitions rarely weaken social
inequality. In contrast, human hunter-gatherers show a remarkable
tendency to egalitarianism, and human coalitions and alliances occur
not only among individuals and groups, but also among groups of groups
\citep{boe99,pan03}. These observations suggest that the evolutionary
dynamics of human coalitions can only be understood in the context
of social networks and cognitive evolution.
Only in the last few decades has attention turned to social interactions
and cooperation through competition as the initial causes of the evolutionary
transition to modern humans. This is known as the \emph{social brain
}hypothesis, also known as the \emph{Machiavellian intelligence} hypothesis
\citep{byr88,whi97}. A theoretical study of this hypothesis was conducted
by \citet{gavr06}, but its effect on social structure of early hominids
was not assessed. Chapter \ref{cha:allies} presents an individual-based,
continuous time stochastic model without genetics. The model aims
to understand the emergence of networks of allies resulting from within-group
competition for status or mates between individuals utilizing dyadic
information.
\subsubsection*{Hybrid speciation in butterflies in a jungle}
While plausible explanations for the evolution of humans and other
historical biological processes are important for understanding the
current world, the other crucial aspect of science is its ability
to extrapolate current knowledge and create predictions on the future
behavior of present systems. Of increasing interest in biology is
the process of speciation, and in particular the role that ecology
plays in it. This has lead to a new focus on \emph{ecological speciation}
\citep{may47,run05,schl00}, which is defined as speciation driven
by ecologically based divergent selection. Another novel development
is a resurrection of arguments about the role of hybridization in
speciation and adaptive radiation \citep{arn97,bul94,gom06,mal07,see04}.
In particular \emph{homoploid hybrid speciation} (i.e. speciation
through hybridization without change in the number of chromosomes),
is receiving renewed interest and new empirical and theoretical support.
Arguably the most convincing case of homoploid hybrid speciation in
animals \citep{mav06} is theoretically studied in Chapter \ref{cha:hybrids}.
The proposed model is spatial, individual-based, with non-overlapping
generations and explicit genetics.
\subsubsection*{Simulating population genetics on the XT5}
Individual-based biological simulations with spatial layouts involve
the simulation of millions of individuals explicitly. Such a simulated
space contains over a thousand patches, each one containing thousands
of individuals and run for hundreds of thousands of simulated generations.
Within a patch, a simulated generation typically requires a number
of operations that scales like the square of the local population
size to complete. Such quadratic complexity comes from the evaluation
of non-random-mating, and sometimes also from viability selection
comprising the effects of between-individual competition. In some
simulations, however, the computation of mate choice or viability
can be very expensive, driving the total execution time to the order
of years or decades even when run on the fastest supercomputers. In
these cases, we require the development of optimized algorithms for
mate choice and viability to allow the simulation to run in reasonable
time. In Chapter \ref{cha:cug} we present the steps implemented in
order to optimize a model of adaptive radiation in \emph{Anolis} lizards
both from the point of view of the mathematical tools required and
from the practical restructuring of the simulation to run it in one
of the biggest super computers in the world: \emph{Kraken}, a Cray
XT5 at the National Institute for Computational Sciences in Oak Ridge
National Lab. We discuss the lessons learned from the computational
challenges encountered, and describe how we have dealt with them within
the constraints presented by time and hardware.
\subsubsection*{Efficient implementation of crossover and mutation operators}
The genetic operations of recombination, mutation, inversion, translocation,
and more, are other potential bottlenecks of genetically explicit
simulations and genetic algorithms. From these operators, probably
the most widely used are recombination (also called \emph{crossover})
and mutation. Chapter \ref{cha:crossmut} offers an efficient implementation
(both in terms of memory and speed) of several variants of recombination
and mutation, based on the work of \citet{vos99}. In addition, a
statistical analysis compared against a straightforward implementation
is conducted. This analysis proves the correctness and numerical stability
of the efficient implementation, at least from a statistical point
of view.
\subsubsection*{No free lunch on random algorithms}
Without question, optimization is central to much of human activity.
Due to the complexity of certain optimization problems, a plethora
of heuristic optimization algorithms have been suggested by many researchers.
Real-world systems exhibit properties like robustness, efficiency,
adaptiveness, or self organization. Biologically inspired methods
have been proposed in the hope that such properties could be captured
and would, thus, help in solving complex or computationally intractable
problems \citep{eib03,fog06,gol89,hol91,hol92,sch92}. In particular,
biological evolution has been used as a model to construct algorithms
for problem solving.
Genetic Algorithms have been traditionally regarded as general purpose
optimization techniques, and much has been argued about their performance
and suitability when compared with other optimization techniques,
including specialized algorithms, enumeration, and random walks \citep{gol89}.
Nonetheless, the theoretical basis for heuristic optimization algorithms,
especially those simulating evolutionary processes, has received relatively
small attention considering the number of heuristic algorithms suggested
with little or no theoretical framework to support them. One of the
best known approaches to studying search algorithms theoretically
is the \emph{No free lunch }concept and its associated theorems\emph{
}\citep{wol97}. After the original formulation of these theorems,
several researchers have questioned their applicability to real world
problems \citep{dom98,dro99,aug07,mar09} and have proposed scenarios
where NFL theorems would not hold \citep{whi99a}. Several generalizations
and extensions have been proposed aimed to relax the assumptions required
for the theorems to hold \citep{sch01,schu00,ige04,whi08,row09}.
These generalizations have created their own round of articles concerning
the applicability of these new theorems \citep{ige01}. In Chapter
\ref{cha:nfl} an extension of existing NFL theorems is proposed,
as well as a new result concerning truly random search algorithms.
One of the strongest arguments against NFL applicability is the requirement
of special classes of functions \citep{ige01}. The new result removes
these restrictions by studying average performance of algorithms over
given benchmarks.
\include{allies}
\include{hybrids}
\include{cug}
\include{genetics}
\include{nfl}
\chapter{Conclusions}
Computer science is a relatively new science. While in its early days,
it was almost exclusively concerned with problem solving, over time
it has acquired more and more a specialized body of research. Applications
of computer science to biology are also relatively new, and there
is still ample opportunity for research in this area. The contributions
presented here range from the development of custom made simulations
of specific biological systems to the theoretical study of black-box
optimization algorithms and their limitations.
The model presented in Chapter \ref{cha:allies} shows that alliances
often emerge in a phase transition-like fashion if the group size,
awareness, aggressiveness, and persuasiveness of individuals are large
and the decay rate of individual affinities is small. With cultural
inheritance of social networks, a single leveling alliance including
all group members can emerge in several generations. Our results suggest
that a rapid transition from a hierarchical society of great apes
to an egalitarian society of hunter-gatherers (often referred to as
\textquotedblleft{}egalitarian revolution\textquotedblright{}) could
indeed follow an increase in human cognitive abilities. The establishment
of stable group-wide egalitarian alliances creates conditions promoting
the origin of cultural norms favoring the group interests over those
of individuals. %
\begin{comment}
we made minimum assumptions about cognitive abilities of individuals.
In particular, we did not require them to be able to identify the
best coalitionary strategies, no cultural beliefs. Early stages, low
levels of cognitive abilities, absence of culture and traditions (which
should be included into any discussions of both modern societies -
experimental economics, and modern hunter-gatherers local information,
psychology of learning of main goal: over-riding alpha-males rather
than free-riders.
\end{comment}
{}
In Chapter \ref{cha:hybrids} we analyzed a case of hybrid speciation
in butterflies. Although our results are based on numerical simulations
tailored to this particular case, some of the relevant ecological,
spatial and behavioral features of Heliconius are shared with other
suggested cases of homoploid hybrid speciation, which might expand
the generality of our conclusions. For instance, several instances
of animal homoploid hybrid taxa also appear sympatric with at least
one parental species (e.g. Pogonomyrmex, \citealp{sch07}; Daphnia,
\citealp{tay05}; Papilio, \citealp{scr05}. See review in \citealp{mav08}).
In addition, it has been suggested that some forms of pre-zygotic
barriers such as assortative mating might play an important role during
homoploid hybrid speciation (Xiphophorus, \citealp{mey06}) and our
study provides strong support to this idea. On the other hand, most
animal homoploid hybrid taxa appear morphologically closer to one
parental species (see supporting material in \citealp{mav08}), which
has been interpreted as evidence for extensive backcrossing during
speciation. Our study also supports this idea and therefore suggests
that reproductive isolation might be a non-immediate consequence of
hybridization that can evolve after many generations of genetic exchange
between parental forms. However, the \emph{Heliconius }case is unique
in that the genetic architecture of the traits considered is relatively
well known, which justifies some of the choices taken during the implementation
of our model, but that reduces its generality. For example, \emph{Heliconius}
might be unusual in that single (or simple) traits such as color patterns
play such an important and simultaneous role in survival and mating
\citep{kap01,jig01,mal89a,mav06}. Current evidence suggests that
this kind of {}``magic traits'' are clearly not very common in nature
\citep{gav04}, not even among putative hybrid homoploid taxa. %
\begin{comment}
Because of the expected evolution of colors, preferences, habitat
utilization and genetic incompatibilities in the simulations, the
long-term coexistence of the three species is not expected, nor observed.
The strong directional selection for the fixation of a color allele
hints that, at least phenotypically, the three species cannot be preserved.
Convergence of wing patterns through Mullerian mimicry appears to
be the most significant driving force in this case. This situation
is similar with the sex chromosome and autosome dynamics. Selection
of fully reproductively compatible individuals prevents the existence
of populations with (partial) incompatibilities.
On the other hand, the genetic nature of the reproductive incompatibilities
and linkage between preference and color patterns are only starting
to be understood. Further studies on these mechanisms would provide
a more reliable understanding of how the evolution is driven. This,
together with a deeper understanding of role and intensity of predation
by birds, would certainly allow us to more accurately understand the
future development of these and potentially other species of \emph{Heliconius}
butterflies.
\end{comment}
{}
Large scale numerical simulations present computational challenges
at several different levels. When standard techniques and the computational
power available are not enough to solve the problem at hand, specific
optimizations need to be performed. Finding and removing bottlenecks
of algorithms is required in order to fit realistic computational
constraints. Some techniques used to address these challenges range
from pre-computation, lazy evaluation and the creation of equivalence
classes to the usage of different patterns of communication in multi-processor
supercomputers. Moreover, computer simulations involving numerical
integration typically rely upon subroutines from sources such as the
GNU Scientific Library, Netlib, or the Numerical Algorithms Group.
Routines are often quadrature based and employ acceleration heuristics
based on linear or nonlinear sequence transformations. Most accept
user specified limits on absolute and relative error. The underlying
assumptions are violated in practice, however. Subroutines may return
an incorrect result accompanied by a small error estimate, telling
the caller that the incorrect result should be trusted. Chapter \ref{cha:cug}
presented a case study where both, optimization of algorithm bottlenecks
and development of more accurate numerical integration routines, resulted
in the possibility of analyzing a numerical simulation that would
have been otherwise impossible to run under realistic time and technological
constraints.
Another example of the development of algorithm optimizations tailored
for biological simulations as well as evolutionary algorithms was
presented in Chapter \ref{cha:crossmut}. In this case, a general
framework for optimizing both the memory requirements and the execution
time of genetic operators is discussed. In addition, specific implementations
of extensively used genetic operators are given, their performance
compared against a straightforward implementation and their correctness
is assessed via a statistical analysis. While the algorithmic complexity
of the operators is not improved, the proposed implementations are
found to outperform the straightforward ones by factors ranging from
two to over ten. The discrepancy in speed-up and memory efficiency
is due to the inherent differences in the operators, as well as their
parameters. Furthermore, the techniques and specific implementations
proposed have already been incorporated by several studies of speciation
\citep{gav07a,gav07b,due09}.
Contrary to early biological intuition, evolutionary processes are
not inherently optimization processes. The traditional view of {}``the
survival of the fittest'' was held and even analytically proved in
some models (notably by Fisher and Wright in the early 1930s, and
later revisited by Kimura in the 1950s). It was not until \citet{mor64}
proved that the fitness maximization principle doesn't hold in general
that this view started to dissipate. Even close to a decade after,
however, researchers still attempted to find circumstances under which
fitness was maximized in a population. The justification being that
under fitness maximization principles, mathematical tools of optimization
would be applicable and yield insight on the evolution of a system
\citep{dea73}.
The value of biologically inspired computation lies not in evolution
being a general purpose optimization algorithm. Indeed, under the
light of NFL theories, there is no such algorithm (see Chapter \ref{cha:nfl}).
Evolution, however, is not about efficiency but about adaptation to
an ever-changing environment. NFL theorems applied to evolution as
a process is big misconception, to say the least. Fitness in nature
is not an static concept, and it is certainly not a target function
to optimize. Learning and competition among individuals, be they conspecifics
or heterospecific, reshapes the fitness landscape constantly and in
highly complex ways.
As discussed previously, \citet{fog06} considers that simulating
the process of evolution itself is arguably our best attempt at creating
artificial intelligence. The plausibility of this argument relies
in part on the argument that intelligence, like evolution, is not
an optimization process \citep{dre84,fog06}. Moreover, recent decades
have brought an increase in our understanding of the conditions under
which intelligence is likely to evolve \citep{byr88,dun98,byr97,whi97,gavr06},
and the consequences to social structure \citep{gav08}. The importance
of simulating evolutionary processes for computer science has been
taken further, by arguing the incorporation of elements found to be
conducive to the evolution of intelligence in natural populations
\citep{sad09b}.
Computer science, biology and mathematics are in a stage where mutual
beneficial interactions arise in a natural manner. Development of
optimized algorithms and numerical simulations help better understand
biological systems. A better understanding of nature offers new insights
on analytical techniques and stimulate mathematical research. In its
turn, this research offers new perspectives into computer science
theory and applications. The new National Institute for Mathematical
and Biological Synthesis (NIMBioS) is but one example of this trend.
Advances within these disciplines accrue with the collaborations among
them and vice versa.
\newpage{}
\begin{center}
\textbf{\Huge \thispagestyle{empty} }
\par\end{center}{\Huge \par}
\begin{center}
\vspace*{\fill}
\textbf{\LARGE Bibliography}\vfill{}
\par\end{center}
\noindent \begin{center}
\bibliographystyle{plainnat}
\bibliography{coal,ecol_spec,heli,kniga,mach,nfl,sniche}
\par\end{center}
\chapter*{Vita}
Edgar Alfredo Du\'e\~nez Guzm\'an was born in Guadalajara, Jalisco,
Mexico on June 19, 1981. In 2004 he graduated from the University
of Guanajuato with a Bs. Sc. in mathematics with a minor in computer
science. He received a Ms. Sc. in industrial mathematics and computer
science from the Mathematics Research Center (Centro de Investigaci\'on
en Matem\'aticas, CIMAT) in 2004. From there, he went to the University
of Tennessee, Knoxville and received a Ph. D. in Computer Science
with an Interdisciplinary Graduate Minor in Computational Science
in 2009.
Edgar is currently working as a postdoctoral research fellow in the
department of Organismic and Evolutionary Biology at Harvard University,
Cambridge, MA.
\end{document}