系統的/局所的探索の協調によるファジィ制約充足問題の近似解法

概要

論文の詳細を見る
A fuzzy constraint satisfaction problem (FCSP) is an extension of the classical CSP, a powerfultool for modeling various problems based on constraints among variables. Basically, the algorithms forsolving CSPs are classified into two categories: the systematic search (complete methods based on searchtrees) and the local search (approximate methods based on iterative improvement). Both have merits anddemerits. Recently, much attention has been paid to hybrid methods for integrating both merits to solveCSPs efficiently, but no such attempt has been made so far for solving FCSPs.In this paper, we present a hybrid, approximate method for solving FCSPs. The method, calledthe 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 degreeof the worst constraints (which are the roots of the trees) is improved. We empirically show that SRSoutperforms the SR algorithm as well as the well-known methods such as Forward Checking and FuzzyGENET, when the size of the problems is sufficiently large.
人工知能学会の論文
2006-11-01