Muhammed Basharu
Escaping local optima: constraint weights vs value penalties.
Basharu, Muhammed; Arana, In�s; Ahriz, Hatem
Authors
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.
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
Presentation Conference Type | Conference Paper (published) |
---|---|
Conference Name | 27th Annual international conference of the British Computer Society's Specialist Group on Artificial Intelligence (SGAI) (AI-2007) |
Start Date | Dec 10, 2007 |
End Date | Dec 12, 2007 |
Acceptance Date | Dec 31, 2007 |
Online Publication Date | Dec 31, 2007 |
Publication Date | Dec 31, 2007 |
Deposit Date | Dec 23, 2008 |
Publicly Available Date | Dec 23, 2008 |
Publisher | Springer |
Peer Reviewed | Peer Reviewed |
Pages | 51-64 |
ISBN | 9781848000933 |
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 |
Public URL | http://hdl.handle.net/10059/279 |
Contract Date | Dec 23, 2008 |
Files
BASHARU 2007 Escaping local optima
(332 Kb)
PDF
Publisher Licence URL
https://creativecommons.org/licenses/by-nc-nd/4.0/
You might also like
Real-time relative permeability prediction using deep learning.
(2018)
Journal Article
Stoch-DisPeL: exploiting randomisation in DisPeL.
(2006)
Presentation / Conference Contribution
Escaping local optima with penalties in distributed iterative improvement search.
(2005)
Presentation / Conference Contribution
Verification of redesign models: a CSP approach.
(2001)
Presentation / Conference Contribution
DisBO-wd: a distributed constraint satisfaction algorithm for coarse-grained distributed problems.
(2007)
Presentation / Conference Contribution
Downloadable Citations
About OpenAIR@RGU
Administrator e-mail: publications@rgu.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2025
Advanced Search