人工知能学会 インタラクティブ
情報アクセスと可視化マイニング研究会(第31回)
SIG-AM-31-07

確率的経路生成モデルの規格化条件の導出と実験による評価
Derivation of Normalization Conditions for Probabilistic RouteGenerative Model and Experimental Evaluation
柴田祐樹 1∗ 高間康史 1

Hiroki Shibata1
1
1

Yasufumi Takama1

東京都立大学大学院システムデザイン研究科

Graduate School of System Design, Tokyo Metropolitan University

Abstract: This paper derives normalization conditions for the probabilistic route generative model(PRGM). Variety of uncertaity must be delt with in the sightseeing route recommendation. PRGM isappropriate as the model of it because PRGM intrinsically expresses the uncertainty, and can employ
well studied methods such from statistical physics. After the proposal of PRGM, its formulation stilllacks generality, i.e., each node in a graph of road map must be visited only onece or less than once.
It is extended so that any node can be visited infinitely and shows conditions the model satisfies
mathematically and its validity by neumerical experiments.
はなく無限になるという問題がある．無限の状態空間に1対して定められる確率分布は，各標本に対する確率の和

はじめにが 1 となることが自明ではないため，規格化の条件を別

本稿では，確率的経路生成モデルの確率分布が規格化途定める必要がある．本研究はこの問題に取り組む．

されるための目的関数が持つべき条件の導出を行う．ま

不確実性とは，天気の変化，交通網上での事故，予定た評価実験によりその妥当性を示す．本研究はインタラの変更，移動速度のばらつきなどの観光を行う上で発生

クティブ観光経路推薦システムに関するものである．

しうる要因のことである．観光経路推薦における不確実

インタラクティブ観光経路推薦のための確率的経路生成モデルが提案されている [1]．文献 [1] は，不確実性の性を取りあつかう方法は，[1] のような確率分布による方法以外にも数多く研究されている [2,3]．扱う不確実性の多い状況で利用が想定される観光経路推薦システムに対

粒度はそれぞれの研究で異なるが，これらはどれも経路して，確率モデルによる推薦問題の定式化の有用性を主を求める問題を TSP，および Selective TSP (STSP) [9]張している．一般のグラフ上での順回路（経路）を扱い，をもとにした最適化問題として定式化し，最適な経路を

巡回 Salesman 問題（Traveling Salesman Problem）[9]

利用者へ提示することを想定している．実際の不確実性と同様に一つ経路で各節点は一度のみ通過可能であるとへの対処方法として，[3] はユーザからのフィードバック

している．本研究では，このモデルを拡張し，何度でもを得られるたびに再計算を実行するシステムを提案して節点を通過可能であるとする．この仮定は，もと来た道

いる．[2] は問題の定式化に着目している一方で実時間を引き戻さなくてはならない事態の発生しうる，インタ

での状況変化へ対処法については言及がされていない．

ラクティブな経路推薦を行う上で必要となる．文献 [1]このように不確実性を適切に取り扱う試みが最適化問題

はインタラクティブに実際の状況に応じて経路を再構成の枠組みでなされているが，依然としてさらなる一般化

することを想定しているモデルであるが，この仮定を満の余地が残されていると言える．

たしていないため，起こりうる経路の経路長さが有界で[1] は経路の確率生成モデルを観光経路推薦に用いる

なくなるという問題が発生する．より形式的に言えば，ことを提案している．確率分布を用いることで，不確実経路の状態空間の大きさが [1] で仮定されていた有限で性はモデルに内在するため，追加の定義なしに表現することが可能となる．また，近年統計物理学の発展により∗ 連絡先：東京都立大学システムデザイン学部情報科学科〒191-0065 東京都日野市旭が丘 6-6

E-mail: hshibata@tmu.ac.jp

得られている，Markov Chain Monte Carlo (MCMC)
法 [7] や，Exchange Monte Carlo 法 (EMC) [6, 10] とー 40 ー

人工知能学会 インタラクティブ
情報アクセスと可視化マイニング研究会(第31回)
SIG-AM-31-07

言った多くの先進的な標本抽出法を用いることができ利得（価値）を最大化するという問題の Selective TSP

る．Bayes 推論の枠組みを適用可能であることから，先(STSP) が実際には良く用いられる [1, 5, 9]．これについて説明する．N を節点の集合，E を辺の集合として，完全グラフ G = (N, E) を考える．STSP は各 n (∈ N )に価値を割り当てる b : N → R を定義する．これは観光経路における，スポット（Point of Interest）の価値に相当する．経路を x ∈ N N で表し Lx (≤ #N ) を x の長さであるとする*1 ．w : E → R+ を辺の重み，f : N → R+
を節点での滞在時間とする．ある C ∈ R+ に対して，以下の P1 , P2 ，φ を定義する．

端の機械学習の成果を取り込むことが容易である．確率モデルの標本抽出法は単一解の最適化法に比べると計算量が大きいため，従来は実問題への適用が難しくあったが，近年の計算機の発展により，実用化の可能性が見られる．これらの背景から，[1] の提案は近年の背景に即したモデル化となっていると考える．このモデルを発展させることで，今後の経路推薦問題の定式化と推薦システ
ムの性能向上が期待できるため，本研究は [1] のモデル化に着目する．具体的に，本稿では節点の訪問回数に制限をなくす一般化を行う．

φ(x) = −本稿は上記一般化を行う際に必要となる確率分布を規LxX定する目的関数が満たすべき規格化条件の導出を行う．
また，実際にその規格化条件を満たす目的関数を複数提P2 (x) :⇔案し，評価実験によりそれぞれの特性を調査する．評価
実験から，規格化条件を満たす目的関数を用いた確率分
布からは，経路長さの期待値が収束し，そうでない場合

手法をモデルの性質から考慮し，確率的経路生成モデルの定式化を行う研究は，著者の知る限り存在しないた

LxX[w(xi−1 , xi ) + f (xi )] < C,

(1)

i=2

このとき，STSP は，

P (x∗ ) ∧ φ(x∗ ) =は収束しないことを示す．結果について理論から想定されないことに関し考察を行う．インタラクティブな推薦b(xi ), P1 (x) :⇔ i =6 j ⇒ xi =
6 xj

i=1

min

φ(x)

P1 (x)∧P2 (x)となる x∗ を求める問題と定式化される*2 ．

C は時間制約（time budget）などと呼ばれ，全体のめ，本研究の創造性は高いと考える．

旅行にかけることのできる総時間である．この定式化で

1.1

ため，地図情報を用いるには前処理を要する．多くの研は問題のグラフは完全グラフでなくてはならない．その定義と記法

究では，地図中のうちスポットに該当する地点を，最大R+ を正の実数，N を自然数全体の集合とする．自然で 100 程度選び，それらスポットで N を定義し b, f を

数 n に対して，[n] = {1, 2, ..., n} とする．集合を { } で設定する．また，スポット間を結ぶ最短経路を w として{1, 2, ...} のように書き，族（列）を (1, 2, ...) のように( ) で表す．集合 A と自然数 N に対して，AN は直積集
合を表し，その要素 a ∈ AN は ∀i ∈ N [ai ∈ A] を満
たす列である. 例えば x ∈ R[n] は x = (x1 , x2 , ..., xn )で表される数ベクトル x の全体を意味する．#A は Aの要素の数を示す．標本空間を Ω で表す．確率変数 xが与えられたとき, x(Ω ) は x の実現値の集合（状態空間）を示す．x の確率分布を p(x), 特定の値 x に対する確率を p(x = x) と表す．この他の記法について [13] に設定する．#N ≈ 100 程度である理由は主に計算負荷の削減のためである．近年ではより高性能な計算機が利用可能となっていることから，[1] ではその計算能力を活用可能な #N > 1000 の場合を想定したモデル化と計算手法を提案している．これについて節 2.3 で後述する．

2.2

最適化法と標本抽出法

節 1 で述べたとおり，本稿が研究対象とする観光経路

従う．

推薦問題は，ほとんどの研究で最適化問題として定式化

2

関連研究

似問題として定式化する．本稿の研究と関連する最適化

2.1

Traveling Salesman Problem

される．例外として [1] は標本抽出による確率分布の近手法と [1] で用いられる標本抽出法をここで紹介する．

Traveling Salesman Problem (TSP) [9] は観光経路
推薦問題の基礎的な定式化を提供する． TSP は最短順回路を求める問題であるが，これと類似の定式化で経路長さ制限が存在する元で，線形和で表される順回路のー 41 ー*1 循環定義を避けるために経路は無限列 N N の要素であるとしている．これに形式的に長さを定めるためには，N に実在しない
特殊な節点 n∗ を用意し，n∗ = xi となった i を Lx とすれば良い．
*2 普通 φ(x) の符号は本稿と逆であり max により定義されるが，本稿の他の定式化と一貫性を取るために，min による定義を用いている．

人工知能学会 インタラクティブ
情報アクセスと可視化マイニング研究会(第31回)
SIG-AM-31-07

観光経路推薦問題は，Non-deterministic Polynomial
Hard （NP 困難）に属するため，最適化手法は主に局所最適化と Meta-Heuristics (HM) を元に近似解法として構成される．よく用いられるのが， k 最適化法 [11]と Genetic Algorithm (GA) や Simulated Annealing(SA) といった HM の組み合わせである．また，GA や
SA ほどの認知度がないと見られるが，近年発展の目覚ましいものに，Exchange Monte Carlo (EMC, Parallel
Tempering とも言う) が挙げられ，TSP に対する適用事例 [6] や，STSP に対する適用事例 [1] が存在する．
k-最 適 化 法 は， 最 適 化 途 中 の 経 路 x の k 個 の 辺((xi , xi+1 ; i ∈ K), #K = k, K ⊂ N を選び，これらについてのみ式 (1) の φ を最小化するように最適化を行うことを集合 K を変更しながら繰り返す．これは貪欲法であり，容易に局所最適解へ早期収束する問題があるため，MH と組み合わせて通常用いられる．

SA は目的関数 φ を指数部に持つ，次の Boltzmann
分布を元に構成される．

p (x = x) = Z(T )−1 exp −T −1 φ(x)(2)

ここで，x : Ω → N は経路の確率変数，Z は確率分布
N

Carlo 法 (EMC) [6, 10] はこの温度計画を不要にし，SAと同様に低い温度の分布から近似最適解を抽出可能な性質を保ちつつ，定常的に最適化を続けることができる方法である．さらに，EMC は任意の温度に対する p(x)を近似する標本を抽出することができる．これにより，確率分布を近似することが可能となる．MCMC でも確率分布は近似できるが，多峰性の分布に対して性能が低い．一方で EMC は高い T を持つ分布を利用することで，高い T の分布は分布の山が平坦になるため MCMCでの遷移が容易となることから，他の低い T の分布を精度良く近似できるという特徴を持つ．

EMC について少し定式化を説明する（詳しくは [1]の節 3 を参照されよ．）．EMC では，SA の温度計画の代わりに温度の列 (Tm ; m ∈ M ) を用意する．これらに対して，T のみが異なる式 (2) と同様の分布 p(xm ; Tm )に対して MCMC 法で標本抽出を繰り返す．これら分布を複製（Replica）と呼ぶ．得られた標本を，任意の間隔で，2 つの複製間で交換し MCMC を継続する．この交換は MCMC と同様の基準で確率的に行われ，常に発生するとは限らない．この基準による確率的交換により，それぞれの p(xm ) の分布に悪影響を与えること無く，そを規格化するための定数，T (∈ R+ ) は温度と呼ばれるの標本の精度を向上させることができる．

T → 0 の極限において，2.3

分布の平滑さを制御する制御変数である．式 (2) より，

φ(x) = min φ(y) ⇒ p (x = x) =y

インタラクティブ観光経路推薦

インタラクティブな観光経路推薦手法の提案が行われ

1,# argminy φ(y)ている [1–3]．ここでは，確率分布から標本を抽出する

φ(x) =
6 min φ(y) ⇒ p (x = x) = 0

ことによりインタラクティブ観光経路推薦問題を定式化となる．極限の分布から標本抽出を行うことは困難であり，[1] は機械学習分野や統計物理学の手法を適用可能なるため，MCMC 法などの平衡分布に標本が近づく手法

程度に一般性が高く発展させる価値があると考えるからにより標本抽出を繰り返しながら，徐々に T を 0 へ近である．[1] の定式化を Probabilistic Route Generativeづけ，極限分布から標本，すなわち最適解を抽出するこ

Model (PRGM) と本稿では呼ぶ．
PRGM の定式化を説明する． PRGM では目的関数
φ : N N → R を以下の通り定義する．この関数の値が小する [1] に着目する．着目する理由は節 1 で述べたとおyとを期待する方法である．最適解が抽出できない場合でも，無作為に選んだ場合に比べれば最適解に近い解を得られることが期待できる．ここで，MCMC では，提案

さいほど良い経路であるとする．

分布と呼ばれる状態の無作為な変更方法が定義される必

φ(x) = F (α(x) − C) − β(x),要があるが，ここに k-Opt 法を用いることができる．ただし，k-Opt 法で φ を最小化する変更は必ずしも適用さ

α(x) =

れず， MCMC の棄却基準により適用の選択がされる．
詳細は省くが T が小さいほど選択基準は貪欲的になり，

LxX

w(xi−1 , xi ), β(x) =

i=2

Lx
X

(3)

b(xi−1 , xi )i=2

逆の場合探索的になる．

ここで，F : N N → R は制約関数であり STSP の制約をSA では T の変化方法の定義に自由度があり，この点に問題がある．一度設定した T の降下計画が終われ

この目的関数を最小化する問題には STSP の制約が含ば，そこで最適化が終わってしまうからである．これは，最適化に使える時間を見積もることが難しい，例えば

real-time 性の高い場面で問題となる．Exchange Monte表現する．実際に F (x) = lima→∞ exp (ax) とすれば，まれる．その他の制約については，式 (1) の P1 (x) を満たすものとする，つまり，同じ節点を複数回訪れる経路は生成されない．

ー 42 ー

人工知能学会 インタラクティブ
情報アクセスと可視化マイニング研究会(第31回)
SIG-AM-31-07

w : N 2 → R+ , b : N 2 → R はそれぞれ辺の負荷と価るため，インタラクティブ性に優れることが主張されて値である．これは完全グラフを前提とした定式化である

いる．

が，PRGM では完全グラフでない一般のグラフに対応可能とするために，仮想辺と呼ばれる辺が導入される．

制約関数 F について STSP に対するものの他には，
F (x) = ReLU(x) などがある．PRMG では ReLU と同

仮想辺は，MCMC の状態変化において経由されること等な関数により急激な目的関数の変化を防ぎ，最適化をで，非完全グラフの E0 に対する局所変化を完全グラフ

容易にしているとある．しかし，その効果について実証に対する方法と同様に適用可能とするものである．元のはされていない．次節以降 F について議論する．

グラフを N, E0 として，e ∈ E0 を実辺，e 6∈ E0 を仮想辺と呼ぶ．このとき，e ∈ N 2 に対し，次のとおり w, bを定義する．

つまり経路長さの制限をなくす一般化を行う． PRGMe 6∈ E ⇒ [w(e) = s(e), b(e) = −Bs(e)] ,の定式化では，来た道を戻ることができず，その状況

ここで，w0 は実辺の負荷であり，b0 (e) は実辺の価値である*3 ．s は仮想辺の負荷であり，e = (n, n0 ) としたと
き以下の通り定義される．

s(n, n0 ) = minx0 ∈N Nが起こった場合に別途処理が必要であるという問題があった．実際にそういう場合は，実時間でのインタラク
ティブな操作を想定したときユーザの行動が予想できな
いため十分に考えられる．よって，一般化を行うが，このとき確率分布が規格化されることが自明でなくなる．

w0 (x0i , x0i+1 ), x01 = n,

式 (2) の分母 Z の規格化定数は，分子の x の状態空間

i=1

xLx0 = n0 , ∀i ∈ [Lx0 − 1](xi , xi + 1) ∈ E0 .

提案
本稿は PRGM [1] の定式化のうち式 (1) の P1 の制約，e ∈ E ⇒ w(e) = w0 (e), b(e) = b0 (e) ,

Lx0
X

3

(4)

B ∈ R+ は罰則係数であり，ハイパーパラメータとな
る．e 6∈ E0 の場合，e は実際の道に対応しない辺であり，最終的に生成される経路に含まれてはならない．Bs(e)の値を大きくすることで，この辺を持つ経路 x の φ(x)は比較的高い値を持つため，生成されにくくなる．よって，Bs(e) は大きな値となるように B, s(e) を定めるべきであるが，MCMC の効率を低下させることになるた
め際限なく大きな値とすることはできない．PRGM ではこれに対し式 (4) のように e 6∈ E0 に対しての E0 上の辺で構成される最短経路の負荷で s(e) を定義する．これにより ∀e ∈ E0 b0 (e) = 0 のグラフに限るが，遷移が効率的に行われ，貪欲法であっても最終的に経路から仮想辺が消滅することが示されている．
実際の経路生成では，目的関数 φ を指数部に持つ式(2) により確率分布を定義し，EMC により標本抽出を行う．標本平均により描かれた経路の確率分布をユーザに提示する．ユーザが確率分布の値の高さをその道の推x(Ω ) についての総和であり，この状態空間の大きさが無限となるとき，一般に総和が有限の値とはならないか
らである．

3.1

規格化条件の導出

経路が定義されるグラフとして完全グラフを仮定する．この仮定は議論の一般性を失わない．また頂点の数は有限で M とする．M < ∞ であるが，このグラフ上で生成される経路長は同じ節点を通過することが際限なく可能であるため ∞ となりうる．重みは，場合の数が最も大きくなり，最も厳しい場合の議論ができるように
すべて 1 であると仮定する．式 (3) における価値は 0 とする．
経路 x の長さ（重みの合計）を α(x) と表す．α(x) = nである場合の数は，ほぼ M n−1 である（始点と終点が固定される分の自由度が減るため M n ではない．
）．今，目的関数は (3) の定義から経路の長さ n のみに依存するため，これを φn で表す．このとき，

薦度とみなし，経路を自ら描くという用途を期待する．
単一の経路を一つ提示する従来の最適化に基づく推薦p (α(x) > k) ∼に比べ，ユーザの意志を不必要に制限する必要がなくな

∞
X

M

n=k+1

り，また，EMC によりユーザが選択した以外の経路を，≤

ユーザの選択を制約として，持続的に再計算が可能であ

∞
X
n=k


1
exp n log M − φnT1
exp − φn
Z
T


n−1 1



であるが，p は確率分布であるから任意の k について
*3 辺に価値が割り当てられておりこれは STSP の定式化である節点に価値を割り当てる定義と異なるが，ここでは簡素化のため，
また PRGM と同様の定義とするためにこの定義を用いる．

ー 43 ーp (α(x) > k) ≤ 1(5)

人工知能学会 インタラクティブ
情報アクセスと可視化マイニング研究会(第31回)
SIG-AM-31-07

でなければならない．このための必要十分条件は，
∞
X



1
∃C ∈ R,
exp n log M − φn
T
n=1


<C

(6)

である．また式 (6) の必要条件は，


1
lim exp n log M − φn = 0
n→∞
T

(7)
図 1 Comparison of convergence of route length on

である．よって，任意の M, T (∈ R+ ) について成立さ

maximum temperature T = 4 for each, x1+a , a =0.0, 0.2, 0.3, 1.0.

せるためには，

O(n) ⊂ O(φn ) ∧ O(n) 6= O(φn )(8)となることが式 (5) の必要条件である．例えば，φn = n2などは式 (8) を満たす．またこれは，式 (6) も成立させるため，φn = n2 は式 (5) の十分条件となる．

3.2とし b0 (e) は 0, 0.25, 0.5 の中から無作為に設定した．

式 (8) を満たすものとして，前節最後の n2 の他には，ある a > 0 に対する式 (9) や式 (10) がある．

F (x) = x1+a(9)

F (x) = x log(x + 1)

(10)

上記はさらに，式 (6) も満たすため，確率分布が規格化されるための十分条件式 (5) を満たす．
ここで，式 (7) には温度 T があるため，これに依存して 0 への収束速度が決まると考えられる．収束速度が小さい場合，より長い経路が生成されやすくなるが，長い経路は計算負荷が高いため問題となる．これについて検証する．φx = F (x) を代入して，指数部が負となる場所を考える．式 (9) の場合，指数部は，

 p1

図 2 に目的関数の違いによる平均経路長さと温度の関係を，F (x) = x1+a ,(11)である．この値より x > x∗ の領域で確率の値は x の増加に伴い減少を始めるため，経路長さの期待値は x∗ 付
近となると考えられる．実問題において M には実効的に O(1) 程度になると考える．

4

うる状態に制限が与えられていないと推測できる．すなて妥当であるとわかる．

となるが，これが極大値を取る x = x∗ は，

T log M
1+a

#N = 576, #E0 = 1104, C = 96, B = 1 である．EMC
を 用い て標 本 抽出 を 行い， Tm = 0.1d exp(m/(M −1)0.9d)), m ∈ [128] の温度を持つ複製を用いた．d = 3, 4を図 1，図 2 の実験にそれぞれ用いた．MCMC を 210
回行うごとに EMC の状態交換を行った．これを 210 回行い， 2 回ごとに統計量の計算に用いる標本を記録した．乱数生成に Mersenne Twister [12]，実数の近似に
64 bit 浮動小数点数を用いた．
図 1 に 経 路 長 さ と 計 算 の 進 度 の 関 係 を F (x) =1+a
x , a = 0.0, 0.2, 0.3, 1.0 について両対数軸により示す．縦軸は T = 4 の状態の経路長さである．a = 0 の場
合を除いて収束している．これにより，式 (6) が十分条件として妥当であるとわかる．a = 0 の結果について，
これは典型的な Random walk の状態であるため，取りわち，確率が規格化されておらず，(8) が必要条件とし

1
x log M − x1+aT

りとなるか調べる．数値実験では [1] と同様の 24 × 24の格子状グラフを用い， e ∈ E0 について w0 (e) = 1

目的関数の提案x∗ =か検証する．またその期待値が (11) で予測されるとおa = 0.08, 0.1, 0.12, 0.14, 0.2, 0.3, 0.5, 1 および F (x) =x log(x + 1) の場合について両対数軸により示す．図 2から，高い T で経路が長くなる傾向はどの場合も認められ，a の値が小さいほど，大きいとわかる．T = 1 を堺にして増加が始まり，a に依存せずすべて同程度の増加
速度となっている．式 (11) では，a の値により増加率が変わるため，この結果は式 (11) の予想に反する．T = 1
を堺に増加が始まっていることについて，実験で用いた評価実験

グラフの価値 ≈ 0.5 が影響していると考えられる．T が式 (9) と式 (10) を用いた場合に確率分布が規格化されている，つまり経路長さの期待値が収束するかどう

価値を超えたときに状態が仮想辺を通過することが可能となり始めるため，このような遷移が現れていると考えー 44 ー

図 2 Comparison on various constraint function,

x1+a , a = 0.08, 0.1, 0.12, 0.14, 0.2, 0.3, 0.5, 1 andx log(x + 1).

られる． a による増加率が予想に反することについて，
これも価値が影響を及ぼしていると考えられる．今回一般的な条件とするために価値を与えたグラフを実験で用いたが，価値を与えないグラフを用いた実験を行った場
合に違った傾向が観測されると考える．

5

おわりに
本稿では，確率的経路生成モデルの確率分布が規格化されるための目的関数が持つべき条件の導出を行い，また評価実験によりその妥当性を検証した．数値実験より，導出した条件の妥当性を示した．一方で，予測される確率分布の裾の広がりと，実験で示される裾の広がりが一致しなかった．この点についてさらなる調査が望まれる．
インタラクティブな推薦手法をモデルの性質から考慮し，また，確率的経路生成モデルの定式化を行う研究は，著者の知る限り存在しないため，本研究の創造性は高い
と考える．

謝辞
本研究の一部は JSPS 科研費 JP22H03698 の助成を受けたものである．

参考文献[1] 柴田祐樹，高間康史: インタラクティブ観光経路推薦手法の構築に対する検討，第 27 回 SIGA， pp.
19–24 (2021).
[2] Hasuike, T., Katagiri, H., Tsubaki, H., Tsuda,
H.: Interactive multi-objective route planning forsightseeing on Time-Expanded Networks undervarious conditions, Procedia Computer Science,Vol. 22, pp. 221–230 (2013)[3] Fu, C., Hu, M., Lai, J., Wang, H., Wu, J.: TravelBuddy: Interactive Travel Route Recommendation with a Visual Scene Interface, MultiMedia
Modeling, pp. 219–230 (2014)[4] Hang, L., Kang, S., Jin, W., Kim, D.: Design
and Implementation of an Optimal Travel Route
Recommender System on Big Data for Tourists
in Jeju, Processes, Vol. 6, No. 8 (2018)[5] 倉田 陽平: CT-Planer 3: Web 上での対話的な旅行プラン作成支援, 観光科学研究, No. 5, pp. 159–165(2012)[6] Wang, C., Hyman, J., Percus, A., Caflisch,
R.: Parallel Tempering For The Traveling Salesman Problem, International Journal of Modern
Physics C, Vol. 20, No. 4, pp. 539-556 (2009)[7] Metropolis, N., Rosenbluth, A., Rosenbluth,M., Teller, A.: Equation of State Calculations
by Fast Computing Machines, The Journal ofChemical Physics, Vol. 21, No. 6, pp. 1087–1092(1953)[8] Kirkpatrick, S., Gelatt, C., Vecchi, M.: Optimization by Simulated Annealing, Science, Vol.
220, No. 4598, pp. 671-68 (1983)[9] Feillet, D., Dejax, P., Gendreau, M.: Traveling
Salesman Problem with Profits: An Overview,
Transportation Science, Vol. 39, No. 2, pp.
188–205 (2005)[10] Hukushima, K., Nemoto, K.: Exchange Monte
Carlo Method and Application to Spin Glass
Simulations, Journal of the Physical Society ofJapan, Vol. 65, No. 6, pp. 1604–1608 (1995)[11] Sohl-Dickstein, J., Mudigonda, M., DeWeese,M.: General k-Opt Submoves for the LinKernighan TSP Heuristic, Mathematical Programming Computation, Vol. 1, No. 2–3, pp.
119–163 (2009)[12] Matsumoto, M., Nishimura, T.: Mersenne
Twister: A 623-Dimensionally Equidistributed
Uniform Pseudorandom Number Generator,
ACM Transactions on Modeling and Computer
Simulation, Vol. 8, No. 1, pp. 3–31 (1998)[13] 松坂和夫: 集合・位相入門，岩波書店，第 59 版
(1968)