GSoC 2014
Here we are again, ready to start a new coding adventure!!!
These are some projects we propose for the 2014 application of PaGMO/PyGMO to the Google Summer of Code. In case PaGMO/PyGMO will be selected as a mentoring organization we will pick the projects to actually carry out according to the best applications received. You can also submit your own idea on what part of PaGMO you would like to develop, in which case provide as many details as possible in your application so that we can look for the best possible mentorship.
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.
We would like to provide optimization, and hence PyGMO, as a service for the users. To do so we need to construct a web interface for PyGMO where the user can define the optimization problem, select one of the available algorithms, construct the archipelago (see "Archipelago Builder and Inspector" project, for the "PyGMO goes online" project only single thread optimization is considered but it need to be designed extendible to archipelago architectures), and follow in real time the results of its evolution. The web module will be released to be deployed on private server to control the access of the user and avoid for the time being malware detection.
The student will be mentored to implement a web module that will provide as many as possible of the following functionality:
- definition of an optimization problem (following the PyGMO specifications) in an embedded python notebook framework or by uploading python files that need to be parsed for compatibility with the PyGMO problem definition,
- selection of one of the available algorithms and tuning of its parameters (a list of algorithms that suits the given problem need to be returned to the user, according to the problem characteristics: continuous/combinatorial, constrained/unconstrained and single/multi objective),
- representation of the evolution with some preliminary statistics (something inspired to this),
- log of the optimization processes running on the server,
- possibility to generate a Python file with the sequence of PyGMO instructions needed to achieve the setup configured through the web interface.
Implementation Details: The editing environment for the problem definition can be developed embedding one of the existing open source code editor such as Ace. The parsing of custom python files, can be performed by a Python module running on the server. The web interface is developed using HTML5. For the graphical representation of the evolution and the possibility to interact with its solution Javascript will be used.
The student is asked to write clean and well documented code.
Skills Required: Web programming skills (HTML5, Javascript) and Python
Skills that help: Previous experience with web development and evolutionary optimization... being creative!
Mentors: Mentors#Lisa, Mentors#Dario
The standard PyGMO working cycle is to build an archipelago and run evolutions on it. This is usually done constructing islands and pushing them back into the archipelago. Then evolution starts. Then the optimized results are inspected. With this project we want to build a graphical interactive archipelago builder (GIABU) to be embedded in the future into the PyGMO web interface. The user will be given the possibility to select via simple gestures (drag and drop) and menus the algorithm in each island, the migration paths and policies. He will be able to follow up the migrants and study what is working and what is not to then resume the evolution at the archipelago level after having changed some of the islands, e.g. the algorithm or the selection policies etc.
The student will be mentored to implement a Java script module that will provide as many as possible of the following functionality:
- selection and tuning of optimization algorithms exposed in PyGMO;
- graphical configuration of the multiple sub-populations (islands) to undergo optimization. This includes setting up the topology of the archipelago, the multiple algorithms controlling each island, and the migrations between islands;
- possibility to generate a Python file with the sequence of PyGMO instructions needed to achieve the setup configured in the graphical application, either for loading back in future optimizations, or for the user to then manually extend the setup according to his/her needs;
- plots updated in real-time with statistics from ongoing optimizations (at the level of the archipelago, but also of individual islands);
- visualization and inspection of solutions along the Pareto front in optimizations with two and three objectives;
- Parallel coordinates visualization showing relationships between performance and values in the multiple variables under optimization (ideally with a degree of interactivity similar to the one provided by parvis);
Implementation Details: The graphical interface will essentially serve to instantiate and explore interactively an object of the class PyGMO.archipelago. This is a rather complex object containing (essentially) a PyGMO.topology and a number of PyGMO.islands Each PyGMO.island contains a PyGMO.algorithm and a PyGMO.population. Each PyGMO.population contains a set of individuals and a PyGMO.problem. D3 could be the underlying tool to achieve this goal, but other equivalent graphical libraries can also be proposed (such as Raphael and WebGL).
A static, non-interactive visualization of archipelago topologies is already provided through the NetworkX library (see PyGMO/topology/init.py). The student may build on top of this structure, or re-implement a more suited visualization. The student is asked to write clean and well documented code.
Skills Required: Knowledge of Javascript and HTML5
Skills that help: An artistic sense for the beautiful & functional!
Mentors: Mentors#Daniel, Mentors#Jacco
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.
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 Genetic Algorithm). The project aim to extend the class of heuristic algorithms able to tackle discrete optimization problems and including well established deterministic 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:
- Implement as priority the Ant Colony Optimization framework. If possible (time constraint) also the implementation of the Branch and Bound framework is forseen as a task for this project.
- Test the implemented algorithms on the set of discrete benchmark problems already available in the PaGMO/PyGMO framework. The PaGMO/PyGMO framework already include an implementation of the Traveling Salesman Problem (TPS). The expansion of this class of problems, including all the variations retrieved from benchmarking test suites such as this is task of the student for this project, together with the implementation of a simple graphical visualization of the TSP problem. [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.
Implementation Details: For each family of algorithms (ACO and BB) create a class that inherits from the base class pagmo::algorithm::base (algorithm/base.h algorithm/base.cpp). The method evolve of the class, that takes as argument an instance of the population, contains most of the juice of specific algorithms. The implementation of a new class of problem, derived from the problem base class pagmo::problem::base (problem/base.h problem/base.cpp) is also necessary due to the problem-dependent nature of the algorithms.
The student is asked to write clean and well documented code.
Skills Required: Programming skills (C++, Python)
Skills that help: Previous experience in optimization... being able to count till 100
Mentors: Mentors#Lisa, Mentors#Paul, Mentors#Marcus
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