%% LyX 1.3 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass{article}
\usepackage[]{fontenc}
\usepackage{float}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\providecommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\@}
%% Bold symbol macro for standard LaTeX users
\newcommand{\boldsymbol}[1]{\mbox{\boldmath $#1$}}

%% Because html converters don't know tabularnewline
\providecommand{\tabularnewline}{\\}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
 \newenvironment{lyxcode}
   {\begin{list}{}{
    \setlength{\rightmargin}{\leftmargin}
     \setlength{\listparindent}{0pt}% needed for AMS classes
     \raggedright
     \setlength{\itemsep}{0pt}
    \setlength{\parsep}{0pt}
     \normalfont\ttfamily}%
    \item[]}
   {\end{list}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\def\figurename{Example}

\makeatother
\begin{document}

\title{GenAnneal: Genetically modified Simulated Annealing}
\author{Ioannis G. Tsoulos$^{1}$, Isaac E. Lagaris$^{2}$\footnote{
	Permanent address: 
	Department of Computer Science, University of Ioannina, 
	P.O. Box 1186, Ioannina 45110 - GREECE. E-mail: lagaris@cs.uoi.gr
}} 
\date{
	$^{1}$Department of Computer Science, University of Ioannina, 
	      P.O. Box 1186, Ioannina 45110 - GREECE
	      \\
        $^{2}$Physics Department, University of South Africa (UNISA), Pretoria RSA.
}
\maketitle
\begin{abstract}
A modification of the standard Simulated Annealing (SA) algorithm
is presented for finding the global minimum of a continuous multidimensional,
multimodal function. We report results of computational experiments
with a set of test functions and we compare to methods of similar
structure. The accompanying software accepts objective functions coded
both in Fortran 77 and C++.
\end{abstract}
\textbf{PACS}: 02.60.-x ; 02.60.Pn ; 07.05.Kf;  02.70.Lq; 07.05.Mh 
\\
\textbf{Keywords}: Global optimization, genetic programming, grammatical evolution, simulated annealing.


\section*{PROGRAM SUMMARY }

\textit{Title of program}: GenAnneal

\begin{flushleft}\textit{Catalogue identifier}:\end{flushleft}

\begin{flushleft}\textit{Program available from}: CPC Program Library,
Queen's University of Belfast, N. Ireland.\end{flushleft}

\begin{flushleft}\textit{Computer for which the program is designed
and others on which it has been tested}: The tool is designed to be
portable in all systems running the GNU C++ compiler. \end{flushleft}
\begin{flushleft}\emph{Installation}: University of Ioannina, Greece
on Linux based machines.\end{flushleft}
\begin{flushleft}\textit{Programming language used}: GNU-C++, GNU-C,
GNU Fortran - 77.\end{flushleft}
\begin{flushleft}\emph{Memory required to execute with typical data}:
200KB.\end{flushleft}
\begin{flushleft}\textit{No. of bits in a word}: 32\end{flushleft}
\begin{flushleft}\emph{No. of processors used}: 1\end{flushleft}
\begin{flushleft}\emph{Has the code been vectorised or parallelized?}:
No.\end{flushleft}
\begin{flushleft}\emph{No. of bytes in distributed program,including
test data etc}.: 100 Kbytes.\end{flushleft}
\begin{flushleft}\emph{Distribution format}: gzipped tar file.\end{flushleft}
\begin{flushleft}\emph{Keywords}: Global optimization, stochastic
methods, genetic programming, grammatical evolution.\end{flushleft}
\begin{flushleft}\emph{Nature of physical problem}: \textbf{}A multitude
of problems in science and engineering are often reduced to minimizing
a function of many variables. There are instances that a local optimum
does not correspond to the desired physical solution and hence the
search for a better solution is required. Local optimization techniques
are frequently trapped in local minima. Global optimization is hence
the appropriate tool. For example, solving a non - linear system of
equations via optimization, employing a {}``least squares'' type
of objective, one may encounter many local minima that do not correspond
to solutions. ( i.e. they are far from zero).\end{flushleft}
\begin{flushleft}\emph{Typical running time}: Depending on the objective
function.\end{flushleft}
\begin{flushleft}\emph{Method of solution}: 
We modified the process of step selection that the traditional Simulated 
Annealing employs and instead we used a global technique based on grammatical
evolution.
\end{flushleft}
\section*{LONG WRITE UP}
\section{Introduction }
In this article we deal with a modification of the Simulated Annealing
(SA) algorithm \cite{key-1,key-2,key-3,key-5} that results in a performance
enhancement. We first give a brief description of the standard SA
method for locating a global minimum of a continuous, differentiable
function $f$ with many variables inside a bounded domain $S\subset R^{n}$.
SA is based on an analogy with the physical phenomenon of annealing.
In a liquid the molecules move almost freely when the temperature
is high. If the temperature is lowered gradually and slowly enough,
then the system crystallizes into a state of minimum energy. If the
temperature is lowered quickly , ( this is called quenching ) the
system settles into a state of higher energy. A typical description
of SA algorithm is as follows:

\begin{enumerate}
\item Initially \textbf{Set} $k=0,\ \  T_{0}>0$. Sample $x_{0}\in S$.
\item \textbf{Sample} a point $y\in S$ .
\item \textbf{Set} $x_{k+1}=x_{k}$.
\item \textbf{Reset} $x_{k+1}=y$, with probability $\min\left\{ 1,\exp\left(-\frac{f(y)-f\left(x_{k}\right)}{T_{k}}\right)\right\} $
\item \textbf{Set} $k=k+1$
\item \textbf{Lower} the temperature $T_{k}$ using an annealing schedule.
\item \textbf{Goto} step 2.
\end{enumerate}
When the temperature $T_{k}$ is high, the method performs a global
exploration; however, when the temperature $T_{k}$ tends to 0, the
behavior of the algorithm closely resembles that of a local search.
The new method proposes a modification in step 2 and samples a new
point utilizing the GRS technique \cite{key-7}. The GRS method produces
steps by employing genetic programming and more specifically grammatical
evolution \cite{key-8,key-9,key-10}, and it is briefly reviewed in
subsection \ref{sub:The-GRS-procedure}.

The rest of this article is organized as follows: in section \ref{sec:Description}
the proposed algorithm is presented in detail. In section \ref{sec:Experimental-results}
some experimental results from the application of the proposed method
are listed and a comparison is made against traditional simulated
annealing methods and in section \ref{sec:Software-documentation}
the installation and the execution procedures of the GenAnneal are
presented.


\section{Description of the algorithm \label{sec:Description}}


\subsection{The GRS procedure\label{sub:The-GRS-procedure}}

The main steps of the GRS procedure are the following:

\begin{description}
\item [INPUT]Data:
\end{description}
\begin{itemize}
\item A point $x=\left(x_{1},x_{2},\ldots,x_{n}\right),\  x\in S\subset R^{n}$.
\item $\epsilon$, a small positive number. Typical values for this parameter
are $10^{-4}$ to $10^{-5}$. 
\item \textbf{Set} $k$ as the maximum number of allowed generations.
\item \textbf{Set} selection rate and mutation rate.
\end{itemize}
\begin{description}
\item [INITIALIZATION]step:
\end{description}
\begin{itemize}
\item The initialization of each element of the genetic population is performed
by selecting a random integer in the range {[}0,255{]}.
\end{itemize}
\begin{description}
\item [LOOP]Step:
\end{description}
\begin{itemize}
\item \textbf{For} $i=1,...,k$ \textbf{Do}

\begin{itemize}
\item \textbf{Set} $x_{\mbox{old}}=x$.
\item \textbf{Create} a new generation of chromosomes in the population
with the use of the genetic operations (crossover, mutation, reproduction). 
\item \textbf{Set} y=f(x).
\item \textbf{For} every chromosome \textbf{Do}

\begin{itemize}
\item \textbf{Split} the chromosome uniformly into $n$ parts $\left(p_{i},\  i=1,\ldots,n\right)$,
one for each dimension. On every piece $p_{i}$ the grammatical evolution
transformation is applied to generate a  univariate function $f_{i}$. 
\item \textbf{Denote} by $d$ the vector $\left(d_{1}=f_{1}\left(x_{1}\right),d_{2}=f_{2}\left(x_{2}\right),...,d_{n}=f_{n}\left(x_{n}\right)\right)$.
\item \textbf{Set} $x_{+}=x+d$.
\item \textbf{If} $x_{+}\notin S$ or $f\left(x_{+}\right)>y$ \textbf{then}

\begin{itemize}
\item \textbf{Set} $x_{-}=x-d$.
\item \textbf{If} $x_{-}\ \notin S$ or $f\left(x_{-}\right)>y$ , \textbf{then}
\end{itemize}
\textbf{$\quad\quad$Set} the fitness value to a very large number.

\begin{itemize}
\item \textbf{Else}
\end{itemize}
\textbf{$\quad\quad$Set} the fitness value to $f\left(x_{-}\right)$.

\begin{itemize}
\item \textbf{Endif}
\end{itemize}
\item \textbf{Else}

\begin{itemize}
\item \textbf{Set} the fitness value to $f\left(x_{+}\right)$.
\end{itemize}
\item \textbf{Endif}
\end{itemize}
\item \textbf{Endfor}
\item \textbf{Set} $x=x+d_{\mbox{best}}$, where $d_{\mbox{best}}$ the
movement that corresponds to the chromosome with the best fitness
value.
\item \textbf{If} $\left|x-x_{\mbox{old}}\right|\le\epsilon$, terminate
and \textbf{return} $x$ as the located minimizer.
\end{itemize}
\item \textbf{Endfor}
\item \textbf{Return} $x$ as the located minimizer.
\end{itemize}

\subsection{The proposed algorithm}

The steps of the proposed algorithm are presented below:

\begin{description}
\item [Initialization\_Step]~
\end{description}
\begin{itemize}
\item \textbf{Set} values for the parameters TLAST, T and $\epsilon$. The
parameters TLAST and $\epsilon$ control the termination of the algorithm.
The algorithm terminates when either the best value was not changed
in the last TLAST iterations, or the temperature T has dropped below
$\epsilon$.
\item \textbf{Set} the value of the temperature reduction factor $a\in(0,1)$.
\item \textbf{Sample} uniformly a point $x\ \in S$.
\item \textbf{Set} $f_{c}=f(x)$, $x_{\mbox{best}}=x$, $f_{\mbox{best}}=f_{c}$.
\end{itemize}
\begin{description}
\item [Main\_step]~
\end{description}
\begin{itemize}
\item \textbf{Start} the GRS procedure from point $x$ and denote by $\tilde{x}$
the resulting point.
\item \textbf{If} $f\left(\tilde{x}\right)<f_{c}$ \textbf{then}

\begin{itemize}
\item \textbf{Set} $x=\tilde{x}$, $f_{c}=f\left(\tilde{x}\right)$
\item \textbf{If} $f_{c}<f_{\mbox{best}}$ \textbf{then}

\begin{itemize}
\item \textbf{Set} $x_{\mbox{best}}=x$, $f_{\mbox{best}}=f_{c}$
\end{itemize}
\item \textbf{EndIf}
\end{itemize}
\item \textbf{Else}

\begin{itemize}
\item \textbf{If} $e^{\frac{f\left(\tilde{x}\right)-f_{c}}{T}}>\xi$, where
$\xi$ a random number in the range (0,1) \textbf{then}

\begin{itemize}
\item \textbf{Set} $x=\tilde{x}$\textbf{,} $f_{c}=f\left(\tilde{x}\right)$
\end{itemize}
\item \textbf{EndIf}
\end{itemize}
\item \textbf{EndIf}
\end{itemize}
\begin{description}
\item [Update\_Step]~
\end{description}
\begin{itemize}
\item \textbf{Update} the temperature T according to the scheme $T=aT$.
\item \textbf{If} there was no improvement during the last $\mbox{TLAST}$
iterations or \textbf{if} the temperature T has dropped below $\epsilon$,
\textbf{go to} \textbf{Main\_Step else goto} \textbf{Optimization\_Step}.
\end{itemize}
\begin{description}
\item [Optimization\_Step:]~
\end{description}
\begin{itemize}
\item Start a local search at $x$ and let the resulting point be defined
by $x^{*}$.
\item \textbf{Return} $x^{*}$.
\end{itemize}

\section{Experimental results\label{sec:Experimental-results}}
The suggested approach was compared against two publicly available
variants of Simulated Annealing: The method of Corana \cite{key-3}
(labeled SA in Table \ref{cap:Experimental-results} ) and the Adaptive
Simulated Annealing of Ingber \cite{key-5} ( labeled ASA in Table
\ref{cap:Experimental-results} ) . The comparison is performed on
a suite of test problems listed in Appendix A. Each method was run
50 times on every problem using different random seeds each time.
We have measured the percentage of times the global minimum was found
and the number of function evaluations it required. The parameters
for the proposed method are listed in table \ref{cap:GenAnneal-parameters}.
Both for SA and ASA we used the default parameters as suggested in
the provided software packages available from the sites http://www.netlib.org
and http://www.ingber.com respectively. The trial steps produced by
the grammatical evolution were evaluated using the FunctionParser
programming library \cite{key-6}. The local search procedure used
in all methods was a BFGS implementation due to Powell \cite{key-11}.
In table \ref{cap:Experimental-results} we list the results for SA,
ASA and the proposed method (GSA). Numbers in the cells represent
the average number of function evaluations required by each method.
The figures in parentheses denote the fraction of runs during which
the global minimum was discovered. Absence of this number denotes
that the global minimum was recovered in every single run. 
From the reported results one can easily deduce the superiority of
the new method as far as the above benchmarks are concerned. Hence,
we recommend its use for solving difficult practical problems.
%
\begin{table}[H]

\caption{Average number of function evaluations for SA, ASA and GSA.\label{cap:Experimental-results}}

\begin{center}\begin{tabular}{|c|c||c||c|}
\hline 
FUNCTION&
SA&
ASA&
GSA\tabularnewline
\hline
\hline 
CAMEL&
4820&
3125&
1791\tabularnewline
\hline 
RASTRIGIN&
4843&
3534&
488\tabularnewline
\hline 
GRIEWANK2&
4832(0.27)&
3271(0.43)&
580\tabularnewline
\hline 
GKLS(2,50)&
4820&
3354&
1641\tabularnewline
\hline 
GKLS(3,50)&
7228&
5269(0.17)&
2004\tabularnewline
\hline 
GOLDSTEIN&
4842&
3385(0.93)&
1281\tabularnewline
\hline 
TEST2N(4)&
9631&
6460&
2923\tabularnewline
\hline 
TEST2N(5)&
12034(0.87)&
10763&
3456\tabularnewline
\hline 
TEST2N(6)&
14438(0.66)&
18466&
3633\tabularnewline
\hline 
TEST2N(7)&
16840(0.37)&
29972&
3840\tabularnewline
\hline 
TEST30N(3)&
7930(0.23)&
3220&
1425\tabularnewline
\hline 
TEST30N(4)&
9858(0.23)&
6002&
1001\tabularnewline
\hline 
POTENTIAL(3)&
21404&
50202&
3075\tabularnewline
\hline 
POTENTIAL(5)&
36212&
80527&
2770\tabularnewline
\hline 
NEURAL&
76667(0.93)&
67167&
6241(0.93)\tabularnewline
\hline
\end{tabular}\end{center}
\end{table}
%
\begin{table}

\caption{GenAnneal parameters\label{cap:GenAnneal-parameters}}

\begin{center}\begin{tabular}{|c|c|}
\hline 
PARAMETER&
VALUE\tabularnewline
\hline
\hline 
SELECTION RATE&
90\%\tabularnewline
\hline 
MUTATION RATE&
5\%\tabularnewline
\hline 
CHROMOSOME COUNT&
100\tabularnewline
\hline 
CHROMOSOME LENGTH&
$10\times\mbox{problem dimensionality}$\tabularnewline
\hline 
$\epsilon$&
$10^{-5}$\tabularnewline
\hline 
TLAST&
4\tabularnewline
\hline
\end{tabular}\end{center}
\end{table}



\section{Software documentation\label{sec:Software-documentation}}
\subsection{Distribution }
The package is distributed in a tar.gz file named \texttt{GenAnneal.tar.gz}
and under UNIX systems the user must issue the following commands
to extract the associated files:

\begin{enumerate}
\item gunzip \texttt{GenAnneal.tar.gz}
\item tar xfv \texttt{GenAnneal.tar}
\end{enumerate}
These steps create a directory named \texttt{GenAnneal} with the following
contents:

\begin{enumerate}
\item \textbf{bin}: A directory which is initially empty. After compilation
of the package, it will contain the executable \textbf{make\_genanneal}
\item \textbf{examples}: A directory that contains the test functions used
in this article, written in ANSI C++.
\item \textbf{include}: A directory which contains the header files for
all the classes of the package.
\item \textbf{src}: A directory containing the source files of the package.
\item \textbf{Makefile}: The input file to the \texttt{make} utility in
order to build the tool. Usually, the user does not need to change
this file.
\item \textbf{Makefile.inc}: The file that contains some configuration parameters,
such as the name of the C++ compiler etc. The user must edit and change
this file before installation.
\end{enumerate}

\subsection{Installation }

The following steps are required in order to build the tool:

\begin{enumerate}
\item Uncompress the tool as described in the previous section.
\item \texttt{cd GenAnneal.}
\item Edit the file \texttt{Makefile.inc} and change (if needed) the five
configuration parameters.
\item Type \texttt{make}.
\end{enumerate}
The five parameters in \texttt{Makefile.inc} are the following:

\begin{enumerate}
\item \textbf{CXX}: It is the most important parameter. It specifies the
name of the C++ compiler. In most systems running the GNU C++ compiler
this parameter must be set to g++.
\item \textbf{CC}: If the user written programs are in C, set this parameter
to the name of the C compiler. Usually, for the GNU compiler suite,
this parameter is set to gcc.
\item \textbf{F77}: If the user written programs are in Fortran 77, set
this parameter to the name of the Fortran 77 compiler. For the GNU
compiler suite a usual value for this parameter is g77.
\item \textbf{F77FLAGS}: The compiler GNU FORTRAN 77 (g77) appends an underscore
to the name of all subroutines and functions after the compilation
of a Fortran source file. In order to prevent this from happening
we can pass some flags to the compiler. Normally, this parameter must
be set to -fno-underscoring. 
\item \textbf{ROOTDIR}: Is the location of the GenAnneal directory. It is
critical for the system that this parameter is set correctly. In most
systems, it is the only parameter which must be changed.
\end{enumerate}

\subsection{User written subprograms }

The user can write his objective function either in C, C++ or in Fortran77
in a single file. Each file has a series of functions in an arbitrary
order. However, the C++ files must have the lines 

\begin{lyxcode}
~extern~$"\mbox{C}"$~\{
\end{lyxcode}
before the functions and the line 

\begin{lyxcode}
\}
\end{lyxcode}
after them. The meaning of the functions are the following:

\begin{enumerate}
\item \textbf{getdimension}(): It is an integer function which returns the
dimension of the objective function.
\item \textbf{getleftmargin}(left): It is a subroutine (or a void function
in C) which fills the double precision array left with the left margins
of the objective function. 
\item \textbf{getrightmargin}(right): Is is a subrourine ( or a void function
in C) which fills the double precision array right with the right
margins of the objective function.
\item \textbf{funmin}(x): It is a double precision function which returns
the value of the objective function evaluated at point x.
\item \textbf{granal}(x,g): It is a subroutine (or a void function in C)
which returns in a double precision array g the gradient of the objective
function at point x.
\end{enumerate}

\subsection{The utility make\_genanneal}

After the compilation of the package, the executable \texttt{make\_genanneal}
will be placed in the subdirectory \texttt{bin} in the distribution
directory. This program creates the final executable and it takes
the following command line parameters:

\begin{enumerate}
\item \texttt{-h}: Prints a help screen and terminates.
\item \texttt{-p} \textbf{filename}: The \textbf{filename} parameter specifies
the name of the file containing the objective function. The utility
checks the suffix of the file and it uses the appropriate compiler.
If this suffix is .cc or .c++ or .CC or .cpp, then it invokes the
C++ compiler. If the suffix is .f or .F or .for then it invokes the
Fortran 77 compiler. Finally, if the suffix is .c it invokes the C
compiler.
\item \texttt{-o} \textbf{filename}: The \textbf{filename} parameter specifies
the name of the final executable. The default value for this parameter
is GenAnneal..
\end{enumerate}

\subsection{The utility GenAnneal}

The final executable \texttt{GenAnneal} has the following command
line parameters:

\begin{enumerate}
\item \texttt{-h}:The program prints a help and it terminates.
\item \texttt{-c} \texttt{\textbf{count}}: The integer parameter \texttt{\textbf{count}}
specifies the number of chromosomes for the Genetic Random Search
procedure. The default value for this parameter is 20.
\item \texttt{-s} \texttt{\textbf{srate}}: The double parameter \texttt{\textbf{srate}}
specifies the selection rate used in the Genetic Random Search procedure.
The default value for this parameter is 0.10 (10\%).
\item \texttt{-m} \texttt{\textbf{mrate}}: The double parameter \texttt{\textbf{mrate}}
specifies the mutation rate used in the Genetic Random Search procedure.
The default value for this parameter is 0.05 (5\%).
\item \texttt{-r} \texttt{\textbf{seed}}: The integer parameter \texttt{\textbf{seed}}
specifies the seed for the random number generator. It can assume
any integer value.
\item \texttt{-o} \texttt{\textbf{filename}}: The parameter \texttt{\textbf{filename}}
specifies the file where the output from the GenAnneal will be placed.
The default value for this parameter is the standard output.
\end{enumerate}

\subsection{A working example}

Consider the Rastrigin function given by\[
f(x)=x_{1}^{2}+x_{2}^{2}-\cos\left(18x_{1}\right)-\cos\left(18x_{2}\right),\  x\in[-1,1]^{2}\]
 with 49 local minima. The implementation of this function in C++
and in Fortran77 is shown in examples \ref{cap:Codificationcpp} and
\ref{cap:codificationfortran}. Let the file with the C++ code be
named \texttt{rastrigin.cc} and that with the Fortran code \texttt{rastrigin.f.}
Let these files be located in the \texttt{examples} subdirectory.
Change to the \texttt{examples} subdirectory and create the GenAnneal
executable with the \texttt{make\_genanneal} command:

\begin{lyxcode}
../bin/make\_genanneal~-p~rastrigin.cc
\end{lyxcode}
or for the Fortran 77 version

\begin{lyxcode}
../bin/make\_genanneal~-p~~rastrigin.f
\end{lyxcode}
The \texttt{make\_genanneal} responds:

\begin{lyxcode}
RUN~./GenAnneal~IN~ORDER~TO~RUN~THE~PROBLEM~
\end{lyxcode}
Run GenAnneal \texttt{} by issuing the command:

\begin{lyxcode}
./GenAnneal~~-c~100~-r~1
\end{lyxcode}
The resulting output appears as:

\begin{lyxcode}
FUNCTION~EVALUATIONS~=~468

GRADIENT~EVALUATIONS~=~1

MINIMUM~=~~0.000000~~0.000000~~-2.000000
\end{lyxcode}

\section*{A. Test Functions}

The functions used for testing accompanied with the corresponding
parameter range and the global minimum are listed below. Further information
may be found in Floudas et al \cite{key-160} as well as in the URL:

\begin{lyxcode}
http://www.imm.dtu.dk/\textasciitilde{}km/GlobOpt/testex/testproblems.html.
\end{lyxcode}

\subsubsection*{Camel}

$f(x)=4x_{1}^{2}-2.1x_{1}^{4}+\frac{1}{3}x_{1}^{6}+x_{1}x_{2}-4x_{2}^{2}+4x_{2}^{4}$,
$x\in[-5,5]^{2}$ with 6 local minima and global minimum $f^{*}=-1.031628453$.


\subsubsection*{Rastrigin}

$f(x)=x_{1}^{2}+x_{2}^{2}-\cos(18x_{1})-\cos(18x_{2})$, $x\in[-1,1]^{2}$
with 49 local minima and global minimum $f^{*}=-2.0$.


\subsubsection*{Griewank2}

$f(x)=1+\frac{1}{200}\sum_{i=1}^{2}x_{i}^{2}-\prod_{i=1}^{2}\frac{\cos(x_{i})}{\sqrt{(i)}}$,
$x\in[-100,100]^{2}$ with 529 loca minima and global minimum $f^{*}=0.0$


\subsubsection*{Gkls}

$f(x)=\mbox{Gkls}(x,n,w)$, is a function with $w$ local minima,
described in \cite{key-12}, $x\in[-1,1]^{n},\  n\in[2,100]$. In
our experiments we use $n=2,3$ and $w=50$.


\subsubsection*{GoldStein \& Price }

\begin{eqnarray*}
f(x) & = & [1+(x_{1}+x_{2}+1)^{2}\\
 &  & (19-14x_{1}+3x_{1}^{2}-14x_{2}+6x_{1}x_{2}+3x_{2}^{2})]\times\\
 &  & [30+(2x_{1}-3x_{2})^{2}\\
 &  & (18-32x_{1}+12x_{1}^{2}+48x_{2}-36x_{1}x_{2}+27x_{2}^{2})]\end{eqnarray*}


The function has 4 local minima in the range $[-2,2]^{2}$ and global
minimum $f^{*}=3.0$.


\subsubsection*{Test2N }

\[
f(x)=\frac{1}{2}\sum_{i=1}^{n}x_{i}^{4}-16x_{i}^{2}+5x_{i}\]
with $x\in[-5,5]^{n}$. The function has $2^{n}$ local minima in
the specified range. In our experiments we used the cases of $n=4,5,6,7$.


\subsubsection*{Test30N}

\[
f(x)=\frac{1}{10}\sin^{2}\left(3\pi x_{1}\right)\sum_{i=2}^{n-1}\left(\left(x_{i}-1\right)^{2}\left(1+\sin^{2}\left(3\pi x_{i+1}\right)\right)\right)+\left(x_{n}-1\right)^{2}\left(1+\sin^{2}\left(2\pi x_{n}\right)\right)\]
with $x\in[-10,10]^{n}$. The function has $30^{n}$ local minima
in the specified range. In our experiments we used the cases of $n=3,4$.


\subsubsection*{Potential}

The molecular conformation corresponding to the global minimum of
the energy of $N$ atoms interacting via the Lennard-Jones potential
is determined for two cases: with $N=3$ atoms and with $N=5$ atoms.
We refer to the first case as \textbf{Potential(3)} (a problem with
9 variables) and to the second as \textbf{Potential(5)} (a problem
with 15 variables). The global minimum for the first cases is $f^{*}=3$
and $f^{*}=-9.103852416$


\subsubsection*{Neural}

A neural network (sigmoidal perceptron) with 10 hidden nodes (30 variables)
was used for the approximation of the function $g(x)=x\sin\left(x^{2}\right),\  x\in[-2,2]$.
The global minimum of the training error  is $f^{*}=0.0$


\section*{B. Examples}

%
\begin{figure}[H]

\caption{Implementation of Rastrigin function in C++.\label{cap:Codificationcpp}}

\textbf{\footnotesize extern} {\footnotesize {}``C''\{}{\footnotesize \par}

\textbf{\footnotesize $\;$int} {\footnotesize getdimension()}{\footnotesize \par}

{\footnotesize $\:$\{}{\footnotesize \par}

{\footnotesize $\quad$}\textbf{\footnotesize return} {\footnotesize 2;}{\footnotesize \par}

{\footnotesize $\:$\}}\\
{\footnotesize \par}

\textbf{\footnotesize $\:$void} {\footnotesize getleftmargin(}\textbf{\footnotesize double}
{\footnotesize {*}left)}{\footnotesize \par}

{\footnotesize $\:$\{}{\footnotesize \par}

{\footnotesize $\quad$left{[}0{]}=-1.0;}{\footnotesize \par}

{\footnotesize $\quad$left{[}1{]}=-1.0;}{\footnotesize \par}

{\footnotesize $\:$\}}\\
{\footnotesize \par}

\textbf{\footnotesize $\:$void} {\footnotesize getrightmargin(}\textbf{\footnotesize double}
{\footnotesize {*}right)}{\footnotesize \par}

{\footnotesize $\:$\{}{\footnotesize \par}

{\footnotesize $\quad$right{[}0{]}=1.0;}{\footnotesize \par}

{\footnotesize $\quad$right{[}1{]}=1.0;}{\footnotesize \par}

{\footnotesize $\:$\}}\\
{\footnotesize \par}

\textbf{\footnotesize $\:$double} {\footnotesize funmin(}\textbf{\footnotesize double}
{\footnotesize {*}x)}{\footnotesize \par}

{\footnotesize $\:$\{}{\footnotesize \par}

{\footnotesize $\quad$}\textbf{\footnotesize double} {\footnotesize x1=x{[}0{]},x2=x{[}1{]}; }{\footnotesize \par}

{\footnotesize $\quad$}\textbf{\footnotesize return} {\footnotesize x1{*}x1+x2{*}x2-cos(18.0{*}x1)-cos(18.0{*}x2);}{\footnotesize \par}

{\footnotesize $\:$\}}\\
{\footnotesize \par}

\textbf{\footnotesize $\:$void} {\footnotesize granal(}\textbf{\footnotesize double}
{\footnotesize {*}x,}\textbf{\footnotesize double} {\footnotesize {*}g)}{\footnotesize \par}

{\footnotesize $\:$\{}{\footnotesize \par}

{\footnotesize $\quad$}\textbf{\footnotesize double} {\footnotesize x1=x{[}0{]},x2=x{[}1{]}; }{\footnotesize \par}

{\footnotesize $\quad$g{[}0{]}=2.0{*}x1+18.0{*}sin(18.0{*}x1);}{\footnotesize \par}

{\footnotesize $\quad$g{[}1{]}=2.0{*}x2+18.0{*}sin(18.0{*}x2);}{\footnotesize \par}

{\footnotesize $\:$\}}{\footnotesize \par}

{\footnotesize \}}
\end{figure}
%
\begin{figure}[H]

\caption{Implementation of Rastrigin function in Fortran 77.\label{cap:codificationfortran}}

\textbf{\footnotesize integer function} {\footnotesize getdimension()}{\footnotesize \par}

{\footnotesize getdimension = 2}{\footnotesize \par}

\textbf{\footnotesize end}{\footnotesize }\\
{\footnotesize \par}

\textbf{\footnotesize subroutine} {\footnotesize getleftmargin(left)}{\footnotesize \par}

\textbf{\footnotesize double precision} {\footnotesize left(2)}{\footnotesize \par}

{\footnotesize left(1)=-1.0}{\footnotesize \par}

{\footnotesize left(2)=-1.0}{\footnotesize \par}

\textbf{\footnotesize end}{\footnotesize }\\
{\footnotesize \par}

\textbf{\footnotesize subroutine} {\footnotesize getrightmargin(right)}{\footnotesize \par}

\textbf{\footnotesize double precision} {\footnotesize right(2)}{\footnotesize \par}

{\footnotesize right(1)= 1.0}{\footnotesize \par}

{\footnotesize right(2)= 1.0}{\footnotesize \par}

\textbf{\footnotesize end}{\footnotesize }\\
{\footnotesize \par}

\textbf{\footnotesize double precision function} {\footnotesize funmin(x)}{\footnotesize \par}

\textbf{\footnotesize double precision} {\footnotesize x(2)}{\footnotesize \par}

\textbf{\footnotesize double precision} {\footnotesize x1,x2}{\footnotesize \par}

{\footnotesize x1=x(1)}{\footnotesize \par}

{\footnotesize x2=x(2)}{\footnotesize \par}

{\footnotesize funmin=x1{*}{*}2+x2{*}{*}2-cos(18.0{*}x1)-cos(18.0{*}x2)}{\footnotesize \par}

\textbf{\footnotesize end}{\footnotesize }\\
{\footnotesize \par}

\textbf{\footnotesize subroutine} {\footnotesize granal(x,g)}{\footnotesize \par}

\textbf{\footnotesize double precision} {\footnotesize x(2)}{\footnotesize \par}

\textbf{\footnotesize double precision} {\footnotesize g(2)}{\footnotesize \par}

\textbf{\footnotesize double precision} {\footnotesize x1,x2}{\footnotesize \par}

{\footnotesize x1=x(1)}{\footnotesize \par}

{\footnotesize x2=x(2)}{\footnotesize \par}

{\footnotesize g(1)=2.0{*}x1+18.0{*}sin(18.0{*}x1)}{\footnotesize \par}

{\footnotesize g(2)=2.0{*}x2+18.0{*}sin(18.0{*}x2)}{\footnotesize \par}

\textbf{\footnotesize end}
\end{figure}


\begin{thebibliography}{10}
\bibitem{key-1}Kirkpatrick S., Gelatt C. D. and Vecchi M. P., Optimization by simulated
annealing, Science \textbf{220}, 671-680 (4), 1983.
\bibitem{key-2}P. J. M. van Laarhoven and E. H. L. Aarts, {}``Simulated Annealing:
Theory and Applications'', 1987, D. Riedel, Boston.
\bibitem{key-3}Corana A., Marchesi M., Martini C. and Ridella S., Minimizing Multimodal
Functions of Continuous Variables with the {}``Simulated Annealing''
Algorithm, ACM Transactions on Mathematical Software, Vol. \textbf{13},
pp. 262-280, 1987.
\bibitem{key-5}Ingber L., Simulated Annealing: Practice versus theory, J. Math. Comput.
Modelling \textbf{18}, pp. 29-57,1983.
\bibitem{key-7}Tsoulos I.G. and Lagaris I.E., Genetically Controlled Random Search:
A global optimization method for continuous multidimensional functions,
to be appear on Computer Physics Communications.
\bibitem{key-8}M. O'Neill, Automatic Programming in an Arbitrary Language: Evolving
programs with grammatical evolution, PhD Thesis, University of Limerick,
Ireland, August 2001.
\bibitem{key-9}M. O'Neill and C. Ryan, Grammatical Evolution: Evolutionary Automatic
Programming in a Arbitrary Language, volume 4 of Genetic programming.
Kluwer Academic Publishers, 2003. 
\bibitem{key-10}M. O'Neill and C. Ryan, {}``Grammatical Evolution,'' IEEE Trans.
Evolutionary Computation, Vol. 5, pp. 349-358, 2001.
\bibitem{key-6}Nieminen J. and Yliluoma J., ``Function Parser for C++, v2.7'', available
from http://www.students.tut.fi/$\tilde{}$warp/FunctionParser/.
\bibitem{key-11}Powell M. J. D., {}``A Tolerant Algorithm for Linearly Constrained
Optimization Calculations'', Mathematical Programming 45 (1989),
547.
\bibitem{key-160}Floudas C. A. and Pardalos P.M., Adjiman C., Esposoto W., G$\ddot{\mbox{u}}$m$\ddot{\mbox{u}}$s
Z., Harding S., Klepeis J., Meyer C, Schweiger C., Handbook of Test
Problems in Local and Global Optimization, Kluwer Academic Publishers,
Dordrecht, 1999.
\bibitem{key-12}Gaviano M., Ksasov D. E., Lera D. and Sergeyev, Y. D. Software for
generation of classes of test functions with known local and global
minima for global optimization, ACM Trans. Math. Softw. \textbf{29},
pp. 469-480, 2003.
\end{thebibliography}
\begin{lyxcode}
\end{lyxcode}


\end{document}
