 |
GTOP Database - Basic solvers GOTP is a database containing the exact definition of some global optimisation spacecraft trajectory problems and their best putative solutions. |
Back to Global Optimisation  |
We applied some standard global optimisation solvers on the proposed problems (see the description of them on this page). A short description of these solvers are given together with their references. For the benchmarking results see our paper: Vinkó, T. and Izzo, D., Global Optimisation Heuristics and Test Problems for Preliminary Spacecraft Trajectory Design, European Space Agency, the Advanced Concepts Team, ACT technical report (GOHTPPSTD), 2008. (link) |
|
|
Differential Evolution (DE) This optimisation algorithm is based on updating each element of a set (population) of feasible solutions by using the weighted difference of two (or more) other randomly selected population elements. This way no separate probability distribution has to be used which makes the scheme completely self-organizing. The method is described in detail in [1]. In the benchmarking a slightly modified version of the MATLAB code from the Differential Evolution website was used. |
|
|
Particle Swarm Optimization (PSO) This is another population-based algorithm inspired by the social behaviour of bird or fish flockings [2]. In a PSO method, each element (particle) evolves by taking the combination of the current global best and individual best solutions into account. |
|
|
The goodness of an individual in the population is measured by its fitness value (i.e. the objective function value). GA evaluates the fitness of each individual in the population and then while not converged it selects individuals to reproduce, performs crossover and mutation to make the offspring evaluates the individual fitnesses of the offspring and finally replaces the worst ranked part of the population with the offspring. We used a simple GA implementation by Gordy in MATLAB. Download the code. |
|
|
Simulated Annealing (SA) [4] picks some neighbour y of a point x and compute its energy (this is like the fitness value in the above algorithms). SA moves to this new point y based on a randomly selected number which depends on the distance of the corresponding function values and on a global parameter T (temperature), that is gradually decreased during the process. The original SA algorithm was coded in MATLAB. Download the code. |
|
Adaptive simulated annealing (ASA) [5] is a variant of SA in which the algorithm parameters that control temperature schedule and random step selection are automatically adjusted according to algorithm progress. For the benchmarking a MATLAB gateway version was used; details can be found at here. This program requires the original code of Ingber's ASA available here. Note that this algorithm was tested in the IAF conference paper, see above. |
|
|
We used the recent version of this solver implemented in MATLAB and documented in [7]. Download the code. Note that this algorithm was tested in the IAF conference paper, see above. |
|
|
References [1] Storn, R. and Price, K., Differential Evolution - a Simple and Efficient Heuristic for Global Optimization over Continuous Spaces, Journal of Global Optimization, 11, pp.341-359, 1997. [2] Kennedy, J. and Eberhart, R. C., Particle swarm optimization, Proceedings of IEEE International Conference on Neural Networks, pp.1942-1948, 1995. [3] Holland, J. H., Adaptation in Natural and Artificial Systems, University of Michigan Press, 1975. [4] Kirkpatrick, S., Gelatt, C., and Vecchi, M., Optimization by simulated annealing, Science, 220, pp.671-680, 1983 [5] Ingber, A.L., Very fast simulated re-annealing, Journal of Mathematical Computer Modelling, 12, 967-973, 1989. [6] Csendes, T., Nonlinear parameter estimation by global optimization - efficiency and reliability, Acta Cybernetica 8, 361-370, 1988. [7] Csendes, T., Pál, L., Sendín, J.O.H., and Banga, J.R., The GLOBAL Optimization Method Revisited. Submitted for publication, 2007.
|
