Genetic algorithms (GAs) are randomized population based search techniques closely emulating the natural process of evolution. They are predominantly string or integer-based searches with each member of the population represented by a string of bits (alleles), alphabets or other enumerated forms. This string or member is known as the 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 generation. Each member of the new population is derived from one or more members from the previous set. Hence, the new chromosome is the child of the parent chromosome(s) from the previous generation. This process of reproduction is driven by a 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 genotype and the fitness which is the genotype’s physical manifestation, is known as the 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 [?] or SQP (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 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 [?] and Goldberg [?]. DeJong [?] did an extensive study on optimizing real-valued functions including near singular and discontinuous ones. Davis [?] 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 [?]. There seems to be little work in the area of optimal control however, except for ongoing research on optimal robot arm trajectory following [?]. Rao [?], Hajela [?] are investigating application in structural design. Katragadda [?] investigating and Krishnakumar [?] are investigating applications in aerospace design.

There are predominantly two processes which form the core of the evolutionary process:

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

• Mutation. Mutation is a allele-based process, where the mutation of an allele implies replacing the existing value with a random value.

Both processes or 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 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 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 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.

0.1 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:

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

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

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

4. 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 3.

5. 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 2. Otherwise, return the best individual as the solution.

The GA code used in this study was written in C using a framework and data structures similar to ones used by Goldberg [?]. Several modifications were made to improve efficiency, mostly as suggested by Davis [?]. 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:

• Specifying mutation rate per individual rather than per allele to decouple it with change in chromosome size affected by change in precision

requirements.

• Effecient duplicate detection schemes to avoid exhaustive searches.

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

• 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 [?] with the template generated by logical summing of two or more ‘best’ individuals.

Details are given in a thesis on the study of GAs and other optimization techniques for the trajctory optimization problem [?].

Validation of the GA coded was done using the first four test functions of DeJong [?], the modified binary (F6) [?] and goldberg’s example [?]. The algorithm converged well for all the functions and outperformed the results by Davis [?], by about 1.5 [?] on a log scale, giving an accuracy of 5 decimal places. However using real number encoding, Davis [?] 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.

0.2 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 (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 [?] 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 niches. This leads to the three chief uses of GAs for such problems:

• To find solutions to the given problem with no coding except for objective function evaluation (simulation), saving time on investigation of sensitive problems.

• To add specific enhancements and code hybrid GAs [?] to give robustness and superior performance.

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

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 [?] 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 [?]:

Φ(X) = F (X)/σ+∑ |C_{e}(X)|+∑ C_{i}(X)^{−}, C_{i}(X)^{−} = max(−C_{i}(X), 0) (1)

Where constraints C_{e}(X) = 0 and C_{i}(X) ≥ 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 [?] for integration, the following genetic algorithm specific techniques help in significant reduction of the computation costs:

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

• 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:

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

– Terminate trajectory after the coast phase if the radius is more than half the ‘interplanetary’ distance d_{1}.

– For the escape problem, terminate the trajectory if the control angle has exceeded 0.3 radians before (t_{f} − t_{o})/10 has elapsed, since the optimal escape is known to be very close to zero for almost the entire trajectory.

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