Assessing Metaheuristics by Means of Random Benchmarks

AbstractTypically, the performance of swarm and evolutionary methods is assessed by comparing their results when applied to some known finite benchmarks. In general, these metaheuristics depend on many parameter values and many possible exchangeable sub-steps, which yields a huge number of possible algorithm configurations. In this paper we argue that this high setup versatility lets developers expressively tune the method, in an ad-hoc way, to the target inputs to be solved, and hence to those in the benchmark under consideration. However, this does not imply properly solving any other input not considered in the benchmark. Several subtle ways to support that tuning (which can be consciously noticed by the developer, but can also be unconscious) are presented and discussed in the paper. Besides, as a possible alternative to using known finite benchmarks, we discuss the pros and cons of using random input generators, and we illustrate how to use such generators in a specific problem, MAX-3SAT. A general protocol to support the fair development of comparisons of metaheuristics based on random input generators is presented