The mean, along with some measure of variability (SD, CV, quantile, box plot) seem necessary for self-validation, but more is needed to examine performance. You can have a heuristic that provides a better mean and better measure(s) of variability than other heuristics, but they all might not be good performers. Compare to an exact solution, even for small problems, to gauge whether the heuristics are good; then apply to larger models and use statistics such as these.

Hi Nikola,

The significant statistic F-test P-value between quantiles/percentiles will be insignificant in all cases for a specific fixed settings of my problem and I think the same issue in most evolutionary computation problems for specific fixed settings. Thus, in my opinion, the mean values comparison from multiple runs between algorithms for fixed settings will be the best option.

Thanks

Osman

The performarmance the evolutionary and swarm intelligence algorithms could be evaluated in many ways. It is required, in the first place, to submit the algorithm used to an Monte Carlo experimentation cycle and, starting from the obtained results, you could to define the following, among others, indicators: mean obtained value, assured with certain probability value, better  value (minimum or maximum, according to the case) of the utility function and/or some of it components.

Best wishes.

You might view this paper...

Bettinger, P., J. Sessions, and K. Boston. 2009. A review of the status and use of validation procedures for heuristics used in forest planning. Mathematical and Computational Forestry & Natural-Resource Sciences. 1(1): 26-37.

http://mcfns.com/index.php/Journal/article/view/MCFNS.1-26

Dear Osman Ibrahim,

Thank you for starting the discussion. Unfortunately I do not understand your answer. Please, could you explain it a little further? Perhaps you might give a simple example.

------------------------

Let me give an example of my suggestion:

Assume a minimization problem P and optimization algorithm A. For example, I can run algorithm A for 60 seconds or maybe 10000 iterations. Then I obtain a solution of some quality. I can repeat the experiment to get for example 31 samples (solutions quality/cost):

42449, 42267, 42184, 42355, 42352, 42205, 42315, 42350, 42235, 42255, 42392, 42363, 42394, 42378, 42388, 42238, 42128, 42282, 42363, 42354, 42417, 42442, 42253, 42267, 42184, 42460, 42276, 42221, 42392, 42343, 42473.

Now I can say:

-algorithm A produces solutions with 0.5 quantile quality (or 50 percentile quality or median quality) equal to 42350

-algorithm A produces solutions with 0.3 quantile quality equal to 42267

By reading that I have reported Q0.5=42350 and Q0.3=42267

(1) you know if you use algorithm A once for problem P for 60 seconds you might expect to obtain:

-solution whose quality is at least 42350 (might be even better) with probability of 50%

-solution whose quality is at least 42267 with probability of 30%

(2) You also know if you use 5 times algorithm A for problem P for 60 seconds you might expect to obtain:

-solution whose quality is at least 42350 with probability of 96.88%

-solution whose quality is at least 42267 with probability of 83.19%

For (3) I need another example.

Of course, if you use algorithms A, B and C with problem P, then you can use nonparametric statistical tests (in evolutionary computation optimization algorithms usually don not produce solutions that are normally distributed!).

I read your article. Would be not difficult for you to implement my recomendations. I could provide more information for you, if needed.

Dear José Arzola-Ruiz,

Here I am not interested in a general discussion about experimental research with stochastic optimization algorithms. To simplify, it is the question of quantiles vs arithmetic mean.

I know that arithmetic mean is usually used as indicator of algorithmic performance. I claim that quantile/percentiles are much better. My arguments are inside short paper "Measuring Performance of Optimization Algorithms in Evolutionary Computation" attached with my question.

Please also consider the example that I provided in my answer to the comment of Osman Ibrahim.

I don't see a practical (useful) way of using probabilities with arithmetic mean.

I would like to hear that other agree with my arguments or have some counter arguments if they think that arithmetic mean is better.

Dear Pete Bettinger,

could you express your opinion for quantile vs arithmetic mean.

Do you agree with my arguments that quantiles are better or you have same arguments in favor of arithmetic mean.

Hi Nikola,

Thank you very much for your reply. The mean value of the runs is the middle points between the variation from run to another. Yes, sometimes the algorithm may have high values and sometimes low values but it should be the mean is the middle point between runs. In my case, I have 9 pages of table of contents of tables for the average values in at least 40 pages of tables. If I want to make it quartiles reports by R commandar, I should have at least 125 pages of tables which is a bulky of data. However, you can report algorithms with mean values or best and worst run or write the average +- the difference between highest and lowest performance. In most data mining and text classification, they write the mean values +- highest variation values. In my case is 0.1 maximum variations between runs. In addition, you should run the algorithm in a large number of variously available datasets which will give you variations in quartiles values which you can not compare them. But if you have the average values on each dataset. You can spot in which algorithm outperform a dataset as an average performance. However, you should make training data become testing data and vice versa to generalise your results on the dataset.

Also, the main questions how you can compare between algorithms quartiles on a various large number of datasets ????????????????

However, providing the package of algorithms with the datasets is the best option for research replications than quantiles measurements.

Best wishes

Osman

However, providing the package of algorithms with the datasets is the best option for research replications if the algorithm varying so much than bulk of quartile data.

What is your opinion Nikola?

Hi Osman,

I don't understand why would you get more data when you use chosen quantile instead of arithmetic mean.

In example I provided before, there is only one value for median Q0.5=42350

You also have only one value for arithmetic mean arithMean=42321.7741935484.

If you have 3 algorithms to compare and one instance of the problem, then you have exactly 3 medians (or some other chosen quantile) and exactly 3 arithmetic means.

In general, for N problem instances and M algorithms you get MxN arithmetic means and MxN 0.5-quantiles.

I am aware that people often do present best obtained solution, but best or worst obtained solutions are particularity problematic because in general there is a problem with reproducibility of results.

(In past I did the same thing – report arithmetic mean, standard deviation and best solution. Now I use quantiles because of the reasons I already explained.)

Eiben and Jelasity [1] did propose best obtained solution as a measure of peak performance of the algorithm. This was criticized by Birattari and Dorigo in [2]. I agree with Birattari and Dorigo that best obtained solution is problematic because of reproducibility.

I don’t understand why do you think that it is harder to compare quantiles but easier to compare arithmetic means. It is very simple in both cases.

For problem P and algorithms A, B, and C can have following results

* 0.5-quantiles: * arithmetic mean

Q0.5_A=42350 arithMean_A=42321.77

Q0.5_B=42235 arithMean_B= 42268.23

Q0.5_C=42403 arithMean_C= 42431.34

By looking 0.5-quantiles you can see that algorithm B is the best and algorithm C is the worst. By looking arithmetic mean you would make a similar comparison.

When you have many algorithms and many problem instances and want to use statistical tests you can for example use Friedman test. For multiple hypotheses in post hoc procedures you have to control familywise error e.g. with Holm's or Hochberg's procedures.

I agree with you that it would be best to provide a package of algorithms with the datasets, but I don't see that this has anything to do with the question "arithmetic mean vs. quantiles".

I have noticed that you have mentioned data mining and text classification. I am not sure what kind of optimization you are referring to. Is it minimization or maximization problem? Could you explain what is the optimization problem you are thinking about and what is a solution. Please notice that that this discussion is intended for hard (single-oblective) optimization problems e.g. NP-hard combinatorial problems. Maybe we are not talking about same thing.

[1] A. E. Eiben and M. Jelasity, “A critical note on experimental research methodology in ec,” in 2002 Congress on Evolutionary Computation (CEC’2002), D. B. Fogel, M. A. El-Sharkawi, X. Yao, G. Greenwood, H. Iba, P. Marrow, and M. Shackleton, Eds., vol. 1. IEEE Press, Piscataway, NJ, 2002, pp. 582–587.

[2] M. Birattari and M. Dorigo, “How to assess and report the performance of a stochastic algorithm on a benchmark problem: Mean or best result on a number of runs?” Optimization Letters, vol. 1, pp. 309–311, 2007.

Best regards,

Nikola

I don't understand the insistence in this problem when  the really important thing consists on evaluating the performance of evolutionary algorithms when facing the optimization  tasks with different characteristics 

As the papers sent by Nikola discussed this issue, we do not run and measure the performance of n times of random restart of the same algorithm but the average performance of running the algorithm. This is because you will not keep several random restarts of the algorithm on the same dataset for several times with the same algorithm settings on your system to get an optimal solution for one setting. There are also infinity of settings of variations for each machine learning or computation intelligence approach that can be applied. However, if the algorithm consumes too much time in one run, it will be sufficient to report the best performance in one run and the time regarding it. 

[1] A. E. Eiben and M. Jelasity, “A critical note on experimental research methodology in ec,” in 2002 Congress on Evolutionary Computation (CEC’2002), D. B. Fogel, M. A. El-Sharkawi, X. Yao, G. Greenwood, H. Iba, P. Marrow, and M. Shackleton, Eds., vol. 1. IEEE Press, Piscataway, NJ, 2002, pp. 582–587.

[2] M. Birattari and M. Dorigo, “How to assess and report the performance of a stochastic algorithm on a benchmark problem: Mean or best result on a number of runs?” Optimization Letters, vol. 1, pp. 309–311, 2007.

Dear Peter Husar,

I am glad that you have joined this discussion.

I completely agree with you that in general quantile and arithmetic mean have nice and bad properties.

However, specifically in the case of measuring performance of stochastic optimization algorithms I think that quantiles are much better choice. The main arguments for my claim are presented in the short paper I have attached.

In the case of measuring performance of stochastic optimization algorithms I don’t see particular advantages of LINEAR measure on data. Anway this LINEARITY would be lost when we would consider the experiments with many problem instances.

Regarding the problem of "sort(ing) the data for quantiles after EVERY iteration..." there might be a misunderstanding in the way this quantiles or arithmetic mean are used in measuring performance in stochastic optimization algorithms. To clarify possible misunderstanding I will post a separate comment.

Dear researchers that have so far participated in this discussion

I have realized that I have omitted some details about the way the stochastic optimization algorithms (like those from evolutionary computation and swarm intelligence) work and are evaluated.

These lack of these details might be the main source of misunderstandings in this discussion!

Stochastic optimization algorithms (SOA) in evolutionary computation and swarm intelligence:

-have as input: problem instance (also the following might be viewed as inputs: (pseudo)random number sequence or source, and various parameters (including stopping criteria))

- often (internally) generate many solutions in one run (one run often have many iterations)

-have as output: (normally) only the best solution that was generated during one run (we don’t care about bad solutions when we have good one – we will only use the best solution.)

The problems in measuring performance arise because of the stochastic nature of the algorithm. If we run the same algorithm again we will get a different solution (one that was best in this second run).

Let me focus here on the more common way of measuring performance in SOA where computational time (or number of iterations) is stopping criteria and solution quality is measured.

We care only about solutions that are outputs of our algorithms (the best solution in the first run, the best solution in the second run, etc.). The arithmetic mean is calculated from: the best solution in the first run, the best solution in the second run,… , the best solution in the last run. Then people use this arithmetic mean as a measure/indicator of performance. I claim that in this field of application a quantile calculated from the best solution in the first run, … , the best solution in the last run is much better choice.

In the case when solution quality is stopping criteria and computational time is measured there are even more arguments why a quantile should be used instead of arithmetic mean.

Dear Peter, I don't think that statistical convenience should be put before meaning/interpretation of statistical value.

Let me first try to find an example from other domain (not stochastic optimization). You can think about average wage for some country in a term of arithmetic mean and median.

- If you are interested to see what is the total amount of money earned by workers in that country, then arithmetic mean is what you are interested.

- If you are interested "economic power" of that country normalized with regard to the number of people, then arithmetic mean is what you are interested.

- But if want to compare your wage with the wages of workers in that country then you are interested in median. E.g. you want to know is your wage larger than 50% of the other workers. (Even though there might be millions of samples, in this case, I would prefer median over arithmetic mean.)

Now let me present you an example with stochastic optimization algorithms A and B.

You might have an optimization problem you are interested to solve, i.e. find the best solution you can with available resources.

You have 10 computers available for 24 hours and the budget of 10000€ for implementing the solution.

You know that when you run algorithm A for 24 hours, then the median of solutions has the cost of 10000€ and algorithm B produces solutions whose arithmetic mean is 10000€. Which one would you use?

I would prefer the algorithm A. Reason: I expect with probability at least 99.9023% that I will obtain solution whose cost is at most 10000€. (This is because 1-(1-0.5^10)=0.999023.)

What kind of solution can you expect with algorithm B?

It you have some simple example with stochastic optimization algorithm where arithmetic mean would be preferable, then I would appreciate if you could present it.

P.S.

I might also know that for algorithm A, Q_0.3=8000€, so I am pretty sure (at least with 89.26%) that I will obtain solution that costs at most 8000€.

Peter Husar,

I was expecting real arguments and not inappropriate statements about my scientific work.

You should know that when your argument is that you are right because you are on a higher position or better scientist actually means that you don't have real arguments.

I am willing to look in your lectures if there is something that could be useful for this discussion. Please give me the links.

You did not comment any of my examples. Are they correct or incorrect? If there are flaws please explain them. Why didn't you provide an example where arithmetic mean is more appropriate in discussed area?

By the way, I didn't see any of your scientific papers that deal with optimization algorithms in evolutionary computation and swarm intelligence. Do you have any practical experience with optimization algorithms in evolutionary computation and swarm intelligence?

I think the convergence of the SOA over predefined runs will define the efficiency of performance analysis than the statistical mean calculation.May be the mean calculation can be done once the predefined runs have been performed using the algorithms and provided the threshold is fixed as convergence criterion.

Dear Nicola:

    there are so several papers discussing this that it is hard to recommend. A good starting point could be

https://link.springer.com/article/10.1007/BF02430363

Journal of Heuristics September 1995, Volume 1, Issue 1, pp 9–32

Designing and reporting on computational experiments with heuristic methods

and the references therein. Papers older than 20 years!

Regards

David

Hi David,

In 1995, there is a little research comparison between various algorithms and limited resources that force for reporting in that way, but now I think Nikola papers are the most recent papers and I think their opinions are convincing. Please, read them:

[1] A. E. Eiben and M. Jelasity, “A critical note on experimental research methodology in ec,” in 2002 Congress on Evolutionary Computation (CEC’2002), D. B. Fogel, M. A. El-Sharkawi, X. Yao, G. Greenwood, H. Iba, P. Marrow, and M. Shackleton, Eds., vol. 1. IEEE Press, Piscataway, NJ, 2002, pp. 582–587.

[2] M. Birattari and M. Dorigo, “How to assess and report the performance of a stochastic algorithm on a benchmark problem: Mean or best result on a number of runs?” Optimization Letters, vol. 1, pp. 309–311, 2007.

Thanks Nikola and others

Best regards

Osman

The mean, along with some measure of variability (SD, CV, quantile, box plot) seem necessary for self-validation, but more is needed to examine performance. You can have a heuristic that provides a better mean and better measure(s) of variability than other heuristics, but they all might not be good performers. Compare to an exact solution, even for small problems, to gauge whether the heuristics are good; then apply to larger models and use statistics such as these.

hi,

we have recently done some works  in this regard:

1) A-TOPSIS – An Approach Based on TOPSIS for Ranking Evolutionary Algorithms

http://www.sciencedirect.com/science/article/pii/S187705091501529X

2) Ranking and comparing evolutionary algorithms with Hellinger-TOPSIS

 http://www.sciencedirect.com/science/article/pii/S1568494615005104

both  papers are available

Best regards

Renato

Dear,

Rajine Swetha

The convergence speed is a suitable measure of performance when there is an algorithm that is proven to converge towed optimal solution, and in each following step finds a solution that is better or equally good as the previous solution. However, this is not the case for optimization algorithms in evolutionary computation and swarm intelligence.

In the field of evolutionary computation and swarm intelligence, you can have an algorithm that is converging toward a suboptimal solution. Usually if you set parameters of the algorithm to get very greedy behavior you will end up with the algorithm that will converge very fast toward moderately good or bad solution. Also some algorithm may wonder around search area without converging to any value but can find very good solutions. This is a good algorithm.

Obviously the speed of convergence cannot be an appropriate measure of performance for optimization algorithms in evolutionary computation and swarm intelligence.

However, the speed of convergence is usually interesting information about the behavior of the algorithm. (When I investigate the behavior of stochastic algorithms I usually examine the speed of convergence.)

If the means of performance, whatever performance metric is used (solution quality, running time, etc.), are representative of the distributions of the metric for the algorithms being compared, then I think it would be safe to compare the means. Therefore, I would first visualize the data, if possible, to see how the distributions look like and then make a decision on how to compare the algorithms. Usually, I end up trying to determine if the distributions are significantly shifted to one another. That means formulating the null hypothesis as P(X=Y) = 1/2, where X and Y are the random variables modelling the distributions of the scores for two algorithms being examined.

In general, I agree that quantiles are more informative than the arithmetic mean alone and provide a deeper insight into performance of the algorithms. However, I do not agree that "you know what solution quality and with what probability you might expect, if you use an algorithm once" or n times. By NFL theorems, any elevated performance of an algorithm on a specific class of problems is offset by performance on another class of optimisation problems. Therefore, the assessed probabilities and metric scores can hold only for the benchmarks used or the class(es) they belong to. This applies to the probabilities associated with the selected quantiles in Your approach, as well as to P(X=Y), P(XY) that I mostly deal with.

Personally, I look at the median in terms of the number of function evaluations (speed of convergence), and quantiles for a given function evaluation budget. (I call that reliability, in the sense that the average and median should be close to the optimum, and the standard deviation small.)

Dear Miloš Simić,

analysing data before determining if arithmetic mean is safe to use for an indicator of performance seems reasonable, but it has some disadvantages.

Please consider the following scenario.

1. you conduct same experiments (e.g. with three algorithms)

2. you analyze distributions and conclude that arithmetic mean is safe to use

3. you publish your results by using the arithmetic mean

Now some independent researcher wants to compare some other (forth) algorithm with your results. Obviously you have made your decision before knowing results of the future experiments.

The experimental results of this independent researcher are such that he cannot use the arithmetic mean (maybe arithmetic mean cannot be calculated for example when running time is observed value). Now, this is a problem. If quantiles where used he might have a better chance.

P.S.

I will address the other part about implications of NFL theorems separetly

Dear Nikola Ivkovic,

I agree that quantiles would be more convenient in that case, but it would be even more convenient if I shared all the raw data with the research community so that anyone can analyze them as they see fit. That way, if it is the case that the means are indeed good indicators of the algorithms' performances in my experiment, I could use them in the analyzis, whereas other researchers may use other statistics if they find them better suited for their studies. I would go even one step further and suggest that new studies repeat my experiments, but I'm aware that replications may be time-consuming and may slow down the research.

As far as the NFL theorems are concerned, what I had in mind was the wording generally used in conclusions. Instead of expressions conveying certainty, I'd prefer probabilistic statements. The NFL theorems are not the only reason for that, another one being the very nature of statistical inference.

Here's a rigorous alternative to both quantiles and mean:

Article Benchmarking Derivative-Free Optimization Algorithms