How can we conclude that an optimization algorithm is better than another one
Whenever possible, you should use the average performance when comparing different methods, and preferably even mention the standard deviation across different runs (see this question for an example why it's important sometimes). It's perfectly fine to also provide the best performance, ideally you can even present a boxplot comparison of the different methods.

What is really unacceptable is to compare a best performance for one method against a mean performance for the other method (it should go without saying but I remember a paper where the authors were happily doing just that in order to make their method look better).