%%\documentstyle[epsf]{tainn}
\documentstyle[eclepsf]{tainn}

\begin{document}

\title{Does Diploidy Affect Evolutions of Hopfield Associative Memory?}

\author{Akira Imada\inst{1} and Keijiro Araki\inst{2}}

\institute{
        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\\
        \hspace*{1in}\\
\and
        Department of Computer Science and Computer Engineering\\
        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}

\maketitle

%% hebb -> no effect
%% random real -> 
%% clipped weight -> efficient


\begin{abstract}
\noindent
We apply genetic algorithms to the Hopfield's neural network model of 
associative memory.
Previously, we observed that {\it random} synaptic weights of a network 
evolved to create the fixed point attractors corresponding to a set of given
patterns to be stored.
In that simulation, a weight configuration was expressed as a sequence of 
genes which might be called a {\it haploid} chromosome.
Then a population of these haploid chromosomes underwent evolution.
In this paper, we employ {\it diploid} chromosomes, a pair of chromosomes.
We have reported elsewhere two different versions of the evolution that uses 
diploid chromosomes.
One is the evolution of the {\it Hebbian synapses} in which some of 
the synapses are adaptively pruned according to information in the diploid 
chromosomes.
The other is the evolution of {\it real-valued random synaptic weights} which are encoded directly into diploid chromosomes.
Here, we describe the evolution based on the latter scheme with the weights 
being restricted to take the value $\pm1$.
\end{abstract}

\begin{small}
\begin{center}
{\bf keywords}\\
Hopfield model of associative memory, genetic algorithm, diploid chromosome.
\end{center}
\end{small}


\section{Introduction}
\noindent
Associative memory is a dynamical system which has a number of stable states with a domain of attraction around them
(Koml\'{o}s et al. 1988).
If the system starts at any state in the domain, it will converge to the stable state.
Hopfield~(1982) proposed a fully connected neural network model of associative memory
in which information is stored by being distributed among neurons.\\

\noindent
The Hopfield model consists of $N$ neurons and $N^2$ synapses.
Each neuron state is either active (+1) or quiescent ($-1$).
When an arbitrary $N$-bit length {\it bipolar pattern}, a sequence of $+1$ 
and $-1$, is given to the network as an initial state,
the network changes its state dynamically afterwards.
The dynamical behaviors are determined by the \mbox{strengths} of the $N^2$ 
synapses which are referred to as  {\it weights}.
Here, the weight from neuron $j$ to neuron $i$ is denoted as $w_{ij}$;
and these $w_{ij}$'s construct a {\it weight matrix}.
If these $w_{ij}$'s are prescribed appropriately, then the network can store 
a number of patterns as attractors; 
and hence works as an associative memory.
The prescription of $w_{ij}$'s is called a {\it learning}.
Hopfield employed the so called Hebbian rule\footnote{The rule was at first 
advocated by Hebb (1949) and later formalized by Cooper (1973).}
for the learning; while we explore it by genetic algorithms (GA).
The GA was proposed by Holland (1975) to solve combinatorial optimization problems by borrowing the idea of natural selection.
In GAs, a problem is usually represented using one-dimensional array, which might be called  a {\it haploid} chromosome
from an analogy of biological evolution.
In our problem, $N^2$ synaptic weights of a network can be represented as a string of genes of a haploid chromosome.
In this way, we have already observed a random configuration of $w_{ij}$'s at the start of simulation 
evolves to store a number of patterns as fixed point attractors (Imada et al. 1997a).\\

\noindent
On the other hand, there is an alternative way to express a configuration of weights using
two one-dimensional arrays as a pair of chromosomes,
which are called {\it diploid} chromosomes.
The genetic algorithms using diploid chromosomes are said 
to be more biologically realistic than those using haploid chromosomes.
At the same time, the associative memory taking advantage of  dynamical behaviors of fully connected neurons
might be taken as a model of human memory.
This is one of the reasons of our interest in exploiting diploid chromosomes to evolve the associative memory network,
though this is too simple to be compared to our memory mechanisms.
Here, $w_{ij}$ and $w_{ji}$, which occupy two symmetric positions in the weight matrix, 
are mapped onto the same position in each pair of diploid chromosome.
If two genes at the same position of a chromosome pair take a same value as an allele, 
the position is said to be {\it homozygous}, and {\it heterozygous} otherwise.
Hillis (1991) used diploid chromosomes in his GA to optimize a sorting network.
He expected an evolutionary pressure to decrease the number of heterozygous positions in the chromosome pairs, 
which would minimize the number of comparisons of sorting entries.
He showed that the number of heterozygous site decreases as generation proceeds.
In our problem, homozygous site means that the two symmetric elements 
in the weight matrix, $w_{ij}$ and $w_{ji}$, are identical.
Our previous results show that when random synaptic weights, which are 
entirely asymmetric at the beginning, 
become somehow symmetric after evolving to be able to store 
some \mbox{patterns} (Imada et al. 1997a).
Hence, we expect a more efficient evolution from an entirely asymmetric weight configuration 
to somehow a symmetric weight configuration
by exploiting diploid chromosomes than exploiting usual haploid chromosomes.\\

\noindent
Thus far, we have reported elsewhere two versions of the GA that employs diploid chromosomes.
One is the evolution in which 
an {\it over-loaded Hebbian} network is diluted using information in the diploid chromosome (Imada et al. 1997c);
the other is the evolution of {\it real-valued random synaptic weights} 
which are encoded directly into the diploid chromosomes (Imada et al. 1998).
In this paper, we evolve {\it random synaptic weights} which are clipped into two values, 1 and $-1$, based on the latter scheme. 
We will see that the diploidy works more efficiently in the last case than the previously reported two cases.

\section{The Hopfield Model and Our fitness Evaluation}
\noindent
{\bf The Hopfield model} consists of fully  connected neurons.
The network with $N$ neurons has $N^2$ synapses.
An instantaneous state of a neuron is determined by the sign of the weighted sum of all the other neuron's state, i.e., 
\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$.
Thus, neurons are updated asynchronously (one neuron at a time) in certain pre-fixed order\footnote{One neuron is updated 
only once per cycle in which all the $N$ neurons must be updated. 
Hopfield chose neuron to be updated in random order, while we updated them in a pre-fixed order.
It was verified that the both cause essentially the same results.}.
In general, when a bipolar pattern is given to the network as an initial state, states of neurons vary from time to time afterwards.
To store $p$ bipolar patterns $\xi^{\nu}$:
\begin{displaymath} 
{\xi}^{\nu} = ({\xi}^{\nu}_{1},\cdots,{\xi}^{\nu}_{N}), \hspace{.2in}{\nu} = 1, \cdots, p,
\end{displaymath}
as fixed point attractors, Hopfield prescribed the weight values employing the Hebbian rule:
\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 stored patterns to the network keeps all the states unchanged (fixed points), 
unless the number of patterns exceeds the capacity;
and an input of the stored patterns 
including a few noise possibly converges to the pattern in its perfect form.\\

\noindent
{\bf Fitness Evaluation} is made as follows:
Since we start with random $w_{ij}$, the network state diverges
in early stages of the evolution.
In order for the network to be improved to function as an associative memory,
instantaneous state $s_{i}^{\nu}(t)$ should become similar to the input 
pattern $\xi^{\nu}$.
The similarity as a function of time is defined by,
\begin{displaymath}
m^{\nu}(t) = \frac{1}{N} \sum_{i=1}^{N} { {\xi}_{i}^{\nu} s^{\nu}_{i}(t) }.
\end{displaymath}
This is conventionally called an {\it overlap}.
The temporal average of $m^\mu(t)$ is calculated for each stored pattern.
Then, our fitness function is obtained by further averaging these temporal 
averages of overlap over all the given patterns.
That is, our fitness value $f$ is
\begin{displaymath}
f = \frac {1}{p \cdot t_{0}}
\sum _{\nu=1}^{p}
{
\sum_{t=1}^{t_{0}}
{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 fitness less than~1 includes many other cases.


\section{Experiment}
\noindent
The GA Implemented in this paper is as follows:
A set of $p$ random bipolar patterns 
${\xi}^{\nu}$ (${\nu} = 1, 2, \cdots, p$) is generated before each run.
The goal of the GA is to evolve networks to store all these patterns as fixed 
point attractors.
In each generation, the \mbox{networks} are estimated fitness value using 
these patterns as a target.
In this paper, weight values are restricted to either 1 or $-1$.
A configuration of weights of a network (phenotype) is represented by a pair 
of chromosomes (genotype) in which each gene takes this clipped weight value.
At the 1st generation, these 1 and $-1$ are assigned at random.\\

\noindent
Previously, we employed haploid chromosomes to solve the same problem 
(Imada et al. 1997a),
where weights were expressed as:
\begin{displaymath}
( c_1, \cdots, c_k, \cdots, c_{N^2} ).
\end{displaymath}
That is,
\begin{displaymath}
w_{ij} = c_k,  \hspace{.2in} k = j + (i-1)N
\end{displaymath}
\noindent
Here, instead, we employ diploid chromosomes.
Two genes of the same position in a pair of chromosomes correspond to the two 
symmetric sites of the weight matrix.
Thus, each pair represents components 
in the upper right triangle and lower left triangle of the matrix, 
independently.
To be more specific, assume that the diploid chromosome pair is denoted as \\
\begin{displaymath}
\left\{
\begin{array}{ll}
\mbox{chromosome 1:} \hspace{.1in} ( c_1^1, c_2^1, \cdots, c_{N(N-1)/2}^1 )\\
\mbox{chromosome 2:} \hspace{.1in} ( c_1^2, c_2^2, \cdots, c_{N(N-1)/2}^2 ).\\
\end{array} \right.
\end{displaymath}

\noindent
Then, weights in the upper right triangle of the matrix are 
\begin{displaymath}
w_{ij} = c_k^1 \hspace{.2in} \mbox{for} \hspace{.1in} i = 1, \cdots, N-1 \hspace{.1in} \mbox{and} \hspace{.1in}  j = i+1, \cdots, N;
\end{displaymath}
and weights in the lower left triangle are 
\begin{displaymath}
w_{ji} = c_k^2 \hspace{.2in} \mbox{for} \hspace{.1in}   j = 1, \cdots, N-1 \hspace{.1in} \mbox{and} \hspace{.1in}  i = j+1, \cdots, N,
\end{displaymath}
where
\begin{displaymath}
k = \frac{(2N-i)(i+1)}{2} - 2N + j.
\end{displaymath}
Note that we assume diagonal elements are all zero.\\

\noindent
Two genes of a heterozygous position in the diploid chromosome remain
the corresponding components of the phenotype asymmetric;
while two genes of a homozygous position introduce symmetry in the weight 
matrix.
The more homozygous positions, the more symmetric.
A completely homozygous genotype will produce a symmetric phenotype.\\

\noindent
The fitness of each network is measured as mentioned earlier.
All the diploid chromosomes in the population are ranked according to the 
fitness value.
In the usual genetic algorithms,
the mating processes of selecting two better parents to be recombined to 
produce offspring are iterated at this stage.
Here, before being mated, all the diploid chromosomes are operated uniform 
crossover within each pair to produce a single chromosome called {\it gamete},
such that each gene of the gamete is chosen from either of the pairs at random.
Thus, each pair of diploid chromosomes produces a single gamete.
The length of the gamete is same as the chromosome ($=N(N-1)/2$).
It is these gametes that are recombined in this implementation.\\



\noindent
Two diploid chromosomes are chosen randomly from the best $T\%$ of the population, prohibiting self-mating.
Two gametes from these two parent diploid chromosomes are combined.
This forms a new child diploid chromosome.
This particular mating process is repeated until the worst $(100-T)\%$ of the population are replaced with these new children.
The offspring is  occasionally mutated by flipping the sign of a gene that is selected with the probability $p_m$.\\

\noindent
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.\\

\noindent
All the simulations are carried out on networks with 49 (=$N$) neurons.
Hence, the length of a chromosome is 1176.
The parameters we used in the GA are as follows.
The population number is 256. This is just because of our limited computer resources.
The mutation rate $p_m$ is set to 0.01.
In selecting two parents, $T$ is chosen to be 40\%.  
Searching procedure is iterated until 12000 generations unless perfect 
solution is found.
These values were determined mainly on the basis of trial and error.

\section{Results and Discussion}
\noindent
We started the GA with a population of networks with random clipped weights 
($\pm 1$).
At an early stage of generation, any patterns given to these networks will 
result in chaotic behavior of neurons' state.
This is due to the asymmetry of their weight matrix.
The behaviors are visualized, for example, by observing trajectories of the 
Hamming distance between the initial state given to the network 
and the instantaneous states afterwards.
In Figure~\ref{trajectory}, we show examples of the trajectories.
The Hamming distances are plotted against updating time steps.
The goal is to find 
a solution which makes all trajectories for the given input patterns 
coincide with the {\it x-axis} (fixed point attractor).\\

\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=trajectory-0154.eps,width=5.0cm,height=5.0cm}
   \caption{Time expansion of the Hamming distance of instantaneous state from the initial input state (a snapshot during evolution).}
   \label{trajectory}
 \end{center}
\end{figure}

\noindent
The effect on evolution of varying $p$, the number of given patterns, 
is studied.
We repeat each simulation 30 times with different random number seed for the 
fixed $p$. 
If we find the perfect solution(s) then we increment $p$.
Thus, we found a matrix evolved to store a maximum of five patterns.
In Figure~\ref{diploidy} (left), we show the representative sample of the best fitness versus generation of the evolution for $p=5$.
It was found that a  network that stores all the five patterns as fixed points
eventually emerges.\\

\noindent
The degree of  symmetry of the weight matrices vary as the population evolves.
We investigated the time expansion of the ratio of the best fit weights in each generation. 
The degree of symmetry is defined by
\begin{displaymath}
\sigma = \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}
following after Krauth et al. (1988).
The results are shown in Figure~\ref{diploidy} (right).
Here, the data were taken from the evolution presented in the right figure.\\

\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=0115-fitness.eps,width=5.0cm,height=5.0cm}
   \epsfile{file=0115-symm.eps,width=5.0cm,height=5.0cm}
   \caption{The best fitness versus generation (left); degree of symmetry during evolution (right).}
   \label{diploidy}
 \end{center}
\end{figure}

\clearpage
\noindent
To see how different is the affect of diploid chromosomes to the evolution 
from the one using haploid chromosomes,
an example of evolution using haploid chromosomes is shown in Figure \ref{haploidy}.
As Hertz (1987) suggested, asymmetry of the synaptic weights is relevant to the number of spurious attractors, 
and hence, the function of associative memory.
We can observe significant difference in the degree of symmetry, 
while in our previous experiment that evolved symmetric Hebbian weights, 
we were not able to observe such difference.
The degree of symmetry 
when the fitness reaches 1 is around 0.6 with diploid chromosome, whilst 0.3 with haploid chromosome.
We conclude that the difference is due to the pressure to homozygosity of diploid chromosomes.\\


\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=0005-fit-symm.eps,width=5.0cm,height=5.0cm}
   \caption{Fitness and degree of symmetry versus generation with haploid chromosomes.}
   \label{haploidy}
 \end{center}
\end{figure}

\noindent
To say a network an associative memory system, the tolerance for certain amount of noises should be shown.
Namely, each memorized pattern must have a certain domain of basin of attraction.
We studied elsewhere the basin size of attractors created by our genetic algorithm (Imada et al. 1996).
According to our observation, the basin of attraction of the created memory by evolutionary process is generally small.\\

\noindent
Here, to study the basin of attraction, 1000 initial states are sampled by
randomly picking up a stored pattern with $d$ bits being flipped. 
Each of them is repeatedly given to the network and the state is updated $2N$ 
times (possibly it reaches a stable state). 
The resulting state is compared with the original memorized state.
The run is called a success if the two states match {\it exactly}. 
In Figure~\ref{basin}, the numbers of successes out of the 1000 runs 
are plotted against the number of input errors~$d$.
We can see that the network obtained from the above experiment shows the 
tolerance of noisy input.
The difference shows diploid chromosome works a little more favorably as to 
the basin size than by haploid chromosome.
However, the basin sizes obtained from both experiments are fairy small,
probably because of  the remaining spurious attractors around the created 
memories.

\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=0005-0115-basin-3.eps,width=5.0cm,height=5.0cm}
   \caption{Tolerance for noise of the networks with diploid and haploid chromosome.}
   \label{basin}
 \end{center}
\end{figure}

\section{Conclusion}
\noindent
We have described how diploid chromosomes affects the evolution of fully connected neural networks which are to be used as an associative memory.
Experiments were carried out on networks with 49 neurons; and evolved here were weights of clipped value ($\pm1$).
The GA using diploid chromosomes succeeded in emerging a network that can store a maximum  of five random bipolar patterns as fixed points.
If we employ the Hebbian algorithm to prescribe weights of a network with the same size,
the network will store around eight patterns, or six patterns if the weights are clipped to $\pm1$.
In both cases, the weight matrix will be totally {\it symmetric}.
Here, we have started with totally asymmetric weights on the contrary ($\approx 0 \%$ symmetry),
and observed that they evolved to be considerably symmetric ($\approx 60 \%$).
The degree of symmetry was much higher than the one when we employed haploid chromosomes ($\approx 30 \%$).\\

\noindent
This phenomenon was also observed in our previous experiment of evolving {\it real-valued random} weights.
However in that experiment, the maximum storage capacity obtained were only two patterns.
The GA was also applied to the Hebbian weights that had learned patterns 
exceeding the capacity where we found that the weights evolved to perform 
better by reducing the degree of symmetry.
In that case, however, we did not observe the difference between diploid 
and haploid chromosomes.\\


\noindent
The Hopfield associative memory has an upper bound in capacity to store patterns; 
a network stores a maximum of only $2N$ patterns, as Gardner (1988) discussed.
However, it is not so difficult to extend the model to the one with a higher ($\lambda$-th) order synapses, 
where storage capacity scales $N^\lambda$ (Baldi and Venkatesh, 1987).
We think we can employ {\it multi-ploidy} chromosomes also to express the network with this higher order synapses.

\section*{Acknowledgments}
\noindent
We thank Peter Davis at Advanced Telecommunication Research Institute (ATR)
for providing us great insight into the dynamics of the Hopfield neural networks,
in the early stage of this research.

\section*{References}
\begin{small}
\begin{description}
\setlength{\itemsep}{0pt}
\item[]Baldi, P., and  S. S. Venkatesh (1987)
{\em Number of Stable Points for Spin-Glasses and Neural Networks of Higher Orders.}
Physical Review Letters, 58(9), pp913--915.

\item Cooper, L. N. (1973)
{\em A Possible Organization of Animal Memory and Learning.}
Proceedings of the 24th Nobel Symposium on Collective Properties of Physical Systems,
pp252--264.


\item[] Gardner, E. (1988)
{\em The Phase Space of Interactions in Neural Network Models.}
Journal of Physics 21A, pp257--270.

\item[]Hebb, D. O. (1949)
{\it The Organization of Behavior.}, Wiley.

\item[]Hertz, J. A.,  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 No.275, Springer-Verlag, pp538--546.

\item[]Hillis, W. D. (1991)
{\em Co-Evolving Parasites Improve Simulated Evolution as an Optimization Procedure.}
C. G. Langton, C. Taylar, J. D. Farmer, and S. Rasmussen eds.
Artificial Life II. SFI Studies in the Science of  Complexity Vol. X,  Addison-Wesley,
pp295--312.

\item[]Holland, J. (1975)
{\it Adaptation in Natural and Artificial Systems.}
The University of Michigan Press.

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

\item[]Imada, A., and K. Araki (1996),
{\em Basin of Attraction of Associative Memory as it Evolves from Random Weights.}
Proceedings of the 1st Asia-Pacific Conference on Simulated Evolution and Learning, pp271--278.
\item[]Imada, A., 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. 2, pp223--226.

\item[]Imada, A., and K. Araki (1997)
{\em Evolution of Associative Memory using  Diploid Chromosomes.}
The 10th Australian Joint Conference on Artificial Inteligence.
Proceedings of the Workshop on Evolutionry Computation, pp24--36.

\item[]Imada, A., and K. Araki (1998)
{\em How Real-valued Random Synapses Evolve toward Symmetry with Diploid Chromosomes?}
International ICSC/IFAC Symposium on Neural Computation (to appear).


\item[]Koml\'{o}s, J., and R. Paturi (1988)
{\em Convergence Results in an Associative Memory Model.} 
Neural Networks 1, pp239--250.

\item[]Krauth, W., 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.

\end{description}
\end{small}

\end{document}
