日立と一緒に計算機の概念を変えよう！

研究開発グループ
基礎研究センタ 日立北大ラボ

研究開発グループ
Printed in Japan February 2017（01）

基礎研究センタ 日立北大ラボ

Hitachi × Hokkaido Univ.

複雑化する社会システムの最適化に向けて「日立北大ラボ」がめざすこと
交通渋滞の解消や物流コストの最小化、電力送電網による安定したエネルギー供給など、複雑化する社会システムの課題解決には、全体最適となる組み合わせを見いだすことが重要です。しかし、社会システムが複雑化すると、システムを記述するパラメータとその組み合わせが爆発的に増大し、最適なパラメータを決定することが困難になります。この問題は組み合わせ最適化問題と呼ばれており、日立ではこの問題を効率よく解く技術として、イジングコンピュータを開発しました。
複雑化する社会システムの最適化に向けて、日立北大ラボは個別テーマを超えた組織対組織の新しい協創をめざしています。

日立は、大学が有する豊かなイノベーション資源（知識・ネットワーク）と密に連携するため、2016年、国内3大学に日立北大ラボ、日立東大ラボ、日立京大ラボを開設しました。日立北大ラボでは、課題先進地域の特性を活用したソリューションの社会「社会創造数学」の3テーマの研究を推進しています。
実証をめざし、「エリアデザイン・北極域」「北大COI※・食と健康の達人」

課題先進地域の特性を活用したソリューションの社会実証
北海道の地域課題解決をめざし社会実験・協創を加速

エリアデザイン・北極域
気候、経済変動予測

北大COI・食と健康の達人
健康コミュニティーシステム

社会創造数学
複雑な社会を数学モデル化

寒冷地の都市デザイン学

地域の自律的健康管理を支援

最適化問題をリアルタイムに解く

北極域研究センター

FMI 国際拠点

電子科学研究所※文部科学省、国立研究開発法人科学技術振興機構が実施している「革新的イノベーション創出プログラム」（COI STREAM）にて推進されているものです。
● COI： センター・オブ・イノベーション ● FMI：フード＆メディカルイノベーション

12新たなコンピュータがなぜ必要か？

Hitachi × Hokkaido Univ.

組み合わせ最適化問題とは組み合わせ最適化問題の難しさ組み合わせ最適化問題とは、さまざまな制約のもとで多くの選択肢から、ある指標（価値）を最もよいものにする変数の値（組み合わせ）を求めることです。
最適化問題を解くことは、日常生活のさまざまな場面で皆さんも経験しています。
子どものときの遠足の菓子選び（菓子選択問題）を思い出してみましょう。

最適化問題の別の例として、セールスマンが複数の都市をどのように訪問すれば、最短の移動経路（最適経路）で済むかを考えてみましょう。
都市C
都市D

都市BからCまでの距離

3

都市B

変数

指標
（価値）

制約

どの菓子を選ぶのか？

?

決められた総額（予算）

経路1 [A-B-C-D-E-(A)]C

5

経路 M [A-C-B-D-E-(A)]

D

B・・・

8

4
5

満足度

A

E

C

D

A

E

B

都市E

都市A

五つの菓子（チョコ、ガム、クッキー、ポテトチップス、グミ）の値段と満足度が与えられています。
予算300円で満足度が最大となる組み合わせを求めなさい。
ヒント

4
7

4

菓子選択問題を具体的に考えてみよう

問題

52

変数 x1、x2、…x5 Э｛0, 1｝, 0：選択しない、1：選択する を導入して経路の候補

菓子選択問題を数式で表現してみよう。
■価値最大化（満足度） ………
■制約（決められた総額）………

10x1+3x2+4x3+8x4+7x5

120x1+30x2+90x3+150x4+120x5≤300

変数

値段満足度

チョコ x1120円

10点

ガム x230円

3点

クッキー x390円

4点

ポテトチップス x4 150円

8点

グミ x5

120円

都市数が少なければすべての候補数を調べることが可能です。しかし、都市数が増えると、候補数が爆発的に増加し、最新クラスのコンピュータでも計算を終えるのに何日もかかってしまいます。

制約300円ABCDE(A)ABCED(A)ABDCE(A)ABDEC(A)ABECD(A)ABEDC(A)ACBDE(A)ACBED(A)ACDBE(A)ACEBD(A)ADBCE(A)ADCBE(A)

移動距離222420262226252723252121

都市数（n）

経路の候補

52530

12
3.1×1023
4.42×1030

巡回する都市数nが増えると、経路の候補が爆発的に増大［（n-1）!/2通り］

7点

社会システム
最適経路（移動距離最短）最適化問題抽出

経路を繰り返し探索

従来のコンピュータとプログラミングでは実用的な速度で問題が解けない。

計算量
爆発

～～
最適経路

●答えは10ページ

34

最適化問題に特化した計算機を開発

イジングコンピュータでできること

Hitachi × Hokkaido Univ.

半導体微細化の終えん

イジングコンピュータによる基底状態探索

従来の計算機はプログラミングによる柔軟性と汎用性を兼ね備え、さらに、ムーアの法則に従い、CPUの動作クロック周波数の向上に支えられることで、計算機の性能が向上してきました。
しかし、2000年代前半の半導体プロセス微細化の鈍化に伴い、クロック周波数が頭打ちとなってきています。これまでコア数増加による性能向上を図ってきましたが、今後、半導体微細化も終えんを迎え、コア数増加による向上も困難となることが予想されます。そのため、これまでの動作原理とは全く異なる計算機の開発が必要となります。

イジングコンピュータでは、最適化問題の価値・制約をイジングスピンのエネルギー関数に対応させ、エネルギー関数の最小値（基底状態）が最適化問題の最適解に対応します。
菓子選択問題の場合、スピンの値がその菓子を採用するか否か、総額が相互作用係数（ただし、金額が決められた総額を超えないように補助スピンを導入）、満足度が外部磁場に対応します。

CPUのコア数のトレンド

CPUの動作クロック周波数のトレンド

18

5.12
2.56

Intel (x86 Server DP)

1.28

Intel (x86 Server MP)

0.64

Intel (Itanium)

0.32

IBM (POWER)

0.16

106

0.04

4

ムーアの法則に従ったシステム設計

クロック周波数限界

1983

1988

1993

1998

2003

2008

1978

2013 年

1983

1988

1993

1998

2003

2008

2013 年

イジングチップ（12mm2の面積に約2万個のスピンを搭載）

J14σ4σ75J47J78σ8J45σ5J58J12J89σ2J25σ9J56σ6J69J23H(σ)=ΣJijσiσj+Σhiσi<i,j>i●

スピンの状態

●

相互作用

Jij

●

外部磁場

hiσ2=1 /=0(補助スピン)

h2

イジングチップでは、設定したスピン間相互作用・外部磁場に従い、スピン値の更新をデジタル回路で計算し、エネルギー関数が低い方向にスピンの状態を更新します。
ここで、エネルギー極小値（局所解）での停滞を回避するため、仮想的に温度による状態間のゆらぎを導入し、その温度に応じて、有限の確率でエネルギー関数が増加する方向にスピンの状態を更新させます。
温度を時間とともに下げていくことで、状態間のゆらぎが徐々に収束し、最終的にスピンの状態が基底状態（最適解）に遷移します。
σ1
J12 σ2J23
このアルゴリズムは「シミュレーテッド・アニーリング」と呼ばれ、イジングJ
J2514σ4σ5σ6J45J56
チップはデジタル回路技術でこのアルゴリズムを実現しており、近似的にJ47J58J69σσσ789最適解を求めることが可能です。
JJ78σ2スピンの状態、相互作用、外部磁場をメモリ（” 1” /” 0”）で表現

σ3J25J45σ5J47σ7J23J36J56σ6J58
J78σ8J69J89σ9J14σ4

スピン間相互作用

J14半導体回路で模擬

J3689

σ1σ：
i 0=↓ or 1=↑

J12σ4σ3徐々に更新（〈i, j〉は相互作用が存在するスピンの組）

σ1σ3
J36=0 選択しない

イジングモデルのエネルギー関数（三つの要素で構成）

イジングモデルσ1

CMOSプロセスを用いた専用ハードから、FPGAを用いた再構成可能プロトタイプ環境を構築

外部磁場（価値：満足度）=1 選択する

σ5h1

i=1

グミを選びたいが、菓子間の相互作用でガムが選択される

h5σ1エネルギー関数（評価関数）

磁石などの磁性体は内部の電子スピンの磁気モーメントがそろうことで磁性を得ます。
磁性体の物理現象はイジングモデルで記述されます。
イジングモデルのエネルギー関数は相互作用と外部磁場の2次形式で与えられます。

y3第1世代（CMOSイジング）

FPGAボードi=1

N2

i=1,…, N（N：菓子の種類数）、n=1, …, P（P：決められた総額）
σ：i 1 or 0（i番目の菓子を選択するときσ i=1、選択しないときσ i=0）
● y n：不等式の制約条件を扱うための補助スピン（金額n’ が1≤n’≤Pのもとで最適な総額に最も近いときyn’ =1、yn=0（n≠n’）となるように制約する）● w：i 各菓子の値段、h：i 各菓子の満足度● γ： 制約条件の強さに対応するパラメータ（エネルギー最小の解が、拘束条件を満たし、価値が最大の状態となるように決定する）

σ4y2

日立が開発したイジングコンピュータ

第2世代（FPGAプロト）

n=1

σ3

イジングコンピュータの開発
日立は最適化問題に特化したイジングコンピュータを開発しました。本計算機は、従来の計算機のように逐次計算を実行するのではなく、最適化問題を磁性体のスピンの振る舞い（磁性体の物理現象）にマッピングし、その物理現象の収束動作を実行・観測することで、短時間で適切な近似解をみつけることができます。

N相互作用

h4h3

P（制約：総額）●01978

n=1

●

y1

2

H(σ,y)=γ［(1-Σyn ) +(Σ nyn -Σ wiσi ) ］-Σ hiσi

AMD (Opteron)

20.01

P

Intel (Itanium)
IBM (POWER)（個） 8

選択されたお菓子の総額の候補は1からPのうちの一つ

総額の候補は一つであるIntel (x86 Server MP)

120.080.02Intel (x86 Server DP)

14AMD (Opteron)

コア数増大Intel (x86 Desktop)

16コア数

動作クロック周波数（GHz）Intel (x86 Desktop)

Hitachi × Hokkaido Univ.

σ7J47J78σ8J45局所解σ5J58J12J89σ2J25σ9J56σ6J23σ3J36J69徐々に更新

σ1局所解
基底状態(最適解)
スピンの状態（2nパターン）

状態間のゆらぎJ14σ4σ7J47J78σ8J45σ5J58J12J89σ2J25σ9J56σ6J23σ3J36J69n：スピン数6イジングコンピュータを使いこなすには？

Hitachi × Hokkaido Univ.

イジングコンピュータで最適化問題を解くには最適化問題（巡回セールスマン問題）をイジングスピンの基底状態探索問題に変換する方法の一例

イジングコンピュータを使いこなすには、従来のプログラミングに相当する、最適化問題の定式化、ハード実装可能な相互作用の変換（マッピング）が課題であり、数学の力が必要となります。
これらの課題を解決できれば、イジングコンピュータは最適化問題に対する強力なツールとなり、コンピュータの歴史にイノベーションを起こす可能性を持っています。

例：都市数4の場合の巡回セールスマン問題

入力：最適化問題

2

各都市を1度ずつ、もれなく訪問して最初の都市に戻る場合のD

最短距離は？

D24

D12

評価関数に定式化

新技術を切り開く鍵となる部分

P

巡回セールスマン問題
エネルギー関数（評価関数）

2

P

N

n=1

i=1

n=1

従来のプログラミングに相当

N N NNN

i=1 j=1 k=1

k=1

i=1

距離の項

エネルギー関数

最適解へ

2

N

N

i=1

k=1

2

制約条件を与える項

Dij:： 都市iから都市jまでの距離［ただし、都市間の距離は対称（Dij=Dji）とする］
σik ： 1 or 0（k番目に都市iに訪問するときσik=1、k番目に都市iを訪問しないときσik=0）● N ： 都市の総数、σj,N+1=σj,1（ j=1, …, N）とする（すべての都市訪問後は最初の都市に戻る）● γ ： 制約条件の強さに対応するパラメータ●

最適解へ

2番目に都市4と都市1が同時に選ばれない（制約1）

青色の相互作用は距離の項、赤色の相互作用は制約条件を表し、訪問する都市を上向きで表現しています。
マッピング後、アニーリングにより、最短距離が求められます。

アニーリングで求めた最短距離：

D14＋D42＋D23＋D31

k=1

k=2

k=3

k=4

σ1,1

σ1,2

σ1,3σ1,4

順番▶
都市
▼

i=1
i=2

スピン観測

従来の計算機を置き換える部分

制約2：すべての都市を必ず1度は訪れる●

イジングコンピュータ

スピンの状態i=1

制約1： k番目にどれか、一つの都市にいる（できる限り短く）

基底状態探索（アニーリング）N

H(σ)=ΣΣΣ Dij σik σj,k+1 +γ［Σ(1-Σσik ) +Σ(1-Σσik ) ］

イジングコンピュータにマッピング

基底状態
(最適解)

2H(σ,y)=γ［(1-Σyn ) +(Σ nyn -Σ wiσi ) ］-Σ hiσi
都市間の距離Dij をエネルギーとして加算

物理現象（イジングコンピュータ）にマッピング

4D14

社会環境

北大の学生と一緒に開発したい！

D34

D13

1

最適化問題抽出（評価関数に定式化）

3

D23

σ2,1

D14

σ2,2i=3σ3,1σ3,2i=4σ4,1σ4,2σ2,3D42

σ3,3σ2,4
D23

σ4,3

都市1へ

D31

σ3,4σ4,4

2番目に訪問した都市4は3番目に選ばれない
（制約2）

78

イジングコンピュータで社会課題を解決しよう
最適化問題を見つけてイジングコンピュータで解いてみよう
交通渋滞の解消、物流・除雪コストの最小化など、日常のありとあらゆる場面で、リアルタイムで最適化する必要性が高まっている課題があり、イジングコンピュータはこれらの課題を解く有効な手段の一つです。
例えば、2015年の札幌市の除雪対策費は年間約150億円※であり、そのうち車道除雪、排雪費は約40％を占めています。

株式会社 日立製作所 研究開発グループ
基礎研究センタ 日立北大ラボ〒001-0021 北海道札幌市北区北21条西11丁目
北海道大学フード＆メディカルイノベーション国際拠点213

最適化により、除雪・排雪コストを20％削減することで、札幌市だけで年間12億円の経済効果が期待できます。
日立北大ラボは、複雑化する社会環境に内在する最適化問題をイジングコンピュータで解決するためのアイデアを募集しています。
また、応募いただいたアイデアは、応募者に帰属しますが、今後の弊社の研究・事業において自由に利用・公開されます。秘密情報・個人情報の開示はお控えください。
イジングコンピュータに興味を持ってくれた皆さん、日立北大ラボに加わり、ぜひわれわれと一緒に開発しませんか？

?

至麻生

地下鉄南北線
北24条駅

フード＆メディカル
イノベーション国際拠点

中央バス
北21条西15丁目

北20条東門

循環バス
創成科学研究棟前※一般車両は通行できません。

エルムトンネル※出典元：札幌市ホームページ 雪対策実績 平成28年度の予算より http://www.city.sapporo.jp/kensetsu/yuki/jigyou/budget.html

地下鉄南北線
北18条駅

環状門

社会環境の最適化問題を具体的に考えてみよう

問題

北13条門

●交通網・物流・除雪に関して、最適化すべき制御対象を挙げなさい。

至小樽

交通網
交通渋滞の解消

物流
物流コストの最小化

至千歳

JR函館本線

経路の移動コスト

JR札幌駅

札沼線(学園都市線)

ビック
カメラ

至すすきの？

徒歩
循環バスルート

北海道大学 電子科学研究所 附属
社会創造数学研究センター
実験数理研究分野（山岡研究室）

降雪量
交通状況

〒060-0811 北海道札幌市北区北12条西7丁目

旧西武
札幌

札幌
東急

中央バス
札幌駅前(旧札幌西武前)

北海道大学中央キャンパス
工学部前

北海道大学中央キャンパス 総合研究棟2号館5階104●答えは10ページ

北海道大学病院(歯科医療センター)
イチョウ並木海外から注目！日立のイジングコンピュータ

入口

薬学部

北13条門

セブンイレブン
北半導体のオリンピックといわれる国際会議ISSCC2015で、CMOSイジングコンピュータを発表し、数多くのメディアに取り上げられました。日立は、イジングコンピュータ計算機実用化に向けた研究開発を推進しており、現在、国内外から大きな注目を集めています。

地下鉄南北線

交通状況
各車の行き先北海道大学正門

除雪コストの最小化

目的

入力

JR桑園駅

除雪

地下鉄南北線
北12条駅

循環バス
事務局前

●上記以外の社会環境に内在する最適化問題を挙げなさい。

条駅

12総合研究棟2号館
5階104 山岡研究室

連絡先
担当：竹本 享史
田中 咲

msc_hitachi@es.hokudai.ac.jp

2015年2月24日（火）▲日経産業新聞（8面）

9●答え
菓子選択問題 ： チョコ、ガム、ポテトチップス（満足度21点、総額300円）
社会環境の中の最適化問題 ： 制御対象は、信号・車の動き（交通網）、移動経路（物流）、除雪機・信号の動作（除雪）など◀2015年2月24日（火）日本経済新聞（16面）

10