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).

[img] PDF
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 [2]. 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)
Research Group:
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 237670