« Constraint Satisfaction Using Neural Networks with a Local and Autonomous Annealing Technique | メイン | Methods of Parallel Processing of Constraint Satisfaction Using CCM -- A Model for Emergent Computation »

Constraint Satisfaction by Parallel Optimization of Local Evaluation Functions with Annealing

Kanada, Y., 未出版, 1996.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト ファイル ]

[ Java による各種の制約充足問題のデモ (それぞれ触媒,規則,フラストレーションをかえてためせます) ]

要旨 (英語のみ): A method for solving large-scale constraint satisfaction problems is proposed in the present paper. This method is stochastic (or randomized) and uses local information only, i.e., no global plan is expressed in the program and the computation refer to no global information. This method uses CCM (Chemical Casting Model) as a basis, which is a model for emergent computation proposed by the author. The original CCM-based method minimizes the number of constraint violations not directly but throught optimization of local functions, which are called LODs (local order degrees). This method sometimes falls into a "local maximum." This difficulty is solved by a type of annealing, which we call the frustration accumulation method (FAM). FAM also works only with local information. No global functions is used in FAM, No global parameters such as temperature are used, and global control is thus unnecessary. Experiments show that the performance of this method is not very sensitive to parameter values. This means that parameter tuning is easy. In several problems, the performance is comparable to conventional simulated annealing or GSAT, which are based on global evaluation functions. Because of the nonexistence of global information reference, CCM with FAM can be parallelized very easily. Thus, the performance is improved and is almost linear in certain cases.

研究テーマ紹介: CCM: 化学的計算のモデル

キーワード: CCM, 制約充足問題, ランダム化計算, ランダム化問題解決, ランダマイズド計算, ランダマイズド問題解決, アニーリング, 規則ベース計算, 規則ベース問題解決, ルールベース計算, ルールベース問題解決, 関数最適化, 局所情報, 局所的計算, 局所評価関数, FAM, フラストレーション蓄積法



1996-01-01 00:00に投稿されたエントリーのページです。


(C) 2008 by Yasusi Kanada
Powered by
Movable Type 3.36