Optimization by precomputation

摘要

We discuss the scenario of developing an optimizer for a given space of problem instances. Standard practice typically resorts to choosing a broad approach (such as evolutionary search), then tuning the optimizer based on example problem instances, and/or hybridizing with domain-specific heuristics and expert knowledge. This will lead to a capable optimizer for the task, but we argue that the delivered optimizer will dramatically under-exploit domain information. We propose a different approach, in which the optimizer may be capable of (comparatively) ultra-fast and effective performance on new instances. The essence of this approach is straightforward: in the extreme, we can solve all possible instances of interest during development, and then deliver an ‘optimizer’ in the form of a lookup table. In practice, the approach effects a compromise, exploiting a very large base of pre-computed solutions to bootstrap the solving of new instances. We explore this idea in the simple context of seeding a simple evolutionary algorithm with solutions selected from a large pre-solved set. We find in three test domains that optimizers exploiting a large base of pre-solved instances can deliver significantly better results.