Who says that a heuristic need to be deterministic? You need to reevaluate what you want to do.

@Michael Patriksson I agree with you, but in this case the heuristic is deterministic. So you can suppose it for my question. Thank you.

You're going to be able - perhaps - to say something about the heuristic. For example, if the heuristic is to relax the integrality constraints of an integer programming problem, you may even already know the result, based on known theory on continuous relaxations on certain classes of integer programs. But if you compare with a metaheuristics, you will probably only get nonsense output, since a metaheuristic tend to (a) NOT be based on the properties of the original model, and (b) metaheuristics as such are *not* - I would say they cannot be - designed to provide a guaranteed quality.

I agree with you again Michael Patriksson, but I think I am having a problem to show you my needs. I hope the next explanation makes it clear. Thank you again.

Suppose you have a problem with objective funcion F(x), x in X. I have a way to create a greedy solution (deterministic one) to get a value for an input instance A. the instance A have a natural xA in X and i can change it to xG using the greedy solution. Ofc I can evaluate F(xA) and F(xG) and F(xG) uses to be better than F(xA). That is the heuristic side.

I am trying to show that a meta-heuristic will lead to better solutions than the greedy heuristic. At least most of the time, to justify its use in the problem. How could I test it in an effective way? If you know some papers showing heuristic vs meta-heuristics or even meta-heuristic vc meta-heuristic would be great too.

I am quite positive that you cannot say for sure that one is better than the other. None of the two can guarantee that you even terminate at a local optimum, for example. For a rich enough class of problems, and rich enough variations of data, you most certainly will not be able to say that one beats the other. Given that you may find in practice that one of them is better then the other more often, you still cannot claim that this must then be true always. I feel that you have asked the wrong question: you should not try to show that one is better than the other, because the urge to see your method win may mean that you do not runa fair experiment. And speaking of experiments: if you really want to test your two methodologies, you need a test bed that is huge, and you need to utilize more than one criterion with which to compare the methods (speed, accuracy, portion of fails/successes, ...). It will keep you awake for a few days. :-)

Mr Robinson, Iooking at classical and global techniques, model performance with non-deterministic values is superior to that of deterministic… Meaning that the solution from Metaheuristic is better than that of heuristic solution. I have done a good number of research by comparing the solution strength of greedy heuristic(GH) and meta-heuristic(MH). MH solution gives far better solution in most cases. For MH versus MH, it is usually indecisive if one technique is better than the other.

Michael Patriksson, your answers are great, and again I will agree with you. But what I do mean is something about what Modestus Okwu have written. In my experience with meta-heristic and heuristics, usually MH is better than H, and MH gives far better solutions in most cases (as Modestus Okwu told us).

The point is, what would be a good statistical way to say that I could choose the MH, or the H or they gives some statistical non significant difference. Because in my case, I run the MH 200 in some instances and all the 200 tives it is better than the H results. I will not say in the end: "The MH is better or worst than the H", I would like say "Using this methodology(or this criteria, or this test), the MH is better (or worst) than the H".

That is why I am searching for some papers that did something similar: comparisons with MH and H. At least I could cite someone If they are using some interesting methodology, or criteria, or test.

I would like to ask you, Modestus Okwu, about some papers you have wrote in this field.

Thank you Michael Patriksson and Modestus Okwu.

Michael Patricksson,

"if you really want to test your two methodologies, you need a test bed that is huge, and you need to utilize more than one criterion with which to compare the methods (speed, accuracy, portion of fails/successes, ...)" That is what I am looking for... some papers or references doing something like this.

My articles on related research area are under review. The links below will be helpful. Regards!

https://ac-els-cdn-com.uplib.idm.oclc.org/S156849461630182X/1-s2.0-S156849461630182X-main.pdf?_tid=6b7943a9-1f64-4fac-92e3-40ab8dd63859&acdnat=1521665275_769977b398d1d95007a516ab95c53f6c

https://www-sciencedirect-com.uplib.idm.oclc.org/science/article/pii/S0020025513001588

Thank you Modestus Okwu, but I cant access the UP library :(

Could you please share the name/authors of the references?

Thank you.

Oh sorry Robinson, am already set to sleep now. I will do that first thing tomorrow morning. Pls drop your email add. Regards!!

Given multiple independent runs of your metaheuristic and your heuristic, you can compute the Expected runtime to reach a desired quality, or you also can compute the Empirical cumulative distribution of reaching multiple target (quality of the solution). All the details are in [1]. These measures can be used to evaluate both heuristics and metaheuristics and are particularly interesting to evaluate them on multiple problems.

The goal of these measure is quantify the robustness and fiability of your algorithms such that they can solve a a wide range of problem and also does there are any statistical guarantee to reach the optimum or approach the optimum.

Please let me know if you have issues to implement these metrics.

[1] Hansen, N., Auger, A., Mersmann, O., Tusar, T., & Brockhoff, D. (2016). COCO: A platform for comparing continuous optimizers in a black-box setting. arXiv preprint arXiv:1603.08785. https://arxiv.org/pdf/1604.00359.pdf

Thank you Mr. Nacim Belkhir

I am going to read about COCO for sure.

I think there are two interesting comparisons that you can make.

One is to give to a metaheuristic algorithm exactly equal time (or the number of generated solutions if this is more appropriate) as your deterministic heuristic algorithm required for particular problem instance and compare the solution quality.

The other is to set the soulution quality reached by your heuristic algorithm for particular problem instance as stopping criteria for metaheuristic algorithms (they stop if they reach equally good or better solution) and you observe the elapsed time (or the number of generated solutions if this is more appropriate).

For both cases I would suggest using median and/or other suitable qunatile/percentile (not arithmetic mean).

For reasons why I am suggesting median/quantile/percentile instead of the arithmetic mean you can read in the paper Measuring "Performance of Optimization Algorithms in Evolutionary Computation", available on http://www.ijmlc.org/index.php?m=content&c=index&a=show&catid=64&id=679

and also attached in this answer.

Although it is cited in the paper I suggested, you might also consult the following paper written by Birattari and Dorigo to see why best and worst solutions are not so important and cannot be used as a measures of performance.

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

Thank you very much Nikola Ivkovic.

Performance profiles (Dolan/Moré) - used wisely - can also be useful.

Thank you Michael Patriksson! I am going to read about it.

Hi Robinson, it has been a while, I hope the articles on H and MH are helpful. Any update on your findings so far?

Regards,

Modestus

We wrote a paper on validating the results from heuristics a few years ago. It includes some thoughts on comparing the performance of different heuristics.

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.

Article A review of the status and use of validation procedures for ...

Prof. Pete Bettinger,

Thank you for sharing the review article "....Validation procedures for heuristics used in forest planning". The article will be very useful.

Regards,

Modest