%%\documentstyle[twocolumn,epsf]{article}
\documentstyle[twocolumn,eclepsf]{article}


%%{\def\abstractname{Abstract}}{}
%%{\def\pagename{Page}}{}

\oddsidemargin  -10pt
\evensidemargin -10pt
\topmargin -47pt
\headheight 12pt
\headsep 25pt
\footskip 75pt
\textheight 9in
\textwidth 6.75in
\columnsep .375in
\columnseprule 0pt

%%\def\@oddhead{}\def\@evenhead{}
%%\def\@oddfoot{\rm\rightmark \hfil \pagename{} \thepage}
%%\def\@evenfoot{\@oddfoot}

%%\def\@oddhead{}\def\@evenhead{}
%%\def\@oddfoot{\rm\rightmark \hfil \pagename{} \thepage}
%%\def\@evenfoot{\@oddfoot}

%%\twocolumn
\sloppy
\parindent 1em
\leftmargini 2em
\leftmargin\leftmargini
\leftmarginv .5em
\leftmarginvi .5em
\flushbottom


\begin{document}

\title{The Baldwin Effect on the Evolution of Associative Memory}
\author{\begin{small}
        \begin{minipage}[t]{8.5cm}
        \begin{center}
        Akira Imada\\
        Graduate School of Information Science\\  
        Nara Institute of Science and Technology\\
        8916-5 Takayama, Ikoma, Nara, 630-01 Japan\\
        akira-i@is.aist-nara.ac.jp\\
        \end{center}
        \end{minipage}
        \begin{minipage}[t]{8.5cm}
        \begin{center}
        Keijiro Araki\\
        Graduate School of Information Science\\ 
        and Electrical Engineering, Kyusyu University\\
        6-1 Kasuga-koen, Kasuga, Fukuoka, 816 Japan\\
%%      araki@c.csce.kyusyu-u.ac.jp
        \end{center}
        \end{minipage}\end{small}}
\date{}
\maketitle

\thispagestyle{empty}
\pagestyle{empty}


\begin{small}
\noindent
{\bf Abstract} --- We apply genetic algorithms to the Hopfield model of associative memory.
Previously, we reported that a genetic algorithm evolves a network with random synaptic weights
to store eventually a set of random patterns. In this paper, we present the Baldwin effect on the evolution
enhances the storage capacity.
\end{small}

\section{Introduction}
\noindent
Associative memory is a system in which an incomplete or a noisy input of stored patterns should result in the retrieval in its complete form.
The error-correcting capability is due to its distributed storage of the patterns.
We are exploring basic behaviors of the associative memory under simple evolutionary processes.

In 1982, Hopfield~\cite{hopf} proposed a neural network model of the associative memory.
He used the Hebbian rule~\cite{hebb} to make connection matrix store a set of patterns.
He estimated the storage capacity to be at most 15\% of the number of neurons with computer simulations.
Later the capacity was verified analytically by Amit et al.~\cite{amit} with spin-glass theory.
Since then many researchers have been trying to enlarge the storage capacity in various ways. 
We try it by genetic algorithms (GA).

In an earlier papers, we showed that network with random connections evolves to 
store some number of patterns by a GA without any learning rules~\cite{imad-1}.
We also showed that the GA enlarges the capacity of Hebb-rule associative memory by pruning some connections~\cite{imad-2}.
In these experiments, individuals in the population do not learn the patterns in their life time.

The effect of life time learning on evolutions was first studied as a biological process by Baldwin~\cite{bald}.
Now this is known as the Baldwin effect.
As an analog of this effect, many researches concerning the combination of GAs and neural networks have addressed 
the relationship between {\it learning on a population level through evolution} and {\it on an individual level during its life time}.
Gruau et al. show an enhancement of performances of their neural networks by introducing the Baldwin effect on the evolution
(see also \cite{hint,pari} for example).

In this paper, we redesigned our previous GA so that each individual in the population can learn a set of pre-determined random patterns
before its fitness evaluation, i.e., the Baldwin effect on the evolution.
And we found that it enlarges the storage capacity, as well as makes the convergence much faster.

The overall goal for this research is to clarify the process of this learning mechanism of the GA.

\section{Associative memory}
Hopfield network which has $N$ neurons can store some number of $N$-bit bipolar patterns.
The pattern is denoted by ${\xi}^{\mu} = ( {\xi}^{\mu}_{1}, {\xi}^{\mu}_{2}, \cdots , {\xi}^{\mu}_{N})$,
where ${\xi}^{\mu}_{i}$ is the $i$-$th$ bit of the ${\mu}$-$th$ pattern which takes the value of either $-1$ or 1.
To store these $p$ patterns, each connection weight has to be appropriately determined.
If we use the Hebbian rule, for example, the weight $w_{ij}$ is determined as follows:
\begin{displaymath}
w_{ij} = \sum _{ \mu = 1}^{p} { { \xi }_{i}^{ \mu }{ \xi }_{j}^{ \mu }}.
\end{displaymath}
This process of determining $w_{ij}$ is called {\it learning}.

The retrieval of one of stored memories is as follows.
Each neuron state is asynchronously updated by
\begin{displaymath}
s_{i}^{\mu}(t+1) = sgn \left( \hspace{.04in} \sum_{j \ne i}^N { w_{ij} s_{j}^{\mu}(t)} \hspace{.04in} \right),
%%(\sum _{j=1}^{N} { w_{ij}s_{j}^{\mu}(t)}),
\end{displaymath}
where $s_{i}^{\mu}(t) $ is the state of the $i$-$th$ neuron at time $t$ when the $\mu$-$th$ pattern is given to the network.
For each neuron, the weighted sum of inputs is computed, and if this is
greater than or equal to zero, the state of the neuron takes the value of 1, and $-1$ otherwise.
In this paper, a neuron is chosen according to pre-assigned order (once in a cycle) at each step of updating, instead of chosen randomly.

When input is one of stored patterns which is given small noises, 
this input pattern relaxes to the stored pattern after several steps of update.
In this simulation, however, we do not give any noise to the input.
In this case, when one of a stored patterns is given to the network, neuron states should remain unchanged from the start, 
then the patterns are said to be memorized as {\it fixed points}.
We evaluate the ability of the network by the upper bound of the number of patterns possible to store as fixed points.
\section{GA Implementation}

In this section we describe our GA implementation briefly.

{\bf (1)} At first a weight matrix $W_{0}(N \times N)$
is produced randomly so that each component of the matrix $w_{ij}$ is chosen from $\{ -1, 1\}$.
Hence the matrix does not store any patterns at this moment.
This matrix remains unchanged during evolution.
{\bf (2)} Then a population of  chromosomes are produced randomly. 
The chromosome has a fixed length of $N \times N$ alleles which  are chosen from $ \{ -1, 0, 1\}$,
where the probability of choosing either $-1$ or 0 is set to 1/70.
As we shall see  in procedure (3) below, each component of the original weight matrix $w_{ij}$ is multiplied by one of these alleles.
Allele 0 implies to prune the connection which is multiplied, and $-1$ to reverse the excitatory/inhibitory connection.
{\bf (3)} Chromosomes modifies the original weight matrix $W_{0}$, and produce a population of the copies slightly different from $W_{0}$.
The modification was made as follows:
\begin{displaymath}
w^{(n)}_{ij} = w_{ij} \cdot c^{(n)}_{ij}
\end{displaymath}
where $c^{(n)}_{ij}$ is an allele of $n$-$th$ chromosome and $w^{(n)}_{ij}$ is $i$-$j$ component of the $n$-$th$ copy of the original matrix.
We set the population size to 256 here. This is just because of our computer resources.
{\bf (4)} Each individual phenotype learns a set of pre-determined random patterns $\xi^{\mu}$ by the Hebbian learning rule as follows.
\begin{displaymath}
w_{ij} = w_{ij}+\lambda \sum _{ \mu = 1}^{p} { { \xi }_{i}^{ \mu }{ \xi }_{j \ne i}^{ \mu }}.   
\end{displaymath}
We set the value of $\lambda$ to 0.4.
These matrices are used only for fitness evaluation in procedure (5) below, and the learning results do not affect chromosomes.
Hence we can regard this as the  Baldwin effect on the evolution.
{\bf (5)} When one of memorized patterns ${\xi}^{\nu}$ is given to the network as an initial state, 
the state of neurons varies from time to time afterwards (unless ${\xi}^{\nu}$ is a fixed point).
In order for the network to function as associative memory, the instantaneous network state must be similar to the input pattern. 
The similarity is defined by,
\begin{displaymath}
m^{\mu}(t) = \frac{1}{N} \sum_{i=1}^{N} { {\xi}_{i}^{\mu} s^{\mu}_{i}(t) },
\end{displaymath}
where $s_{i}^{\mu}(t)$ is the state of neuron $i$ at time $t$. 
This $m^{\mu}(t)$ is referred to as {\it overlap}.
The quality of retrieval of memorized patterns are represented by $\left \langle m^{\mu} \right \rangle$, 
a temporal average of $m^{\mu}(t)$ over certain time interval $t_0$.
We evaluate the fitness value of each network by further averaging these $\left \langle m^{\mu} \right \rangle$'s over all memorized patterns. 
Namely, the fitness $f$ is
\begin{displaymath}
f = \frac {1}{t_{0} \cdot p}
\sum_{t=1}^{t_{0}}{\sum _{\mu=1}^{p}{m^{\mu}(t)} }.
\end{displaymath}
In this paper, $t_{0}$ is set to $2N$, twice the number of neurons.
Note that the fitness 1 implies all the $p$ patterns are stored as fixed points, while all other cases have a fitness less than 1.
{\bf (6)} Two parent chromosomes are chosen to be recombined uniformly at random from the upper 40\% of the population which is ranked by fitness.
{\bf (7)} Recombinations are made with uniform-crossover.
We tested several types of crossover including one- and two-point-crossover, and observed that uniform-crossover outperformed
the others.
Furthermore, the offspring are occasionally mutated,
where mutation rotates the value of randomly chosen allele in a chromosome cyclically, as
%\begin{displaymath}
$(1)\rightarrow(-1), \hspace{.02in}(-1)\rightarrow(0), \hspace{.02in}(0)\rightarrow(1)$.
%%$(1) \rightarrow (-1), \hspace{.02in}(-1) \rightarrow (0), \hspace{.02in}(0) \rightarrow (1)$.
%\end{displaymath}
The mutation rate is set to 0.01.
{\bf (8)} Unless highest fitness value reaches the value of 1 nor generation exceeds 12000, 
the individuals in the best (40\%) survive to constitute the next generation with their offspring (60\%),
and the processes from (2) to (8) are repeated.\\
\indent
Both these operations and parameter values were determined mainly on the basis of trial and error.

\section{Results and Discussion}
To see the Baldwin effect on the evolution of associative memory,
we show two preliminary results at first.
One is evolution from a random matrix without using any learning algorithms, 
and the other is from the  Hebbian matrix.
Then we will describe the Baldwin effect on the evolution of random weight matrix using the Hebbian rule as a life time learning of each individual.
All these simulations were carried out on networks with 49 neurons.
\indent
\begin{figure}[thbp]
 \begin{center}
   \epsfile{file=random-fitness.eps,width=3.9cm,height=3.9cm}
   \epsfile{file=random-symm-and-zero.eps,width=3.9cm,height=3.9cm}
   \caption{Evolution from random matrix}
   \label{random}
 \end{center}
\end{figure}
\indent

The Genetic Algorithm per se has an ability to make a random weight matrix store some number of patterns.
In fact, we succeeded in evolving random weight matrix to store 8 patterns as fixed points~\cite{imad-1}.
The GA used in this experiment was similar to the one described above, except for the Hebbian learning process before fitness evaluation.
In Figure~\ref{random} (left), we show the results of the best fitness vs generation for 4, 6, 8, and 9 patterns.
These are samples of fastest convergence among several runs with different random number seed, 
or, when they do not converge, the samples of maximum number of patterns stored as fixed points. 
For 9 patterns, we did not obtain the perfect solution after repeating 30 runs with different random number seed.
Although this capability of storing 8 patterns with 49 neurons is almost the same as in the original Hebb-rule associative memory,
the structure of weight matrix is different from each other. 

Hebbian matrix is symmetric and all its diagonals are zero.
In this experiment, on the other hand, evolutions are started with a fully asymmetric matrix with no zero components.
%and during the evolution, symmetry is recovered to some extent and some components become zero.
In Figure~\ref{random} (right), we show the zero-density and degree-of-symmetry\footnote{It 
is defined as $\sum_{i=1}^{N} \sum_{j=1}^{N} {w_{ij} w_{ji}} / \sum_{i=1}^{N} \sum_{j=1}^{N} {w_{ij}^{2}}$.}
of the weight matrix which eventually stores 8 patterns.
Both zero-density and degree-of-symmetry increases from zero 
and asymptotically approach to the value of approximately 0.2.
We conjectured that both of the symmetry recovery and pruning connections play an important roll to store the patterns effectively.
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=hebbian-fitness.eps,width=3.9cm,height=3.9cm}
   \epsfile{file=hebbian-symm-and-zero.eps,width=3.9cm,height=3.9cm}
   \caption{Evolution from Hebbian matrix}
   \label{hebbian}
 \end{center}
\end{figure}

Since we use Hebbian learning rule as a life time learning in the simulation of the Baldwin effect,
it is interesting to see whether the Hebbian matrix itself will be able to  increase its capacity through evolution.
We applied the GA to the over-loaded Hebbian matrix~\cite{imad-2}.
As a result, we were able to enlarge the capacity to 16 patterns.
In Figure~\ref{hebbian} (left), we show the evolution for 14, 16 and 17 patterns.
We obtain the perfect solution for a maximum of 17 patterns.

The structure of the obtained matrix is very different from the evolution starting with random matrix.
In Figure~\ref{hebbian} (right), we show the zero-density\footnote{Since 
this matrix learns even number of patterns, some of its components are zero as a result of Hebbian learning. 
Here only the zero density introduced by the GA is shown.}
and degree-of-symmetry of the weight matrix which eventually stores 16 patterns.
As shown in the figure, the matrix obtained in this experiment is more symmetric,
and the GA prunes much fewer connections than in the above experiment.
The degree of symmetry and the zero density approaches to the value of approximately 0.7 and 0.03, respectively.

\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=baldwin-fitness.eps,width=3.9cm,height=3.9cm}
   \epsfile{file=baldwin-symm.eps,width=3.9cm,height=3.9cm}
   \caption{\it The Baldwin effect} 
   \label{baldwin}
 \end{center}
\end{figure}

In Figure~\ref{baldwin} (left), we show the evolution from random matrix under the Baldwin effect for 17, 19 and 20 patterns.
We can see that the enhancement of  the storage capacity to 19 patterns.
Although the increase in capacity is not so drastic compared to the evolution starting with the Hebbian matrix,
the convergence speed is tremendously improved.
The perfect solution was obtained at generation 996 for 17 patterns,
while the evolution from the Hebbian matrix for 16 patterns needed 10795 generations to converge.
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=comparison.eps,width=3.9cm,height=3.9cm}
   \epsfile{file=zero-in-chromosome.eps,width=3.9cm,height=3.9cm}
   \caption{Baldwin versus no-Baldwin}
   \label{baldwin-2}
 \end{center}
\end{figure}
\indent
In the Baldwin evolution, as we can see in Figure~\ref{baldwin} (right), 
the degree of symmetry remains unchanged from the beginning (around 0.8).
This is because learning of the patterns affects individuals only in their life time.

%We must note that the component of each weight matrix in the population never be zero after individual's learning in this third experiment.
To further compare the Baldwin effect with the other two evolutions,
we show best-fitness vs generation of the three experiments for the same set of 19 patterns in Figure~\ref{baldwin-2} (left).
We can see that evolution under the Baldwin effect outperforms the other two.
A  matrix which stores all these 19 patterns as fixed points emerged at generation 5408,
while the other two evolutions never converged.
Tempral expantions of the zero density in chromosome of the best individual are also shown in Figure~\ref{baldwin-2} (right).
We can see the significant differences among them.
We conjecture that the evolution pressures in these GAs are different from each other.
In the Baldwin version, the pressure works to enhance learnability rather than to directly increase a capacity.
That is, individuals which have higher ability to learn tend to survive.

%We can see it, for example, in the assignment of zeros in their chromosomes during an evolution.
In the experiment of the Baldwin effect, the results of learning of individuals do not change their chromosomes, 
but only affect the selection after fitness evaluation.
However, it is reported that incorporation of learning results into chromosomes 
also enhances the performance of GAs 
(see \cite{grua,whit} for example).
%%(see \cite{grua,whit,bart} for example).
This is known to be the Lamarckian inheritance.
We also investigate the effect of Lamarckian inheritance on the evolution of associative memory,
though a different implementation is required where the chromosomes are made up of components of the weight matrix instead~\cite{imad-4},
and we obtained almost similar enhancement of the capacity to the result in this paper.

\section{Conclusions}
We have described the Baldwin effect on the evolution of Hopfield model of associative memory.
The comparison of three evolutions from a random matrix, a Hebbian matrix, 
and a random matrix with the Hebbian lifetime learning, reveals  
that the learning {\it on an individual level during its life time} enhances the learning abililiy of the subsequent generations
%% future -> subsequent 
than in the case of only the {\it learning on a population level}.

However the more precise relationship between the two is  still an open question.
We leave this to the future research.

\begin{thebibliography}{5}
\setlength{\itemsep}{0pt}

\bibitem{hopf}Hopfield, J. J. (1982) 
{\em `Neural Networks and Physical Systems with Emergent Collective Computational Abilities'}
Proceedings of the National Academy of Sciences, USA {\bf 79}, pp2554-2558.

\bibitem{hebb}Hebb, D. O. (1949) 
The Organization of Behavior. Wiley.

\bibitem{amit}Amit, D. J., Gutfreund, H., and Sompolinsky, H. (1987) 
{\em `Statistical Mechanics of Neural Networks near Saturation'}
Annals of Physics, {\bf 173}, pp30-67.

\bibitem{imad-1}Imada, A, and Araki, K. (1995) 
{\em `Mutually Connected Neural Network Can Learn Some Patterns by Means of GA'}
{\it Proceedings of the World Congress on Neural Networks} {\bf 1}, pp803-806. 

\bibitem{imad-2}Imada, A., and Araki, K. (1995) 
{\em `Genetic Algorithm Enlarges the Capacity of Associative Memory'}
Proceedings of 6th International Conference on Genetic Algorithms, pp413-420.

\bibitem{bald}Baldwin, B. J. (1886) 
{\em `A New Factor in Evolution'}
The American Naturalist {\bf 30}, pp441-451 \& pp536-553.

\bibitem{hint}Hinton, G. E., and Nowlan, S. J. (1987) 
{\em `How Learning Guides Evolution'}
Complex System {\bf 1}, pp495-502.

\bibitem{pari}Parisi, D., and Nolfi, S. (1995) 
{\em `How Learning can Influence Evolution within a Non-Lamarckian Framework'}
Plastic Individuals in Evolving Populations. Santa Fe Institute Series, Addison-Wesley.

\bibitem{grua}Gruau, F., Whitley, D. (1993) 
{\em `Adding Learning to the Cellular Development of Neural Networks: Evolution and the Baldwin Effect'}
Evolutionary Computation {\bf 1}(3), pp213-233.

\bibitem{whit}Whitley, D., Gordon, V. S., and Mathias, K. (1994)
{\em `Lamarckian Evolution, the Baldwin Effect and Function Optimization'}
Proceedings of the 3rd Conference on Parallel Problem Solving from Nature, pp6-15.

\bibitem{imad-4}Imada, A., and Araki, K. (1996) 
{\em `Lamarckian Evolution of Associative Memory'}
Proceedings of IEEE International Conference on Evolutionary Computation, pp676-680.
\end{thebibliography}


\end{document}
