狠狠撸

Gibbs cloner を用いた組み合わせ最適化と
cross-entropy を用いた期待値推計: 道路ネット
ワーク強靭化のための耐震化戦略を例として
長江剛志 a ?武井伸生 b
a 東北大学大学院工学研究科技術社会システム専攻
(nagae@tohoku.ac.jp)
b 東北大学大学院工学研究科技術社会システム専攻 2015 年度修了生
2016 年 7 月 16 日 (土)
道路の信頼性アドバンスセミナー @ 近江町交流プラザ
(ver1.0.1)
1 / 71

Outline
はじめに
モデル
例題
稀少確率推計問題と重点サンプリング
Cross entropy 法を用いた期待交通不便益推計
Gibbs cloner 法を用いた組み合わせ最適化
ネットワーク耐震化問題への適用結果
まとめと今後の課題
参考文献
2 / 71

大地震による広域道路網の機能障害
阪神淡路 (1995): 阪神高速神戸線倒壊をはじめ, 道路 7245 ヶ
所, 橋梁 330 ヶ所が被災
十勝沖 (2003): 高速自動車国道，国道及び県道等累計 68 か所
で通行規制
中越 (2004): 関越自動車道や国道 17 号，県管理道路等で多数
の通行止め
中越沖 (2007): 北陸自動車道，国道 8 号，県管理道路等 43 区
間で通行規制
能登半島 (2007): 能登道路，能越自動車道，県管理道路等 29
区間通行規制
岩手?宮城内陸 (2008): 県管理道路等 22 区間で通行規制
静岡沖 (2009): 東名高速の一部崩壊，通行止め
東日本大震災 (2011): 東北自動車道，国道 45 号，国道 6 号が
寸断
3 / 71

莫大な経済損失
迂回交通による混雑悪化
(=交通量×追加所要時間×時間単価)
静岡沖 (2008) では 8/11?15 の 5 日間で 21 億円の損失 (中日本高
速道路, 2008)
ネットワーク容量低下や経路途絶 (孤立化) によるトリップ機会の
損失
(=旅行できなかった利用者数×旅行していれば得られた便益)
中越 (2004) では 7 市町村で 61 の集落が孤立 (内閣府, 2005)
全国で孤立可能性のある集落は 17,000 にのぼる (内閣府, 2010)
長江ら [1] の試算:渋滞損失+機会損失は復旧費用の約 10 倍!!
4 / 71

防災基本計画 (2012) における道路災害対策
第 2 編「地震災害対策編」第 1 章「災害予防」第 2 節「地震に強い国づく
り，まちづくり」
国，公共機関及び地方公共団体は，主要な鉄道，道路，港湾，空港，通信局舎等の基幹的な交通?通
信施設等については，各施設等の耐震化や国土ミッシングリンクの解消等のネットワークの充実，
施設?機能の代替性の確保，各交通?通信施設の間の連携の強化等により，大規模災害発生時の輸
送?通信手段の確保に努めるものとする．
第 10 編「道路災害対策編」第 1 章「災害予防」第 2 節「道路施設等の整備」
道路管理者は，道路施設等の点検を通じ，道路施設等の現況の把握に努めるものとする．
道路管理者は道路における災害を予防するため，必要な施設の整備を図るものとする．
道路管理者は，道路施設等の安全を確保するため，必要な体制等の整備に努めるものとする．
道路管理者は，道路防災対策事業等を通じ，安全性?信頼性の高い道路ネットワーク整備を計画的
かつ総合的に実施するものとする．
国及び地方公共団体は，主要な交通施設の被災による広域的な経済活動，国民生活への支障や地域の
孤立化の防止等のため，主要な交通網が集中している地域の土砂災害対策や海岸保全対策を重点的
に実施するものとする．
具体的な意思決定のための定量的分析手法必要不可欠.
5 / 71

道路ネットワーク耐震化問題
道路施設を耐震化することで社会的不便益は減少させられる
全ての道路施設を一様に耐震化することは非効率
米田 [2] らの試算：RC 橋脚の耐震化 6,000 万円/橋
大きな地震外力を受けにくい施設や滅多に利用されない道路は
耐震化しなくてもよい？
耐震化によって軽減される社会的不便益と耐震化にかかる費用との
バランスが大事
耐震化戦略：どの施設を耐震化し，どの施設を現状のまま残
すか？
費用対効果が最も高い耐震化戦略は？
6 / 71

既存研究 (1)
道路ネットワークの信頼性
Bell and Cassir[3], Bell and Iida[4]
信頼性の指標
連結信頼性: Iida and Wakabayashi[5]
時間信頼性: Asakura et al.[6]
容量信頼性: Lo and Tung[7; 8], Yang et al.[9], Chen et al.[10]
Uni?ed Network Performance Measure: Nagurney and Qiang[11]
7 / 71

既存研究 (2)
ネットワークの脆弱性
Critical Infrastructure: Taylor and D’Este[12]
Link importance and site exposure: Jenelius et al. [13]
Degradable network: Nicholson and Du [14]
Link-level vulnerability: Knoop et al. [15]
Road network vulnerability: Jenelius and Mattsson [16]
信頼性を考慮したネットワーク設計問題
感度分析: Yang [17], [18]
最適リンク投資問題: Asakura et al. [19]
8 / 71

既存研究 (3)
道路ネットワークの耐震化の便益評価と最適化
長江ら [1], Nagae et al.[20]
耐震化問題を数理計画問題として分析する枠組を提案
理解し易さ?実装し易さと再現可能性を目的とした解法を開発
得られた戦略の最適性 (better solution かどうかすら) が保証され
ない
提案手法が任意のネットワークに対して有効か否かも未検証
Du and Peeta [21]
Nagae et al. [20] と同様の問題を確率的最適化問題として定式化
目的関数 (事後対応に要する時間の期待値 ) を MCMC で推計し
ながら最適化→ 期待値を過少推計する可能性 (後述)
各リンクの耐震化の度合いが連続変数→ 実際の耐震化の意思決
定は「いくつかの設計基準の中から 1 つ選択」になる (はず)
「2 つの耐震化基準 A, B を (例えば 3:7 で) ミックスした橋梁」が
自在に設計?施工でき, 「投資金額に対する限界損壊確率」が連
続的に評価できるなら連続変数でもよい.
9 / 71

既存研究 (4)
災害時の交通ネットワーク信頼性
先行研究扱う話題　災害規模複数リンク途絶最適化
Nicholson and Du (1997) [14] 脆弱性 -
Taylor and D’Este (2004) [12] 脆弱性 -
Jenelius et al. (2006) [13] 重要性と暴露小
Chen et al. (2012) [10] リンク重要性 -
Knoop et al. (2012) [15] 脆弱性の指標 -
Jenelius and Mattsson (2012) [16] 重要性と暴露小
Du and Peeta (2014) [21] 耐震化戦略大
Nagae et al. (2012) [20] 耐震化戦略大
10 / 71

やりたいこと
Nagae et al.[20] のモデルに対して，以下の性質を満足する手法を
開発する
(極限において) 大域的最適解への収束が見込まれる
任意の規模のネットワークに対して, 現実的な計算時間内に
ad-hoc に決めたものよりマシな耐震化戦略が具体的に求め
られる
具体的な目的は後述
11 / 71

Outline
はじめに
モデル
例題
参考文献
12 / 71

モデルの枠組
道路ネットワーク上の各リンクに脆弱な交通施設が存在
する．
A: リンク集合
B: 交通施設集合
地震災害によって，各リンクは二つの状態のうちどちらか一
つの状態になる：
通行可能 (ya = 0) か不可能 (ya = 1)．
y = {ya : a ∈ A}: 被災パターン
Y: 被災パターン集合
交通施設の耐震性能を次の二つで表現する：
耐震化されない (xb = 0) か，耐震化される (xb = 1)．
x = {xb : b ∈ B}: 耐震化戦略
X: 耐震化戦略集合
13 / 71

期待交通不便益
ua(x): 戦略 x の下でのリンク a の被災確率
φ(y|x): 戦略 x の下での被災パターン y の条件付生起確率
φ(y|x) =
a∈A
ua(x)ya
(1 ? ua(x))1?ya
τ(y): 被災パターン y の交通不便益
戦略 x の下での期待交通不便益:
T(x) =
y∈Y
φ(y|x)τ(y) (1)
14 / 71

道路ネットワーク耐震化問題
K(x) 耐震化戦略 x の耐震化費用
K(x) =
b∈B
Kbxb
Kb: 施設 b ∈ B の耐震化にかかる費用
耐震化戦略 x の社会的損失:
Z(x) :=
y∈Y
φ(y|x)τ(y)
期待交通不便益 (T(x))
+
b∈B
Kbxb
耐震化費用 (K(x))
道路ネットワーク耐震化問題:
min
x∈X
Z(x)
15 / 71

Outline
はじめに
モデル
例題
参考文献
16 / 71

ネットワーク耐震化問題の例
A: リンク集合
B: 交通施設集合
1 2 3
4 5 6
7 8 9
a
b
c
d e
f
g
h
i j
k l
.16
.79
.29
.80 .05
.67
.11
.26
.26 .49
.69 .84
起点終点 (交通需要)
1 3(50) 4(40) 9(60)
2 8(50)
5 9(100)
min
x∈X
Z(x)
y∈Y
φ(y|x)τ(y)
交通不便益の期待値
+ K(x)
耐震化費用
x = {xb}: 耐震化戦略 (xb = 1 なら耐震化)
y = {ya}: 被災パターン y = 1 なら利用不能)
τ(y): 被災パターン y の下での交通不便益 (=
トリップできない利用者数)
φ(y|x): 戦略 x の下でのパターン y の生起
確率
リンク横の数値は耐震化しない場合の被災確
率．耐震化によって被災確率は半分になる．
耐震化費用はリンク 1 本あたり 10 とする．
いずれのリンクも容量 100 とする．
17 / 71

被災パターンごとの交通不便益
簡単のため，交通配分モデルとして最大流問題を採用する．ト
リップできなかった利用者数を交通不便益とする．
1 2 3
4 5 6
7 8 9
a
b
c
d e
f
g
h
i j
k l
いずれのリンクも容量 100
起点終点 (交通需要)
1 3(50) 4(40) 9(60)
2 8(50)
5 9(100)
被災パターンごとの交通不便益
pt. ID a b c d e f g h i j k l τ(y)
0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 50
2 0 1 0 0 0 0 0 0 0 0 0 0 50
3 1 1 0 0 0 0 0 0 0 0 0 0 150
4 0 0 1 0 0 0 0 0 0 0 0 0 50
5 1 0 1 0 0 0 0 0 0 0 0 0 50
6 0 1 1 0 0 0 0 0 0 0 0 0 100
7 1 1 1 0 0 0 0 0 0 0 0 0 150
8 0 0 0 1 0 0 0 0 0 0 0 0 50
: : : : : : : : : : : : : :
4093 1 0 1 1 1 1 1 1 1 1 1 1 260
4094 0 1 1 1 1 1 1 1 1 1 1 1 300
4095 1 1 1 1 1 1 1 1 1 1 1 1 300
0: 被害なし, 1: 通行不能
18 / 71

交通不便益の期待値 (その 0)
耐震化戦略 x の下での期待交通不便益: T(x) =
y∈Y
φ(y|x)τ(y)
無対策 x0 = (0, 0, · · · , 0) の
場合のリンク被災確率:
1 2 3
4 5 6
7 8 9
a
b
c
d e
f
g
h
i j
k l
.16
.79
.29
.80 .05
.67
.11
.26
.26 .49
.69 .84
リンク耐震化費用:
K(x0) = 0
pt. ID τ(y) φ(y|x0) φ(y|x0)τ(y)
0 0 9.68 (-05) 0.00 (+00)
1 50 1.84 (-05) 9.22 (-04)
2 50 3.64 (-04) 1.82 (-02)
3 150 6.94 (-05) 1.04 (-02)
4 50 3.95 (-05) 1.98 (-03)
5 50 7.53 (-06) 3.77 (-04)
6 100 1.49 (-04) 1.49 (-02)
7 150 2.83 (-05) 4.25 (-03)
: : : :
4092 260 2.90 (-06) 7.53 (-04)
4093 260 5.51 (-07) 1.43 (-04)
4094 300 1.09 (-05) 3.27 (-03)
4095 300 2.07 (-06) 6.22 (-04)
T(x) 204.55
社会的不便益: Z(x0) = T(x0) = 204.55.
19 / 71

リンク a のみを耐震化する
戦略 x1 = (1, 0, · · · , 0) の場
合のリンク被災確率:
1 2 3
4 5 6
7 8 9
a
b
c
d e
f
g
h
i j
k l
.08
.79
.29
.80 .05
.67
.11
.26
.26 .49
.69 .84
K(x1) = 10
0 0 1.06 (-04) 0.00 (+00)
1 50 9.22 (-06) 4.61 (-04)
2 50 3.99 (-04) 1.99 (-02)
3 150 3.47 (-05) 5.20 (-03)
4 50 4.33 (-05) 2.17 (-03)
5 50 3.77 (-06) 1.88 (-04)
6 100 1.63 (-04) 1.63 (-02)
7 150 1.42 (-05) 2.13 (-03)
: : : :
4092 260 3.17 (-06) 8.24 (-04)
4093 260 2.76 (-07) 7.17 (-05)
4094 300 1.19 (-05) 3.58 (-03)
4095 300 1.04 (-06) 3.11 (-04)
T(x) 201.24
社会的不便益:
Z(x1) = T(x1) + K(x1) = 201.24 + 10 = 211.24
20 / 71

リンク a, d, e, g, i を耐震化す
る戦略 x345 =
(1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0)
の場合のリンク被災確率:
1 2 3
4 5 6
7 8 9
a
b
c
d e
f
g
h
i j
k l
.08
.79
.29
.40 .02
.67
.05
.26
.13 .49
.69 .84
K(x345) = 50
0 0 4.12 (-04) 0.00 (+00)
1 50 3.58 (-05) 1.79 (-03)
2 50 1.55 (-03) 7.75 (-02)
3 150 1.35 (-04) 2.02 (-02)
4 50 1.68 (-04) 8.41 (-03)
5 50 1.46 (-05) 7.31 (-04)
6 100 6.33 (-04) 6.33 (-02)
7 150 5.50 (-05) 8.25 (-03)
: : : :
4092 260 1.44 (-07) 3.75 (-05)
4093 260 1.25 (-08) 3.26 (-06)
4094 300 5.42 (-07) 1.63 (-04)
4095 300 4.72 (-08) 1.41 (-05)
T(x) 182.35
社会的不便益: Z(x345) = T(x345) + K(x345) =
182.35 + 50 = 232.35
21 / 71

全てのリンクを耐震化する
戦略 x4095 = (1, 1, · · · , 1) の
場合のリンク被災確率:
1 2 3
4 5 6
7 8 9
a
b
c
d e
f
g
h
i j
k l
.08
.40
.15
.40 .02
.34
.05
.13
.13 .24
.35 .42
K(x4095) = 120
pt. ID τ(y) φ(y|x4095) φ(y|x4095)τ(y)
0 0 3.75 (-02) 0.00 (+00)
1 50 3.26 (-03) 1.63 (-01)
2 50 2.50 (-02) 1.25 (+00)
3 150 2.17 (-03) 3.26 (-01)
4 50 6.62 (-03) 3.31 (-01)
5 50 5.76 (-04) 2.88 (-02)
6 100 4.41 (-03) 4.41 (-01)
7 150 3.84 (-04) 5.76 (-02)
: : : :
4092 260 6.71 (-09) 1.75 (-06)
4093 260 5.84 (-10) 1.52 (-07)
4094 300 4.48 (-09) 1.34 (-06)
4095 300 3.89 (-10) 1.17 (-07)
T(x) 108.80
社会的不便益: Z(x4095) =
T(x4095) + K(x4095) = 108.80 + 120 = 228.80
22 / 71

最適耐震化戦略
1 2 3
4 5 6
7 8 9
a
b
c
d e
f
g
h
i j
k l
st. ID a b c d e f g h i j k l T(x) K(x) Z(x)
0 0 0 0 0 0 0 0 0 0 0 0 0 204.55 0.00 204.55
1 1 0 0 0 0 0 0 0 0 0 0 0 201.24 10.00 211.24
2 0 1 0 0 0 0 0 0 0 0 0 0 188.38 10.00 198.38
3 1 1 0 0 0 0 0 0 0 0 0 0 185.09 20.00 205.09
: : : : : : : : : : : : : : : :
2569 1 0 0 1 0 0 0 0 0 1 0 1 150.39 40.00 190.39
2570 0 1 0 1 0 0 0 0 0 1 0 1 136.53 40.00 176.53
2571 1 1 0 1 0 0 0 0 0 1 0 1 132.61 50.00 182.61
2572 0 0 1 1 0 0 0 0 0 1 0 1 147.06 40.00 187.06
: : : : : : : : : : : : : : : :
4093 1 0 1 1 1 1 1 1 1 1 1 1 128.17 110.00 238.17
4094 0 1 1 1 1 1 1 1 1 1 1 1 113.09 110.00 223.09
4095 1 1 1 1 1 1 1 1 1 1 1 1 108.80 120.00 228.80
23 / 71

最適耐震化戦略
1 2 3
4 5 6
7 8 9
a
b
c
d e
f
g
h
i j
k l
リ
ンク {b, d, j, l} のみを重点的
に耐震化することで社会的
不便益を最小化できる
st. ID a b c d e f g h i j k l T(x) K(x) Z(x)
0 0 0 0 0 0 0 0 0 0 0 0 0 204.55 0.00 204.55
1 1 0 0 0 0 0 0 0 0 0 0 0 201.24 10.00 211.24
2 0 1 0 0 0 0 0 0 0 0 0 0 188.38 10.00 198.38
3 1 1 0 0 0 0 0 0 0 0 0 0 185.09 20.00 205.09
: : : : : : : : : : : : : : : :
2569 1 0 0 1 0 0 0 0 0 1 0 1 150.39 40.00 190.39
2570 0 1 0 1 0 0 0 0 0 1 0 1 136.53 40.00 176.53
2571 1 1 0 1 0 0 0 0 0 1 0 1 132.61 50.00 182.61
2572 0 0 1 1 0 0 0 0 0 1 0 1 147.06 40.00 187.06
: : : : : : : : : : : : : : : :
4093 1 0 1 1 1 1 1 1 1 1 1 1 128.17 110.00 238.17
4094 0 1 1 1 1 1 1 1 1 1 1 1 113.09 110.00 223.09
4095 1 1 1 1 1 1 1 1 1 1 1 1 108.80 120.00 228.80
23 / 71

数え上げの恐怖
ネットワークの規模が少しでも大きくなると，被災パターンや戦
略の数え上げは不可能．
ネットワークリンク数被災パターン数/戦略数
3 × 3 格子 12 4, 096
4 × 4 格子 24 16, 777, 216
5 × 5 格子 40 1, 099, 511, 627, 776
Sioux-Falls 76 7.56 × 1022
12 × 12 格子 264 2.96 × 1079
c.f.)
観測可能な宇宙の星の数：3 × 1022 ～ 7 × 1022
観測可能な宇宙内の原子の数：1080
24 / 71

本研究の目的
ネットワーク耐震化問題 (厳密な定式化は Nagae et al.[20]) に固有
の 2 種類の組み合わせ爆発に対応した効率的計算手法を開発
する:
被災パターンが膨大なため，目的関数の厳密な評価が困難
→ 目的関数を推定するために Cross-entropy 法 (CE) 法を用いた重点
サンプリング
非凸組み合わせ最適化問題で戦略集合が膨大なため，大域的最適解
を見つけることが困難
→ Gibbs cloner (GC) 法を用いた組合せ最適化
25 / 71

Outline
はじめに
モデル
例題
参考文献
26 / 71

稀少確率推計問題
CE 法 / GC 法では, 期待値推計問題や組み合わせ最適化問題を稀
少確率推計問題に帰着させて解く. 事象集合 Z 上の確率密度
f : Z → [0, 1] と何らかの評価関数 S : Z → R が与えられた時, 評
価関数が γ 以上となる確率は以下の式で表される.
= Pr.f
I z:S(z)≥γ (Z) =
Z∈Z
f(Z)I z:S(z)≥γ (Z)
ここで, IA(Z) は集合 A ? Z に対する標示関数 (indicator
function) で, Z が A に含まれるなら 1, そうでなければ 0 を取る.
以下では簡単のため, 標的事象 {z : S(z) ≥ γ} を {S(Z) ≥ γ} と記載
し, I z:S(z)≥γ (Z) を I S(Z)≥γ と記載する.
が十分に小さい (例えば, < 10?5) とき, {S(Z) ≥ γ} を稀少事象,
を稀少確率と呼ぶ.
27 / 71

期待値推計/組み合わせ最適化と稀少確率推計問題 (1)
期待値推定
耐震化戦略 x を与件とした条件つき期待交通不便益
T(x) =
y∈Y
φ(y|x)τ(y)
を推計する代わりに, 「元の密度から被災パターン Y を抽出した時
に期待値への貢献度 E(Y) = φ(Y|x)τ(Y) が γ 以上となる確率」
=
Y∈Y
φ(Y)I E(Y)≥γ
を推計する問題を考える.
28 / 71

期待値推計/組み合わせ最適化と稀少確率推計問題 (2)
組み合わせ最適化
耐震化戦略 x に対応する社会的損失 Z(x) = T(x) + K(x) が評価でき
るとして, 組み合わせ最適化問題
min
x∈X
Z(x)
を解く代わりに, 「一様分布から耐震化戦略 X を抽出した時に社会
的損失 Z(X) が γ 以下となる確率」
=
X∈X
?(X)I Z(X)≤γ
を推計する問題を考える. ただし, ?(X) = 1
|X| は X 上の一様分布.
29 / 71

Crude Monte-Carlo 法による稀少確率推計
稀少確率を推計する最もナイーブな方法は, crude Monte-Carlo
(CMC) 法: 元の密度 f(·) から N 個の標本 Z1, · · · , ZN を抽出し,
?=
1
N
N
n=1
I S(Zn)≥γ , Zn ～ f(·)
を不偏推定量とする.
しかし, {S(Z) ≥ γ} が稀少事象の場合, を精度よく推定するため
には膨大な標本が必要となる.
30 / 71

重点サンプリング
この問題点を克服する手法の 1 つが重点サンプリング: 元の密度
f(·) とは異なる別のサンプリング密度 g : Z → [0, 1] から N 個の
標本 Z1, · · · , ZN を抽出し,
?=
1
N
N
n=1
I S(Zn)≥γ W(Zn), Zn ～ g(·)
を尤度比推定量 (likelihood ratio (LR) estimator) とする. ただし,
W(Z) =
f(Z)
g(Z)
は尤度比 (LR:likelihood ratio) と呼ばれる.
どのようにサンプリング密度 g を選べばよいのか？
31 / 71

理想的なサンプリング密度
標的事象 {S(Z) ≥ γ} が確率 1 で生成されるような密度:
g?
(Z, γ) =
I S(Z)≥γ f(Z)
=
?
???
???
1 if S(Z) ≥ γ
0 otherwise
を用いれば, たった 1 つの標本で誤差ゼロでを推定できる.
そんな密度が最初から判れば世話はない.
32 / 71

多段階アルゴリズム (multi-level algorithm)
目標レベルに徐々に近づくようなレベルの順列
γ(1)
≤ γ(2)
≤ · · · ≤ γ(T)
～ γ
を考え, 各 γ(t) に対応するサンプリング密度 g(t) = g?(Z; γ(t)) の
列 g(1), g(2), · · · , g(T) が g?(Z; γ) に漸近するような手続きを構成.
その基本構造は以下の通り.
Step 0 初期密度 g(0) を与え (e.g. g(0) = f), t = 1 とする.
Step 1 既知のサンプリング密度 g(t?1) から N 個の標本
Z1, · · · , ZN を抽出する. 各標本について
S(Z1), S(Z2), · · · , S(ZN) を計算する. 上位 M(< N)
個をエリート標本 Z?
1, · · · , Z?
M とし, 閾値となるレ
ベルを γ(t) とする.
Step 2 エリート標本 Z?
1, · · · , Z?
M を用いて新たなサンプリ
ング密度 g(t) = g?(Z; γ(t)) を求める.
Step 3 収束条件を満足すれば終了．そうでなければ
t = t + 1 として Step 1 へ.
33 / 71

CE 法と GC 法の特徴 (1)
Cross entropy (CE) 法
元の分布とサンプリング密度を, それぞれ, 同じ族のパラメト
リックな密度関数 f(Y; u), f(Y; v) で表し, 各繰返しにおいてサ
ンプリング密度 g(t) を求める問題を, サンプリング?パラメータ
v(t) を求める問題に帰着
理想的な密度とサンプリング密度との「距離」を cross entropy
で評価し, それを最小とするサンプリング?パラメータを非線
形最適化問題の解として特徴づける
非線形最適化問題が解析解を持つことを利用してサンプリン
グ?パラメータの簡潔な改訂ルールを導出
34 / 71

CE 法と GC 法の特徴 (2)
Gibbs cloner (GC) 法
各繰返しにおいてサンプリング密度 g(t) (やそれに対応するパラ
メータ) を明示的に取り扱わない
エリート標本の複製 (cloning) と MCMC (Markov chain
Monte-Carlo) の手法である Gibbs サンプラーを活用することで,
サンプリング密度 g(t) に従う標本を効率的に生成
35 / 71

Outline
はじめに
モデル
例題
参考文献
36 / 71

対応する稀少確率推計問題 (再掲)
耐震化戦略 x を与件とした条件つき期待交通不便益
T(x) =
y∈Y
φ(y|x)τ(y)
を推計する代わりに, 「元の密度 f(·; u) = φ(Y|x) から被災パ
ターン Y を抽出した時に期待値への貢献度 E(Y) = φ(Y|x)τ(Y) が
γ 以上となる確率」
=
Y∈Y
f(Y; u)I E(Y)≥γ
を推計する問題を考える.
37 / 71

Cross entropy による「理想的密度」との距離 (1)
期待値への貢献度 E(y) が γ 以上となる被災パターン y が確率 1
で生成される理想的な密度:
g?
(Y) =
I E(Y)≥γ φ(Y)
と (パラメトリックに表現された) サンプリング密度
fv(Y) = f(Y; v) との乖離を cross entropy (Kullbuck-Leibler
divergence / 相対エントロピー) で評価する:
D(g?
, fv) =
Y∈Y
g?
(Y) ln
g?(Y)
fv(Y)
=
Y∈Y
g?
(Y) ln g?
(Y) ?
Y∈Y
g?
(Y) ln fv(Y)
38 / 71

最適サンプリング?パラメータ (1)
理想的な密度 g?(Y) = I E(Y)≥γ f(Y; u) との cross entropy
D(g?, fv) を最小とするパラメータは
v?
= arg min
v
D(g?
, fv) =
Y∈Y
g?
(Y) ln g?
(Y) ?
Y∈Y
g?
(Y) ln fv(Y)
? arg max
v
Y∈Y
g?
(Y) ln f(Y; v) (g?
ln g?
の項は v と独立なので)
? arg max
v
Y∈Y
I E(Y)≥γ f(Y; u) ln f(Y; v) (g?
を代入)
の解として与えられる.
ただし, この問題は目的関数の厳密な評価に Y の列挙が必要な
ため，実用上は解けない. そこで, 以下の 2 つの工夫を行なう.
39 / 71

最適サンプリング?パラメータ (2)
1. 元の分布 f(·; u) から抽出された N 個の標本 Y1, · · · , YN を用
いた stochastic counterpart の解:
?v = arg max
v
1
N
N
n=1
I E(Yn)≥γ ln f(Yn; v) Yn ～ f(·; u)
を最適パラメータの推定量とする.
2. 元の分布 f(·; u) から標的事象が抽出されることは極めて稀
なため, 既知のサンプリング密度 f(·; w) を用いた重点サン
プリングによって目的関数を書き直す:
?v = arg max
v
1
N
N
n=1
I E(Yn)≥γ W(Yn; u, w) ln f(Yn; v) Yn ～ f(·; w)
ここで, W(Y; u, w) = f(Y; u)/ f(Y; w) は尤度比.
40 / 71

多段階アルゴリズム
一般に, 標的事象 {E(Y) ≥ γ} を十分に抽出できるようなサンプリ
ング?パラメータ w を予め求めておくことは不可能なので, 多段
階アルゴリズム (multi-level algorithm) を用いてレベルとサンプ
リング?パラメータの列を順次生成する.
具体的には, t 回目の繰返しにおいて, サンプリング?パラメータ
w に直前の繰返しで求められた v(t?1) を用い，目標レベル γ を
(それより小さい) レベル γ(t) に置き換えた問題:
max
v
1
N
N
n=1
I E(Yn)≥γ(t) W(Yn; u, v(t?1)
) ln f(Yn; v) Yn ～ f(·; v(t?1)
)
を解いて, 新たなサンプリング?パラメータ v(t) を求める. γ(t) や
v(t) の決定には, エリート標本の考え方を利用する.
41 / 71

レベル γ(t)
の決定方法
直前のサンプリング密度 f(·; v(t?1)) から N 個の標本 Y1, · · · , YN
を抽出する. それぞれの標本について, 期待値への貢献度
E(Y1), · · · , E(YN) を求め, 大きい方から順に
E(1) ≥ E(2) ≥ · · · ≥ E(N)
と並べ替える. そして, レベルとして上位から ρN 番目の値を採
用する:
γ(t)
= E( ρN )
ここで, ρ は極度に小さすぎないパラメータ (e.g. ρ = 0.01). これ
により, 抽出された N 個の標本 Y1, · · · , YN ～ f(·; v(t?1)) のうち,
少なくとも ρN 個は E(Yn) ≥ γ(t) を満たすことが保証される．
これらの標本:
Y?(t)
= {Yn : E(Yn) ≥ γ(t)
}
をエリート標本と呼び, その要素数を M(t) で表す.
42 / 71

サンプリング?パラメータ v(t)
の決定方法 (1)
レベル γ(t) の決定に用いたのと同じ標本 Y1, · · · , YN を用いるこ
とにすれば, サンプリング?パラメータ決定問題:
max
v
1
N
N
n=1
I E(Yn)≥γ(t) W(Yn; u, v(t?1)
) ln f(Yn; v)
の目的関数は, エリート標本 Y?(t) を用いて,
max
v
1
N
Yn∈Y?(t)
W(Yn; u, v(t?1)
) ln f(Yn; v)
と書き直せる. エリート標本は少なくとも ρN 個存在すること
が保証されるから, 「標本が少な過ぎて目的関数が評価できない」
という問題は回避できる.
43 / 71

の決定方法 (2)
さらに, ln f(Y; v) が v について凹かつ連続微分可能ならば, 最適
パラメータの推定量 ?v は非線形連立方程式:
Yn∈Y?(t)
W(Yn; u, v(t?1)
) v ln f(Yn; v) = 0
を解いて求められる. 特に, f(Y; v) が自然指数族 (natural
exponential family) ならば, この非線形方程式が解析解
(closed-form solution) を持つことが知られている [22].
例えば, ネットワーク耐震化問題では被災パターン生起確率 (ひい
てはサンプリング密度) として多変数 Bernoulli 分布:
f(Y; v) =
a∈A
v
ya
a (1 ? va)1?ya
44 / 71

の決定方法 (3)
を採用するため, パラメータの推定量が以下の簡潔な式で求めら
れる:
v
(t)
a =
Yn∈Y?(t) W(Yn; u, v(t?1))Yn,a
Yn∈Y?(t) W(Yn; u, v(t?1))
.
この式の分子および分母は, それぞれ,
分子: エリート標本の中でリンク a が被災しているものの
尤度比 Wu,w(t?1) (·) の和
Yn∈Y?(t)
W(Yn; u, v(t?1)
)Yn,a
分母: エリート標本の尤度比の和
Yn∈Y?(t)
W(Yn; u, v(t?1)
)
であるから, 極めて容易に計算できる.
45 / 71

CE 法による期待交通不便益推定 (1)
1. 耐震化戦略 x の下でのリンクの損傷確率 u = {ua(x)} を初期
パラメータ v(0) = u とし, 繰り返しカウンタを t = 1 とする．
2. サンプリング密度 f(·; v(t?1)) から N 個の標本被災パターン
Y1, · · · , YN を抽出し, (元の密度 f(·; u) で測った) 期待値への
貢献度 E(Yn) = f(Yn; u)τ(Yn) の大きい方から M 番目の値
を γ(t) とする. エリート標本を Y?(t) = {Yn : E(Yn) ≥ γ(t)} と
する.
3. サンプリング?パラメータを以下の式で改訂する.
v
(t)
a =
Yn∈Y?(t) W(Yn; u, v(t?1))Yn,a
Yn∈Y?(t) W(Yn; u, v(t?1))
.
46 / 71

CE 法による期待交通不便益推定 (2)
4. 適当な t ≥ d (eg. d = 5) について
γ(t)
= γ(t?1)
= · · · = γ(t?d)
ならば終了する (最後の反復を T とする)；そうでなければ，
t = t + 1 として 2 に戻る.
こうして得られた参照パラメータ v(T) の下で, 適当な数 (例えば
K 個) の被災標本パターン Y1, · · · , YK を抽出し, 以下を期待交通
不便益の LR 推定量とする:
?T(x) =
1
K
K
k=1
τ(Yk)W(Yk; u, v(T)
), Yn ～ f(·, v(T)
)
47 / 71

Outline
はじめに
モデル
例題
参考文献
48 / 71

対応する稀少確率推計問題 (再掲)
耐震化戦略 x に対応する社会的損失 Z(x) = T(x) + K(x) が評価で
きるとして, 組み合わせ最適化問題
min
x∈X
Z(x)
を解く代わりに, 「一様分布から耐震化戦略 X を抽出した時に
社会的損失 Z(X) が γ 以下となる確率」
=
X∈X
?(X)I Z(X)≤γ
を推計する問題を考える. ただし, ?(X) = 1
|X| は X 上の一様分布.
49 / 71

Gibbs cloner 法の基本構造
CE 法と同様に,
γ(1)
≥ γ(2)
≥ · · · γ(T)
と次第に小さくなるようなレベルの列と, それに対応したサンプ
リング密度の列
g?
(·; γ(1)
), g?
(·; γ(2)
), · · · , g?
(·; γ(T)
)
を生成. ここで, g?(·; γ) は「社会的損失 Z(X) が γ 以下となるよう
な耐震化戦略 x を確率 1 で生成する密度」:
g?
(X; γ) =
?
???
???
1 if Z(X) ≤ γ
0 otherwise
g?(·; γ) の関数形を特定化しないので，サンプリングに工夫が必要.
50 / 71

Gibbs サンプラーによる MCMC (1)
サンプリング密度 g(X) から直接標本を取り出すことが困難な場
合によく使われるのが，MCMC (Markov chain Monte-Carlo) 法:
定常分布が g(X) となるような Markov 連鎖を構成するように標
本 X1, X2, · · · を順に生成する.
その具体的な方法の 1 つとして, 最もよく知られるのが Gibbs サ
ンプラー:
n 番目の標本 Xn = (Xn,1, · · · , Xn,B) が与えられた時,
n + 1 番目の標本の各要素 Xn+1,1, · · · , Xn+1,B を以下の
ように順に生成:
1. Xn+1,1 を g(X1|Xn,2, Xn,3, · · · , Xn,B) から生成
2. Xn+1,2 を g(X2|Xn+1,1, Xn,3, · · · , Xn,B) から生成
3. Xn+1,3 を g(X3|Xn+1,1, Xn+1,2, Xn,4, · · · , Xn,B) から
生成
以下，同様にして, Xn+1,4, · · · , Xn+1,B を生成
51 / 71

Gibbs サンプラーを用いて g?(X; γ) に従う標本戦略 X1, · · · , XN
を抽出するための具体的な手続きは，以下のように整理できる.
1. Z(X0) ≤ γ なる初期標本 X0 = X を探し, n = 1 とする.
2. n 番目の標本戦略を以下の手続きで生成する:
2.1 二項分布に従う乱数 χ1 ～ Ber 1
2 を発生させ,
Z(χ1, Xn?1,2, Xn?1,3, · · · , Xn?1,B) ≤ γ なら Xn,1 = χ1, そうでな
ければ Xn,1 = Xn?1,1 とする.
2.2 χ2 ∈ Ber 1
2 を発生させ, Z(Xn+1,1, χ2, Xn?1,3, · · · , Xn?1,B) ≤ γ
なら Xn,2 = χ2, そうでなければ Xn,2 = Xn?1,2 とする.
2.3 χ3 ∈ Ber 1
2 を発生させ,
Z(Xn+1,1, Xn+1,2, χ3, Xn?1,4, · · · , Xn?1,B) ≤ γ なら Xn,3 = χ3,
そうでなければ Xn,3 = Xn?1,3 とする.
2.4 以下，同様に Xn,3, · · · , Xn,B を決定する.
3. n = N ならば終了. そうでないなら n = n + 1 として 2. へ
戻る.
52 / 71

上述の手続きによって生成された標本 X1, · · · , XN のうち, 最初の
方に生成されたもの (i.e. n が小さいもの) は, 初期標本 X0 の周辺
に偏在する. そのため, 通常は, 最初の K 個を稼働検査 (burn-in)
期間として棄てた後に, 改めて N 個の標本を生成する.
このため, Gibbs サンプラーを組み合わせ最適化の多段階アルゴ
リズムにそのまま適用するには，以下の問題点が残る:
X1, · · · , XN が g?(X; γ) に従うことを保証するためには
burn-in 期間 K を十分に大きく取る必要がある
γ(t) を改訂するたびに, 初期標本 X0 から新たに MCMC を行
なう必要がある (t ? 1 回目までに求めた標本が活用できない).
53 / 71

Bootstrap による Gibbs サンプラーの改良 [24] (1)
t 回目繰返しにおいて, g?(·; γ(t?1)) に従う標本
X(t?1) = {X
(t?1)
1 , · · · , X
(t?1)
M
} が得られているなら, それを使わない
手は無い→ bootstrap したものを初期状態として複数の Gibb サ
ンプラーを並走させる.
Bootstrap 法 [23]
事象集合 X 上の確率分布 f(X) の性質を知るための方法の 1 つ. f(X)
に従うことが判っている標本 (データ) x1, · · · , xN ～ f(x) が与えられ
ているとする. この標本に対して B N 回の復元抽出を行なって得
られる標本
x1, · · · , xB
の統計量 (比率, 平均, 分散など) を用いて元の分布 f(X) の性質を調
べる.
54 / 71

Botev and Kroese[24] のアルゴリズム
1. 予め γ(0) ≥ γ(1) ≥ γ(2) ≥ · · · ≥ γ(T) と, g?(X; γ(0)) に従う N 個の
エリート標本 X?(0) = {X
(0)
1 , · · · , X
(0)
N
} を生成しておく. t = 1 と
する.
2. t ? 1 回目のエリート標本 X?(t?1) から復元抽出によって N 個の
初期標本 ˇX1, · · · , ˇXN を生成する.
3. n = 1, · · · , N のそれぞれについて, ˇXn を初期標本とした Gibbs
サンプラーを行ない, g?(X; γ(t?1)) に従う標本 Xn を生成する.
4. X1, · · · , XN の中から Z(Xn) ≤ γ(t) を満たす標本をエリート標本
とし, その集合を X?(t) = {Xn : Z(Xn) ≤ γ(t)} とする.
5. t = T なら終了. そうでなければ t = t + 1 として 2. に戻る.
55 / 71

Botev and Kroese[24] の問題点
レベルの列 γ(0) ≥ γ(1) ≥ γ(2) ≥ · · · ≥ γ(T) を予め与えないとい
けない→ 最適値のアタリがついていないと厳しい ({γ(t)} を求め
るための pilot-run の手法が提案されてはいる [24])
MCMC ステップ 3. において, 例えば, N 個の初期標本のそれぞ
れから r 回 Gibbs サンプラーを行なった場合, 最初の (r ? 1)N
個の標本を burn-in として棄ててしまう→ 棄てた中に社会的損
失が γ(t) 以下となるものがあるかもしれない.
56 / 71

Gibbs cloner (Rubinstein [25]) (1)
Botev and Kroese [24] アルゴリズムをさらに改良
CE 法と同様に γ(1), γ(2), · · · を adaptive に改訂
Cloning によって, Gibbs サンプラーにおける burn-in の回
数と bootstrap における復元抽出の回数をうまくバランス
t ? 1 回目の繰返しで選抜されたエリート標本を
X?(t?1)
= X
?(t?1)
1 , · · · , X
?(t?1)
M(t?1)
とする. Gibbs cloner では, t 回目のサンプリングおよび γ(t) の改
訂を, (1 つ前に得られた) エリート標本 X?(t?1) およびレベル
γ(t?1) を用いて行う. その手続きは, 3 つのパラメータ η(t), b(t) お
よび ρ によって以下のように特徴づけられる:
57 / 71

1. X?(t?1) の各要素を η 倍に複製した (i.e. (η(t) ? 1) 個の複製
(clone) にそれ自身を加えた) もの
ˇX(t)
= X
?(t?1)
1 , · · · , X
?(t?1)
1
η(t)
, · · · , X
?(t?1)
M(t?1)
, · · · , X
?(t?1)
M(t?1)
η(t)
,
= η(t)
X?(t?1)
を初期標本とする.
2. M(t?1)η(t) 個の初期標本 ˇX(t) のそれぞれから b(t) 世代分の
Gibbs サンプラーを行ない, g?(X; γ(t?1)) に従う
N(t) = M(t?1)η(t)b(t) 個の標本 X(t) を生成する.
58 / 71

3. 標本 X
(t)
1 , · · · , X
(t)
N(t)
を社会的損失 Z(X
(t)
n ) が小さい方から
順に
Z(1) ≤ Z(2) ≤ · · · ≤ Z(N(t))
と並べ, 上位から ρN(t) 番目の値を γ(t) として採用する:
γ(t)
= Z( ρN )
これにより, 少なくとも ρN(t) 個の Z(X
(t)
n ) ≤ γ(t) を満たす
ことが保証される. これらの標本をエリート標本 X?(t) と
する.
GC 法では, N(t) ～ N かつ, 複製倍数 η(t) と MCMC 世代数 b(t) が
適度にバランスするように, 以下の式を満たす中で同程度の整数
が選ばれる:
η(t)
b(t)
=
N
M(t)
.
59 / 71

GC 法による耐震化戦略の導出 (1)
1. 二項分布 Ber 1
2 に従う N 個の耐震化戦略 X(0) を求める.
N(0) = N, 繰り返しカウンタを t = 1 とする．
2. X(t?1) の各要素について社会的損失を計算し, ρN(t?1) 番目
に小さい社会的損失を γ(t) とする. エリート標本を
X?(t) = {X
(t)
n : Z(X
(t)
n ) ≤ γ(t)} とし, その要素数を M(t) とする.
3. 適当な t ≥ d (eg. d = 5) について
γ(t)
= γ(t?1)
= · · · = γ(t?d)
ならば終了する (最後の反復を T とする).
4. 複製倍数 η(t) および MCMC 世代数 b(t) を決定する.
5. X?(t?1) を η(t) 倍に複製したものを ˇX(t) とする.
6. ˇX(t) の各要素を初期標本とした Gibbs サンプラーにより,
g?(X; γ(t)) に従う標本を b(t) 世代分生成したものを X(t) と
する.
7. t = t + 1 として 2. に戻る.
60 / 71

Outline
はじめに
モデル
例題
参考文献
61 / 71

Outline
はじめに
モデル
例題
参考文献
62 / 71

まとめ (1)
道路ネットワークの耐震化問題に対して
膨大な被災パターンを列挙することなく, ある耐震化戦略の
下での条件付期待値交通不便益を効率的に推定する方法
膨大な耐震化戦略を列挙することなく, 優れた耐震化戦略を
効率的に求める方法
を, 乱択アルゴリズムを活用して開発
いずれの手法も, 対象とする期待値推定問題/組み合わせ最適
化問題を稀少確率推計問題に帰着
1. 与えられたサンプリング密度に従う標本を数多く抽出し, そ
の中からエリート標本を選び出す
2. エリート標本がより多く生成されるようにサンプリング密度
を改訂する
という多段階 (multi-level) アルゴリズムを採用
CE(cross entropy) 法による期待値推定
被災パターンが従う「元の密度」「理想の密度」「サンプリン
グ密度」を同族の密度関数でパラメトリックに表現
63 / 71

まとめ (2)
理想の密度とサンプリング密度との乖離を cross-entropy で
測り, それを最小化するようにパラメタを改訂
遺伝的アルゴリズムに似たシンプルな改訂ルール
期待交通不便益を精度よく効率的に推計
GC(Gibbs cloner) 法による組み合わせ最適化
ノンパラメトリックな密度から耐震化戦略をランダムに生成
Bootstrap 法 (cloning) と MCMC 法 (Gibbs サンプラー) を組み
合わせることで, サンプリング密度を明示的に取り扱うこと
なく, 標本抽出とサンプリング密度の改訂を効率的に行なう
大域的最適解 (やそれに準ずる解) を効率的に導出
64 / 71

今後の課題
方法論的なところ
耐震性能の多レベル化 (e.g. 松，竹，梅)
混雑やトリップ中止を評価できる交通配分 (e.g. 利用者均衡
配分)
並列化 ? 大規模化 (「 N 個の標本から上位 ρN 個を求める」
部分は並列化と相性がよさそう)
実証! 実証! 実証!
「言うてもデカいネットワークになったら動かへんのちゃ
う？」「やってみないと判らないです」の無限ループ
交通不便益の計量に必要
「ネットワーク構造」「OD 交通量」「各リンク上の交通施設」
「トリップできない時の交通不便益」
被災パターン生起確率の計量に必要
各交通施設の「地理座標」「耐震性能ごとの脆弱性と耐震化
費用」
想定される地震シナリオと, 各シナリオにおける地震強度分布
(震央と震央強度が判れば, 各地点の地震強度は経験式から推
定可能 [26])
65 / 71

今後の課題
方法論的なところ
耐震性能の多レベル化 (e.g. 松，竹，梅)
混雑やトリップ中止を評価できる交通配分 (e.g. 利用者均衡
配分)
並列化 ? 大規模化 (「 N 個の標本から上位 ρN 個を求める」
部分は並列化と相性がよさそう)
実証! 実証! 実証!
「言うてもデカいネットワークになったら動かへんのちゃ
う？」「やってみないと判らないです」の無限ループ
交通不便益の計量に必要
「ネットワーク構造」「OD 交通量」「各リンク上の交通施設」
「トリップできない時の交通不便益」
被災パターン生起確率の計量に必要
各交通施設の「地理座標」「耐震性能ごとの脆弱性と耐震化
費用」
想定される地震シナリオと, 各シナリオにおける地震強度分布
(震央と震央強度が判れば, 各地点の地震強度は経験式から推
定可能 [26])
あとやる気と根気と時間 ← 無限ループの主要因
65 / 71

Outline
はじめに
モデル
例題
参考文献
66 / 71

参考文献 (1)
[1] 藤原友, 長江剛志, 朝倉康夫, GIS と需要変動型利用者均衡配分を用いた道路ネット
ワーク耐震化の便益評価, 土木計画学研究?論文集 24 (2) (2007) 233–242.
URL
http://library.jsce.or.jp/jsce/open/00039/200612{_}no34/pdf/188.pdf
[2] 米田慶太, 川島一彦, 庄司学, 藤田義人, 耐震技術基準の改訂に伴うＲＣ橋脚及びくい
基礎の耐震性向上度に関する検討, 第 2 回地震時保有水平耐力法に基づく橋梁の耐震
設計に関するシンポジウム講演論文集 2 (1998) 453–460.
[3] M. G. H. Bell, C. Cassir, Reliability of Transport Networks, Research Studies Press, UK,
1999.
[4] M. G. H. Bell, Y. Iida, The Network Reliability of Transport, Pergamon, Oxford, UK.,
2003.
[5] Y. Iida, H. Wakabayashi, An approximation method of terminal reliability of a road
network using partial minimum path and cut set, in: Proceedings of the 5th WCTR,
Yokohama, 1989, pp. 367–380.
[6] Y. Asakura, M. Kashiwadani, Road network reliability caused by daily ?uctuation of
tra?c ?ow, in: 1991, 1991, pp. 73–84.
[7] H. Lo, Y. K. Tung, A chance constrained network capacity model, in: M. G. Bell, C. Cassir
(Eds.), Reliability of Transport Networks, Research Studies Press, 2000, pp. 159–172.
67 / 71

参考文献 (2)
[8] H. K. Lo, Y.-K. Tung, Network with degradable links: capacity analysis and design,
Transportation Research Part B: Methodological 37 (4) (2003) 345–363.
doi:DOI:10.1016/S0191-2615(02)00017-6.
URL
http://www.sciencedirect.com/science/article/pii/S0191261502000176
[9] H. Yang, K. K. Lo, W. H. Tang, Travel time versus capacity reliability of a road network.,
in: M. G. H. Bell, C. Cassir (Eds.), Reliability of Transport Networks, Research Studies
Press,, 2000, pp. 119–138.
[10] A. H. Chen, H. Yang, H. Lo, W. H. Tang, Capacity reliability of a road network: an
assessment methodology and numerical results., Transportation Research Part B 36 (3)
(2002) 225–252.
[11] A. Nagurney, Q. Qiang, Fragile Networks: Identifying Vulnerabilities and Synergies in an
Uncertain World,, John-Willey & Sons., 2009.
[12] M. A. P. Taylor, G. M. D’Este, Critical infrastructure and transport network vulnerability:
developing a method for diagnosis and assessment, in: A. Nicholson, A. Dantas (Eds.),
Proceedings of the 2nd International Symposium on Transportation Network Reliability,
Christchurch, New Zealand, 2004, pp. 96–102.
[13] E. Jenelius, T. Petersen, L.-G. Mattsson, Importance and exposure in road network
vulnerability analysis, Transportation Research Part A 40 (2006) 537–560.
68 / 71

参考文献 (3)
[14] A. Nicholson, Z.-P. Du, Degradable transportation systems: An integrated equilibrium
model, Transportation Research Part B: Methodological 31 (3) (1997) 209–223.
doi:DOI:10.1016/S0191-2615(96)00022-7.
URL
[15] V. L. Knoop, M. Snelder, H. J. van Zuylen, S. P. Hoogendoorn, Link-level vulnerability
indicators for real-world networks, Transportation Research Part A: Policy and Practice
46 (5) (2012) 843–854. doi:10.1016/j.tra.2012.02.004.
URL
[16] E. Jenelius, L.-G. Mattsson, Road network vulnerability analysis of area-covering
disruptions: A grid-based approach with case study, Transportation Research Part A:
Policy and Practice 46 (5) (2012) 746–760. doi:10.1016/j.tra.2012.02.003.
URL http://linkinghub.elsevier.com/retrieve/pii/S0965856412000213
[17] H. Yang, Sensitivity analysis for the elastic-demand network equilibrium problem with
applications, Transportation Research Part B: Methodological 31 (1) (1997) 55–70.
doi:DOI:10.1016/S0191-2615(96)00015-X.
URL
http://www.sciencedirect.com/science/article/pii/S019126159600015X
69 / 71

参考文献 (4)
[18] H.-J. Huang, M. G. H. Bell, A study on logit assignment which excludes all cyclic ?ows,
Transportation Research Part B 32 (6) (1998) 401–412.
doi:10.1016/S0191-2615(98)00008-3.
[19] Y. Asakura, E. Hato, M. Kashiwadani, Stochastic network design problem: an optimal
link improvement model for reliable network, in: M. G. H. Bell, Y. Iida (Eds.), The
Network Reliability of Transport, Pergamon, 2003, pp. 245–259.
[20] T. Nagae, T. Fujihara, Y. Asakura, Anti-seismic reinforcement strategy for an urban road
network, Transportation Research Part A: Policy and Practice 46 (5) (2012) 813–827.
doi:10.1016/j.tra.2012.02.005.
[21] L. Du, S. Peeta, A Stochastic Optimization Model to Reduce Expected Post-Disaster
Response Time Through Pre-Disaster Investment Decisions, Networks and Spatial
Economics 14 (2) (2014) 271–295. doi:10.1007/s11067-013-9219-1.
URL http://link.springer.com/10.1007/s11067-013-9219-1
[22] R. Y. Rubinstein, D. P. Kroese, The cross-entropy method: a uni?ed approach to
combinatorial optimization, Monte-Carlo simulation, and machine learning, Springer,
New York, 2004.
[23] B. Efron, R. J. Tibshirani, An introduction to the bootstrap, Chapman & Hall, 1994.
70 / 71

参考文献 (5)
[24] Z. I. Botev, D. P. Kroese, An E?cient Algorithm for Rare-event Probability Estimation,
Combinatorial Optimization, and Counting, Methodology and Computing in Applied
Probability 10 (4) (2008) 471–505. doi:10.1007/s11009-008-9073-7.
URL http://www.springerlink.com/index/10.1007/s11009-008-9073-7http:
//dx.doi.org/10.1007/s11009-008-9073-7
[25] R. Rubinstein, The Gibbs Cloner for Combinatorial Optimization, Counting and
Sampling, Methodology and Computing in Applied Probability 11 (4) (2009) 491–549.
doi:10.1007/s11009-008-9101-7.
URL http://www.springerlink.com/index/10.1007/s11009-008-9101-7http:
//dx.doi.org/10.1007/s11009-008-9101-7
[26] 安中正, 山崎文雄, 片平冬樹, 気象庁 87 型強震計記録を用いた最大地動及び応答スペ
クトル推定式の提案, 土木学会第 24 回地震工学研究発表会講演論文集 1 (3) (1997)
161–164.
71 / 71

狠狠撸

Gibbs cloner を用いた組み合わせ最適化と cross-entropy を用いた期待値推計: 道路ネットワーク強靭化のための耐震化戦略を例として

More Related Content

Gibbs cloner を用いた組み合わせ最適化と cross-entropy を用いた期待値推計: 道路ネットワーク強靭化のための耐震化戦略を例として