Diederick L. Vermetten

Non-Elitist Selection among Survivor Configurations can Improve the Performance of Irace

View CodeNotebook

Modern optimization strategies such as evolutionary algorithms, ant colony algorithms, Bayesian optimization techniques, etc.~come with several parameters that steer their behavior during the optimization process. To obtain high-performing algorithm instances, automated algorithm configuration techniques have been developed. One of the most popular tools is irace, which evaluates configurations in sequential races, at the end of which a statistical test is used to determine the set of survivor configurations. It then selects up to five elite configurations from this set, via greedy truncation selection. We demonstrate that an alternative selection of the elites can improve the performance of irace. Our strategy keeps the best survivor and selects the remaining configurations uniformly at random from the set of survivors. We apply this alternative selection method to tune ant colony optimization algorithms for traveling salesperson problems and to configure an exact tree search solver for satisfiability problems. We also experiment with two non-elitist selection criteria, based on entropy and Gower's distance, respectively. Both methods provide more diverse configurations than irace, making them an interesting approach for exploring a wide range of solutions and understanding algorithms' performance. Moreover, the entropy-based selection performs better on our benchmarks than the default selection of irace.

Via