Measuring the effectiveness and efficiency of simulation optimization metaheuristic algorithms

Abstract Metaheuristic algorithms have proven capable as general-purpose algorithms for solving simulation optimization problems. Researchers and practitioners often compare different metaheuristic algorithms by examining one or more measures that are derived through empirical analysis. This paper presents a single measure that can be used to empirically compare different metaheuristic algorithms for optimization problems. This measure incorporates both the effectiveness and efficiency of the metaheuristic algorithm, which is especially important in simulation optimization applications because the number of simulation runs available to the analyst (i.e., the run budget) can vary significantly with each simulation study. Therefore, the trade-off between the effectiveness and efficiency of a metaheuristic algorithm must be examined. This single measure is especially useful for multi-objective optimization problems; however, determining this measure is non-trivial for two or more objective functions. Additional details for calculating this measure for multi-objective optimization problems are provided as well as a procedure for comparing two or more metaheuristic algorithms. Finally, computational results are presented and analyzed to compare the performance of metaheuristic algorithms using knapsack problems, pure binary integer programs, traveling salesman problems, and the average results obtained across a diverse set of optimization problems that include simulation and multi-objective optimization problems.