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)
• Conference Location: Edinburgh, UK
• Start Date: Jul 30, 2005
• End Date: Aug 5, 2005
• Deposit Date: Oct 8, 2009
• Publicly Available Date: Oct 8, 2009
• Keywords: DisPeL; Distributed Constraint Satisfaction Problems (DisCSPs); Local optima; DisCSPs
• Public URL: http://hdl.handle.net/10059/428