前提知識として知っておいてほしい単語は以下の2つくらいです。
- グラフ(点と点が繋がってるアレのこと)
- 次数(頂点に繋がってる辺の本数のこと)
問題内容
自然数nとdが与えられる。頂点数nでどの頂点の次数もd以下であるようなグラフのうち
1. 直径
2. ASPL
が小さいものを構成せよ。ただし直径が小さい方良く、直径が同じで会った場合はASPLで比較する。
Graph Golfのページを見ればわかるのですが実際には与えられるnとdは決まっていて、このようになっています。
グラフの直径(diameter)は最短経路長のうち最大のものです。
ASPL(Average Shortest Path Length)というのはその名の示す通り最短経路長の平均の値のことで、要するにワーシャルフロイド法などで求めた全点対の距離の平均の値のことを指します。
＊表の各セルのパーセントのところはASPLには理論的に下限があって、その下限に対して今得られているベストなグラフには何パーセントの誤差があるのか、というのを表しています。
問題背景
この問題は元々はOrder/degree Problemとして有名な問題で、今まで特に有効な手法などは与えられていませんでした。もともとグラフの頂点数(order)、直径(diameter)、次数(degree)の間には関係があって、３つのうち二つを固定してもう一方を最適化するという研究はあって、中でも一番有名なのは直径と次数を固定して頂点数を最大にするDegree/diameter Problemというものです。これについてはCombinatorics Wikiが詳しいです。
今回のOrder/degree Problemの実用上の応用としてはネットワークトポロジーの設計ひいてはスーパーコンピュータの設計にあります。いわばCPUがn個あってそれぞれはd個のケーブルでつなげることができるとした時に平均ホップ数をできるだけ小さくしたいという設計思想があるわけです。
基本手法
ナイーブな手法について説明します。まず初期グラフ(n頂点d-regularなランダムグラフ)を生成します。d-regularというのは全ての頂点の次数が等しくdであるという意味です。
ここで、今持っているグラフから辺を2本選び、それぞれをa-b, c-dとします。その辺を図のようにa-c, b-dとつなげ変える操作をswitchと呼びます。
次に今持っているグラフの評価関数(evaluation function) f(G)を定義します。ここではそのグラフのASPL値を評価関数として採用しましょう。
そうすると、一つの素朴な反復アルゴリズムを与えることはできます。初期グラフからスタートして近傍を取り、評価してその評価値が何かしらの条件(例えば今持っているグラフの評価値より良いなど)を満たしていた時に解を更新していくというものです。
このように近傍を探索して解を更新していくアルゴリズムの枠組みを局所探索(local search)と呼び、特に評価値が良くなったら即更新、というものを貪欲法(greedy)と呼びます。また、今回のswitchのように2本のエッジを付け替えるものを近傍として定義したgreedyのことを2-opt法と呼び、主に巡回セールスマン問題(TSP : Traveling Salesman Problem)に対する一つの手法として有名です。
これ以上更新が行えなくなった時の解のことを局所最適解と呼びます。評価関数が凸だったら局所最適解が全体の最適解であることが保証されるのですが、今回はそういうわけではありません。したがって、初期解の場所によっては悪い局所最適解に行き着くこともありうる、という問題点をこの局所探索ははらんでいます。
さらに、この局所探索は評価関数の呼び出しを非常に大きな回数行います。したがって評価関数の時間計算量が大きな障害になります。今はASPLを評価関数として用いているので時間計算量は各頂点からのBFSによってO(VE)=O(n^2 d)だけかかります。これでは到底現実的な時間では良い解を得ることはおろか局所最適解を得ることすら困難です。
ということで、この2点をどう克服したかについて簡単に紹介しようと思います。
GPGPUによるASPLの評価
特にトピックとしてあげるまでもないのですが、ASPLの評価をGPGPUを使って並列化しました。隣接行列のk乗の(i,j)成分はiからjへの長さkのパスの本数を意味しています。したがって隣接行列を2乗、3乗、・・・としていき初めて(i,j)成分が非ゼロになった時のkの値がi-j間の最短経路長になります。実際は累乗の計算はグラフの直径と同じ回数まで求めればよく、あとは行列積をCUDAで書けばOKです。しかも今回は隣接行列がsparse行列(非ゼロ成分の個数が少ない)なので、その点をうまく利用することができます。
ASPLの近似
このトピックがこの記事のメインとなります。要するに長い時間をかけてASPLを計算するのではなくその近似値を高速に評価しよう、という話です。実はO(1)時間の評価関数を考えました。
まず前提としてグラフの直径を3に限定します(それ以外の直径のグラフに関してはGPGPUで頑張りました)。Graph Golfでいうとn=10000, d=64といった大規模なグラフをターゲットにします。
ここで発想のモチベーションがいくつかあるので書いておきます。
- 「switchというちょっとの変化をちょっとの時間で捉えよう」という思想。
- 評価関数自体を求めるのではなく、switchによる評価関数の差分を何かしらのテーブルを使って求めよう。
- 小さい閉路があると望ましくない。
というところから来ています。ここでグラフの頂点vを適当に一つとってきてvからBFSでグラフを展開してみましょう。このような感じになります。
一番上がv、その下の段にはvと隣接している頂点(当然d個)、さらにその下にはvからの距離が2の頂点(個数はグラフに依存。多いほどASPL的に良い)、最後にvからの距離が3の頂点が並んでいます。ここで、もしグラフ(直径は3)に三角形四角形が存在しないと仮定しましょう。すると、距離2の頂点の個数はd(d-1)となり最大になります。したがってASPLの下界を達成し最適なグラフとなります。また、vを含む三角形や四角形があると距離2の頂点数がその分減ってしまい、結果としてASPLに悪影響をおよぼしてしまいます。つまり、グラフの三角形の四角形を減らせば良い、ひいては三角形の個数と四角形の個数を評価関数に採用すれば良さそうじゃね？となってくるわけです。そこで三角形の個数を△、四角形の個数を口として、評価関数を以下のように定義しました :
f(G) = 3△+2口
3と2がでてくる理由はこの図のように
- 三角形が一つあると(i-j),(j-k),(k-i)の3つのペア
- 四角形が一つあると(a-c),(b-d)の2つのペア
に影響を与えるからです。また、実は直径3のグラフのASPLというのは
このような関係が成り立つことが証明できます。つまり上で定義したfを減少させるというのはASPLの上界を下げるということにつながります。
O(1)時間で評価
ASPLはグラフに含まれる三角形と四角形の個数を使って近似でき、それを評価関数に採用すれば良いという話をしました。ここでは、switchによる三角形と四角形の個数の増減をO(1)で評価する方法について説明します。まず前処理として、以下の三つをテーブルとして持ちます。
- A[][] : 隣接行列
- A2[i][j] : iからjへの長さ3のパスの本数
- A3[i][j] : iからjへの長さ3のパスの本数(ただし同じ辺を二度以上通らないパス)
こうすると、例えばグラフに辺i-jを追加した時に増える三角形の個数はA2[i][j]で取得でき、逆に辺i-jを削除した時に減る三角形の個数もまたA2[i][j]で取得できます。
四角形の場合もそれぞれA3[i][j]で取得できます。
目標はswitch後の△と口の増減です。そして今持っているのはswitch前のグラフについてのテーブルです。switchという操作はa-b , c-dの削除およびa-d, b-cの追加と捉えることができます。まず三角形についてですが、a-bとc-dを削除する時は大丈夫でしょう。しかしそのあとa-dとb-cを辺を追加する時にはテーブルではa-bは繋がったままの値しか取得できないので、A2[a][d]で増えると想定している三角形の中にはa-bを利用しているものもあります。実際はこれらの三角形は増えることはないので、その分、つまりa-b, a-dを利用する三角形の個数をカウントして引かなければいけません。実際これはA[b][d]と等しくなります。四角形について考えるとさらにややこしくなります。
調整が必要なのでデバッグとかはかなり大変なのですが、このようにすれば個数の上限をO(1)で評価することが可能になります。
最後にテーブルの書き換えについての話をします。解を更新するとグラフ自体も変化するためテーブルの値も動的に書き換えなければいけません。詳細は省きますがA2の書き換えはO(d)、A3の書き換えはO(d^2)でできます。
焼きなまし法
ここまででO(1)で評価できる近似について述べました。これを使うとn=10000 d=64のグラフでも、いろいろなテクニック(多くの三角形四角形に含まれてる順で近傍を探していく)を使えば、3時間ちょっとで局所最適解にたどり着きます。しかしやはりより良い解を得るためにgreedyではなく焼きなまし法を使うことができます。実際Graph Golfの問題に置いては焼きなまし法はかなり有効で、greedyで得られる局所最適解と比べてかなり良いグラフを得ることができると経験的にわかっています。実際私たちも一位をとったほとんどのグラフは焼きなまし法で得ることができました。
まとめ
- 三角形と四角形の個数でASPLを近似できる
- この事実を使うとO(1)の評価関数を設計できる
- 焼きなまし法は強い
- 北海道は寒い
発展
実は、直径が3のグラフのASPLの近似はさらに良いものがあります。というか結構簡潔で美しい等式が証明できます。(それは三角形四角形の個数以外にも幾つかの図形の個数を用いるのでO(1)で評価できるとは限りませんが...)
この辺の細かいことは論文に書こうと思っています。
0 件のコメント:
コメントを投稿