%%This issue is returned to in the Conclusion.
%%fitness landscape
%%\documentstyle[alife5,epsf]{article}
\documentstyle[alife5,eclepsf]{article}

%% height:235mm, width:86mm, between-column:6mm, right-margin:19mm, top-margin:25mm, 10 points  max-8-pages

%%\textheight 235mm
%%\textwidth 178mm
%%\topmargin -20mm
%%\oddsidemargin -5mm

\begin{document}

\title{Evolution of Associative Memory \\ with Environmental Change}

\author{Akira Imada\\
        akira-i@is.aist-nara.ac.jp\\
        \hspace*{1in} \\
        Keijiro Araki\\
        araki@is.aist-nara.ac.jp\\
        \hspace*{1in} \\
        Graduate School of Information Science\\  
        Nara Institute of Science and Technology\\
        8916-5 Takayama, Ikoma, Nara, 630-01 Japan}
\date{}
\maketitle

\begin{abstract}
\noindent
There have been a lot of researches which apply evolutionary techniques to layered neural networks.
However, their applications to Hopfield neural networks remain few so far.
We have been applying a genetic algorithm to fully connected associative memory model of Hopfield, and reported elsewhere 
that the network can store some number of patterns only by evolving weight matrices with the genetic algorithm.
In this paper, we present that 
evolving both weight matrices and patterns to be stored 
results in the higher capacity of associative memory 
than in the case of fixed patterns above.
From an Artificial Life perspective, the patterns to be stored are considered to be an environment.
\end{abstract}

\section{Introduction}
\noindent
Associative memory is a process in which we can store information by distributing it among neurons.
One of the most appealing features is its capability to tolerate noisy and/or partial input in recalling the information,
though it has a limited capacity.\\
\indent
These networks might be used as a memory organ of digital organisms of our Artificial Life research in the future.
However, as a preliminary step, we are now investigating basic behavior of the function of associative memory under simple evolutionary processes.
We are now using a genetic algorithm (\cite{holl}, \cite{gold}) to evolve the networks.\\
\indent
Genetic algorithms have been extensively exploited for layered neural networks (see e.g, \cite{whit}), 
but curiously have not been applied to Hopfield model. 
Probably this is because the Hopfield network has a fixed architecture. 
However, sparse connectivity of the network has a possibility to enhance the associative memory capacity~\cite{yana}.
Hence the genetic algorithm may be used also as a method to determine the architecture of Hopfield networks.
In fact, we showed that the genetic algorithm enlarges the capacity of Hebb-rule associative memory by pruning some of its connections~\cite{imad-2}.
We also reported that a random weight matrix was evolved to store some number of patterns only by means of the genetic algorithm~\cite{imad}.\\
\indent
In the context of Artificial Life, it has been shown that environmental change enhances some performances \cite{zhou}, \cite{unem}.
Here we give the patterns to be stored an opportunity to be modified in every certain generations so that the fitness of individuals are improved.
When we take the patterns as a language of individuals in a population, it is interesting to see if slight occasional modifications of their language
enhance the individual's adaptability.\\
\indent
The goal of this research is twofold.
One is to improve the techniques to enlarge the associative memory capacity which are proposed so far, and
the other is to know if the ability of associative memory can be adaptive to the changing environment.\\

\noindent
In the following section, we provide an outline of our experiment, a brief review of associative memory and
the implementation of our genetic algorithm.
The difference from our previous implementation is described in detail.

\section{Experiment}
We apply a simple genetic algorithm to fully connected associative memory model of Hopfield.
To be more specific, an auto-associative, discrete-time asynchronous-update, bipolar-state network.
The connection weights are chosen randomly either from $-1$ or 1 at the start of the genetic algorithm,
therefore the network can not store any patterns initially.
The objective of the experiment is to make this network store some number of patterns without any learning algorithm besides the genetic algorithm.\\
\indent
We set the size of the network to 49 neurons in this paper, considering computational expense.
This size of {\it Hebb-rule associative memory} would have a capacity of 7 patterns at most.
In our previous simulation with the networks of the same size, 
we succeeded in evolving a random weight matrix eventually to store 8 patterns~\cite{imad}.
In this new version of the experiment, we occasionally change the patterns to be stored to see if it enhances the capacity.\\
\indent
From Artificial Life point of view, each individual in the population tries to memorize a given set of patterns, 
increasing its accuracy, generation by generation.
And our concern in this paper is how these occasional changes in language affect the accuracy and the capacity.\\

\noindent
Before describing the implementation of our genetic algorithm, let us review some fundamental concepts relating to associative memory.
\subsection*{Associative Memory}
Hopfield network which has $N$ neurons can store some number of $N$-bit bipolar patterns, 
if all the connection weights are determined adequately.
The patterns are $n$-dimensional random vectors whose elements take the values $\pm 1$ randomly with equal probability.
The $\mu$-$th$ pattern is denoted as
\begin{displaymath}
{\xi}^{\mu} = ( {\xi}^{\mu}_{1}, {\xi}^{\mu}_{2}, \cdots ,{\xi}^{\mu}_{i}, \cdots, {\xi}^{\mu}_{N}) ,
\end{displaymath}
\noindent
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 patterns, each connection weight has to be adequately adjusted.
If we use 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}

\noindent
where $p$ is the number of patterns to be stored.
This process of determining $w_{ij}$ is referred to as {\it learning}.\\
\indent
These $w_{ij}$'s define a so called energy function on an $N$-dimensional bipolar state space, i.e.,
\begin{displaymath}
E(S) = \frac{1}{2} \sum_{i,j(i \ne j)} w_{ij}S_{i}S_{j},
\end{displaymath} 

\noindent
where $S$ moves over all possible combinations of $N$-dimensional vector $\{-1, 1\}^{N}$ and $S_{i}$ is the $i$-$th$ component of the state $S$.
If the number of stored patterns is small enough, 
this function takes a local minimum where $S$ corresponds to one of stored patterns.
In this sense the stored patterns are said to be {\it attractors} and the size of this local minimum are referred to as {\it basin of attraction}.
As the number of stored patterns $p$ increases, spurious minima become non-negligible and finally these local minima are randomized.\\
\indent
The retrieval of one of stored memories is as follows.
The state of each neuron is asynchronously updated by
\begin{displaymath}
s_{i}^{\mu}(t+1) = sgn(\sum _{j=1}^{N} { w_{ij}s_{j}^{\mu}(t)}),
\end{displaymath}
\noindent
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 its 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.\\
\indent
When input is one of the stored patterns which is given small noise within the size of basin of attraction,
this input pattern relaxes to the original stored pattern after several steps of the update.
If we do not give any noise to the input, on the other hand, i.e., one of stored patterns is given to the network, 
all the states remain unchanged from the start, and the patterns are said to be memorized as {\it fixed points}.
We evaluate the ability of weight matrix by the upper bound of the number of patterns stored as fixed points.\\
\indent
When Hopfield~\cite{hopf} proposed a neural network model as an associative memory system, in which he used Hebbian learning rule,
he estimated the memory capacity to be at most 15\% of the number of neurons with using computer simulations. 
Later the capacity was verified more analytically by Amit et al.~\cite{amit} with spin-glass theory,
and by Amari et al.~\cite{amar} with statistical neuro-dynamical method.
Since then, many researchers have been successfully trying to enlarge the capacity.
%% Since Kohonen~\cite{koho} proposed several types of connection matrices for associative memory to improve the capacity,
%% other various successful methods have been proposed for that.
For example, Yanai et al.~\cite{yana} made it by introducing sparse connectivity, 
Morita~\cite{mori} by replacing the sigmoid function with a non-monotonic transfer function,
and Willshow et al. \cite{will}, Palm \cite{palm} and Meunier et al. \cite{meun} by using sparsely coded patterns 
instead of random patterns.
%% (the last issue is returned to later).
%% Those mechanisms, however, are not well understood yet. 
Here we are exploring this by means of genetic algorithms.\\

\noindent
To know more about associative memory, see for example~\cite{hass}.

\subsection*{Genetic Algorithm}
In this subsection we describe the implementation of our genetic algorithm briefly.
As in Figure~\ref{overview}, our genetic algorithm proceeds as follows:\\

\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=reproduction.eps,width=8.4cm,height=4.2cm}
   \caption{\bf Schematic representation of our GA}
   \label{overview}
 \end{center}
\end{figure}

\noindent
{\bf (1)} At first a weight matrix $W_{0}$(49x49) is produced randomly so that each component of the matrix $w_{ij}$ are chosen from $ \{ -1, 1\}$.
Hence the matrix does not store any patterns at this moment.
This original weight matrix remains unchanged during evolution.
{\bf (2)} Then 256 chromosomes are produced also randomly. The chromosome has a fixed length of 2401(=49x49) alleles, 
and its alleles are chosen randomly from $ \{ -1, 0, 1\}$,
where the probability of choosing either $-1$ or 0 is set to 0.02 here.
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 excitatory/inhibitory connection.
We denote the $i$-th allele of the $n$-th chromosome as $c^{(n)}(i)$.
{\bf (3)} Each chromosome modifies the original weight matrix $W_{0}$, which produces 256 weight matrices slightly different from $W_{0}$.
The modification was made as follows:
\hspace*{3in}\\
\hspace*{.2in} $ w^{(n)}_{ij} = w_{ij} \cdot c^{(n)}(49i+j)$, \\ 
\hspace*{.5in}  $ (i,j = 0, 1,2, \cdots , 48; \hspace{.1in} n = 1,2,3, \cdots 256)$,\\
\hspace*{3in}\\
where $w^{(n)}_{ij}$ denotes $i$-$j$ component of the $n$-th weight matrix in the population.
We must note that the larger the population number, the higher the performances.
In these experiments, however,  we set it to 256 just because of our computer resources.
{\bf (4)} Evaluation of fitness value $f$ for each individual weight matrix is made with a set of randomly predetermined patterns $\xi^{\mu}$ 
(see preceding subsection).
First we calculate the total of all the inner products (overlap) of initial states and
states at each time of update not more than certain time $t_{0}$. And then these are summed up over all sets of initial patterns, i.e.,
\begin{displaymath}
f = \frac {1}{p \cdot (t_{0} - 1) \cdot 49}   \sum _{\mu=1}^{p} \sum_{t=2}^{t_{0}} 
{ \sum _{j=1}^{49} {\xi_{j}^{\mu} s_{j}^{\mu}(t)}}. \\
\end{displaymath}
\noindent
In this paper, $t_{0}$ is set to 98 i.e., two times the number of neurons, and we observed that was enough.
We must note that fitness 1.000 implies that all the initial patterns are stored as fixed points, 
while fitness less than 1.000 includes many possible cases.
If we evaluated the fitness at one point of updating time instead, some solutions might be limit cycle.
We adopted the above time-consuming fitness evaluation in order to avoid these oscillated solutions.
{\bf (5)} Every 40 generations, we give a perturbation to one randomly chosen bit of each pattern,
and for the new set of modified patterns we evaluate fitness of each individual of the generation in the same way as above. 
If the highest fitness value exceeds the previous value, we replace the new patterns with old ones.
This process is repeated five times for the same population.
{\bf (6)} Two parent matrices are chosen uniformly at random from the upper 40\% of the population which is ranked by fitness.
Then those are recombined to make one child chromosome, and an individual in the lower 60\% of the population is replaced with it.
This process is repeated until all the individuals in the lower subpopulation are replaced.
{\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 from each crossover are mutated in times, 
where mutation rotates the value of randomly chosen allele in chromosome $c^{(n)}(i)$ cyclically i.e.,
\begin{displaymath}
(1) \rightarrow (-1), \hspace{.1in}(-1) \rightarrow (0), \hspace{.1in}(0) \rightarrow (1).
\end{displaymath}
The mutation rate is set to 0.01 in this paper.
{\bf (8)} The processes from (2) to (8) are repeated until best-so-far-fitness converges to 1.000 or generation reaches 12000. 
In repeating the processes, individuals in upper subpopulation (40\%) survive to constitute the next generation with their offspring (60\%).\\

\noindent
These operations and parameter values were determined mainly on the basis of trial and error.

\section{Results and Discussions}
\noindent
In our previous simulation \cite{imad}, where the patterns to be stored remained fixed during evolution, 
the network were able to store up to 8 patterns as fixed points.
In those simulations, we repeated 30 runs for 9 patterns with different random number seed,
nevertheless we did not obtain the weight matrix which stored all these 9 patterns.
So we concluded the associative memory capacity obtained with that method was 8 patterns for 49 neurons.
On the other hand, new version of the simulation in this paper, where the patterns to be stored were also evolved occasionally,
we obtained the weight matrix which stored all the 9 patterns as fixed points.
Again we repeated the simulation for 10 patterns with different random number seed, however none of the best-fitted matrix did not store them
as fixed points.
We show the fitness vs generation for 9 and 10 patterns in Figure~\ref{evolution}.\\

\begin{figure}[htbp]
 \begin{center}
   \epsfile{file=fitness.eps,width=7cm,height=7cm}
   \caption{\bf Fitness vs Generation}
   \label{evolution}
 \end{center}
\end{figure}
\begin{figure}[htbp]
 \begin{center}
   \epsfile{file=change.eps,width=7cm,height=7cm}
   \caption{\bf Frequency of Replacement of Patterns}
   \label{improvement}
 \end{center}
\end{figure}

%%\clearpage
\noindent
In this new version of the simulation, one bit of each pattern is flipped at every 40 generations,
and these modified patterns are checked if they give a higher fitness value to the best-so-far individual.
When this occurs, the old patterns are replaced with the new ones.\\
\indent
At early stages of evolution, the modified patterns tend to give individuals higher fitness value.
However, as evolution proceeds the number of individual's accepting new patterns decreases asymptotically.
In Figure~\ref{improvement} we show the number as evolution proceeds.\\
\indent
It shows that the effect of learning by the genetic algorithm itself in each generation is very weak. 
Therefore even the individual which learned those patterns most efficiently have a room to accept the slight changes in patterns at early stages.
As evolution proceeds, however, accumulated effects of the learning make them difficult to accept the changes. \\
\indent
To ascertain this, we experimented with Hebbian matrix instead of random one as the original weight matrix $W_{0}$.
However, the modified patterns were never accepted from the first generation at all (not shown in the figures in this paper),
probably because Hebbian learning effect is much stronger than the one by genetic algorithm.\\
\indent
Some experiments in Artificial Life literatures show that changing environment in every generation enhances the evolvability of individuals
(see for example \cite{zhou} and \cite{unem}). 
In this paper a set of patterns to be given to the individual networks could be taken as an environment.
We tried to change the environment in every generation.
Although it works at the beginning (until around the 100-th generation), 
the effect is saturated afterwards without attaining fitness of 1.000 (not shown here neither).\\
\begin{figure}[htbp]
 \begin{center}
   \epsfile{file=pattern.eps,width=7cm,height=7cm}
   \caption{\bf Density of ``1'' in Patterns}
   \label{sparceness-of-pattern}
 \end{center}
\end{figure}

\noindent
To see what happens in these replaced patterns, we counted the number of 1's  
in patterns which were successfully modified and adopted as new patterns.
In Figure~\ref{sparceness-of-pattern}, we show an example of the density of 1's in the replaced patterns as a function of generation numbers.
We can see in the figure that these accepted patterns tend to have more 1's than in the previous patterns.
So we conjectured that the enhancement in memory capacity is due to the decrease of $-1$'s in the patterns.\\
\indent
As we mentioned in the previous section,
Willshow et al. \cite{will}, Palm \cite{palm} and 
Meunier et al. \cite{meun} showed that sparsely coded patterns enhanced the capacity of {\it Hebb-rule associative memory}.
Hence we expected that the density of 1's would be decreased through evolution, though we do not use Hebbian learning.
However, we obtained the opposite results here. Yet we do not know the reason for that.
\section{Conclusions}
By slightly modifying patterns occasionally in the evolution of associative memory, 
we obtain a little higher memory capacity than in the case of fixed patterns.
Acceptance of the modified patterns occurs more frequently at early stages of evolution, 
and asymptotically decreases its chance as generation proceeds.
The improvement in capacity is due to the increase of the number of 1's in patterns.\\
\indent
The enhancement in capacity in this method is not so drastic than we expected, 
comparing to other experiments of changing environment \cite{zhou}, \cite{unem}. 
However, from an Artificial Life point of view, these  phenomena observed here might be interesting 
when we take the patterns as a language of the individuals.
Changes in language could be more easily allowed when the culture is young and a little higher rate of ``1'' is more acceptable in this society.
%%Since this research is quite immature, 
Furthermore, to consider evolvability or elaboration of language, we have to incorporate communication between individuals or species probably.\\
\indent
The result in this paper is just a beginning of our research, 
we can not draw further conjectures yet.
So we will keep researching to obtain further interesting phenomena in Artificial Life context.

\section*{Acknowledgments}
We thank Peter Davis at Advanced Telecommunication Research Institute (ATR).
The ideas in this paper were originally derived from discussions with him.

%%\clearpage

\begin{thebibliography}{99}
\bibitem{holl}J.~Holland (1975). {\it Adaptation in Natural and Artificial Systems.} The University of Michigan Press.
\bibitem{gold}D.~Goldberg (1989). {\it Genetic Algorithms in Search, Optimization, and Machine Learning.} Addison-Wesley.
\bibitem{whit}J.~D.~Schaffer, D.~Whitley, L.~J.~Eshelman (1992).
Combinations of Genetic Algorithms and Neural Networks: A Survey of the State of the Art.
{\it Proceedings of the Workshop on Combinations of Genetic Algorithms and Neural Networks} 1-37.
\bibitem{imad-2}A.~Imada, and K.~Araki (1995). Genetic Algorithm Enlarges the Capacity of Associative Memory.
{\it Proceedings of 6th International Conference on Genetic Algorithms} 413-420.
\bibitem{imad}A.~Imada, and K.~Araki (1995). Mutually Connected Neural Network Can Learn Some Patterns by Means of GA.
{\it Proceedings of the World Congress on Neural Networks} {\bf 1} 803-806. 
\bibitem{zhou}L. Zhou, and S. Franklin (1994).
Character Recognition Agents.
{\it Artificial Life IV: Proceedings of the 4th International Workshop on the Synthesis and Simulation of Living Systems} 301-306.
\bibitem{unem}T.~Unemi, M.~Nagayosi, N.~Hirayama, T.~Nade, K.~Yano, and Y.~Masujima (1994).
Evolutionary Differentiation of Learning abilities: A Case Study on Optimizing Parameter Values in Q-Learning by a Genetic Algorithm.
{\it Artificial Life IV: Proceedings of the 4th International Workshop on the Synthesis and Simulation of Living Systems} 331-336.
\bibitem{hopf}J.~J.~Hopfield (1982). Neural Networks and Physical Systems with Emergent Collective Computational Abilities. {\it Proceedings of the
National Academy of Sciences, USA} {\bf 79}  2554-2558.
\bibitem{hebb}D.~O.~Hebb (1949). {\it The Organization of Behavior.} Wiley.
\bibitem{amit}D.~J.~Amit, H.~Gutfreund, and H.~Sompolinsky (1987). Statistical Mechanics of Neural Networks near Saturation. 
{\it Annals. of Physics} {\bf 173}  30-67.
\bibitem{amar}S.~Amari, and K.~Maginu (1987). Statistical Neurodynamics of Associative Memory. {\it Neural Networks} {\bf 1}  63-73.
%% \bibitem{koho}T.~Kohonen (1977). {\it Associative Memory: A System-Theoretical Approach.} Springer-Verlag. 
\bibitem{yana}H.~Yanai, Y.~Sawada, and S.~Yoshizawa (1991).
Dynamics of an Auto-Associative Neural Network Model with Arbitrary Connectivity and Noise in the Threshold. 
{\it Network} {\bf 2}(3)  295-314.
\bibitem{mori}M.~Morita (1993). Associative Memory with Nonmonotone Dynamics. {\it Neural Networks} {\bf 6}  115-126.
\bibitem{will}D.~J.~Willshow, O.~P.~Buneman, and \\H.~C.~Longuett-Higgins (1969).
Nonholographic Associative Memory. {\it Nature} {\bf 222} 960-962.
\bibitem{palm}G.~Palm (1980). 
On Associative Memory. {\it Biological Cybernetics} {\bf36} 19-31.
\bibitem{meun}C.~Meunier, H.~Yanai, and S.~Amari (1991).
Sparsely Coded Associative Memories: Capacity and Dynamical Properties. {\it Network} {\bf 2} 469-487.
\bibitem{hass}M.~H.~Hassoun (Ed.) (1993).
{\it Associative Neural Memories: Theory and Implementation.}
Oxford University Press.
\end{thebibliography}
\end{document}