Title: Experience-based Optimization: A Coevolutionary Approach,
Abstract: This paper studies improving solvers based on their past solving experiences,
and focuses on improving solvers by offline training. Specifically, the key
issues of offline training methods are discussed, and research belonging to
this category but from different areas are reviewed in a unified framework.
Existing training methods generally adopt a two-stage strategy in which
selecting the training instances and training instances are treated in two
independent phases. This paper proposes a new training method, dubbed LiangYi,
which addresses these two issues simultaneously. LiangYi includes a training
module for a population-based solver and an instance sampling module for
updating the training instances. The idea behind LiangYi is to promote the
population-based solver by training it (with the training module) to improve
its performance on those instances (discovered by the sampling module) on which
it performs badly, while keeping the good performances obtained by it on
previous instances. An instantiation of LiangYi on the Travelling Salesman
Problem is also proposed. Empirical results on a huge testing set containing
10000 instances showed LiangYi could train solvers that perform significantly
better than the solvers trained by other state-of-the-art training method.
Moreover, empirical investigation of the behaviours of LiangYi confirmed it was
able to continuously improve the solver through training.