Muhammed Basharu
Escaping local optima with penalties in distributed iterative improvement search.
Basharu, Muhammed; Arana, In�s; Ahriz, Hatem
Abstract
The advantages offered by iterative improvement search make it a popular technique for solving problems in centralised settings. However, the key challenge with this approach is finding effective strategies for dealing with local optima. Such strategies must push the algorithm away from the plateaux in the objective landscape and prevent it from returning to those areas. A wide variety of strategies have been proposed for centralised algorithms, while the two main strategies in distributed iterative improvement remain constraint weighting and stochastic escape. In this paper, we discuss the two phased strategy employed in Distributed Penalty Driven Search (DisPeL) an iterative improvement algorithm for solving Distributed Constraint Satisfaction problems. In the first phase of the strategy, agents try to force the search out of the local optima by perturbing their neighbourhoods; and use penalties, in the second phase, to guide the search away from plateaux if perturbation does not work. We discuss the heuristics that make up the strategy and provide empirical justification for their inclusion. We also present some empirical results using random non-binary problems to demonstrate the effectiveness of the strategy.
Citation
BASHARU, M., ARANA, I. and AHRIZ, H. 2005. Escaping local optima with penalties in distributed iterative improvement search. Presented at the 6th International workshop on distributed constraint reasoning (DCR 2005), part of the 19th International joint conference on artificial intelligence (IJCAI-05), 30 July - 5 August 2005, Edinburgh, UK.
Presentation Conference Type | Conference Paper (unpublished) |
---|---|
Conference Name | 6th International workshop on distributed constraint reasoning (DCR 2005) |
Start Date | Jul 30, 2005 |
End Date | Aug 5, 2005 |
Deposit Date | Oct 8, 2009 |
Publicly Available Date | Oct 8, 2009 |
Peer Reviewed | Peer Reviewed |
Keywords | DisPeL; Distributed Constraint Satisfaction Problems (DisCSPs); Local optima; DisCSPs |
Public URL | http://hdl.handle.net/10059/428 |
Contract Date | Oct 8, 2009 |
Files
BASHARU 2005 Escaping local optima with penalties
(210 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
Verification of redesign models: a CSP approach.
(2001)
Presentation / Conference Contribution
Escaping local optima: constraint weights vs value penalties.
(2007)
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