CCM をつかった単純な問題解決の例

はじめに

CCM は， 記号処理を，局所的な情報だけをつかってランダムさをふくんだやりかたで 実行するための モデルです．CCM のプログラムはプロダクション規則 (下記のような例題では 通常 1 個だけ) と局所評価関数とで構成されて，どちらも局所的な (少数の) データから計算されます．CCM は 遺伝的アルゴリズムににている点もあります．ここでは Java をつかって，いくつかの例題をしめします．

このページにも，ここからリンクされたページにも専門的な解説をくわえています が，それに興味がなければ，下記の例題 ( が ついたリンク) だけをためしてみてください．(ただし，ここでつかって いる解法がこれらの問題をとくためにつかわれる標準的な方法ではないことに 注意してください.)

Java による例題

CCM が得意としているのは 制約充足問題 です．3 つ (+ 1) の制約充足問題を例としてしめします．

N クイーン問題とならべかえ

N クイーン問題の解と N 個のデータのならべかえ (ソート) とは，おなじ規則を つかって，局所評価関数だけをかえることによって計算できます．このページは これらの問題をとくアプレットをふくみます．

地図と グラフ頂点のぬりわけ

例題として米国本土の地図を 4 色でぬりわけます．

魔方陣

魔方陣の解をもとめます．

私は CCM にもとづく計算言語 SOOC を Lisp 上に開発しました．SOOC をつかえば 「はじめに」に書いたようにプログラムを プロダクション規則と局所評価関数とのくみあわせとしてかんたんに記述する ことができます．しかし，SOOC は Java には移植されていないので， 上記のプログラムは Java のプログラムに ``ハンド・コンパイル'' されています．

上記のページからリンクされた Java アプレットは，Windows 95 上の Netscape Navigator 3.0 と Internet Explorer 3.0 などで動作を確認しています が，Macintosh 上ではかならずしもただしく動作しないことがわかっています． うまく動作しないときは，どうももうしわけありません (_o_)

参考文献など

CCM について，くわしくは CCM についての リンク集がここにあります．そこからもたどることができますが，文献リストに は時間の 逆順にならべたものと 問題のタイプによって分類したものとがあります．また， 他の 研究の論文までふくめたリストもあります．いずれか，よみやすいものを 選択してください．

上記のリストにふくまれる論文のおおくは，インターネットからはポスト スクリプトでだけ見ることができますが，つぎのものは HTML によってかかれて いるので，Web ブラウザで直接みることができます．

• Kanada, Y., and Hirokawa, M.: Stochastic Problem Solving by Local Computation based on Self-organization Paradigm, 27th Hawaii International Conference on System Sciences (HICSS-27), 82-91, 1994.
• 金田　泰 : コンピュータによる自己組織系のモデルをめざして, 第 33 回プログラミング・シンポジウム報告集, 1992.1
• 金田　泰 : 自己組織系としての計算システム -- ソフトウェア研究への 2 つの 提案 --, 夏のプログラミング・シンポジウム報告集, 1992.7

CCM は著者が現在も所属している 日立製作所 中央研究所において 考案し，新情報処理開発機構 つくば研究センタ において研究を つづけたモデルです．ただし，上記のアプレットは仕事としてつくったものでは ないので，その著作権は著者個人に属します．アプレットのコピー，改造などは 商用でなければまったく自由にできます．

このページはこれらのメッセージをつかって 検索エンジンやディレクトリ・サービスで宣伝しました．