Progress Control in Variable Neighbourhood Search
Curtois, T. and Fijn van Draat, L. and Post, G.F. and Ommeren, J.C.W. van (2006) Progress Control in Variable Neighbourhood Search. In: Proceedings of the 6th International Conference on the Practice and Theory of Automated Timetabling, 30 Aug - 01 Sept 2006, Brno, The Czech Republic (pp. pp. 376-380).
Restricted to UT campus only : Request a copy
|Abstract:||The methods of intensification and diversification are indispensable in successful meta heuristics for local search. Intensification corresponds in some sense to local optimisation; the neighbourhood of a solution is searched intensively for solutions which are better or have better opportunities. On the other hand, diversification tries to escape from (relatively small) neighbourhoods to solutions which might lead to better final results. A heuristic that is well aware of the intensification versus diversification problems, is the Variable Neighbourhood Search (VNS), see . In this method, more than one neighbourhood structure is considered. After finishing intensification with respect to one neighbourhood, the heuristic diversifies to another neighbourhood. In this way one hopes to escape from poor local optima.
In this work we introduce a model to predict the quality of a neighbourhood. We use this model to identify 'bad' neighbourhoods and avoid searching them. We call this process 'Progress Control'. Computational results are presented to show that progress control helps us finding better solutions in the same amount of time.
|Item Type:||Conference or Workshop Item|
Electrical Engineering, Mathematics and Computer Science (EEMCS)
|Link to this item:||http://purl.utwente.nl/publications/63728|
|Export this item as:||BibTeX|
Daily downloads in the past month
Monthly downloads in the past 12 months
Repository Staff Only: item control page
Metis ID: 237670