An Integrated White+Black Box Approach for Designing and Tuning Stochastic Local Search

Publication Type

Conference Proceeding Article

Publication Date

9-2007

Abstract

Stochastic Local Search (SLS) is a simple and effective paradigm for attacking a variety of Combinatorial (Optimization) Problems (COP). However, it is often non-trivial to get good results from an SLS; the designer of an SLS needs to undertake a laborious and ad-hoc algorithm tuning and re-design process for a particular COP. There are two general approaches. Black-box approach treats the SLS as a black-box in tuning the SLS parameters. White-box approach takes advantage of humans to observe the SLS in the tuning and SLS re-design. In this paper, we develop an integrated white+black box approach with extensive use of visualization (white-box) and factorial design (black-box) for tuning, and more importantly, for designing arbitrary SLS algorithms. Our integrated approach combines the strengths of white-box and black-box approaches and produces better results than either alone. We demonstrate an effective tool using the integrated white+black box approach to design and tune variants of Robust Tabu Search (Ro-TS) for Quadratic Assignment Problem (QAP).

Discipline

Artificial Intelligence and Robotics | Business | Operations Research, Systems Engineering and Industrial Engineering

Publication

International Conf. on Principles & Practice of Constraint Programming (CP)

First Page

332

Last Page

347

ISBN

9783540749691

Identifier

10.1007/978-3-540-74970-7_25

Publisher

Springer Verlag

Additional URL

http://dx.doi.org/10.1007/978-3-540-74970-7_25

Link to Full Text

Share

COinS