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

%%\title{Evolution of Hopfield Model of Associative Memory  by the Breeder Genetic Algorithm}
\title{Evolution of a Hopfield Associative Memory\\by the Breeder Genetic Algorithm}

\author{
        {\bf 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\\
\And
        {\bf 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
}

\begin{document}
\maketitle

\begin{abstract}
We apply some variants of evolutionary computations to the Hopfield model of associative memory.
In this paper, we use the Breeder Genetic Algorithm (BGA) to explore the optimal set of synaptic weights with respect to the storage capacity.
We present the BGA has tremendous ability to search a solution in the massively multi-modal landscape of the synaptic weight space.
The main goal of this study is to shed new light on the analysis of the Hopfield model of associative memory.
We also expect the model to be used as a new test function of evolutionary computations.
\end{abstract}



\section{INTRODUCTION}
Associative memory is a dynamical system which has a number of stable states with a domain of attraction around them~\cite{koml}.
If the system starts at any state in the domain, it will converge to the stable state.
In 1982, Hopfield~\cite{hopf} proposed a fully connected neural network model of associative memory
in which we can store information by distributing it among neurons, and we can recall it from its noisy and/or partial input.

The dynamical behavior of its neuron states strongly depends on synaptic strength between neurons.
The synaptic strength from neuron $j$ to neuron $i$ is called {\it weight} and denoted as $w_{ij}$. 
Hopfield used  the Hebbian rule~\cite{hebb} to determine them.
So far, a lot of methods to prescribe $w_{ij}$'s have been proposed.

Since the Hopfield's proposal, many discussions have been made extensively, nevertheless some issues still remain open.
How many solutions exist in synaptic weight space is an example.
The distribution of the solutions is also of interest.
We explore these issues by applying evolutionary computations to the model.
If, for example, we can locate all the solutions, we will have a new information about the model.
In the sense, this study sheds new light on the analyses of the Hopfield model of associative memory.

In this paper, we apply the Breeder Genetic Algorithm (BGA) proposed by M\"{u}hlenbin et al.~\cite{MSV} to the Hopfield model of associative memory.
The BGA is based on ``{\it artificial selection similar to that used by human breeders}''
expecting ``{\it artificial selection to be more efficient for optimization than natural selection}''~\cite{MSV}.

M\"{u}hlenbein et al. applied the BGA to multi-modal test functions 
and concluded that ``{\it the BGA mutation scheme is able to optimize many multi-modal functions.''}
However, they also say ``{\it But are such problems typical applications? We have not encountered such a problem.}''
We might take the Hopfield model  as a test function of the multi-modal parameter optimization problem.
In fact, for a given set of random patterns to be stored, searching an appropriate combination of $\{w_{ij}\}$ is a real parameter optimization problem.

M\"{u}hlenbein wrote in the paper that ``{\it a good theory has to be proven with challenging applications}'',
and we take the Hopfield model as a more challenging benchmark than the existing common test functions  for evolutionary computations.

The remainder of this paper is organized as follows.
Since we modify only the synaptic weights in the framework of the Hopfield model, 
the model is described more fully in the following section.
The other evolutionary approaches to the Hopfield model will be described  in the third section.
The fourth section presents our BGA implementation.
After presenting experimental results and discussion, the final section describe the concluding remarks.

\section{THE HOPFIELD MODEL}
The model consists of $N$ neurons and $N^2$ synapses.
Each neuron can be in one of two states $\pm 1$, and $p$ bipolar patterns
\begin{displaymath} 
{\xi}^{\nu} = ({\xi}^{\nu}_{1},\cdots,{\xi}^{\nu}_{N}), \hspace{.2in}{\nu} = 1, \cdots, p
\end{displaymath}
where $\xi^{\nu}_{i}$ takes the value of either 1 or $-1$, are to be memorized as equilibrium states.
Hopfield employed a discrete-time, asynchronous update scheme.
Namely, at most one neuron updates its state at a time\footnote
{Though Hopfield chose one neuron at a time {\it randomly}, in this paper, a neuron is chosen according to pre-assigned order (once in a cycle).}
, according to 
\begin{displaymath}
s_{i}\hspace{.02in} (t+1) = sgn \hspace{.02in} \left( \hspace{.04in} \sum_{j \ne i}^N { w_{ij} s_{j}(t)} \hspace{.04in} \right),
\end{displaymath}
where $s_{i}(t)$ is a state of $i$-th neuron at time $t$.
The behaviors of the collective states of individual neurons are characterized by the synaptic weights.
When these synaptic weights are determined appropriately, networks store some number of patterns as fixed points.
Hopfield specified these $w_{ij}$'s by the Hebbian rule \cite{hebb}, i.e.,
\begin{displaymath}
w_{ij} = \frac{1}{N} \sum _{ \nu = 1}^{p} {{ \xi }_{i}^{ \nu }{ \xi }_{j}^{ \nu }}\hspace{.1in}(i \ne j), \hspace{.1in} w_{ii} = 0.
\end{displaymath}
Then giving one of the memorized patterns, possibly including a few errors, to the network as an initial state
will result in the stable state after certain time steps.
Hopfield suggested by using computer simulation that the maximum number $p$ of the patterns to be stored in a network with $N$ neurons is $0.15N$,
on the condition that a small error in recalling is allowed.
Later, this was theoretically calculated by Amit et al.~\cite{ags} by using {\it replica} method. 
They showed that the storage capacity is $ p=0.138N $.
In 1987, McEliece et al.~\cite{mcel} proved that when $p < N / 4 \ln N$ holds, the Hopfield's model is able to recall the memorized patterns without error.

The storage capacity depends on how synaptic weights are specified. 
The specification of the synaptic weights is conventionally referred to as {\it learning}.
Other learning schemes have been proposed for their increased storage capacity. 
Kohonen et al.~\cite{koho} proposed the {\it pseud-inverse matrix method} by extending the Hebbian learning rule, and enlarged the capacity to $p=N$.

Then, what is the ultimate capacity when only the learning scheme is explored within the Hopfield's framework?
Generally the storage capacity is traded off against basin size.
Gardner~\cite{gard} studied the optimal storage capacity as a function of the size of basin of attraction.
She showed that the ultimate capacity will be $p=2N$ as the basin size tends to zero\footnote
{we can increase the storage capacity exponentially instead of proportionally by modifying the architecture of the network.
The ultimate storage capacity might be $2^N$ (see e.g.~\cite{chiu}).}. 
She also proposed  an algorithm to realize it.

\section{RELATED WORKS}
In the classical analyses of the Hopfield model, the Hebbian synaptic weights $J_{ij}$ were modified.
For example, Derrida et al.'s~\cite{DGZ} pruned some of the Hebbian synapses by
\begin{displaymath}
J_{ij} \times c_{ij},
\end{displaymath}
where $c_{ij}$'s take the value of either 0 or 1. 
Or Somploinsky~\cite{somp} gave small perturbations on the Hebbian synaptic weights by
\begin{displaymath}
J_{ij} + \eta_{ij},
\end{displaymath}
where $\eta_{ij}$ is a Gaussian random variable of mean 0 and small standard deviation.
Both of them showed the robustness of the network for synaptic noises.

We modify synaptic weights essentially with these two schemes using evolutionary computations.
The difference is that they selected synapses to be modified {\it randomly}, while we select synapses {\it adaptively}.

Previously, we reported that a genetic algorithm  enhances the storage capacity of the Hebb rule associative memory 
by {\it pruning} some of the connections.~\cite{imad-1}.
We also reported that the genetic algorithm  evolves the random synaptic weights to store some number of random patterns~\cite{imad-7}.

At the same time, we can evolve the synaptic weights by {\it giving perturbations} on them~\cite{imad-12,imad-13}.
In this implementation, an allele in the chromosome represents a perturbation $\eta_{ij}$, and this is added to 
a component of the original matrix which remains fixed during evolution.
Then genetic operations work on these perturbations.
In this paper, on the other hand, it is the components of weight matrices $w_{ij}$'s that are represented by alleles,
and perturbations are given by mutations.
In the former case, search points explore within a small domain around a specific point, while in the latter case
they are allowed to wander all over search space.
 
\section{THE BGA IMPLEMENTATION}
In this simulation, a set of $p$ random bipolar patterns ${\xi}^{\nu}$ (${\nu} = 1, 2, \cdots, p$) are produced before each run.
The goal of the BGA is to search weight matrices which store all of these patterns as fixed points.
At the beginning of a run, a population of chromosomes are initialized.
Chromosome is a  real-valued $N^2$-dimensional vector which represents a set of synaptic weights of an individual network, i.e.,
\begin{displaymath}
(w_{11}, w_{12}, \cdots, w_{1N}, w_{21}, \cdots \cdots, w_{NN}).
\end{displaymath}
In each generation, these chromosomes are modified through crossover and mutation operation,
and fitness value of individual phenotype is evaluated.
According to the fitness values, individuals of the next generation are selected.
The cycle of reconstructing the new population with better individuals and restarting the search is repeated until a perfect
solution is found or a maximum number of generation has been reached.
Specific details of the operations are  as follows.

\begin{description}
%%\item[]{\bf Initialization:}
\item[] {\bf Fitness evaluation:}
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 an associative memory, the instantaneous network state must be similar to the input pattern $\xi^{\nu}$. 
The similarity is defined by,
\begin{displaymath}
m^{\nu}(t) = \frac{1}{N} \sum_{i=1}^{N} { {\xi}_{i}^{\nu} s^{\nu}_{i}(t) },
\end{displaymath}
where $s_{i}^{\nu}(t)$ is the state of neuron $i$ at time $t$. 
%%Clearly it is related to Hamming distance between the two states.
This $m^{\nu}(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^{\nu}(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 _{\nu=1}^{p}{m^{\nu}(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.
%%The attractor distributions are parametrized by these $p$ overlaps $m^{\nu}$.

\item[] {\bf Selection:}
The BGA uses the truncation selection~\cite{MSV}, i.e., two parent chromosomes are chosen {\it randomly} from the best $T$\% of the population.
and mated randomly (except for itself) to produce one offspring. 
This is repeated until the number of offspring is equal to the size of the population.
\item[] {\bf Recombination:}
Recombination is made with discrete crossover~\cite{MSV} which is similar to {\it uniform crossover} \cite{sysw} in binary chromosomes.
It operates on alleles of the selected parents' chromosomes.
Two parents, $(u_1, \cdots, u_n)$ and $(v_1, \cdots, v_n)$, produce an offspring $(w_1, \cdots, w_n)$
so that $w_i$ is either $u_i$ or $v_i$ with equal probability.
M\"{u}hlenbein et al.~\cite{MSV} proposed  other two crossovers: {\it extended intermediate crossover} and {\it extended line crossover}.
We tested these two crossovers, however the results were both disappointing for our case.
This is probably because these two schemes change the values of synaptic weights, while the discrete crossover only shuffles them.

\item[] {\bf Mutation:}
An allele $x_{i}$ is chosen with probability $p_{m}$ to be mutated.
The BGA mutation is to give a small perturbation $\mit\Delta x_{i} \times \delta$ on a variable $x_{i}$,
where $\mit\Delta x_{i}$ is a mutation range for the variable $x_{i}$, and $\delta$ is calculated as
\begin{displaymath}
%%\delta = \frac {\alpha_0}{2^0} + \frac {\alpha_1}{2^1} + \frac {\alpha_2}{2^2} + \cdots + \frac {\alpha_{15}}{2^{15}}.
\delta = \alpha_0 + \frac {1}{2}\alpha_1 + \frac {1}{2^2}\alpha_2 + \cdots + \frac {1}{2^{15}}\alpha_{15}.
\end{displaymath}
Each $\alpha_{k}$ takes the value 1 with probability $1/16$, and otherwise takes the value 0.
Then mutated new allele is 
\begin{displaymath}
x_{i} \pm {\mit\Delta}_{i} \times \delta,
\end{displaymath}
with the sign $+/-$ being chosen with equal probability.
\end{description}

\section{EXPERIMENT}
All experiments in this paper are carried out on networks with 49 neurons. 
The update scheme are based exactly on the Hopfield model.
Only synaptic weight values are explored with the BGA.

Parameters used for the BGA are as follows.
The population number is 256. 
In truncation selection, $T$ is chosen to be 40\%.  
The mutation range $\mit\Delta x_{i}$ is set to 0.1 for all $x_i$, 
since M\"{u}hlenbein et al. recommended it to be set to 0.1 times the search interval of $x_i$,
and our $x_i$, synaptic weight value, takes the value out of $[-1, 1]$.
As for mutation probability $p_m$, M\"{u}hlenbein et al.'s suggestion is $1/n$, where n is the number of alleles in a chromosome.
However, this is too small because of the robustness of the Hopfield network for synaptic noises.
Hence we set it to $100/n$ instead, i.e., $100 / 49^2 = 100 / 2401$. 
Searching procedure is iterated until 12000 generations unless a solution is found.


\section{RESULTS AND DISCUSSION}
\subsubsection*{Departure from Random Matrices\footnote{This expression is taken from Amit~\cite{amit}.}}
\noindent
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=hamming-r.eps,width=6cm,height=3.5cm}
   \epsfile{file=hamming-h.eps,width=6cm,height=3.5cm}
  \caption{Examples of Trajectories}
   \label{hamming}
 \end{center}
\end{figure}
In the first experiment, individuals are initialized randomly.
In other words, each network in the first generation is assigned a different set of random synaptic weights.
They do not function as an associative memory but each input of a given set of random patterns results in a chaotic trajectory.
In Figure~\ref{hamming} (a), we show examples of these trajectories taken from our experiment.
The Hamming distance of instantaneous network state from the input is plotted against updating time.

The BGA evolves these random matrices by adapting them to the patterns.
Up to 9 patterns, we were able to obtain the matrix that creates fixed point attractors exactly at the location of given patterns.
Note that this limit of the storage is slightly higher than the capacity of the network of the same size 
when synaptic weights are determined by the Hebbian rule.
In Figure~\ref{evolution-r}, we show the best fitness vs generation curve when 9 patterns are given.

\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=fitness-r.eps,width=6cm,height=4cm}
   \caption{Best Fitness vs Generation}
   \label{evolution-r}
 \end{center}
\end{figure}

\subsubsection*{Departure from Over-loaded Hebbian Matrix}
Then we proceed to the next experiment.
We initialize all the individuals with an over-loaded Hebbian matrix.
By over-loaded, we mean that the network learns the patterns exceeding the capacity.

The network of this type was analytically studied by Amit et al.~\cite{ags-2}.
When the number of patterns $p$  approaches to the capacity, some of the memorized states are shifted slightly. 
As $p$ increases further, some inputs of these patterns relax to the other attractors rather than to the memorized states,
and finally, the network will be dominated by the vast amount of  spin glass attractors.

As shown in Figure~\ref{evolution-h}, we successfully evolved this type of networks to re-store all the given patterns as fixed point attractors. 
We have obtained a maximum storage of 25 patterns so far.
The evolution we obtained this result started with the matrix where each of the given patterns converges to the attractor 
whose Hamming distance from the input is 
1, 1, 2, 4, 5, 10, 11, 12, 12, 12, 13, 14, 14, 14, 15, 15, 16, 17, 17, 17, 19, 19, 19, 21 and 22.
No fixed point attractor was found.
In Figure~\ref{hamming} (b), two of these 25 trajectories are shown.
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=fitness-h.eps,width=6cm,height=4cm}
   \caption{Best Fitness vs Generation}
   \label{evolution-h}
 \end{center}
\end{figure}

\subsubsection*{Departure from Zero Matrix}
Then the above enhancement of the storage from 9 to 25 patterns is due to the Hebbian learning?
The answer is no. To see this, we started the BGA with the {\it all-zero-component-matrix} for a change\footnote{
This is refered to as learning from {\it tabula rasa.}}, 
and we also succeeded in evolving this matrix to store all the 25 patterns as fixed points.
Therefore, we might conclude the above enhancement in storage capacity is due to the search from one specific point 
rather than from randomly distributed points.

However, the success is strongly dependent on the point to be started.
We have not been able to observe the solution started with an identical arbitrary determined random matrix for 25 patterns.

We increment the number of given patterns in this 3rd experiment.
So far, we have observed that the zero matrices can evolve to store up to 90 patterns as fixed points.
Surprisingly large number of storage patterns.
We show the result in Figure~\ref{evolution-z}.
Moreover, we must note that the values of diagonal elements of the obtained matrix here were of the same order of magnitude as the off-diagonal elements.
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=fitness-z.eps,width=6cm,height=4cm}
   \caption{Best Fitness vs Generation}
   \label{evolution-z}
 \end{center}
\end{figure}

\subsubsection*{Identical vs Different Initialization}
Usually in genetic algorithms, individuals are initialized randomly as our first experiment, 
so that starting points are distributed randomly over the search space.
In fact, in the M\"{u}hlenbein et al.'s experiment~\cite{MSV} ``convergence means that all individuals have the same value.''

In the latter two of our experiments, all individuals start the search from a specific point in the space.
This initialization works much more effective for the current problem.
%%, unless the search stagnates by some local minima near the starting point.
In this case, the discrete crossover does not work initially, since all the individuals are similar. 
However the BGA mutation increases diversity of the population quickly, which enables the evolution.
In Figure~\ref{sigma}, the standard deviation of the best fitness value is plotted against generation number, 
for the evolution shown in Figure~\ref{evolution-h}.
%%started from over-loaded Hebbian matrrx given 25 patterns as an example.
The fitness diversity grows rapidly in early stages.
Then, as in Figure~\ref{distribution}, we can observe enough diversity of population, say at generation 50, is obtained,
and finally the most of the population converge to a solution.
 
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=sigma.eps,width=6cm,height=4cm}
   \caption{Time Development of Standard Deviation}
   \label{sigma}
 \end{center}
\end{figure}
\noindent
\begin{figure}[hbtp]
 \begin{center}
%%   \epsfile{file=distribution-r.eps,width=6cm,height=5cm}
   \epsfile{file=distribution-h.eps,width=6cm,height=4cm}
   \caption{Fitness Distribution}
   \label{distribution}
 \end{center}
\end{figure}

\subsubsection*{The Search Becomes Difficult as $p$ Increases?}
Each experiment was repeated 30 times with different random number seed.
For a given set of 25 patterns, the BGA starting with the over-loaded Hebbian matrix locates one of the optimum solutions in 7 runs, 
while 25 runs locate a solution starting with zero matrix.

In our problem, it usually becomes difficult to locate a solution as the number of patterns increases.
For example, a genetic algorithm using normal random mutation~\cite{imad-12} located a solution in the way shown in Table~\ref{sga}. 

\begin{table}[hbtp]
\begin{center}
%\caption{Number of Patterns vs Successful Run\\ \hspace*{1.91in}(out of 30 trials)}
\caption{Number of Patterns vs Successful Run Taken from a GA with Uniform Random Mutation~\cite{imad-12}\\ (out of 30 trials)\\}
\label{sga}
\begin{tabular}{c c c c c c } \hline \hline
number of patterns  &   14   &   15   &   16    &    17   &   18         \\    \hline
Successful trial    &   22   &   17   &    5    &     2   &     0        \\    \hline \hline
\end{tabular}
\end{center}

\end{table}

In the BGA starting with zero matrix shows somewhat peculiar behaviors.
It seems to locate a solution more easily for larger number of given patterns.
We have observed that it locates a solution in 27 out of 30 trials for 25 patterns, 
while it locates a solution in all of 30  trials for 49 patterns.
For 90 patterns, although we have tried only 5 trials, we succeeded to find the optimum in all the 5 trials.

\subsubsection*{Can the BGA Locate All the Optima?}
It is difficult  to locate all the optima in multi-modal fitness landscape, while it is comparatively easy to locate one of the optima.
We are running the BGA starting with zero matrix for a given set of 49 patterns which remains fixed over the runs.
We observed the spatial distribution of the solution by measuring the Euclidian distance of each solution from the origin.
So far, we have tried 68 runs and observed that 67 runs locate the optimum solution.
Only two out of the 67 runs have located one exactly the same solution, and others have located different solutions. 
The Euclidian distances of the optimum from the origin were ranging from 4.556 to 16.297 dependent on the random number seed at the start.
This result shows that there exit many different solutions within this domain of hyper-sphere.
Hence, we might conclude  that the BGA locates these multi-modal solutions 

\subsubsection*{Degree of Symmetry of the Weight Matrix}
To see the difference further between our 2nd and 3rd experiment,
we investigated the time evolution of degree of symmetry of weight matrices.
We define the degree of symmetry, following Krauth et al.~\cite{krau}, as follows:
\begin{displaymath}
\sum_{i=1}^{N} \sum_{j=1}^{N} {w_{ij} w_{ji}} \cdot \left( \sum_{i=1}^{N} \sum_{j=1}^{N} {w_{ij}^{2}} \right)^{-1}.
\end{displaymath}
We show the results in Figure~\ref{symmetry}. 
At the beginning, both matrices are  totally symmetric.
The Hebbian matrix decreases its degree of symmetry as evolution proceeds.
Then it asymptotically approaches to the value around 0.6.
The BGA started with the Hebbian matrix seems to hillcrimb by introducing small amount of asymmetry to the Hebbian matrix.
In the evolution started with zero matrix, the degree of symmetry decreases abruptly and remains zero thereafter.

\noindent
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=symmetry.eps,width=6cm,height=4cm}
   \caption{Time Development of Degree of Symmetry}
   \label{symmetry}
 \end{center}
\end{figure}

\subsubsection*{Basin of Attraction}
Hertz et al.~\cite{herz} suggested that an asymmetry of the synaptic weights destabilizes spin-glass attractors, 
without affecting the memorized state strongly.
The effect of destabilizing spin-glass attractors will enlarge the basin of attraction of the memorized states.

We observed the basin size of the network of the above experiments as follows.
An input is produced from the memorized patterns by flipping $d$ bits at random.
Then this is given to the network, and temporal average of {\it overlaps} of the network state visited by the dynamics is calculated.
This is repeated 800 times for each incremented value of $d$.

In Figure~\ref{basin}, the averaged overlap over the 800 repetitions are plotted against the number of noisy-bit $d$,
for the obtained matrices described in Figure~\ref{evolution-h} and \ref{evolution-z}, 
together with the one derived from the Gardner's optimized algorithm~\cite{gard}.
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=basin.eps,width=8cm,height=4cm}
   \caption{Comparison of Basin of Attraction}
   \label{basin}
 \end{center}
\end{figure}

The BGA started with a Hebbian matrix can establish a fair amount of asymmetry which leads to
about the  same size of basin of attraction of the Gardner's optimized network.
The suggestion by Hertz et al. seems to be  supported here.

On the other hand, the evolution started with zero matrix yields small basin of attraction.
This is probably because the 100\% asymmetry is too strong to remove spurious attractors around the created memory.

Parisi~\cite{pari} suggested another effect of asymmetry, i.e., converting the spin-glass attractors into chaotic trajectories.
We leave this issue to our future research.

\subsubsection*{Evolution only by the BGA mutation}
One objectives of our study is to analyze the Hopfield model of associative memory using evolutionary computations.
The recombination operation makes the analysis difficult.
Hence, we tried to evolve networks only by the BGA mutation starting with the zero matrix.
However, for even a set of 6 patterns, we were not able to obtain a solution as in Figure~\ref{evolution-m}.
The search seems to stagnate soon by a local minimum near the origin.
In the BGA, {\it selection, recombination, and mutation seem to have a synergetic effect} as M\"{u}hlenbin et al. suggested~\cite{MSV}.

\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=fitness-m.eps,width=6cm,height=4cm}
   \caption{Best Fitness vs Generation}
   \label{evolution-m}
 \end{center}
\end{figure}

\section{CONCLUSIONS}
We have described an application of the Breeder Genetic Algorithm to the Hopfield model of associative memory.
We found that networks with 49 neurons evolved to store a maximum of 25 given patterns started with over-loaded Hebbian matrix. 
Furthermore, we found that networks of the same size evolves to create fixed point attractors 
exactly at the location of each given patterns even when the number of patterns was 90.

The network of this size would store only 8 patterns with the Hebbian learning rule. 

Our previous experiments using Evolution Strategy (ES), for example, 
found the network which stores a maximum of 17 patterns started with the over-loaded Hebbian matrix
and 8 patterns started with zero matrix~\cite{imad-11}.

The evolutionary algorithms using adaptive mechanism of mutation, like ES, require elaborate tunings of the relevant parameters.
M\"{u}lenbein et al.~\cite{MSV} wrote: {\it ``the BGA mutation does not need an adaptation of the mutation range.''}
All we had to determine was population size and probability $p_m$.
(Note that for usual applications, $p_m = 1/n$, where $n$ is a number of variables, is recommended by M\"{u}hlenbein et al.)

We expect the BGA will be able to find solutions for more number of given patterns.
Furthermore, if, for example, the BGA is able to locate {\it all} the solutions in the synaptic weight space 
which give a network a function of associative memory,
then we will have an important information about the number and the distribution of these solutions,
which are still open issues despite of the extensive discussions since Hopfield proposal.

Therefore, we believe these studies  will shed new light on the analysis of the Hopfield model.

At the same time the model could be a more challenging test function
than the existing common test functions  for evolutionary computations.

Other problems like the fate of the spin-glass attractors as well as the chaotic trajectories which exist before evolution,
are also waiting for our explorations.

\subsubsection*{Acknowledgments}
\noindent
We thank Peter Davis at Advanced Telecommunication Research Institute (ATR)
for providing us great insights into the dynamics of the Hopfield neural networks.
Thanks are also due to anonymous reviewers for comments and encouragements on this work.

\begin{thebibliography}{5}

\bibitem{koml}J.~Koml\'{o}s, and R. Paturi (1988).
{\em ``Convergence Results in an Associative Memory Model.''} 
Neural Networks {\bf 1}. pp239--250.

\bibitem{hopf}J.~J.~Hopfield (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}D.~O.~Hebb (1949).
{\it The Organization of Behavior.} Wiley.

\bibitem{MSV}H. M\"{u}hlenbein, and D. Schlierkamp-Voosen (1995)
{\em ``Predictive Models for the Breeder Genetic Algorithm I. Continuous Parameter Optimization.''}
Evolutionary Computation {\bf 1} (1996)  pp25--49.

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

\bibitem{mcel} R. J. McEliced, E. C. Posner, E.~R.~Rodemick, and S.~S.~Venkatesh (1987).
{\em ``The Capacity of the Hopfield Associative Memory.''}
IEEE Trans. Information Theory {\bf IT-33}. pp461-482.

\bibitem{koho} T. Kohonen, and M. Ruohonen (1973).
{\em  ``Representation of Associated Data by Matrix Operators.''}
IEEE Trans. Computers {\bf C-22(7)}.  pp701--702.

\bibitem{gard} E. Gardner (1988).
{\em ``The Phase Space of Interactions in Neural Network Models.''}
Journal of  Physics  A: Math Gen. {\bf 21}. pp257--270.

\bibitem{chiu} T. D. Chiueh, and R. M. Goodman (1991)
{\em ``Recurrent Correlation Associative Memories.''}
IEEE Trans. Neural Networks {\bf 2(2)}, pp275--284.

\bibitem{DGZ}B. Derrida, E. Gardner, and A. Zippelius (1987).
{\em ``An Exactly solvable Asymmetric Neural Network Model.''}
Europhysics Letter {\bf 4(2)} pp167-173.

\bibitem{somp}H. Sompolinsky (1986).
{\em ``Neural Network with Non-linear Synapses and Static Noise.''}
Physical Review {\bf A34}  pp2571-2574.

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

\bibitem{imad-7}A. Imada, and K. Araki (1997).
{\em ``Evolved Asymmetry and Dilution of Random Synaptic Weights in Hopfield Network Turn a Spin-glass Phase into Associative Memory.''}
The 2nd International Conference on Computational Intelligence and Neuroscience.
Proceedings of Joint Conference of Computer Science, vol. {\bf 2},  pp223--226.

\bibitem{imad-12}A. Imada, and K. Araki (1997).
{\em ``Random Perturbations to Hebbian Synapses of Associative Memory using a Genetic Algorithm.''}
International Work-Conference on Artificial and Natural Neural Networks. (to appear).

\bibitem{imad-13}A. Imada, and K. Araki (1997).
{\em ``Hopfield Model of Associative Memory as a Test Function of Evolutionary Computations.''}
The 1st International Workshop on Frontiers in Evolutionary Algorithms.
Proceedings of Joint Conference of Computer Science, vol. {\bf 1},  pp180--183.

\bibitem{sysw}G. Syswerda (1989).
{\em ``Uniform Crossover in Genetic Algorithms.''}
Proceedings of the 3rd International Conference on Genetic Algorithms, pp2--9.

\bibitem{amit}D.~J.~Amit (1989).
{\it Modeling Brain Function: The World of Attractor Neural Networks.} Cambridge University Press.

\bibitem{ags-2}D. J. Amit, H.~Gutfreund, and H.~Sompolinsky (1985).
{\em ``Storing Infinite Number of Patterns in a Spin-glass Model of Neural Networks.''}
Physical Review Letters {\bf 55}. pp1530-1533.

\bibitem{krau}W. Krauth, J.-P. Nadal, and M.~Mezard (1988).
{\em ``The Roles of Stability and Symmetry in the Dynamics of Neural Networks.''}
Journal of Physics A: Math. Gen. {\bf 21} pp2995--3011.

\bibitem{herz} J. A. Hertz, G. Grinstein, and S. A. Solla (1987).
{\em ``Irreversible Spin Glasses an Neural Networks.''}
in L. N. van Hemmen and I. Morgenstern eds. Heidelberg Colloquium on Glassy Dynamics. Lecture Notes in Physics {\bf No.275} Springer-Verlag, pp538--546.

\bibitem{pari} G. Parisi (1986).
{\em ``Asymmetric Neural Networks and the Process of Learning.''} 
Journal of Physics {\bf A19} ppL675--L680.

\bibitem{imad-11}A. Imada, and K. Araki (1997).
{\em ``Application of an Evolution Strategy to the Hopfield Model of Associative Memory.''}
IEEE International Conference on Evolutionary Computation (to appear).

\end{thebibliography}

\end{document}