I need to show the convergence speed of my optimization algorithm. There are two conflicting objectives to be minimized. The algorithm produces a set of Pareto optimal solutions.
As far as I know, for single objective optimization problems, it can be shown by means of a graph i.e., Plot fitness value on Y-axis and plot iteration number on X-axis.
Can I show the convergence speed by means of the number of iterations for a desired number of Pareto optimal solutions? i.e., Plot number of Pareto optimal solutions obtained so far on Y-axis and plot iteration number on X-axis.
Kindly suggest me some way to show the convergence speed for the given scenario.
Any help is appreciated
Thanks in Advance
Regards
I think you may use a surface to show the convergence with 2 objectives, i.e., plot fitness value of objective 1 on X-axis, plot fitness value of objective 2 on Y-axis, plot iteration number on Z-axis. Maybe you could also use a heatmap to represent the steps as a color. Of course, none of these approaches would work with more than two objectives.
Best,
I suggest you to use the Hypervolume indicator. You can show the hypervolume by graph between Hypervolume and iteration.
Plot the pareto solutions in higher dimensional plots. Then, repeat the plot as the iterations progresses, this will show how the multi-objectives converge through time.
Could you please share one example of such plot. I have two objectives. The number of Pareto optimal solutions may vary through the time.
I do not recommending making 3D plots with Pareto fronts because it gets pretty unreadable. How about just making 2D plots with several Pareto fronts, of different colour, say spectral palette from red (low nr. of iterations) to purple (final iteration)?
To my mind, the question formulation is not quite correct.
1. In general, the number of Pareto optimal points (in the criteria space) is infinite. The number may be finite if, e.g., both criteria take a finite number of their values in the interval between their minimal and maximal values.
2. Usually, we are trying to estimate the algorithm convergence speed if we are dealing with an algorithm that finds an approximate solution that approaches the optimum with number of steps that goes to the infinity. Otherwise, we usually want to estimate the running time of an algorithm.
Thus, you should clarify your situation and your question.
Possibly, you want to find (or estimate) the number of steps (number of operations) for finding each new Pareto point (solution) or you want to estimate the speed of approaching the number of all Pareto points in dependence of the number of the algorithm steps (if the former number is finite).
When the solution is a Pareto front, you have to decide how to compare different Pareto fronts coming from either different algorithms or different runs of a stochastic algorithm. Several metrics were developed to accomplish this task, focusing on different aspects of the Pareto front itself (spreading, extension, etc).
If you have a reference Pareto front, you can use most of those metrics as a criterion, and plot the value of the indicator as a function of either the number of function evaluations or as a function of the iterations.
If you don't have a reference front, you can either use an indicator that doesn't require a reference front (hypervolume, for instance), or compute a collective Pareto front from all the runs/algorithms, and compare the individual fronts with respect to the collective front using any of the previously mentioned metrics as a function of iterations/function evaluations.
Keep in mind that whatever choice you perform to compare the fronts, it will never give the full picture. So, even if it is not a quantitative approach, I think it's always a good idea to plot the Pareto front (when possible), maybe also as a function of the iterations.
Typically we have two main interests, that is, to obtain solutions that are close to the Pareto front while also diverse (i.e. covering the Pareto front) at the same time. Therefore, it is highly useful if we could use a metric that simultaneously measures both the proximity and the diversity. To this end, I usually use the following two metrics:
1. Inverted Generational Distance (IGD). IGD uses a set of reference points from the Pareto front and computes the distance of your reference Pareto set to the current non-dominated solutions. Here, low IGD indicates a good proximity and good diversity. IGD is also very easy to be coded.
2. Hypervolume (HV). HV is particularly useful when you do not possess reference points from the Pareto front (for example, if you are dealing with real-world optimization). It can be simply explained as a volume that is bounded by the current non-dominated solutions and the reference point for HV calculation. Higher HV indicates a good quality of solutions in terms of both proximity and diversity. There are some open-source implementations of HV calculation in languages such as MATLAB or C++.
Since both metrics are monotonous measures, they are highly useful to show the convergence speed of your optimizer. When I have the reference points for computing IGD, I usually both IGD and HV, not just IGD.
Hope that helps.
You can plot convengence speed in n dimensions with matlab but you can just see in 3d mode in matlab and just 2d mode in printing, so you have to compare one object with another by 2d figure.
You can use either or both "Hypervolume Indicator"(Link 1) and Inverse Generational Distance (Link 2) for this purpose.
Link 1: http://lopez-ibanez.eu/hypervolume
Link 2: http://iridia.ulb.ac.be/~leonardo/publications/conferences/BezLopStu2017.pdf
- Badges
- Science topic