\chapter{TEST FUNCTIONS FOR OPTIMIZATION METHODS}       \label{Appendix:C}

%% ===================================================================================================================================================
%% ===================================================================================================================================================
%%   APPENDIX C
%% ===================================================================================================================================================
%% ===================================================================================================================================================

There is a suite of benchmark functions \cite{Shi1999a, Mendes2004} which are commonly used to critically test the performance of numeric optimization algorithms. These functions are chosen because of their particularities, which render their optimization difficult. These comprise
\begin{itemize}
\item Multi-modality
\item Deceptive gradient information
\item The curse of dimensionality
\end{itemize}

%% ===================================================================================================================================================
\section{Sphere/DeJong} \index{DeJong}
%% ===================================================================================================================================================
This function is very simple. Any algorithm capable of numeric optimization should solve it without any problem. Its simplicity helps to focus on the effects of dimensionality in optimization algorithms. It is unimodal, with its global minimum located at $x = \langle 0, \ldots, 0 \rangle$, with $f(x) = 0$. This function has no interaction between its variables and gradient information always points toward the global minimum.

\begin{tabular}{lcl}
Function        &   :   &   $f(\langle x\rangle) = \sum_{i=1}^n x_i^2$\\
Search Space    &   :   &   $\{\langle x_i \rangle | \forall i: -100 \leq x_i \leq +100\}$\\
Dimensionality  &   :   &   30\\
Minimum         &   :   &   0\\
Maximum         &   :   &   $3\cdot10^5$\\
Criterion       &   :   &   $f(x) \leq 0.01$\\
\end{tabular}

\begin{figure}[htbp]
  \centering
    \includegraphics[totalheight=2.2in]{Appendices/Figures/Sphere.pdf}
    \rule{35em}{0.5pt}
  \caption{Graph of \emph{Sphere} function in two dimensions}
  \label{fig:fcn1}
\end{figure}

%% ===================================================================================================================================================
\section{Rosenbrock}    \index{Rosenbrock}
%% ===================================================================================================================================================
Not all unimodal functions are simple to optimize. The fitness landscape is simple from afar but banana shaped when close to the minimum. Rosenbrock's variables are strongly dependent and gradient information often misleads algorithms. Its global minimum of $f(x) = 0$ is located at $x = \langle 1, \ldots, 1\rangle$.

\begin{tabular}{lcl}
Function        &   :   &   $f(\langle x\rangle) = \sum_{i=1}^{n-1} 100(x_{i+1}-x^2)^2+(x_i-1)^2$\\
Search Space    &   :   &   $\{\langle x_i \rangle | \forall i: -30 \leq x_i \leq +30\}$\\
Dimensionality  &   :   &   30\\
Minimum         &   :   &   0\\
Maximum         &   :   &   $2508237869$\\
Criterion       &   :   &   $f(x) \leq 100$\\
\end{tabular}

\begin{figure}[htbp]
  \centering
    \includegraphics[totalheight=2.2in]{Appendices/Figures/Rosenbrock1.pdf}
    \includegraphics[totalheight=2.2in]{Appendices/Figures/Rosenbrock2.pdf}
    \rule{35em}{0.5pt}
  \caption{Graph of \emph{Rosenbrock} function in two dimensions}
  \label{fig:fcn2}
\end{figure}

%% ===================================================================================================================================================
\section{Ackley}    \index{Ackley}
%% ===================================================================================================================================================
Ackley is a multi-modal function with many local optima. The global minimum is $f(x) = 0$, where $x = 0$. This function is difficult because optimization algorithms can easily be trapped in a local minimum on its way to the global minimizer.

\begin{tabular}{lcl}
Function        &   :   &   $f(\langle x\rangle) = 20+e-20e^{-0.2\sqrt{\frac{\sum_{i=1}^n x_i^2}{n}}}-e^{\frac{\sum_{i=1}^n\cos 2\pi x_i}{n}}$\\
Search Space    &   :   &   $\{\langle x_i \rangle | \forall i: -30 \leq x_i \leq +30\}$\\
Dimensionality  &   :   &   30\\
Minimum         &   :   &   0\\
Maximum         &   :   &   $22.35040$\\
Criterion       &   :   &   $f(x) \leq 0.01$\\
\end{tabular}

\begin{figure}[htbp]
  \centering
    \includegraphics[totalheight=2.2in]{Appendices/Figures/Ackley1.pdf}
    \includegraphics[totalheight=2.2in]{Appendices/Figures/Ackley2.pdf}
    \rule{35em}{0.5pt}
  \caption{Graph of \emph{Ackley} function in two dimensions}
  \label{fig:fcn3}
\end{figure}

%% ===================================================================================================================================================
\section{Rastrigin F1}  \index{Ratirigin F1}
%% ===================================================================================================================================================
A multi-modal version of the Spherical function, characterized by deep local minima arranged as sinusoidal bumps. The global minimum is $f(x) = 0$, where $x = 0$. An optimization algorithm can easily become trapped in a local minimum on its way to the global minimizer.

\begin{tabular}{lcl}
Function        &   :   &   $f(\langle x\rangle) = \sum_{i=1}^n x_i^2 - 10\cos 2\pi x_i+10$\\
Search Space    &   :   &   $\{\langle x_i \rangle | \forall i: -5.12 \leq x_i \leq +5.12\}$\\
Dimensionality  &   :   &   30\\
Minimum         &   :   &   0\\
Maximum         &   :   &   $1210.6$\\
Criterion       &   :   &   $f(x) \leq 100$\\
\end{tabular}

\begin{figure}[htbp]
  \centering
    \includegraphics[totalheight=2.2in]{Appendices/Figures/Rastrigin1.pdf}
    \includegraphics[totalheight=2.2in]{Appendices/Figures/Rastrigin2.pdf}
    \rule{35em}{0.5pt}
  \caption{Graph of \emph{Rastrigin} function in two dimensions}
  \label{fig:fcn4}
\end{figure}

%% ===================================================================================================================================================
\section{Griewank}  \index{Griewank}
%% ===================================================================================================================================================
This function is strongly multi-modal with significant interaction between its variables, caused by the product term. This function has the interesting property that the number of local minima increases with dimensionality. However, the influence of the product term also diminishes dramatically in these circumstances. In fact, it becomes negligible once the $n > 30$. The common benchmark used in the literature is when $n = 30$. The global minimum, $x = \langle 100, 100, . . . , 100\rangle$, yields a function value of $f(x) = 0$.

\begin{tabular}{lcl}
Function        &   :   &   $f(\langle x\rangle) = 1+\frac{\sum_{i=1}^n (x_i-100)^2}{4000}-\prod_{i=1}^n \cos \frac{x_i-100}{\sqrt{i}}$\\
Search Space    &   :   &   $\{\langle x_i \rangle | \forall i: -600 \leq x_i \leq +600\}$\\
Dimensionality  &   :   &   10 and 30\\
Minimum         &   :   &   0\\
Maximum         &   :   &   1666.839 and 3676.839\\
Criterion       &   :   &   $f(x) \leq 0.05$\\
\end{tabular}

\begin{figure}[htbp]
  \centering
    \includegraphics[totalheight=2.2in]{Appendices/Figures/Griewank1.pdf}
    \includegraphics[totalheight=2.2in]{Appendices/Figures/Griewank2.pdf}
    \rule{35em}{0.5pt}
  \caption{Graph of \emph{Griewank} function in two dimensions}
  \label{fig:fcn5}
\end{figure}

%% ===================================================================================================================================================
\section{Schaffer F6}   \index{Schaffer F6}
%% ===================================================================================================================================================
This is a very difficult function, especially devised to trick optimization algorithms with its many local optima arranged in concentric circles around the global optimum that is itself located in a narrow basin.

\begin{tabular}{lcl}
Function        &   :   &   $f(\langle x\rangle) = 0.5+\frac{\sin (\sqrt{x_1^2+x_2^2})^2 - 0.5}{(1+0.001(x_1^2+x_2^2))^2}$\\
Search Space    &   :   &   $\{\langle x_i \rangle | \forall i: -100 \leq x_i \leq +100\}$\\
Dimensionality  &   :   &   2\\
Minimum         &   :   &   0\\
Maximum         &   :   &   1\\
Criterion       &   :   &   $f(x) \leq 0.00001$\\
\end{tabular}

\begin{figure}[htbp]
  \centering
    \includegraphics[totalheight=2.2in]{Appendices/Figures/Schaffer1.pdf}
    \includegraphics[totalheight=2.2in]{Appendices/Figures/Schaffer2.pdf}
    \rule{35em}{0.5pt}
  \caption{Graph of \emph{Schaffer} function in two dimensions}
  \label{fig:fcn6}
\end{figure}

On the zoom of Fig.~\ref{fig:fcn6}, the inner contour line represents the area of points with values lower than the ones located in the outer belt of local optima. Only these values lead to the global best. Optimization algorithms are usually stuck on that belt and unable to converge on the global optimum whose fitness is zero. 


\vspace*{0.4in}
\begin{center}
* * * * *
\end{center}