%%%%% mini-slide version was compiled at aist. %%%%%
%\documentstyle[landscape,fleqn,a4j,12pt,epsf]{jarticle}
%\documentstyle[landscape,a4j,12pt,epsf]{jarticle}
\documentstyle[landscape,12pt,eclepsf]{article}
\thispagestyle{empty}
\pagestyle{empty}
\begin{document}
\begin{LARGE}

%%%%%%%%%%  1. title  %%%%%%%%%%
\clearpage
\begin{center}
\begin{Huge}
\noindent
{\bf A Multimodal GA and a Visualization Technique\\
     Applied to\\
     the Hopfield Model of Associative Memory}\\
\end{Huge}
\vspace{1in}
{\bf
Akira Imada\\
Anadolu University\\
Turkey
}
\end{center}

%%%%%%%%%%  2. to be more specific  %%%%%%%%%%
\clearpage
\begin{center}

{\bf A visualization technique\\

\hspace{1in}\\

using\\

\hspace{1in}\\

Principal Component Analysis (PCA)\\

\hspace{1in}\\

observes\\

\hspace{1in}\\

a convergence behaviour\\

\hspace{1in}\\

of\\

\hspace{1in}\\

a multimodal Genetic Algorithm.}
\end{center}

%%%%%%%%%%  3.contents  %%%%%%%%%%
\clearpage
{\bf $\Box$ Contents:}\\

\begin{itemize}
\item What is Associative Memory?
\item How we evolve it?
\item Fitness Landscape.
\item Results and Discussion.
\item Conclusion.
\end{itemize}

%%%%%%%%%%  4. Associative 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}

%%%%%%%%%%  5.  category of trajectory  %%%%%%%%%%
\clearpage
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=trajectory.eps,width=24cm,height=14cm}
 \end{center}
\end{figure}

%%%%%%%%%%  6. Realization  %%%%%%%%%%
\clearpage
{\bf
\noindent
The Associative Memory can be realized with:\\
\begin{itemize}
%%\item neural network model \\ \hspace*{1.9in}(layered/recurrent/self-organized)\\
\item fully-connected neural network model \\ \hspace*{4.9in}(Hopfield model)\\
\item immune system model\\
\item etc
\end{itemize}
}

%%%%%%%%%%  7. 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}

%%%%%%%%%%  8. further examples of the N=3 %%%%%%%%%%
\clearpage
\begin{figure}[tbph]
 \begin{center}
   \epsfile{file=three-neuron-sim.eps,width=21cm,height=14cm}
 \end{center}
\end{figure}

%%%%%%%%%%  8. State Transition} %%%%%%%%%%
\clearpage
\noindent
{\bf $\Box$ State Transition}
%%\vspace{1in}
\begin{displaymath}
s_{i}\hspace{.02in} (t+1) = sgn \hspace{.02in} \left( \hspace{.04in} \sum_{j}^N { w_{ij} s_{j}(t)} 
     \hspace{.04in} \right)
\end{displaymath}
%%\vspace{1in}
\noindent
Example:
\begin{displaymath}
\begin{array}{ccl}
s_1(1) & =  & sgn \hspace{.02in} \left( \hspace{.04in} w_{11} \cdot s_1(0) 
                                     +  w_{12} \cdot s_2(0) 
                                     +  w_{13} \cdot s_3(0) \hspace{.04in} \right) \\
       &    & \\
       & =  & sgn \hspace{.02in} \left( \hspace{.04in} 0.14 \cdot 1
                                     + (-0.34) \cdot 1 +  (-0.52) \cdot 1 \hspace{.04in} \right) \\
       &    & \\
       & = & -1
\end{array}
\end{displaymath}

%%%%%%%%%%  9. Hebbian Weights %%%%%%%%%%
\clearpage
\noindent
{\bf $\Box$ Hebbian Weights}
\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}
\vspace{1in}
\begin{displaymath}
\left(
\begin{array}{ccc}
 0    &  0.11 &  0.11 \\
 0.11 &  0    &  0.11 \\
 0.11 &  0.11 &  0
\end{array}
\right)
\end{displaymath}

%%%%%%%%%%  9. chorus  %%%%%%%%%%
\clearpage
\noindent
\begin{center}
$\bullet$ Thus we have many solutions in weight space.\\

$\Downarrow$ \\

$\bullet$ A large network has an infinitely large  number of these solutions.\\

$\Downarrow$ \\

$\bullet$ How we can obtain them exhaustively?\\

$\Downarrow$ \\

$\bullet$ Evolutionary Computations.
\end{center}

%%%%%%%%%%  9. chorus  %%%%%%%%%%
\clearpage
\noindent
\begin{center}
To apply an EC to a problem:\\

$\Downarrow$ \\

a number of {\bf candidate solutions} are produced (mostly) at random,\\

$\Downarrow$ \\

representing them as strings ({\bf chromosomes}).\\

$\Downarrow$ \\

{\bf population}\\

\end{center}

%%%%%%%%%%  9. GA in AM  %%%%%%%%%%
\clearpage
\begin{Large}
\begin{displaymath}
\left(
\begin{array}{ccc}
 0.14 & -0.34 & -0.52 \\
 0.62 &  0.62 & -0.47 \\
-0.22 & -0.04 & 0.77
\end{array}
\right)
= (0.14, -0.34 , -0.52, 0.62 ,  0.62 , -0.47, -0.22 , -0.04 , 0.77)
\end{displaymath}

\begin{displaymath}
\left(
\begin{array}{ccc}
 0.82 & -0.39 & -0.45 \\
 0.38 & -0.24 &  0.70 \\
 -0.58 &  0.46 & -0.88
\end{array}
\right)
=  (0.82 , -0.39 , -0.45 , 0.38 , -0.24 ,  0.70 , -0.58 ,  0.46 , -0.88)
\end{displaymath}
\end{Large}
\noindent
\hspace*{5in} \begin{Huge} $\cdots$ \end{Huge}\\
\hspace*{5in} \begin{Huge} $\cdots$ \end{Huge}\\
\hspace*{5in} \begin{Huge} $\cdots$ \end{Huge}\\
\begin{Large}
\begin{displaymath}
\left(
\begin{array}{ccc}
-0.62 & 0.28 & -0.61 \\
 0.92 & -0.24 & 0.06 \\
-0.11 & -0.85 & 0.49
\end{array}
\right)
=  (-0.62 , 0.28 , -0.61 , 0.92 , -0.24 ,  0.06 , -0.11 , -0.85 , 0.49)
\end{displaymath}
\end{Large}

%%%%%%%%%%  9. GA in AM  %%%%%%%%%%
\clearpage
\noindent
{\bf $\Box$ Fitness Evaluation:} \\

\begin{itemize}
\item The degree to how a weight configuration works as an associative memory.
\end{itemize}
     \begin{itemize}
     \item[]
     \begin{displaymath}
     f = \max \{ \hspace{.05in} \frac {1}{t_{0}} \sum_{t=1}^{t_{0}}{m^{\nu}(t)}\hspace{.1in} \vert 
                 \hspace{.1in}\mu = 1, 2, \cdots, p \}.
     \end{displaymath}
     \end{itemize}
\begin{itemize}
\item[]
\item At the start:
     \begin{itemize}
     \item low fitness,
     \item different from each other.
     \end{itemize}
\end{itemize}


%%%%%%%%%%  9. evolution  %%%%%%%%%%
\clearpage
{\bf $\Box$ Evolution proceeds by:} 

\begin{itemize}
\item[]
\item {\bf Selection} 
\item {\bf recombination}
\item {\bf mutation}
\end{itemize}

%%%%%%%%%%  9. GA in AM  %%%%%%%%%%
\clearpage
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=three-d-ga.eps,width=24cm,height=16cm}
 \end{center}
\end{figure}

%%%%%%%%%%  9. chorus  %%%%%%%%%%
\clearpage
\noindent
{\bf $\Box$ How to observe evolutions?}\\

\begin{itemize}
\item[(1)] State trajectories.
\end{itemize}

%%%%%%%%%% 10. Hamming vs time -- 1 %%%%%%%%%%
\clearpage
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=trajectory-0154.eps,width=10cm,height=7cm}
   \epsfile{file=trajectory-0200.eps,width=10cm,height=7cm}
 \end{center}
\end{figure}

%%%%%%%%%% 11. Hamming vs time -- 2  %%%%%%%%%%
\clearpage
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=trajectory-0210.eps,width=7cm,height=5cm}
   \epsfile{file=trajectory-0240.eps,width=7cm,height=5cm}
   \epsfile{file=trajectory-0300.eps,width=7cm,height=5cm}
 \end{center}
\end{figure}

%%%%%%%%%% 12. Hamming vs time -- 3  %%%%%%%%%%
\clearpage
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=trajectory-1000.eps,width=7cm,height=5cm}
   \epsfile{file=trajectory-2200.eps,width=7cm,height=5cm}
   \epsfile{file=trajectory-final.eps,width=7cm,height=5cm}
 \end{center}
\end{figure}

%%%%%%%%%%  13.chorus  %%%%%%%%%%
\clearpage
\noindent
{\bf $\Box$ How to observe evolutions?}\\

\begin{itemize}
\item[(2)] Fitness value of the best individual in the population
\end{itemize}

%%%%%%%%%%  14. three examples of fitness evolution %%%%%%%%%%
\clearpage
\begin{figure}[tbph]
 \begin{center}
   \epsfile{file=fit-r.eps,width=8cm,height=12cm}
   \epsfile{file=fit-h.eps,width=8cm,height=12cm}
   \epsfile{file=fit-z.eps,width=8cm,height=12cm}
 \end{center}
\end{figure}

%%%%%%%%%%  15. concept of fitness landscape %%%%%%%%%%
\clearpage
\begin{center}
{\bf Fitness Landscapes on Weight Space}\\

\vspace{.6in}

$\bullet$ 
all the possible configurations of $w_{ij}$ of a network with $N$\\

$\Downarrow$ \\

$\bullet$ an $N^2$-dimensional Euclidean space \\

$\Downarrow$ \\

$\bullet$ a specific configuration is represented as a point in the space\\

$\Downarrow$ \\

$\bullet$ ``fitness landscape'' can be defined on the space

$\Downarrow$ \\

$\bullet$ where we can imagine the optima as peaks

\end{center}

%%%%%%%%%%  16. string space vs weight space %%%%%%%%%% 
\clearpage
\noindent
{\bf $\Box$ The preliminary step:}
\begin{itemize}
\item Many different solutions by EC's.
\item[]
\end{itemize}

\noindent
{\bf $\Box$ The next step:}
\begin{itemize}
\item What does the Fitness Landscape look like?
   \begin{itemize}
   \item How is its geometry?
   \end{itemize}
\item Exploration of Weight Space.
   \begin{itemize}
   \item The number and distribution of weight solutions?
   \end{itemize}
\end{itemize}

%%%%%%%%%%  17. string space vs weight space %%%%%%%%%% 
\clearpage
\noindent
{\bf $\Box$ Weight Space and String Space:}\\
\begin{itemize}
\item weight space
   \begin{itemize}
   \item a given set of patterns to be memorized: fixed
   \item $N^2$-dimensional; real-valued genes
   \end{itemize}
\item[]
\item string space
   \begin{itemize}
   \item defined on all the possible N-bit binary patterns
   \item a configuration of weights: fixed
   \item $N$-dimensional; binary genes
   \end{itemize}
\end{itemize}

%%%%%%%%%%  17. string space vs weight space %%%%%%%%%% 
\clearpage
\noindent
{\bf $\Box$ The dimensionality of weight space:}\\
\begin{itemize}
\item $N$-neurons $\Rightarrow$ $N^2$-dimensional.
\item 49-neurons $\Rightarrow 49^2 = 2401$-dimensional.
\end{itemize}

%%%%%%%%%%  18. to be more specific  %%%%%%%%%%
\clearpage
\begin{center}
{\bf
A Multimodal GA\\

\hspace{1in}\\

explores\\

\hspace{1in}\\

string space\\

\hspace{1in}\\

searching for\\

\hspace{1in}\\

patterns embedded by the Hebb rule\\

\hspace{1in}\\

starting at\\

\hspace{1in}\\

random points.\\
}
\end{center}

%%%%%%%%%%  17. string space vs weight space %%%%%%%%%% 
\clearpage
\begin{center}
{\bf $\Box$ A multimodal Genetic Algorithm}\\

$\Downarrow$\\

locates multiple solutions simultaneously at a run.
\end{center}

%%%%%%%%%%  19. example of fitness in pattern space %%%%%%%%%%
\clearpage
\begin{figure}[tbph]
 \begin{center}
   \epsfile{file=sga-fit.eps,width=24.0cm,height=14.0cm}
 \end{center}
\end{figure}

%%%%%%%%%%  21. evolution by crowding  %%%%%%%%%% 
\clearpage
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=crowding.eps,width=24cm,height=14cm}
 \end{center}
\end{figure}

%%%%% 20. Crowding Algorithm %%%%%
\clearpage
\noindent
{\bf Deterministic Crowding (Mahfoud, 1992)}\\

\begin{itemize}
\setlength{\itemsep}{0pt}
%% \item[(1)] Choose two parents, $p_1$ and $p_2$, at random, with no parent being chosen more than once.
\item[(1)] Choose two parents, $p_1$ and $p_2$, at random, without repetition.
\item[(2)] Produce two children, $c_1$ and $c_2$, with uniform crossover.
\item[(3)] Mutate the children by flipping bit chosen at random with probability $p_m$,\\
           yielding $c_1^{\prime}$ and $c_2^{\prime}$.
\item[(4)] Replace parent  with child as follows: 
   \begin{itemize}
   \item IF \hspace{.05in} $d(p_1, c_1^{\prime}) + d(p_2, c_2^{\prime}) > d(p_1, c_2^{\prime}) + d(p_2, c_1^{\prime})$
      \begin{itemize}
      \item IF \hspace{.05in} $f(c_1^{\prime}) > f(p_1)$ THEN \hspace{.05in} replace $p_1$ with $c_1^{\prime}$
      \item IF \hspace{.05in} $f(c_2^{\prime}) > f(p_2)$ THEN \hspace{.05in} replace $p_2$ with $c_2^{\prime}$
      \end{itemize}
   \item ELSE
      \begin{itemize}
      \item IF \hspace{.05in} $f(c_2^{\prime}) > f(p_1)$ THEN \hspace{.05in} replace $p_1$ with $c_2^{\prime}$
      \item IF \hspace{.05in} $f(c_1^{\prime}) > f(p_2)$ THEN \hspace{.05in} replace $p_2$ with $c_1^{\prime}$
      \end{itemize}
   \end{itemize}
\end{itemize}

%%%%%%%%%%  15. concept of fitness landscape %%%%%%%%%%
\clearpage
\begin{center}
{\bf $\Box$ Techniques of observing high dimensional space:}\\

$\Downarrow$ \\

visualization\\

by\\

dimension reduction\\

$\Downarrow$ \\

\begin{displaymath}
\left\{
\begin{array}{l}
\cdot \hspace{.1in} \mbox{Principal Component Analysis (PCA)}\\
\cdot \hspace{.1in} \mbox{Genetic Algorithm (GA)}
\end{array} \right.
\end{displaymath}
\end{center}

%%%%%%%%%%  22. pca result one  %%%%%%%%%% 
\clearpage
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=pca.eps,width=24cm,height=14cm}
 \end{center}
\end{figure}

%%%%%%%%%%  23. pca result two  %%%%%%%%%% 
\clearpage
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=pca-2d.eps,width=24cm,height=14cm}
 \end{center}
\end{figure}

%%%%%%%%%%  24. other visualization 1  %%%%%%%%%% 
\clearpage
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=line-point.eps,width=12cm,height=14cm}
   \epsfile{file=block-point.eps,width=12cm,height=14cm}
 \end{center}
\end{figure}

%%%%%%%%%%  25. other visualization 2  %%%%%%%%%% 
\clearpage
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=hopfield-point-10-new.eps,width=12cm,height=14cm}
   \epsfile{file=hopfield-point-90.eps,width=12cm,height=14cm}
 \end{center}
\end{figure}

%%%%%%%%%% 26. conclusion %%%%%%%%%%
\clearpage
{\bf $\Box$ Conclusions:}\\
\begin{itemize}
\item We have many different weight solutions for Associative Memory.
   \begin{itemize}
   \item[] The Number and distribution of these solutions?
   \end{itemize}
\item[]
\item PCA \& GA visualize a high dimensional space.
\item[]
\item We shed new light on the analysis.
\end{itemize}

\end{LARGE}
\end{document}
