10の140乗―。配電網の経路組み合わせの数は天文学的数字にのぼる。湊真一氏のチームは、その中から電力損失が最小となる経路をわずか1時間で探索、配電網全体でロスを3％削減できることを証明した。スマートグリッドの実現を後押ししたのは、湊氏が考案した圧縮アルゴリズム「ZDD」だ。
配電網の経路は、どのくらい複雑なのですか。
配電経路を切り替えるためのスイッチは、30万人規模の都市に電力を供給する一般的な配電網で468個存在します。これらのスイッチを通る経路は、全体で2の468乗通り考えられます。これは10の140乗の組み合わせに相当します。宇宙の原子の数は全部で10の80乗と言われているので、ものすごい数なわけです。
スーパーコンピュータ「京」でも1秒間にできる演算は10の16乗（1京）回。100年、1000年かけても計算しきれない規模です。従来は全ての経路を正確に把握するのは不可能でした。このため、最も効率の良い配電経路を導き出すこともできなかったのです。
2012年2月に送電ロスを最小化する技術を発表しました。
1993年に私が考案した「ZDD（ゼロサプレス型二分決定グラフ）」というアルゴリズムを使って演算回数を減らすことで、「京」でも計算しきれない数の組み合わせから最適解を探し出せるようにしました。
送電網の経路は「各家庭が変電所から必ずつながっている」などの幾何学的条件や、「電線が焼き切れないよう許容電流が超えないようにする」といった電気的な制約を満たす必要があります。これらの条件を満たす経路を表すためにZDDを利用したところ、計算対象のデータをCD-ROM1枚分にまで圧縮できたのです。この中から効率の良い配電経路を見つけ出すアルゴリズムを新たに開発し、最適解を導き出しました。
一生で最もうれしかった出来事
ZDDは演算回数を減らすためのアルゴリズムです。1986年に開発されたBDD（二分決定グラフ）というアルゴリズムを基にしています。BDDは二つのルールで演算処理を圧縮します。配電網のスイッチは「ON」か「OFF」の状態をとりますが、一つめのルールは、あるスイッチがONでもOFFでも結果が同じであれば、そのスイッチによる分岐は省略するというもの。もう一つは、ある部分の複数のスイッチについてONとOFFの組み合わせを変えても残りのスイッチの条件が変わらない場合、分岐を一つにまとめてしまうというものです。
ZDDはこのBDDを改良したもので、「必ず0になると分かりきっている変数は削除する」という考え方のアルゴリズムです。固定的に0となる変数の出現確率が高い演算ほど、高い圧縮効果を期待できます。
例えば、必ずOFFになることが明らかなスイッチがあれば、ZDDではそのスイッチによる分岐は存在しなかったものとして削除します。条件によりますが、BDDより100～1000倍高速化できることもあります。
ZDDに対する反応はどうでしたか。
まずLSI設計のトップカンファレンスで発表しました。その分野では反響があったのですが、情報科学全体から見るとすごく狭い分野です。2000年頃からデータマイニングなどの分野でも使えそうだという話にじわじわとなってきたのですが、一気に有名になったのは2009年に米スタンフォード大学のドナルド・クヌース名誉教授の書籍『The Art of Computer Programming Volume 4』に載ってからですね。この本は情報科学分野の研究者にとってはバイブルのような存在です。そんな『The Art of Computer Programming』シリーズの中で、日本人が考案したアルゴリズムが独立した項目として詳しく解説されるのは初めてのことでした。
私が面白いと思ったことをクヌース氏も面白いと思ってくれた。一生の中でも最もうれしかった出来事です。あとは何もしなくても満足というくらい、ありがたいことでしたね。
電力危機で一気に具体化
配電網を扱ったきっかけは？
ZDDが有名になったのを機に、2009年秋に「ERATOプロジェクト」を始めました。目指したのは、従来より100倍、1000倍速い演算を可能にして、データマイニングや統計解析といった分野で実際に役立つような技術基盤を構築することです。
ちょうどその頃、早稲田大学の林泰弘教授がスマートグリッドに関する委員会の座長を務めていました。実は林先生とは1990年代にBDDを使った電力網の最適化を一緒に考えたことがあり、ERATOを立ち上げた直後、「一緒にやりましょう」と話していました。東日本大震災以降の電力危機で、この話が一気に具体化していったのです。
今回の研究成果の意義をどう捉えていますか。
この研究により、配電経路の最適化で電力ロスを3％抑えられることを証明できました。将来的に、ZDDによる経路最適化の技術はスマートグリッドの実現に貢献します。それをきっちりと証明できた。この点が大切だと思います。
実用化のメドは。
ERATOプロジェクトは2014年度で完了します。それまでに電力会社の方々などがツールとして使える形にしておきたい。企業との共同研究の部分で開示できないところ以外は、オープンソースとして開示していくつもりです。
ところでアルゴリズムに興味を持ったきっかけは何ですか。
小さい頃はラジオ少年で、授業中に回路図を書いていてよく叱られましたね。高校時代にNECの「PC-8001」を使い始めました。感動しましたね。プログラムを打ち込めば、いくらでも好きなことができる。大学で回路図を設計するソフトの研究室に入り、BDDに出会いました。
社会人になってからは、NTTのLSI研究所でアルゴリズムの研究をしました。しかし、徐々に研究よりはマネジメントが主になりました。そんな時に北海道大学で情報科学研究科設置の話があり、声を掛けてもらったのです。
このときに「やはり自分は好きな研究をしたかったんだ」と感じました。寿司職人はやっぱり寿司を握っていたいんですね。
湊氏は自身の研究領域を、原理原則を突き詰める「Science」と実際に動くものを作る「Engineering」の中間に位置する「Art（技法）」の領域だと説明する。
「Artはできるだけシンプルで汎用性の高いものであるべきだ」と、湊氏は話す。実社会における様々な問題の解決に役立つことを重視しているためである。
湊氏が考案したアルゴリズムである「ZDD（ゼロサプレス型二分決定グラフ）」が威力を発揮するのは配電網の最適化だけに留まらない。例えば、避難所の定員や距離、道の細さなどの条件を考慮した最適な避難所の設置検討にも応用できる。1票の格差に関する問題についても、最も格差がつきにくい選挙区割を導き出すようなこともできるという。
北海道大学大学院 情報科学研究科 教授
