%%\documentstyle[proceedings,epsf]{article} 
\documentstyle[proceedings,eclepsf]{article} 
 
\title{Genetic Algorithm Enlarges the Capacity of Associative Memory}

\author{ {\bf Akira Imada\thanks{8916-5 Takayama, Ikoma, Nara  630-01 Japan}}  \\
Department of Information Processing\\
Graduate School of Information Science\\  
Nara Institute of Science and Technology\\
akira-i@is.aist-nara.ac.jp\\
\And 
{\bf Keijiro Araki}  \\
Department of Information Processing\\
Graduate School of Information Science\\  
Nara Institute of Science and Technology\\
araki@is.aist-nara.ac.jp 
}

\begin{document} 
 
\maketitle 
 
\parindent 20pt
 
\begin{abstract} 
We propose a genetic algorithm for mutually connected neural networks to obtain a higher capacity of associative memory.
In Hopfield network as an associative memory system, the memory capacity is at most 15\%  of the number of neurons. %% as in standard literatures. 
Here we applied our method to the Hopfield network, 
%and succeeded in doubling its capacity.
and obtained the capacity of 33\%.
%about twice as much as that of Hopfield network by applying our method 
%to connection matrices which memorized some binary patterns by Hebbian rule in advance.
We conjectured that this is due to both asymmetry and sparseness of the connection matrix introduced by the genetic algorithm.
\end{abstract} 
 
\section{Introduction}

In 1982 Hopfield~\cite{hopf} proposed a neural network model as an
associative memory system. He used the Hebbian rule~\cite{hebb} to make
connection matrix memorize a set of patterns.
He estimated experimentally the memory capacity to be 15\% of the
number of neurons. Later the capacity was verified more analytically 
by Amari et al.~\cite{amar} with neurodynamics and by Amit et al.~\cite{amit} with spin-glass theory.
Since Kohonen~\cite{koho} proposed several types of connection matrices for associative memory,
many researchers have successfully improved the capacity in various ways. 
For example, Yanai et al.~\cite{yana} tried that by introducing sparse connectivity, and
Morita~\cite{mori} by using a different dynamic system.
Those mechanisms, however, are not well understood yet.
Here we tried to improve the memory capacity by using a genetic algorithm.\\
\indent
Since the late 1980's there have been a lot of papers dealing with neural
networks by genetic algorithms (see~\cite{whit}). 
Most of them, however, were for layered neural networks 
(see [9, 10] for example), and only a few were for mutually connected neural networks~\cite{fuji}. 
In this paper, we applied a simple genetic algorithm to mutually connected
neural networks, and we have found that it can improve the capacity of associative memory.\\
\indent
We presented in another paper that randomly generated connection matrices
can learn some patterns using a genetic algorithm without any learning rules~\cite{imad}. 
In this paper, on the other hand, we applied a genetic algorithm to the connection matrices which learned some patterns in advance 
by Hebbian rule.\\
\indent
The overall goal for this research is twofold. One is to know if we can use 
the genetic algorithm as a more effective learning method than that proposed so far,
and  the other is to clarify the process of this learning mechanism of the genetic algorithm.\\
\indent        
In the following sections we will present the detailed descriptions of 
our method, some results of our simulations, discussions about our conjecture of 
how we can enlarge the memory capacity, and the conclusions.  

\section{Method}
We simulated associative memory with mutually connected neural networks with 49 neurons. 
\begin{figure}[htbp]
 \begin{center}
   \epsfile{file=overview.eps,width=8.2cm,height=4.1cm}
   \caption{The overview of our genetic algorithm. The original connection matrix $W_{0}$ is remained unchanged during evolution.
And 256 matrices are produced by slightly modifying this original $W_{0}$ in each generation.
The modification is done by being multiplied by zero or $-1$ at a very small rate. 
Note that this time we gave no noise to the patterns.}
   \label{overview}
 \end{center}
\end{figure}
\subsection{Hebbian learning}
The connection weights $w_{ij}$ are determined in advance by Hebbian rule according to 
the initially given \mbox{$p$-patterns}, i.e.,
\begin{displaymath}
w_{ij} = \sum _{ \mu = 1}^{p} { { \xi }_{i}^{ \mu }{ \xi }_{j}^{ \mu }},
\end{displaymath}
\noindent
where $ {\xi}_{i}^{\mu} \hspace{.01in} ( i = 1,2, \cdots , 49)$  is the $i$-th state of the \mbox{$\mu$-th} pattern 
${ \xi }^{ \mu } \hspace{.01in} ( \mu = 1,2, \cdots , p)$, 
and is either 1 or $-1$ generated randomly.
Note that some $w_{ij}$ could be equal to zero by chance when $p$ is even number.\\
\indent
What is new about the application of this algorithm to mutually connected neural network is that
the connection matrix $W_{0}$ calculated in this way remains fixed during the evolution.\\
%\indent
\subsection{population}
We multiply each $w_{ij}$ by $e_{ij} \in \{ -1, 0, 1 \}$ which is
generated randomly where the generation rates of $-1$ and 0 are both at 1/50.
Here we must notice that $-1$ reverses the role of excitation/inhibition 
of connection weight, and 0 prunes the connection. 
By repeating this 256 times, we produce 256 connection matrices which are slightly different from 
the original $W_{0}$.\\
\indent
In our simulation, the larger the population, the higher the capacity we obtained.
In this paper, however, the population size are set to 256, considering the limited resources of our computers.\\
%\indent
\subsection{chromosome}
The chromosome of each individual matrix is made up of these $e_{ij}$. 
The chromosome has the length of  $N^{2}$, and keep its size constant during evolution.\\
\subsection{asynchronous update and fitness}
We evaluate fitness of each chromosome during the states of neurons are updated.
In the beginning, the \mbox{$i$-th} neuron is assigned a value of ${\xi}_{i}^{\mu}$. 
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 $i$-th neuron at time $t$, and $N$ is
the total number of neurons. At each step of updating, a neuron is chosen according to
pre-assigned order (once in a cycle), instead of chosen randomly.
For the remainder of this paper, the term ``update'' will refer to this 
asynchronous update.\\
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=update2.eps,width=8.2cm,height=3.5cm}
   \caption{The evaluation of fitness. The fitness is calculated by summing up the
inner products of initial states(at $t=0$) and the states after being updated $t_{1}$ steps,
over all sets of initially given patterns, and normalizing it.}
   \label{fitness}
 \end{center}
\end{figure}
\indent
As shown in Figure \ref{fitness}, the fitness $f$ of each modified matrix is calculated by summing up the
inner products of initial states and the states after being updated 98 steps,
over all sets of given initial patterns. 
That is,
\begin{displaymath}
f = \frac {1}{49 \cdot p}   \sum _{\mu =1}^{p} 
{ \sum _{j=1}^{49} {s_{j}^{\mu}(0) s_{j}^{\mu}(98)}} 
\end{displaymath}
evaluate the fitness value of each individual in the population.\\
\indent
The time of updates was twice as much as the number of neurons here. And this was enough for the present purpose of selecting 
individuals of higher fitness.
The modification of the original Hebbian learned matrix is made only slightly,
and we eliminate the solution of limit cycle by keeping diagonal elements of connection matrix zero.
As described above,
when states of neurons are updated, a neuron is selected once in a $N$ steps according to the pre-assigned order.
So if all the neurons do not change their states in this cycle, they will not change afterwards. 
Indeed, if the number of neuron which change its state at $N$-th step is zero, or, if the number at $2N$-th step is one, 
we can evaluate that the solution is quite stable.
And this worked well to find solutions of high fitness in our genetic algorithm.
Therefore we set it to $2N$, i.e. 98 in this paper.
We must notice, however, that we need another way of fitness evaluation in the case of randomly generated connection matrix~\cite{imad}.\\

\subsection{mutation and crossover}
The individuals which have higher fitness produce other individuals to make the next generation.
In making offsprings we used the following system of mutation and crossover.\\
\indent
As the mutation, we add one at the rate of 1/100 to the value of allele, which is either $-1$, 0 or 1,
and if the allele value becomes 2 we change it into $-1$.\\
\indent
And then crossover is as follows.
Two chromosomes were chosen randomly from the upper 40\% of the population, 
which is rearranged in every generation in descending order of their fitness value, 
and a new chromosome is produced by taking either allele value of the two parent chromosomes, allele by allele.
Then this is replaced with the one in the lower 60\% of the population. This process is repeated until all the chromosomes
in the lower 60\% of the population are replaced with new chromosomes, in other words, a uniform crossover.
%% i.e. the uniform crossover. 
We show the schematic diagram of the uniform crossover in Figure~\ref{unicrossover}.\\
\indent
We are trying other types of crossover, but up to now we obtain the best results when we use this uniform crossover.\\
\indent
We determined those parameters above through some trial and error tests and set them fixed in the simulation of this paper.\\
\indent
We show the overview of our genetic algorithm in Figure~\ref{overview}.
As we do not give any noise to initial patterns in this paper, each basin volume has not been evaluated yet.
\begin{figure}[htbp]
 \begin{center}
   \epsfile{file=unicrossover.eps,width=7cm,height=5cm}
   \caption{Schematic diagram of uniform crossover. Two chromosomes were chosen randomly from the upper 40\% of the population, 
and a chromosome is produced by taking either allele value of the two parent chromosomes, allele by allele. This is repeated until
all chromosomes in the lower population are replaced.}
   \label{unicrossover}
 \end{center}
\end{figure}

\section{Results and Discussions}
We applied the genetic algorithm above to the Hopfield network, and obtained twice as much associative memory capacity.
In this section we are describing the results of our simulations with some discussions.
\subsection{General features of the evolution}
To grasp the overview of our evolution, let us start from the general features of the evolution of Hebbian learned matrices.
\subsubsection{mild modification}
As we described above, our method modify original connection matrix $W_{0}$ %%, which is kept constant during evolution, 
by multiplying zero and $-1$ at a very small rate.
In this situation, only a few elements of $W_{0}$ are modified even after long generations.
The following is an example of the modification of connection matrix.
\begin{itemize}
\item total number of elements: $49^2$ = 2401
\item number of modified elements: 316 (13.2\%)
\item number of pruned connections: 62 (2.6\%)
\end{itemize}
This is an example for the most successful case where 16 patterns are given to the network, and all of them are successfully memorized 
after evolving 10795 generations. 
13.2\% of the whole connections are modified, and 2.6\% are pruned through evolution.
Though we will describe this  more precisely later, here 
we have to notice that we observe the same tendencies, be it successful or not so, throughout our simulations in this paper.
We have to also notice that all the diagonal elements of connection matrix remain zero during evolution,
because those are set to zero by Hebbian rule before evolution, and can not be changed by being multiplied by any $e_{ij}$.
Therefore we do not allow a neuron to have feedback to itself.
In this sense, the modification might be said to be very mild.
\begin{figure}[hbtp]
\begin{center}
\epsfile{file=evolution2.eps,width=8cm,height=8cm}
   \caption{Examples of fitness versus  generation, for 12, 16, 20, 24, 28 and 32 patterns.}
%   \caption{Examples of fitness versus  generation for 12, 16, 20, 24, 28 and 32 patterns. We must notice that fitness value of 0.500
%is the level of no memory.}
   \label{evolution2}
\end{center}
\end{figure}


\subsubsection{evolvabilty}
The size of the neural network used in this simulation was 49 neurons.
And we simulated with the number of initial patterns to be memorized from 12 to 32. 
Since the connection matrices in this paper had learned those patterns by Hebbian rule beforehand, 
even at the first generation the fitness values are quite high when the number of patterns are small enough.
But still we can observe the fitness increase.
We show some results in Figure~\ref{evolution2}.  

\subsubsection{convergence}
Naturally, the smaller the number of patterns, the faster the fitness attains to the highest value.
We show the generation at which the elitest individual attained the fitness of 1.000 in Table~\ref{convergence}.
For more than 16 patterns, we have not obtained the fitness of 1.000 yet, 
though we could obtain higher capacity with larger population and/or longer generations.
%%at this point of the experiment 16 patterns might be a capacity of our system in this paper.

\begin{table}[bhtp]
\begin{center}
\caption{Generation number at which the elitest individual in the generation attains fitness of 1.000, for 12, 13, 14, 15 and 16 patterns.}
\label{convergence}
\vspace{.1in}
\begin{footnotesize}
\begin{tabular}{c c c c c c}                           \hline \hline
patterns                & 12  &  13   &   14  &   15    &   16    \\   \hline
generation              & 354 & 1268  &  6003 &  6688   &  10795  \\   \hline \hline
\end{tabular}
\end{footnotesize}
\end{center}
\end{table}

%%\subsection{Improvement of Memory Capacity}
\subsection{Twice as much memory capacity}
We succeeded in doubling the associative memory capacity of Hopfield network with the genetic algorithm mentioned above.
This section explore the improvement of the capacity in detail. 
\subsubsection{overlap}
In our simulations, we first generate some patterns ${\xi}^{\mu}$ randomly,
and then determine connection matrix $W_{0}$ according to the patterns by Hebbian rule.
To see the extent to which our method improve memory capacity, we evaluated the memory capacity of this original connection matrix $W_{0}$.
Network with connection matrix $W_{0}$ are given the patterns ${\xi}^{\mu}$ and updated 98 steps in the same way as in the genetic algorithm.
And the overlapping rate defined by
\begin{displaymath}
\frac {1}{49 \cdot p}   \sum _{\mu =1}^{p} { \sum _{j=1}^{49} {s_{j}^{\mu}(0) s_{j}^{\mu}(98)}}
\end{displaymath}
\noindent
are calculated, which is also the same as the fitness defined above.
When an updated state $s_{j}^{\mu}(98)$ overlaps with its initial state $s_{j}^{\mu}(0)$, the product of them is 1, whilst $-1$ otherwise.
So, if all the updated states overlap with their corresponding initial states, the overlapping rate will equal to unity.
And if the half of them overlap with their initial states, this will be zero.
The results obtained are shown in Table \ref{hebbandga}, for 15, 16, 17 and 18 patterns, 
with the fitness values of the elitest individual evolved from the same original connection matrix $W_{0}$.\\
\indent
We can always obtain the higher memory capacity after modifying the connection matrix by the genetic algorithm.\\
\indent
Here we must note that 0.801 in Table \ref{hebbandga}, for example, simply means 
\mbox{$(49 \cdot 15 - 73 \cdot 2)/(49 \cdot 15)$}.
This implies that the total of 73 updated states are different from the corresponding initial states.
These figures in Table~\ref{hebbandga} seems to indicate that the capacity of this system could be 16 patterns.\\

\begin{table}[bthp]
\begin{center}
\caption{Overlapping rate of the states updated 98 steps with their corresponding initial states 
before and after genetic algorithm, for 15, 16, 17 and 18 patterns.}
\label{hebbandga}
\vspace{.1in}
\begin{footnotesize}
\begin{tabular}{l c c c c} \hline \hline
patterns           &    15    &    16    &     17    &     18        \\    \hline
before GA      &  0.801   &  0.842   &   0.772   &   0.752       \\
after GA       &  1.000   &  1.000   &   0.990   &   0.982       \\    \hline \hline
\end{tabular}
\end{footnotesize}
\end{center}
\end{table}

\subsubsection{fixed point}
In Hopfield network, when the number of patterns to be memorized is small enough, all the patterns are
guaranteed to be memorized as a fixed point, i.e.,
\begin{center}
$s^{\mu}(t) = s^{\mu}(0)$, \hspace{.15in}for $\forall t$.
\end{center}
The same does not hold for the patterns greater than the capacity, around eight in this case. 
Take an example of our case for 16 patterns, which exceeds the capacity.
Although a few patterns are still memorized as a fixed point, most of them do not converge.
An example of a pattern which does not converge is shown in Table~\ref{hamming}~(a).
This is a time series of Hamming distance between the initial states and each updated states, 
i.e. the number of neurons different from its corresponding initial states.   
When this pattern is given to the network, overlapping states increases with time of update.
\noindent
After applying the genetic algorithm, however, this pattern was memorized as a fixed point, hence the Hamming distances remain zero from 
the beginning as shown in Table~\ref{hamming}~(b).\\ 
\indent
In this simulation, the matrix which has the fitness of 1.000 implies that all the patterns
initially given to the network are memorized as a fixed point.
\begin{table*}[bthp]
\begin{center}
\caption{An example of time series of Hamming distances between initial states and each updated states,
i.e. the number of neurons different from its initial state at each time, up to 220 time steps. 
Time is from top left towards right.
(a): Worst case out of 16 patterns before genetic algorithm, and (b): after genetic algorithm for the same pattern.}
\label{hamming}
\vspace{.1in}                      
\begin{tiny}
\begin{tabular}{c c c c c c c c c c c c c c c c c c c c c c c c c} \hline
{\bf (a)}\\
 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1& 1& 1& 1 \\ 
 1& 1& 1& 1& 2& 2& 3& 3& 3& 3& 3& 3& 3& 3& 3& 3& 4& 4& 5& 6& 6& 6& 6& 7& 7 \\ 
 7& 7& 7& 7& 7& 7& 7& 7& 7& 7& 7& 7& 7& 7& 7& 7& 8& 8& 8& 8& 8& 8& 8& 8& 8 \\ 
 8& 8& 8& 8& 8& 8& 9& 9& 9&10&10&10&10&10&10&10&10&10&10&11&11&11&11&11&11 \\ 
11&11&11&11&11&11&11&11&11&11&11&12&12&12&12&12&12&12&12&12&12&12&13&13&13 \\ 
13&13&14&14&15&15&15&15&15&15&15&15&15&15&15&15&15&15&16&17&17&17&17&17&18 \\ 
18&18&18&18&18&18&19&19&19&19&19&19&19&19&19&19&19&19&19&19&19&19&19&19&19 \\ 
19&19&19&19&20&20&20&20&20&20&20&20&20&20&20&20&20&20&20&20&20&20&20&20&20 \\ 
20&20&20&20&20&20&20&20&20&20&20&20&20&20&20&20&20&20&20&20&$\cdots$       \\
\hspace{.01in}\\
{\bf (b)}\\
 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\ 
 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\ 
 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\ 
 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\ 
 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\ 
 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\ 
 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\ 
 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\ 
 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0&$\cdots$       \\ 
\hspace{.01in}\\  \hline
\end{tabular}
\end{tiny}
\end{center}
\end{table*}

\begin{small}
\begin{table}[bhtp]
\begin{center}
\caption{The comparison of the number of patterns memorized as a fixed point
before and after genetic algorithm, for 15, 16, 17 and 18 patterns.}
\label{fixedpoints}
\vspace{.1in}
\begin{tabular}{l c c c c} \hline\hline
patterns            &    15   &    16       &     17       &     18       \\    \hline
before GA           &     2   &     4       &      3       &      3       \\
after  GA           &    15   &    16       &     15       &     14       \\    \hline\hline
\end{tabular}
\end{center}
\end{table}
\end{small}
\noindent
The number of patterns which are memorized as a fixed point $p_{0}$ could also be the criterion for the memory capacity.
In Table~\ref{fixedpoints}, we show the number of patterns memorized as a fixed point before and after the genetic algorithm, 
for 15, 16, 17 and 18 patterns, which also seems to indicate 16 patterns are the capacity.\\
%%for the same  connection matrix.

\noindent
From the discussions above, we conjectured the capacity of our method in this paper to be 16 patterns, that is 
33\% of the number of neurons.
In the Hopfield network, on the other hand, the capacity of associative memory
is about 15\% of the number of neurons as described earlier.
As we experimented with 49 neurons here, the eight patterns are around this limit.
Therefore we may conclude that we can double the associative memory of Hopfield network.

%%In the case of the Hopfield network the full connection of the neurons
%%and the symmetric connection matrices might prevent the system having a large capacity. 
%%The genetic algorithms above, however, cut some of the connections during
%%the evolution by multiplying zero to the weight. And the final connection 
%%matrices are not symmetrical.
%%And we suppose that the improvement of the capacity of our simulations
%%is partly due to those facts.\\
%%\indent
%%The performance of the GA-modified-matrix is always higher than the original
%%Hebbian-learning-matrix, but their performances decrease as the number of 
%%patterns increases. %%We show this in Figure~3.
%%Although we did not obtain the fitness of 1.000 for 16 patterns as in Table 1, we regard
%%the network memorized them, because network can retrieve a pattern that is quite
%%close to the initial pattern.
%%Therefore, we conclude that we can obtain the ``effective'' memory
%%capacity of about twice as much as the Hopfield network.

\subsection{Features of the connection matrices}
To investigate what is essential for the improvement in memory capacity, 
we checked two parameters in the elitest connection matrix in each generation, i.e. the degree of symmetry and the number of connections pruned.

\subsubsection{degree of symmetry}

\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=hebb-w-symm.eps,width=8cm,height=8cm}
   \caption{A typical example of transition of degree of symmetry at an early stage of evolution, for 15 patterns.
(This is a different sample from the one in Figure~\ref{symm3}). We can see rapid decrease in earlier generations.}
   \label{symm2}
\end{center}
\end{figure}

We calculated the degree of symmetry $\eta$ of the matrices by 
\begin{displaymath}
\eta = \sum_{i=1}^{N} \sum_{j=1}^{N} {w_{ij} w_{ji}} 
/ \sum_{i=1}^{N} \sum_{j=1}^{N} {w_{ij}^{2}}.
\end{displaymath}
\noindent
At the beginning of the evolution, the connection matrices are symmetric because 
they are determined by Hebbian rule. And as shown in Figure~\ref{symm2} the connection matrix changes quite 
rapidly from symmetry to asymmetry as higher fitnesses are attained.
We also show examples of transition of the degree of symmetry, for 15, 16, 17 and 18 patterns in Figure~\ref{symm3}.
For these patterns the values converge to around 70\% \\
\indent
Consequently, we may conjecture that asymmetry introduced by 0 and $-1$ in the chromosome have 
something to do with the effectiveness of the learning.
%% the patterns. 



\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=hebb-symm.eps,width=8cm,height=8cm}
   \caption{Transition of the degree of symmetry of the connection matrices up to 12000th generation. Examples of 15, 16, 17 and 18 patterns. 
The values converge to around 70\%}
   \label{symm3}
\end{center}
\end{figure}

\subsubsection{rate of pruned connection}
When we start the genetic algorithm, the diagonal elements of the original weight matrix $W_{0}$ are all zero.
In addition, when the patterns given to the network are even number, some of other elements could also be zero,
whilst in the case of odd number of patterns this dose not happen. And these elements of zero do not alter during evolution.  
In producing individuals in each generation, some of the non-zero elements of the original Hebbian matrix become zero by being multiplied by zero
in chromosome. This implies that the connections are pruned, as we described before. Here we define the rate of pruned connection $\zeta$ as
\{the number of non zero elements multiplied by zero in producing individuals\} divided by \{total number of connections\}.
%%\begin{displaymath}
%%\zeta = ( N^2 - \sum_{i=1}^{N} \sum_{j=1}^{N} {e_{ij}^2} ) / N^2.
%%\end{displaymath}
%%As is the case of degree of symmetry,
As shown in Figure~\ref{zero2}, the rate of pruned connection increases quite rapidly until higher fitness is obtained, 
and does not alter drastically afterwards.
We also show an example for 15, 16, 17 and 18 patterns in Figure~\ref{zero3}. We can observe the rates converge approximately to the value of 3\%.\\ 
\indent 
Hence, we may conjecture that pruned connections also play an important role to improve the associative memory capacity of Hopfield network.
%The behavior of the zero rate in the connection matrix, on the other hand, is somewhat different from the degree of symmetry above. 
%We define the zero rate $\zeta$ as the number of zero in the connection matrix divided by total number of connectivity $N^{2}$.
%When we start the algorithm, the zero rates are $49/49^2 \sim 0.02$ bediscribedcause orthogonal factors of Hebbian matrix are all zero. 
%And from the first generation, the elitest connection matrix has certain levmechanisms,hoel of zero rate and does not alter its value drastically afterwards. 
%Here we noticed the fact that there were two stable levels of zero rate, depending on the number of patterns.
%We show an example of 15, 16, 17, and 18 patterns in Figure~\ref{zero2}.
%In the case of p = 15 and 17, we observed the zero rates of 6.1\% and 7.2\% respectively, 
%while in the case of p = 16 and 18, 24.1\% and 25.0\% respectively. 
%Including other cases, we have observed the zero rate of around 7\% for odd number of patterns, whilst 25\% for even number of patterns.
%As for this phenomena, however, we have to keep simulating to know why.
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=figzero1.eps,width=8cm,height=8cm}
   \caption{An Early stage of the rate of pruned connection. An example of 15 patterns. We can see quite a rapid increase.}
   \label{zero2}
\end{center}
\end{figure}

\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=figzero4.eps,width=8cm,height=8cm}
   \caption{Transition of rate of pruned connection up to 12000th generation. Examples of 15, 16, 17 and 18 patterns. The values
converge to around 3 through 4\%.}
   \label{zero3}
\end{center}
\end{figure}

\subsubsection{roles of 0 and -1 in the chromosome}

As described earlier, $-1$ in the chromosome reverses the role of excitation/inhibition 
of the weight, and 0 prunes the connection. 
To ascertain the effect of $-1$ and 0 in the chromosome,
we made the following two experiments. One is with chromosomes chosen from $\{-1, 1\}$ and the other is from
$\{0, 1\}$, with other parameters remain exactly the same as those chosen from $\{-1, 0, 1\}$ above.
We showed the results in Figure~\ref{crom}.
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=rollofzeroh15.eps,width=8cm,height=8cm}
   \caption{The evolution of the fitness with the chromosome chosen from (a):~\{1, 0, $-1$\},
             (b):~\{1, $-1$ \} and (c):~\{1, 0\}. In the case of (c), the evolution was trapped in a local minimum.} 
   \label{crom}
\end{center}
\end{figure}
\noindent
As we can see in Figure~\ref{crom}, although the chromosome chosen from (a):$\{-1, 0, 1\}$ worked most effectively,
the chromosome chosen from (b):$\{-1, 1\}$ also worked. In the case of the chromosome chosen from (c):$\{0, 1\}$, however, it was trapped
in a local minimum at an very early stage of evolution.
The number of fixed points obtained in the experiment(b) was 14, whereas 9 in the experiment(c).
The role of $-1$ seems to be more important than 0, but we also need 0 to obtain 16 fixed points in the experiment(a). 
And in addition, $-1$ helps to avoid being trapped in a local minimum.\\


\noindent
With those results described here we may conclude that both full connectivity and 
symmetry of the connection matrices prevented the networks from 
attaining high memory capacity in Hopfield network, though we need further analysis to explain these phenomena.


\subsection{Generality of those simulations}
In each number of patterns above, we repeated simulations with 20 (or more) different seeds of random numbers 
with other parameters remain fixed, and we were able to observe the general tendencies described here.
Some examples of the data from 15 patterns are shown in Table \ref{generality}.\\
\indent
The figures in this paper are mainly those of best results out of these simulations.\\
\begin{table}[bthp]
\begin{center}
\caption{Example of data from ten simulations with different seeds of random numbers with other parameters remain fixed, for 15 patterns.
The letters $f$, $\zeta$, $\eta$, $\delta$ and $p_{0}$ in the first row  represent fitness, rate of pruned connections, degree of symmetry, 
rate of modified elements of the connection matrix and rate of patterns memorized as a fixed point, respectively.}
\label{generality}
\begin{footnotesize}
\vspace{.1in}
\begin{tabular}{l c c c c c} \hline \hline
\hspace{.01in}  &  $f$       &   $\zeta$    &   $\eta$    &  $\delta$ &    $p_{0}$     \\  \hline
pattern - a    &  0.986      &   0.035      &   0.673     &   0.199   &      12        \\
pattern - b    &  1.000      &   0.041      &   0.676     &   0.201   &      15        \\
pattern - c    &  0.997      &   0.042      &   0.654     &   0.209   &      14        \\
pattern - d    &  0.997      &   0.039      &   0.659     &   0.190   &      14        \\
pattern - e    &  0.992      &   0.024      &   0.696     &   0.166   &      12        \\
pattern - f    &  0.984      &   0.037      &   0.623     &   0.196   &      13        \\
pattern - g    &  0.995      &   0.030      &   0.708     &   0.162   &      13        \\
pattern - h    &  1.000      &   0.052      &   0.634     &   0.250   &      15        \\
pattern - i    &  0.995      &   0.027      &   0.696     &   0.164   &      13        \\
pattern - j    &  0.989      &   0.046      &   0.635     &   0.214   &      13        \\  \hline \hline
\end{tabular}
\end{footnotesize}
\end{center}
\end{table}

\section{Conclusions}
First, we proposed a new simple technique of genetic algorithm to modify the connection matrix of
a mutually connected neural network to enlarge the associative memory capacity of Hopfield network.
The feature of our technique is to keep the original connection
matrix unchanged during the evolution. 
The individuals of each generation are slightly different from 
the original weight matrix, keeping the diagonal elements zero.
This is done by multiplying $-1$ or 0 at a very small rate to the original matrix, 
which introduces both asymmetry of the weight matrix and sparseness of the connections.
The genetic algorithm searches the best allocation of zero and $-1$ in the chromosome to obtain a higher capacity.\\
\indent
Next, we described that this technique is quite successful in
improving the associative memory capacity of Hopfield network.
The capacity was always higher in the modified connection matrix 
than in the original matrix learned by Hebbian rule.
We obtained the capacity of about 33\% of the number of neurons after 
applying the genetic algorithm whereas the original Hebbian matrix has 
the capacity of about 15\%.\\
\indent
We suppose this effect is due to the sparseness of connection and the asymmetry of
weight matrix introduced by the genetic algorithm.\\
\indent
Our investigations, however, have not been conclusive on this point, due to 
the difficulty of specifying exactly what is meant by these asymmetry and sparseness.
In the present studies we have shown that there is already some possibility to use our method
to obtain high capacity of associative memory.

\section{Future works}
The results reported in this paper should be thought of as a first attempt to establish a method to obtain
higher associative memory capacity and construct a model to explain the mechanism. 
And we are thinking of the following procedures as a next step.\\
\indent
First, to make the results more reliable, we want to simulate neural networks with at least 100 neurons instead of 49 neurons.
The problem is the time of simulation. So we are beginning to explore them by parallel processing on a distributed system.\\
\indent
Second, to make our simulation more effective, we are introducing continuous values with the sigmoid function instead of discreate values 
with the signus function.
In addition, we use either $-1$ or 0 in the chromosome to modify the weight values,
and they do not change the absolute value of the connection weights except for the case of making them zero. 
So, we are thinking of other types of chromosome and crossover to change the weight values more flexibly through evolution.\\ 
\indent
Third, we are trying to combine some weight matrices obtained from independent simulations 
in order to attain much higher capacity, though we have not succeeded yet.\\
\indent
Finally, we should construct a model to account for the phenomena described in this paper.



\section*{Acknowledgements}

We thank Peter Davis and Shin Ishii at ATR (Advanced Telecommunication 
Research Institute) for giving us helpful comments and suggestions about the evolution of 
associative memory of recurrent neural networks. Thanks also go to other people 
at ATR as well as at NAIST (Nara Institute of Science and Technology) 
who gave us useful discussions at various stages of this research. 


\newpage
\begin{thebibliography}{99}

\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.} New York: Wiley.
\bibitem{amar}S.~Amari, and K.~Maginu (1987). Statistical Neurodynamics of Associative Memory. {\it Neural Networks} {\bf 1}:63-73.
\bibitem{amit}D.~J.~Amit, H.~Gutfreund, and H.~Somplinsky(1987). Statistical Mechanics of Neural Networks near Saturation. 
{\it Annals. of Physics} {\bf 173}:30-67.
\bibitem{koho}T.~Kohonen (1977). {\it Associative Memory: A System-Theoretical Approach.} Berlin Heidelberg: 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{whit}J.~D.~Schaffer, and D.~Whitley (1992) (ed.), 
{\it Proceedings of the Workshop on Combinations of Genetic Algorithms And Neural Networks.} The IEEE Computer Society Press.
\bibitem{kita}H.~Kitano (1990). Designing Neural Networks using Genetic Algorithm with Graph Generation System. {\it Complex Systems} {\bf 4}:461-476.

\bibitem{grua}F.~Gruau, and D.~Whitley(1993). Adding Learning to the Cellular Development of Neural Networks Evolution and Baldwin Effect. 
{\it Evolutionary Computation}:213-233.
\bibitem{fuji}S.~Fujita, and H.~Nishimura (1994). An Evolutionary Approach to Associative Memory in Recurrent Neural Networks. 
{\it Technical Report at Hyogo University of Education.} HUIS-94-3.
\bibitem{imad}A.~Imada, and K.~Araki (1995). Genetic Algorithm as a Learning Method in Associative Memory.  
WCNN'95 (to appear).

\end{thebibliography}

\end{document}







