\documentstyle[landscape,fleqn,a4j,12pt,epsf]{jarticle}
\thispagestyle{empty}
\pagestyle{empty}

\begin{document}
\begin{LARGE}

%% (1)title 
\clearpage
\begin{center}

\begin{Huge}
\noindent
{\bf Evolution of a Hopfield Associative Memory\\by the Breeder Genetic Algorithm}\\



\end{Huge}

\vspace{1in}
{\bf
Akira Imada\\
Nara Institute of Science and Technology\\
(akira-i@is.aist-nara.ac.jp)\\
\hspace*{1in} \\
Keijiro Araki\\
Kyusyu University\\
(araki@is.aist-nara.ac.jp)\\
}
\end{center}

%% (2)introduction
\clearpage
{\bf
\noindent
Introduction:\\

\begin{itemize}
\item We apply 
   \begin{itemize}
   \item ECs to neural network model of Associative Memory.
   \end{itemize}
\item We study
   \begin{itemize}
   \item
 basic behaviors of the model under simple evolutionary\\ processes.
   \end{itemize}
\item Here,
\begin{itemize}
   \item we use the Breeder Genetic Algorithm. \\\hspace*{5in}(H. M\"{u}lenbein et al.)
   \end{itemize}
\end{itemize}
}


%% (3)asociative memory as a dynamical system
\clearpage
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=what-is-am.eps,width=21cm,height=14cm}
 \end{center}
\end{figure}

%% its realization
\clearpage
{\bf
\noindent
It can be realized with\\
\begin{itemize}
\item neural network model \\ \hspace*{1.9in}(leyered/recurrent/self-organized)\\
\item immune system model\\
\item etc
\end{itemize}
}


%% (4)associative memory with Hopfield model
\clearpage
{\bf
\noindent
The Hopfield Model of Associative Memory:\\
\begin{itemize}
\item stores information by distributing it among neurons;
\item has a capability to tolerate noisy and/or partial input in recalling the information;
\item[]
\item has a limited storage capacity.
\item The capacity is traded-off against basin of attraction.\\
\end{itemize}
}


%% (5)schematic diagram of hopfield model for N=3
\clearpage
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=fig-nn.eps,width=21cm,height=10cm}
 \end{center}
\end{figure}

%% (5)schematic diagram of hopfield model for N=3
\clearpage
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=trajectory.eps,width=24cm,height=14cm}
 \end{center}
\end{figure}

%% specification of synaptic weight
\clearpage
{\bf
\noindent
How to Specify Synaptic Weights ?\\
\begin{itemize}
\item Hopfield used the ``Hebb's rule''.
\item[]
\item Kohonen \& Ruohonen's ``pseud inverse''.
\item Panch et al.'s ``specral algorithm''.
\item Gardner's algorithm.
\item[]
\item We explore it with ``Evolutionary Algorithms''.
\end{itemize}
}


%% (2)introduction
\clearpage
{\bf
\noindent
Modification of Synaptic Weights in the Classical Analysis:\\

\begin{displaymath}
\mbox{J}_{\mbox{ij}} \mbox{ $B!&(B } \mbox{c}_{\mbox{ij}} \hspace{.4in}  \mbox{(Derrida, Gardner \& Zeppelius)}\\
\end{displaymath}

\begin{displaymath}
\mbox{J}_{\mbox{ij}} \mbox{ + } \mbox{$\eta$}_{\mbox{ij}} \hspace{.4in}  \mbox{(Sompolinsky)}
\end{displaymath}

\vspace{.6in}

\noindent
We also modify them by ECs based on these 2 schemes.


\vspace{.6in}

\noindent
They selected synapses ``randomly'' to show the robustness,
\begin{center} 
while 
\end{center}
\noindent
we select synapses ``adaptively'' to create/enlarge memories.
}

%% 
\clearpage
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=sompolinsky.eps,width=24cm,height=17cm}
 \end{center}
\end{figure}

\clearpage
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=mapping-nn.eps,width=26cm,height=9cm}
 \end{center}
\end{figure}

%% (9)GA implementation
\clearpage
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=overview.eps,width=21cm,height=14cm}
 \end{center}
\end{figure}

%% fitness evaluation
\clearpage
{\bf
\noindent
Fitness Evaluation\\

\indent
- ``overlap''of 2 states:
\begin{displaymath}
\frac{1}{N} \sum_{i=1}^{N} { {S}_{i}^{1} S^{2}_{i}}
\end{displaymath}

- overlap  of instantaneous state with input:
\begin{displaymath}
m^{\nu}(t) = \frac{1}{N} \sum_{i=1}^{N} { {\xi}_{i}^{\nu} s^{\nu}_{i}(t) },
\end{displaymath}

- temporal average:
\begin{displaymath}
\left \langle m^{\nu} \right \rangle
\end{displaymath}

- average over all patterns:
\begin{displaymath}
\left \langle\langle m \right \rangle \rangle
\end{displaymath}

- fitness:
\begin{displaymath}
f = \left \langle\langle m \right \rangle \rangle
\end{displaymath}
}

\clearpage
\noindent
{\bf  $\Box$ Initialization:\\
\begin{table}[hbtp]
\begin{center}
\begin{tabular}{l c}
$\bullet$ Random matrices\hspace{.5in}                                 & (uniformly at random) \\
$\bullet$ Zero matrix\hspace{.5in}                                   & (completely homogeneous) \\
$\bullet$ Over-loaded Hebbian  matrix\hspace{.5in}                   & (completely homogeneous) \\
\end{tabular}
\end{center}
\end{table}
}
\clearpage
\clearpage
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=bga-mutation.eps,width=26cm,height=13cm}
 \end{center}
\end{figure}

%% (6)conceptual algorithm
\clearpage
%%{\bf The Breeder Genetic Algorithm Implementation:}
{\bf The BGA Implementation:}
\begin{itemize}
\setlength{\itemsep}{0pt}
\item[]{\bf begin}
   \begin{itemize}
   \item[]{\bf initialize} 256 chromosomes (with either of random/zero/Hebbian)
   \item[]{\bf while} termination criterion not fulfilled {\bf do}
      \begin{itemize}
      \item[]{\bf evaluate} fitness of each individual
      \item[](by counting how many patterns can be memorized as fixed points)
%%      \item[]{\bf select} the best $T$\% individuals
      \item[]{\bf repeat} until the whole population are replaced {\bf do} 
         \begin{itemize}
         \item[]{\bf select} two individuals {\it randomly} from the best 40\%
         \item[]{\bf recombine} them with ``discrete crossover'' to produce one offspring
         \item[]{\bf mutate} the offspring
         \end{itemize}
%%    \item[]{\bf od}
      \end{itemize}
   \item[]{\bf return} a set of $w_{ij}$'s
%% \item[]{\bf od}
   \end{itemize}
%%\item[]{\bf end}
\end{itemize}

%% (8) initial trajectory
\clearpage
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=hamming-r.eps,width=21cm,height=14cm}
 \end{center}
\end{figure}

%% (8) initial trajectory
\clearpage
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=hamming-h.eps,width=21cm,height=14cm}
 \end{center}
\end{figure}

%% (11)evolution
\clearpage
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=fitness-h.eps,width=21cm,height=14cm}
 \end{center}
\end{figure}
%%%% replace the one with p=33

\clearpage
\noindent
$\bullet$ Departure from {\bf Hebbian} matrix ($N =49$)
\begin{table}[hbtp]
\begin{center}
\begin{tabular}{c l l } \hline \hline
{\bf p = \hspace{.13in} 8}\hspace{.45in}   & only Hebb's rule             &\hspace{.45in}               \\    \hline
\hspace*{.1in}                             & \hspace{.1in}                & \hspace{.1in}               \\    \hline 
{\bf p = 13}\hspace{.45in}                 & EP                           &\hspace{.45in}   EP'97       \\    \hline
{\bf p = 16}\hspace{.45in}                 & discrete-GA (pruning)        &\hspace{.45in}   ICGA'95     \\    \hline
{\bf p = 17}\hspace{.45in}                 & ES                           &\hspace{.45in}   ICEC'97     \\    \hline
{\bf p = 17}\hspace{.45in}                 & Lamarckian + continuous-GA   &\hspace{.45in}   ICEC'96     \\    \hline
{\bf p = 17}\hspace{.45in}                 & continuous-GA (perturbation) &\hspace{.45in}   IWANN'97    \\    \hline
{\bf p = 19}\hspace{.45in}                 & Baldwin + pruning-GA         &\hspace{.45in}   ICANNGA'97  \\    \hline 
\hspace*{.1in}                             & \hspace{.1in}                & \hspace{.1in} \\  \hline 
{\bf p = 32}\hspace{.45in}                 & BGA                          &\hspace{.45in}   ICGA'97  \\    \hline \hline
\end{tabular}
\end{center}
\end{table}

%% (11)evolution
\clearpage
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=fitness-z.eps,width=21cm,height=14cm}
 \end{center}
\end{figure}

\clearpage
\noindent
$\bullet$ Departure from {\bf zero} matrix ($N =49$)
\begin{table}[hbtp]
\begin{center}
\begin{tabular}{l l l } \hline \hline
{\bf p = \hspace{.13in}6}\hspace{.45in}   & EP\hspace{3.3in}               &\hspace{.45in}   EP'97    \\    \hline
{\bf p = 11}\hspace{.45in}   & ES                           &\hspace{.45in}   ICEC'97  \\    \hline
\hspace*{.1in}               & \hspace{.1in}                & \hspace{.1in} \\  \hline 
{\bf p $>$ 90}\hspace{.45in}   & BGA                          &\hspace{.45in}   ICGA'97  \\    \hline \hline\\
\end{tabular}
\end{center}
\end{table}

\clearpage
\noindent
{\bf $\Box$ T. C. Fogarty's GA in an industrial application} (ICGA'89)\\
\begin{itemize}
\item starting with
   \begin{itemize}
   \item a completly {\bf homogenous} population;
   \end{itemize}
\item with a mutation of 
   \begin{itemize}
   \item an initially high but exponentially decreasing rates.\\
   \end{itemize}
\end{itemize}
\noindent
He said:\\ This mutation was not effective when start with a randomized population.

\clearpage
$\bullet$ Departure from {\bf random} matrices ($N =49$)

\begin{table}[hbtp]
\begin{center}
\begin{tabular}{l l l } \hline \hline
{\bf p =  7}\hspace{.45in}   & continuous-GA (purturbation) &\hspace{.45in}   IWANN'97  \\    \hline
{\bf p =  8}\hspace{.45in}   & discrete-GA (pruning)        &\hspace{.45in}   ICGA'95  \\    \hline
\hspace*{.1in}               & \hspace{.1in}                & \hspace{.1in} \\  \hline 
{\bf p =  9}\hspace{.45in}   & BGA                          &\hspace{.45in}   ICGA'97  \\    \hline \hline
\end{tabular}
\end{center}
\end{table}



\clearpage
\noindent
{\bf $\Box$ With the completly homogenous initialization:}
\begin{itemize}
\item premature convergence
   \begin{itemize}
   \item[] \hspace*{1.2in}seems to be no problem as far as these 2 starting points
   \end{itemize}
\item population diversity
\end{itemize}

\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=distribution-h.eps,width=16cm,height=8.2cm}
 \end{center}
\end{figure}

\clearpage
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=symmetry.eps,width=21cm,height=14cm}
 \end{center}
\end{figure}

\clearpage
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=basin.eps,width=21cm,height=14cm}
 \end{center}
\end{figure}

\clearpage
\noindent
{\bf $\Box$ The BGA can locate multi-modal solutions?}\\

\begin{itemize}
\item for a fixed 49 patterns $\rightarrow$ 92 runs $\rightarrow$  seems to locate different solutions
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=distance-from-origin.eps,width=26cm,height=3cm}
 \end{center}
\end{figure}
\item[]
\item The Hopfield model could be a good test function;
   \begin{itemize}
   \item has unknown optima (closer to real world problems);
   \item fullfills Whitley et al.'s requirement (ICGA'95), i.e.,
        \begin{itemize}           
        \item scalable but not separable, etc.
        \end{itemize}
   \end{itemize}
\end{itemize}


%% (13) future work
\clearpage
{\bf
\noindent
$\Box$ Conclusions:\\
\begin{itemize}
\item The BGA can create fixed point attractors exactly at the location of given patterns starting with:
   \begin{itemize}
   \item random matrices (max p = 9);
   \item zero matrix (p $>$ 90);
   \item over-loaded Hebbian matrix (max p = 32).
   \end{itemize}
%%\item If the BGA can locate all the optima, we can obtain the information about: e.g.,
\item If the BGA can locate all the optima, we can obtain, e.g.,
   \begin{itemize}
      \begin{itemize}
      \item the number of solutions;
      \item their distribution.
      \end{itemize}
   
 \end{itemize}
\item[]
\item These studies shed new light on the analysis of the Hopfield model of associative memory.
\end{itemize}
}

\end{LARGE}
\end{document}




