本研究における今後の課題は以下に挙げる。
（1） 拡張方向における選択方法の高度化
（2） パラメータ設定・調整の高度化と手法の適応化
本研究の提案手法で近接最適性原理に基づく良い解の付近により良い解を探索する戦略 のみを使用するため，拡張方向における選択方法は，単純に拡張方向とする解の評価値の 良さで選択することである。本論文の5.2.3 節に述べたように，本研究で提案した新たな 探索点の移動戦略を適用すると解空間の中に探索済み領域と未探索領域は簡単に分けられ る。そのため，領域の拡張を良い解のある方向への移動で集中化探索をすることと，未探 索領域の大きい方向への移動で多様化探索することは選択できる。多様化・集中化のバラ ンスの良い探索点の移動戦略の構築は，さらなる汎用性が広く，性能が高い手法の開発を 可能にする。故に，多様化・集中化戦略を考慮する拡張方向における選択方法の高度化は 重要な課題である。
また，6.1節で述べたように，メタヒューリスティクスのパラメータの設定・調整によっ て，組合せ最適化問題に対する探索性能は大きく異なる。本研究の中心とされる2つの手 法もそれぞれパラメータを有しており，異なるベンチマーク問題に対する適するパラメー タが異なることも確認されている。これらの手法を実際に使用する時，パラメータの設定・
調整はユーザーに対する大きな負担である。故に，より汎用性・有用性の高い組合せ最適 化を開発するため，提案手法のパラメータ設定・調整の高度化を通して，異なる問題に対 する適応的な探索の実現は重要な課題である。
A 本論文で用いたベンチ マーク問題
付録では，本研究の数値実験て用いた組合せ最適化問題である0-1ナップサック問題
（0-1KP），巡回セールスマン問題（TSP），フローショップスケジューリング問題（FSP）， 二次割当問題（QAP）について，問題の概要，解の構造と定式化，距離・近傍の定義を説 明する。
0-1 ナップサック問題
(0-1KP: 0-1 Knapsack Problem)
ナップサック問題とは，各荷物iに対する，重量ai，価値ci，および重量制限bが与えら れた時，与えられたn個の荷物集合V ={1,2,· · · , n}からいくつかを選び，選ばれた荷物 の重量の合計が重量制限を超えないという条件の下で，価値の合計を最大にする有制約組 合せ最適化問題である。
㔜㔞ไ㝈‶ࡓࡍୖ ౯್᭱
ࡶࡢ
㔜㔞 ౯್
ࡶࡢ
㔜㔞 ౯್
ࡶࡢ
㔜㔞 ౯್
ࡶࡢ
㔜㔞 ౯್
ࡶࡢ
㔜㔞 ౯್
ࡶࡢ
㔜㔞 ౯್
ࣂࢵࢢ 㔜㔞ไ㝈
㑅ᢥ
図A.1: ナップサック問題
付録A 本論文で用いたベンチマーク問題 58
0-1KP問題の解は，xi をナップサックに入れる荷物i ∈ V の個数としたときにx =
(x1, x2,· · ·, xn)で与えられる(xiは非負整数)。特に，xi ∈ {0,1}, i ∈ V の場合，解は n bitの二値ベクトルとして表現される。この時は0-1ナップサック問題（0-1KP）と呼ば れる。
0-1KP問題は次のように定式化される。
max f(x) =
∑n
i=1
cixi
subj. to
∑n
i=1
aixi ≤b
0-1KP問題の距離について，本研究ではHamming距離［29］を用いる。その距離関数は 次式で定義する。ここで，xiは二値ベクトルxのi番目の要素である。
dKP(x,y) =| {i|xi ̸=yi(i= 1,· · · , n)} |
0-1KP問題の近傍について，本研究ではHamming距離が1の近傍を用いる。近傍の表
現は1bitの0-1変換である。解と近傍は次式の関係を満たす。
dKP(x,y) = 1, y∈N(x)
巡回セールスマン問題
（ TSP: Traveling Salesman Problem ）
巡回セールスマン問題（TSP）［25］とは，n個の都市の集合V ={1,· · · , n}，及び都市i と都市jの間の距離d(i, j), i, j ∈V が与えられた時，すべての都市をちょうど一度ずつ訪 問した後，元に戻る巡回路のうち，距離が最小になるものを求める問題である。
TSP問題の解は，e(i,j)を都市iと都市jを頂点とした時の都市i, j間の辺とすれば，n個 の点のHamilton閉路x= (V,{e(x1,x2), e(x2,x3),· · · , e(xn−1,xn)}), xi ∈V で与えられる。
TSP問題は次のように定式化される。
min f(x) =
n−1
∑
k=1
d(xk, xk+1) +d(xn, x1)
付録A 本論文で用いたベンチマーク問題 59
ᕠᅇ㊥㞳᭱ᑠ
図A.2: 巡回セールスマン問題
TSP問題の距離について，本研究ではHamiltonグラフの共通しない辺数を用いる。そ の距離関数は次式で定義する。ここで，G(x)はHamiltonグラフxの辺集合である。
dTSP(x,y) =|G(x)\G(y)|
TSP問題の近傍について，本研究では2-opt近傍を用いる。近傍の表現は，Hamiltonグ ラフのうち，隣接しない2つの辺の交差変換である。解と近傍は次式の関係を満たす。
dTSP(x,y) = 2, y ∈N(x)
フローショップスケジューリング問題
（ FSP: Flowshop Scheduling Problem ）
フローショップスケジューリング問題（FSP）［26］とは，S台の機械U ={1,2, . . . , S} とn個の仕事V ={1,2, . . . , n}，機械i∈U が仕事j ∈V が処理する時間tijを与えられ た時，全ての仕事の総処理時間を最小にする仕事の処理順序を求める問題である。処理の 時，全ての仕事は全ての機械に同一の順序で処理される必要があり，一つの機械は同時に 一つの仕事しか処理できない。
FSP問題の解は，xj を仕事j ∈ V が処理される順位とした時（ここで，xj ∈ W = {1,2, . . . , n}とする），x= (x1, x2,· · · , xn)として表される。
付録A 本論文で用いたベンチマーク問題 60
ؽփ1 A ؽփ2 A ؽփ3 A
B B
B C
C C
⏕⏘㛫᭱ᑠ
図A.3: フローショップスケジューリング問題
FSPは以下のように定式化される。ただしtjI(0) =t0I(k) = 0である。
min TSI(n)
TjI(k) = max(TjI(k−1), Tj−1I(k)) +tjI(k) I(k) =i; xi =k
i= 1, 2, · · · , n∈U j = 1, 2, · · · , S∈V k = 1, 2, · · · , n∈W
FSP問題の距離について，本研究ではSpearman’s Footrule［29，30］を用いる。その距 離関数は次式で定義する。ここで，x(i)は順位xの対象iの位置番号である。
dFSP(x,y) =dSF(x,y) =
∑n
i=1
|x(i)−y(i)|
FSP問題の近傍について，本研究では距離が4以内の交換近傍を用いる。解と近傍は次 式の関係を満たす。
dFSP(x,y)≤4, y∈N(x)
二次割当問題
（ QAP: Quadratic Assignment Problem ）
二次割当問題（QAP）［27］とは，配置すべきn個の施設とn箇所の地区，施設iから施 設jへの物の移動量a(i, j)，および，地区kから地区lまでの距離b(k, l)が与えられた時，
物資の輸送コストを最小とする施設の配置を求める問題である。
付録A 本論文で用いたベンチマーク問題 61
A 1 4
2 3
B
C B
ሙᡤ㊥㞳 ᕤሙ≀㔞
㊥㞳≀㔞 ⥲᭱ᑠ 㓄⨨
図A.4: 二次割当問題
QAP問題の解は，施設iを配置する地区をxiとした時，順列x= (x1, x2,· · · , xn)とし て表される。
QAP問題は次のように定式化される。
min
∑n
i=1
∑n
j=1
a(i, j)b(xi, xj)
QAP問題の距離について，本研究ではCayley距離を用いる。順列yに対する順列xの Cayley距離［29，31］は，任意の要素対を入れ替える操作によりxからyへ変換するため に，必要となる最小操作回数である。その距離関数は，置換(xT,yT)Tの巡回置換(cycle) の数|T(
(xT,yT)T)
| を用いて，次式で定義する。
dQAP(x,y) =dC(x,y) = n− |T(
(xT,yT)T)
|
QAP問題の近傍について，本研究では交換近傍を用いる。解と近傍は次式の関係を満 たす。
dQAP(x,y) = 1, y∈N(x)
参考文献
参考文献
［1］ 貝原俊也：「スマーターワールド実現にむけたシステムズアプローチの新潮流」，計測 と制御，Vol.55，No.8，pp.641–649（2016–8）
［2］ 茨木俊秀：「組合せ最適化とスケジューリング問題：新解法とその動向」，計測と制御，
Vol.34，No.5，pp.340–346（1995–5）
［3］ 青木義次・村岡直人：「遺伝的アルゴリズムを用いた地域施設配置手法」，日本建築学 会 計画系論文集，No.484，pp.129–135（1996–6）
［4］ A. Klose, A. Drexl: “Facility location models for distribution system design”, European Journal of Operational Research, Vol.162, No.1, pp.4–29 (2005–4)
［5］ 柳浦睦憲・茨木俊秀：「組合せ最適化―メタ戦略を中心として―」，朝倉書店（2001）
［6］ 相吉英太郎・安田恵一郎（編著）：「メタヒューリスティクスと応用」，オーム社（2007–10）
［7］ 安田恵一郎：「メタヒューリスティクスの現在と未来」，計測と制御，Vol.47，No.6， pp.453–458 (2011–4)
［8］ 落合広樹・金澤貴彦・田村健一・安田恵一郎：「解空間の階層構造に基づく組合せ最適 化手法」，電気学会 電子・情報・システム部門誌，Vol.135，No.2，pp.254–264 (2015–2)
［9］ 落合広樹・田村健一・安田恵一郎：「解空間の階層構造に基づく多点探索型組合せ最適
参考文献 63
化手法」，電気学会 電子・情報・システム部門誌，Vol.134，No.7，pp.999–1000 (2014–7)
［10］ E. Aarts, J. K. Lenstra: Local Search in Combinatorial Optimization, Wiley-interscience, Chichester (1997)
［11］ R. J. M. Vaessens, E. H. L. Aarts, and J. K. Lenstra: “A local search template,”
Computers Ops Res, Vol.25, No.11, pp.969–979 (1998–11)
［12］ 金澤貴彦，安田恵一郎：「組合せ最適化問題の解空間における上位構造に基づくメタ ヒューリスティクスの基礎検討」，平成22年電気学会 電子・情報・システム部門大会，
OS4-11, pp.807–812 (2010–9)
［13］ 金澤貴彦・安田恵一郎：「組合せ最適化問題の解空間における上位構造に基づくメタ ヒューリスティクスの基礎検討」，電気学会・情報・システム部門誌，Vol.131，No.4， pp.934–935 (2011–4)
［14］ C. Blum and A. Roli: “Metahuristics in Combinatorial Optimization: Overview and Conceptual Comparison,” ACM Computing Surveys, Vol.35, No.3, pp. 268–308 (2003–9)
［15］ F. Glover and M. Laguna: TABU SEARCH, Kluwer Academic Publishers, Nor-well (1997)
［16］ 森田真英・落合広樹・田村健一・安田恵一郎：「問題構造の概形の推定機構を有する 多点型組合せ最適化手法」，電気学会 電子・情報・システム部門誌，Vol.136，No.7， pp.963–976 (2016–7)
［17］ M. Hashimoto, K. Tamura, J. Tsuchiya, and K. Yasuda: “Multipoint Combina-torial Optimization Method with a Search Strategy in Higher Structure Solution Space,” IEEJ Transactions on Electrical and Electronic Engineering, Vol.12, No.S2, pp.S133–S134 (2017–12)
［18］ 橋本雅俊・田村健一・土屋淳一・安田恵一郎：「解空間の上位構造と多様化・集中 化に基づく多点探索型組合せ最適化手法」，電気学会 電子・情報・システム部門誌，
参考文献 64
Vol.138，No.7，pp.860–869 (2018–7)
［19］ J. Little, K. Murty, D. Sweeney, and C. Karel: “An Algorithm for the Traveling Salesman Problem”, Oper. Res, Vol.11, pp.972–989 (1963–1)
［20］ H. Sakoe, S. Chiba: “Dynamic programming algorithm optimization for spoken world recognition”, IEEE Trans. Acoustics., Speech, Signal Processing, Vol.ASSP-26, No.1, pp.43–49 (1978–2)
［21］ D. E. Goldberg: Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, Boston (1989)
［22］ J. Kennedy and R. C. Eberhart: Swarm Intelligence , Morgan Kanfmann Publishers(2001)
［23］ E. Aarts, and J. Korst: Simulated Annealing and Boltzmann Machines, John Wiley & Sons (1989)
［24］ 加藤十吉：「集合と位相」，朝倉書店（1982–4）
［25］ G. Reinelt: “TSPLIB - A Traveling Salesman Problem Library,” ORSA Journal on Computing. Vol.3, No.4, pp.376–384 (1991–11)
［26］ E. Taillard: “Taillard’s instances”,
http://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/ordonnancement.html, Accessed on Mar. 13th (2018)
［27］ R. E. Burkard, S. E. Karisch, F. Rendl: “QAPLIB: A quadratic assignment problem library, ” Journal of Global Optimization, vol.10, pp.391–403 (1997–6)
［28］ A. E. Eiben, R. Hinterding, Z. Michalewicz: “Parameter Control in Evolutionary Algorithms,” IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, Vol.3, No.2, pp.124–141 (1999–7)
［29］ J. I. Marden: Analyzing and Modeling Rank Data, Chapman & Hall (1995)
参考文献 65
［30］ P. Diaconis, R.L. Graham: “Spearman’s Footrule as a Measure of Disarray,”
Journal of the Royal Statistical Society, Series B, Vol.39, No.2, pp.262–268 (1977)
［31］ 神嶌敏弘：「順序の距離と確率モデル」，人工知能学会研究会資料， SIG-DMSM-A902-07（2009）
国際会議発表論文
［32］ X. Li, K. Tamura, J. Tsuchiya, and K. Yasuda: “Combinatorial Optimization Method Using Expanded Search Mechanism Based on Hierarchical Interpretation in Solution Space,” in Proc. of IEEE International Conference on Systems, Man, and Cybernetics, pp.3134–3139, Bari, Italy (2019–10)【査読有】
国内会議発表論文
［33］ 李絮元・田村健一・土屋淳一・安田恵一郎：「解空間の上位構造と局所探索法に基 づく組合せ最適化手法」，計測自動制御学会 システム・情報部門 学術講演会 2018， GS01-20（2018–11）【査読無】
【計測自動制御学会 システム・情報部門 優秀論文賞 受賞】
［34］ 李絮元・田村健一・土屋淳一・安田恵一郎：「解空間の上位構造と拡張的探索機構に基 づく組合せ最適化手法」，第32回 回路とシステムワークショップ，pp.49–54（2019–8）
【査読有】
［35］ X. Li, K. Tamura, J. Tsuchiya, and K. Yasuda: “Multi-Point Combinatorial Optimization Method Utilizing Expanded Search Mechanism Based on Hierarchical Interpretation in Solution Space,” Proc. of 2019 IEEJ Conference on Electronics, Information and Systems, pp1594–1595. (2019–9)【査読無】