\documentstyle[eclepsf]{article}
\textheight 250mm
\topmargin -10mm
\textwidth 180mm
\oddsidemargin -7mm

\pagestyle{myheadings}
\markright{(Practice --- Evolutionary Computations)}
\thispagestyle{empty}

\title{{\large (Brest State Technical University 2006 Fall Semester: Course Practice)}\\
Contemporary Intelligent Information Technology}
\author{Akira Imada\\
(e-mail akira@bstu.by)\\
\hspace{1in}\\
This document is still under construction and was lastly modified on}

\begin{document}
\maketitle

\section{The Simplest Test Function --- Sphere Model}
\noindent
The first task of this practice is to obtain the minimul value of a multi-dimensional function.\\

\noindent
To be more specific, we now assume that 
we have the following function defined in a 20-dimensional space:
\begin{equation}
y = x_1^2 + x_2^2 + x_3^2 + \cdots + x_{20}^2.
\end{equation}
Then obtain which point of $(x_1, x_2, x_3, \cdots, x_{20})$ gives a minimum value of $y$
and how much is the value of minimum $y$.\\

\noindent
Try the following algorithm.

\newtheorem{algorithm}{Algorithm}
\begin{algorithm}[The simplest example]\hspace{1in}\\
\begin{itemize}
\item[1.] Create 100 chromosomes at random.
   \begin{itemize}
   \item[$cdot$] The number of gene is 20. Thus our chromosomes here have the form 
                 $(x_1, x_2, x_3, \cdots, x_{20})$.
   \item[$cdot$] Assume here each of $x_i$ takes the continuous value from $-1$ to 1, that is
                 $-1<x_i<1$.
   \end{itemize}
\item[2.] Calculate {\it fitness} value by $y = x_1^2 + x_2^2 + x_3^2 + \cdots + x_{20}^2.$
          Note that the smalle the better.
\item[3.] Select 2 chromosomes at random from the better half of the population of 100 chromosomes.
\item[4.] Create a child chromosome by a {\it crossover}.
\item[5.] Give the child a {\it mutation} 
\item[6.] Repeat from 2. to 5. above 100 times and create the next {\it generation}.
\item[7.] Repeat 6. until the fitness value reaches 0.
\end{itemize}
\end{algorithm}


\noindent
The the question is as follows.

\newtheorem{excersize}{Excersize}
\begin{excersize}[Obtaining the global minimum]\hspace{1in}\\
(1) Plot the average fitness value of all the 100 chromosomes versus generation.
(2) Also plot the minimum fitness value of each generation.
\end{excersize}

%%-------------------------------------------------------------------------------------------
\section{Neural Networks for XOR}
\noindent
This is probably a simplest examples. We now try the below.

\begin{itemize}
\item Output $Y$ of the neuron which receives weighted-sum of the signals $X_i$
      from other $N$ neurons is:
\begin{displaymath}
Y = \mbox{sgn} (\sum_{i=1}^N w_{i}X_i - \theta)
\end{displaymath}
\item[] where $\mbox{sgn}(x) = 1$ if $x \ge 0$ and 0 otherwise, and $w_{i}$ and $\theta$
        are called {\it weight} and {\it threshold}, respectively. \\
\item NN to solve AND \& OR. \\
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=and.eps,width=6cm,height=3cm}
 \end{center}
\end{figure}
\item[$\cdot$] Well, how about NN to solve XOR?
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=xor.eps,width=8cm,height=4cm}
 \end{center}
\end{figure}
\end{itemize}

\newtheorem{exercise}{Exercise}
\begin{exercise}
Obtain six weights values so that the above NN function as XOR.
\end{exercise}
\begin{exercise}
Create Pseudo code for EC to obtain the six weights above.
\end{exercise}

\section{TSP or Knapsack Problem}

\clearpage
\section{Multi Modal Genetic Algorithms\\
-- What if we have multipul different meaningful solution?}

\subsection{Target Functions}
Assuming our goal is maximization, that is, we want to know when $y$ takes the maximum
value and for which $x$, we try two test functions.

\begin{large}\begin{equation}
y = \sin ^6 (5 \pi x)
\end{equation}\end{large}

\noindent
and

\begin{large}\begin{equation}
y = -2((x-0.2)/0.8)^2 \sin ^6 (5 \pi x)
\end{equation}\end{large}

\noindent
Now take a look what do these two function look like.

\begin{figure}[h]
 \begin{center}
   \epsfile{file=test-for-share.eps,width=7.5cm,height=6cm}
   \epsfile{file=test-for-share-2.eps,width=7.5cm,height=6cm}
\caption{A multi-peak 2-D function and its variation}
 \end{center}
\end{figure}


\subsection{Encoding}
\noindent
The question is how we design our chromosomes.
In the multi-dimensional function $y = f(x_1, x_2, \cdots, x_n)$
our genes might be continuos value each of which corresponds to the independent
variable $x_i$ $(i = 1, 2, \cdots n)$, that is, our chromosomes are made up of $n$ genes.
On the other hand how should we design our chromosomes when the number of independent variable
is only one? A chromosome with only one gene? Then how we crossover two parents? \\

\noindent
O.K. we usually use binary chromosome in this situation.
Any (decimal) real-valued variable $x_i \in [a, b]$ could be encoded by $n$-bit binary
strings where $a$ and $b$ is represented by $(00\cdots0)$ and $(11\cdots1)$, respectivley, and
therfore accuracy (or granularity) is $(b - a)/(2^n - 1)$.
For example, if our concern is the above $x \in [0, 1]$ then
10 bit of binary strings from $0000000000$ to $1111111111$
are expresses decimals with the precision of 1/1024.

\subsection{Two Algorithms}
Here, we have two algorithms for the current purpose of finding multiple solutions at a run.
\subsubsection{Fitness Sharing} 
Fitness of each individual is derated by an amount related to 
the number of similar individuals in the population.
That is, shared fitness $F_s(i)$ of the individual $i$ is 

\begin{displaymath}
F_s (i) = \frac{F(i)}{\displaystyle \sum_{j=1}^\mu s(d_{ij})}
\end{displaymath}

\noindent
where
$F(i)$ is fitness of individual $i$;
$d_{ij}$ is distance between individual $i$ and $j$;
Typically $d_{ij}$ is {\it Hamming distance} if in {\it genotypic space} 
{\it Euclidean distance} if in {\it phenotypic space} and 
$s(\cdot)$ is called {\it sharing function} and defined as:

\begin{displaymath}
s(d_{ij}) = \left\{
\begin{array}{ll}
1 - (d_{ij} / \sigma_{\mbox{\small share}})^{\alpha} & \hspace{.2in} 
                         \mbox{if} \hspace{.1in} d_{ij} < \sigma_{\mbox{\small share}} \\
0                                           & \hspace{.2in} 
                         \mbox{otherwise}
\end{array}
\right.
\end{displaymath}

\noindent
where
$\sigma_{\mbox{\small share}}$ is interpreted 
as size of niche, and 
$\alpha$ determines the shape of the function.
The denominator is called {\it niche count}.
You see shape dependency of $s(d_{ij})$ on $\alpha$
in Figure~\ref{fig:shareing}.

\begin{figure}[h] \label{fig:shareing}
 \begin{center}
   \epsfile{file=sharing.eps,width=9cm,height=6cm}
   \caption{A shape dependency of $s(d_{ij})$ on $\alpha$.}
 \end{center}
\end{figure}

\noindent
To be short (not so short though): Similar individual should share fitness.
The number of individuals that can stay around any one of peaks (niche)
         is limited. \\
The number of individuals stay near any peak will theoretically 
         be proportional to the {\it hight} of the peak\\


\subsubsection{Deterministic Crowding}
If the parents will be replaced or not with their childeren
will be determined under a criteria of the distance between parents and children.

\hspace*{1in}\\

\noindent
{\bf Algorithm} Assuming crossover, mutation and fitness function are already defiened
{\it
\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[2.] Produce two children, $c_1^{\prime}$ and $c_2^{\prime}$.
\item[3.] Mutate the children 
           yielding $c_1$ and $c_2$, with a crossover.
\item[4.] Replace parent  with child as follows: 
   \begin{itemize}
   \item[-] IF \hspace{.05in} $d(p_1, c_1) + d(p_2, c_2) > d(p_1, c_2) + d(p_2, c_1)$
      \begin{itemize}
      \item IF \hspace{.05in} $f(c_1) > f(p_1)$ THEN \hspace{.05in} replace $p_1$ with $c_1$
      \item IF \hspace{.05in} $f(c_2) > f(p_2)$ THEN \hspace{.05in} replace $p_2$ with $c_2$
      \end{itemize}
   \item[-] ELSE
      \begin{itemize}
      \item IF \hspace{.05in} $f(c_2) > f(p_1)$ THEN \hspace{.05in} replace $p_1$ with $c_2$
      \item IF \hspace{.05in} $f(c_1) > f(p_2)$ THEN \hspace{.05in} replace $p_2$ with $c_1$
      \end{itemize}
   \end{itemize}
\end{itemize}
\noindent
where $d(\zeta_1, \zeta_2)$ is the Hamming distance between 
two points $(\zeta_1, \zeta_2)$ 
in pattern configuration space.
The process of producing child is repeated until 
all the population have taken part in the process.
Then the cycle of reconstructing a new population 
and restarting the search is repeated until 
all the global optima are found or a set maximum number of generation has been reached.
}\\


\subsection{Results you should show.}
\noindent
Hopefully you apply two algorithms to each of two test functions. Besides fitness-generation
graph, as usual, you try visualize how your individual change their location as generation goes.\\

\noindent
That is to say, show all points of individuals in, say,  every 20 generations 
in order to see how theyconverge to the peaks.





\end{document}


create your own $p$ patterns 
each of which is made up of $N^2$ binary pixels.
Examples are shown in Figure 1.



\begin{figure}[hbtp]
\begin{center}
   \epsfile{file=patterns.eps,width=12cm,height=3cm}
   \caption{An example for $N=3$. White pixcel is represented by $-1$ and 
            white pixel is by $+1$. That is, patterns are represented 
            with 9-bit {\it bipolar} vectors.}
\end{center}
\end{figure}


\noindent
To be more formal, our $p$ patterns are expressed as

\begin{equation}
(\xi^1_1, \xi^1_2, \cdots, \xi^1_N),\hspace{.1in}
(\xi^2_1, \xi^2_2, \cdots, \xi^2_N),\hspace{.1in}
(\xi^3_1, \xi^3_2, \cdots, \xi^3_N),\hspace{.1in} \cdots, \hspace{.1in}
(\xi^p_1, \xi^p_2, \cdots, \xi^p_N).
\end{equation}

\noindent
where $\xi^{\mu}_{i} \in \{-1,1\}$, \hspace{.05in} 
$\mu = 1,2, \cdots, p$ \hspace{.05in} and \hspace{.05in} 
$i = 1,2, \cdots, N^2.$ \\

\hspace*{1in}\\
\noindent
For example, the first example in the Figure 1 is 

\begin{displaymath}
(-1, +1, -1, 
 +1, +1, +1, 
 -1, +1, -1)
\end{displaymath}



\newtheorem{excersize}{Excersize}
\begin{excersize}[10 Patterns to be Stored]
Create your own 10 patterns 
each of which is made up of $10 \times 10$ binary pixels.
\end{excersize}



\section{Construct a Hopfield Neural Network to store your patterns!}

\noindent
Now Let's create a Hopfield Neural Network with $N \times N$ neurons.
All neurons are connected with each other via synapse.\\

\noindent
Each of  neurons are influenced by other $(N \times N -1)$ neurons.
The strength of an influence from one neuron is according to the weight value
of the synapse.  
Thus, state of neuron $i$ at time $t+1$ $s_{i}\hspace{.02in} (t+1) $is given as

%%\begin{Large}
\begin{equation} \label{eq:1-1}
  s_{i}\hspace{.02in} (t+1) 
    = sgn \hspace{.02in} \left( \hspace{.04in} 
      \sum_{j \ne i}^N { w_{ij} \cdot s_{j}(t)} \hspace{.04in} \right).
\end{equation}
%%\end{Large}

\subsubsection{How we update state of neurons?
--- Sinchronous and Asynchronous update}
\noindent
Now a question arise, how are neurons updated? Simultaneously-at-a-time 
or one-by-one? The former is called {\it Sinchronous update} and the latter
is {\it Asynchronous update.} In this practice course we use the asynchronous
update.\\

\noindent
In other words, at time $t$, neuron-1 is firstly updated, and, 
this new state will be used to update other neurons here after; 
next, neuron-2, neuron-3, and so on, until all the neurons are updated.
Then this updated procedures are repeated at time $t+1$, 
and on and on. \footnote {We can update neurons in a random order
different order at every time $t$, but here we update from the 1st neuron
to the last neuron one by one.}

\subsection{An experiment with random weight values:}
Now we have $10^2$ synapses and each snyapse has 
a strength called {\it weight}.
The weight value from neuron-$j$ to neuron-$i$ is denoted here as $w_{ij}$
\hspace{0.05in} $i,j = 1,2, \cdots 100$. \\

\noindent
We must assign these 100 weight values appropriately to store
our patterns. However, we start with a set of 100 random values
each of which is in $[-1, 1]$, such as $-0.534$, are assigned.


\begin{excersize}[Observe the behaviours of your Hopfield Network.]
Give one of your patterns to your Hopfield Network 
with random weight values, and observe what will happen.
That is, set $S_i(0) = \xi_i^\mu$ for all $i = 1, 2, \cdots, N^2$
with a specific $\mu$ you like. Then observe the pattern 
for $t= 1, 2, \cdots$, namely, how the pattern changes as time proceeds. 
\end{excersize}

\section{Let's store your patterns!}

\subsection{Hebbian Learning}
Here we calculate the weight according to the following equation,
called Hebbian Learning.
\begin{Large}
\begin{equation} \label{eq:1-2}
w_{ij} = \frac{1}{N} \sum _{ \mu = 1}^{p} 
         {{ \xi }_{i}^{ \mu }{ \xi }_{j}^{ \mu }}
         \hspace{.1in}(i \ne j), \hspace{.1in} w_{ii} = 0.
\end{equation}
\end{Large}


\begin{excersize}[Observe the behaviours of your Hopfield Network Part II.]
Repeat the previous excersize with the weights calculated with the above
equation, instead of random values.
\end{excersize}

\section{Let's observe how it is clever (or fool)!}
Now if your work is successful
Network recognize your patterns in the following way.
\begin{itemize}
\item[(1)] If you give one of your patterne as it is, 
then the initial state never be changed. \footnote{In
this case the pattern is called {\it fixed point}.}
\item[(2)] If you give a noisy version of your pattern, then
initial state changes several  steps and converges to the 
original pattern. \footnote{We call it ``An initial state
in the vasin of attraction is attracted to its fixed point.}
\item[(3)] If you give a very different pattern from any of 
your patters, then network shows a {\it chaotic} behaviour,
e.g., repeat a same cycle of patterns or changes forever in
a random way.
\end{itemize}

\noindent
Then you may test your Hopfield Network to know how it is clever
or fool.by changing (i) the number of patterns stored and/or
(2) number of noisy bit.

\begin{excersize}[Observe the behaviours of your Hopfield Network Part III.]
Starting with 1 pattern, test the capability of the Network
by incrementing the number of noisy bits from zero, 
and observe when the Network become to be chaotic.
Plot this critical number as a function of number of noise with
a parameter of the number of patterns stored.  
\end{excersize}

\section{Fuzzy Logic}


\begin{figure}[hbtp]
\begin{center}
   \epsfile{file=membership-function.eps,width=7cm,height=4cm}
   \epsfile{file=membership-function-.eps,width=7cm,height=4cm}
   \caption{An example for $N=3$. White pixcel is represented by $-1$ and 
            white pixel is by $+1$. That is, patterns are represented 
            with 9-bit {\it bipolar} vectors.}
\end{center}
\end{figure}



\end{document}
