GSoC 2013 Multi objective Optimization

Table of Contents Enrichment of the Multi-Objective Optimization Algorithms Set Project Description Code Plan Web Log

Enrichment of the Multi-Objective Optimization Algorithms Set

Project Description

left

At the current state the PaGMO/PyGMO library is able to define and solve single and multi-objective optimization problems. The set of algorithms available to solve multi-objective problems is limited to the genetic algorithm NSGA2 and the Improved Harmony Search. Multi-objective optimization problems more often arise in practical optimization problems where the interested is not limited to minimize a single objective function while to achieve a trade-off between different objectives. In literature several stochastic multi-objective optimization techniques have been developed. The integration of some of them in the current PaGMO/PyGMO framework will be a further enrichment for the library. In particular the following algorithms have been selected for the different way of tackling the multi-objective nature of the problem:

1. MOEA/D [5]: is a multiobjective optimization evolutionary algorithm based on decomposition. It decomposes a multiobjective optimization problem into a set of simple problems and then solves them in a collaborative way.
2. Multi-Objective Particle Swarm Optimization [1]: it uses an external archive and a Pareto ranking schema to evaluate dominance between solutions and a geographically based approach to maintain the diversity.
3. Niched Pareto Genetic Algorithm [2]: the tournament selection into the single-objective genetic algorithm is modified into Pareto dominance tournament. Two individuals randomly chosen are compared against a subset from the entire population, if one is dominated and the other one no, this one is chosen for reproduction, if there is a tie the result of the tournament is decided through a fitness sharing technique that maintains genetic diversity and favor the spread of the solutions along the Pareto front.
4. Strength Pareto Evolutionary Algorithm [3]: it uses an external archive updated at each iteration, it contains the set of non dominated solutions. For each individual in the external set a strength index is computed (used as a fitness), which represents the percentage of individuals in the current population dominated by the solution in the archive.
5. Pareto Adaptive <math>\epsilon</math>-Dominance [4]: meta-algorithm that implements an archive strategy based on adaptive grids along the Pareto front to maintain diversity and cover uniformly the front.

In order to test the algorithms for integer optimization it will be also interesting to reformulate single-objective combinatorial problems (as TSP and Knapsack) as multi-objective problems. This can be done creating a new version of the problem in which constraints are expressed as additional objective functions.

The task of the student is:

• Implement as many multi-objective optimization techniques from the list above as possible referring to the algorithms provided in the literature.
• Test the implemented algorithms on the set of multi-objective benchmark problems already available in the PaGMO/PyGMO framework and possibly expand that suite.

Implementation Details: For each algorithm create a class that inherits from the base class pagmo::algorithm::base (algorithm/base.h algorithm/base.cpp). The NSGA2 (nsga2.h nsga2.cpp) algorithm, the only Multi-objective Optimization strategy currently available, can be used as guideline. The method evolve of the class, that takes as argument an instance of the population, contains most of the juice of specific algorithms.

References

[1] Coello Coello C.A., Salazar Lechuga M. MOPSO : A Proposal for Multiple Objective Particle Swarm, in Congress on Evolutionary Computation, pp. 825-830. IEEE, 2002.

[2] Horn J., Nafploitis N., and Goldberg D. E., A Niched Pareto Genetic Algorithm for Multiobjective Optimization, in Proceedings of the First IEEE Conference on Evolutionary Computation, IEEE Press, pp. 82–87, 1994.

[3] Zitzler, E., Laumanns, M., & Thiele, L. SPEA2: Improving the Strength Pareto Evolutionary Algorithm. Technical Report 103, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH). Zurich, Switzerland, 2001.

[4] Hernandez-Dıaz A.G., Santana-Quintero L.V., Coello Coello C.A., Molina J., Pareto-Adaptive <math>\epsilon</math>-Dominance, Evolutionary Computation , Vol. 15(4), pp 493-517, 2007.

[5] Q. Zhang and H. Li, MOEA/D: A Multi-objective Evolutionary Algorithm Based on Decomposition, IEEE Trans. on Evolutionary Computation, vol.11, no. 6, pp712-731 2007

Skills Required: Good knowledge in C++ and Python

Skills that help: Have a good sense of direction

Mentors: Dario Izzo and Annalisa Riccardi

Student:

Code Plan

17/06 - 30/06 : Litterature reivew of MOEA

30/06 - 10/07 : Implementation of MOEA/D

10/07 - 20/7 : Implementation of Multi-Objective Particle Swarm Optimization

20/07 - 30/7: Implementation of Niched Pareto Genetic Algorithm

01/08 - 10/08: Implementation a multi-objective version of Knapsack and TSP

10/08 - 20/08: Implemention of Strength Pareto Evolutionary Algorithm

20/08 - 30/08 : Pareto Adaptive ε-Dominance

01/09 - 15/09 : Fix documentation and wiki pages about the work undertaken and tests.

Web Log