SOCIS 2014
These are some projects we propose for the 2014 application of PaGMO/PyGMO to the ESA Summer of Code in Space. In case PaGMO/PyGMO will be selected as a mentoring organization we will pick the projects to actually carry out according to the quality of the received student applications
Start to get familiar with the code by:
- In Python: install the PyGMO module for your python2.7 (the port to python 3 is under review). Follow the online PyGMO tutorials
- In C++: get familiar with the classes problem.base, algorithm.base and topology.base
- Instantiate some archipelagos with homogeneous and heterogeneous algorithms
- Analyze results from some optimization
- Contact us via the IRC channel, mail or mailing-list as to ask for more details on what is in our mind for the particular project you are interested in.
Interaction with the PaGMO/PyGMO community before, during and after the actual project duration is one of the key element of success for all projects.
Check the PyGMO dedicated web site !!
Check also some more information on the mentors!!
IMPORTANT: we want to make science while having fun! No background is required for the development of the projects below, but programming. 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, doing their best to make PaGMO/PyGMO programming a rewarding experience also from the scientific point of view.
An optimization problem where the optimization variables are restricted to assume integer values belongs to the family of discrete or combinatorial optimization problems. Shortest path problem, Knapsack problem and scheduling problem are an example of typical combinatorial optimization problems. In Aerospace engineering, some complex interplanetary optimization problems, planning and scheduling of robotic exploration or Earth observation are common examples.
The optimization techniques used for solving real variable optimization problems are not suitable for solving this class of problems. Currently in PyGMO few heuristic techniques are able to tackle integer optimization variables (namely Improved Harmony Search, Monte Carlo Search and a Simple Genetic Algorithm). The project aim to extend the class of heuristic algorithms able to tackle discrete optimization problems and including Ant based techniques.
In particular the following algorithms have been selected for the different way of tackling the integer nature of the problem:
- Ant Colony Optimization (ACO) [1]: it is a probabilistic optimization technique inspired by the behavior of ants in searching good path to food. The algorithm has a lot of variants (Simple Ant System, Elitist Ant System, Rank-Based Ant System, Max-Min Ant System, Ant Colony System). There exists already open source implementation of these algorithms, see this. The wrapping of the existing code into the PaGMO algorithms structure is aimed as one of the scope of this project
- Branch and Bound (BB) [2]: deterministic technique. The solution space is partitioned and the problem resolve on each of the substes. Large subsets of candidate solutions are discarded, by using upper and lower estimated bounds of the quantity being optimized and the partition is repeated recursively. As for the heuristic technique ACO different variants of the branch and bound algorithm exists depending on the nature of the problem (branch and cut, branch and prune).
The task of the student is:
- Program a framework to represent TSP problems in PaGMO. A first attempt was already made and can be found at https://github.com/esa/pagmo/blob/master/src/problem/base_aco.h and https://github.com/esa/pagmo/blob/master/src/problem/tsp.h. Is this rich enough to represent all TSP problem variants? What data structure would be best?. Currently the use of std::vector, does not seem to be the best choice (boost graph? Eigen Matrix?).
- Port benchmarking test suites such as this into pagmo as pagmo::problem::base inheriting objects. Implementation of a simple graphical visualization of the TSP problem.
- Implement as priority the Ant Colony Optimization framework. Code for the different variants should be taken online and wrapped into pagmo
- Time permitting, BB techniques should then be implemented and deployed
The student is asked to write clean and well documented code.
[1] M. Dorigo, Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italy, 1992.
[2] A. H. Land and A. G. Doig (1960). "An automatic method of solving discrete programming problems". Econometrica 28 (3). pp. 497–520.
[3] Radice, Gianmarco, and German Olmo. "Ant Colony Algorithms for Two Impluse Interplanetary Trajectory Optimization." Journal of guidance, control, and dynamics 29.6 (2006): 1440-1444.
[4] Claudio Iacopino et al. "How ants can manage your satellites" - to appear in Acta Futura - [http://congrexprojects.com/docs/default-source/13m13_docs/1140_donati.pdf?sfvrsn=2]
[5] Izzo et al. "Search for a grand tour of the Jupiter Galilean moons" - Gold Humies Award Winner 2013 - [http://www.genetic-programming.org/hc2013/Izzo-Presentation-v2.pdf]
Skills Required: Programming skills (C++, Python)
Skills that help: Previous experience in optimization.
Mentors: Mentors#Lisa, Mentors#Daniel, Mentors#Dario
PyGMO 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 PyGMO archipelago is thread-based for single computer use or supporting MPI for clusters. The MPI based archipelago requires substantial network setup and does not include straightforward out-of-the-box fault tolerance in terms of communication drop-outs, node failures etc. This project will use a modern approach, namely ØMQ, an asynchronous communication layer that it very "light-weight" and does not suffer from the above drawbacks.
Implementation Details:
We target a completely broker-less, peer-to-peer, asynchronous message passing solution for migration of solutions between islands. Topology descriptions (connections between islands) will either be served from one node or alternatively read from a data structure server, e.g.: Redis.
The student is asked to write clean and well documented code.
Skills Required: Programming Skills (C++, Python)
Skills that help: Knowledge of ØMQ (zeromq) and Redis, experience with parallel computing
Mentors: Mentors#Daniel, Mentors#Dario
AMPL is a widely used modeling language for mathematical programming. The aim of the project is to interface AMPL models with PaGMO/PyGMO algorithms. The actual architecture of PaGMO/PyGMO allows the user to define the optimization problem as an instance of a user defined C++ or Python class. The new module need to be able to parse AMPL code, translate it into Python code (making use of already existing attempts to create such interface Amply, [IAmpl] (https://github.com/vitaut/iampl)) or directly creating PyGMO objects. The new interface will improve the PaGMO/PyGMO community outreach.
Implementation Details: We target a first exhaustive translation between AMPL models and PyGMO problems. The student should investigate the already existing open source tentative to interface the two programming languages. The module need to be able to parse the AMPL model file, do a semantic validation of the extracted text and generate the corresponding Python code. Available AMPL trajectory models will be used as test bench for the effectiveness of the translator.
Skills Required: Programming Skills (C++, Python), AMPL
Skills that help: Speak more than one language :)
Mentors: Mentors#Lisa, Mentors#Daniel, Mentors#Dario