Ordinal comparison of heuristic algorithms using stochastic optimization

The performance of heuristic algorithms for combinatorial optimization is o ften sensitive to problem instances. In extreme cases, a specialized heuris tic algorithm may perform exceptionally well on a particular set of instanc es while fail to produce acceptable solutions on others, Such a problem-sen sitive nature is most evident in algorithms for combinatorial optimization problems such as job shop scheduling, vehicle routing, and cluster analysis . This paper proposes a formal method for comparing and selecting heuristic algorithms (or equivalently, different settings of a same algorithm) given a desired confidence level and a particular set of problem instances. We f ormulate this algorithm comparison problem as a stochastic optimization pro blem. Two approaches for stochastic optimization, Ordinal Optimization and Optimal Computing Budget Allocation are applied to solve this algorithm sel ection problem. Computational testing on a set of statistical clustering al gorithms in the IMSL library is conducted. The results demonstrate that our method can determine the relative performance of heuristic algorithms with high confidence probability while using a small fraction of computer times that conventional methods require.