Skip to content
This repository has been archived by the owner on Jul 16, 2024. It is now read-only.

Publications

Jump to bottom
Luís F. Simões edited this page Mar 5, 2014 · 7 revisions

##### Table of Contents * [On PaGMO](#On PaGMO) * [Generalized Island Model](#Generalized Island Model) * [Using PaGMO](#Using PaGMO)
## On PaGMO ##
Biscani, F., Izzo, D., & Yam, C. H. (2010). A Global Optimisation Toolbox for Massively Parallel Engineering Optimisation. _4th International Conference on Astrodynamics Tools and Techniques (ICATT 2010)_.

A software platform for global optimisation, called PaGMO, has been developed within the Advanced Concepts Team (ACT) at the European Space Agency, and was recently released as an open-source project. PaGMO is built to tackle high-dimensional global optimisation problems, and it has been successfully used to find solutions to real-life engineering problems among which the preliminary design of interplanetary spacecraft trajectories - both chemical (including multiple flybys and deep-space maneuvers) and low-thrust (limited, at the moment, to single phase trajectories), the inverse design of nano-structured radiators and the design of non-reactive controllers for planetary rovers. Featuring an arsenal of global and local optimisation algorithms (including genetic algorithms, differential evolution, simulated annealing, particle swarm optimisation, compass search, improved harmony search, and various interfaces to libraries for local optimisation such as SNOPT, IPOPT, GSL and NLopt), PaGMO is at its core a C++ library which employs an object-oriented architecture providing a clean and easily-extensible optimisation framework. Adoption of multi-threaded programming ensures the efficient exploitation of modern multi-core architectures and allows for a straightforward implementation of the island model paradigm, in which multiple populations of candidate solutions asynchronously exchange information in order to speed-up and improve the optimisation process. In addition to the C++ interface, PaGMO's capabilities are exposed to the high-level language Python, so that it is possible to easily use PaGMO in an interactive session and take advantage of the numerous scientific Python libraries available.


Izzo., D. 'PyGMO and PyKEP: Open Source Tools for Massively Parallel Optimization in Astrodynamics (the case of interplanetary trajectory optimization)', Proceedings of the International Conference on Astrodynamics Tools and Techniques - ICATT (2012), Noordwijk, ESA, ESTEC

At the intersection between computer science and astrodynamics lies a fertile ground for improving methodologies and performances of spacecraft trajectory computations. In this paper we present two open source projects (written in C++ and exposed to Python) that are focused around computational efficiency and that allow to script massively parallel optimization of aerospace related problems. In particular, we will show their use for interplanetary trajectory optimization. After having described novel findings and technologies powering these two projects, we will show some use examples. We show results on asteroid selection for human mission to asteroids, on the Global Trajectory Optimization Competitions and, finally, on a novel idea to obtain on-line adaptive mesh during the direct optimization of interplanetary low-thrust problems.


### Generalized Island Model ###
Märtens, M., & Izzo, D. (2013). The asynchronous island model and NSGA-II: study of a new migration operator and its performance. In C. Blum (Ed.), Genetic and Evolutionary Computation Conference (GECCO 2013) (pp. 1173-1180). New York, USA: ACM Press.

This work presents an implementation of the asynchronous island model suitable for multi-objective evolutionary optimization on heterogeneous and large-scale computing platforms. The migration of individuals is regulated by the crowding comparison operator applied to the originating population during selection and to the receiving population augmented by all migrants during replacement. Experiments using this method combined with NSGA-II show its scalability up to 128 islands and its robustness. Furthermore, the proposed parallelization technique consistently outperforms a multi-start and a random migration approach in terms of convergence speed, while maintaining a comparable population diversity. Applied to a real-world problem of interplanetary trajectory design, we find solutions dominating an actual NASA/ESA mission proposal for a tour from Earth to Jupiter, in a fraction of the computational time that would be needed on a single CPU.


Izzo, D., Ruciński, M., & Biscani, F. (2012). The generalized Island Model. _Parallel Architectures and Bioinspired Algorithms_, Studies in Computational Intelligence, 2012, Volume 415/2012, 151-169.

The island model paradigm allows to efficiently distribute genetic algorithms over multiple processors while introducing a new genetic operator, the migration operator, able to improve the overall algorithmic performance. In this chapter we introduce the generalized island model that can be applied to a broad class of optimization algorithms. First, we study the effect of such a generalized distribution model on several well-known global optimization metaheuristics. We consider some variants of Differential Evolution, Genetic Algorithms, Harmony Search, Artificial Bee Colony, Particle Swarm Optimization and Simulated Annealing. Based on an set of 12 benchmark problems we show that in the majority of cases introduction of the migration operator leads to obtaining better results than using an equivalent multi-start scheme. We then apply the generalized island model to construct heterogeneous “archipelagos”, which employ different optimization algorithms on different islands, and show cases where this leads to further improvements of performance with respect to the homogeneous case.


Ruciński, M., Izzo, D., & Biscani, F. (2010). On the impact of the migration topology on the Island Model. _Parallel Computing_, 36(10-11), 555-571.

Parallel Global Optimization Algorithms (PGOA) provide an efficient way of dealing with hard optimization problems. One method of parallelization of GOAs that is frequently applied and commonly found in the contemporary literature is the so-called Island Model (IM). In this paper, we analyze the impact of the migration topology on the performance of a PGOA which uses the Island Model. In particular we consider parallel Differential Evolution and Simulated Annealing with Adaptive Neighborhood and draw first conclusions that emerge from the conducted experiments.


Izzo, D., Ruciński, M., & Ampatzis, C. (2009). Parallel global optimisation meta-heuristics using an asynchronous island-model. _IEEE Congress on Evolutionary Computation (CEC 2009)_ (pp. 2301-2308). IEEE.

We propose an asynchronous island-model algorithm distribution framework and test the popular differential evolution algorithm performance when a few processors are available. We confirm that the island-model introduces the possibility of creating new algorithms consistently going beyond the performances of parallel differential evolution multi starts. Moreover, we suggest that using heterogeneous strategies along different islands consistently reaches the reliability and performance of the best of the strategies involved, thus alleviating the problem of algorithm selection. We base our conclusions on experiments performed on high dimensional standard test problems (Rosenbrock 100, Rastrigin 300, Lennard Jones 10 atoms), but also, remarkably, on complex spacecraft interplanetary trajectory optimisation test problems (Messenger, Cassini, GTOC1). Spacecraft trajectory global optimisation problems have been recently proposed as hard benchmark problems for continuous global optimisation. High computational resources needed to tackle these type of problems make them an ideal playground for the development and testing of high performance computing algorithms based on multiple processor availability.


## Using PaGMO ##
Izzo, D., Simões, L. F., Märtens, M., de Croon, G. C. H. E., Heritier, A., & Yam, C. H. (2013). Search for a Grand Tour of the Jupiter Galilean Moons. In C. Blum (Ed.), Genetic and Evolutionary Computation Conference (GECCO 2013) (pp. 1301–1308). New York, USA: ACM Press.

We make use of self-adaptation in a Differential Evolution algorithm and of the asynchronous island model to design a complex interplanetary trajectory touring the Galilean Jupiter moons (Io, Europa, Ganymede and Callisto) using the multiple gravity assist technique. Such a problem was recently the subject of an international competition organized by the Jet Propulsion Laboratory (NASA) and won by a trajectory designed by aerospace experts and reaching the final score of 311/324. We apply our method to the very same problem finding new surprising designs and orbital strategies and a score of up to 316/324.


J. Llorens, I. Prieto, L. Munioz-Camuniez, and P. Postigo, "Analysis of the strong coupling regime of a quantum well in a photonic crystal microcavity and its polarization dependence studied by the finite-difference time-domain method," J. Opt. Soc. Am. B 30, 1222-1231 (2013).

We provide a methodology for the study of a photonic crystal microcavity and a quantum well (QW) in the strong coupling regime by finite difference in the time domain. Numerical results for an InP L7 photonic crystal microcavity coupled to an ideal QW are provided. A comparison of the time analysis processed by the discrete Fourier transform, the Padé approximant, and harmonic inversion is presented to optimize the computation time. We present a method to solve the uncertainty of the frequency spectrum depending on the starting time used in the spectral analysis. The influence of polarization anisotropy on strong coupling is studied. The Rabi splitting is exactly zero only when the induced polarization in the QW is aligned with a field component incompatible with the symmetry of the mode.


Kaleem, M. K., & Leitner, J. (2011). CUDA Massively Parallel Trajectory Evolution. _GPUs for Genetic and Evolutionary Computation competition at the 2011 Genetic and Evolutionary Computation Conference_ (GECCO 2011).

"[...] Over the last year the aim was set to implement capabilities to run the PaGMO optimization heuristics on GPU architectures. As a starting point the evolving docking problem was chosen, which aims to design a neuro-controller for the automatic rendezvous and docking task in spacecraft operations. A genetic algorithm is used to search for a neural network that controls the spacecraft [...]"


Ampatzis, C., Izzo, D., Ruciński, M., & Biscani, F. (2009). ALife in the Galapagos: migration effects on neuro-controller design. In G. Kampis, I. Karsai, & E. Szathmáry (Eds.), _Proceedings of the European Conference on Artificial Life (ECAL 2009)_ (pp. 197-204). Springer.

The parallelization of evolutionary computation tasks using a coarse-grained approach can be efficiently achieved using the island migration model. Strongly influenced by the theory of punctuated equilibria, such a scheme guarantees an efficient exchange of genetic material between niches, not only accelerating but also improving the evolutionary process. We study the island model computational paradigm in relation to the evolutionary robotics methodology. We let populations of robots evolve in different islands of an archipelago and exchange individuals along allowed migration paths. We show, for the test-case selected, how the exchange of genetic material coming from different islands improves the overall design efficiency and speed, effectively taking advantage of a parallel computing environment to improve the methodology of evolutionary robotics, often criticized for its computational cost.


Clone this wiki locally