Many quality indicators were proposed by the EMOA community to assess the performance of multi-objective solvers: Generational Distance, Inverted Generational Distance, hyper-volume, etc.
Most of these indicators try to quantify the distance between a given set of solutions and the Pareto optimal set. Let's take two indicators A(S,R) and B(S,R) where S: set of solutions, and R: reference non-dominated solution set. Assume that both A and B return a distance that is equal to zero when S=R.
How can you say that indicator A is better than indicator B?
Based on an indicator you can compare algorithms. Comparing indicators is a bit difficult. Depends on what you want. There are some properties that an indicator should satisfy. These can be found in the paper 'Performance Assessment of Multiobjective Optimizers: An Analysis and Review'.
HTHs
Usually, Pareto-based multi-objective approaches consider three aspects: closeness to the global Pareto front; spread along the Pareto front; number of solutions of the non-dominated set (see http://seit.unsw.adfa.edu.au/staff/sites/rsarker/ch-7-sarker.pdf). Therefore, the multi-objective metrics are often classified according to the distance, the volume, and the the diversity (http://sci2s.ugr.es/keel/pdf/specific/congreso/okabe03a.pdf)
You must take into account that if the true Pareto-optimal set is known (e.g. if you are solving well-known problem instances such as ZDT1, ZDT2, Kursawe, DTLZ1, DTLZ2,...., etc. functions) you can use metrics that calculate the distance between the non-dominated set obtained by a given optimization method and the true Pareto-optimal set (of course, you can also use volume- and diversity-based measures). However, in many problems, including NP-hard problems, it is not possible to use distance-based metrics to determine the distance between a given set obtained by an optimization method and the true Pareto-set, because the true Pareto-set is unknown. In the latter case is suitable to apply volume- and diversity-based measures (e.g. coverage of two sets (SC), hyper-volume (HV), schott spacing metric (SSM), etc.).
The distance to the true Pareto front is not always a good indicator! Take as example a multimodal test function which has a 'good' local optimum that is far from the optimal Pareto set (in design space)... The algorithm will (or may) logically guide the search toward this region. Else, it will converge to a nearer region which corresponds to dominated region in objective space.
Hi Nabil,
You may be interested in this paper:
A Set of Test Cases for Performance Measures in Multiobjective Optimization
http://link.springer.com/content/pdf/10.1007%2F978-3-540-88636-5_41.pdf
Abstract
Comparing the performance of different evolutive multiobjective algorithms is an open problem. With time, many performance measures have been proposed. Unfortunately, the evaluations of many of these performance measures disagree with the common sense of when a multiobjective algorithm is performing better than another. In this work we present a benchmark that is helpful to check if a performance measure actually has a good behavior. Some of the most popular performance measures in literature are tested. The results are valuable for a better understanding of what performance measures are better.
Thank you very much Chiang. Can you send me this paper (i could not download it).
Dear Nabil,
In a "real" case scenario, when you don't know where the true Pareto front is (you are looking for it, after all) you need to compare solutions with regards to each other. The hypervolume indicator is perfect for that task.
After you have the hypervolumes (or the indicator of your choice) of all your solutions an statistical hypothesis test is required to assert what algorithm provide better results. There a nonparemetric test like Kruskal-Wallis or Mann-Whitney is a good choice.
I have prepared an IPython notebook for my PhD classes that deals with this topic at the end. You can check it out at:
http://nbviewer.ipython.org/github/lmarti/evolutionary-computation-course/blob/master/AEC.06%20-%20Evolutionary%20Multi-Objective%20Optimization.ipynb
or as slides at:
http://lmarti.github.io/evolutionary-computation-course/AEC.06%20-%20Evolutionary%20Multi-Objective%20Optimization.slides.html
The source is available at the class github project:
https://github.com/lmarti/evolutionary-computation-course
Hope this helps.
https://github.com/lmarti/evolutionary-computation-course
http://nbviewer.ipython.org/github/lmarti/evolutionary-computation-course/blob/master/AEC.06%20-%20Evolutionary%20Multi-Objective%20Optimization.ipynb
http://lmarti.github.io/evolutionary-computation-course/AEC.06%20-%20Evolutionary%20Multi-Objective%20Optimization.slides.html
In this topic, does any one know the MATLAB code of Inverted Generational Distance (IGD)? it seems evaluate both convergence and diversity of solutions in the set of Optimal Pareto front set.
Hi Farshid,
You may check PlatEMO: http://bimk.ahu.edu.cn/index.php?s=%2FIndex%2FSoftware%2Findex.html
Mean of ideal deviations (MID): the closeness between Pareto solution and ideal point (0, 0)
- Badges
- Science topic
- Similar topics
- Psychology
- Mental Processes
- Learning