Genetic Algorithms for Interplanetary Trajectory Optimisation
Over the course of the past years, global optimisation algorithms imitating certain principles of nature have proved their usefulness in various domains of applications. One of those optimisation algorithms, namely genetic algorithms, has gained increasing popularity over the past few years.
A genetic algorithm is chosen to optimise the DV, C3 or satellite mass due to its capabilities of optimising non-linear problems in large search spaces. An advantage of genetic algorithms is that no derivatives of the cost function are required. Also, initial values of the parameters are chosen at random by the genetic algorithm. Based on mechanics of natural selection and genetics, genetic algorithms can be used where traditional search and optimisation techniques are less effective. These are cases where the relationship between the optimum and the determining parameters is complex and not well known, combined with the possibility of a simple determination of the optimum. Here, the optimum is the lowest DV, C3 or highest mass required to get to a planet; a criteria which is indeed simple.
According to [Heitkoetter, 1994]: “The genetic algorithm is a model of machine learning which derives its behaviour from a metaphor of the processes of evolution in nature. This is done by the creation within a machine of a population of individuals represented by chromosomes, in essence a set of character strings that are analogous to the base-4 chromosomes that we see in our own DNA. The individuals in the population then go through a process of evolution which is, according to Darwin, uses the mechanics of mutation and selection; however, the modern biological evolution theory also knows crossover and isolation mechanisms to improve the adaptiveness of the living beings to their environments.
With genetic algorithms, elements or chunks of elements are swapped between individuals as if by sexual combination and reproduction (crossover), others are changed at random (mutation). New generations appear from clones of the current population, in proportion to their fitness: a single objective function of the parameters that returns a numerical value, to distinguish between good and bad solutions. Fitness is then used to apply selection pressure to the population in a ‘Darwin’ fashion (principle of the survival of the fittest).”
Genetic algorithms (Ga’s) differ from conventional optimisation and search procedures in four ways [Goldberg, 1989]:
- GA’s work with a coding of the parameter set, not the parameters themselves.
- GA’s search from a population of points, not a single point.
- GA’s use payoff (objective function) information, not derivatives or other auxiliary knowledge.
- GA’s use probabilistic transition rules, not deterministic rules.
Genetic algorithms require the natural parameter set of the optimisation problem to be coded as a finite-length string (analogous to chromosomes in biological systems) containing characters, features or detectors (analogous to genes), taken from some finite-length alphabet. Usually, the binary alphabet that consists of only 0 and 1 is taken. Each feature takes on different values (alleles) and may be located at different positions (loci). The total package of strings is called a structure or population (or, genotype in biological systems).
Users of genetic algorithms have documented & published the characteristics of genetic algorithms with many applications. In some fields these algorithms are very powerful, in other fields they are not. Also the genetic algorithm specific parameters, such as probabilities of crossover and mutation, have an important impact on the convergence.
This study is aimed at answering what are the characteristics of genetic algorithms when applying them to optimisations of interplanetary transfer orbits. Genetic algorithms have already proven to be successful for obtaining innovative solutions such as Weak Stability Boundary orbits, swing-by’s, low-thrust transfers, navigation (Mars Pathfinder) and tether dynamics. Although they have been studied at ESOC by senior Mission Analyst Guy Janin, at ESTEC by they have not been applied to interplanetary trajectory optimisation of multiple swing-bys and deep space manoeuvres.
The innovation in this study is the combination of the genetic algorithm with an existing trajectory optimisation tool and the correct choice of optimisation parameters. The tool to which the genetic algorithm will be coupled is the swing-by calculator, developed by JAQAR under ESA contract for the ESTEC Concurrent Design Facility.
The result is a set of preferred genetic algorithm parameters and an interplanetary optimisation tool with user-friendly GUI that runs on any PC. No input files shall be used; all parameters are selected using the GUI. Trajectory output files are created compatible with STK and IMAT.