DocumentCode :
2456796
Title :
Optimization by precomputation
Author :
Corne, David ; Reynolds, Alan
Author_Institution :
Dept. of Comput. Sci., Heriot-Watt Univ., Edinburgh, UK
fYear :
2011
fDate :
19-21 Oct. 2011
Firstpage :
552
Lastpage :
557
Abstract :
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.
Keywords :
evolutionary computation; statistical analysis; domain-specific heuristics; expert knowledge; optimizer; precomputation; simple evolutionary algorithm; Algorithm design and analysis; Context; Knowledge based systems; Optimization; Routing; Tuning; Vehicles; combnatorial problems; hyper-heuristics; knowledge-based optimisation; memory-based methods; optimisation;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Nature and Biologically Inspired Computing (NaBIC), 2011 Third World Congress on
Conference_Location :
Salamanca
Print_ISBN :
978-1-4577-1122-0
Type :
conf
DOI :
10.1109/NaBIC.2011.6089648
Filename :
6089648
Link To Document :
بازگشت