Combining Systematic and Local Search for Approximately Solving Fuzzy Constraint Satisfaction Problems

Sudo Yasuhiro, Kurihara Masahito

doi:10.1527/tjsai.21.20

Bibliographic Information

Other Title

系統的／局所的探索の協調によるファジィ制約充足問題の近似解法
ケイトウテキキョクショテキタンサクノキョウチョウニヨルファジィセイヤクジュウソクモンダイノキンジカイホウ

Search this article

Description

A fuzzy constraint satisfaction problem (FCSP) is an extension of the classical CSP, a powerful tool for modeling various problems based on constraints among variables. Basically, the algorithms for solving CSPs are classified into two categories: the systematic search (complete methods based on search trees) and the local search (approximate methods based on iterative improvement). Both have merits and demerits. Recently, much attention has been paid to hybrid methods for integrating both merits to solve CSPs efficiently, but no such attempt has been made so far for solving FCSPs. <br> In this paper, we present a hybrid, approximate method for solving FCSPs. The method, called the Spread-Repair-Shrink (SRS) algorithm, combines a systematic search with the Spread-Repair (SR) algorithm, a local search method recently developed by the authors. The SRS algorithm spreads (or expands) and shrinks a set of search trees in order to repair constraints locally until, finally, the satisfaction degree of the worst constraints (which are the roots of the trees) is improved. We empirically show that SRS outperforms the SR algorithm as well as the well-known methods such as Forward Checking and Fuzzy GENET, when the size of the problems is sufficiently large.

Journal

Transactions of the Japanese Society for Artificial Intelligence

Transactions of the Japanese Society for Artificial Intelligence 21 20-27, 2006

The Japanese Society for Artificial Intelligence

Keywords

Details 詳細情報について

Export

Report a problem