-
Notifications
You must be signed in to change notification settings - Fork 86
GSoC 2013 Hypervolumes
|
IMPORTANT: This project was finished Oct 2013. All information on these pages (especially related to the algorithms) might be outdated.
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])
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
Fr 19.7 - Deadline: SMS-EMOA ready to merge to development
Fr 26.7 - Deadline: Bringmann Approximation ready to merge to development
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)
Fr 6.9 - Deadline: MO-CMAES
Mo 9.9 - MILESTONE: Pens down, no more coding, writing documentation, tutorials and examples
Mo 16.9 - MILESTONE: End of GSoC
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.
In[x]: prob = problem.zdt1() In[x]: pop = population(prob, 100) In[x]: hv1 = hypervolume(pop)
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)
1. Constructor argument is neither population object nor a list/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
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
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
ValueError: native2d algorithm works only for 2-dimensional cases
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,] 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
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
ValueError: beume3d algorithm works only for 2-dimensional cases
5. Error: Picking bad index for invidivual
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
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
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
4. Error: Picking bad algorithm
ValueError: native2d algorithm works only for 2-dimensional cases
1. Computing the nadir point
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) In [x]: hv.get_nadir_point(eps=0.01) Out: (6.01, 4.01, 5.01)
2. Error: Incorrect epsilon for nadir point
ValueError: Epsilon must be a non-negative value. In [x]: hv.get_nadir_point(eps="foo") TypeError: Epsilon must be castable to float.
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, <math>(\mu+1)</math> 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.
ValueError: selection method must be equal to 1 (least contributor) or 2 (domination count).
5. Error: Incorrect type for 'hv_algorithm' argument
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
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