図 5.1 N クウィーンにおける解がもとめられる確率
CCM にもとづくプログラミング言語 SOOC [*1] とその処理系を開発し，いくつかの小規 模問題のプログラミングと実行をこころみた．これらのなかで，5.1 節では N クウィーン 問題のプログラムの実験結果，5.2 節にそれ以外の実験結果の要約をしめす．
前述の N クウィーン問題のプログラムを SOOC によって記述し，実験した．その結果を 要約する．インスタンス間の競合のため，系統的なスケジュリング戦略を使用するとリミ ット・サイクルにおちいるばあいもあるが，ランダムに生成した初期状態から計算をはじ めても大半は停止することがわかった [*2]．また，解以外の状態で停止することはない．
最右条件優先戦略をつかって停止するばあいについて，解がもとまるまでの計算時間を N = 50 までもとめたところ， O(N^4) 〜 O(N^5) であることがわかった [*3]．計算時間は規則の 左辺をしらべた回数にほぼ比例する．バックトラックをつかって解を計算するには指数的 な時間がかかるから，このプログラムはそれよりはるかにはやい．ただし， O(N) で解を生成する方法 [Aki 91] にくらべればはるかにおそい．
図 5.1 にはリミット・サイクルにおちいらずに解がもとめられる確率を 100 回の試行から 実験的にもとめてしめした．縦軸は確率を対数スケールであらわしていて，上限が 1 とな っている．
この図には，前記のプログラムにおける条件の出現順をかえて最右条件優先戦略のもとで もとめた確率 (スケジュリング戦略 1 〜 3) と，前記のとはことなる規則 (3 者交換規則) を つかってもとめた確率とをあわせてしめした．初期配置はランダムにきめた．また，この 図にはクウィーンのランダムな配置を生成したときにそれが解になっている確率 (問題空 間中での解の割合) をもあわせてしめした．
この図から，解がもとめられる確率のスケジュリング戦略に対する感度がたかいことがわ かる．すなわち，スケジュリング戦略 1 においては N = 6 のときをのぞいてほぼ確率 1 で 解がもとめられる．他の戦略はこれよりはるかにおとっているが，配置をランダムに発生 させるのにくらべるとはるかによい．この結果は，CCM におけるスケジュリング戦略の 重要性を示唆しているとかんがえられる [*4]．
また，最右条件優先戦略をつかって停止するばあいについて，解がもとまるまでの規則の 適用回数とマッチング回数とを実験的にもとめた．図 5.2 がその結果である．マッチング 回数とは規則の左辺をしらべた回数，すなわちしらべたインスタンスののべ個数である． この実験では，クウィーンの初期配置を乱数によって生成して，ひとつの N につき 10 回測定した．
つぎに，実験などからわかった N クウィーン問題のプログラムの 2 つの性質についての べる [*5]．
上記の N クウィーン問題のプログラムにおいては，その解決手順を構成するためのステ ップを記述するだけで問題解決が可能になっている．したがって，2 章でのべたような問 題解決手順の自己組織化がおこなわれているともかんがえられる．しかし，このプログラ ムは本来の自己組織系がもつべき性質の一部をもつだけであり，自己組織系だとはいえな いであろう．また，このプログラムの動作に関してはまだわからないことがおおく，その 解析は今後の課題である．たとえば，なぜ停止しないばあいがあるかという問に対するこ たえはまだえられていない [*9]．
上記の N クウィーン問題のほかに，これまでに巡回セールスマン問題 (TSP)，輸送問題， ニューラル・ネットによる N クウィーン問題，ソートなどを SOOC によって記述して実 験した．これらのうちTSP は，10×10 の格子点に 8 個または 9 個の都市を配置すると， いずれのばあいも10 回の試行のうち 9 回は最適解がもとめられた．また，都市数 500 ま で実験をおこない，計算時間は O(N^2.3) であることがわかった．TSP においても，解がも とめられたあとで都市を追加または削除することにより再動作させられる [*10]．
[→ 次章]
[*1] SOOC = Self-Organization-Oriented Computing．以前は SOOP (P = Programming) という ことばを使用していたが，Programming ということばを消去するために SOOC とした．
[*2] インスタンスの選択にランダムネスを導入すれば，規則的な選択によってはリミッ ト・サイクルにおちいるばあいでも，それをふせぐことができる．
[*3] スケジュリング戦略などによっても計算時間のオーだは変化するが，現在の SOOC 処理系でランダム戦略をつかったばあいには，O(N^4.6) であることがわかっている．
[*4] なお，疑似乱数を使用するランダム戦略においては，上記のようなリミット・サイ クルは生じないことが予想されるが，このことは実験的にほぼたしかめられている．その 理論的うらづけも廣川 [Hir 92] によってほぼえられている．
[*5] このほかに，この図からは N = 6 のときの確率が特異的にひくいこともわかる．すな わち，たいていの方法においては，6 クウィーンのときの確率が特異的にひくくなってい る．このようになる理由はまだわかっていない．
[*6] この論文の以前の版においては，この性質を漸動性とよんでいた．ここでは造語を やめ，これを漸進性とよぶことにした．
[*7] 通常のプロダクション・システムにおいても，プログラミングしだいでこのような 意味での漸進性をもたせることができるのはもちろんである．ただし，CCM においては 3 章の脚注でのべたように規則が可逆であっても秩序度が定義されているためにシステム が動作するのに対して，プロダクション・システムにおいては規則が不可逆でなければな らないことから，巧妙なプログラミングによらなければ漸進性をもたせることができない とかんがえられる．なぜなら，漸進性がなりたつということは，システムにあたえられた 問題が過去の時点にもどされたならば，システムの状態ももとの解状態 (あるいはそれと 等価な状態) にもどらなければならないということを意味するからである．実際，N クウィーン問題のばあいには CCM による規則の左辺と右辺は対称になっている (すなわち，左辺と右辺とは交換可能である)．
[*8] N クウィーン問題のプログラムにおいては，交換の際に他のすべてのクウィーンと の関係をしらべるようにすると，上記のプログラムとはちがって大域的秩序度関数が局所 最大値をとる点 (袋小路) での停止がおこるようになる．実験の結果によれば，6 クウィー ン問題のばあいには10 回中 8 〜 9 回は局所最大点での停止がおこった．
[*9] N クウィーン問題のプログラムの実行結果に関しては，さらに解析をすすめたうえ で再度報告する予定である．
[*10] 巡回セールスマン問題や他の問題の実行結果に関しても，後続の報告においてのべ る予定である．