ニューラルネットによるNクイーン問題

羽鳥研究室  清水 秀之 有馬 雅彦

 


1.はじめに

カオス・複雑系の一環としてニューラルネットを学んだ。その応用としてニューラルネットを使ってNクイーン問題を解く。

 

2.Nクイーン問題とは

Nクイーン問題とは「n×nの升の中に、n個のクイーンを、どのクイーンもお互いに効きが当たらないように並べよ」というものである。クイーンというのは、チェスで使われているクイーンのことを指し、チェス盤のなかで、縦、横、斜めに関してどこまでも進むことができる。クイーンは日本の将棋でいえば、ちょうど飛車と角を合わせた動きをする。解は1通りとは限らない(図1参照)。問題の条件さえ満たしていればクイーンの置き方に制限はない。

 

 

 

 

Q

 

 

 

Q

 

 

 

Q

 

 

 

 

 

 

 

 

 

 

Q

 

 

 

Q

 

 

 

Q

 

 

 

 

 

図1

6クイーンの解答例

 

 

 

 

3.問題の表現

ニューラルネットワークで組み合わせ最適化問題を解く際に、まず一番最初に行う作業は、その問題に対して適切なニューラル表現を与えてやることである。ニューロンを用いた問題の表現をニューラル表現という。このニューラル表現を得ることこそニューラルネットワークで問題を解決しようとするときの最重要課題である。

Nクイーン問題のニューラル表現を考えてみよう。n×nのチェス盤の上にクイーンがどう配置されているかは、n×n個のニューロンを使った2次元の行列で表現する。こうすれば、列目の升にクイーンがおいてあるかないかは、として簡単に表すことができる。たとえば、4行5列目の升にクイーンが置いてあれば、3行2列目の升にクイーンが置いてなければという具合である。クイーンが升に置いてあればニューロンが発火して1になり、置いてなければ0になっているのが読みとれる。この行列を用いたクイーンの配置の表現は、直感的に理解しやすいと思う。

ニューラルコンピューティングでは、このような問題の表現を与えることを、「n×n個のニューロンを使ってNクイーン問題を表現した」などといい、すなわち4行5列目の升にクイーンが置いてあることを「4行5列目のニューロンの()が発火している」などという。「ニューラル表現」、「ニューロン発火」などというのはニューラルネットワークに頻繁に使われる大事な用語である。行列の具体的な値は次の図2のようになる。

 

図2

ニューラル表現の例

 

 

 

 

4. Nクイーン問題の動作式

動作式とは、ニューロンが問題解決を目指して動くようにするための式で、各ニューロンの結合係数を決定している。この式がニューラルネットワークのまさに心臓部であり、問題をニューロンで表現して動作式が設計できれば、実はほとんどニューラルネットワークは完成なのである。

Nクイーン問題における、マッカロック・ピッツニューロンを用いたときの列目のニューロンの動作式を次に示す。

 

                                        

                                                 

 

 

 

Nクイーン問題の解を求めるには、各行各列に1個ずつクイーンを並べなくてはいけない。これはn×nの盤にn個のクイーンをお互いに効きが当たらないように並べるのだから、当たり前の必要十分条件である。このことを実現するための工夫が、さきに示した動作式の第1項および2項である(ABは正の定数)。第1項は、各行にただ1個のクイーンを置くようにニューロンの動きを制約している。条件が満たされていれば項の値は0になり、矛盾があれば負の値になり、矛盾が大きければ大きいほど、負の絶対値も大きくなることが読みとれる。負の値をとるということは、マッカロック・ピッツニューロンの定義

から、ニューロンを発火させない方向へ向かうということである。同様にして、第2項は各列の制約を与えている。さらに縦横だけでなく、斜めに関してもお互いに効きが当たってはいけないので、第3項と第4項で斜めに関する制約も与えている。斜めに関しては0個または1個のクイーンが置かれていなくてはならない。縦横に比べると少しややこしい項になっているが、式を追っていくとわかると思う。ニューロンが制約条件を満たすと、動作式の右辺の値が0になることが読みとれる。

 

5.ヒルクライミングターム

次の2つの項を先の動作式に加える方法もある。すなわち

 

 

はヒルクライミングタームと呼ばれ、ニューラルネットワークの状態が極小解に陥ったときに、そこから脱出するための工夫である(Cは正の定数)。ここは非常に大事な最後の詰めであり、ニューラルネットワークをより完成度の高いものにするための隠し味である。たとえば、第4行および第2列にはクイーンを置くことができず行き詰まってしまうことがある(図3参照)。このような硬直状態を最小解といい、その打開策はヒルクライミングタームが働いてくる。ここでヒルクライミングターム中の関数を次のように定義する。

 

 

行と列に発火しているニューロンが1つもなければ、ヒルクライミングタームが働いて、を発火する方向へと導き、最小解を脱出させる。こうして最終的な動作式は次のようになる。

                                                                                   

 

 

 

 

 

 

 

 

 

 

 

                                                  

 

 

 

Q

 

 

 

 

 

 

 

Q

Q

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Q

 

 

 

Q

 

 

 

 

6クイーンにおける極小解の例

 

 

 

 

 

連続モデル

今回、Nクイーン問題を解く際、次のようなモデルを使って解いている。

for(i=1;i<=n;i++){

   for(j=1;j<=n;j++){

U[i][j] += dU[i][j];

if(U[i][j]>0) V[i][j] = 1;

else V[i][j] = 0;

  }

}

このモデルは連続モデルと呼ばれている。各ニューロンについてUの値を一つ更新するごとに、入出力関数を通じてVに結果を反映させている。

 

7.解の個数

はじめに述べたように解は一つではない。

クイーン数

解(全パターン数)

10

40

92

352

10

724

11

2680

12

14200

13

73712

14

365596

15

2279184

クイーン数と解の個数

 

n=6ぐらいまでは自力で解けるがそれ以上になると気が遠くなる。斜めの制約をしない場合、各行各列に一つずつクイーンを置く総数はn!通りあり、全てを検索するとコンピュータでも時間がかかる。しかしニューラルネットを使って解くと数秒から数十秒で解ける。これはニューラルネットの戦略の優秀性を証明している。

 

 

8.解の個数の求め方

自分たちのプログラムには解の個数を求めることはしていないので、引用したプログラムに従って解の個数の求め方について説明する。

全解数を求めるには全探索する必要がある。したがって探索時間を犠牲にしてしまうことになります。そこで「対称を考慮して全解数を導く」という方法が考えられている。全解の中から回転・反転などによる変換によって同型になるものどうしをグループ化したものをユニーク解ということにする。これは、左右反転によるパターンの探索を省略して最後に結果を2倍するというアイデアの拡張版といえるものである。そしてそれを実現させるには「あるユニーク解が属するグループの要素数はいくつあるのか」という考察が必要になる。
 最初に、N=5についてはクイーンが右上角にあるユニーク解を考えます。斜軸で反転したパターンがオリジナルと同型になり)、右上角のクイーンを他の3つの角に写像させることができるので)、このユニーク解が属するグループの要素数は必ず8個(=2×)になります。
 次に、クイーンが右上角以外にある場合は少し複雑になるが、結果は以下のようになる。

 (1) 90度回転させてオリジナルと同型になる場合、さらに90度回転(オリジナルから180度回転)させても、さらに90度回転(オリジナルから270度回転)させてもオリジナルと同型になる。

 (2) 90度回転させてオリジナルと異なる場合は、270度回転させても必ずオリジナルとは異なる。ただし、180度回転させた場合はオリジナルと同型になることも有り得る。

(1)に該当するユニーク解が属するグループの要素数は、左右反転させたパターンを加えて2個しかない。(2)に該当するユニーク解が属するグループの要素数は、180度回転させて同型になる場合は4個(左右反転×縦横回転)、そして180度回転させてもオリジナルと異なる場合は8個(左右反転×縦横回転×上下反転)になる。 以上のことから、ひとつひとつのユニーク解が上のどの種類に該当するのかを調べることにより全解数を計算で導き出すことができます。

 

9.考察

動作式を解く際、ヒルクライミングタームを加えずに解いてみると、硬直状態になることもあったがほとんど解に到達した。ヒルクライミングタームを加えたものと比べて解に到達するまでの時間が遅かった。よってヒルクライミングタームを加えることは極小解からの脱出の他に時間短縮にも関与していると考えられる。

 

10.参考文献

 

ニューラルネットワーク

著者 武藤 佳恭

ニューロコンピューティングの数学的基礎

著者 上坂 吉則

独習java

著者 ジョゼフ・オニール

java入門

著者 林 晴比古