# Subpages

IMPORTANT: This project was finished Oct 2013. All information on these pages (especially related to the algorithms) might be outdated.

# Original Project Description for hyperfast hypervolumes

Multi-objective optimizers usually do not search for the single best solution of a problem, because there is not such a thing if you have more than 1 objective. Instead, they create a set of solutions that represent the best-possible trade-offs between all involved objectives. These solution-sets are called Pareto-approximations, as they try to approximate the Pareto-front of the problem.

While a comparison of two solutions with respect to a single objective is straight-forward (take the better one), assigning a quality to a whole Pareto-approximation is a difficult matter. The hypervolume indicator can be used to assign a quality to a Pareto-approximation, defined by the volume of the fitness space that is dominated by the Pareto-approximation. It is the only unary single set quality measure that is known to be strictly monotonic with regard to Pareto dominance (That is, the Pareto-optimal front guarantees the maximum possible hypervolume while any worse set will assign a lower hypervolume). This is nice, since now we can compare different solution sets and take the one with the best hypervolume.

As determining the exact hypervolume of a number of points is computationally #P-hard [1], most exact computations unfortunately scale exponentially in the number of objectives. However, recent advances in the research on multi-objective optimization provide fast approximations on a reasonable precision that will allow not only to use the hypervolume to judge the quality of an algorithm, but also to design efficient evolutionary algorithms based on the hypervolume as a mechanism for selection, diversification or archiving. Thus, the hypervolume is an extremely versatile concept and would significantly level up PaGMOs capabilities for multi-objective optimization! We suppose, the students tasks should consist of

• Adding exact and approximative methods for the computation of the hypervolume (candidates could be from [1], [2], [3], [5], [6])
• Testing the performance and quality of the approximations for varying parameters on the available multi-objective problems of PaGMO
• Adding one or more multi-objective algorithms based on the hypervolume indicator (a candidate could be Hype [2] or maybe SMS-EMOA [7])
• Implementing an efficient migration operator based on the contribution of single individuals to the hyper-volume (preferably based on [4])

Implementation Details: the population class needs to be enhanced by a method get_hypervolume. Given a set of reference points (a vector of fitness vectors) the method shall return a value reflecting the exact hypervolume of the population corresponding to the reference points. An optional keyword 'variant' shall be used to switch between the exact computation and different approximative methods. All algorithms using the hypervolume are supposed to use the functionalities of the population class and not to compute the hypervolume by themselves!

A new replacement policy has to be added based on the exclusive hypervolume (i.e. the contribution of a single individual to the collective hypervolume). This replacement strategy should select the n members of the population which contribute the least to the hypervolume. Accordingly, a new selection policy shall send migrants with high contribution to the hypervolume in the their home population to other populations.

All functionalities need to be written in clean and documented C++ code and made available for the Python interface. Automated functional tests need to be added to PaGMO as well.

References

[1] Bringmann, Karl, and Tobias Friedrich. "Approximating the least hypervolume contributor: NP-hard in general, but fast in practice." Theoretical Computer Science 425 (2012): 104-116. paper

[2] Bader, Johannes, and Eckart Zitzler. "HypE: An algorithm for fast hypervolume-based many-objective optimization." Evolutionary computation 19.1 (2011): 45-76. paper

[3] Fonseca, Carlos M., Luıs Paquete, and Manuel López-Ibánez. "An improved dimension-sweep algorithm for the hypervolume indicator." Evolutionary Computation, 2006. CEC 2006. IEEE Congress on. IEEE, 2006.

[4] Bradstreet, Lucas, Lyndon While, and Luigi Barone. "A fast incremental hypervolume algorithm." Evolutionary Computation, IEEE Transactions on 12.6 (2008): 714-723. paper

[5] Guerreiro, Andreia P., Carlos M. Fonseca, and Michael TM Emmerich. "A Fast Dimension-Sweep Algorithm for the Hypervolume Indicator in Four Dimensions." paper

[6] Emmerich, Michael, and Carlos Fonseca. "Computing hypervolume contributions in low dimensions: asymptotically optimal algorithm and complexity results." Evolutionary Multi-Criterion Optimization.

[7] Beume, Nicola, Boris Naujoks, and Michael Emmerich. "SMS-EMOA: Multiobjective selection based on dominated hypervolume." European Journal of Operational Research 181.3 (2007): 1653-1669.

Skills Required: Good knowledge in C++, Python

Skills that help: Thinking in more than 1 dimension, understanding of high dimensional geometries, the concept of Pareto-dominance and not being too afraid of recursion

Mentors: Marcus Märtens and Luís F. Simões

Fr 21.6 - Deadline: Lebmeasure, optimal 2D

Mi 26.6 - Deadline: optimal 3D

Di 2.7 - Deadline WFG, 3D, 2D ready to merge to development

Di 16.7 - Deadline: SMS-EMOA working fine

Mo 29.7 - MILESTONE: Midterm done, optimal 2D/3D, WFG, SMS-EMOA and Bringmann are merged

Fr 16.8 - Deadline: HOY, set selection, migration policies

Fr 23.8 - Deadline: FPRAS, HV4D (fast dimension sweep for 4d)

Fr 30.8 - Deadline: HyCon3d, IWFG

Mo 2.9 - MILESTONE: We are ready to merge all features so far (this time for real)

Mo 9.9 - MILESTONE: Pens down, no more coding, writing documentation, tutorials and examples

Mo 16.9 - MILESTONE: End of GSoC

# Use Cases

These are the formal use cases and specifications about how PyGMO should interact with the hypervolume functionalities. All numbers are made up, the syntax should be like that. These are mock IPython commands. A few Use cases describe Errorsituations that are particularly important. Nevertheless, no bad input should result in any computation or crash of PyGMO regardless if there exists a Use Case for it.

## I. Hypervolume object construction

### a) Population

```In[x]: prob = problem.zdt1()
In[x]: pop = population(prob, 100)
In[x]: hv1 = hypervolume(pop)
```

### b) Fixed set of points

```In[x]: ps1 = [[2,3,1],[3,2,1],[3,2,0]]
In[x]: hv1 = hypervolume(ps1)
```
```In[x]: ps2 = ((2,3), (4,1))
In[x]: hv2 = hypervolume(ps2)
```

### Errors

1. Constructor argument is neither population object nor a list/tuple

```In[x]: hv1 = hypervolume("Not a population, list or a tuple")

TypeError: Hypervolume object must be constructed from a list/tuple of points or a population object

In[x]: hv2 = hypervolume([[1,2,3],[2,1,"foo"]])

TypeError: Hypervolume object must be constructed from a list/tuple of points or a population object
```

2. list/tuple provided to constructor is empty/contains incorrect points

```In[x]: hv3 = hypervolume([[],])

ValueError: Points of dimension > 1 required

In[x]: hv4 = hypervolume([[1,],[2,]])

ValueError: Points of dimension > 1 required
```

## II. Hypervolume computation

1. Exact hypervolume

```In [x]: prob = problem.dtlz1(k=18, fdim=5)  # construct 22-dimensional problem with 5 objectives
In [x]: pop = population(prob, 100)
In [x]: hv_obj = hypervolume(pop) # constructs a set of points out of population's invididuals
In [x]: refpoint = [0.7] * 5
In [x]: hv_obj.compute(r=refpoint)
Out [x]: 2315.32
```

Given no algorithm keyword, PyGMO shall determine the fastest algorithm for the hypervolume by itself, execute it and return its result.

2. Exact hypervolume using specific algorithm

```In [x]: prob = problem.dtlz1(k = 18, fdim = 3)  # construct an 20-dimensional problem with 3 objectives
In [x]: pop = population(prob, 100)
In [x]: hv_obj = hypervolume(pop) # constructs a set of points out of population's individuals
In [x]: refpoint = [0.7] * 3
In [x]: hv_obj.compute(r=refpoint, algorithm=hv_algorithm.beume3d())
Out [x]: 3653.32
```

This should trigger the given algorithm for computation, in that case the Beume3D algorithm

3. Error: Bad reference point for hypervolume

```In [x]: prob = problem.dtlz1(k=18, fdim=10)  # construct 27-dimensional problem with 10 objectives
In [x]: pop = population(prob, 100)
In [x]: hypervolume(pop).compute(r=[0.7] * 14)

Value Error: Point set dimensions and reference point dimension must be equal

In [x]: hypervolume(pop).compute(r="Definitely not a list or a tuple")

TypeError: Reference point must be a list/tuple of real numbers, e.g.: r = [1.0, 1.0, 1.0]

In [x]: hypervolume(pop).compute(r=[1.0, 1.0, "foo"])

TypeError: Every item in a referece point list/tuple must be castable to float, .e.g: r=[1, '2.5', 10e-4]

In [x]: hypervolume(pop).compute(algorithm=hv_algorithm.wfg())

TypeError: Reference point (keyword argument 'r') is mandatory
```

4. Error: picking bad algorithm for hypervolume

```In [x]: prob = problem.dtlz1(k=5, fdim=3)  # constructs 7-dimensional problem with 3 objectives
In [x]: pop = population(prob, 100)
In [x]: refpoint = [0.7] * 3
In [x]: hypervolume(pop).compute(r=refpoint, algorithm=hv_algorithm.native2d())

ValueError: native2d algorithm works only for 2-dimensional cases
```

## III. Hypervolume contribution of a single individual

1. Exclusive hypervolume contribution of an individual with specific reference point

```In [x]: prob = problem.dtlz1(k = 18, fdim=3)  # construct 20-dimensional problemlation(prob, 100)
In [x]: hv = hypervolume(pop)
In [x]: refpoint = [1.1] * 3
In [x]: hv.exclusive(p_idx=42, r=refpoint)
Out: 22.0
```

This gives the exclusive hypervolume of the individual with index 42 of the population, using the vector [1.1, 1.1, 1.1] as the reference point.

2. Exclusive hypervolume contribution of an individual with specific algorithm

```In [x]: prob = problem.dtlz1(k = 18)  # construct 18-dimensional problem
In [x]: pop = population(prob, 100)
In [x]: refpoint = [1.1] * 3
In [x]: hv = hypervolume(pop)
In [x]: hv.exclusive(p_idx=42, r=refpoint, algorithm=hv_algorithm.wfg())
Out: 14.0
```

This gives the exclusive hypervolume of the individual with index 42 of the population using the given algorithm, in that case WFG.

3. Error: Bad reference point for hypervolume

```In [x]: prob = problem.dtlz1(k=18, fdim=10)  # construct 27-dimensional problem with 10 objectives
In [x]: pop = population(prob, 100)
In [x]: hv = hypervolume(pop)
In [x]: hv.exclusive(p_idx=42, r=[1.1] * 7, algorithm=hv_algorithm.wfg())  # 7-dimensional reference point to 10 objectives

Value Error: Point set dimensions and reference point dimension must be equal

In [x]: hypervolume(pop).exclusive(p_idx=42, r="Definitely not a list or a tuple")

TypeError: Reference point must be a list/tuple of real numbers, e.g.: r = [1.0, 1.0, 1.0]

In [x]: hypervolume(pop).exclusive(p_idx=42, r=[1.0, 1.0, "foo"])

TypeError: Every item in a referece point list/tuple must be castable to float, .e.g: r=[1, '2.5', 10e-4]

In [x]: hypervolume(pop).compute(algorithm=hv_algorithm.wfg())

TypeError: Reference point (keyword argument 'r') is mandatory
```

4. Error: Picking bad algorithm for hypervolume

```In [x]: prob = problem.dtlz1(k=5, fdim=2)  # constructs 6-dimensional problem with 2 objectives
In [x]: pop = population(prob, 100)
In [x]: refpoint = [0.7] * 2
In [x]: hypervolume(pop).exclusive(p_idx=42, r=refpoint, algorithm=hv_algorithm.beume3d())

ValueError: beume3d algorithm works only for 2-dimensional cases
```

5. Error: Picking bad index for invidivual

```In [x]: prob = problem.dtlz1(k=5, fdim=3)  # constructs 7-dimensional problem with 3 objectives
In [x]: pop = population(prob, 100)
In [x]: refpoint = [0.7] * 3
In [x]: hypervolume(pop).exclusive(p_idx=0.5)

TypeError: individual index (p_idx) must be a non-negative integer

In [x]: hypervolume(pop).exclusive(p_idx=-5)

TypeError: individual index (p_idx) must be a non-negative integer

In [x]: hypervolume(pop).exclusive(p_idx=100000)

ValueError: Index of the individual is out of bounds
```

## IV. Least contributor to the hypervolume within the set of points

1. Determine the least contributor exactly

```In [x]: prob = problem.dtlz1(k=18, fdim=5)  # construct 22-dimensional problem with 5 objectives
In [x]: pop = population(prob, 100)
In [x]: hv_obj = hypervolume(pop) # constructs a set of points out of population's invididuals
In [x]: refpoint = [0.7] * 5
In [x]: hv_obj.least_contributor(r=refpoint)
Out [x]: 13
```

Given no algorithm keyword, PyGMO shall determine the fastest algorithm for the hypervolume by itself, execute it and return its result.

2. Exact least contributor by algorithm

```In [x]: prob = problem.dtlz1(k = 18, fdim = 3)  # construct an 20-dimensional problem with 3 objectives
In [x]: pop = population(prob, 100)
In [x]: hv_obj = hypervolume(pop) # constructs a set of points out of population's individuals
In [x]: refpoint = [0.7] * 3
In [x]: hv_obj.least_contributor(r=refpoint, algorithm=hv_algorithm.beume3d())
Out [x]: 17
```

This should trigger the given algorithm for computation, in that case the Beume3D algorithm

3. Error: Picking bad reference point

```In [x]: prob = problem.dtlz1(k=18, fdim=10)  # construct 27-dimensional problem with 10 objectives
In [x]: pop = population(prob, 100)
In [x]: hypervolume(pop).least_contributor(r=[0.7]*14) # 14-dimensional reference point

Value Error: Point set dimensions and reference point dimension must be equal

In [x]: hypervolume(pop).least_contributor(r="Definitely not a list or a tuple")

TypeError: Reference point must be a list/tuple of real numbers, e.g.: r = [1.0, 1.0, 1.0]

In [x]: hypervolume(pop).least_contributor(r=[1.0, 1.0, "foo"])

TypeError: Every item in a referece point list/tuple must be castable to float, .e.g: r=[1, '2.5', 10e-4]

In [x]: hypervolume(pop).compute(algorithm=hv_algorithm.wfg())

TypeError: Reference point (keyword argument 'r') is mandatory
```

```In [x]: prob = problem.dtlz1(k=5, fdim=3)  # constructs 7-dimensional problem with 3 objectives
In [x]: pop = population(prob, 100)
In [x]: refpoint = [0.7] * 3
In [x]: hypervolume(pop).least_contributor(r=refpoint, algorithm=hv_algorithm.native2d())

ValueError: native2d algorithm works only for 2-dimensional cases
```

```In [x]: ps = [[2,4,5], [4,1,1], [6,2,1]]
In [x]: hv = hypervolume(ps)
In [x]: hv.get_nadir_point()  # by default eps=1.0
Out: (7.0, 5.0, 6.0)
Out: (6.01, 4.01, 5.01)
```

2. Error: Incorrect epsilon for nadir point

```In [x]: ps = [[4,1],[3,2],[2,3]]
In [x]: hv = hypervolume(ps)

ValueError: Epsilon must be a non-negative value.

TypeError: Epsilon must be castable to float.
```

## VI. Multiobjective Algorithms

### SMS-EMOA

1. Optimization with default parameters

```In[x]: from PyGMO import *
In[x]: prob = problem.dtlz(fdim=2)
In[x]: algo = algorithm.sms_emoa()
In[x]: pop = population(prob, 100)
In[x]: for _ in xrange(300):
In[x]:    pop = algo.evolve(pop)
In[x]: pop.plot_pareto_fronts()
```

SMS-EMOA uses hypervolume computation internally to steer the evolution process. This is done automatically, and the best method is chosen dynamically. User can provide a specific algorithm to sms_emoa in order to force a certain algorithm to be used.

2. Optimization using specific hypervolume algorithm

```In[x]: from PyGMO import *
In[x]: prob = problem.dtlz(fdim=7)
In[x]: algo = algorithm.sms_emoa(hv_algorithm=hv_algorithm.wfg())
In[x]: pop = population(prob, 100)
In[x]: for _ in xrange(300):
In[x]:    pop = algo.evolve(pop)
In[x]: pop.plot_pareto_fronts()
```

This time the WFG algorithm will be used for the computation of the hypervolume.

3. Optimization using alternative strategy for dominated fronts

```In[x]: from PyGMO import *
In[x]: prob = problem.dtlz(fdim=2)
In[x]: algo = algorithm.sms_emoa(sel_m=2)  # using alternative strategy
In[x]: pop = population(prob, 100)
In[x]: for _ in xrange(300):
In[x]:    pop = algo.evolve(pop)
In[x]: pop.plot_pareto_fronts()
```

SMS-EMOA is a steady state algorithm, (μ + 1) which requires us to determine the "worst" individual in the population which is targeted for removal. Optional selection principle applies only to the cases where population has more than one pareto front (after non-dominated sorting).

'sel_m' keyword can take two values:

• 1 (default) - remove the individual contributing the least to the hypervolume.
• 2 - remove the individual with the highest domination count.

4. Error: Incorrect value for 'sel_m' argument

```In[x]: algorithm.sms_emoa(sel_m=6)  # non-existing variant

ValueError: selection method must be equal to 1 (least contributor) or 2 (domination count).
```

5. Error: Incorrect type for 'hv_algorithm' argument

```In[x]: algorithm.sms_emoa(hv_algorithm="foo")

TypeError: Hypervolume algorithm must be an instance of a correct type, e.g.: algo = hv_algorithm.wfg()
```

6. Error: Incompatible hypervolume algorithm to the problem

```In[x]: from PyGMO import *
In[x]: prob = problem.dtlz2(fdim=2)
In[x]: algo = algorithm.sms_emoa(hv_algorithm=hv_algorithm.beume3d())
In[x]: pop = population(prob, 100)
In[x]: algo.evolve(pop)

ValueError: Algorithm Beume3D works only for 3-dimensional cases
```

## VII. Migration

1. Selection policies

```In[x]: from PyGMO import *
In[x]: sel1 = migration.hv_greedy_s_policy(10)
In[x]: sel2 = migration.hv_best_s_policy(0.2, migration.rate_type.fractional)
```

2. Replacement policies

```In[x]: from PyGMO import *
In[x]: rep1 = migration.hv_greedy_r_policy(10)
In[x]: rep2 = migration.hv_fair_r_policy(0.1, migration.rate_type.fractional)
```

3. Deploy policies on island

```In[x]: from PyGMO import *
In[x]: sel = migration.hv_greedy_s_policy(10)
In[x]: rep = migration.hv_fair_r_policy(10)
In[x]: prob = problem.dtlz1()
In[x]: alg = algorithm.nsga_II()
In[x]: isl = island(alg, prob, 100, s_policy=sel, r_policy=rep)
In[x]: isl.evolve(42)
```

4. Error: Deploying multiobjective migration policies on single-objective islands

```In[x]: from PyGMO import *
In[x]: sel = migration.hv_greedy_s_policy(10)
In[x]: rep = migration.hv_fair_r_policy(10)
In[x]: prob = problem.rosenbrock()
In[x]: alg = algorithm.pso()
In[x]: isl = island(alg, prob, 100, s_policy=sel, r_policy=rep)
```
```ValueError: Selection policies applies only for multi-objective problems
```