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

はじめに

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

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

Java による例題

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

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

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

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

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

魔方陣

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

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

Java から JavaScript へのかきかえ

上記のプログラムははじめは Java のアプレットとして書いていましたが，2016 年ごろに Java アプレットが廃止されて，動作しなくなりました．最初は人手で JavaScript にかきかえようとしましたが，容易ではありませんでした．

ChatGPT でプログラミングができるようになってから，そのちからを借りて JavaScript にかきかえようとしましたが，なかなかおもうようにいきませんでした．ChatGPT 4o にも変換するにはいくつかのステップをふむ必要があるといわれて，放置していました．ところが，ChatGPT 5 がつかえるようになってすぐにためしてみると，一発でただしく動作する JavaScript プログラムに変換できました．そこで，これらのプログラムと Web ページを数時間でかきかえることができました．

それでも，JavaScript のやっかいさにはかなりなやまされました．2 つの JavaScript の canvas をひとつのページで表示させようとすると変数のスコープがかさなってうまく表示できず，特殊な方法を ChatGPT におしえてもらう必要がありました．最初からそういうつかいかたをすることを ChatGPT につたえておけばよかったのかもしれません．

参考文献など

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

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