Number of function evaluations (NFEs) is the most important criterion to compare different algorithms for obtaining a VTR (value to reach). 

CPU time can be considered as well  as different optimization algorithms may have some additional features and NFEs do not reflect these.   

The average and standard deviation of sufficient number of runs to compare accuracy and reliability.

All the comparisons you gave are reasonable to select and compare between algorithms.  We must never forget that algorithms are for problems, so we compare algorithms based on the problems the algorithm is proven to solve (or approximately solve).  Ultimately, when it comes to algorithms themselves we usually (in general when we are after approximate or even exact solutions) at the end of the day care the most about:

1)  Efficiency - Does it take a long time to get the answer?  What do the time-complexities dictate?  Also how much space is required?  Are we considering many instances, or just a select bunch that would operate "average" for that problem.

2) Quality of solution - In turn with (1), many optimization algorithms are very efficient but only yield answers within a factor of the optimal (with respect to exact-solution algorithms).  Does the problem also require exact answers?  Is the algorithm worth running that long to solve the problem?  Or can an approximate answer be fine.  I mean, for most NP-hard problems, we just go after the approximate answer unless you have the resources to exhaust a result.

Most research motivations in Algorithms are driven by these two factors, and the interplay between them is what is worth exploring the most and giving pragmatic results at the end of the day.  For example, a user or employer typically  isn't going to sit around 1 day for something that I could do that is maybe 3/4 as good, but takes 5 seconds to do unless they are willing to sacrifice that crunching time for an exact answer.

Hope this helps! 

For performance evaluation Number of Function Evaluations(FEs) is considered in following ways. Eg. 1. For a particular  number of FEs optimal obtained is observed.  Eg. 2. Success rate can be measured on the basis of pre-specified target optimal value or FEs.

Number of Iteration or Generations(NG) can also be utilized as FEs. 

Another way to measure performance is convergence rate of algorithms to reach optimal value. For this purpose, best or average optimal value achieved is observed at regular interval of   NG or FEs.

Some statistics such as Mean, Standards deviation, median etc. can also be measured for multiple runs (say 50 or 100) of algorithms. 

In my view, the best way "to ensure fair comparison between optimization methods "A" and "B" is the development of Online Tool "A" (Site "A") and Online Tool "B" (Site "B") in the Internet to be accepted for any users to compare "A" and "B" for their personal input data. Then you will get a huge statistics that would be the best way to justify that "A" is better than "B" or vice versa. This way would be the best solution for all people as scientists, researchers, practitioners, and usual users without any special knowledge.

• You need to to test them on standard problems. 
• Compare the average , minimum , maximum best solutions they find 
• Convergence speed (how many iterations does it usually take to converge?)
• Simulation speed (CPU time)

BY hybrid method you can make a comparison between wheating methods, epslom constraints method  for the multi-objective problem

Other answers have covered time and accuracy. One additional consideration is tuning. Most method have parameters you can set, and neighborhood search methods depend on the definition of the neighborhood. For most accurate comparison, either use default settings for all methods or, better still, tune each method for the class of problems being considered.

I'd say the number of function evaluations and then the overall CPU time (as long as the accuracy of obtained solutions are comparable).

Since value and time are less meaningful if one of those is used as stopping condition, I would suggest to use anytime plots. For this plot the progress of value (or bound) over CPU or REAL time. Some methods will make fast progress, other will provide later a useful solution but give in the end the best or optimal results. Anytime plots do not give You a number to compare but show more detailed what is going on.

You should also keep in mind that it often does not make sense to find the global optimal solution. Model noise can cause near optimal solutions to be better when it is evaluated on application specific loss.

Further points are:

*scalability of a method

* can the method be parallelized

Other important points has already be mentioned:

* selection of test instances

* tuning of parameters

Finally keep in mind that You do not compare methods, You compare the implementations of methods. This is a tiny but fundamental difference.

I think that the application of any approximate solution needs justification. It means that you must prove that the problem cannot be solved exactly. We should distinguish "online" and "design" problems. "Online" problems must be solved many times within a short time frame. In that case the necessary CPU time matters a lot. In the case of "design" problems it is enough to solve the problem only once but in that case its effect is long-term Therefore the quality of the solution is more important than CPU time. I agree with Paul. Exact solvers have a lot of parameters. They give feasible solutions and the obtained feasible solutions are different if the values of the parameters are different. Thus you must also compete with exact model started to be solved by exact solvers but the solver is stopped within a certain time frame.

This discussion is almost completely overlaps with the discussions on the links:

https://www.researchgate.net/post/Can_anyone_give_more_clarification_on_the_difference_between_the_effectiveness_and_efficiency_of_an_algorithm/2

https://www.researchgate.net/post/Is_there_really_a_significant_difference_between_the_performance_of_the_different_meta-heuristics_other_than_e2

1. Currently, developing any approximation algorithm "A" is not a big problem usually. Therefore, there are very many different approximation algorithms "A" to find any apparoximate solution A(D), where D is input data. Looking through any paper, I don't read description of approximation algorithm "A" in detail. I is not interested never know about this approximation algorithm in detail, absolutely is not interested. I know that I could develop always my personal approximation algorithm "B" if it would be necessary to me. Therefore I want to ask: if you think that you developed effective approximation algorithm, then please place your algorithm in the Internet as an Online Tool to be accepted for any users to use your algorithm for personal input data. In my opinion, currently, development of any approximation algorithm (heuristics, metaheuristics, an so on) IS CRAFT BUT NOT SCIENCE ITSELF.

2. In contrast to approximate algorithms, development of quality Lower Bounds LB(D) has huge value in order to evaluate quality of A(D) by a formula p = 100% * (A(D) - LB(D)) / LB(D) . From this point of view, in my opinion development of any quality LB(D) IS ONLY SCIENCE BUT NOT CRAFT.

Thus, please concentrate your attention on finding quality lower bounds. Now that would be a million times more meaningful for science.

I agree with those previous speakers who deem algorithm testing a quite unscientific exercise, if hese tests are not very carefully executed, AND illuminated. Remember the statement from gigantic scholars from the past: it is INSIGHT that we need, not NUMBERS. Tests should not be performed only on  a small set of randomly selected problems - they need to focus on many other aspects that are important for the problem that is addressed, and great care is needed.

The art of performing and presenting computational experiments that are of use for anyone else but yourself is a very demanding one, indeed! 

The quality of solution(optimal), the number of function evaluations(NFE's) and then the overall CPU time.

I would say the number of function/gradient evaluations and then the overall CPU time required to obtain highly accurate solutions.

For this propose, the use of statistical methods such as the Wilcoxon method is appropiate