% -*-LaTex-*- 
%******* Chapter 4: Genetic Algorithms and Optimal Trajectories *****
\label{genetic_chap}

  Genetic algorithms (GAs) are randomized {\em population} based
search techniques closely emulating the natural process of evolution.
They are predominantly string or integer-based searches with each {\em
member} of the population represented by a string of bits ({\em
alleles}), alphabets or other enumerated forms. This string or member
is known as the {\em chromosome}. The evolution process is punctuated
by evolving a new population set from the previous set. Each of these
population sets is known as a {\em generation}.  Each member of the
new population is derived from one or more members from the previous
set.  Hence, the new chromosome is the {\em child} of the {\em parent}
chromosome(s) from the previous generation. This process of {\em
reproduction} is driven by a {\em fitness} value associated with each
chromosome. The objective of a GA is to find the maximum global
fitness.  In this context, the chromosome is known as the {\em
genotype} and the fitness which is the genotype's physical
manifestation, is known as the {\em phenotype}. The problem specifics
play a role in genetic algorithms only in decoding the chromosome and
constructing its fitness value or phenotype. There are no restrictions
on the domain of the decoded design space or the solution space. This
flexibility and the robust nature of genetic algorithms makes them
very powerful tools.  Unlike dynamic programming and similar methods,
they do not possess the curse of dimensionality. However, they are not
as efficient as some of the specialized schemes like BFGS~\cite{fletcher} or 
SQP ({\em Sequential Quadratic Programming}) when
applied to problems in their domains. Hybridization or using specific
problem properties to enhance GAs is known to restore efficiency
without sacrificing too much robustness or flexibility.

The {\em adaptive} nature of these search algorithms is used for
optimization and classifier systems. Hence, they have been used for a
variety of problems like minimizing noisy functions, playing chess,
designing gas turbines, and robot arm trajectory following.  The
primary references in this field are due to Holland~\cite{holland} and
Goldberg~\cite{goldberg}.  DeJong~\cite{dejong} did an extensive study
on optimizing real-valued functions including near singular and
discontinuous ones.  Davis~\cite{lawerence} gives a commentary on
optimizing real-valued functions and a compilation of papers. One of
first applications of GAs was in real time optimal control of pipeline
scheduling~\cite{goldberg}. There seems to be little work in the area
of optimal control however, except for ongoing research on optimal
robot arm trajectory following~\cite{lawerence}. Rao~\cite{ssrao},
Hajela~\cite{hajela} are investigating application in structural
design.  Katragadda~\cite{katragadda} investigating and
Krishnakumar~\cite{krishnakumar} are investigating applications in
aerospace design.

  There are predominantly two processes which form the core of the
evolutionary process:
\begin{itemize}
\item Crossover. A child produced using this process will have part(s)
of its chromosome from one parent and the rest from the second parent.
More than two parents are rarely used. 
\item Mutation. Mutation is a allele-based process, where the mutation
of an allele implies replacing the existing value with a random value.
\end{itemize}
Both processes or {\em operators} are carried out with a specified
probability of success. They affect a child only if they pass the
probability test. A typical crossover probability is 0.8 per two
children and a typical mutation probability is 0.01 per allele.  Which
means that on average 8 out of 10 children have been produced by the
{\em mating} of more than one parent and 1 out of 100 alleles (bits) are
mutated. The selection of parents is a weighted probability of their
fitness.  This process of evolution and the population-based nature is
what differentiates genetic algorithms from the rest of the search
and optimization techniques.


      If pure crossover is used, the algorithm degenerates into a
combinatorial search. If pure mutation is used, it degenerates into a
random search. The primary construct being searched for by the GA is
the best {\em schema}. A schema is a similarity template which can
match more than one chromosome. For example, a bit string chromosome
100110 matches the schemata $10****$, $100*10$, $100110$ and
61 more. The `$*$' represents the ``don't care'' logical value. Given
a string of length $l$, there are $3^l$ possible schemata. A given
chromosome matches $2^l$ schemata. The best solution is represented by
a set of one or more best schema. Hence, the GA evolves the population
by mixing schema of the superior individuals and weeding out unwanted
schemata by assigning low survival to weak individuals. It is assumed
that the superior individuals have more parts of the best schema.
However, some good schemata may be masked in the weak individual and
lost. Hence, mutation (and recently {\em diploidy}) is primarily
responsible for maintaining a diverse pool of schemata. Crossover is
used to combine existing ones. A host of operators based on these two
basic ones have been developed to enhance reproduction.


\subsection {Genetic Algorithms in Optimization}
   Our interest in genetic search is restricted to optimizing
nonlinear functions with low noise. The solution is the best
individual obtained from the entire search. By tradition, as in the
code presented, GAs are used to maximize a function. A GA for
optimization is described as follows:
\begin{enumerate}

\item Get an initial population from the user or by random string
generation. 

\item  
\label{gaeval}
Decode the genotypes (strings) of the population and evaluate the
fitness value (phenotype). The chromosome is a composite
of binary substrings, each representing a real number. The
binary substring is decoded to an integer and then mapped to a specified
domain of real numbers by linear interpolation. 


\item \label{scale:fit}
Scale the fitness values to be all positive. Assign a survival probability to each
individual in the population based on fitness. For this study, this probability
is the ratio of the sum of an individual's fitness and the average
population fitness to twice the total fitness. The total probability is 1.

\item Generate a new population. In general, a part of the population
is cloned from the best of the previous population. The rest is
generated by the reproduction process described above. The parents for
reproduction are selected by random selection with assigned probability as
in Step~\ref{scale:fit}.

\item Check the termination criteria, for example, the number of new
individuals produced, fitness difference between the best and the
weakest, or computation time elapsed. If the process is not terminated,
continue from step~\ref{gaeval}. Otherwise, return the best individual as
the solution.

\end{enumerate}

The GA code used in this study was written in C using a framework and
data structures similar to ones used by Goldberg~\cite{goldberg}.
Several modifications were made to improve efficiency, mostly as
suggested by Davis~\cite{lawerence}. These include generating only a
fraction of the population per reproduction, ensuring that no twins
exist, scaling the fitness values, interpolating mutation and
crossover rates over the run, adding new operators like multiple point
crossover and adaptive template crossover. The probabilistic nature of
GAs gives rise to the need for averaging several runs with the same
initial parameters for performance evalutaion. Further modifications
to the genetic code developed during this investigation include:

\begin{itemize}
\item Specifying mutation rate per individual rather than per
allele to decouple it with change in chromosome size affected
by change in precision requirements.

\item Effecient duplicate detection schemes to avoid exhaustive
searches.

\item Modified fitness scaling by adding the average fitness of the
population  to each individuals fitness to reduce bias for very
strong individuals and at the same time retain the relative properties. 

\item Adding new operators like multi point crossover where crossover
is done for each substring denoting a real number and the adaptive template
operator which is uniform crossover~\cite{lawerence} with the template generated by
logical summing of two or more `best' individuals.

\end{itemize}

Details are given in a thesis on the study
of GAs and other optimization techniques for the trajctory
optimization problem~\cite{katragadda}. 

    Validation of the GA coded was done using the first four test
functions of DeJong~\cite{dejong}, the modified binary
(F6)~\cite{lawerence} and goldberg's example~\cite{goldberg}. The
algorithm converged well for all the functions and outperformed the
results by Davis~\cite{lawerence}, by about 1.5~\cite{katragadda} on a
log scale, giving an accuracy of 5 decimal places. However using real
number encoding, Davis~\cite{lawerence} shows faster convergence.
These test functions demonstrated the ability of the GA to converge on problems 
which are badly scaled, nonconvex, multiple local maxima and nonlinear.

\subsection{GAs in Optimal Control} 
      Optimal trajectory problems present an
opportunity to apply GAs to develop a general algorithm for generating
initial trajectories for the indirect method. The objective is to find
a solution close enough to the optimal solution with enough digits of
accuracy (normally two or three) to enable more efficient codes like
SQP or one of the NEM ({\em Neighbouring Extremal Method}) 
codes to converge to the optimal solution. This
objective has been successful with GAs. The literature surveyed so far
fails to reveal a method for obtaining the indirect
solution for optimizing spacecraft trajectories.

Finding a feasible trajectory for optimal control problems in general,
let alone the one under consideration, is reported~\cite{bryson} to be
very difficult due to the sensitive nature of the costate equations.
GAs also have the ability to find more than one optimal solutions or
{\em niches}.  This leads to the three chief uses of GAs for such
problems:
\begin{itemize}
\item To find solutions to the given problem with no coding
except for objective function evaluation (simulation), saving
time on investigation of sensitive problems.

\item To add specific enhancements and code hybrid GAs~\cite{lawerence} to give
robustness and superior performance.

\item To aid in better problem understanding. Analytic tools have long
been the major source for problem understanding, using simplified
problems. Hence, there is limited meaning to be found (except by long
experience) on quantities like costates. Genetic codes by virtue of
finding several solutions and allowing deductive modifications
can enhance this process. An instance of such a process is given below.

\end{itemize}

    In solving the optimal trajectory problem, the unknown initial
states, costates and time intervals are taken as the design variables.
Each variable is represented by a string of a specified number of bits.
It was found that using slightly more bits than required for the
anticipated accuracy gave better performance. Given a length of $l_i$
bits for the ith variable, its domain is discretized to $2^{l_i}$
uniformly spaced real numbers. Goldberg's~\cite{goldberg} simple
genetic algorithm is not suitable for real world applications because
of its low efficiency. However, if we incorporate the enhancements
described above, the GA starts rivalling conventional algorithms in
efficiency.  However, there was no problem the
GA did not converge for. Some parametric adjustments were required to
get more performance. Constraints are handled by the L1 exact penalty
function described by Fletcher~\cite{fletcher}:
\begin {equation}
\label{L1exact}
\Phi(\Xb) = F(\Xb)/ \sigma + \sum\mod{C_e(\Xb)} + \sum C_i(\Xb)^-,
~~C_i(\Xb)^- = \max(-C_i(\Xb), 0)
\end{equation}
\noindent Where constraints $C_e(\Xb)=0$ and
$C_i(\Xb)\ge 0$. The unconstrained minima of this function have been
proved to be the constrained minima of the problem. These functions
exhibit slope discontinuities and therefore cannot be minimized using
gradient based techniques.  The constraints were sufficiently weighted
in order to ensure boundedness of the function.  Bounds on the domain
of the design vector are implicitly handled by the decoding scheme
used. The major computation cost involved in the problems under
consideration is the numerical integration over time of the problem
model. Beside using effecient, variable step size and variable order
schemes~\cite{gear} for integration, the following genetic algorithm
specific techniques help in significant reduction of the computation
costs:

\begin{itemize}

\item Numerical integration can be carried out with much lower
accuracies as compared to the requirements of nonlinear programming
methods, since gradient information is no longer required. The integration accuracy
was specified ad hoc to be an order of magnitude higher than the maximum required
accuracy of the solution.

\item Incomplete Simulation.
Genetic search permits function discontinuities and  hence allows incomplete
or coarse trajectory simulation using the physical know how of the
problem. The following modifications gave significant
performance increase with no change in convergence:
\begin{itemize}
\item Terminate trajectory after the first engine on phase if the
radius is less than the initial radius or if the radius is less than
five times planet radius. The former truncates trajectories spiraling
down and the latter conservatively weeds out non-escape conditions.

\item Terminate trajectory after the coast phase if the radius is more
than half the `interplanetary' distance $\di$.

\item For the escape problem, terminate the trajectory if the control
angle has exceeded 0.3 radians before $(\tf-\to)/10$ has elapsed,
since the optimal escape is known to be very close to zero for almost
the entire trajectory.

\end{itemize}

\end{itemize}

     These modifications, by no means extensive, were deemed safe in terms
of not restricting the flexibility of the genetic code.

\end{document}




