« Combinatorial Problem Solving Using Randomized Dynamic Tunneling on A Production System | メイン | Constraint Satisfaction Using Neural Networks with a Local and Autonomous Annealing Technique »

Combinatorial Problem Solving Using Randomized Dynamic Composition of Production Rules

Kanada, Y., 1995 Int'l Conference on Evolutionary Computation (ICEC '95), pp. 467-472, (C) Copyright 1995 by IEEE.

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

要旨 (英語のみ) : The present paper proposes a method of solving combinatorial problems using randomized dynamic rule composition. This method is called CCM* and is based on a computational model called Chemical Casting Model (CCM), which is a rule-based computational model for emergent computation. CCM was proposed by the author toward solving dynamic, open and incompletely specified problems using a few simple rules and evaluation functions. By composing a rule from a given production rule dynamically and randomly, CCM* makes it possible to escape from local maxima, which cannot be escaped from by applying the original rule. This method is compared with the original CCM and another extended version of CCM, i.e., CCM with simulated annealing. 0-1 integer programming problems are solved using these methods. Our experiments show that CCM* performs much better than both the original and annealed CCM. In addi-tion, suboptimal solutions can be found in less time than a branch-and-bound method.

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

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

コメントを投稿

About

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

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

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