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

%% \documentstyle[12pt,eclepsf]{article}
\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{rsfs}

\usepackage{graphicx}
\usepackage{color}

\textheight 230mm
\topmargin 5mm
\textwidth 160mm
\oddsidemargin -2mm

\pagestyle{myheadings}
\markright{(Practice -- Contemporary Intelligent Information Techniques)}
\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

\clearpage
\section{All One Problem}
\noindent
In order to study what will be going on under the computational evolution, let's start
very simple experiment.\\

\noindent
We now evolve binary chromosomes. We start with the initial population with, say, 
100 binary chromosomes with, say, 40 genes, -- all created at random.
The fitness is the number of ``1'' in chromosome --- the more the better.
That is our target is all-one-chromosome.\\

\noindent
Try a standard evolution with (i) one-point-crossover and (ii) uniform-crossover,
with mutation rate being $1/N$ where $N$ is the number of genes in one chromosome.\\


\newtheorem{algorithm}{Algorithm}
\bigskip
\begin{algorithm}[All-One-Problem]\hspace{1in}
\begin{itemize}
\setlength{\itemsep}{0pt}
\item[1.] Create, say, 100 binary-chromosomes at random where the number of gene is 40. 
\item[2.] {\it Fitness} is the number of ``1'' in one chromosome -- the more 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}.
      \begin{itemize}
      \item[$\cdot$] Compare two performances one with one-point-crossover and the other with uniform-crossover.
      \end{itemize}
\item[5.] Give the child a {\it mutation} with a probability of 1/40 = 0.025.
\item[6.] Repeat from 2. to 5. 40 times and create the next {\it generation}.
\item[7.] Repeat 6. until the fitness value reaches 40.
\item[8.] Show the result:
      \begin{itemize}
      \item[(1)] Desplay the best chromosome in each generation from generation to generation.
      \item[(2)] Desplay the best-fitness vs. generation and average-fitness vs. generation.
      \end{itemize}
\end{itemize}
\end{algorithm}





\clearpage
\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{large}
\begin{equation}
y = x_1^2 + x_2^2 + x_3^2 + \cdots + x_{20}^2.
\end{equation}
\end{large}
\noindent
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$. Now, try the following algorithm.


\begin{algorithm}[The minimization of the simplest high-D function]\hspace{1in}\\
\begin{itemize}
\item[1.] Create, say, 100 chromosomes at random.
   \begin{itemize}
   \item[$\cdot$] The number of gene is 20. 
      \begin{itemize}
         \item[] Thus our chromosomes here have the form $(x_1, x_2, x_3, \cdots, x_{20})$.
                 
      \end{itemize}
   \item[$\cdot$] Assume here each of $x_i$ takes the continuous value from $-1$ to 1, that is
      \begin{itemize}
                 \item[] $-1<x_i<1$.
      \end{itemize}
   \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 smaller 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. 100 times and create the next {\it generation}.
\item[7.] Repeat 6. until the fitness value reaches 0.
\end{itemize}
\end{algorithm}


\noindent
Then 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}



\clearpage
\section{A little more tricky function} 
Let's try a little more tricky function. for example, the one called Rastrigin's Function.

\begin{Large}
\begin{displaymath}
y = nA + \sum_{i=1}^n {(x_i^2 - A \cos(2\pi x_i))},  \hspace{.2in}
x_i \in [-5.12-5.12].
\end{displaymath}
\end{Large}

\noindent
Dimensionality $n$ is arbitorary, but to see how its graph look like, see the Figure when $n=1$.


\begin{figure}[h]
\begin{center}
\includegraphics[width=16cm,height=4cm]{rastrigin.eps}
\caption{A 2-D version of Rastrigin function}
\end{center}         
\end{figure}


\begin{excersize}[Obtaining the global minimum]\hspace{1in}\\
(0) Try in the case of $n=20$.
(1) Plot the average fitness value versus generation.
(2) Also plot the minimum fitness value of each generation.
(3) Make an experiment with different value of mutation rate.
\end{excersize}


\clearpage
\section{2-D Functioon}
We now try a 2-D Function in order to observe what will be going on under an evolution.
Let's try to find the minimum point of the following function as an example.

\begin{large}
\begin{displaymath}
y = x^4 - 5x^3 - 6x^2 + 8x + 15
\end{displaymath}
\end{large}

\noindent
The graph looks like when  $ x \in [-2,5]$

\begin{figure}[hbtp]
 \begin{center}
\includegraphics[width=16cm,height=6cm]{f-4th-order.eps}
   \caption{Yet another test function: $y = x^4 - 5x^3 - 6x^2 + 8x + 15$ with $x \in [-2,5]$.} 
 \end{center}
\end{figure}

\subsubsection*{How you design chromosome to solve this problem?}
\noindent
In the previous problem, the number of genes is $n$ if the function is difiened on
$n$ dimensional space. Then our chromosome here has only one gene?
How, on earth, we crossover two chromosomes?\\

\noindent
The answer is, we use binary chromosome. In the above example, ...




\clearpage
\section{Neural Networks for XOR}
Assuming McCulloch-Pitts neurons which take the state 1 or 0,
the output $Y$ of the neuron which receives weighted-sum of the signals $X_i$ from other $N$ neurons is usually specified as:
\begin{large}
\begin{displaymath}
Y = \mbox{sgn} (\sum_{i=1}^N w_{i}X_i - \theta),
\end{displaymath}
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. Here, we assume neurons take binary state but -1 or 1, instead of 0 or 1. Hence the equation is modified as
\end{large}

\begin{large}
\begin{displaymath}
Y = 2 \cdot \mbox{sgn} (\sum_{i=1}^N w_{i}X_i - \theta) -1.
\end{displaymath}
\end{large}

\begin{figure}[hbtp]
 \begin{center}
\includegraphics[width=12cm,height=4cm]{xor.eps}
 \end{center}
\end{figure}


\clearpage
\section{Neural Network for Even-n-Parity}
Even-$n$-Parity is a boolean function to check whether number of 1 of $n$-bit binary is even or not. \\


\noindent
We now assume $n=4$ for the sake of simplisity.
Again our binary made up of  $-1$ and 1 instead of 0 and 1 for a convenience.
Hence, as in previous section, transfer function is
\begin{large}
\begin{displaymath}
y_i = 2 \cdot \mbox{sgn} (\sum_{j=1}^N w_{ij}x_j - \theta_j) -1,
\end{displaymath}
\end{large}
where $y_i$ is output of neuron-$i$, $w_{ij}$ is weight of the synapse from 
neuron-$j$ to neuron-$i$, $x_j$ is state of neuron-$j$, $\theta$ is threashold of 
neuron-$j$, and $N$ is the number of neurons connected to neuron-$i$. We assmue here
$\theta_j = 0.5$ for all $j$. 



\begin{table}[h]
\begin{center}
\begin{tabular}{c c c c c}
\hline \hline
$x_1$  &  $x_2$  &  $x_3$  &  $x_4$  &  y  \\ \hline
$-1$   &  $-1$   &  $-1$   &  $-1$   & $+1$\\
$-1$   &  $-1$   &  $-1$   &  $+1$   & $-1$\\
$-1$   &  $-1$   &  $+1$   &  $-1$   & $-1$\\
$-1$   &  $-1$   &  $+1$   &  $+1$   & $+1$\\
$-1$   &  $+1$   &  $-1$   &  $-1$   & $+1$\\
$-1$   &  $+1$   &  $-1$   &  $+1$   & $-1$\\
$-1$   &  $+1$   &  $+1$   &  $-1$   & $-1$\\
$-1$   &  $+1$   &  $+1$   &  $+1$   & $+1$\\
$+1$   &  $-1$   &  $-1$   &  $-1$   & $+1$\\
$+1$   &  $-1$   &  $-1$   &  $+1$   & $-1$\\
$+1$   &  $-1$   &  $+1$   &  $-1$   & $-1$\\
$+1$   &  $-1$   &  $+1$   &  $+1$   & $+1$\\
$+1$   &  $+1$   &  $-1$   &  $-1$   & $+1$\\
$+1$   &  $+1$   &  $-1$   &  $+1$   & $-1$\\
$+1$   &  $+1$   &  $+1$   &  $-1$   & $-1$\\
$+1$   &  $+1$   &  $+1$   &  $+1$   & $+1$\\ \hline \hline
\end{tabular} 
\end{center}
\end{table}

\noindent
We now exploit a feedfoward Neural Network with 4 input neurons, 4 hidden neurons, and one output neurons.
So, we have 20 synapsis and as such our chromosome has 20 genes. Create 100 chromosomes with random
weight from $-1$ to 1. 
Fitness evaluation is by counting the correct answer after giving all the possible 16 cases of 4 inputs, one by one.
Then evolve the population.


\begin{excersize}[Neural Network for Even-4-Parity]\hspace{1in}\\
(1) Plot the average fitness in the population as a function of generation.
(2) Plot the maximum fitness in the population as a function of generation.
(3) Demonstrate the finally obtained neural network by giving 4 inputs from keybord.
\end{excersize}


\clearpage
\section{Navigoation in gridworld}
\noindent
Assume now that we want to make an agent, or a robot, in a gridworld, a possible chromosome
can be made up of integer gene from 1 to 4 where 1, 2, 3, and 4 correspond to one cell movement 
of the agent to north, south, east and west. Take a look at the below as an example.


\begin{figure}[h]
\begin{center}
\includegraphics[width=7.5cm,height=5cm]{robot-move.eps}
\caption{An example of chromosome and the trace of the robot whose has this chromosome.}
\end{center}
\end{figure}

\subsubsection*{Search for a path of maximum Manhattan distance}.
Starting with the center of a huge 2-dimensional gridworld, a robot navigate
following its chromosome. The length of the chromosome is 40 for example.
That is, the robot explore the gridworld with 40 steps.\\

\noindent
At the beginning, robots explore with random walk because its chromosome is given
at random.\\

\noindent
Some robot would just explore around the starting points. Think of the robot, for example, 
whose chromosome is
\begin{displaymath}
(1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 )
\end{displaymath}

The goal is to find a robot who reaches to the point with the maximum (40) Manhattan distance
from the starting point.


\clearpage
\subsubsection*{Search for a path to the goal with minimum Manhattan distance}
\noindent
In this problem, the point robots start with, and the goal they should reach are pre-specified.\\

\noindent
The goal is to find a robot who reaches the goal with the minimum Manhattan distance.
Sea the Figure below as an example.

\bigskip
\begin{figure}[bhtp]
\begin{center}
   \includegraphics[width=5cm,height=6cm]{trace-96-start.eps}
   \includegraphics[width=5cm,height=6cm]{trace-96-end-new.eps}
\caption{In the grid-world of $96\time96$ starting from (24,24) a robot walks aiming the goal at (72,72) of which the robot had no {\it a-priori} information. Left: The path of minimum length among 100 trials by random walk. Right: Minimal path the robot found after an evolutionary learning as shown in Fig.~3. (Marginal area is omitted.)}
\end{center}
\end{figure}



\clearpage
\section{Traveling Salesperson Promblem (TSP)}
Assuming $N$ cities all of whose cordinate are given, Traveling Salse-person Problem (TSP) is a problem in which a sales-person should visit all of these cities once but only once with its goal being to look for the shortest tour.\\

\noindent
We now take a look at 4 cities -- A, B, C, and D -- as a simplest example. We now assume the cities location are given as follows, for instance.
\begin{table}[h]
\begin{center}
\begin{tabular}{c c}  
\hspace*{.1pt} & $(x,y)$         
\vspace{.05in}                    \\ 
A              &  $(0.83, 7.79)$  \\
B              &  $(3.28, 8.32)$  \\
C              &  $(1.52, 4.48)$  \\
D              &  $(7.65, 3.46)$  \\
\end{tabular} 
\end{center}
\end{table}

\noindent
Then the Eucledean distances between all possible pair of cities are calculated using a formula:
\begin{equation}
r_{ij} = \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}
\end{equation}
where $r_{ij}$ is the distance between city $i$ and city $j$ and $(x_i, y_i)$ and $(x_j, y_j)$ are coordinate of city $i$ and city $j$, respectively. The distances are:

\begin{table}[h]
\begin{center}
\begin{tabular}{c c c c c}
\hspace*{.1pt} &   A   &   B   &   C   &   D   \vspace{.05in} \\ 
A              & 0.000 & 2.505 & 3.382 & 8.074 \\
B              & 2.505 & 0.000 & 4.232 & 6.539 \\
C              & 3.382 & 4.232 & 0.000 & 6.214 \\
D              & 8.074 & 6.539 & 6.214 & 0.000 \\
\end{tabular} 
\end{center}
\end{table}

\begin{figure}[hbtp] \label{fig:tsp}
 \begin{center}
\includegraphics[width=9cm,height=3.5cm]{city-4.eps}
 \end{center}
\caption{An example of 4 cities and a possible tour therein.}
\end{figure}

\noindent
All possible routes in this example are
\begin{center}
\begin{small}
(A-B-C-D-A), (A-B-D-C-A), (A-C-B-D-A), (A-C-D-B-A), (A-D-B-C-A), and (A-D-C-B-A).
\end{small}
\end{center}
\noindent
Notice here that lengths of a pair of tours is identical such as a pair
 (A-B-C-D-A) and (A-D-C-B-A).
That is, we have $3!/2 = 3$ routes in total in this example. \\

\noindent
Let's see now one root A-C-B-D-A out of them, in the map shown in Figure 5.\\ %%\ref{fig:tsp}.\\

\noindent
The length of the tour in the figure is 
\begin{displaymath}
r_{A-C-B-D-A} = 3.382 + 4.232 + 6.539 + 8.074 = 22.227
\end{displaymath}
\noindent
In the same way, we can calculate the other two route. That is,
\begin{displaymath}
r_{A-B-D-C-A} = 2.505 + 6.539 + 6.214 + 3.382 = 15.640
\end{displaymath}
\begin{displaymath}
r_{A-B-C-D-A} = 2.505 + 4.232 + 6.214 + 8.074 = 21.025
\end{displaymath}
\noindent
So, the tour of minimum length is A-B-D-C-A (or A-C-D-B-A).\\

\noindent
But what if we have larger number of cities? 
Now you know even in case of 10 cities, we have $9!/2 = 181,440$ possible differnt route. 
Do you want calculate those distances of all the possible tour? Of course not!
Further more, what about 1000 cities, for example?

\bigskip
\noindent
Then let's apply our evolutionary algorithm. Note that, however, chromosomes like
\begin{center}
(B D C)
\end{center}
for tour A-B-D-C-A and
\begin{center}
(D C B)
\end{center}
for tour A-D-C-B-A, would not work, because possible child
after {\it one-point crossover} by cutting between 1st and 2nd genes will be
\begin{center}
(B C B) and (D D C)
\end{center}
would not be feasible, because both are not a leagal tour -- visits one city twice 
neglecting one city. \\

\noindent
Then a possible design of chromosome is as follows.
\bigskip
{\it
\begin{itemize}
\item[]
   \begin{itemize}
   \item[]
      \begin{itemize}
      \item[Step-1.] Set $i=1$.
      \item[Step-2.] If $i$-th gene is $n$ then $n$-th city in the list is the city 
                     to be currently visited.
      \item[Step-3.] Remove the city from the list.
      \item[Step-4.] Set $i=i+1$ and repeat Step-2 to Step-4 while $i < n$.
      \end{itemize}
   \end{itemize}
\end{itemize} 
}

\bigskip
\noindent
For example, when the list of cities besides the starting city A is
\begin{center} \{B, C, D\} \end{center} 
\noindent
chromosome: $(1 2 1)$ is the tour:
\begin{center} A-B-D-C-A. \end{center}

\noindent
Note that genes can be any integer and {\it mutation} might be by simply replacing
a gene with another random integer. The probability might be 1/number-of-genes 
(you may change the ratio as an experiment, of course.)


\bigskip
\begin{excersize}[TSP]\hspace*{1in}
\begin{itemize} 
\setlength{\itemsep}{0pt}
\item[(1)] Create 14 cities by assign random coordinate $(x_i, y_i)$.
\item[(2)] Calculate the distance between all the possible two cities.
\item[(3)] Then evolve them until the total distance of tour converges one value.
\item[(4)] Repeat (3) until fitness value (= total distance of tour) converges a value. 
\end{itemize}
\end{excersize}

\bigskip
\subsubsection*{Results you should show me.}
\begin{itemize}
\setlength{\itemsep}{0pt}
\item Coordinates of All the cities.
\item Matric of distance between any 2 cities.
\item Graphic of the location of all the cities and the shortest tour.
\end{itemize}


\clearpage
\section{Knapsack Problem}
We now assume $n$ items whose $i$-th item has weight $w_i$ and profit $p_i$, 
then we pick up $x_i$ of the $i$-th item $i=1, 2, \cdots, n$ and $x_i$ is non-negative
integer. The goal is to  maximizes 
     \begin{equation}
     \sum_{i=1}^n {x_ip_i}.
     \end{equation}
such that 
     \begin{equation}\label{eq:knap-sack-capacity}
     \sum_{i=1}^n {x_iw_i} < C
     \end{equation} 
where $C$ is the capacity of the knapsack. \\

\noindent
GA implementation is quite simple. Our chromosomes are in the form
\begin{equation}
(x_1 x_2 x_3 \cdots x_n)
\end{equation}

\noindent
with each $x_i$ being the number of the $i$-th items to be in the knapsack.

\subsubsection*{Kill infeasible chromosomes}
One important aspect is if a chromosome does not fulfill the condition
of Eq.(\ref{eq:knap-sack-capacity}), simply kill the choromosome
and repeat the procedure which resulted in the infeasible child chromosome
(cross-over, mutation, or whatever.) untill creating a feasible child chromosome.
\begin{excersize}[Knapsack Problem]Assumming the size of knapsack is, say, 60.
\begin{itemize}
\setlength{\itemsep}{0pt}
\item[(1)] Create, say, 100 items, by giving each of whose price $p_i$ and size $w_i$ at random, 
both raging from 0 to 1. For example:
\begin{table}[h]
\begin{center}
\begin{tabular}{c c c c}
item              & price     & size   \vspace{.05in} \\ 
1st               & 0.37      & 0.62                  \\
2nd               & 0.52      & 0.45                  \\
3rd               & 0.95      & 0.38                  \\
$\cdots$          & $\cdots$  & $\cdots$              \\
100th             & 0.72      & 0.32                  \\
\end{tabular} 
\end{center}
\end{table}
\item[(2)] Creat 40 chromosomes each of which has 100 integer genes, like
\begin{center}
(5, 7, 13, $\cdots$ 2)
\end{center}
which means five 1st items, seven 2nd items 13 3rd items, $\cdots$, two 100th items.
\item[(3)] Try to check by replace with one item with price being 0.99 and size being 0.01
Imagine this item is like diamonds small and precious. Hence all items should converge this one.
And then replace all items with price being 0.01 and size being 0.01
In this case you know clearly the results.
\item[(4)] Try evolution and plot maximum fitness vs. generation, 
as well as average fitness vs. generation 
\item[(5)] Visualize the inside of the knapsack.
\end{itemize}
\end{excersize}

\clearpage
\section{Sammon Mapping by GA}
%% \hspace*{0.5in} --- {\large Sammon Mapping by GA}
\noindent
Here we learn about Sammon Mapping. Sammon Mapping is a mapping 
a set of points a in high-dimensional space to the 2-dimensional space
with the distance relation being preserved as much as possible, or equivalently,
the distances in the $n$-dimensional space are approximated by distances in the 2-dimensional 
distance with a minimal error.\\

\noindent
This method was proposed in 1980's as an optimization problem to which they approached by 
Operations Research technique suchas {\it Steepest Descend}, which is not 
so simple. Here, on the other hand, we employ Evolutionary Computatins which is
quite simple. Let's see now what is the original Sammon Mapping look like.\\
\hspace*{1in}\\

\noindent
{\bf Algorithm (Sammon Mapping)}
{\it
\begin{itemize}
\setlength{\itemsep}{0pt}
\item[1.] Assume $N$ points are given in the $n$-D space.
\item[2.] Calculate distance matrix $R$ ($N \times N$) whose $i$-$j$ element
          is the Euclidean distance between the $i$-th and $j$-th point.
\item[3.] Also think of a tentative $N$ points in the 2-D space that are
          located at random at the beginning.
\item[4.] The distance matrix $Q$ is calculated in the same way as $R$.
\item[5.] Then the error matrix $P=R-Q$ is defined.
\item[6.] Search for the locations of $N$ points in the 2-D space
          that minimizes the sum of element $P$.
\end{itemize}
}

\hspace*{1in}\\

\noindent
This is an optimization problem which we now can solve quite simply by using EC. 
That is, 
{\it by creating $N$ points in 2-D space each of which corresponding
$N$ points in the $n$-D space
with the distance relation being preserved as much as possible, or equivalently,
such that the $n$-D distances are approximated by 2-D distances with a minimal error.}\\

\noindent
In an actual GA implementation of Sammon Mapping, chromosomes might be
made up of $n$ genes each of which corrisonds to $x-y$ coordinate of
a candidate solution of $n$ optimally distributed points in 2-dimensional space.
Uniform crossover is employed and from time to time mutation is given
by replacing one gene with other random $x-y$ coordinate. See the Figure~2.
See also the Figure bellow.

\begin{figure}[htbp]
 \begin{center}
   \includegraphics[width=14cm,height=5cm]{summon-2.eps}
   \caption{A chromosome representation and uniform crossover}
 \end{center}
\end{figure}

\noindent
Examples in $49^2=2401$ dimensional space:
\begin{figure}[htbp]
 \begin{center}
%%   \includegraphics[]{line-point.eps,width=5.2cm,height=5.2cm}
   \includegraphics[width=5.2cm,height=4.6cm]{block-point.eps}
   \includegraphics[width=5.2cm,height=4.6cm]{sphere-two.eps}
   \includegraphics[width=5.2cm,height=4.6cm]{sphere-one-small.eps}
   \includegraphics[width=5.2cm,height=4.6cm]{hopfield-point-10-new.eps}
   \includegraphics[width=5.2cm,height=4.6cm]{hopfield-point-90.eps}
   \includegraphics[width=5.2cm,height=4.6cm]{ep-01.eps}
\caption{Six Examples of Mapping from 2401-dimensional space to the 2-dimensional space.
Further explanations are shown in the text.}
 \end{center}
\end{figure}



\clearpage
\section{Multi Modal Genetic Algorithms\\
-- When we have multipul 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}
   \includegraphics[width=7.5cm,height=6cm]{test-for-share.eps}
   \includegraphics[width=7.5cm,height=6cm]{test-for-share-2.eps}
\caption{A multi-peak 2-D function and its variation}
 \end{center}
\end{figure}


\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}
   \includegraphics[width=9cm,height=6cm]{sharing.eps}
   \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.
}\\


\noindent
Hopefully the following two figures would help you understand why.

\begin{figure}[h] \label{fig:shareing}
 \begin{center}
   \includegraphics[width=7cm,height=2cm]{crowding-1.eps}
   \includegraphics[width=7cm,height=2cm]{crowding-2.eps}
   \caption{Two cases of parents-children's distance relation.}
 \end{center}
\end{figure}


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


\clearpage
\section{Multi Objective Genetic Algorithm (MOGA)}
\noindent
So far we have learned how to get the possible solution(s) 
which fulfills one objective function for the problem, that is,
the goal is maximize the fitness function. 
In real world problem, however,  we have usually 
multiple objectives or criteria to be fulfilled simultaneously.\\

\noindent
Those objectives sometimes conflict with each other.
Like ``time'' and ``money'': The more we want to earn money, the less time to spent the money; 
or ``reliability'' of the product and ``cost'' to produce it in a manufactural factory. 
Or, suppose an Opera Company trys to employ one Soprano singer.
The criteria is voice, beauty-or-not), slim-or-not, language-capability (Italian, German, etc).
However God tend not to give us two talents at a time, alas.\\

\noindent
Then, first of all, when we have multiple objective function, we must define
an important concept of parate optimal or equvalently non-dominated solution.\\

\bigskip
\noindent
{\bf Definition (Parate Optimal or Non-dominated Solution)}
{\it A candidate solution is called a non-dominated iff there is no ohter better 
solution w.r.t. all the objectives.}\\

\hspace*{1in}\\

\noindent
To be more specific, assume we have $n$ objective functions;
\begin{displaymath}
f_1(\mbox{\bf x}), f_2(\mbox{\bf x}), f_3(\mbox{\bf x}), \cdots f_n(\mbox{\bf x})
\end{displaymath}

\noindent
where {\bf x} is a candidate solution. Now if a new candidate solution {\bf y}
improves all the objetives for {\bf x}, i.e.,
\begin{displaymath}
f_i(\mbox{\bf y}) > f_i(\mbox{\bf x})\hspace{.05in} \mbox{for} \hspace{.05in} \forall i 
\end{displaymath}

\noindent
we say 

\begin{center} {\it ``{\bf y} dominate {\bf x}.}'' \end{center}

\noindent
When no such {\bf y} exists, we say

\begin{center} ``{\it {\bf x} is non-dominated}'' or ``{\it Parete Optimum.}'' \end{center}

\hspace*{1in}\\

\noindent
{\bf A toy example}:  We now assume the two objective functions as follows.
\begin{eqnarray}
\nonumber
\left\{
\begin{array}{l}
f_1(x) = x^2 \\
f_2(x) = (x-2)^2 
\end{array}
\right.
\end{eqnarray}

\begin{itemize}
\item[$\cdot$] x=0 is optimum w.r.t. $f_1$ but not so good w.r.t. $f_2$.
\item[$\cdot$] x=2 is optimum w.r.t. $f_2$ but not so good w.r.t. $f_1$.
\item[$\cdot$] Any other point in between is a compromise or trade-off 
               and is a Pareto-optimum.
\item[$\cdot$] But the solution x=3, e.g., is not a Pareto-optimum 
               since this point is not better than the solution $x=2$ w.r.t. either objective.
\item[$\cdot$] If we plot in the $f_1$-$f_2$ space, 
an increase in $f_1$ in some reagion means a decrease in $f_2$, or vice versa which
implys that the solutions in the region are Parete optimum, while in other region
an increase in $f_1$ make $f_2$ increas (decrease). See Figure~\ref{parete}.
This  $f_1$-$f_2$ space is called a {\it Trade-off Space}.
\end{itemize}


\noindent
We now take a look at a typical implemetation of MOGA.

\hspace*{1in}\\

\noindent
{\bf Algorithm (A Multi Objective GA)}
{\it
\begin{itemize}
\setlength{\itemsep}{0pt}
\item[1.]Initialize the population.
\item[2.]Select individuals uniformly from population.
\item[3.]Perform crossover and mutation to create a child.
\item[4.]Calculate the rank of the new child.
\item[5.]Find the individual in the entire population that is most similar to the
child. Replace that individual with the new child if the child's ranking is
better, or if the child dominates it. \footnote{\noindent Step 5 implies that 
the new child is only inserted into the population if it
dominates the most similar individual, or if it has a lower ranking, i.e. a lower 
degree of dominance. 

The restricted replacement
strategy also constitutes an extreme form of elitism, as the only way of replacing a
non-dominated individual is to create a child that dominates it.

The similarity of two individuals is measured using a distance function.
}

\item[6.]Update the ranking of the population if the child has been inserted.
\item[7.]Perform steps 2-6 according to the population size.
\item[8.]If the stop criterion is not met go to step 2 and start a new generation.
\end{itemize}
}



\begin{excersize}[Parate Optimal Solutions]\hspace{1in}\\
Try the algorithm above with two objective functions $y=(x-2)^2$ and 
$y=(x-4)^2$. Then show the possibly parate optimum solutions you found. 
\end{excersize}


\clearpage
\section{Evolving both structure and weight of Neural Network}
We have such an algorithm called NeuroEvolution of Augmenting Topologies (NEAT)\footnote{K.~O.~Stanley and R. Miikkulainen (2002) ``Evolving Neural Networks through Augmenting Topologies.'' Evolutionary Computation, Vol. 10, pp. 99-127.}
We now summerise the method by paraphrasing the original paper by Stanley and Mikikkulainen (2002).\\

\noindent
Each gene is made up of (1) inovation number (2) connection from which neuron (3) to which neuron and enable (ON) or disable (OFF).

A population of chromosomes are created at random initially. When created this first generation, genes of  each chromosome is assigned an integer from left to right as 1, 2, 3, .... This is called \it{'inovation number'} for some reason. Then selecting two parents according to fitness value; 
give mutation with a small probability, and crossover these two parents, which produce one child. By repeating this procedure, the next generation is created. \\

\noindent
Now let's see how we mutate and how we crossover.

\subsection{mutation}
\noindent
We have two different mutations. From one gene to the next, mutate or not mutate are determined at random with a low probability. If to be mutated, which of the followin two is used also at random.

\begin{itemize}
\item Add connection mutation
   \begin{itemize}
   \item A single new connection gene with a random weight is added connecting 
         two previously unconnected neurons.
   \end{itemize}
\item Add neuron mutation
   \begin{itemize}
   \item An existing connection is split and the new neuron placed where the old connection used 
         to be. 
   \item The old connection is disabled and two new connections are added to the chromosome.
   \item The new connection leading into the new neuron receives a weight of 1, 
         and the new connection leading out receives the same weight as the old connection.
   \end{itemize}
\end{itemize}

\begin{figure}[h]
 \begin{center}
   \includegraphics[width=14cm,height=9cm]{stanley-mutation.eps}
\caption{Two types of mutation in NEAT. (Re-drawed the figure in Stanley et al.)}
 \end{center}
\end{figure}

\noindent
In the future, whenever
these chromosomes mate, the offspring will inherit the same innovation numbers on
each gene; innovation numbers are never changed. Thus, the historical origin of every
gene in the system is known throughout evolution.



\subsection{crossover}
the genes in both chromosomes with the same innovation numbers are lined up. These genes
are called matching genes. Genes that do not match are either disjoint or excess, depending
on whether they occur within or outside the range of the other parent�fs innovation
numbers.\\

\noindent
the genes in both chromosomes with the same innovation numbers are lined up. These genes
are called matching genes. Genes that do not match are either disjoint or excess, depending
on whether they occur within or outside the range of the other parent�fs innovation
numbers.


\begin{figure}[h]
 \begin{center}
   \includegraphics[width=14cm,height=12cm]{stanley-xover.eps}
\caption{A crossover in NEAT. (Re-drawed the figure in Stanley et al.)}
 \end{center}
\end{figure}


\begin{excersize}[Evolving structure of NN]\hspace{1in}\\
To make it simple, fitness is the number of gene.
\end{excersize}

\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}
   \includegraphics[width=12cm,height=3cm]{patterns.eps}
   \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}
   \includegraphics[width=7cm,height=4cm]{membership-function.eps,}
   \includegraphics[width=7cm,height=4cm]{membership-function-.eps}
   \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}






\begin{table}[h]
\begin{center}
\begin{tabular}{c c c c c c c c c c c c c c c}%%\hline \hline 
\bigskip
\hspace*{.1pt} & A & B & C & D & E & F & G & H & I & J & K & L & M & N \\ 
A              & 0 & 3 & 1 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\
B              & - & 0 & 1 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\
C              & - & - & 0 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\
D              & - & - & - & 0 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\
E              & - & - & - & - & 0 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\
F              & - & - & - & - & - & 0 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\
G              & - & - & - & - & - & - & 0 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\
H              & - & - & - & - & - & - & - & 0 & 4 & 4 & 4 & 4 & 4 & 4 \\
I              & - & - & - & - & - & - & - & - & 0 & 4 & 4 & 4 & 4 & 4 \\
J              & - & - & - & - & - & - & - & - & - & 0 & 4 & 4 & 4 & 4 \\
K              & - & - & - & - & - & - & - & - & - & - & 0 & 4 & 4 & 4 \\
L              & - & - & - & - & - & - & - & - & - & - & - & 0 & 4 & 4 \\
M              & - & - & - & - & - & - & - & - & - & - & - & - & 0 & 4 \\
N              & - & - & - & - & - & - & - & - & - & - & - & - & - & 0 \\
%%\hline \hline
\end{tabular} 
\end{center}
\end{table}


\begin{figure}[hbtp]
 \begin{center}
\includegraphics[width=12cm,height=4cm}{tsp.eps}
 \end{center}
\caption{An example of 14 cities and a possible tour therein.}
\end{figure}



