%% LATEX TWICE TO GET THE REFERENCES RIGHT
%%
%% \documentstyle[11pt,psfig]{article}        
%%
\documentstyle[12pt,epsf,psfig]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% macro for postscript figures - the easy way.
%% See directory ftp.cis.ufl.edu/tech report by fishwick@cis.ufl.edu 
%% This will help to control the size of the figure.
%%
\newcommand{\postscript}[2]
 {\setlength{\epsfxsize}{#2\hsize}
  \centerline{\epsfbox{#1}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{theorem}{Theorem}
\newtheorem{itlemma}{Lemma}[section] %number by section (set in \em by default)
%%%same numbering counter as itlemmas:
\newtheorem{itproposition}[itlemma]{Proposition}
\newtheorem{itcorollary}[itlemma]{Corollary}
\newtheorem{itremark}[itlemma]{Remark}
\newtheorem{itnote}[itlemma]{Note}
\newtheorem{itobservation}[itlemma]{Observation}
\newtheorem{itdefinition}[itlemma]{Definition}
\newtheorem{itexercise}[itlemma]{Exercise}
\newtheorem{itexample}[itlemma]{Example}

\newenvironment{lemma}{\begin{itlemma}\rm}{\end{itlemma}} %no-italics
\newenvironment{remark}{\begin{itremark}\rm}{\end{itremark}} %no-italics
\newenvironment{observation}{\begin{itobservation}\rm}{\end{itobservation}} %no-italics
\newenvironment{corollary}{\begin{itcorollary}\rm}{\end{itcorollary}}
\newenvironment{proposition}{\begin{itproposition}\rm}{\end{itproposition}}
\newenvironment{definition}{\begin{itdefinition}\rm}{\end{itdefinition}}
\newenvironment{exercise}{\begin{itexercise}\rm}{\end{itexercise}}
\newenvironment{example}{\begin{itexample}\rm}{\end{itexample}}

\tolerance=1600 %allow some tolerance in extending after line.
\parskip=3pt plus 1pt minus 1pt
\overfullrule=0pt %no dark lines if overfull

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This are for choices.  They take 4 or 6 args
%% (carriage returns allowed in between}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\twoif}[4]{
\left\{ \begin{array}{ll}#1&#2\\#3&#4\end{array}\right.
}
\newcommand{\threeif}[6]{
\left\{ \begin{array}{ll}#1&#2\\#3&#4\\#5&#6\end{array}\right.
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\partmlab#1#2#3#4#5#6#7#8{\bordermatrix{&#1&#2\cr#3&#5&#6\cr
					\noalign{\medskip}#4&#7&#8\cr}}
%% For 2by2 partitioned matrices; arguments are: two labels of top, side,
%% 4 entries (row by row).  If entries are themselves matrix or pmatrix,
%% better for readability of source to define first: \def\matrix1{...} etc.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\bigframebox}[1]{\framebox{\parbox{\smallerwidth}{#1}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Warning: use \noindent before!
% AND IN TEXT, after begin doc, do:
% \newlength{\smallerwidth}  %for bigboxes
% \setlength{\smallerwidth}{\textwidth}
% \addtolength{\smallerwidth}{-8pt}        %MUST BE DONE AFTER begin doc
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def \beq {\begin{eqnarray}}
\def \eeq {\end{eqnarray}}
\def \beqn {\begin{eqnarray*}}
\def \eeqn {\end{eqnarray*}}

\newcommand{\rf}[1]{[\ref{#1}]}            %bibliographical references

\newcommand{\text}[1]{\hbox{\rm \ #1\ \/}}
\newcommand{\be}[1]{\begin{equation}\label{#1}}
\newcommand{\ee}{\end{equation}}
\newcommand{\bl}[1]{\begin{lemma}\label{#1}}
\newcommand{\ble}[1]{\begin{lemmaex}\label{#1}}
\newcommand{\br}[1]{\begin{remark}\label{#1}}
\newcommand{\bn}[1]{\begin{note}\label{#1}}
\newcommand{\bo}[1]{\begin{observation}\label{#1}}
\newcommand{\bt}[1]{\begin{theorem}\label{#1}}
\newcommand{\bd}[1]{\begin{definition}\label{#1}}
\newcommand{\bp}[1]{\begin{proposition}\label{#1}}
\newcommand{\bc}[1]{\begin{corollary}\label{#1}}
\newcommand{\bfact}[1]{\begin{fact}\label{#1}}
\newcommand{\ber}[1]{\begin{exercise}\label{#1}}
\newcommand{\bex}[1]{\begin{example}\label{#1}}
\newcommand{\bem}[1]{\begin{example}\label{#1}}    %Yes, 2 different ones...
\newcommand{\ec}{\mybox\end{corollary}}
\newcommand{\efact}{\mybox\end{fact}}
\newcommand{\eer}{\mybox\end{exercise}}
\newcommand{\eex}{\mybox\end{example}}
\newcommand{\eem}{\mybox\end{example}}
\newcommand{\el}{\mybox\end{lemma}}
\newcommand{\ele}{\mybox\end{lemmaex}}
\newcommand{\er}{\mybox\end{remark}}
\newcommand{\en}{\mybox\end{note}}
\newcommand{\eo}{\mybox\end{observation}}
\newcommand{\et}{\qed\end{theorem}}
\newcommand{\ed}{\mybox\end{definition}}
\newcommand{\ep}{\mybox\end{proposition}}
\newcommand{\epr}{\end{proof}}
\newcommand{\bpr}{\begin{proof}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  These are just for statements, no "qed" box is put in.
%%  (Also for when I have to finish something after a displayed equation
%%        or itemized.)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\ecs}{\end{corollary}}
\newcommand{\eers}{\end{exercise}}
\newcommand{\eexs}{\end{example}}
\newcommand{\eems}{\end{example}}
\newcommand{\els}{\end{lemma}}
\newcommand{\eles}{\end{lemmaex}}
\newcommand{\ers}{\end{remark}}
\newcommand{\ens}{\end{note}}
\newcommand{\eos}{\end{observation}}
\newcommand{\ets}{\end{theorem}}
\newcommand{\eds}{\end{definition}}
\newcommand{\eps}{\end{proposition}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\qed}{\hfill \halmos} %put \qed at right margin
\newcommand{\mybox}{\hfill $\Box$} %put \qed at right margin (white square)

%%%\newcommand{\pmat}[2]{\left( \begin{array}{#1} #2 \end{array} \right) }
%%%use as e.g. \pmat{cc}{ a&b\\ a &c }  Note 'cc' for 2 Centered cols
%%%can also use \pmatrix{ a&b\cr a &c \cr} for plainTeX standard construct
%%%\setcounter{page}{27} should set the CURRENT page to 27

\def \R {\bb R} % reals
\def \C {\bb C} % complexes
\def \Z {\bb Z} % integers
\def \X {\bb X} % for this paper only!
\def \inter {{\rm int \,}}
\def \rank {{\rm rank \,}}

%%%\def \inf {{\rm inf \,}}  %better in Latex -- subscripts OK!
%%%\def \min {{\rm min \,}}

\def \im {{\rm im \,}}
\def \ker {{\rm ker \,}}
\def \norm #1{\Vert #1 \Vert}
\def \ip #1\by #2{\langle #1 , #2 \rangle}
\def \Sone {{\bf S}^1} % circle
\def \wigglearrow {\sim \mkern -6mu >}

\def \today {\ifcase \month \or January\or February\or  
  March\or April\or May\or June\or July\or August\or 
  September\or October\or November\or December\fi\   
  \number \day, \number \year}                       
\newcommand{\comment}[1]{}
\newcommand{\halmos}{\rule{1ex}{1.4ex}}
%%%alternative to \qed (see below)
\newenvironment{proof}{\noindent {\em Proof}.\ }{\hspace*{\fill}$\halmos$\medskip}

%%%\def\qed{\kern 1em \vrule height .5em width .5em depth 0em}
%%%(I now use new qed: in right margin)

\def\vbar{\mathchoice{\vrule height6.3ptdepth-.5ptwidth.8pt\kern-.8pt}
   {\vrule height6.3ptdepth-.5ptwidth.8pt\kern-.8pt}
   {\vrule height4.1ptdepth-.35ptwidth.6pt\kern-.6pt}
   {\vrule height3.1ptdepth-.25ptwidth.5pt\kern-.5pt}}
\def\fudge{\mathchoice{}{}{\mkern.5mu}{\mkern.8mu}}
\def\bbc#1#2{{\rm \mkern#2mu\vbar\mkern-#2mu#1}}
\def\bbb#1{{\rm I\mkern-3.5mu #1}}
\def\bba#1#2{{\rm #1\mkern-#2mu\fudge #1}}
\def\bb#1{{\count4=`#1 \advance\count4by-64 \ifcase\count4\or\bba A{11.5}\or
   \bbb B\or\bbc C{5}\or\bbb D\or\bbb E\or\bbb F \or\bbc G{5}\or\bbb H\or
   \bbb I\or\bbc J{3}\or\bbb K\or\bbb L \or\bbb M\or\bbb N\or\bbc O{5} \or
   \bbb P\or\bbc Q{5}\or\bbb R\or\bbc S{4.2}\or\bba T{10.5}\or\bbc U{5}\or

%%%   \bbb P\or\bbc Q{5}\or\bbb R\or\bba S{8}\or\bba T{10.5}\or\bbc
%%%   U{5}\or

   \bba V{12}\or\bba W{16.5}\or\bba X{11}\or\bba Y{11.7}\or\bba Z{7.5}\fi}}
%
%
\renewcommand{\thefootnote}{\fnsymbol{footnote}}

%%% read as: theFOOTNOTE (i.e. the command  executed when doing a footnote) is
%%% now to be set as a FOOTNOTESYMBOL (type of number) value of counter
%%% FOOTNOTE (Instead of roman).  See LaTeX manual pp.91-92 as well as
%%% 175.

\def\bi{\begin{itemize}}
\def\ei{\end{itemize}}
\def\ben{\begin{enumerate}}
\def\een{\end{enumerate}}
\def\st{\, | \,}

\newcommand{\myboxineq}{\eqno\Box} %put \qed at margin (white square) in eqn
\newcommand{\qedineq}{\eqno\halmos} %put \qed at margin in eqn

\topmargin -0.5in %default is 0.0, i.e. 1 inch from top.  Now it is 0.5
\textheight 9in
\oddsidemargin 0.25in %more reasonable margins!  (This is 1.25; can use <0 too)
\evensidemargin 0.25in %(same as above)
\textwidth 6.25in %(could use also -.5,-.5,7.5 for instance)
\tolerance=1600 %allow some tolerance in extending after line.
\parskip=3pt plus 1pt minus 1pt
\overfullrule=0pt %no dark lines if overfull

%%%%%%%%%%%%%%% FROM HERE, macros special for paper %%%%%%%%%
\def\mm{m}
\def\pp{p}
\def\proj{\pi _1}     %%%% projection on first group of coordinates
\def\x{u}  % vector argument
\def\SEC{(SEC)}
\def\SECo{(SEC$^0$)}
\def\INV{(INV)}
\def\Fp{{\cal F}_\pp}
\def\Fpm{{\cal F}_\pp^\mm}  %%%% there is a 3,3 and a 2,1 in text

\def\Rm{\R^m}
\def\Rn{\R^n}
\newcommand{\ball}[2]{{\bb B}(#1,#2)}
\newcommand{\cball}[2]{\overline {\bb B} (#1,#2)}
\def\Fnm{{\cal F}_n^\mm}
\def\clos{{\rm clos\,}}
\def\inter{{\rm int\,}}

\def\CCF{compatible class of functions}
\begin{document}

\bibliographystyle{plain}

\pagestyle{empty}
\begin{flushright}
{\sl AI-Modeling}
\end{flushright}
\vfill
\begin{center} 
\hrule
\hrule
\vspace{.05cm}
\hrule
\vspace{.25cm}
{\bf 
Punctuated Equilibrium and Criticality in a Simple Model of Evolution
-   Brief Review, Some Modification, and  Computer Simulation
}
\vspace{.25cm}
\hrule
\vspace{.05cm}
\hrule
\hrule
\vspace{1cm}
Saleh Elmohamed\\
saleh@\{cis, npac\}.syr.edu\\   
\end{center}

\vspace{1.5cm}

\vfill
\centerline{December 1996}
\vfill

\newpage

\pagestyle{plain}


\section{Introduction}
\setcounter{page}{1}

The idea of evolution as a self-organized phenomenon is certainly an
interesting one, but at present it suffers from a lack of hard
evidence either to prove or disprove it. Although a number of authors
have cited examples of biological data which appear to support the
idea of self-organization, there is by no mean a clear case in favor
of it. Well, there is evidence of self-organized critical behavior in
a number of other systems. For example, there is evidence of it in
computer experiments on the evolution of ``artificial life''. Using
{\it Tierra} (Ray \cite{11}), a simulation system in which
self-reproducing computer programs evolve and compete for limited
resources, Adami \cite{12} has observed a series of discontinuous {\it
phase transitions} in the fitnesses of interacting species and
measured the distribution of waiting times between transitions. On the
basis of these experiments, Adami suggests that one should see a
spectrum of co-evolutionary avalanches which lacks any defining size
scale, possessing a probability distribution $p(s)$ following a power
law: $p(s) \propto s^{-r}\;$. This power law form has been taken as
evidence of self-organization in a wide variety of systems. However,
in the crucial case of biological evidence in favor of
self-organization has been rather difficult to pin down. Eldredge and
Gould \cite{13} presented evidence of uneven rates of evolution of
single species; periods of equilibria separated by intervals of rapid
change (or punctuations). 

A number of explicit mathematical models of avalanche behavior in
evolution have been given by, for example, Kauffman and Johnson
\cite{14} and by Bak and Sneppen \cite{1, 2}. It is outlined in these
papers that under suitable conditions, the size distribution of
avalanches in these models follows a power law, and it has been
suggested by the authors that this might potentially give rise to a
corresponding power law in the extinction distribution. 

Our focus for the rest of the report is on the mathematical model
introduced in \cite{1, 2}.

\section{Summary of the Model}

This is a short review and some modification to the ``minimal
self-organized criticality'' model proposed by Bak and Sneppen
\cite{1, 2}. (For further analysis of this model see \cite{3, 4, 5, 6,
7, 8, 9, 10}) The model represents the following essential features:
(1) A set of species of size N with periodic boundary conditions. (2)
A random barrier, $B_i$, equally distributed between $0$ and $1$, is
assigned to each species. The barrier to mutation is a measure of how
far the species must mutate against a selection gradient before
reaching a new evolutionarily stable phenotype. This phenomena is
illustrated by the ``rugged fitness landscape'' picture, shown in
Figure \ref{figure-1}, where the horizontal axis represents different
phenotypes and the vertical axis represents some measure of species
success, such as lifetime reproductive success. 
(3) A measure of fitness of how susceptible a species is to extinction
from environmental effects such as a climate change; it is not a gauge
of the relative merits of one species over another in direct
competition. Nothing in the model addressing mechanisms for direct
inter-species competition. 

In regard to the abovementioned barrier, Bak and Sneppen \cite{1} make
the assumption that the neighbors of the site with lowest barrier get
new, random barriers. The picture in Figure \ref{figure-1} is
one-dimensional; in reality the landscape will be multi-dimensional.
Species spend most of their time at a maxima in the fitness landscape,
where they are reasonably well adapted to their environment. Small
mutations away from the maximum are driven back to that maximum by the
selection gradient. On occasions, a species can undergo large
mutations, or a succession of smaller mutations, which cause it to
pass over a barrier and reach the region of attraction of a different
maximum in the fitness landscape. The selection gradient will then
drive it to this new maximum, where it will be stable until another
rare large change drives it on to yet another maximum. In the
meantime, the species will undergo small fluctuations about its new
phenotype. These jumps over barriers can set off a chain reaction of 
coevolution in other species, giving a burst or ``avalanche'' of
evolutionary activity.

\vspace{0.25cm}
\begin{figure}[htb]
\centerline{\psfig{figure=phenotype.eps,height=350pt,width=385pt,angle=-90}}
\vspace{0.30cm}
\caption{A schematic representation of a portion of a rugged fitness
landscape. Maxima in the fitness function correspond to stable
phenotypes. The smallest fitness barrier that has to be traversed by a
species at the indicated point in order of it to mutate to a new
stable form is given by $b$.}
\label{figure-1}
\end{figure}

Since there are no obvious units for the barrier heights, they can be
chosen following \cite{1} to lie between zero and one.

\section{Simulation and Some Modification to the Model}

The simulation code \cite{10} I have written is based on Bak and 
Sneppen's model \cite{1}. In addition to their barrier variables, 
I also calculate a fitness variable. 
This fitness plays no role in the dynamics of the
barrier variables, so the results for the barriers are just the result
we would get out of the Bak and Sneppen's model. In addition, the code
can be compiled to calculate a variant of their model where instead of
randomly changing the barrier of neighboring species, I change it by
adding or subtracting some small value from their current barrier value. 
It turns out that the long time results (meaning, avalanche
statistics) are similar for both versions of the model. 

In the simulation each of the $N$ species in the model is
characterized by two real numbers, a fitness $f_i$ and a barrier to
mutation $b_i$.

\section{Some Analysis of the Results}

Figures \ref{figure-2} and \ref{figure-3} illustrate the results of barrier
versus fitness. Figure \ref{figure-2} is for Bak and Sneppen's model
and the output shown in Figure \ref{figure-3} is for my modification
to the model. As mentioned above the fitnesses don't have much effect
on the dynamics of the barriers.

Figure \ref{figure-3} shows less spread of points and more clustering
near barrier 1 than shown in Figure \ref{figure-2}. This is mainly due
to the fact that Bak and Sneppen make the assumption that the neighbors
of the site with the lowest barrier get new, random barriers. In my
modification they will get randomly shifted some value from their
current barrier value. This tends to drive barriers up on average
because a neighbor that is shifted down is more likely to be the
lowest barrier (and hence get changed) than is a barrier that is
shifted up. For this reason the final distributions of both models
(Bak's and my modification to it) will be different. However, if you
look at the size distribution of avalanches, the results are pretty
much the same. The avalanche cutoff will be different for the two
models, however.
\vspace{0.25cm}
\begin{figure}[htb]
\centerline{\psfig{figure=Bak-model.ps,height=350pt,width=380pt,angle=-90}}
\vspace{1.5cm}
\caption{Fitness vs. barrier for Bak and Sneppen's model. It shows a
spread of points between approximately a barrier of 0.5 and 1 and a
higher density between 0 and 1 of the fitness range. Number of steps
used to produce these points is 10,000.}
\label{figure-2}
\end{figure}

\vspace{0.25cm}
\begin{figure}[htb]
\centerline{\psfig{figure=My-model.ps,height=350pt,width=380pt,angle=-90}}
\vspace{1.5cm}
\caption{Fitness vs. barrier for the modification model of Bak and 
Sneppen's model. It shows a spread of points between approximately 
a barrier of 0.7 and 1 and a higher density between 0 and 1 of the
fitness range. Furthermore, clustering of fitness points occurs along
the barrier 1 due to the slight difference between the two
models. Number of steps used to produce these points is 10,000.} 
\label{figure-3}
\end{figure}

\clearpage
\begin{thebibliography}{model}
\bibitem{1}
Bak, P., and Sneppen, K, ``Punctuated Equilibrium and Criticality in a
Simple Model of Evolution,'' Physical Review Letters, vol. 71, No. 24,
4083-4086, 13 December 1993.

\bibitem{2}
Sneppen, K., Bak, P, Flyvbjerg, H, and Jensen, M, ``Evolution as a
self-organized phenomenon,'' Proc. National Acad. of Sci., USA,
vol. 92, pp. 5209-5213, May 1995.

\bibitem{3}
Flyvbjerg, H, Sneppen, K, Bak, P., ``Mean field theory for a simple
model of evolution,'' Physical Review Letters, 71, No. 24, 4087 (13
Dec 1993).

\bibitem{4}
Ray, T. and Jan, N, ``Anomalous approach to the self-organized
critical state in a model for `life at the edge of chaos','' Physical
Review Letters, 72, 4045 (1994).

\bibitem{5}
de Boer, J., Derrida, B, Flyvbjerg, H., Jackson, A. and Wettig, T.,
``Simple model of self-organized biological evolution,'' Physical
Review Letters, 73, 906 (1994).

\bibitem{6}
Paczuski, M, Maslov, S, Bak, P., ``Field theory for a model of
self-organized criticality,''Europhysics Letters, 27, 97 (1994); 28,
295 (Erratum) (1994).

\bibitem{7}
Marsili, M, ``Renormalization group approach to the self-organization
of a simple model of biological evolution,'' Europhysics Letters, 28,
85 (1994).

\bibitem{8}
Maslov, S., Paczuski, M., and Bak, P., ``Avalanches and 1/f noise in
evolution and growth models,'' Physical Review Letters, 73, 2162
(1994).

\bibitem{9}
Jovanovic, B, Buldyrev, S., Havlin, S. and H. Stanley, ``Punctuated
equilibrium and `history-dependent' percolation,'' Physical Review E
50, 2403 (1994).

\bibitem{10}
Elmohamed, S, ``Simulation code based on Bak and Sneppen's Model,''
see references (1) and (2) above. The code is available on {\it
top.cis.syr.edu} under userid ``saleh''. The pathname is
``saleh/modeling''. 

\bibitem{11}
Ray, T. S, `` An evolutionary approach to synthetic biology: Zen and
the art of creating life,'' Artificial Life 1, 179. Reprinted in
Artificial Life, An Overview, C. Langton (Ed.), MIT Press 1995.

\bibitem{12}
Adami, C, ``Self-organized criticality in living systems,'' Physics
Letters A 203, 29 (1995).

\bibitem{13}
Eldredge, N, and Gould, S. J., ``Punctuated equilibria: an alternative
to phyletic gradualism,'' In {\it Models in Paleobiology},
T. J. M. Schopf (Ed.), Freeman, San Francisco 1972.

\bibitem{14}
Kauffman, S. A. and Johnson, S. ``Coevolution to the edge of chaos:
Coupled fitness landscapes, poised states, and coevolutionary
avalanches,'' J. Theor. Biology 149, 467 (1991).

\end{thebibliography}
\end{document}








