Skip to main content

Research Repository

See what's under the surface

Advanced Search

Escaping local optima: constraint weights vs.

Basharu, Muhammed; Arana, Inés; Ahriz, Hatem

Authors

Muhammed Basharu

Inés Arana

Hatem Ahriz



Contributors

Max Bramer
Editor

Frans Coenen
Editor

Miltos Petridis
Editor

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.

Start Date Dec 10, 2007
Publication Date Dec 31, 2007
Publisher Springer (part of Springer Nature)
Pages 51-64
ISBN 9781848000933
Institution Citation BASHARU, M., ARANA, I. and AHRIZ, H. 2008. Escaping local optima: constraint weights vs. value penalties. In Bramer, M., Coenen, F. and Petridis, M. (eds.) Research and development in intelligent systems XXIV: technical proceedings of the 27th Annual international conference of the British Computer Society's Specialist Group on Artificial Intelligence (SGAI) (AI-2007): innovative techniques and applications of artificial intelligence, 10-12 December 2007, Cambridge, UK. London: Springer [online], pages 51-64. Available from: https://doi.org/10.1007/978-1-84800-094-0_5
DOI https://doi.org/10.1007/978-1-84800-094-0_5
Keywords Local optima; Constraint satisfaction problems; Iterative improvement techniques; Constraint violation; Penalty based algorithm; Constraint weights

Files





You might also like



Downloadable Citations

;