I recommend the performance profile - through which you can assess, for example, how often one algorithm is compared to another. Here are two papers:

https://pdfs.semanticscholar.org/54a2/0dbd409436be4f188dfa9a78949a1cac230d.pdf

http://www.numerical.rl.ac.uk/people/j_scott/publications/2016/GouldScott.2016_TOMS.pdf

Thanks a lot Dear colleagues;

I'm exploring all your orientations.

Many thanks for the question and suggestions from the respected colleagues. In addition to the replies, my comments are as follows:

(1) Number (objective and constraint) function evaluations. This is besides the number of iterations, which may be correlated with the number of function evaluations.

(2) Number function evaluations and number of iterations are likely to be correlated with CPU time.

(3) Accuracy of solution is probably correlated with computational effort (measured by number of iterations or number of function evaluations or CPU time).

(4) Although some performance criteria may be correlated, it is desirable to use as many as possible.

Dear colleague Gade,

Thank you for interest and for your response.

In the following link you can see 9 metrics used to evaluate and compare Heuristic Algorithms (Multi Objective). Open Source: PlatEMO, A MATLAB Platform for Evolutionary Multi-Objective Optimization.

The inputs for metrics evaluation are: Resulted Pareto front, True Pareto Front.

For more information, check the following ResearchGate link:

PlatEMO paper: Article PlatEMO: A MATLAB Platform for Evolutionary Multi-Objective ...

Thank you very much dear Andres.

Sincerely, Djamel

(1) Number of function evaluations (i.e. algorithm cost)

(2) final error (use some known test problems to test your algorithm and track the error as your solution converges - there are lots of these test problems in the optimization literature)

(3) exit flag (if you are using Matlab or similar) to see if you converged to a local/global solution or if the algorithm just hit the maximum default function evaluations

(4) Sensitivity to starting point

(5) Sensitivity to convergence tolerance

(6) Amount of constraint violation (if it is a constrained problem)

If you test your algorithm in Matlab, you there are built-in tools to track all of these things as you run test cases for your algorithm and give you a report at the end

Thanks a lot Albert for your interest.

I'm not using Matlab, indeed, my algorithms implement some existing heuristics with respect of the Agent technology using the Influence/Reaction Principle. These implementations are performed on agent platforms such as Jade and Madkit.

I was confused when I have been asked to speak about the convergence of my Agent Algorithms, which seem to perform better than previous ones applied to the same benchmarks. so I asked on RG my question :

Convergence versus Performance ? It still without response, perhaps it was not clear enough !!!!

I have to give to Mohamed Azab, Nicolas Dupin, Michael Patriksson, Gade Pandu Rangaiah, Andres Felipe Abril Duran, Albert E. Patterson and all other interested colleagues some explanations:

1. The context given as indication to Albert above;

2. Best performance is not enough to attest convergence?;

3. Which metrics to apply for this issue similar to Precision and Recall used in Data retrieval;

4. What is the relation between Algorithm's Complexity, Convergence and Performance?.

Sincerely, Djamel.

Thanks, Andres Felipe Abril Duran! I haven't worked with evolutionary algorithms in some years but the paper you indicated ignited my curiosity on a Thursday night (here weekends are on Friday and Saturday) so I am reading it as we speak. :)

Djamel Zeghida I think I better understand what you are asking now. I am not a mathematician, but my experience with optimization algorithms has been, in general and for all different kinds of algorithms:

1. "Convergence" means that the algorithm is "able to reliably find an answer that makes sense from some starting point". There is a formal mathematical definition, but this seems to be a good working definition. Without proving you have some kind of convergence, the algorithm is worthless because it cannot find any answers.

2. After you show that the algorithm can converge to some answer that makes sense for your problem, you have to consider the type of convergence. Most optimization problems have a whole set of feasible answers, some of which are better than others. If you have local convergence, the algorithm found one of the set of feasible solutions; on the other hand, if your algorithm can find the one best solution among all the possible solutions, you have global convergence. Using the exit flags and a variety of different starting points will tell you which it is - there are some mathematical proofs in the literature if you want to explore these in more depth. Global convergence is more valuable but it can be very expensive and difficult to find and is not always possible to find. There is an entire branch of optimization theory dedicated to finding algorithms and problem formulations to make this easier.

3. Once you prove that the algorithm can converge, THEN you can be concerned with performance of the algorithm. But remember that elegance and efficient performance are worth nothing if your algorithm cannot converge, so prove convergence and then worry about performance.

4. The most important aspect of performance you need to worry about is robustness. A simple definition for this is "the ability for the algorithm to provide useful information and consistent convergence from more than one starting point". If you get a different answer each time you run the algorithm, it isn't very robust; on the other hand, if you always get the same answer from a wide variety of starting points, it is very robust.

5. Now, you can worry about complexity of the problem. I do not understand the idea of "algorithm complexity". The algorithm is simply a procedure for solving a problem, so the complexity of the problem being solved is the important consideration. You can make an algorithm that is clunky and inefficient, but that would be from lack of knowledge and ability from the user, not from the nature of algorithms in general. Some good algorithms can have complex procedures, but only because many steps are needed to solve a large or unfriendly problem. In short, you want your algorithm to be as simple as possible while remaining powerful enough to handle the problem you give it to solve - doing this will come from good modeling practice, a knowledge of the mathematics behind the algorithms, and from experience of the user.

6. Finally, you can be concerned with the performance. This is the most simple part (because it usually does not require mathematical proofs) and usually just involves running the algorithm for several test problems or against another algorithm and measuring how efficient and fast it is for the type of problems you are dealing with. The most simple way to do this is to count the number of function evaluations, as this will give you a good metric for understanding how much it "costs" to use your algorithm in terms of time and computational power.

In my previous answer,

1. Final error, exit flag, and amount of constraint violation show convergence

2. Sensitivity to starting point and convergence tolerance show robustness

3. Number of function evaluations shows performance

Is this a helpful explanation? I hope the others will add to this and give more formal answers

Is this any help?

" Best Practices for Comparing Optimization Algorithms"

https://arxiv.org/pdf/1709.08242.pdf

or this

" A Benchmark Study of Optimization Search Algorithms"

http://www.redcedartech.com/pdfs/SHERPA_Benchmark_0110.pdf

and have a look at these

http://www.cleveralgorithms.com/nature-inspired/advanced/racing_algorithms.html

https://www.mcs.anl.gov/~more/dfo/

https://www.sfu.ca/~ssurjano/optimization.html

https://github.com/ralna/CUTEst/wiki

The trade-off criteria for deciding whether to use an optimization algorithm for solving a given problem is to arrive at an optimal solution/solutions with completeness, accuracy and precision with faster execution time.

In general,

1) The minima of the test functions are compared to show its optimal performance.

2)the convergence curves (Best solutions obtained so far Vs Number of iterations) of the optimization algorithms are compared to show how fast your algorithm is giving the best solution.

3) Algorithm can be tested on various test functions (uni-modal/ multi modal) to prove its completeness.

4) Algorithm can be run for several times and the average and the standard deviation of each test function can be compared to show its stability.

So far no-one has designed a fool-proof measure based on the performance profile, which otherwise is very good for the purpose of comparing *two* algorithms. With three competitors you may receive a result that is not to be trusted, as demonstrated a few years ago. So does anyone have a better tool?

By the way, a comparison - it seems to me - can only be trusted if we compare methodologies that can actually find an *optimum*. How do you compare a meta-heuristic's performance when it almost never reaches an optimum, and cannot even declare that it is found? We need an optimality certificate, and I don't see one is this thread.

It is hard to compare the performance of two optimization heuristics as most heuristics are mostly suited for special classes of problems. What you can do as mentioned of course is to compare

1. CPU time

2. Function evaluations

3. How fast and how well they converge starting from the same initial point

Hi Dear Colleagues Albert E. Patterson , Jeremy Dudley , Prajna Kunche , Michael Patriksson , Temitayo Bankole I have first to apologize for the delay to give feedback on your contributions, orientations and references, being busy to deal with some very urgent issues.

I will give a general response as comment for all:

1. The optimization algorithm can be a new heuristic or an improvement of existing one;

2. An heuristic is an algorithm used for a specific given Problem;

3. If it can be used for different kind of problems it isn't any more an heuristic, it define a meta-heuristic;

4. We deal, in our case, with a given problem, with its benchmarks, and different algorithms applied on the same set of benchmarks;

5. Algorithm's complexity is a mathematics matter.

Thanks for all,

Djamel.

Dear Djamel,

Regarding the " 5. Algorithm's complexity is a mathematics matter". Could you mention more details, please?

Dear Mohammad Shehab ,

Thanks for you interest and contribution.

Concerning my previous fifth point: " 5. Algorithm's complexity is a mathematics matter", I will say the following:

The Algorithm's complexity is a computer science field where it matter to enumerate time, space or any other necessary resources for the algorithm execution. Where can be used a case numeration and arithmetic progression concepts.

Since different implementations of the same algorithm may differ in efficiency, asymptotic estimates are, usually, used.

The complexity is generally expressed as a mathematical function: big O notation, typically O ( n ).

Time/space complexity can be Linear, Polynomial, Logarithmic, Exponential, etc. It defines complexity classes which can be study as a Sets' inclusion, with the P versus NP unsolved problem where it is matter of “Logic”, Sets and Isomorphism problem.

So Algorithm's complexity is a computer science field using strongly mathematics' concepts. It is in such sense that is a mathematics matter.

Sincerely, Djamel.

Thanks a lot Fateh Boutekkouk

I proposed an improvement of existing heuristics with respect of the Agent technology using the Influence/Reaction Principle. These implementations were implemented on agent platforms such as Jade and Madkit.

With my publication: Article Agent Influence/Reaction Ant System Variants: An Experimenta...

I was confused when I have been asked (in the review phase) to speak about the convergence of my Agent Algorithms, which seem to perform better than previous ones performed on the same benchmarks. I manage, but I still wonder about this issue.

After the publication, I asked on RG the question :

Convergence versus Performance ? It still without response, perhaps it was not clear enough !!!!

Your response can be used to affirm that :

"For a given algorithm its best performance is enough to attest its convergence".

Sincerely, Djamel.

Thank you very much Djamel Zeghida for the explanation.

Dear Mohammad Shehab

It was an honor for me, Thanks a lot Mohammed.

As you know, the term Algorithm has its origins in the name of the Mohamed Ibn Moussa El Khawarismy, the prominent scientist and Mathematician who gave rules and "define" the Algebra as a part of mathematics.

Also, by 1894, the German Mathematician and historian of mathematics, Paul Bachmann defines the Big-O notation, used after that as a notation of the algorithms' complexity.

Sincerely, Djamel.

If you are using Matlab for example, you can modify for your convenient all the parameters of the optimization methods just by using optimization tool box.

Dear Azeddine Kabouche ,

Thank you for your interest and contribution.

"Unfortunately", I'm not using Matlab.

I'm using the Jade and Madkit agent platforms.

Sincerely, Djamel.

Djamel Zeghida You are welcome.

Djamel: it is indeed a problem when a researcher claims that a methodology is convergent, without actually establishing it in theory. I have seen many papers in my day, where an individual or a group of scientists claim that some new methodology is better than another group of methods were. (Nowadays I see many metaheuristics claimed to be superior, while there is NEVER any argument even for their convergence.) That claim can certainly be correct, but only for the limited test cases that they used. It is however NOT a proof that one method is ALWAYS better than another, AND it is not even a proof that the winning method is even convergent! You need to confirm - for a clearly specified subset of problems (with a precise definition of their properties in terms of continuity, convexity, etcetera) that the methodology terminates with an optimal solution - fair and square - or else admit that you do not have a proof of convergence, while you have experienced that it almost always work.

Djamel Zeghida Proof of convergence can be non trivial in some cases. For heuristics, the argument can only be made that since it converges on most test cases, it will converge on any given problem. At least to a local optimum

Temitayo: you can't even guarantee that! Typically the methodology will *not* search every point in a neighbourhood around a given solution, whence you will not be sure whether you are at a local optimum, for example.

Most researchers that I have come across here, and many in reality, appear to not know even the most rudimentary basics on optimality in operations research. This is quite shocking, and I fear that "scientists" at large do not even really care whether they are doing it right or not - just publish at all costs is the dogma. Not surprising then that what I see here at RG mostly is re-hashes or hastily done work.

If anyone has a different view, then please show me a more positive one.

Dear Michael Patriksson and Temitayo Bankole

I'm so honored and glad to have your reflections on my question.

I have first to give some clarifications for Micheal's answer and after that comment both Temitayo's contribution and Michael's replica on it.

Dear Micheal, I completely agree with you that convergence has to be established and proved and not just claimed without proof.

I never claim the convergence of my proposed algorithms at all. I just give an experimental comparative study where I have proved that my improved algorithms perform better than the previous ones. So I claimed, experimentally, the performance of these algorithms not their convergence.

But I was confused if performance lead to convergence, so I asked, three months ago, a question on RG: Convergence_versus_Performance

https://www.researchgate.net/post/Convergence_versus_Performance

Which still without response until now!!!.

Dear Temitayo, I completely agree with you on the content of the first sentence; that the "Proof of convergence can be non trivial in some cases". For the remaining of your answer, I will say that in these cases, if it can be proved, we will claim the heuristic's convergence under some restricted constraints and for specific application cases not for the heuristic in general for whom its convergence remains not established. For all this, I find Micheal's replica on your answer very justified.

Sincerely, Djamel.

Convergence, stop criteria, roundoff errors, local extrema etc. However, the worst is if the objective function has the form of a "multidimensional bucket". That is fast away from the extreme and almost no changes nearby. The solution of such a task may be an assessment of the algorithm perfomance. Regards,

You may be able to establish a theoretical upper bound on the difference between the optimal and the heuristic. If not, you may design some experiments and pick a typical version of your problem with ranges of parameters and then establish the empirical gap that way. If the algorithm is not deterministic, then you have to run it sufficient number of times and then you can look at the worst, best, average performances and the variance, etc. CPU time and worst case theoretical complexity are also important.