GSoC2020 project ideas
Pagmo is a C++ scientific library for massively parallel optimization. It is built around the idea of providing a unified interface to optimization algorithms and problems, and to make their deployment in massively parallel environments easy. Started 2006 as a passion project of researchers at the European Space Agency (ESA), pagmo originated as a tool for optimizing trajectories, but its capabilities are far more general. Some of pagmos key features are
- comprehensive library of solvers, including state-of-the art bio-inspired algorithms
- cross-platform: works on Windows, Linux and MacOS
- island model for coarse-grained and customizable parallelization
- batch-fitness evaluation for fine-grained parallelization
- fast hypervolume computation
- multi- and many-objective optimization
- constraint handling techniques
More about pagmos capabilities.
Pagmo received a major update (from veresion 1.x to 2.x) in the recent years, which included a complete recoding in modern C++11 (with some features from C++14/17). Our new codebase makes it much easier to extend pagmo and covers already all core features of the - no longer supported - previous version. However, some legacy features still require porting and many new ideas have emerged within this process.
Before the update, pagmo was already selected twice for the Google Summer of Code:
We welcome motivated students, who would like to become part of our development team and like to help us making pagmo even better. If you are interested, you can find general information and some of our project ideas below.
All students interested in applying should have
- Working knowledge in development with modern C++ (C++11/14/17)
- Working knowledge in development with Python (for the pygmo-interface)
- Experience in using git, git workflows and online repositories like github
Not necessary, but nice to have:
- Solid understanding of parallel programming (synchronization, threads, processes, mutex, etc.)
- Experience with continuous integration and testing
- Basic understanding of optimization
Additionally requirements might be needed depending on project idea.
In case pagmo is selected as a mentoring organization for GSoC2020, we will select the projects to be carried out in accordance with the number of slots and the best applications received. Thus, we give priority to the projects where we have strong candidates.
As an applicant, we recommend to try out pagmo by installing pygmo first, as this is the most common way how our software is used for science and production. You could run for example some of our tutorials either in Python or C++ to understand what this software is about. Play with it and try to solve some of our optimization problems!
Next step would be to check out our codebases for pagmo/pygmo on github, including our coding guidelines.
Interaction with the development community before, during and after the actual project duration is one of the key element of success for all projects. We invite you to say hello to us in our GSoC2020 channel on gitter.im. If you want to prove your skills to us, you are also welcome to propose and implement small additions to pagmo or tackle some of our open issues (pagmo/pygmo) together with us.
Lastly, you may want to have a look at the scientific references that we have included for each project, but you do not need to be too concerned about it: our mentors are all qualified scientific programmers/researchers that are well versed within the field. They are willing to bring people into the science of optimization/evolutionary computation, doing their best to make pagmo/pygmo programming a rewarding experience also from the scientific point of view.
Background: Multi-objective optimization problems arise frequently as the result of design optimization:
- the car should be lightweight but also robust
- the notebook should have a high performance but also conserve battery
- the spacecraft should reach its destination orbit as fast as possible by spending as little fuel as possible
These examples highlight a common issue: designers often want multiple objectives to be optimal at the same time. As those objectives usually conflict with each other, optimal trade-off solutions are searched, where one of the objectives may not be improved without sacrificing another objective (see: Pareto efficiency).
Pagmo is capable of multi-objective optimization (see Tutorial) by deploying specific multi-objective algorithms like NSGA-II or MOEA/D.
Project Details: This project is about enhancing the multi-objective features of pagmo by the use of quality indicators.
The project consists of two parts: the first part is about refactoring and extending the hypervolume computation capabilities of pagmo, which have been ported from the legacy version, but are currently incomplete and require some modernization. The computation of the hypervolume, while it is relatively simple to understand, can be fairly tricky in practice, as a high computational speed is desired.
The second part is about implementing new quality indicators into pagmo, that have not been there before. Having a variety of quality indicators at disposal is very useful, as they are frequently deployed as building blocks for multi-objective algorithms and are helpful in quality assessment. Indicators of particular interest are:
- inverted generational distance, inverted generational distance+ [1]
- additive epsilon indicator [2]
- R-indicators (R2) [3]
- (empirical) attainment function [4]
- averaged Hausdorff-distance [5]
Additionally, new visualization methods like (parallel cooordinates, radar plots, Andrew curves, etc.) shall be added to pygmo to aid visual inspection of solution sets.
The students task will be to implement as many of the above listed features as possible. Additional features to expand the multi-objective capabilities can be discussed with the mentor. Since quality indicators are at the core of many algorithms, the implementations need to be reliable, fast, well tested and thoroughly documented. Part of the project will also be devoted to bench-marking the performance of the different quality indicators and their potential combinations.
Desired skills: C++, Python, ability to think and code in at least n dimensions (without getting dizzy)
Mentors: Marcus Märtens, Dario Izzo
References:
[1] Hisao Ishibuchi, Hiroyuki Masuda, Yuki Tanigaki, and Yusuke Nojima. Modified Distance Calculation in Generational Distance and Inverted Generational Distance. In Antonio Gaspar-Cunha, Carlos Henggeler Antunes, and Carlos Coello Coello, editors, Evolutionary Multi-Criterion Optimization, 8th International Conference, EMO 2015, pages 110–125. Springer. Lecture Notes in Computer Science Vol. 9019, Guimaraes, Portugal, March 29 - April 1 2015
[2] Eckart Zitzler, Lothar Thiele, Marco Laumanns, Carlos M. Fonseca, and Viviane Grunert da Fonseca. Performance Assessment of Multiobjective Optimizers: An Analysis and Review. IEEE Transactions on Evolutionary Computation, 7(2):117–132, April 2003.
[3] Dimo Brockhoff, Tobias Wagner, and Heike Trautmann. On the Properties of the R2 Indicator. In 2012 Genetic and Evolutionary Computation Conference (GECCO’2012), pages 465–472, Philadelphia, USA, July 2012. ACM Press. ISBN: 978-1-4503-1177-9.
[4] Carlos M. Fonseca, Viviane Grunert Da Fonseca, Luis Paquete Exploring the Performance of Stochastic Multiobjective Optimisers with the Second-Order Attainment Function, EMO (2005)
[5] Oliver Schutze, Xavier Esquivel, Adriana Lara, and Carlos A. Coello Coello. Using the Averaged Hausdorff Distance as a Performance Measure in Evolutionary Multiobjective Optimization. IEEE Transactions on Evolutionary Computation, 16(4):504–522, August 2012.
Background: A large number of open source projects offering optimization algorithms and metaheuristics have a decent maturity and can be interfaced to pygmo.
- https://github.com/fmfn/BayesianOptimization
- https://stefan-endres.github.io/shgo/
- https://platypus.readthedocs.io/en/latest/
- https://docs.scipy.org/doc/scipy/reference/tutorial/optimize.html
These examples are all in pure python (thus contributing to pygmo code base). More can be proposed for our consideration.
Project Details: This project is based in answering to the community need to have more solvers available as shipped UDAs (User Defined Algorithm) in pygmo. The opened issues #77, #356, #362 are, for example, related.
Wrapping new third party solvers requires
- to agree on the wrapping API.
- to check that the third party code is maintained and distributed at a sufficient level to be considered trustworthy.
- to write the wrapping code so that corresponding pagmo UDAs are made available.
- to test the functionality (beyond unit tests also performing some algoritmic performance tests).
- to write docs and tutorials on the new UDAs.
In the course of the project we expect, at a minimum, Platypus and Scipy algorithms to be interfaced, plus a few proposals form the student.
Desired skills: Python, ability to think and code in at least n dimensions (without getting dizzy)
Mentors: Dario Izzo, Francesco Biscani, Moritz v. Looz
Background: A large number of open source projects offering optimization algorithms and metaheuristics have a decent maturity and can be interfaced to pagmo.
These examples are all in C/C++ (thus contributing to pagmocode base). More can be proposed for our consideration.
Project Details: This project is based in answering to the community need to have more solvers available as shipped UDAs (User Defined Algorithm) in pagmo. The opened issues #77, #356, #362 are, for example, related.
Wrapping new third party solvers requires
- to agree on the wrapping API.
- to check that the third party code is maintained and distributed at a sufficient level to be considered trustworthy.
- to write the wrapping code so that corresponding pagmo UDAs are made available.
- to test the functionality (beyond unit tests also performing some algoritmic performance tests).
- to write docs and tutorials on the new UDAs.
In the course of the project we expect, at a minimum, Nomad and Bonomin to be interfaced, plus a few proposals form the student, possibly including C++ code.
Desired skills: C++, ability to think and code in at least n dimensions (without getting dizzy)
Mentors: Dario Izzo, Francesco Biscani, Moritz v. Looz