日本ソフトウェア科学会第 39 回大会 (2022 年度) 講演論文集

メタヒューリスティクスの適用を効率的に記述する
ドメイン特化言語
冨井 陸矢

岩崎 英哉

数理最適化プログラムを書く機会とその裾野は，競技プログラミングのコンテストを通して近年格段に幅広くなっている．一方で，焼きなまし法やビームサーチといった典型手法は抽象化の試みがあまりなされておらず，似たようなプログラムを一からコーディングするケースが多い．また，スコアの差分計算では，機械的に生成し得る内容の複
雑なコードを，人間が手書きすることを強いられている．これらの問題を解決するため，いくつかの典型的なメタ
ヒューリスティクスを適切に抽象化し，それらを利用する数理最適化プログラムを最小限のコードで記述して，これを C++へ変換するドメイン特化言語（DSL）を設計し開発した．本発表では，DSL の設計，DSL でのプログラム記
述について説明した後，所定の内容を記述するのに要する行数と実行時間について，C++で記述した場合と DSL で記述した場合とを比較する．さらに，実用的な場面での利用を想定した上での現状の DSL の問題点と，今後の拡張について述べる．

として学会で発表されたり [7] [8] [9]，企業が実際に運1 はじめに用するソフトウェアに用いられることもある．また，アルゴリズムと数学による問題解決能力を競う

問題の本質的な要素を抽出した適切なモデル化が行

AtCoder†1 ，データサイエンスのコンペティションをわれることで，それまで数理最適化に馴染みのなかっ

開いている Kaggle†2 [5]，Web サービスのパフォーマた人間でも新たに参入がしやすくなっている．

ンスチューニングを競う ISUCON†3 など，情報科学を

これらの問題を解くプログラムにおいて用いられ競技の形式にすることで大きな研究成果を得たり，人るアルゴリズムの枠組みは大抵の場合ごく少数のパ材の育成を図ったりするサービスが年々盛り上がってターンに絞られ，特に焼きなまし法 [6] とビームサー

いる．従来は専門の研究者やプログラマのみが扱う

チ [10] に二分される．しかし，これらの典型手法は抽領域であった数理最適化においてもその傾向は強く，象化の試みがあまりなされておらず，ライブラリもほ多くの企業や研究機関が，各々の取り扱っている研究

とんど存在していない．そのため，多くのプログラマ

内容をモデル化した問題をコンテストとして出題しは過去に書いたプログラムと共通点が所々にあると感ている．それらのコンテストの中で生み出されたアルじながらも，問題に合わせてプログラムを書き直してゴリズムやプログラムはそのまま最先端の研究成果いるのが現実である．

A Domain-Speciﬁc Language that Describes The Applicationof Metaheuristics Eﬃciently.
Rikuya Tomii, 電気通信大学情報理工学研究科, Dept. of Information and Computer Science, The University of ElectroCommunications.
Hideya Iwasaki, 明治大学理工学部情報科学科, Dept. ofInformation and Computer Science, Meiji University.
†1 https://atcoder.jp/†2 https://www.kaggle.com/†3 https://isucon.net/

また，実行速度の面でより高い性能のプログラムを書くにはいくつか典型的なテクニックが存在するが，それらはどれも可読性や記述性を大きく犠牲にしたものである．そのため，性能を追求する結果として非本質的なバグに悩まされて時間と労力を浪費することも多い．これらの問題は業界全体の生産性を落としており，数理最適化問題に新たに取り組む者にとっての壁にもなっている．

そこで本研究では，いくつかの典型的なメタヒュー

つくり，その一部を変化させていく探索アルゴリズム

リスティクスを適切に抽象化し，それらを利用する数の枠組みを局所探索法と呼ぶ．山登り法は焼きなまし

理最適化プログラムを最小限のコードで記述して，こ法において常に温度を 0 に設定した場合であると一れを C++へ変換するドメイン特化言語（DSL）を設般化できるため，本研究においては焼きなまし法とい計し開発した．本 DSL は，数理最適化問題に取り組う言葉で局所探索法全般を扱う．

む入り口としてのコンテストにおいて有用であるだ
けでなく，競技を離れた実際の業務や研究においても

2. 2 ビームサーチ

そのまま有効利用できるようなものを目指している．

最初に解をひとつ完成させるのではなく，解の一部を徐々に組み立てていくことを考える．このとき最も

2 数理最適化問題に対するメタヒューリス

素朴で確実な手法は幅優先探索であるが，最適解をティクス必ず見つけられる一方で膨大な時間とメモリを消費

2. 1 焼きなまし法

する．また，もうひとつ簡単な手法は貪欲法であり，問題に対する解をひとつ持っているとき，その解のその時々で次にとることが出来る選択肢のうち，最も一部を小さく変更することを考える．変更によって解良いものを採用して解を構築していく．計算コストはのスコアが改善するならば，その新たな解を採用し，非常に小さいが，発見できる解の質は悪くなる．

悪化するならばもとの解のままにする．この試行を反そこで，解の全ての候補を保持するのではなく，途復することで，次第により良い解が得られるようにな

中まで組み上がった解の暫定的なスコアに基づいてる．このアルゴリズムを山登り法と呼び，解に与える

上位 𝐾 個のみを保持する．このアルゴリズムをビー

変更を遷移，変更を加えた解を近傍と呼ぶ．

ムサーチと呼び，𝐾 をビーム幅と呼ぶ．図 1 に幅優山登り法の問題点は局所最適解に一度到達するとそ

先探索，ビームサーチ，貪欲法のアルゴリズムの比較

こから抜け出せず，大域的最適解を探索できなくなっを示す．描かれている数値は暫定のスコアを示しておてしまう点にある．そこで，焼きなまし法ではスコア

り，灰色のノードは保持する対象から外された解を意が悪化する遷移も確率的に受理することでより大域味する．

的な最適化を行えるようにする．ただしスコアが悪化

図 1 からも分かるように，幅優先探索はビームサーする遷移を受理し続けていると局所最適解にさえ至チにおいて 𝐾 を無限大とした場合，また，貪欲法はらないため，反復試行の過程のうち序盤は受理しやす𝐾 を 1 とした場合であると一般化できる．そのため，

く，終盤にかけて受理しにくくする．この受理しやす

本研究においてはビームサーチという言葉で幅優先さのパラメータを温度と呼ぶ．遷移確率は温度を 𝑇 ，探索，貪欲法を含めて扱う．

スコアの悪化量を 𝐷 として 𝑒 −𝐷/𝑇 という指数関数が用いられることが一般的であるが， 𝐷 として悪化量

3 数理最適化プログラムの効率を高める手法（差）ではなく悪化の割合（比）を用いたり，指数関

3. 1 スコア計算の差分化

数ではなく線形な関数を用いたりといったバリエー

典型的で扱いやすい数理最適化問題として，巡回ションも存在する．また，温度の下げ方についても指セールスマン問題（TSP） [2] を題材にして説明する．

数関数的に下げたり，線形に下げたり，下げてから高TSP にはいくつかのバリエーションが存在するが，こ温へ戻すことを繰り返したりといった様々な手法が考こでは各頂点が 2 次元平面上に位置しており，2 点間えられる．焼きなまし法の適用にあたって大きくアルの距離がユークリッド距離であるようなものを考え

ゴリズムの性能を左右する部分であるのは，遷移の種

る．また，スタートは必ず頂点 0 とし，最後に頂点 0類，遷移確率関数の設定，温度スケジューリングの設に戻ることはせず，全ての頂点を訪問したらその時点

定などである．
山登り法や焼きなまし法のように，適当な解を一度で巡回を終えるものとする．この TSP に，訪問順序のうち適当な区間を反転する操作を遷移として焼き図1

幅優先探索，ビームサーチ，貪欲法の比較なまし法を適用する．最も素朴なアルゴリズムは以下の擬似コードで表される．
1: procedure TSP-SA-naive(state, iter, prob)
2:

score = pathDistance(state)3:

for 𝑖 = 0 . . . iter do

4:

nextState = randomFlip(state)5:

diﬀ = pathDistance(nextState) − score

6:

accept = 𝑇𝑟𝑢𝑒示す．現在の訪問順序が 3,5,1,0,4,6,2 であり，このう

7:

if diﬀ > 0 then

ち区間 [2, 5] を反転しようとしている．ここで有用な

8:

if prob(diﬀ, i) < rand(0, 1) thenaccept = 𝐹𝑎𝑙𝑠𝑒

9:10:

end if

図2

区間反転の際の経路長の変化

事実として，2 点間の距離がユークリッド距離である
ならば，頂点 𝑥 から頂点 𝑦 へ向かう辺も，頂点 𝑦 から頂点 𝑥 へ向かう辺も長さは変わらない．よって，区11:

end if間の反転を行う際，経路長のうち変化する部分は反12:

if accept then

転する区間の両端の 2 辺の長さのみである．そこで，

13:
14:

state = nextStateend if

その 2 辺の長さの変化のみ追跡することでスコアの変化を高速に得ることができる．図 2 で言えば，頂15:

end for点 5,1 間の距離と頂点 6,2 間の距離を引き，頂点 5.6

16:

return state間の距離と頂点 1,2 間の距離を足せばよい．この改善

17: end procedure

引数として初期状態 state，繰り返し回数 iter，遷移を行った焼きなまし法の擬似コードを以下に示す．
1: procedure TSP-SA(state, iter, prob)

確率関数 prob をとっている．毎回の繰り返しの中で

2:

score = pathDistance(state)

今の解の訪問順序の適当な区間を反転した状態を抽

3:

for 𝑖 = 0 . . . iter do

出し，その新たな経路長を計算して，もとの経路長か4:

ﬂipRange = randomRange()

らの変化をとる．遷移確率関数に応じて，状態を反転

5:

diﬀ = diﬀWhenFlip(ﬂipRange)

後のものへ変えるかそのままにするかを決める．

6:

accept = 𝑇𝑟𝑢𝑒

このアルゴリズムでは毎回の試行で解のスコアを

7:

if diﬀ > 0 then

計算しているが，これは大きな無駄となる． 7 頂点の8:

TSP について，区間反転の際に起こる変化を図 2 に

9:
10:

if prob(diﬀ, i) < rand(0, 1) thenaccept = 𝐹𝑎𝑙𝑠𝑒
end if図3

同一視できる解11:

end ifとこれは容易に数十行へ膨らんでしまう．配列の添字

12:

if accept thenなどを正確に合わせながらそのようなアルゴリズム

state = applyFlip(state)13:

end if

14:
15:

end for16:

return state

17: end procedure

を正しく実装し切るには労力を必要とし，プログラムの性能と記述の労力とのトレードオフを生んでいる．

3. 2 ハッシュ値による状態重複の除去
ビームサーチでは同時に複数個の解を保持するが，また，ビームサーチでも同様の考え方を活用するこ

本質的に同一視できるような状態の解を何個も保持とができる．TSP においてスタート地点の頂点 0 にするのは無駄であり，その中で最もスコアが良いもの

居る状態から始め，未訪問の頂点へ移ることを遷移とだけを残せばよい．

したビームサーチを考える．新たに別の頂点へ移った

例えば，図 3 のように別々の経路を辿って頂点 4 に際には暫定の経路に辺が 1 本足されることになるた居るような暫定の解が 2 つあり，それぞれ A，B とす

め，その辺の長さのみを足すことで新たなスコアが得る．この 2 つの解はどちらも同じく頂点 0，1，2，5

られる．

を訪問した上で頂点 4 に居るため，経路の長い解 𝐴

このような差分計算は大幅な高速化が行える一方を保持する意味はなく，より暫定の経路長の短い解 𝐵

で，プログラムが煩雑になりがちである．実際，区間のみ残せばよい．つまり，この TSP に対するビームを受け取ってスコア変化を得るような関数は以下のよ

サーチにおいて，解は (訪問済み頂点集合，現在居る

うに記述される．ここで区間は頂点番号のペアで表さ頂点) の組をもって同一視できることになる．ここで，れるものとし，配列 order に頂点の訪問順序が，配訪問済み頂点集合は多くの場合ビット配列を用いて管列 points に各頂点の座標があるものとする．

理することになるが，重複の除去のためにわざわざdouble check_diff(pair<int, int> tr) {int i = tr.first, j = tr.second;
return dist(points[order[i - 1]],points[order[j]])+ dist(points[order[j + 1]],points[order[i]])- dist(points[order[i - 1]],points[order[i]])- dist(points[order[j]],points[order[j + 1]]);}

配列の一致判定を行うとかえって大きなオーバーヘッ

1
2
3
4
5
6
7
8
9
10
11

ドを生んでしまい，全体としてのプログラムの性能が悪化しがちである．そこで，解の内部状態のうち重複判定に用いる情報からハッシュ値を保持し，そのハッ
シュ値を利用して重複判定を行う．本来同一視できないはずの解を誤って重複していると見なして除去してしまう可能性はわずかに生まれるが，ひとつの整数のこの例のように，スコアが単なる経路長の合計で表されるような単純な場合はあまり複雑なプログラムにはならないが，スコア関数が少し入り組んだものになるみを用いて判定が出来るようになるため大幅に高速化ができる．
例えば，ビット配列に関するハッシュ関数として，

下から 𝑖 ビット目が立っているような全ての 𝑖 に関し手の技術を要求することになる．

て 2𝑖 を加算し，それを素数 1000000007 で割ったものを考える．このとき，新たに頂点 𝑘 を訪れるなら

4 提案する DSL

ばハッシュ値には 2 𝑘 を加算して剰余をとればよい．

数理最適化問題を解く従来のプログラミングの問題

また，解のハッシュ値としてはさらに現在居る頂点の点を踏まえ，本研究で提案する DSL の概要を説明す

情報を組み合わせる必要があるため，2 つの値からさる．DSL プログラムは C++プログラムへ変換し，そらにハッシュ値を生成しなくてはならない．各データの C++プログラムを GCC 等の外部のコンパイラによ構造にハッシュ関数を考え，解の内部状態に変化を加りコンパイルして実行する．このような形式をとる利

えるたびにハッシュ値を更新し，複数のハッシュ値を点として，C++の豊富な標準ライブラリをそのまま使組み合わせたものを重複判定に用いる，という工程用できること，DSL コンパイラ側で典型的なコンパはとても煩雑なものである．さらに，ハッシュ関数のイラ最適化を実装せずとも既存のコンパイラの強力設計が不適切だと本来同一視するべきでない解のハッな最適化の恩恵を得られることが挙げられる．また，

シュ値が大量に衝突し，解を探索する性能を大きく落

C++プログラムとしてそのままコンテストサイトへのとしてしまう可能性もある．

提出にも使える．

また，焼きなまし法においても解のハッシュ値を活基本的な文法は汎用言語と大きく乖離させないこと用できる．局所探索法の一種であるタブーサーチ [4]で学習コストを抑える．クラスと継承の機能を備え，と呼ばれるアルゴリズムでは，一度探索した解をタDSL の標準ライブラリとして用意された問題クラス

ブーリストに一定期間登録する．そして近傍を生成すを継承して必要なメソッドを実装することで，実行速る際に，タブーリストに載っている解には移らないよ

度を重視しながらメタヒューリスティクスを最小限のうにする．この仕組みによって何度も同じ解へループ記述で簡単に適用できるようにする．実際に本 DSL

して探索が停滞することを防ぐことができる．つまで TSP に焼きなまし法とビームサーチを適用するプ

り，ビームサーチの場合と同様に解にハッシュ値を持

ログラムを記述したものを図 4、図 5 に示す．

たせ，タブーリストとして整数集合を管理すること

SAState と BSState はそれぞれ焼きなまし法とで，効率良くタブーサーチを実現することができる．

ビームサーチを適用するための事前に用意されたライブラリである．型引数として遷移の型を与えてこれ

3. 3 SIMD 命令の活用を継承し，それぞれのアルゴリズムに必要な要素をプCPU に搭載される Single Instruction Multiple Data

ログラマが各自考えて実装する．それらの準備が終（SIMD）命令はベクトル演算とも呼ばれ，1 命令で多わったら，main 関数などから数のデータに対して同じ演算を行うことができる．当

1
2
3
4
5
6

初はスーパーコンピュータ等において性能を追求する技術であったが，近年は家庭用 PC の CPU でも多くの場合搭載されている．例として Intel の AVX-512

state:TSP_SA;
after:TSP_SA = SA(state, 20000000,(T:double, diff:double) => {exp(-diff/T/500)});

は 512 ビットのベクトルレジスタを持っており，32のように実際にメタヒューリスティクスのアルゴリズ

ビットのデータであれば 1 命令で 16 個を同時に処理

ムを呼び出し，実行することができる．このような効することができる．数理最適化プログラムにおいても率的な開発を実現するためのいくつかの特徴についSIMD 命令をうまく活用することで大幅な高速化が達て個別に説明する．

成できる場合がある [1]．一方で，機械語とそのまま対応した組み込み関数を直接書くとプログラムの可4. 1 メタヒューリスティクスの抽象化

読性が損なわれ，コード量も大きく増える．また，命TSP に焼きなまし法やビームサーチを適用する際

令の種類や仕様を熟知している必要があるため，書きの考え方を踏まえ，より一般的に，様々な問題にメタ

1
2
3
4
5
6
7
8
9
10
11
12
13
14

TSP_SA := class(SAState<Pair>){
order:vector<int>;
init := { order = range(0,n); };?score := {(0..(n-1)).sum(d: i =>dist(points[order[x:i]],points[order[y:i+1]]));};
get_transition := { rand_pair(1,n-1); };accept_transition := (tr)=>{@score(d(tr.0-1):y->tr.1,d(tr.1):x->tr.0);
reverse(order,tr.0,tr.1+1);
};
};

図4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

TSP_BS := class(BSState<int>){
order:vector<int>;#visited:vector<bool>;#now:int;
init := { now = 0; };?score := {(0..order.size-1).sum(d: i =>dist(points[order[i]],points[y:order[i+1]]));};
enumerate_transitions := {(0..n).filter(i => !visited[i]);};accept_transition := (tr)=>{@score(+d(order.size-1):y->tr);order.push_back(tr);visited[i] = true;
now = tr;};};

焼きなまし法図5

ビームサーチヒューリスティクスを適用するにはアルゴリズムをどによって自動で生成し得る内容である．区間反転を遷のような要素に分解すれば良いかを表 1,2 に示す．

移とした TSP における例では，反転する区間の両端抽象化された要素に対応する，TSP に適用した際のの 2 辺の長さを計算し直していた．この操作は「スコ

具体例は右の列に示している．これらをそれぞれ実装

アは 𝑁 − 1 本の辺の長さの総和である」という事実とし，メタヒューリスティクスのアルゴリズム本体のラ「訪問順序のうちの区間 [𝑖, 𝑗] を反転したとき，𝑖 − 1

イブラリに与えることで実行することができるように番目から 𝑖 番目へ至る辺と 𝑗 番目から 𝑗 + 1 番目に至なる．また，実際に実行する際には焼きなまし法である辺の長さが変わる」という事実から導出される．しれば遷移確率関数やイテレーション回数，ビームサー

たがって，この 2 つの事実を処理系が解釈することがチであればビーム幅などのパラメータも考える必要できれば，差分計算の処理を自動で生成することがでがある．これらは解法の実装とは独立させ，アルゴリ

きる．

ズムを実行するたびに引数として与えるものとする．

これを実現するため，まずスコア関数の計算の内容

本来焼きなまし法とビームサーチは全く異なるアを構造化された形式で処理系が認識できる必要があ

ルゴリズムであるが，このように抽象化を行うと，考る．C++のような既存の言語ではそのような記述は困える必要がある要素は共通したものになる．2 つの違難であるため，DSL では以下のように特殊な形式のいは遷移をひとつ抽出するか，すべて列挙するかのみメソッドとして宣言的な記述をサポートする．この記である．そのため，焼きなまし法を適用するプログラ

述は，図 4，図 5 で共通している．

ムを書いた後にビームサーチも試したいような場合，

1
2
3
4
5
6

改めてビームサーチのためのプログラムを書き直さなくても大部分を流用することで，効率よくプログラ
ミングを行うことができる．

?score := {// 途中のノードに d，x，yとタグを付ける(0..(n-1)).sum(d:i => dist(points[order[x:i]],points[order[y:i+1]]));};

ここで，スコアを計算する過程の式には，スコアがど

4. 2 スコア差分計算の自動化

う変化するかを後で指定する際のためにタグを付け

メタヒューリスティクスの実装において，スコアのている．d は引数として i を受け取って前から i 番目

差分計算はバグを生みやすい要素である．一方で愚直の辺の長さを計算する関数であり，x と y は何も手をに毎回スコア計算を行う処理から差分のみを計算し加えなければそれぞれ verb—i—と i+1 に相当する変直す処理への書き換えは機械的な部分が多く，処理系数である．この記述から，処理系は図 6 に示すよう

表1

抽象化した焼きなまし法

抽象化された要素

TSP における例

プログラムとの対応解がもつ情報スコアの計算法
遷移の型
遷移の抽出法
ある遷移を受理した時のスコア変化
ある遷移を受理した時の処理

訪問順序
𝑁 − 1 本の辺の長さの総和
整数のペアとして表される，特定の区間[1, 𝑁 − 1] の範囲のランダムで異なる 2 整数
反転する区間の両端の 2 辺の長さが変わる
訪問順序のうちの区間を反転する

order?scorePair
get_transition@scoreaccept_transition

表2
抽象化された要素解がもつ情報スコアの計算法
遷移の型
遷移の列挙法
ある遷移を受理した時のスコア変化
ある遷移を受理した時の処理抽象化したビームサーチ
プログラムとの対応

TSP における例
訪問順序，訪問済み頂点集合，
現在居る頂点
途中までの辺の長さの総和次に訪れる頂点番号を示す 1 整数
未訪問の頂点番号全て
現在居る頂点と次に訪れる頂点の間の距離が足される
訪問順序，訪問済み頂点集合と現在居る頂点を更新する

order,visited,now?scoreint
enumerate_transitions@scoreaccept_transition

こともあり得る．そのため，区間を反転しているという操作だけからは，反転した区間全体の長さを計算し直す必要があるとしか読み取ることができない．
そのため，本 DSL では以下のように最低限のアノテーションを用いて変化箇所を指定する．これは図 4の焼きなまし法の場合である．
1
2
3
4

accept_transition := (tr) => {@score(d(tr.0-1):y->tr.1, d(tr.1):x->tr.0);
reverse(order,tr.0,tr.1);};

仮引数 tr の型は遷移の型，つまり整数の 2 つ組であり，tr.0 と tr.1 によってそれぞれの要素にアクセス
図6

構造化されたスコア関数

することができる．@score で始まる 1 行がアノテーションであり，ここでは 2 箇所の変化点を指定してな構造化された情報を得ることができる．

いる．1 つ目の d(tr.0-1):y->tr.1 の意味は，「スコ

この情報を用いて，スコア関数のうちの変化点を知

ア関数の計算における関数 d に，引数として tr.0-1

ることができれば差分計算の処理を自動で生成できが与えられたときは，ノード y の値を tr.1 で上書きる．しかし，「遷移を受理した際の解の内部状態の変する」というものである．例として，3.1 節の図 2 の化」のみから正しく変化点を定めることは困難であように現在の order が 3,5,1,0,4,6,2 で，反転しよう

る．TSP における例で遷移にともなって長さが変わるとする区間 tr が [2, 5] である時を考える．スコア関辺が 2 本で済むことは，距離がユークリッド距離であ数のうちの関数 d に引数 tr.0-1= 1 が与えられたとるために辺の方向を逆転しても長さが変わらない事

きの y の値が，そのままなら tr.0= 2 であるところ，

実に依存していた．しかしこのことは自明ではなく，

tr.1= 5 に上書きされる．これを用いて，変化前の辺問題の設定次第では方向を逆転すると長さが変わるの長さを引き，変化後の辺の長さを足す，という処理を生成することができる．

焼きなまし法においては遷移にともなう変化が特4. 4 SIMD による並列化

定の辺の長さの変更であったが，図 5 のビームサーチ

SIMD 命令によってメタヒューリスティクスのプロにおいては新たな辺が加わる．このような場合は以下

グラムの性能を向上させる方針としては大きく 2 通のように，+を前に指定することで単にその値が加え

りある [3]．ひとつは，ボトルネックとなっているよられる．逆に-とすれば辺を削除することになる．

うな特定の操作を並列化することでイテレーションを

1
2
3
4
5
6

accept_transition := (tr)=>{@score(+d(order.size-1):y->tr);order.push_back(tr);visited[i] = true;
now = tr;};

より多く回すものである．例えば行列にベクトルを掛けるような処理は SIMD によって顕著な高速化が見込める．しかし，これは適用できる局面が限られており，あまり汎用的なものではない．

差分計算にすることで計算量を落としている本質的

もうひとつの方針は，複数の解に対して並列してアな部分は，集約関数 sum において集約対象のうちのルゴリズムを実行し，最終的に最も良い解を選ぶとい

1 要素の変化を集約結果に伝播させることができる点

うものである．それぞれを完全に独立に実行する以外であった．sum であれば古い値を引いて新しい値を足に，途中で解が互いに影響を及ぼし合うような工夫もすだけでよいが，max のような関数では少し複雑にな可能であり，これを行うと遺伝アルゴリズムに近いアる．例えば，集約対象の値が {2, 6, 5, 8, 3} であるとす

ルゴリズムとなる．これは高速化と言うよりも解のる．現在の最大値は 8 である．このうち 8 が 4 へ変質を高める活用方法となるが，特定の問題に限定さ化したら新たな最大値がどうなるか，ということは，れることなく，汎用的に適用することができる．本研

最大値を管理しているだけではわからない．そのた究の DSL ではこちらを焦点として自動並列化を達成

め，データ構造として平衡二分探索木等を用い，常にすることを目指している．GPU や多数のプロセッサ

集約対象の値の集合を管理することで，動的に最大値による並列化は数多く研究されている一方で，SIMDを更新することになる．この場合は定数時間での更新によるものはまだあまり前例がない．

は行えず，𝑂 (log 𝑁) 時間が掛かる．

5 評価
4. 3 ハッシュ関数の自動生成とハッシュ値の自動更新

現時点では処理系のプロトタイプの実装を行い，スコアの差分計算を自動で生成するシステムを実現しまず，配列や集合など典型的なデータ構造に対するた．TSP に対して焼きなまし法とビームサーチを適ハッシュ関数は適切なものを標準で用意する．その上用するプログラムを C++と本 DSL のそれぞれで記述

で，解の内部状態のうちハッシュ値に含めたいプロ

し，プログラムの行数と 10 回の実行時間の平均を

パティを指定することで，それらを組み合わせたハッ比較した．実行環境の CPU は AMD Ryzen 7 5700U

シュ関数も自動で生成することができるようにする．

(1.80GHz × 8Core)，RAM は 16GB である．GCC に

この指定は以下のように，プロパティの宣言時に変数よるコンパイルでは最適化オプションの-O3 を指定し名の先頭に#を付加することで行う．

た．TSP の入力データは頂点数 𝑁 = 100 とし，各頂

TSP_BS := class(BSState<int>) {order:vector<int>;#visited:vector<bool>;#now:int;
init := { now = 0; }点の 𝑥 座標， 𝑦 座標はそれぞれ 0 から 10000 までの

1
2
3
4
5

また，遷移を受理した際の解の内部状態の変化に合わせてハッシュ値の更新を人力で記述しなくとも，データ構造に操作を与えるたびに自動で更新が行われるようにする．

整数でランダムに定めた．焼きなまし法においてはイ
テレーション回数を 2000 万回とり，ビームサーチにおいてはビーム幅を 200 とした．
結果を表 3 に示す．現在の DSL 処理系は C++で手書きしたプログラムと本質的に同じ内容のものを出力するよう設計しているため，実行時間に関しては余計な一時変数が要因と考えられるわずかな増加となっ表3

TSP での評価

焼きなまし法ビームサーチ

行数

実行時間 /ms

行数

実行時間 /ms

C++

25

688

23

253

DSL

12

693

18

257

ている．行数に関しては大きく削減され，特に焼きな

参考文献

まし法では半分以下となった．

[ 1 ] B. M. Shabanov1, A. A. Rybakov1, S. S. S.: Vectorization of High-performance Scientiﬁc Calculations Using
AVX-512 Instruction Set, Lobachevskii Journal of Mathematics, Vol. 5, No. 4(2019), pp. 580–598.
[ 2 ] Bellmore, M. and Nemhauser, G. L.: The Traveling
Salesman Problem: A Survey, Operations Research, Vol. 16,
No. 3(1968), pp. 538–558.
[ 3 ] D.Janaki Ram, T.H.Sreenivas, K. S.: Parallel Simulated
Annealing Algorithms, Journal of Parallel and Distributed
Computing, Vol. 37, No. 121(1996), pp. 207–212.
[ 4 ] Glover, F.: Tabu Search―Part I, ORSA Journal on Computing, Vol. 1, No. 3(1989), pp. 190–206.
[ 5 ] Goldbloom, A.: Data Prediction Competitions–Far Morethan Just a Bit of Fun, IEEE International Conference on
Data Mining Workshops, (2010), pp. 1385–1386.
[ 6 ] Rutenbar, R.: Simulated annealing algorithms: An
overview, IEEE Circuits and Devices Magazine, Vol. 5,
No. 1(1989), pp. 19–26.
[ 7 ] Sugie, Y. e. a.: Graph Minors from Simulated Annealing
for Annealing Machines with Sparse Connectivity, Theory
and Practice of Natural Computing, (2018), pp. 111–123.
[ 8 ] Takemoto Takashi, Mertig Normann, H. M.: FPGABased QBoost with Large-Scale Annealing Processor andAccelerated Hyperparameter Search, International Conference on ReConFigurable Computing and FPGAs (ReConFig), (2018), pp. 1–8.
[ 9 ] Uchigaito Hiroshi, Okamoto Mamoru, A. G.: Multiobjective Spatiotemporal Optimization of Transportation
and Power Management by using Multiple Electric Vehicles
in Nanogrid Networks, IEEE Electrical Power and Energy
Conference (EPEC), (2021), pp. 1–8.
[10] White, G. M.: Dynamic programming, the viterbi algorithm, and low cost speech recognition, IEEE International
Conference on Acoustics, Speech, and Signal Processing,(1978), pp. 413–417.

6 まとめと今後の課題
本研究では数理最適化問題にメタヒューリスティク
スを適用するプログラムを記述する際の問題点に着目し，アルゴリズムの抽象化について検討した．さらに，抽象化した要素のうち一部が冗長であることを踏
まえ，最低限の記述で残りの要素を補うシステムを備えた DSL を考案した．これは宣言的な記述とアノテーションを組み合わせることで達成される．処理系
は現時点でプロトタイプの実装を行い，巡回セールス
マン問題に焼きなまし法とビームサーチを適用するプログラムについて，C++で記述したものとほとんど同じ実行性能でプログラムの行数を大きく削減できることを確認した．
今後の課題として，SIMD 命令を活用した自動並列化が行えていないため，まずは手書きによる並列化のノウハウを蓄積し，それを処理系に実装することが挙げられる．また，解のハッシュ値によるビームサーチ
での状態重複の除去やタブーサーチの実現も自動化
できていないため，この実装も今後行い，より多くの問題を本 DSL を用いて記述・評価し，有効性を検証していく予定である．