Methods to compare expensive stochastic optimization algorithms with application to road design

Analyzing test data of stochastic optimization algorithms under random restarts is challenging. The data needs to be resampled to estimate the behavior of the incumbent solution during the optimization process. The estimation error needs to be understood in order to make reasonable inference on the actual behavior of the incumbent solution. Comparing the performance of different algorithms based on proper interpretation of the estimator is also very important. We model the incumbent solution of the optimization problem over time as a stochastic process and design an estimator of it based on bootstrapping from test data. Some asymptotic properties of the estimator and its bias are shown. The estimator is then validated by an out-of-sample test. Three methods for comparing the performance of different algorithms based on the estimator are proposed and demonstrated with data from a road design optimization problem.Arts and Sciences, Irving K. Barber School of (Okanagan)Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan)Graduat