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 5 times in the last year. View Statistics

Files in This Item:

File Description SizeFormat
Ahriz DCR2005.pdf205.47 kBAdobe PDFView/Open
Title: Escaping local optima with penalties in distributed iterative improvement search.
Authors: Basharu, Muhammed
Arana, Ines
Ahriz, Hatem
Keywords: DisPeL
Distributed Constraint Satisfaction Problems (DisCSPs)
Local optima
Issue Date: Jul-2005
Publisher: IJCAI
Citation: BASHARU, M., ARANA, I. and AHRIZ, H., 2005. Escaping local optima with penalties in distributed iterative improvement search. In: Proceedings of the 6th International Workshop on Distributed Constraint Reasoning, DCR2005. 30 July 2005. pp. 192-206.
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.
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