Methods of Parallel Processing of Constraint Satisfaction Using CCM -- A Model for Emergent Computation
Kanada, Y., SIG PPAI, Japan Society for Artificial Intelligence, Feb, 1996, Published by JSAI.
[ English page ]
[ 論文 PDF ファイル ] [ 論文ポストスクリプト・ファイル]
[ 論文 DVI ファイル (図をのぞく)] [ EPSF 形式の図 : 1, 2, 3, 4, 5, 6, 7, 8 ]
要旨 (英語のみ) : Two methods for solving large-scale constraint satisfaction problems using parallel processing are surveyed in the present paper. These methods are based on CCM, which is a model for emergent computation. The number of constraint violations is minimized in these methods. The minimization is performed by optimization of local functions. The computation is stochastic and no global information is used. An annealing method called FAM has been introduced to avoid ``local maxima.'' FAM also works only with local information. Two types of parallel processing of CCM-based constraint satisfaction using FAM has been tested. One is a parallel search and the other is a cooperative search. Our experiments has shown that both methods improve performance almost linearly in large-scale graph coloring problems when the number of processors is ten or so.
研究テーマ紹介: CCM: 化学的計算のモデル