図 3 化学的キャスティング・モデルの構成要素
この章では，前章でしめした 2 つの提案を具体化するために必要なミクロ・モデルとして， 化学的キャスティング・モデル (chemical casting model, CCM) について説明する．このモデ ルは金田 [Kan 92] で提案した化学的プログラミング・モデルを改名したものだが [*1]，ここ では，[Kan 92] において明確に説明しなかったことに重点をおいて説明する．ミクロ・モ デルとしてはもっとべつのものもかんがえられるが，現在のところこのモデルがもっとも 上記の提案で要請されているものにちかいとかんがえられる．
CCM は化学反応系とのアナロジにもとづく計算モデルである．どのようなアナロジにも とづいているかは，以下の説明でもわかるだろうが，くわしくは金田 [Kan 92] を参照さ れたい．CCM は不完全な (非決定的な) 計画にもとづく計算のためのミクロ・モデルであ り，前章でのべた自己組織系のモデルにももとづいている．
CCM の構成要素についてかんたんに説明する．CCM は chemical abstract machine [Ber 90] と同様にプロダクション・システムにもとづくモデルである．プロダクション・システム における作業記憶は CCM においても作業記憶とよぶ．すなわち，CCM が作用するデー タは作業記憶にふくまれる．そして，プロダクション・システムにおける規則ベースすな わちプログラムに相当するものをキャスタ [*3] とよぶ．CCM は不完全な計画にもとづく計算 のためのモデルなので，完全な計画を意味するプログラムということばのかわりに，キャ スタということばを使用する．キャスタの自己組織化すなわち自律的なかきかえというの も興味ある問題だが，いまのところはキャスタはユーザによって記述され，そのままのか たちでつかわれるとかんがえる．したがって，当面は自己組織化の対象となるのはデータ だけである．
作業記憶にふくまれるべきオブジェクトあるいはデータとしては，つぎのようなものがあ る (図 3 参照)．原子はデータの単位であり，内部状態をもつ． 原子にはデータ型があり，それを元素ともよぶ． 原子どうしをリンクによって結合することができ，結合された全体 を分子とよぶ．リンクは無向でも有向でもよい．無向のリンクは化学結合に似ているが， 化学結合には有向のリンクに相当するものはない．また，リンクにはラベルをつけること もできる [*4]．分子どうしをリンクのようなもので結合した超分子あるいは超超分子のような 階層構造をかんがえることもできるが，いまはかんがえない [*5]．
キャスタは反応規則と局所秩序度とで構成される． 反応規則はシステムの局所的な (ミクロな) 変化のしかたをきめる規則であり，ユーザにより定義される．ここで「局所的」と いうことばは，その反応規則によって参照される原子数がすくないということを意味する [*6]．反応規則は前向き推論によるプロダクション規則 [*7] として記述される．したがって，つぎのようなかたちをしている．
LHS → RHS.
反応規則は化学反応式に相当するものだといえる．反応規則の例は次節および金田 [Kan 92] にあげた．後述するグラフ彩色問題や [Kan 92] でしめした N クウィーン問題などをはじめとする おおくの単純なシステムにおいては反応規則は 1 個だけ存在するが，複数の変化の しかたをみとめるより複雑なシステムにおいては複数個の反応規則が存在する．
局所秩序度は局所的な ``組織化'' あるいは ``秩序化'' の程度をあらわす量であり [*8]，作業記憶の局所的な状態が ``のぞましい'' ほどおおきな値をとるように，ユーザにより定義される． 局所秩序度の定義のしかたとしては 自己秩序度 と 相互秩序度 とがあるが，これらについては金田 [Kan 92] が説明している．N クウィーン問題のキャスタは相互秩序度 を使用しているが，以下の説明においては，かんたんのため自己秩序度だけをかんがえる． 自己秩序度は元素ごとに定義され，規則の適用時に原子ごとに計算される．ただし，その 値は当該原子の内部状態だけでなく，その原子からでるリンクがつながったさきの原子の 状態にも依存しうる．
反応はつぎの 2 つの条件をみたすときにおこる．反応規則の左辺 LHS および右辺 RHS に は原子とマッチする 1 個または複数個のパタンがあらわれるが，第 1 の条件は左辺にあら われるすべてのパタンのそれぞれにマッチする原子が存在することである．
反応がおこるとこれらの原子は消滅して，そのかわりに右辺にあらわれる原子が生成され る [*9]．ただし，左辺と右辺とに対応する原子があらわれるばあいは，その原子は生成・消滅 するかわりにかきかえられる [*10]．このような規則とそれにあらわれる (左辺および右辺の) パタンにマッチするすべての原子との組を インスタンスとよぶ．ひとつのインスタンスが ふくむ原子のうち，反応前に存在するものすなわち左辺にあらわれるものの局所秩序度の 総和を ``反応前のインスタンス秩序度''，反応後に存在するものすなわち右辺にあらわれ るものの局所秩序度の総和を ``反応後のインスタンス秩序度'' とよぶ．反応後のインスタ ンス秩序度をあらかじめ計算したものが反応前のインスタンス秩序度よりおおきいとき， すなわち反応によって局所秩序度の和が増加する時だけ反応がおこるというのが第 2 の条 件である [*11]．
そして，いずれかのインスタンスについて上記の 2 条件がみたされているかぎり，反応は くりかえしおこる．これらの条件をみたすインスタンスが存在しなくなると実行は中断さ れる [*12]．
ただし，一般には上記の 2 つの条件をみたすインスタンスは複数個存在する．条件をみた すインスタンスが複数個生成される原因としては，ひとつの規則の条件部をみたす原子の 組が複数個存在するばあいと，複数の規則についてその条件部をみたす原子の組が存在す るばあいとがある．いずれのばあいでも，これらのインスタンスのうちのいずれがどのよ うな順序で，あるいは並列に反応するかは非決定的である．いいかえると，反応の順序は システムが自律的にきめる．したがって，反応を完全に制御することはできない．
しかし，これをある程度は制御することができないと，のぞんだ計算を実現できないばあ いがある．そのために， スケジュリング戦略 というものがさだめられる．ユーザはそれを 指定することによってインスタンスの選択順序を制御し，反応の順序を部分的に制御する ことができる．スケジュリング戦略にはインスタンスを系統的に選択する 系統的戦略 [*13] と， ランダムに選択する ランダム戦略 とがある．スケジュリング戦略としてこれ以外のものも かんがえられるが，前記のものもふくめて金田 [Kan 92] がくわしくのべているので，ここでは説明しない [*14] [*15]．
ところで，反応規則も局所秩序度も局所的に (ミクロに) 作用するということをのべた． 局所性は不完全性の一種だとかんがえることができるが，CCM はこのような不完全な `` 計画'' による大域的な組織化をめざす (すなわちマクロな，より完全なものをめざす) 計算 モデルである．
この節では，CCM にもとづくキャスタの例として，グラフ彩色問題のキャスタをとりあ げる [*15a]．まず問題を説明する．グラフ彩色問題は，グラフの頂点をあらかじめきめられた数 の色たとえば 4 色にぬりわけるという問題である．ただし，ここでグラフの隣接頂点が同 色にならないようにぬらなければならない．この問題は，グラフの頂点を地図の領域に対 応させ，グラフの辺を地図の領域境界と対応させることによって地図の彩色問題と対応づ けることができる．すなわち，おなじキャスタで地図の彩色問題をとくことができる．た とえば，図 4 にしめす 5 頂点からなるグラフを彩色する問題は，そのグラフにかさねてえ がいた 5 領域からなる地図の彩色問題と等価である [*16]．
つぎに CCM によってこの問題をとくためのデータ構造について説明する．グラフの頂点 および辺をそれぞれ原子としてあらわす．したがって，ここには定義はしめさないが， vertex および edge という 2 個の元素を定義する．これにより，たとえば図 4 のグラフは図 5 のように表現される．なお，vertex 型の原子は内部状態として色をもつ． 図 5 では C1, C2, C3, C4 が色をあらわしている．
つぎに，グラフ彩色問題をとくためのキャスタをしめす．第 1 に，このキャスタを構成す る唯一の反応規則の定義を視覚言語のかたちで図 6 にしめす [*17]．この反応規則は，隣接する ひとくみの 2 頂点とそれらのあいだの辺をあらわす原子だけを参照して，一方の頂点の色 をランダムにぬりかえる規則である．
この反応規則のより詳細な意味はつぎのとおりである．規則左辺には，原子にマッチする 3 個のパタンがふくまれている．それらのうちの 1 個は edge 型の原子にマッチし，のこ りの 2 個は vertex 型の原子にマッチする．前者には edge，後者には vertex1 および vertex2 というラベルがつけられている．そして，その edge 型の原子から 2 個の vertex 型の原子 への無名のリンクが存在する [*18]．したがって，この規則左辺にマッチすることができるのは， グラフの隣接する 2 頂点をあらわす vertex 型のデータと，それらをむすぶ辺をあらわす edge 型のデータである．反応によって，vertex2 にマッチした原子の内部状態がかきかえ られる．すなわち，反応前にはその内部状態すなわち色は C2 だったが，それがランダム に生成された色 C3 にぬりかえられる．ここで C3 はあらかじめきめられた色のなかから 選択される [*19]．ところで，C1, C2, C3 のあいだにはなんの制約も記述されていないから，そ れらはことなっていてもよいしおなじでもよい．
図 6 グラフ彩色問題のための反応規則の例
この反応規則を ``不完全な計画'' にもとづく計算という観点から分析する．この反応規則 は，グラフが何個の頂点と何個の辺によって構成されていても上記の 3 点だけを参照する という意味において (空間的に) 局所的であり，その意味で ``不完全'' だといえる．また， この反応規則の適用すなわちひとつの反応は問題をとく手順の 1 ステップを構成するが， それをどうつなぎあわせて手順を構成するかは非決定的であるから，この反応規則は手順 を規定してはいない．したがってこの反応規則は時間的に ``局所的'' であり，その意味で も ``不完全'' だといえる．
第 2 に，局所秩序度の定義をしめす．このキャスタには 2 種類の元素がつかわれるが，こ のうち vertex に対しては局所秩序度を定義しない．局所秩序度が定義されていない元素の 原子の局所秩序度は 0 とみなされる．元素 edge の局所秩序度定義はつぎのように定義す る．
この定義は，辺の両端の頂点が同色ならば 0，そうでなければ 1 という意味である．すな わち，元素 edge の局所秩序度は ``のぞましい'' 状態においてよりたかい値をとる．この定 義の x.vertex[1].color および x.vertex[2].color はそれぞれ edge 型のデータ x からでる最初の リンクおよび 2 番めのリンクがさす vertex 型のデータの color という内部状態すなわち色 を意味している．``不完全な計画'' にもとづく計算という観点からみると，この局所秩序 度は当該の辺が接続している両端の頂点をあらわす原子を参照するが，それ以外の原子を 参照しないという点において局所的であり ``不完全'' だといえる．
上記のキャスタを実行させると，局所秩序度がたかい値をとる方向に，つぎつぎに反応が おこる．しかし，ひとつの反応はそれにかかわる辺の周辺の辺の局所秩序度を低下される 可能性がある．したがって，解にむかって直線的に動作するわけではないし，かならず解 に到達するともいえない (この点については次章で再度論じる)．そこで，CCM にもとづ く言語 SOOC-92 (Self-Organization-Oriented Casting または Computing) [*20] とその処理系を使用 して，スケジュリング戦略としてはランダム戦略をつかって，上記のキャスタのふるまい をしらべた．SOOC-92 はテキスト・ベースの言語である．
前記のキャスタはすなおにコーディングしても動作させることができる．しかし，ここで はそれを改良したキャスタを米国本土 48 州の地図の 4 色ぬりわけ [Tak 92] に適用した結果をしめす [*21]．なお，米国本土 48 州の地図を対応するグラフに変換すると 48 頂点，106 辺のグラフになる．
総反応回数，規則左辺のマッチング回数 (不成功におわるばあいもふくむ)，および実行時 間を SUN4 の KCL (Kyoto Common Lisp) 上の SOOC-92 処理系において測定したところ， その平均値はそれぞれ 585 回，21873 回，4.18 秒となった [*22]．
最後に，上記の例題を 2 つの提案との関係において論じよう．この例題のキャスタはデー タを局所的に参照するだけで，また手順を構成する 1 ステップをあたえるだけで問題解決 をはかろうとしていた．そしてこの問題においては，上記のかんたんなキャスタにおいて 一応は目的を達することができた．したがって，提案におけるマクロ・モデルにもとづく 観測・制御の必要はとくにないといえる．このように制御なしで目的を達することができ たのは，反応規則として適切なものをえらんだという理由もあるが，最大の理由は局所秩 序度として適切なものをえらんだことである [*23]．もし局所秩序度として不適当なものをえら んだときは，計算の方向を修正するためにマクロ・モデルがやくにたちうると予想される． ただし，いまのところこの予想を実証するような例題はみつかっていない．また，計算の 高速化をめざすなら，上記のキャスタについてもマクロ・モデルにもとづく観測・制御が 有効でありうるとかんがえられる [*24]．この点については次章でさらにのべる．
[→ 次章]
[*1]
Programming ということばを追放するため，それにかわることばとして casting をえ
らんだ．Cast という単語には「さいころをなげる」，「計算する」，「配役をきめる」な
どの意味があり，よりふさわしいとかんがえた．
(10/14/94 追記)
しかし，現在でもまだこの単語をつかうことに疑問をもちつづけている．
[*2] (10/14/94 追記) CCM について説明するとき，最近にいたるまで，この章におけるのと基本的には 同様の説明をしている (たとえば ...)．しかし，現在ではもっとわかりやすい説明が 必要だとかんがえている．その一方ではより形式的な定義をするべきだという指摘も うけている．いまのところ形式的な定義は記述していないが，そのおもな理由は， まだ CCM の詳細な意味をどのようにするべきかがきまっていないからである．とくに， いくつかの本質的に重要な問題が解決していないので，現状のままで意味を定義しても (言語としてとじさせることはできるとかんがえられるものの) あまり意味がないとかんがえている．
[*3] CCM においては「計算」や「プログラミング」にかわることばとして「キャスティング」 ということばをつかっている．プログラムに相当するものを「キャスタ」とよぶのも， それゆえである．しかし，キャスティングということばがそうであるように，新奇な ことばをつかうことによって，かえってわかりにくくなったり，誤解をまねいている ともかんがえられるので，この用語に関しても再検討が必要である．
[*4]
ひとつの原子から複数の無名のリンクまたは複数の同名のリンクをはることをゆるす
と，興味ある動作が実現される．実際，後述のグラフ彩色の問題ではこのようなリンクを
使用している．
(10/14/94 追記)
このようなリンクの存在が SOOC の特徴のひとつだとかんがえている
[Kan 94]．
[*5] (10/13/94 追記) 現在もまだ CCM に階層構造をいれていない．その理由は，木構造のような古典的な 階層構造は CCM においてめざしている柔軟な計算にはあわないとかんがえられるからで ある．すなわち，hierarchy ではなく heterarchy (散層) としての階層構造をいれる べきだとかんがえているが，そのための適切な方法はいまもわかっていない．
[*6] CCM においては，化学反応系のように (物理的な意味での) 距離の概念が導入され ていないから，局所的ということばは距離がちかいということを意味しない．
[*7] (10/14/94 追記) プロダクション規則というものは，エキスパート・システムの開発や AI における認知モデルなどにおいてつかわれているプロダクション・システムの もっとも重要な構成要素である．したがって，CCM も一種のプロダクション・ システムだとかんがえられる．しかし，CCM は従来の AI 的なプロダクション・ システムよりは化学反応系 (これも一種のプロダクション・システムだとみなすことが できる) にちかいとかんがえている．
[*8] (10/14/94 追記) 局所秩序度は化学反応系とのアナロジーでみれば，結合エネルギーに相当するものだ とかんがえることができる．
[*9] したがって，右辺にあらわれるパタンは，原子の生成に必要な情報をすべてもって いなければならない．
[*10] したがって，反応規則には記述されていないその原子へのリンクがもしあったとし ても，そのリンクは保存される (dangling link とはならない)．リンクの存在および秩序度 に関する条件により，CCM における反応は通常のプロダクション・システムにくらべて 意味が複雑化している．とくに，後述のように反応前に右辺のインスタンス秩序度を評価 する必要があることから，並列論理型言語における ``コミット'' と同様の困難な問題がお こる．きちんと意味を定義することは今後の課題である．なお，左辺の原子と右辺の原子 は，ラベルをつけることによって対応づけられる (図 6 参照)．
[*11] (10/14/94 追記) 局所秩序度を結合エネルギーとして解釈するばあいには，この条件は，エネルギーが 低下するときだけ反応がおこるということを意味する．
[*12] 金田 [Kan 92] がのべているように，実行が中断されたあとでも条件をみたすインス タンスが生成されると，ふたたび反応がおこる．
[*13] 金田 [Kan 92] は決定的戦略とよんでいるが，まぎらわしいので系統的戦略というな まえにあらためた．
[*14]
金田 [Kan 92] ではのべなかったことを，すこしつけくわえておこう．系統的戦略を
使用するとリミット・サイクル (ダイナミック・ループ) におちいるばあいがある [Kan 92]
が，ランダム戦略においてはこのようなことがないので，そのほうがあつかいやすいであ
ろう．
(10/14/94 追記)
これがランダム戦略に関して現在わかっている最大の利点である．このことは
[Kan 93]
においても指摘している．
[*15] スケジュリング戦略の自己組織化というのも，ここではかんがえないが 興味ある研究課題である．
[*15a] (10/14/94 追記) おなじ問題をとりあげた他の論文として 金田 [Kan 93a], [Kan 94a], [Kan 94b], [Kan 94c] などがある． このなかで 金田 [Kan 94b] は動的な彩色問題をあつかっている．
[*16] なお，CCM においてはシステムの動作中に原子を追加したり削除したりすること ができる．本来，自己組織化の研究はこのような開放系をあつかうはずだが，ここではシ ステムの外部からデータがあたえられるのはシステムの動作前にかぎることにする．
[*17]
図 6 の反応規則の記述においては，わかりやすさを重視して厳密さを犠牲にしてい
ることをことわっておく．
(10/14/94 追記)
この反応規則を SOOC によって記述すると，つぎのようになる．
...
金田 [Kan 94?] においては，これとはことなる
反応規則を定義している．
[*18] このリンクは無名なので，ある edge 型のデータからでるリンクは規則左辺のどのリ ンクともマッチしうる．したがって，そのリンクによって結合された vertex 型のデータは， 規則左辺のどのパタンともマッチしうる．
[*19] C3 はランダムに生成しているので，C3 として C1, C2 と同一の色が選択されること もある．しかし，そのばあいには反応規則の適用によってインスタンス秩序度が増加しな いため，反応規則は適用されない (後述の局所秩序度の定義を参照)．このように，秩序度 に関する条件があることによって，キャスタの記述が簡潔になっている．
[*20] 金田 [Kan 92] においてはこの言語・処理系を SOOP (Self-Organization-Oriented Programming) とよんでいたが， ``完全な計画'' を意味する Programming ということばを追放するために，それを Computation にあらためた．
[*21] このキャスタにおいては辺から頂点へのリンクが単方向のポインタとして実装され る．ところが，これでは規則左辺のマッチングにかかる時間がながくなる．そのため，頂 点から辺へのリンクをもうけることによって双方向のポインタにし，それによって高速化 をはかったという点がおもな改良点である．
[*22]
発表においては，図 6 の規則では 17 頂点，46 辺の例題の解をもとめるまでに 1000
回以上の反応を要すると報告したが，これはあやまりだった．ただし，改良された非局所
的な反応規則 (下図) のほうがすくない反応回数で解がもとめられるという点は，報告の
とおりである．
[*23]
グラフ彩色問題においては，すべての辺について辺の局所秩序度が 1 であるという
ことが解の必要十分条件になっている．すなわち局所秩序度の定義が問題の仕様をあたえ
ているから，問題をとくことができたのである．このことは，金田 [Kan 92] でしめした
N クウィーン問題 (これも制約充足問題) のプログラムについてもいえる．
(10/12/94 追記) CCM においては ``不完全な仕様'' からの計算をめざしているが，
いまのところ仕様の完全化をするための方法は (研究目標においてはいるものの)
あたえられていないので，局所秩序度としてはただしいものをあたえるほかはない．
これに対して，反応規則についてはもっと任意性がある
(第 5 章の脚注 [*3] 参照)．
[*24]
たとえば，観測結果にもとづいて，反応規則をまえの脚注でしめした Change2 にか
きかえるというような ``制御'' をおこなうことは，具体的な方法はここではしめさないが，
可能であろう．
(10/14/94 追記)
このような ``制御'' が可能だとかんがえるのは，脚注 [*23]
においてのべたように，反応規則の定義には任意性があるからである．