4
$\begingroup$

I am trying to solve the capacitated vehicle routing problem (CVRP) with the ALNS metaheuristic.

To test the performance of my algorithm I run it 10 times and I want to calculate the average of the results obtained in each run.

My question is: is the calculation of the average in this case done quite simply by the formula avg = Sum of all values ​​÷ number of values, or is there another way to calculate the average to evaluate the results of metaheuristics?

Improve this question
$\endgroup$
7
$\begingroup$

There are multiple ways you can analyze and compare the results of heuristics/randomized search procedures.

  1. Report the average, best and worst
  2. Report the average, and standard deviation
  3. Graphically represent the results as a boxplot.

When computing the average, you need to be careful when there are instances that could not be solved by the heuristic. This holds in particular for problems where finding a feasible solution is challenging. In such a case, one should also report the number of instances for which a feasible solution was found.

Finally note that just reporting an objective value is not necessary very informative. In many cases, reporting the (average) optimality gap is much more insightful.

Improve this answer
$\endgroup$
2
  • $\begingroup$ thank you for your explanations, can you tell me the formula I can use to calculate the average and standard deviation for the same instance , and what do you mean by reporting the (average) optimality gap ? $\endgroup$ – user14053977 Feb 9 at 18:57
  • 1
    $\begingroup$ @JorisKinable I agree, optimality gap is more informative, and since the optimal value is most likely unavailable, the gap to the lower bound, or if no lower bound is in hand, the gap to the best found solution. $\endgroup$ – Mostafa Feb 10 at 2:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.