OpenAIR @ RGU >
Design and Technology >
Computing >
Conference publications (Computing) >

Please use this identifier to cite or link to this item:
This item has been viewed 7 times in the last year. View Statistics

Files in This Item:

File Description SizeFormat
AI07-weightsVsPenatls.pdf324.6 kBAdobe PDFView/Open
Title: Escaping local optima: constraint weights vs. value penalties.
Authors: Basharu, Muhammed
Arana, Ines
Ahriz, Hatem
Keywords: Local optima
Constraint satisfaction problems
Iterative improvement techniques
Constraint violation
Penalty based algorithm
Constraint weights
Issue Date: 2007
Publisher: Springer Verlag
Citation: BASHARU, M., ARANA, I. and AHRIZ, H. 2007. Escaping local optima: constraint weights vs. value penalties. In: M. BRAMER, F. COENEN and PETRIDIS, M. (eds.) Research and development in intelligent systems XXIV. Proceedings of the 27th SGAI International Conference on Artificial Intelligence, AI-07, 10-12 December 2007. Cambridge. pp. 51-64
Abstract: Constraint Satisfaction Problems can be solved using either iterative improvement or constructive search approaches. Iterative improvement techniques converge quicker than the constructive search techniques on large problems, but they have a propensity to converge to local optima. Therefore, a key research topic on iterative improvement search is the development of effective techniques for escaping local optima, most of which are based on increasing the weights attached to violated constraints. An alternative approach is to attach penalties to the individual variable values participating in a constraint violation. We compare both approaches and show that the penalty-based technique has a more dramatic effect on the cost landscape, leading to a higher ability to escape local optima. We present an improved version of an existing penalty-based algorithm where penalty resets are driven by the amount of distortion to the cost landscape caused by penalties. We compare this algorithm with an algorithm based on constraint weights and justify the difference in their performance.
ISBN: 9781848000933
Appears in Collections:Conference publications (Computing)

All items in OpenAIR are protected by copyright, with all rights reserved.


   Disclaimer | Freedom of Information | Privacy Statement |Copyright ©2012 Robert Gordon University, Garthdee House, Garthdee Road, Aberdeen, AB10 7QB, Scotland, UK: a Scottish charity, registration No. SC013781