\documentstyle[IEEEtran]{article}
\begin{document}
\tolerance 10000
\title{On Interval Factorial Genetic Algorithm in Global Optimization}

\author{Jarmo T. Alander}

\pagestyle{myheadings}

\markright{APIC'95, El Paso,
Extended Abstracts,
A Supplement to the international journal of {\rm Reliable
Computing}\ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ }

\maketitle

\begin{abstract}
In this work, we combine three promising global optimization methods:
\begin{itemize}
\item interval arithmetic methods,
\item  experimental design, and 
\item genetic algorithms, 
\end{itemize}into
a hybrid algorithm that seems to be superior to any of these single methods
in engineering applications where a good estimates of the global optimum of
multimodal function is required.
\begin{itemize}
\item Interval arithmetics gives us simple methods to estimate the range of
functions to be optimized.
\item Experimental design and 
factorial analysis helps to find the essential
parameter values while
\item Genetic algorithms adaptively guides the search.
\end{itemize}
It was not a great surprise that the results that we obtained using this new
hybrid method were superior to other similar methods.
The analysis now continues to reveal the power of the proposed hybrid
in real industrial applications.

{\bf Keywords:} experimental design, factorial analysis, genetic algorithms,
hybrid methods, interval arithmetics, global optimization, multimodal
optimization.
\end{abstract}
  
\auffil{The author is with 
Department of Computer Science and Production Economics,
University of Vaasa,
P. O. Box 700, FIN-65101 Vaasa, Finland.}

\newcommand{\ON}[1]{#1}
\newcommand{\OFF}[1]{}

\section{Introduction}
In this paper, we discuss the following simple type of global optimization
problem:
\[
	\min f(x)= f(x_1,x_2,\ldots,x_n)
\]
\[
	l_i \leq x_i \leq u_i, \ \ \ i=1,\ldots,n
\]
where $f:R_n \rightarrow R$. We denote by $\bf X$ the box
$$\{x=(x_1,\ldots,x_n)\,|\,l_i \leq x_i \leq u_i, i=1,\ldots,n\}.$$
There are many well-known local optimization methods that can be used
to solve this problem when the function $f$ is unimodal.
In the case when $f$ is multimodal, the situation is totally different,
and the problem can be extremely complex.
The book by Horst and Tuy \cite{opt:Horst90book} contains a good review
of the known global optimization methods.
\OFF{According to \cite{opt:Floudas93a} the deterministic global optimization
methods can be largely classified as
\begin{enumerate}
	\item Lipschitzian,
	\item branch-and-bound,
	\item cutting plane,
	\item difference of convex (DC) and reverse convex function,
	\item outer approximation,
	\item primal-dual,
	\item linearization, and
	\item interval methods.
\end{enumerate}
} %end OFF
\subsection{Interval arithmetics}
Interval arithmetic operations \cite{i:Moore66}
are defined for ordered pairs of
real numbers,\footnote{It is also possible to define interval
arithmetics on complex numbers. Then intervals are circles on the
complex plane \cite{i:Rokne82a,i:Rokne83a}.}
which represent closed intervals on the real line:

%\begin{example}
\[	
	A =  [a_1,a_2]= \{x \in R\,|\,a_1 \leq x \leq a_2\}.
\]
%\end{example}

The first element of the pair is the minimum value of the interval
often denoted by $\inf(A)$, while the second element is the maximum denoted by
$\sup(A)$ accordingly.
Real numbers $x$ can be identified with degenerate intervals $[x,x]$.

The interval arithmetic operators are usually defined as follows:
\[
	A + B  = [a_1,a_2] + [b_1,b_2] = [a_1+b_1,a_2+b_2],
\]
\[
	A  - B =  [a_1,a_2] - [b_1,b_2]  =  [a_1-b_2,a_2-b_1] ,
\]
$$A\cdot B=  [a_1,a_2] \cdot[b_1,b_2]=$$
 $$[\min(a_1\cdot b_1,a_1\cdot b_2,a_2\cdot b_1,a_2\cdot b_2),$$
 $$\max(a_1\cdot b_1,a_1\cdot b_2,a_2\cdot b_1,a_2\cdot b_2)],$$
\[
	A / B =  [a_1,a_2] / [b_1,b_2]  =
		  [a_1,a_2]\cdot [1/-b_2,1/b_1] .
\]
	
The most valuable property of interval arithmetics in numerical analysis
and especially in optimization is its inclusion monotonicity.
Let $A$, $B$, $X$, and $Y$ be intervals such that
$A \subseteq X$ and $B \subseteq Y$, then
\[
	A + B  \subseteq X +Y ,
\]
\[
	A - B  \subseteq X - Y,
\]
\[
A\cdot B\subseteq X\cdot Y,
\]
\[
A/B\subseteq X/Y.
\]
In general, inclusion monotonicity holds is for any rational function
$F(A_1,\ldots,A_n)$: If $A_1 \subseteq X_1,\ldots, A_n \subseteq X_n$, then
\[
	F(A_1,\ldots,A_n) \subseteq F(X_1,\ldots,X_n)
\]
for all values $X_1,\ldots,X_n$, for which $F$ is defined \cite{i:Moore66}.
In particular, if we take degenerate intervals (scalars) $x_1,\ldots,
x_n$ as $A_i$, we conclude that if $x_i\in X_i$ for all $i$, then 
\[
	f(x_1,\ldots, x_n) \in F(X_1,\ldots,X_n).
\]
In other words, this means that
\[
	f^*(X_1,\ldots,X_n) \subseteq F(X_1,\ldots,X_n),
\]
i.e., the interval extension $F$ of a scalar function $f$ is a
more or less good upper bound of the range of $f$ (denoted by $f^*$)
over the given hyperbox ${\bf X} = X_1\times X_2\times \cdots \times X_n$.

The quality of the interval range approximation depends on the
form of the function to be evaluated.
In the special case when every variable $x_i$ occurs exactly
once and to the first power in $f$, the interval generalization
gives the exact range $f^*$ \cite{i:Moore79}.
Chuba and Miller have shown that the error is between
$O(w)$ and $O(w^2)$, where $w$ is the width of the argument intervals
\cite{i:Chuba72a}.
A comparison of different interval methods can be found, e.g., in
\cite{A:CetG}.
The so-called {\it centered forms},
described in Subsection \ref{sec:cent}, seems to be
reasonably efficient in approximating
$f^*$.

\subsection{Experimental design and factorial analysis}
A good introduction to experimental design and factorial analysis is
given, e.g., in
\cite{m:Montgomery91book}.
Nam-Ky Nguyen has recently described an algorithm for constructing optimal
or near-optimal incomplete block designs \cite{opt:Nguyen94a}.

%\subsubsection{Taguchi's method}
%A good review of Taguchi's method is given, e.g., in
%\cite{opt:TaguchiBook}.

\subsection{Genetic algorithms}

Living organisms contain huge amounts of information in the form of
genetic code.
Parts of the genetic coding and reproduction system are rather well
known and
the apparent billion years triumph of biological evolution has inspired 
computer scientists to create, analyze, and utilize similar systems in
problems that are known to be computationally hard.
This has led to the study of genetic algorithms (GA) in optimization and
related fields.

One attractive feature of genetic algorithms is their simplicity,
which makes it easy to implement and tailor them to practical problems.
The operation of a genetic algorithm searching for 
an optimal solution to a given
problem can be divided into the following steps:
\newpage

\vspace{2mm}
\noindent
\underline{\bf Genetic Algorithm:}
\begin{itemize}
	\item \  [{\bf initialization}]  generate the initial (e.g. random)
		set of potential solutions;
	\item \  [{\bf natural selection}] calculate how ``far''
is each solution from the goal,
		and take the best ones;
	\item \  [{\bf breeding}] generate new solutions
		by exchanging solution parameters (crossing)
		between the selected good solutions,
	 	and possibly, add some noise (mutations);
	\item \  [{\bf repetition}] if the goal is not reached, go back to 
		the step [{\bf breeding}].
\end{itemize}

In spite of the seemingly simple processing, the GAs
are known to be good in solving some problems that are known to be hard.
The simplicity, flexibility, parallelism, and the good problem solving
capability were the most important facts that inspired 
us to experiment with GAs
in order to find methods of solving robot control problems.

Some apparent good and bad properties of GAs include:

{\small
\begin{center}
\begin{tabular}{|l|l|} \hline
{\it good news} & {\it bad news} \\ \hline
simple & massive \\
parallel in nature & large storage\\
robust   & stochastic  \\
general &  not well known \\ \hline
\end{tabular}
\end{center}
}

The fundamentals of genetic algorithms can be found in David Goldberg's book
\cite{ga:Goldberg89book}.
In addition, Lawrence Davis gives a good overview of applications 
\cite{ga:Davis91book}. 
He also suggests a practical procedure to
attack new problems by combining genetic algorithms with existing methods
into, as he calls, hybrid GA:
The pure basic genetic algorithm is usually not the best possible algorithm
to solve any specific problem if a good specific algorithm already exists.
There is, however, a good chance to create a better algorithm by combining
the best features of existing conventional and genetic algorithms.

\subsection{Related work}
Interval methods have not been used much with genetic algorithms.
According to the bibliography \cite{GA:biblio57-93} compiled by the author,
only the following papers are related to intervals:
\cite{ga:Forrest91f,ga:Muselli92,ga:Schaffer92b,ga:Yam92a,ga:Yam92b}.
Because there are few interval GA papers, one objective of this
paper is to make interval arithmetics and its potential
application in genetic algorithms more familiar to the GA community and
{\it vice versa};
the author also hopes that this paper also makes GAs and their potential
in optimization more familiar to the interval community.
According to \cite{GA:biblio57-93}, only four papers dealing with GA
have appeared in the mainstream optimization journals
\cite{ga:Groot93a,ga:LeGrand93a,ga:Suh91a,ga:Walk88a}, which is quite
small number for such an inherently optimization method as GA!

The lack of papers that we have noticed for 
GAs/interval arithmetics application
applies to GAs and factorial analysis as well.
Only one reference in \cite{GA:biblio57-93} seems to have something to do
with factorial analysis and GAs: \cite{ga:MCGupta93a}.

\section{Methods}
\subsection{Interval arithmetics}
Interval methods for optimization are based on the inclusion monotonicity
of interval generalizations of scalar functions.
In global optimization, branch and bound method is usually used to
find the exact global optimum.
The argument interval are subdivided until the optimum of given tolerance
is found \cite{i:EHansen79a,i:EHansen80a}.

Ratschek and Rokne have proposed the following simple interval optimization
method \cite[Algorithm 2 of Chapter 5]{i:Ratschek88book}:

\begin{enumerate}
	\item put all uninspected boxes into a list $L$. At the beginning,
		$L$ contains only the search box $X$.
	\item subdivide the first box of $L$ into boxes $V_1$ and $V_2$.
	\item put box $V_i$ at the end of $L$ unless it can not contain a
		global solution
	\item if a stopping criterion is met, terminate, else go to step 2.
\end{enumerate}

\subsubsection{Centered forms}
\label{sec:cent}
H. Ratschek gives a definition of the centered form based on the
Taylor expansion of the object function \cite{i:center}.
Let $f(x) = p(x)/q(x)$ be a rational function of one real variable
$x \in X$ and let $n$ be the maximum of the degrees of the polynomials
$p$ and $q$. The centered form of $f$ is defined as
\[
	F(X) = f(m) + G(X-m),
\]
where $m$ is the mid-point of $X$,
\[
	G(Y)  =  \frac{\sum_{i=1}^n a_iY^i/i!}
		{\sum_{i=0}^n q^{(i)}(m)Y^i/i!},
\]
and $a_i = p^{(i)}(m)-f(m)q^{(i)}(m)$.
This expansion can be derived, if instead of the functions $p(x)$ and
$q(x)$, we substitute their their Taylor series at the point $m$.

The above definition of centered  forms can be generalized to higher orders
by expanding $f$ to its Taylor series and taking the first $k$ terms:
\[
	F_k(Y) = f(m) + f'(m)\cdot Y/1!
\]
\[
	+ \cdots + f^{(k-1)}(m)\cdot Y^{k-1}/(k-1)!
\]
\[
	+ \frac{a_k^{(k)}Y^k/k! + \cdots + a_{k+n-1}^{(k)}Y^{k+n-1}/(k+n-1)!}
		{q(m)+q'(m)Y + \cdots + q^{(n)}(m)Y^n/n!},
\]
where
\[
	a_i^{(k)} = p^{(i)}(m) - \sum_{j=0}^{k-1}
		\left(\begin{array}{c} i\\j\end{array}\right)
			f^{(j)}(m)q^{(i-j)}(m).
\]

%\subsection{Factorial analysis methods}


\section{Results}

In this work, we combine three promising global optimization methods:
\begin{itemize}
\item interval arithmetic methods,
\item  experimental design, and 
\item genetic algorithms, 
\end{itemize}into
a hybrid algorithm.In this algorithm:
\begin{itemize}
\item Interval arithmetics gives us simple methods to estimate the range of
functions to be optimized.
\item Experimental design and 
factorial analysis helps to find the essential
parameter values while
\item Genetic algorithms adaptively guides the search.
\end{itemize}

We have applied this algorithm to robot control and to other
engineering problems. The results of this application 
are much better than for other known
methods.

\begin{thebibliography}{99}

\bibitem{A:CetG}
Jarmo~T. Alander,
``On interval arithmetic range approximation methods of polynomials and
  rational functions,''
 {\it Computers\&Graphics}, 1985, Vol. 9, No. 4, pp. 365--372.

\bibitem{GA:biblio57-93}
Jarmo~T. Alander,
 {\bf An indexed bibliography of genetic algorithms: Years 1957--1993},
 Art of CAD Ltd., Vaasa (Finland), 1994
 (over 3000 GA references).

\bibitem{i:Chuba72a}
W.~Chuba and W.~Miller,
 ``Quadratic convergence in interval arithmetic. {P}art {I},''
 {\it BIT}, 12:284--290, 1972.

\bibitem {ga:Davis91book}
Lawrence Davis (editor),
 {\bf Handbook of Genetic Algorithms},
 Van Nostrand Reinhold, New York, 1991.

\bibitem{ga:Groot89a}
Claas de~Groot, Diethelm W{\"u}rtz, and Karl~Heinz Hoffmann.
 {\bf Low autocorrelation binary sequences: Exact enumeration and
  optimization by evolutionary strategies}, 
 Technical Report No. 89-09, Interdisciplinary Center for
  Supercomputing Research, Eidgen{\"o}ssische Technische Hochschule Z{\"u}rich,
  1989.

\bibitem{ga:Groot93a}
Claas de~Groot, Diethelm W{\"u}rtz, and Karl~Heinz Hoffmann,
``Low autocorrelation binary sequences: Exact enumeration and
  optimization by evolutionary strategies,''
 {\it Optimization (UK)}, 1993, Vol. 23, No. 4, pp. 369--384
 (first version appeared as \cite{ga:Groot89a}).

\bibitem{ga:Schaffer92b}
Larry~J. Eshelman and J.~David Schaffer,
``Real-coded genetic algorithms and interval-schemata''.
 In \cite{ga:FOGA92}, pp. 187--202.

\bibitem{ga:MCGupta93a}
Mahesh~C. Gupta, Yash~P. Gupta, and Anup Kumar,
``Minimizing flow time variance in a single machine system using
  genetic algorithm'',
 {\it European Journal of Operations Research}, November 1993, Vol.
70, No. 3, pp. 289--303.

\bibitem{ga:LeGrand93a}
Scott Michael~Le Grand and K.~M. Merz, Jr.,
``The application of genetic algorithms to the minimization of
  potential energy functions,''
 {\it Journal of Global Optimization}, 1993, Vol. 3, pp. 49--66.

\bibitem{ga:Goldberg89book}
David~E. Goldberg,
 {\bf Genetic Algorithms in Search, Optimization, and Machine
  Learning},
 Addison-Wesley, Reading, MA, 1989.

\bibitem{i:EHansen79a}
E.~R. Hansen,
``Global optimization using interval analysis --- the one-dimensional
  case'',
 {\it J. Optim. Theory and Appl.}, 1979, Vol. 29, pp. 331--344.

\bibitem{i:EHansen80a}
E.~R. Hansen.
 Global optimization using interval analysis --- the multi-dimensional
  case.
 {\it Numerische Mathematik}, 1980, Vol. 34, pp. 247--270.

\bibitem{opt:Horst90book}
Reiner Horst and Hoang Tuy,
 {\bf Global Optimization},
 Springer-Verlag, Berlin, 1990.

\bibitem{ga:Suh91a}
Prasanna Jog, Jung~Y. Suh, and Dirk~Van Gucht,
``Parallel genetic algorithms applied to the traveling salesman
  problem,''
 {\it SIAM Journal on Optimization}, 1991, Vol. 1, No. 4, pp. 515--529.

\bibitem{ga:Yam92a}
Kwong~Sak Leung, Yee Leung, Leo So, and Kim~Fai Yam.
 Rule learning in expert systems using genetic algorithm: 1, concepts.
{\it Proceedings of the 2nd International Conference on Fuzzy
  Logic and Neural Networks (IIZUKA'92), Iizuka (Japan), July 17--22,
1992}, Fuzzy Logic Systems Institute, Japan, 1992, Vol. 1, pp. 201--204. 

\bibitem{ga:Yam92b}
Kwong~Sak Leung, Yee Leung, Leo So, and Kim~Fai Yam,
``Rule learning in expert systems using genetic algorithm: 1, empirical
  studies'',
{\it Proceedings of the 2nd International Conference on Fuzzy
  Logic and Neural Networks (IIZUKA'92), Iizuka (Japan), July 17--22,
1992}, Fuzzy Logic Systems Institute, Japan, 1992, Vol. 1, pp. 205--208. 

\bibitem{m:Montgomery91book}
Douglas~C. Montgomery,
 {\bf Design and Analysis of Experiments},
 John Wiley {\&} Sons, New York, 3 edition, 1991.

\bibitem{i:Moore66}
R.~E. Moore,
 {\bf Interval Analysis},
 Prentice-Hall, Inc., Englewood Cliffs, 1966.

\bibitem{i:Moore79}
R.~E. Moore,
 {\bf Methods and Applications of Interval Analysis},
 {SIAM}, Philadelphia, 1979.

\bibitem{ga:Muselli92}
Marco Muselli and Sandro Ridella,
``Global optimization of functions with the interval genetic algorithm''.
 {\it Complex Systems}, June 1992, Vol. 6, No. 3, pp. 193--212.

\bibitem{ga:Forrest91f}
T.~M. Murdock, W.~E. Schmitendorf, and Stephanie Forrest,
``Use of genetic algorithm to analyze robust stability problems'',
{\it Proceedings of the American Automatic Control Conference,
Boston, MA, June 26--26, 1991}, American Automatic Control
  Council, 1991, pp. 886--889.

\bibitem{opt:Nguyen94a}
Nam-Ky Nguyen,
``Construction of optimal block design by computer'',
 {\it Technometrics}, August 1994, Vol. 36, No. 3, pp. 300--307.

\bibitem{i:center}
H.~Ratschek,
``Centered forms'',
 {\it {SIAM} Journal of Numerical Analysis}, 1980, Vol. 17, pp. 656--662.

\bibitem{i:Ratschek88book}
Helmut Ratschek and Jon Rokne,
 {\bf New computer methods for global optimization},
 Ellis Horwood, New York, 1988.

\bibitem{i:Rokne82a}
Jon Rokne and T.~Wu,
``The circular complex centered form'',
 {\it Computing}, 1982, Vol. 28, p. 17--30.

\bibitem{i:Rokne83a}
Jon Rokne and T.~Wu,
``A note on the circular complex centered form'', 
{\it Computing}, 1983, Vol. 30, pp. 201--211.

\bibitem{ga:ZYang93a}
Peng Tian and Zihou Yang,
 ``An improved simulated annealing algorithm with genetic
  characteristics and the traveling salesman problem'', 
 {\it J. Inf. Optim. Sci. (India)}, September 1993, Vol. 14, No. 3,
pp. 241--255.

\bibitem{ga:FOGA92}
Darrell Whitley (editor),
 {\it Foundations of Genetic Algorithms --- 2 (FOGA-92)}, Vail, CO,
  July 24--29, 1992, Morgan Kaufmann, San Mateo, CA. 1992.

\bibitem{ga:Walk88a}
M.~Walk and J.~Niklaus,
 ``Some remarks on computer-aided design of optical lens systems'',
 {\it Journal of Optimization Theory and Applications}, 1988,
  Vol. 59, No. 2, pp. 173--181.

\end{thebibliography}

\end{document}

