%%\documentstyle[twocolumn,epsf]{article}
\documentstyle[twocolumn,eclepsf]{article}
\begin{document}
\setlength{\topmargin}{0.36cm}
\setlength{\oddsidemargin}{-0.14cm}
\setlength{\textheight}{23.0cm}
\setlength{\textwidth}{17.0cm}

\title{How Real-valued Random Synapses Evolve toward Symmetry\\
       with Diploid Chromosomes?}

\author{\begin{small}
        \begin{minipage}[t]{8cm}
        \begin{center}
        Akira Imada\\
        Graduate School of Information Science\\  
        Nara Institute of Science and Technology\\
        1-11-13-604 Abeno, Hannan, Osaka, 545-0021 Japan\\
        akira-i@is.aist-nara.ac.jp\\
        \end{center}
        \end{minipage}
        \begin{minipage}[t]{8cm}
        \begin{center}
        Keijiro Araki\\
        Graduate School of Information Science\\ 
        and Electrical Engineering, Kyusyu University\\
        6-1 Kasuga-koen, Kasuga, Fukuoka, 816 Japan\\
        araki@c.csce.kyusyu-u.ac.jp
        \end{center}
        \end{minipage}\end{small}}

\date{}
\pagestyle{empty}
\thispagestyle{empty}
\maketitle

\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 in pattern space 
exactly at the locations corresponding to a set of given
patterns to be stored.
In that simulation, a weight configuration was represented 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 this evolution.
One is the evolution of the {\it Hebbian synapses} in which some of 
the synapses are adaptively pruned according to information in diploid 
chromosomes.
The other is the evolution of random synaptic weights 
whose values are restricted to $\pm1$,
and are encoded directly into diploid chromosomes.
Here, we describe the evolution of {\it real-valued random synaptic weights}. 
\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
and is retrieved from dynamically relaxed neuron states.\\

\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 {\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 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}$.
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 
also 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 
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 represent a configuration
of weights using two one-dimensional arrays as a pair of chromosomes,
which are called {\it diploid} chromosomes in the field of GAs.
The GAs 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 regarded 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 sites 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 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 diploid chromosome (Imada et al. 1997c).
The other is the evolution of 
{\it random synaptic weights clipped into two values, 1 and $-1$}
which are encoded directly into the diploid chromosomes (Imada et al. 1998).
In this paper, we evolve 
{\it real-valued random synaptic weights} in the same way as 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}
\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{.1in}{\nu} = 1, \cdots, p,
\end{displaymath}
as fixed point attractors, Hopfield prescribed the weight values by 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 a random configuration of synaptic weights, 
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 defined as:
\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 networks are estimated fitness value using 
these patterns as a target.
In this paper, weight values assume any real value taken from $[-1, 1]$.
A configuration of weights of a network (phenotype) is represented by a pair 
of chromosomes (genotype) in which each gene takes this real weight value.
At the 1st generation, weight values are assigned at random.\\

\noindent
Previously, we employed haploid chromosomes to solve the same problem 
(Imada et al. 1997a),
where weights were represented as:
\begin{displaymath}
( c_1, \cdots, c_k, \cdots, c_{N^2} ).
\end{displaymath}
That is,
\begin{displaymath}
w_{ij} = c_k,  \hspace{.1in} 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. 
Namely, two components in the upper right triangle and 
lower left triangle of the matrix.
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{.1in} \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{.1in} \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 in the way 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 parents to be recombined to 
produce offspring are iterated at this stage.
Here, on the other hand, all the diploid chromosomes, before being mated, 
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 mutated with the probability $p_m$
by replacing a gene 
with another random real number taken from $ [-1, 1 ] $. \\

\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
Since we started the GA with a population of networks with
weights chosen randomly from $[1, -1]$, any patterns given 
to these networks at early stages of evolution,  will 
result in chaotic behavior of neurons' states.
This is due to the asymmetry of their weight matrices.
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 an example of 
a sequence of snapshots of the trajectories\footnote{This is 
an example taken from our previous experiment with a GA using 
haploid chromosomes (Imada 1997b).}.
The Hamming distances are plotted against updating time steps.
The goal of the GA is to find 
a solution which makes all trajectories for the given input patterns 
coincide with the {\it x-axis} (fixed point attractors).\\

\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=trajectory-0154.eps,width=6.3cm,height=3.2cm}
   \epsfile{file=trajectory-0200.eps,width=6.3cm,height=3.2cm}
   \epsfile{file=trajectory-0210.eps,width=6.3cm,height=3.2cm}
   \epsfile{file=trajectory-0240.eps,width=6.3cm,height=3.2cm}
   \epsfile{file=trajectory-0300.eps,width=6.3cm,height=3.2cm}
   \epsfile{file=trajectory-1000.eps,width=6.3cm,height=3.2cm}
   \epsfile{file=trajectory-2200.eps,width=6.3cm,height=3.2cm}
   \caption{An example of trajectories of the Hamming distance 
            of instantaneous state from the initial input state
            (seven snapshots during an evolution).}
   \label{trajectory}
 \end{center}
\end{figure}

\noindent
Now, let's look at the evolutions using diploid chromosomes.
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$.\\

\noindent
It was found that a  network that stores two patterns 
as fixed points emerges.
In Figure~\ref{diploidy-1}, we show the representative sample of 
the best fitness versus generation of the evolution.
A maximum storage obtained here were unfortunately very small.\\

\noindent
The degree of symmetry of the weight matrices varies as generation proceeds.
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-2}.
Here, the data were taken from the evolution 
presented in the Figure~\ref{diploidy-1}.\\

\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=0002-fitness.eps,width=8cm,height=8cm}
   \caption{The best fitness versus generation.}
   \label{diploidy-1}
 \end{center}
\end{figure}

\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=0002-symm.eps,width=8cm,height=8cm}
   \caption{Degree of symmetry during evolution.}
   \label{diploidy-2}
 \end{center}
\end{figure}

\noindent
To see how the affect of diploid chromosomes to the evolution 
is different from the one using haploid chromosomes,
the best fitness versus generation and degree of symmetry
under haploid chromosomes are plotted in Figure \ref{haploidy}.
The experiments were made with the same condition 
as in Figure \ref{diploidy-1} and \ref{diploidy-2} above.
As Hertz (1987) suggested, asymmetry of the synaptic weights 
is relevant to the number of spurious attractors, 
and therefore, the function of associative memory.
We can observe significant difference in the degree of symmetry.
The degree of symmetry when the fitness reaches 1 is around 0.6 
with diploid chromosome, while the one with haploid chromosome is 0.3.
We conclude that the difference is due to the pressure 
to homozygosity of diploid chromosomes.
This is in contrast to our previous experiment that evolved symmetric Hebbian weights, 
where we were not able to observe such difference.\\

\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=5002-gdb.eps,width=8cm,height=8cm}
   \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),
and found that the basin of attraction of the created memory 
by evolutionary process is generally small.
Probably, this is because of the remaining 
spurious attractors around the created memories.
Here, using diploid chromosomes, we were not able to enlarge
the size of basins of attraction of the stored patterns either.


\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 real-valued random weights.
The GA using diploid chromosomes succeeded in emerging a network 
that can store a maximum of two 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.
So, it might be argued that since the capacity obtained are too small to 
say the experiment is worthwhile to test.
However, it is important to note that 
the Hebbian weight matrices are 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 weights of random clipped value $(\pm 1)$.
In addition, the storage capacity obtained in that experiment 
were a maximum of five 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 represent 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 (1997a)
{\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 (1997b)
{\em Evolution of Random Synaptic Weights of the Hopfield Associative Memory 
: How Chaotic Trajectories Turn into Fixed Point Attractors?}
Proceedings of the 4th International Conference on Neural Information Processing
and Intelligent Information Systems, vol. 1, Springer Verlag, pp452--455.

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

\item[]Imada, A., and K. Araki (1998)
{\em Does Diploidy Affect Evolutions of Hopfield Associative Memory?}
The 7th Turkish Symposium on Artificial Intelligence and Neural Networks
(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}

