« 局所情報によるアニーリングをつかった大規模制約充足とその並列処理 -- 創発的計算のためのモデル CCM の応用 -- | メイン | Combinatorial Problem Solving Using Randomized Dynamic Composition of Production Rules »

Combinatorial Problem Solving Using Randomized Dynamic Tunneling on A Production System

Kanada, Y., IEEE Systems, Man and Cybernetics '95, (C) Copyright 1995 by IEEE.

[ English page ]
[ 論文 PDF ファイル] [ 論文 ポストスクリプト・ファイル]
[ IEEExplore 論文ページ ]

要旨 (英語のみ) : Levy and Montalvo, Yao, and Shima individually pro-posed tunneling algorithms. The tunneling algorithms employ analogy to tunnel effect in physics, and are used to optimize continuous systems. The present paper proposes a method of solving combinatorial problems using a type of randomized dynamic tunneling technique. This method is based on a computational model called CCM*. CCM* is an extended version of the Chemical Casting Model (CCM). CCM was proposed by the author toward developing a method of solving open and incompletely-specified problems that may change while being solved, using self-organizing computation.

The 0-1 integer programming problem is solved using CCM* with a very simple rule and an evaluation function. CCM* allows us to escape from local maxima by composing the rule dynamically and randomly. This cannot be done by using the original production rule as is. Our experiments show that approximate solutions can be found more rapidly by CCM* than by using a branch-and-bound method in the case of 0-1 integer programming.

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

キーワード: CCM, くみあわせ最適化, 組合せ最適化, 組み合わせ最適化, 整数計画, ランダム化計算, ランダム化問題解決, ランダマイズド計算, ランダマイズド問題解決, 規則ベース計算, 規則ベース問題解決, ルールベース計算, ルールベース問題解決, トンネル効果, トンネリング

コメントを投稿

About

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

他にも多くのエントリーがあります。メインページアーカイブページも見てください。

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