金田の論文

金田　泰, 第 33 回プログラミング・シンポジウム報告集, 1992.1, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ハイパー テキスト版]
[ 論文 ポストスクリプト・ファイル: Part 1, Part 2 (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル ] [ OHP PDF ファイル ]

[ Java による N クイーン問題とソートのデモ ]

要旨: パタン情報処理のよさをとりいれた自己組織的な記号情報処理のための計算モデルで ある化学的プログラミング・モデル (CPM) を提案する． CPM は，局所的に計算される 秩序度関数の値が増加するように動作するプロダクション・システムである． CPM に もとづく言語処理系を作成してかんたんな実験をおこなった． その結果，N クウィー ン問題などのくみあわせ問題の柔軟なプログラムが非常に簡潔に記述でき，非常に効 率的に実行できることがわかった． CPM を発展させれば，人間がもつ不完全性や非合 理性までをもとりこみつつ，分割統治法がうまく適用できない全体性や開放性をもつ 問題をもあつかえるような自己組織系をコンピュータのうえに実現し，それを数理解 析するための一歩となるとかんがえられる．

[注: ここで CPM = CCM です.]

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

金田　泰, 夏のプログラミング・シンポジウム報告集, 1992.7 (原稿は 1992.11), IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ハイパー テキスト版 ]
[ 論文 ポストスクリプト・ファイル: Part 1, Part 2 (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル ]

要旨: ソフトウェアを開発するのは不完全な人間であり，また今日では人間社会と密に結合 された大規模・複雑な開放系が開発されていることをかんがえると，閉じた "完全な 計画" を要求する従来のソフトウェア開発法や理論にかわる自己組織的な計算システ ムの開発法や理論を構築することが必要である． そこで，この報告では 「プログラム なしの計算をめざそう」，「計算システムを自己組織系としてみよう」 というソフト ウェア研究への 2 つの提案をする． これらの提案の実現に必要なミクロ・モデルと マクロ・モデルについて説明し，前報でしめした計算モデル CCM を前者の例として 位置づけ，後者の例として計算を確率過程としてみるマルコフ連鎖モデルをしめす．

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

金田 泰, 第 11 回計測自動制御学会システム工学部会研究会, pp. 27-34, 1993, SICE により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル: Part 1, Part 2 (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ]
[ OHP PDF ファイル: スライド, ハンドアウト ]

要旨: 著者は自己組織的計算のための 「化学的キャスティング・モデル (CCM)」とそれにも とづく計算言語 SOOC を提案している． このモデルは仕様も明確にかきくだせない開 放系の問題への適用を本来の目的として開発した． しかしこれを仕様が明確な最適化 問題に適用しても，巡回セールスマン問題などの単純な最適化問題のばあい，唯一の プロダクション規則と唯一の評価関数 (局所秩序度という) をあたえるだけで，局所 的な情報の参照だけにもとづいて問題がとけるという利点がある． この報告では CCM にもとづく最適化の例として巡回セールスマン問題をとりあげ，解法と実験結果とを しめす． また，この方法による計算過程におけるマクロなふるまいを理解するため， マルコフ連鎖にもとづくモデルにあてはめた結果をしめす．

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

金田 泰, 廣川 真男, 情報処理学会記号処理研究会, 93-SYM-68-2, pp. 9-16, 1993, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ]
[ OHP PDF ファイル: スライド, ハンドアウト ]

[ Java による N クイーン問題のデモ ]

要旨: この報告では，CCM にもとづいてある種の制約充足問題をとく方法をしめす． この方 法では決定的かつ手続き的な制約伝搬にはよらずに確率的な手法によって，また非常 に単純な"プログラム" によって N クウィーン問題や地図の彩色問題などの制約充足 問題を平均すると多項式時間でとくことができる． この報告ではまた，この方法によ る計算の特性すなわち実行時間やその分布などを実測値にもとづいて論じる．

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

金田　泰, 電子情報通信学会コンピューテーション研究会 / ソフトウェアサイエンス研究会, COMP92-93, SS92-40, pp. 1-10, 1993, IEICE により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ]
[ OHP PDF ファイル: スライド, ハンドアウト ]

要旨: 複雑な記号処理をおこなう計算システムは，プログラムを静的に理解することによっ て，あるいはミクロな動作を追っていくことによってそのふるまいを理解することは できない． したがって，それを理解するには計算過程をマクロにみるモデルが必要で ある． 計算過程のマクロ・モデルはまた，計算の自動制御や自己組織的計算の実現の ためにも必要だとかんがえられる． この報告では計算過程のマクロな理論に関する基 礎検討をおこない，確率過程論にもとづくモデル化を提案する． そして，そのひとつ の例として，ミクロ・モデルとしての 化学的キャスティング・モデル (CCM) に対応するマクロ・モデルとしてマルコフ連鎖モデルをしめし，それにもとづいて CCM にもとづくエイト・クウィーン問題の計算過程を分析する． この理論はミクロ・モデル における記号計算とマクロ・モデルにおけるパタン計算との一種の融合をはかってい るということができる．

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

金田 泰, 長期研究会 「複雑系 2」 発表報告 (A4, 1 枚), 物性研究, 1994.2.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル (印刷低速 !) ]
[ ポスター ポストスクリプト・ファイル : ポスター, ハンドアウト ]
[ ポスター PDF ファイル: ポスター, ハンドアウト ]

要旨: この研究はコンピュータ上で自己組織的計算，すなわち局所的・部分的 (不完全) な 情報だけをあたえて，のぞみの大域的な構造をつくりあげる，創発的 (emergent) な 情報処理法の実現をめざしている． CCM にもとづいて，局所的な情報から彩色問題な どの問題解決ができる． CCM にもとづく制約充足問題をとくシステムは，大域秩序度 の時間変化，触媒の作用などにおいて興味ぶかい動特性をしめすことがわかった．

発表は 1993 年 8 月．

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

金田 泰, SWoPP '93 (情報処理学会人工知能研究会), 93-AI-89-2, pp. 11-20, 1993, IPSJ により出版.

[ English page ]
[ 論文 3 訂版 PDF ファイル ] [ 論文 3 訂版 ポストスクリプト・ファイル (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ]
[ OHP PDF ファイル: スライド, ハンドアウト ]

[ Java による彩色のデモ ]

要旨: 制約充足や最適化などの問題解決は解の探索としてとらえられる． 人工知能やオペ レーションズ・リサーチなどにおける従来の解探索法においては，バックトラックを つかって木構造の探索空間を網羅的・系統的に探索することが基本となっている． 著 者は分散・並列的に作用するプロダクション規則と局所評価関数にもとづく計算モデル CCM (化学的キャスティング・モデル) を提案しているが，CCM による解探索は， 評価関数によってバイアスをかけながら探索空間上を酔歩 (random walk) すること だとみなせる． この方法の特徴は，木ではなく強連結なグラフ上を探索すること，可 逆で対称性がある規則を使用すること，規則がふくむ触媒なるものを加減したり規則 を合成したりすることによってバイアスのつよさや規則の局所度がかえられることな どである．

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

金田 泰, 情報処理学会第 47 回全国大会, pp. 1-99-100, 1993.10, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル: Part 1, Part 2 (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ]
[ OHP PDF ファイル: スライド, ハンドアウト ]

要旨: 報告者は局所的部分的な情報にもとづく自己組織的な計算をめざして， 化学的キャスティング・モデル (CCM) という計算モデルを提案している． CCM は化学反応系 とのアナロジーをつかい，プロダクション・システムにもとづく計算モデルであ る．CCM の特徴は，適用対象データに関する局所的な評価関数によってプロダク ション規則の適用が制御される，非決定的あるいは確率的に動作する，手続き的な 解法よりはるかに単純なプログラムで問題がとけるなどである． これまでに N ク ウィーン問題，彩色問題，巡回セールスマン問題などへの CCM の適用を試行した が，ここではそれを拡張して 0-1 整数計画問題に適用した結果を報告する．

P.S. より具体的にいうと，ここでおこなった CCM の拡張とは，シミュレーテッ ド・アニーリングとプロダクション規則の合成 (いずれも局所最大点におちいるの をふせぐための方法) である．

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

金田 泰, 情報処理学会記号処理研究会, 93-SYM-71-5, pp. 33-40, 1993, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ]
[ OHP PDF ファイル: スライド, ハンドアウト ]

[ Java によるソートと N クイーン問題のデモ (ソートは 1 種類だけ)]

要旨: 著者は，局所情報だけで計算されるプロダクション規則と評価関数とを要素とする確 率的な計算モデル 「化学的キャスティング・モデル (CCM)」 とそれにもとづく計算言語 SOOC を提案している． このモデルは仕様も明確にかきくだせない開放系の問題に 適用するために開発したものだが，古典的な問題への適用実験も重要だとかんがえて いる． そこでこの報告では CCM をソートに適用し，あたらしいソート法をしめすと ともに，従来の挿入ソート，交換ソートなどにもとづくソート法をしめす． また，あ わせてそれらの実験結果をしめす． この方法では，唯一のプロダクション規則と唯一 の評価関数をあたえるだけで，局所情報の参照だけにもとづいてソートをおこなうこ とができる． また，局所情報だけをつかうことによって生じる興味ぶかい現象につい ても言及する．

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

Kanada, Y., and Hirokawa, M., 27th Hawaii International Conference on System Sciences (HICSS-27), pp. 82-91, 1994.

[ English page ]
[ 論文 PDF ファイル, (C) Copyright by IEEE ]
[ 論文 ハイパーテキスト版 (図は現在利用できません) ]
[ 論文 ポストスクリプト・ファイル, (C) Copyright by IEEE ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ] [ OHP PDF ファイル: スライド, ハンドアウト ]
[ IEEExplore 論文ページ ]

[ Java による N クイーン問題とソートのデモ ]

要旨: We are developing a new problem-solving methodology based on a self-organization paradigm. To realize our future goal of self-organizing computational systems, we have to study computation based on local information and its emergent behavior, which are considered essential in self-organizing systems. This paper presents a stochastic (or nondeterministic) problem solving method using local operations and local evaluation functions. Several constraint satisfaction problems are solved and approximate solutions of several optimization problem are found by this method in polynomial order time in average.

Major features of this method are as follows. Problems can be solved using one or a few simple production rules and evaluation functions, both of which work locally, i.e., on a small number of objects. Local maxima of the sum of evaluation function values can sometimes be avoided. Limit cycles of execution can also be avoided. There are two methods for changing the locality of rules. The efficiency of searches and the possibility of falling into local maxima can be controlled by changing the locality.

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

金田 泰, 人工知能学会並列人工知能研究会, SIG-PPAI-9401, pp. 7-12, 1994, JSAI により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル: Part 1, Part 2 (印刷低速 !) ]
[ ポスター ポストスクリプト・ファイル: Part 1, Part 2 ]
[ ポスター PDF ファイル : Part 1, Part 2 ]

[ Java による彩色のデモ (静的な彩色) ]

要旨 : 実世界の計算システムは刻々と変化する環境に対してひらかれた複雑なシステムであり，従来 のソフトウェア開発法では根本的に対処できないとかんがえられる． CCM (Chemical Casting Model) は，創発的計算にもとづくソフトウェア開発法の確立をめざして開発した，局所情報に もとづく非決定的 (ランダム) な計算のモデルである． CCM は局所的に計算される評価関数を ともなうプロダクション・システムである． この報告では，CCM にもとづく計算言語 SOOC による動的に変化するグラフ頂点の彩色 (移動放送局への電波のわりあて) の方法と実験結果と をしめす． SOOC によれば，静的なグラフ彩色とおなじプロダクション規則と評価関数とをつ かうだけで，動的な彩色をおこなうことができ，基本的におなじ方法と道具とをつかって結果 を評価できる．

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

金田 泰, 計測自動制御学会第 14 回システム工学分科会研究会 "組合せ問題とスケジューリング問題の新解法," 45-52, 1994, SICE により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル: Part 1, Part 2 (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル : なし (変換失敗!)]

要旨 : トンネリング・アルゴリズムという連続系のための最適化法を Levy and Montalvo，Yao，島ら が提案しているが，この報告では，くみあわせ問題をとくための，一種のトンネリングをとり いれた方法をしめす． この方法は，問題解決の途中で問題じたいが変化するような動的な問題 の自己組織的な解決をめざして著者が提案している CCM* (拡張された 化学的キャスティング・モデル) という計算モデルにもとづいている． ここではグラフ彩色問題と 0-1 整数計画問題と を例題として，この方法を説明する． CCM* はプロダクション・システムの一種であるが，こ の方法をつかえば，あたえられたプロダクション規則をそのまま適用してもぬけだせない局所 最大点を，そのプロダクション規則を動的かつランダムに合成することによって，ぬけだすこ とができる．

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

Kanada, Y., Artificial Life IV, Poster, 1994.

[ English page ]
[ 論文 PDF ファイル ] [ ポスター ハイパーテキスト版 ]
[ 未出版 拡大版論文 PDF ファイル]

要旨 (英語のみ): Cellular automata are used as models of emergent computation and artificial life. They are usually simulated under synchronous and deterministic conditions. Thus, they are evolved without existence of noise, i.e., fluctuation or randomness. However, noise is unavoidable in real world. The objective of the present paper is to show the following two effects and several other effects caused by asynchronism or synchronism and by existence or nonexistence of randomness in the computation order in one-dimensional asynchronous cellular automata (1D-ACA) experimentally. One major effect is that certain properties of two-neighbor 1D-ACA are fully expressed in their patterns if certain level of randomness exists, though they are only partially expressed if no randomness exists. The patterns generated by 1D-ACA may have characteristics, such as mortality of domains of 1's or splitting domains of 0Us into two. These characteristics, which are coded in the RchromosomeS of the automata, i.e., the look-up table, are fully expressed only when the computation order is random. The other major effect is that phantom phenomena, which almost never occurs in real world, sometimes occur when there is no noise. The characteristics of patterns generated by several 1D-ACA are drastically changed from uniform patterns to patterns with multiple or chaotic phases when only low level of noise is added.

参考文献: "非同期セル・オートマトン". Wiki Pedia, この論文のオリジナルな点がかんたんに説明されています.

研究テーマ紹介: RACA: ランダムな非同期セル・オートマトン

金田 泰, SWoPP '94 (情報処理学会人工知能研究会), 94-AI-95-4, pp. 29-38, 1994, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル] [ 論文 ポストスクリプト・ファイル (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ] [ OHP PDF ファイル: スライド, ハンドアウト ]

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

要旨 : CCM (Chemical Casting Model) は，たえず変化する環境に対してひらかれた創発的計算にもと づく問題解決法の確立をめざして開発した，非決定的 (ランダム) に動作する計算のモデルで ある． CCM においては局所的な情報をつかって計算がおこなうが，局所的な極限においては 解をもとめることはできない． したがって，計算，とくに評価関数の計算の局所性を制御し て，局所最適点におちいらないように探索空間内での局所性を制御する必要がある． この報 告では 4 つの局所性の制御法をしめす． それらは，触媒の加減，反応規則の合成またはトン ネリング，シミュレーテッド・アニーリング (SA)，フラストレーション蓄積法 (FAM) であ る． これらを比較した結果，制約充足のばあいは触媒の加減と FAM が有効だが，これらだ けでは従来法に計算時間のうえでおとるばあいがあることがわかった． また最適化のばあい はトンネリングすなわち反応規則の動的な合成が有効だとわかった．

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

金田 泰, 情報処理学会記号処理研究会, 94-SYM-75-5, pp. 31-38, 1994, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ]
[ OHP PDF ファイル: スライド, ハンドアウト ]

[ Java による魔方陣のデモ (SOOC とは無関係です) ]

要旨: たえず変化する環境に対してひらかれた創発的計算にもとづく問題解決法の確立をめざして， 著者は CCM という計算モデルを提案している． CCM は局所的な情報だけで計算される評価 関数をともなう，ランダムに動作する一種のプロダクション・システムである． その実験を おこなうために計算言語 SOOC-94 とその処理系を開発し使用している． ここでは SOOC-94 の特徴と逐次計算機の Lisp 上の実装について，魔方陣の問題を例として説明する． この言語 の特徴としては，規則適用時に評価関数の自動計算や局所的な自動バックトラックをするこ と，規則の両辺におけるパタンの構文がほぼ統一されていること，規則の適用順序に関する 2 種類のスケジューリング戦略とくにランダム戦略の存在，データ (構造体) の要素と して複数の同名の要素の存在をゆるしていることなどがある．

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

Kanada, Y., 未出版, 1994.

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

要旨 (英語のみ): Today's computer applications often require on-line input and output and sometimes requires change of computation methods while processing complex tasks. In future, they will probably be required to change even the objectives of computation. Such a new style of information processing is called real-world computing in the present paper. Real-world computing requires computation languages to work without fixed sequence of control nor fixed data flow, to work without a whole plan of computation, to be always open to environment at any time, to have possibility of distributed and parallel processing, to have possibility to respond to nondeterministic actions, and so on. Because today's programming languages are considered not to satisfy these requirements, a new computation model called CCM (chemical casting model) and a language called SOOC-94, which partially satisfies the requirements, are developed as the first step. Computation is regarded as biased random walk in CCM. The random walk is realized by a randomly acting forward-chaining production system, and the bias is realized by locally computed evaluation functions in SOOC-94. I have developed a preliminary version of compiler and interpreter, and analyzed the computation processes and results of graph coloring problems for example.

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

金田 泰, 情報処理学会 第 49 回全国大会, pp. 4-321 - 322, 1994, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル: Part 1, Part 2 (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ] [ OHP PDF ファイル: スライド, ハンドアウト ]

要旨: CCM (Chemical Casting Model) は，創発的計算にもとづく問題解決法の確立を めざして開発した，非決定的 (ランダム) な計算のモデルである． この研究で は，局所的・部分的な情報だけをつかった，たえず変化する環境のもとでのひ らかれた計算をめざしている． この報告では， CCM にもとづく制約充足問題な どのひとつの並列処理法についてのべる． CCM にもとづく計算においては計算 時間がほぼ指数分布にしたがうばあいがあり，そのときは独立な並列処理に よってプロセッサ台数にほぼ比例する性能向上が期待できることがわかった．

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

金田 泰, 日本神経回路学会第 5 回全国大会, pp. 36-39, 1994, JNNS により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル: Part 1, Part 2 (印刷低速 !) ]
[ OHP PDF ファイル: スライド, ハンドアウト ] [ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ]

要旨 (英語のみ) : The basics of CCM (chemical casting model), which is a computation model for emergent computation, is explained, and an extension of CCM, i.e., dynamical composition of rules, is described. The relation between the extended CCM and neural networks, especially the neural networks with linked state transition, is mentioned, and the importance of designing good concrete dynamics is also mentioned.

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

Kanada, Y., 未出版, 1995.

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

要旨 (英語のみ): A method of solving combinatorial problems, such as the N queens problem or graph coloring problems using independent parallel processes, is proposed in the present paper. This method is stochastic (or randomized). Problems are decomposed for parallel processing implicitly and stochastically by this method. This method is based on CCM, which is a computational model proposed by the author. A program consists of production rules and local evaluation functions in CCM. Each process uses the same set of rules and functions, and it may use the same set of initial data in this method. However, the performance is approximately in proportion to the number of processors in average in certain cases. The theoretical reason of this linear acceleration is explained, and several results of experiments, some of which was successful but others were not, are also shown.

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

Kanada, K., Fuzz-IEEE/IFES '95, pp. 2319-2326, 1995.

[ English version ]
[ 論文 PDF ファイル． (C) Copyright 1995 by IEEE]
[ 論文 ポストスクリプト・ファイル． (C) Copyright 1995 by IEEE]
[ IEEExplore 論文ページ ]

要旨 (英語のみ) : A method of solving fuzzy constraint satisfaction problems defined by Ruttkay is shown in the present paper. This method is based on CCM, which is a computation model for emergent computation or for locality-based problem solving. CCM is a type of production system. It works stochastically, or randomly, and works with evaluation functions that are computed only with local information. CCM has been applied to constraint satisfaction problems (CSPs). Binary-valued evaluation functions, each of which indicates whether a constraint is satisfied, are used. If the values of evaluation functions are extended to real values, fuzzy CSPs can be expressed in CCM, and solved using a technique similar to GSAT or annealing. This method is applied to a fuzzy graph coloring problem, and the performance is evaluated. This method can also be applied to an open and dynamical fuzzy/non-fuzzy CSPs, in which data and constraints are changing dynamically or coming from or going to the outside of the system.

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

金田 泰, SWoPP '95 (情報処理学会人工知能研究会), AI95-16, 17-24, 1995, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル: なし (変換失敗 !) ] [ 論文 ポストスクリプト・ファイル]

要旨 (英語のみ) : この報告では，創発的計算のためのモデル CCM (化学的キャスティング・モデル) にもとづいて大規模な制約充足問題をとくための方法を提案する． また，その並 列処理の方法をしめす． CCM にもとづく方法ではこれまで大規模な問題をとくこ とができなかったが，FAM (フラストレーション蓄積法) という一種のアニーリン グを導入し，さらにパラメタをうまく調整することによって，大規模なグラフ彩 色問題を GSAT や シミュレーテッド・アニーリングと同程度の計算時間で逐次処理で とくことができるようになった． さらに，かぎられた量の相互排斥だけをつ かって，比較的容易に並列処理できることがわかった． ある条件のもとではほぼ プロセッサ数に比例する性能がえられた．

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

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: 化学的計算のモデル

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: 化学的計算のモデル

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: 化学的計算のモデル

Kanada, Y., 未出版, 1996.

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

要旨 (英語のみ): A method for solving large-scale constraint satisfaction problems using an annealed symmetrically-connected neural network, which is called DSN-FAM, is proposed in the present paper. Some conventional methods, such as Hopfield networks, often fail to find a solution. Some others, such as Boltzmann Machines, take too much time. These difficulties are solved by a type of annealing technique, which we call the frustration accumulation method (FAM). DSN-FAM works only with local information, and no global functions or global parameters such as a temperature are used. DSN-FAM thus works autonomously. That is, no external control is necessary while operating. Experiments show that this method does not fail to find a solution and the execution time is less than one tenth of Boltzmann Machines. The performance can be easily and almost linearly improved by parallel processing using tens of processors.

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

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: 化学的計算のモデル

Kanada, Y., 19th International Symposium on Artificial Life and Robotics (AROB 2014), 2014-1.
[ English page ]
[ 論文 (発表後改訂) ]
[ スライド ]
[ 印刷のようす (YouTube) ]

要旨: 3D printing technology usually aims reproducing objects deterministically designed by 3D CAD tools. However, 3D printing can generate patterns similar to randomized (non-deterministic) 1D or 2D cellular automata (CA). Cheap fused deposition modeling (FDM) 3D printers can be used for this purpose. By using an FDM 3D printer, melted plastic filament is extruded by a hot nozzle to shape a 3D object. They can generate CA-like patterns with constant head motion and constant filament extrusion and with unintended fluctuation but no explicit randomness. Because of fluctuation, every time the printer generates a different emergent pattern. This paper proposes a method for printing seaweed-like patterns of 1D and 2D CA using FDM, and computational CA models. This method will open a new horizon of 3D printing applications.

研究テーマ紹介: 3D 造形技術

Kanada, Y., 8th International Workshop on Natural Computing (IWNC8), 2014-3.
[ English page ]
[ 本 ]
[ スライド ]
[ 印刷のようす (YouTube) ]

Abstract: Fused deposition modeling (FDM) is a 3D-printing method that shapes 3D objects by layering melted plastic filament. The process of this type of 3D printing can be regarded as asynchronous cellular-automata because it generates 1D on-off pattern per a head motion. Especially, by a constant head-motion at reduced constant extrusion-velocity, a 3D printer can generate self-organized grids or similar structures, which is much finer than artificial (i.e., program-controlled) patterns. Depending on the parameter values, i.e., layer depth, extrusion velocity, and so on, the generated pattern varies among regular stripes, stripes with crossing waves, and splitting and merging patterns. Some of the patterns can be simulated by a computational model, i.e., asynchronous cellular automata.

研究テーマ紹介: 3D 造形技術

Kanada, Y., 20th International Workshop on Cellular Automata and Discrete Complex Systems (Automata 2014), July 2014.
[ English page ]
[ 論文 PDF ファイル ]
[ 論文 PDF ファイル (拡張版, IWNC8 用原稿) ]
[ スライド (減量版) ]
[ スライド (動画つき, Keynote) ]

Abstract: 3D printers are usually used for printing objects designed
by 3D CAD exactly, i.e., deterministically. However, 3D printing process
contains stochastic self-organization process that generate emergent
patterns. A method for generating fully self-organized patterns using a
fused deposition modeling (FDM) 3D printer has been developed. Melted
plastic filament is extruded constantly in this method; however, by using
this method, various patterns, such as stripes, splitting and/or merging
patterns, and meshes can be generated. A cellular-automata-based
computational model that can simulate such patterns have also been
developed.

研究テーマ紹介:
3D 造形技術