The right choice depends on the nature of the optimization problem itself.

If an algorithm is proven to have a stable performance in terms of the objective function value and/or number of objective function evaluations, then alternative No1 will suffice.

If the performance of an algorithm on a problem is fluctuating with respect to either one or both aforementioned metrics, alternative No2 should be followed and the standard deviation should be computed as well.

Evolutionary algorithms yield approximate solutions to the problem, each time you run the algorithm results would be different ... so to be fair in comparison I would go with Option No 2.

If you want to use convergence graphs I suggest option 2 or 3 with additional information on the variance. However, more sophisticated methods use the information from the convergence graphs to create graphs which capture information of the distribution of your results in a better way. A starting point here are the performance and data profiles described in "Benchmarking Derivative-Free Algorithm" by More and Wild. This requires somewhat more work to create, but is much more useful especially if you comapre your algorithms over several search space dimensionalities and on several test functions.

Evolutionary algorithms belongs to class of the stochastical optimization/adaptation methods, thus, in order to compare different evolutionary processes you have to compare their statistical parameters, like expectation value (average) or median. which of them is better? It depends on the objective function.

I have used 2 before but for completeness you will std as well.

As pointed out that cannot be said in a general way, it depends what is important for your study. However I see some problems even in the way how the question is asked,a s I think you will not have *one single* value per run.

Shouldn't each run contain many data points per generation? one for every individual in the population? Thus it is already the question what is meant by option 1. Are you suggesting to plot the Mean, the Median or the Max of the fitnesses in your population at every generation? As these values will not be normal distributed, most likely, I would suggest to use Median, Modus or Max.

Concerning option 2,3: That would be than a Mean of the Median or a Mean of the Max then? Tricky.

I would show all N evolutionary run in parallel and for each run I would go for Box-and-Whisker plots (Median, Quartiles and Min/Max).

A good way is also to show "time it take each run to achieve X% of the maximal fitness, whereby X=50 and X=95% could be a good choices.

in many paper use average of many iteration and compare two algorithm i used in my ISI paper if you need help i can help you

For my case, as I want to compare my algorithms with others in terms of convergence rate, I use the convergence graph for my best obtained solution. My reasons are give as follows: 1. You demonstrate your best solution history (reduction history), 2. Competing purposes with other optimizers, 3. As I witnessed in the literature, they plotted the convergence rate for their best solution.

Depending on what you want to compare the algorithms, I also recommend the BBOB testbed (http://coco.gforge.inria.fr/doku.php?id=start). They provide a experimental setup and the post-processing generates several graphs, including ones for directly comparing two or more algorithms.

I would go for option no. 3. Since EAs are stochastic optimisation procedures, you need to use some kind of average values to make sure that you are not showing the convergence a statistic outlier (e.g. e very lucky/unlucky run). Unless you are sure that the stochastic variations of the results are normal (i.e. Gaussian), the median is a better measure of the central tendency (i.e. average) of the data. In particular, it is more robust than the mean to skewed distributions and outliers. Finally, in case the distribution of the results is indeed Gaussian, the median and the mean are the same. In other words, the median it is good in all cases, the mean only for normally distributed data.

Using a box plot (or mean+-standard deviation) might be more instructive. Another question might be: plot over fitness evaluations or over generations?

Items 2 and 3 are good enough, and some extra knowledge about the variance will be useful.

Gonzalo, in statistics the arithmetic mean is not a robust estimate of the average of a data set unless you know that the distribution of the values is normal. The same is true for the standard deviation. Some journals accept the arithmetic mean because the reviewers may not be well acquainted with statistics. Personally I got a paper rejected, and as a referee I rejected several papers, for this kind of mistake. Regardless of the feedback from journals, you may lose months of work if you don't analyse the results with the correct statistical tools.

I agree with Yaochu Jin, a box plot would be very informative, giving you valuable information on the central tendency and spread/robustness of the algorithm throughout the iterations. However, plotting multiple box plots in a single graph can be quite confusing. An alternative would be to plot mean points with LSD-corrected standard error bars (as suggested in M.J. Crawley's "The R Book", pp. 464-465), to allow the visual evaluation of statistical significance. If the performance distributions within each iteration are too far from the Normal distribution, you could use median points with median absolute deviation (MAD), which is a robust estimator of dispersion for nonparametric samples.

Hope it helps :)

I agree you should always take the variation in account. I used the average together with the standard deviation (see ref. 1), and the median together with the quartile variation coefficient (see ref. 2) to demonstrate the convergence of my algorithms. I think the box plot is also a good option.

Also, even if the result of a stochastic algorithm is a set of solutions, I would still produce several runs to get reliable statistics.

1) Scoping and screening complex reaction networks using stochastic optimization

2) Integrated framework for the design of pipeline systems using stochastic optimisation and GIS tools

I agree with others that it depends on the point you want to make. If you have enough runs then AVERAGE provides good intuition about which approach is better than the other. However how many 'enough' is will be a function of the variance. If the MEDIAN and AVERAGE curves are smooth then you probably have enough. In my experience the box plot isn't so useful since the range is often so dynamic (i.e. the mins are really low and the maxs really hight - so it doesn't add much showing them).

Variance /STD can be useful. Average with +/- 1 STD where you calculate the upper deviation separate from the lower (bucket all above the mean and calc STD and same for below at each generation).

A single (not necessarily random, but handpicked representative) run can provide a reader with a flavour for what a typical optimisation trajectory looks like. Averaging removes the discrete or quick rises that often happen with EA - so if you wanted them to get a feel for how the approaches move through the fitness landscape then it could be a useful plot... but typically they're not useful in terms of argument support.

Certainly not option 1. Even 2 and 3 are open to mis-interpretation. You would really like to have an estimate of the (bivariate) distribution of solution quality and run-time (or surrogates such as # of function evaluations, populations etc.) for your different techniques. Too many papers are published that are inadequate in this area, but not many people have investigated it properly. One reference I would urge you to read is in the book by Hoos and Stuetzle: Stochastic Local Search (Elsevier, 2005) - Chapter 4 has a very good discusion of these issues.

I agree with Philip's comments on the extreme values shown on box plot. Also it is more appropriate to use median (and quartile variation I would add) since the pdf is not necessarily normal, or when you don't have an adequately large sample.

I agree with the anwers suggesting box plots. They show a lot of interesting information of a series of optimizations runs: median values, typical range of results (e.g. from lower to upper quartile) and the extreme values.

See, e.g. http://en.wikipedia.org/wiki/Box_plot

It's an interesting discussion. I agree that a box plot can show a lot of interesting information however I have a problem with a few local maxima. When you plot all the individuals you can see clearly that there are 2 main attractors, but neither the median nor mean (or box-plots for that matter) allow you to see that. I am however not attempting to compare approaches so I could just plot all runs to discuss my point.

Plotting all runs is certainly a good possibility in case that the number of runs is not too high so that you can still distinguish the runs in the respective figure.

Philip, since you converge to local optima you may need to change the search parameters of your algorithm.

Also, If you have too many runs you can simply draw the pdfs using histograms.

Gonzalo, if you are interested in the central tendency, the median is the most robust estimate. If you are interested in the consistency of the results, then you need a measure of the spread of the distribution. In this case, I would use percentiles because they are robust statistics. Finally, if your concern is the extreme cases you should use the extreme values. Unfortunately, there is no single measure that describes central tendency, spread, and extremals of a distribution.

Box plots give you the complete information (five-number summary), but they are visually more complex. Since the original question was about plotting convergence graphs, I guess the accuracy of the description should be traded off with clarity. Whether to show the central tendency (median), spread (percentiles), or extreme cases (extremals) is certainly down to personal considerations and the application domain (the experimentation requirements, as you said). My personal opinion is that of all possible measures the arithmetic mean is one of the less useful.

This paper might be useful to you Borhan.

http://www.sciencedirect.com/science/article/pii/S0957417412012869#

In order to assess the performance of their proposed Differential Evolution variant for some real-world optimization problems, the authors computed several statistic metrics.

As previously noted, box-and-whisker plots are probably the best visualization for a set of runs -- and as others also pointed out, you will want to show the aggregate results for many runs since stochasticity is involved. Boxplots do a good job of showing the population distribution on a generation-by-generation basis.

However, I've a couple tips regarding using boxplots to show population trajectories. First, showing box-and-whisker plots for each generation can lead to cluttered plots so I generally render just every Nth generation. Naturally, some experimentation may be necessary to find an optimal N. Secondly, boxplots can obscure some fine structure in the trajectories; I address that by having my box plots render over scatterplot "slices" by generation. Each slice corresponding to a generation contains all the individuals with a transparent boxplot overlaid over them; normally all the detail would be obscured by overplotting, which I mitigate by introducing jitter and alpha transparency when plotting the individuals.

One thing not addressed in the comments (or, if it was, I missed it) is that you're comparing *two* trajectories. Sometimes trajectory plots are very difficult to compare visually, especially if the two sets of runs are very similar. To address that, I create a plot that shows a Wilcoxon–Mann–Whitney test for each generation; so for each generation I show the differences in population medians with, say, 95% confidence intervals, thus adding some statistical rigor in trajectory comparisons.

I've attached a PDF demonstrating these techniques. The first two plots show the box-and-whisker technique I mentioned earlier. The third plot is a comparison of the two first plots using the aforementioned Wilcoxon–Mann–Whitney tests.

Another good paper that gives some answers with respect to the initial question posed in this thread is the following:

http://www.tops-scidac.org/papers/DM_benchmark.pdf

In my point of view, the best solution is to plot the best fitness over iterations, until converge.....

I would probably go with 2) or 3). The evolutionary computation is non-deterministic, so I would not depend on a single run.

The choice between 2) and 3) depends on what statistical testing is possible with the particular results you have. If the values have normal distribution use the t-test and graph 2), if not use a test for the medians (e.g. the Wilcoxon signed rank test) and a graph 3).

Krzysztof, Wilcoxon's tests also have a number of restrictive assumptions, even though they are rarely acknowledged: one of the most important (and most restrictive) is that the underlying distribution from which the samples are derived must be continuous and *identical in shape* - which means equality of distributions except for the location parameter. If your data is non-normal, permutation tests using bootstrap tend to work under less restrictive assumptions.

https://www.researchgate.net/publication/297245624_Particle_Swarm_Optimization_Algorithm_and_its_Codes_in_MATLAB

Research Particle Swarm Optimization: Algorithm and its Codes in MATLAB

https://www.researchgate.net/publication/296636431_Codes_in_MATLAB_for_Particle_Swarm_Optimization

Code Codes in MATLAB for Particle Swarm Optimization

https://www.researchgate.net/publication/280244004_A_comparative_study_of_metaheuristic_optimization_approaches_for_directional_overcurrent_relays_coordination

Article A comparative study of metaheuristic optimization approaches...

A plot of the Average of the best fitness over iterations. the average calculated at least 30 runs for each algorithm. because the stochastic nature for optimization algorithm so you can not depend on a single run