Dear Manar I. Hosny,

Usually, researchers set the maximum number of function evaluations as the stoppage criterion so as to make sure that the algorithms being compared have sampled the search space equal number of times. The following reference can be helpful:

Andries P. Engelbrecht:

Fitness function evaluations: A fair stopping condition? SIS 2014: 181-188

Regards,

The below paper is very a good one, but it does not discuss anything about  runtime complexity:

Francisco B. Pereira, , Jorge Tavares, Penousal Machado, Ernesto Costa. GVR: a New Genetic Representation for the Vehicle Routing Problem

Dear Manar I. Hosny,

Usually, researchers set the maximum number of function evaluations as the stoppage criterion so as to make sure that the algorithms being compared have sampled the search space equal number of times. The following reference can be helpful:

Andries P. Engelbrecht:

Fitness function evaluations: A fair stopping condition? SIS 2014: 181-188

Regards,

When comparing metaheuristics, as Soheila stated, the algorithms under study are given the same number of fitness function evaluations (or time).

A different point is if you want to measure how long it takes for an algorithm to reach a solution with a  given cost.

Anyway, you should first need to define what do you want to assess and then which measures should be used.

I think it's more complicated.  For meta-heuristics based on neighbourhood search, it is sometimes possible to evaluate the best neighbour more efficiently by using clever data structures.  For example, the well-known "flip" neighbourhood for the max-cut problem involves moving one node from one shore of the cut to the other.  If you search this neighbourhood in a naïve way, it takes O(n^2) time to find the best neighbour.  But if you use an appropriate data structure, you can search it in O(n) time.  The key is not to evaluate the cost function from scratch each time, but exploit the information you collected in the previous iteration..

Dear Manar I. Hosny,

In my opinion, as stated by Soheila and David before me, a good complexity index of a metaheuristic algorithm is something related to the number of fitness evaluations.

In general, when I choose an algorithm I am interested in the performances in terms of success rate and evaluation time. However, if I have to choose between your algorithm and one developed by someone else, it is very likely that the two algorithms have been tested on different objective functions, which makes any comparison about the elapsed time meaningless.

I think you can find a very detailed example of how to measure the performances of an algorithm (in terms of success rate, complexity, etc.) in any edition of the Congress on Evolutionary Computation (CEC). For example, the report of the 2005 edition states very clearly how the performances of the algorithms are defined. You can have a look at it (the evaluation criteria start at page 40):

https://www.lri.fr/~hansen/Tech-Report-May-30-05.pdf

I hope this can be of any help for you.

Cheers,

Alessandro

Hello Manar.

In general, I disagree with this practice of using function evaluations as  

Thank you all for your replies. They are very useful indeed!

What if you are comparing a population based algorithm with a single solution based algorithm, would it be fair to assign the same number of objective function evaluations as a stopping condition for both? wouldn't this limit the opportunity of the population based algorithm to explore the search space?

Leonardo Bezerra, why don't you agree with this practice? could you please explain more? Your reply seems to be cut for one reason or another!

Thanks,

Using approximations to the utility function transforms a multiple objective task into a series of single objective tasks. At least in engineering, the search space decreases if substitute the ideal values by desirable values of each objective. This way the complexity could substantially decrease.  

Best wishes,

Jose Arzola

Hello, Manar.

As far as I know, the number of objective function evaluations is not an accurate measure of algorithm complexity. As the computation for construct a solution or make a perturbation on a solution may vary between different algorithms.

To evaluate the complexity you could set the same number of function evaluations for all algorithms and compare the execution time of each algorithm.

But that is not an accurate measure also because of various situations that can affect the runtime, e.g. the workload.

Also, you should use the same machine under the same conditions for all executions.

Another measure that you can compare is the convergence (how good is the quality of the solutions throughout the execution). In that way, you can evaluate how long each algorithm took to reach an optimal solution (local or global).

I hope, I helped.

In the work attached you can find some examples of substitution the ideal values by desirable ones of each objective.

Regards,

I have issue with the phrase 'accurate measure' since accuracy is  very subjective . However, I think that number of objective function evaluation is one of the effective measure of the performance of meta-heuristic algorithms

 You can use it as follows: i) if you want to design a fair comparison between   ABC algorithm 10 bees and ACO algorithm with 20 ants then the maximum number function evaluations should be the stop condition of both algorithms. ii) if you want to measure the efficiency of the two metaheuristic algorithms you can set their objective functions equal to a predefined solution as a stop condition then check the resulted number of function evaluations.

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