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

GSoC 2015

Jump to bottom
Krzysztof Nowak edited this page May 21, 2015 · 110 revisions

Table of Contents:

  1. Introduction
  2. First steps and guidelines
  3. Project ideas
  4. PyKEP: Precise solar system ephemerides and Solar Electric Propulsion - difficulty 3/5
  5. PaGMO code reusability improvement
  6. BBOB testbed implementation
  7. Asynchronous communication layer (ØMQ) for the asynchronous island model
  8. Propose your own project

Accepted Projects

We have received many excellent project proposals but this year we could mentor only 2 projects at full capacity. The selected projects are:

Project Student Mentors
BBOB Sunil Mahendrakar Krzysztof Nowak, Dario Izzo
ZeroMQ José Manuel Díez Daniel Hennes, Dario Izzo

Introduction

This the Google Summer of Code 2015 ideas page for the PaGMO & PyKEP mentoring organization. In the following chapters we will provide you with all the necessary information to get familiar with PaGMO and PyKEP and get started on your project.

First steps and guidelines:

Installation

In the remainder of this document you will see three names occurring quite often:

  • PaGMO - The core C++ codebase providing all the optimization features
  • PyGMO - Interface exposing most of the PaGMO C++ functionality to Python
  • PyKEP - The astrodynamics library providing basic tools for Newtonian mechanics and trajectory optimization problem definitions

In order to get started, we suggest first installing PyKEP, using this tutorial: https://esa.github.io/pykep/installation.html), and then PaGMO, along with its Python interface: https://esa.github.io/pygmo/install.html.

In order to get familiar with the general features of the software, we suggest following this quick-start guide, which covers the main features of both packages: https://esa.github.io/pygmo/quickstart.html.

Contact us

If you find any problems with running PaGMO/PyKEP on your local machine please contact us on our corresponding gitter channels:

if you think you're ready and would like to get started on a project contact us on our dedicated GSOC gitter channel, or contact one of our mentors. We find from experience that the interaction with the PaGMO/PyKEP community before, during and after the actual project duration is one of the key element of success for all projects!

Contribution before student application period

If you feel comfortable with the codebase, and feel like providing small contribution to PaGMO (+ convince us about your coding skills 😉 ) we suggest investigating and closing some of the small PaGMO issues tagged beginner

Project ideas

In this section we propose several project ideas, which we think would benefit PaGMO/PyKEP the most. When defining the project we made sure that no additional background is required for carrying out the project, but software engineering and C++/Python programming skills. The mentors are all qualified scientific programmers/researchers competent on the scientific part of the project. They are willing to bring people into the science of optimization, evolutionary computation and celestial mechanics, doing their best to make PaGMO/PyKEP programming a rewarding experience also from the scientific point of view.

1. PyKEP: Precise solar system ephemerides and Solar Electric Propulsion - difficulty 3/5

PaGMO and PyKEP, although maintained as separate packages, are developed concurrently by the same team of developers with the shared goal in mind: pushing the frontier of the evolutionary approaches in the aerospace engineering and spacecraft mission planning. Although PaGMO is the main tool in this composition, PyKEP plays an important role in problems definition and celestial mechanics computations. The goal of this project is enriching PyKEP with the possibility to:

  • Use JPL DE ephemerides (e.g. DE430) for solar system planets and moons. This should be using some wrapper around the SPICE toolkit (http://naif.jpl.nasa.gov/naif/toolkit.html)
  • Introduce the possibility to have the spacecraft low-thrust as a function of solar distance and time as to be able to model Solar Electric Propulsion (at the moment only Nuclear Electric Propulsion is allowed) in the Sims-Flanagan model (both impulsive and continuous thrust)

Although the knowledge of celestial mechanics is a valuable asset, it is not necessary as long as the student is willing to get familiar with the basic concepts through the help of the mentor.

Implementation Details:

For the first part of the project we would like to have a simple interface such as:

from PyKEP import *
pl = planet_spice(name = "jupiter", observer = 'ssb', eph_file='./eph/de430.bin', ref ='J2000') # here planet_spice object derives from  planet and re-implements the eph method
r,v = pl.eph(epoch(5700,"mjd2000")) # here the actual computations are made

All needed external files (to contain the binary ephemerides) will have to be downloaded by the user prior to the use of these calls and check for integrity at run-time. PyKEP could also offer as an utility to convert ASCII ephemerdies to binaries (optional)

For the second part of the project we will need to re-think the spacecraft class, adding an engine class that describes the propulsion characteristics (i.e. the time and distance dependence of the thrust). This would, in turn, have to feedback into the leg class without impacting its current efficiency. Essentially this paper would be a good starting point for the student to look into the issue from a physics point of view. (https://engineering.purdue.edu/people/james.m.longuski.1/JournalArticles/2003/DesignandOptimizationofLow-ThrustTrajectorieswithGravityAssists.pdf)

Required programming skills: C++, Python, boost-python

Skills that help: Knowledge of Newtonian and space flight mechanics.

Mentors: Mentors#Dario, Mentors#ChitHongYam

2. PaGMO code reusability improvement - difficulty 4/5

The codebase of PaGMO grew bigger over the recent years, often in ways which were not expected at the beginning of the project, e.g. increasing modularity or the recently added utility module pagmo::util during Google Summer of Code 2013. Although we slowly change the code structure towards a more flexible and object-oriented design, some "questionable" design choices we made in the past are still a limit factor. Although most PaGMO/PyKEP have a background in computer science and software engineering, as it is often the case with the scientific software, the legacy code maintenance and performance-driven development often won over the good design practices. Being computing enthusiasts at heart, we have as much of an appreciation to a beautiful design pattern, as we do for an elegant scientific theory.

The aim of this project is redesigning some of the core modules of the projects in order to improve core re-usability, simplify the unit-testing as well as decompose some of the legacy methods of core classes, such as pagmo::population into other modules. Project does not require any knowledge of scientific programming or evolutionary computation. Majority of the project will be enhancing current codebase with good software engineering practices, redesigning some of the code structure, writing unit-tests and documenting the interface changes.

Implementation Details:

This section provides some details on the project implementation and time-schedule.

The student will work mostly with the PaGMO code (C++), and to a lesser degree also with Python interface. An example of software engineering , and decompose some of the "rigid" data-structures and methods of core classes such as pagmo::population into separate pagmo::util module, as well as move some of the reusable portions of the pagmo::algorithm and pagmo::problem into base classes. A second part of the project would be supplementing the code with unit-tests coverage.

For example, the pagmo::population class contains several evaluation metrics (e.g., pagmo::population::compute_pareto_fronts) which are specific to multi-objective optimization problems - this is confusing and not consistent with other sections of the codebase which are already separated (e.g., pagmo::util::hypervolume). A typical use-case of classical pareto-dominance metric is as follows:

from PyGMO import *
p = population(...)
par_fronts = p.compute_pareto_fronts()  # This is current way of computing the pareto fronts
par_rank = p.get_crowding_d(0)          # and the crowding distance for given individual

This is not an elegant design, as population object is not inherently connected to the concept of pareto-dominance. Below we propose a desired way of achieving the same:

from PyGMO.util import pareto  # import the pareto-related metrics
par = pareto(p)  # Instantiate the pareto metric
par_fronts = par.compute_fronts()  # Compute the pareto fronts
par_rank = par.get_crowding_d(0)  # Compute the crowding distance

Other examples of improvements include:

  1. Re-usability of the validation sections of the code in each of the algorithms and problems (i.e. checking the type of the problem, single/multi objective etc.) into base classes.
  2. Unit test coverage (both C++ and Python interface) for core PaGMO classes (population, problem, algorithm, island, archipelago).
  3. Supplementing the problems with the implementations of pagmo::problem::get_best_x, pagmo::problem::get_best_f and pagmo::problem::get_best_c methods.
  4. (If time permits) More efficient implementation and performance evaluation of the pareto metrics.

Required programming skills: C++, Python

Skills that help: Good knowledge of object-oriented programming.

Mentors: Mentors#Krzysztof, Mentors#Marcus

3. BBOB testbed implementation - difficulty 3/5

Performance evaluation metrics for evolutionary algorithms are crucial component for parameter tuning, testing new algorithm and problems, as well as characterizing and explaining the properties and behavior of algorithms by statistical runtime comparisons. One such performance evaluation testbed is the Real-Parameter Black-Box Optimization Benchmark (BBOB). The aim of this project is adding a new module to pagmo::util containing several performance evaluation methods from BBOB 2015 experimental setup (see [1] and [2]). The completed module will allow the users to run vast benchmarking campaigns, and analyze the performance of algorithms and initial parameters over a large sets of problems. Student is expected to get familiar with the performance evaluation methods of evolutionary algorithms (with the help of the mentor)

[1] Real-Parameter Black-Box Optimization Benchmarking: Experimental Setup. PDF with explanation and source code

[2] Nikolaus Hansen and Anne Auger. "Performance evaluation of an advanced local search evolutionary algorithm". In In Proceedings of the IEEE Congress on Evolutionary Computation. IEEE Press, 2005 ONLINE

Implementation Details:

The student will extend the pagmo::util module with the pagmo::util::bbob module (as well as interface it to PyGMO's PyGMO.util.bbob). Where possible, the existing reference code should be reused and wrapped as C++ classes. Second part of the project will be dedicated to enriching PyGMO with results visualization (using matplotlib) and writing interface for a more extensive experimental setups (e.g. large benchmarking campaigns over many problems and algorithms).

An example for individual algorithm comparison:

from PyGMO import *
from PyGMO.util import bbob

ert = bbob.compute_ert(algorithm.jde(variant=2, gen=20), problem.rosenbrock(10), n_runs=1000)  # Compute the expected running time data
bbob.plot_cumulative_distribution(ert)  # Presents the results on a cumulative distribution plot

Required programming skills: Python , C++

Skills that help: Knowledge of statistical testing, matplotlib and data presentation

Mentors: Mentors#Krzysztof, Mentors#Dario

##4. Asynchronous communication layer (ØMQ) for the asynchronous island model - difficulty 4/5

PaGMO provides powerful parallelization built around the generalized island-model paradigm ("optimization in an archipelago of islands"). The optimization algorithms are automatically parallelized (asynchronously, coarse-grained approach) thus making efficient use of todays multi/many-core architectures. Islands may run in complete isolation in parallel but once candidate solutions start to migrate between islands the optimization process is speed up. The current implementation of the island model in PaGMO is mainly based on the two classes island_base and archipelago. The island_base class is a polymorphic class that takes care of starting computational tasks. Currently three tpyes of islands are available. A POSIX type of island (spawning a thread), a python type of island (spawning a process), and an MPI island.

This project will make use of a modern approach, namely ØMQ, an asynchronous communication layer that it very "light-weight" to define a new type of island (the ØMQ island) able to communicate to similar islands (anywhere in the network) and exchange information (regardless of their belonging or not to an archipelago object). This would allow an easy access to grid-computing architectures where different machines could be running isolated ØMQ island (on the same "topic") or have them embedded in some local archipelago and still have communication (migration) happening via the network.

Implementation Details:

We target a completely broker-less, peer-to-peer, asynchronous message passing solution for migration of solutions between islands.

Computer 1:

isl = island_zeromq(algo, prob, 20, topic="cool_stuff")
isl.evolve(100)

... in the meantime, somewhere else ....

Computer 2:

isl = island_zeromq(algo, prob, 20, topic="cool_stuff")
isl.evolve(100)

In this setup the two islands would be exchanging individuals as they are subscribed to and talk on the same topic (and only in case the exchange makes sense, i.e., same problem dimensions). The island_zeromq could also, on one or both computers, be embedded into a local archipelago containing other (non-ØMQ) islands. Here is an example of a more complex setup, connecting three local archipelagos (I, J, K) with three ØMQ connections (dashed edges):

Required programming skills: C++, Python

Skills that help: Knowledge of ØMQ (zeromq) and Redis, experience with parallel computing

Mentors: Mentors#Daniel, Mentors#Dario

##5. Propose your own project! - difficulty ?/5 Do you have an idea on how to improve PaGMO/PyKEP ? - Share it with us!

Since PaGMO/PyKEP packages were of scientific and exploratory nature from the very beginning, we are always looking forward to enhancing it with new optimization algorithms, data visualization techniques or a new paradigm for more efficient computation and parallelism. We find that students are often the most motivated when they can pursue their own idea. Even if you don't have any concrete ideas but an expertise in some branch of computer science or software development, feel free to contact us and we might forge an idea for a possible project together. In that case, the sooner you contact us the better, as we need to make sure we will be able to find the mentor for the project.

Clone this wiki locally