最大クリーク問題に対する
探索頻度情報にもとづく反復
k-opt
局所探索法の性能
Performance of Iterated k-opt Local Search based on
Search Frequency Information for the Maximum Clique Problem
金原 一歩
1片山 謙吾
1,2∗富田 悦次
3松崎 空良
4Kazuho KANAHARA
1Kengo KATAYAMA
1,2Etsuji TOMITA
3Sora MATSUZAKI
41
岡山理科大学大学院 工学研究科 情報工学専攻
1
Graduate School of Engineering, Okayama University of Science
2
岡山理科大学 工学部 情報工学科
2
Department of Information and Computer Engineering, Okayama University of Science
3
電気通信大学 先進アルゴリズム研究ステーション
3
The Advanced Algorithms Research Laboratory, The University of Electro-Communications
4
電気通信大学大学院 情報理工学研究科 情報・ネットワーク工学専攻
4
Graduate School of Informatics and Engineering, The University of Electro-Communications
Abstract: We present an effective metaheuristic algorithm, called Iterated k-opt Local Search based on Search Frequency Information (IKLS-SFI), for the maximum clique problem (MCP). IKLS-SFI is a new improved algorithm of the previous IKLS shown in EvoCOP 2007 (LNCS 4446, pp.84–95). The major and significant alteration is to explicitly and thoroughly search unexplored solutions by k-opt local search (KLS) with a vertex-selection method based on the Search Fre-quency Information in which the freFre-quency of each vertex contained in the solutions obtained by KLS performed in IKLS-SFI is counted, instead of basing on the vertex degree information. Computational results show that the proposed IKLS-SFI obtains better results than the previous IKLS for hard benchmark graphs and achieves performance competitive with the state-of-the-art metaheuristic algorithms for the MCP.
1
はじめに
組合せ最適化問題に対するアルゴリズムは，一般に 厳密解法と近似解法に大別される．厳密解法は最適解 の算出を目的とし，近似解法は最適解に近い準最適解 （または近似解と呼ぶ）を実用時間内に算出することを 目的としている．近年では，代表的な組合せ最適化問 題である最大クリーク問題 (maximum clique problem, MCP) [15, 13] に対して，分枝限定法にもとづく厳密 解法と，局所探索法にもとづく近似解法の融合が行わ れている [15, 13, 14, 9, 10]．その基本アイデアは，厳 密解法の前処理として，近似解法により良好なクリー クを短時間に求め，そのクリークサイズを下界として 分枝限定操作において有効に活用することで厳密解法 の高速化をはかるものである．特に文献 [14, 9, 10] で ∗連絡先：岡山理科大学 工学部 情報工学科 〒 700-0005 岡山県岡山市北区理大町 1-1 E-mail: [email protected] は，Tomita らが開発した厳密解法に，Katayama らに よる近似解法の k-opt 局所探索法 (variable k-opt local search, KLS) [5] またはその発展である反復 k-opt 局所 探索法 (iterated KLS, IKLS) [6] を前処理として導入 することで，グラフ例題によっては数万倍の高速化に 寄与することが示されている．上述の k-opt 局所探索法 KLS [5] は，Lin と Kernighan による可変深度探索法 (variable depth search, VDS) [7, 8] のアイデアにもとづき，MCP に応用した局所探索法 である．その発展として，Katayama らは，この KLS を導入した反復 k-opt 局所探索法 IKLS [6] を開発し， 多くの DIMACS ベンチマークグラフに対して既知の 最良解値に一致する高品質なクリークを算出できるこ とを示している．従来の KLS におけるクリーク拡大の 基本アイデアは，現在解（クリーク）に隣接する，追 加可能な頂点集合から高次数の頂点を選び，現在解に 追加することで，より大きなクリークの算出を目指す 人工知能学会研究会資料 SIG-FPAI-B803-06
ものである．高次数の頂点は大きなクリークに含まれ る傾向にあることから，このような知見にもとづくク リークの拡大処理は，近似解法において一般的に利用 されている．しかしながら，高次数情報にもとづくク リーク拡大処理は，MCP における大規模かつ困難な グラフや一部の特殊な “騙し構造”をもったグラフに対 しては必ずしも有効に働くとは限らない．よって，次 数情報とは異なる頂点選択方式を利用する近似解法が 提案されており，その代表例として，ペナルティ情報 を利用する Dynamic Local Search (DLS) [12] をはじ め，DLS と同様のペナルティ情報に加え，ランダム及 び次数情報にもとづく複数の頂点選択方式を切り替え る Phased Local Search (PLS) [11] などが知られてい る．その他，局所解から脱出する摂動の強さを調整す る Breakout Local Search (BLS) [2] などが提案されて おり，いずれも MCP を代表する高性能なメタ戦略ア ルゴリズムとして知られている．
本論文は，上述の高性能アルゴリズム DLS 及び PLS と同様に，頂点次数とは異なる情報として，探索頻度情 報（search frequency information, SFI）を考え，SFI を利用した反復 k-opt 局所探索法 (IKLS-SFI) を示す． この IKLS-SFI は，松崎・富田ら [10] による厳密解法の 前処理として利用した近似解法であり，従来研究 [9] 以 上に厳密解法の高速化に寄与することを確認している． IKLS-SFI は，EvoCOP 2007 (LNCS 4446, pp.84–95) で示した反復 k-opt 局所探索法 (従来 IKLS) [6] の改良 アルゴリズムであり，従来 IKLS よりも未探索のクリー クを重点的に探索する，多様化探索重視のメタ戦略ア ルゴリズムである．DIMACS ベンチマークグラフへの 適用を通して，提案法の有効性を示すとともに，騙し 構造のグラフの代表例である brock グラフに対しては， 従来 IKLS よりも良好なクリークを高頻度に算出でき ることを示す．更に，上述の高性能メタ戦略アルゴリ ズム PLS [11]，BLS [2] に匹敵する，若しくは対象グ ラフによっては同等以上の性能を有することを示す．
2
最大クリーク問題
頂点 (vertex) の集合 V = {1, . . . , n} とそれらの頂 点の対を両端とする無向辺 (undirected edge) の集合 E⊆ V ×V が与えられたとき，G = (V, E) を無向グラ フという．特に，全ての 2 頂点間に 1 つの辺が存在する 無向グラフを完全グラフという．V の部分集合 K⊆ V による誘導部分グラフ G(K) = (K, E∩ (K × K)) が完 全グラフのとき，すなわち，∀i, j ∈ K, i ̸= j に対して (i, j) ∈ E であるとき，K をクリークと呼ぶ．最大ク リーク問題 (MCP) [15, 13] とは，与えられたグラフ G に含まれるクリークの中で，頂点数|K| が最大である クリーク K を求める問題であり，NP-困難 [3] である．3
従来の
k-opt
局所探索法
組合せ最適化問題に対する近似解法において，局所 探索 (local search) は最も基本となるアルゴリズムであ る．代表的な局所探索法として，巡回セールスマン問 題に対する Lin-Kernighan 法 [8] をはじめ，グラフ分 割問題に対する Kernighan-Lin 法 [7] などがあげられ る．これらは，可変深度探索法（variable depth search, VDS），または可変 k-opt 局所探索法などと呼ばれ，組 合せ最適化問題における最も強力な局所探索法として 広く知られている．一般に VDS は，与えられた解に対 して，小さな近傍操作を連鎖的に適用することで到達 可能な解集合をあらためて大きな近傍と捉える局所探 索の一般化のアイデアである．以下，この VDS のアイ デアを MCP に応用した k-opt 局所探索法 (KLS) [5, 4] の基本アルゴリズムについて述べる． KLS の各反復における探索（k-opt 近傍探索）は，与 えられた初期解（現在のクリーク）CC に対して，探 索のサイクリング [16] を抑制することを基本とし，連 鎖的に複数個の頂点をクリークに追加 (Add) またはク リークから削除 (Drop) する操作によって生成可能な近 傍解の集合を得る．得られた近傍解の集合から最良解 CCbest，すなわち，k 回の Add・Drop 操作により得ら れた最良解を選び，その最良解 CCbestを次反復の初期 解 CC とする．この一連の処理をより良好なクリーク が得られなくなるまで反復し，k-opt 近傍探索にもとづ く局所最適解を出力し，KLS の処理を終了する．以下 では，上述の k-opt 近傍探索における Add 操作と Drop 操作の詳細について述べる． MCP に対する最も基本的な探索処理は，与えられ た解（クリーク）に対して追加可能な頂点を 1 つ選び 追加することを，追加可能な頂点が存在しなくなるま で繰り返すことである1．1 つの頂点 v からなるクリー ク CC が与えられたとき，頂点 v に隣接する頂点集合 N (v) ={i : i ∈ V, {i, v} ∈ E} から，1 頂点 u ∈ N(v) を選び，CC に追加（CC = CC∪ {u}）することでク リークサイズ|CC| が 1 つ増大する．KLS は，このよう な頂点追加（Add）操作を，CC に含まれる全頂点∀v ∈ CC に隣接する頂点集合 P A ={i : i ∈ V \CC, {i, v} ∈ E,∀v ∈ CC}（または {∩v∈CCN (v)}）にもとづき繰り 返すことで CC を拡大する．追加可能頂点集合 P A か ら 1 頂点を選び CC に追加する Add 操作は，MCP に 対する多くの解法で共通する重要な操作である． MCP における解の評価値は一般にクリークサイズ |CC| である．よって，上述の P A から 1 頂点を選び CC に追加することで評価値の改善となるが，P A からどの 頂点を 1 つ選んでも評価値の改善は 1 であるため，以降 の探索に有利となるような頂点を経験的に選ぶ場合が 多い．そのような指標として，高次数の頂点は大きなク 1この探索処理にもとづく解法を 1-opt 局所探索法 [5] と呼ぶ．リークに含まれる傾向にあることから，従来の KLS では P A の誘導部分グラフ G(P A) 内の各頂点 v∈ P A の次 数 degG(P A)(v) が最大の頂点 v を選び追加することを基 本とした．また，このような CC への Add 操作に伴い， P A が空集合となった場合は，CC から頂点を削除する Drop 操作を適用する．この際，CC に含まれる全頂点の うち，ある 1 頂点以外の全ての頂点に辺をもつ頂点の集 合 OM ={i : i ∈ V \CC, |N(i) ∩ CC| = |CC| − 1} を もとに，Drop 操作直後の追加可能頂点集合サイズ|P A| が最大となる頂点 v を CC から削除（CC = CC\{v}） する2．KLS では，上述の Add 操作と Drop 操作による k-opt 近傍探索の実現のために，移動候補頂点集合 P を 設けることで，KLS における探索のサイクリング [16] を抑制し，より大きな近傍を効率的に探索する．その 他の詳細については文献 [5, 4] を参照されたい．
4
探索頻度情報にもとづく
IKLS
組合せ最適化問題に対するメタ戦略の基本原理とし て，探索の集中化（intensification）と多様化（diver-sification）が知られており，高性能なメタ戦略の設計 においては，これらの相反する基本原理をバランスよ くあわせもつことが重要である．MCP に対する従来の IKLS [6] は，KLS [5] によって強い集中化探索を行い， 局所解からの脱出をはかる突然変異処理（kick と呼ぶ） と，探索の停滞が生じた際に他の探索空間へ強制的に移 動するリスタート処理によって多様化探索を実現して いる．上述したように従来の KLS は，P A の誘導部分 グラフ G(P A) 内の各頂点 v∈ P A の次数 degG(P A)(v) が最大の頂点 v を逐次選び，CC に追加することを基本 としたが，MCP における困難な一部の特殊な騙し構造 のグラフに対しては必ずしも有効とは限らない．特に， DIMACS ベンチマークグラフ群における brock グラ フは，その典型例であり，従来の KLS のような，高次 数の頂点を逐次選択する探索法3の場合には最適なク リークを算出しづらくしたグラフとして知られている． そのような困難なグラフに対しても有効に働くアルゴ リズムの設計においては，より巧妙な多様化探索の導 入が必要と考えられる．そのような観点から，多様化 探索をより重視したメタ戦略アルゴリズムとして，従 来 IKLS [6] の改良アルゴリズム IKLS-SFI を提案する．4.1
提案法の概要と探索頻度情報
提案する IKLS-SFI の疑似コードを図 1 に示す．提案 法は，従来の IKLS と同様に３つの探索プロセス（局所 探索法 KLS（Lines 2, 5, 9），突然変異処理 LEC-Kick 2OM に対して存在する辺の数が最少の頂点 v を CC から選び 削除することで，その削除頂点 v に隣接しない OM の頂点群は（v を CC から削除した時点で）P A になり，|P A| を最大化できる． 3従来 KLS [5] の他に，高次数の頂点を逐次選択する高性能メタ戦略として，Reactive Local Search [1] がよく知られている．
procedure IKLS-SFI input: graph G = (V, E); output: best clique Cbest in G; begin
1 generate C; compute P A and OM ; initialize SF I; 2 C := KLS(C, P A, OM, SF I); update SF I; Cbest := C;
3 repeat
4 C := LEC-Kick(C, P A, OM );
5 C := KLS(C, P A, OM, SF I); update SF I;
6 if|C| > |Cbest| then Cbest := C; endif
7 if restart=true then
8 generate C; compute P A and OM ; 9 C := KLS(C, P A, OM, SF I); update SF I;
10 if|C| > |Cbest| then Cbest := C; endif
11 endif 12 until terminate=true; 13 return Cbest; end; 図 1: 提案法 IKLS-SFI の疑似コード （Line 4）及びリスタート処理（Lines 7–11））で構成す る，シンプルなメタ戦略アルゴリズムである．提案法に おける大きな特徴は，探索頻度情報（search frequency information, SFI）を利用することである． 最大クリーク問題 MCP における SFI とは，局所探 索によって到達した局所解（クリーク）に含まれる各 頂点の探索回数（頻度）を数えた情報である．頂点の 探索頻度値は，V の全ての頂点 v それぞれに対応づけ て SF I(v) と表記する．頂点 v の探索頻度値 SF I(v) が 大きければ，その頂点 v はこれまでよく探索された頂 点であり，逆に小さければ，十分に探索が行われてい ない頂点となる．よって，多様化した探索を実施する ために，探索頻度の少ない頂点を優先してクリークに 追加することを考える．このような頂点追加の方式に よって，これまで十分に探索されていない頂点を含ん だクリークを優先して探索することになるため，ラン ダムな頂点追加の方式と比べても，その多様化探索の 度合いはより強いものと考えられる． したがって提案法は，SFI の利用によって未探索のク リークを優先して探索可能であることから，多様化探 索重視のメタ戦略アルゴリズムと捉えることができる． 以下，提案法の構成要素である，局所探索 KLS，突 然変異処理 LEC-Kick 及びリスタート処理の各探索プ ロセスの詳細についてそれぞれ述べる．
4.2
局所探索法 KLS
提案 IKLS における局所探索プロセス KLS（図 1 の Lines 2, 5, 9）の疑似コードを図 2 に示す．KLS の各 反復における基本処理（k-opt 近傍探索）は，上述の通 り，現在の解 CC に対し，複数個の頂点を連鎖的に追 加・削除する操作の処理 (それぞれ Add フェーズ (図 2 の Lines 4–7)，Drop フェーズ (図 2 の Lines 8–11) と呼 ぶ) によって構成する．従来 KLS との大きな相違点は， Add フェーズにおける頂点追加方式の違いであり，従 来の高次数頂点追加の方式に代わり（つまり，頂点次数 の情報を一切利用せずに），探索頻度情報（SFI）にもprocedure KLS(CC, P A, OM , SF I) begin
1 repeat
2 CCprev :=CC, D:=CCprev , P :={1, ..., n}, g:=0, gmax:=0;
3 repeat
4 if|P A ∩ P | > 0 then // Add Phase
5 select a vertex v with minv∈{P A∩P } { SF I(v) }; 6 CC := CC∪ {v}, g := g + 1, P := P \{v};
7 if g > gmax then gmax := g, CCbest := CC;
8 else //Drop Phase (if{P A ∩ P } = ∅)
9 select a vertex v∈ {CC ∩ P } such that
the resulting|P A ∩ P | is maximized;
10 CC := CC\{v}, g := g − 1, P := P \{v};
11 if v is contained in CCprev then D := D\{v};
12 endif
13 update P A and OM ; 14 until D =∅;
15 if gmax > 0 then CC := CCbest else CC := CCprev ;
16 until gmax ≤ 0; 17 return CC; end; 図 2: SFI 利用の k-opt 局所探索法の疑似コード procedure LEC-Kick(CC, P A, OM ) begin
1 if all i∈ CC are disconnected to all j ∈ V \CC then
2 select a vertex v∈ V \CC randomly;
3 compute P A and OM ;
4 CC :=∅; CC := CC ∪ {v}; return new clique CC;
5 endif
6 select a vertex v∈ V \CC randomly
with the lowest edge number to vertices of CC. 7 drop vertices from CC that are not connected to v; 8 update P A and OM ;
9 return new clique CC; end; 図 3: LEC-Kick の疑似コード とづく頂点追加方式を利用する点である．具体的には， 現在解 CC に追加可能頂点集合 P A から，SFI の最小 値の頂点 v を選び（Line 5），CC に追加する．よって， SFI にもとづく KLS は，より大きな未探索クリークを 優先して探索する．一般に局所探索は集中化探索を担 う中心的なアルゴリズムであるが，提案 IKLS-SFI に おける KLS は，集中化だけでなく多様化した探索もあ わせもつ局所探索法と捉えられる． 以下，その他の相違点について述べる．従来 KLS で は，Add 操作及び Drop 操作の連鎖的な適用による近 傍解の集合を生成する過程において，探索のサイクリ ングの抑制の目的から，移動候補頂点集合 P (Line 2) によって，既に追加または削除された頂点が再び追加・ 削除されることがないようにしたが，提案 IKLS-SFI における KLS では，IKLS-SFI で算出されている最良 クリークのサイズ|Cbest| を更新する Add 操作の場合 は KLS の移動候補頂点集合 P の制約を緩和する．
4.3
突然変異処理及びリスタート処理
提案法 IKLS-SFI において多様化探索を担う突然変異 処理（図 1 の Line 4）とリスタート処理（図 1 の Lines 7–11）について述べる． LEC-Kick（突然変異処理）は，局所探索により得られ た局所解から脱出することを目的とする処理であり，図 3 にその疑似コードを示す．LEC-Kick (lowest-edges-connectivity-based kick) [6] は，対象グラフ G の頂点 間の隣接関係にもとづき，局所解（クリーク）から削 除する頂点数を適応的に決定するパラメータレスの突 然変異である．これは，2 つのプロセス（例外処理と本 処理）から構成される．まず，例外処理 (Lines 1–5) と して，与えられたクリーク CC に対して，グラフ G に おける CC 以外の頂点群 V\CC が CC に全く隣接して いない場合は，後述の本処理を適用することができな い．よって，V\CC から 1 頂点をランダムに選択し，そ の 1 頂点を新たなクリークとする．本処理 (Lines 6–9) は，グラフ G の V\CC において，CC の頂点群と最低 1 頂点以上隣接する頂点集合から，隣接する数が最も 少ない頂点 v をランダムに選択する (Line 6)．次いで， 頂点 v とそれに隣接する CC の頂点群で新たなクリー クを構成する (Line 7)．なお，従来 IKLS [6] では，突 然変異の本処理によって CC から削除された頂点群は， 次回の KLS の探索における 1 回目の反復において，移 動候補頂点集合 P (図 2 の Line 2) から除外する，探索 の多様化に配慮した処理を行ったが，提案 IKLS では， SFI 利用の KLS によって十分な多様化探索をあわせも つことから，集合 P からの除外処理は行わない． リスタート処理 [6] は，探索に停滞が生じた際に実 行する，最も簡便な多様化探索の処理であり，図 1 の Lines 7–11 で実行される．リスタート処理の条件（図 1 の Line 7）は，反復処理（Lines 3–12）において，得ら れた最良解 Cbestが反復回数として|Cbest| 回以上更新 されなかった場合とする．この条件のもと，他の探索空 間へ移動するために，グラフ G の 1 頂点 v を V\Cbest からランダムに選びクリークとする．その後，KLS を 適用し (Line 9)，反復処理（Lines 3–12）を繰り返す．5
実験結果
提案法 IKLS-SFI の探索性能を評価するために，従 来の IKLS [6] との性能比較実験を実施するとともに， MCP に対する高性能なメタ戦略アルゴリズムとして知 られている Breakout Local Search(BLS) [2] と Phased Local Search(PLS) [11] の報告結果をもとに探索性能 の比較を行った． 対象とする問題例は，様々なタイプのグラフ例題を 集めた DIMACS ベンチマークグラフの 80 グラフから， 標準的な 37 グラフ4と，上述した brock の他グラフ全 てを含めた計 43 グラフを選び，各アルゴリズムを評価 した．提案 IKLS-SFI と従来 IKLS の試行回数は各グ ラフに対してそれぞれ 100 回とし，各アルゴリズムに 4http://archive.dimacs.rutgers.edu/pub/challenge/graph/ benchmarks/volume/Clique/おける初期解は対象グラフ G の頂点群 V からランダム に選んだ 1 頂点を初期クリーク（初期解）とした．各 IKLS の反復の打ち切り終了条件は，各グラフにおい て知られている最適解値（または既知の最良解値）に 一致するクリークを算出した場合，または各グラフに 対して，頂点数|V |(= n)× 1000 回の反復を実行した 場合とした．各 IKLS は C++でコード化し，コンパイ ラは最適化オプション-O3 を付与した g++（Ver. 8.1） である．全ての実験は，Ubuntu 18.04 を OS とする計 算機（CPU: Intel Core i7 3.6GHz, RAM:15.6GiB）上 で実行した．DIMACS Machine Benchmark 5の実行
における，この計算機の CPU 時間は，r300.5 に対し て 0.13(s)，r400.5 に対して 0.79(s)，r500.5 に対して 3.04(s) であり，以降に示す比較解法 BLS 及び PLS の 計算時間は，それぞれの論文 [2, 11] で報告されている DIMACS Machine Benchmark の報告時間にもとづき 校正した． 表 1 に，対象グラフそれぞれに対して，提案 IKLS-SFI，従来 IKLS をそれぞれ 100 回試行した実験結果と， 高性能メタ戦略アルゴリズムの BLS 及び PLS のそれ ぞれ 100 試行の報告結果を示す．表 1 の左欄から，問題 例の名称 name，既知の最良解値 BR，頂点数 n，辺密 度 ρ を示し，以降，提案 IKLS-SFI，従来 IKLS，BLS， PLS それぞれに対して，100 回試行中に BR に一致す るクリークを算出した成功率 Success (Scs)，最良解値 Best，平均解値 Avg，最良解 Best が得られるまでの平 均時間 t(s) を示した．なお，Scs 欄における “( )”付き の表記は，Best 値のクリークを算出した回数（率）で あり，BR に一致するクリークは算出できなかったこと を示している．加えて，表中の “—”は比較解法の論文 において結果の報告・掲載が無かったことを示してい る．更に表中の太字について，各アルゴリズムで性能 差の生じたグラフ例題のみを対象として，各アルゴリ ズムの同欄の結果比較のもとで最も良好なクリーク算 出の結果に対して太字とした． 表 1 の結果から，提案 IKLS-SFI は，対象 43 グラフ 中，C2000.9 を除く 42 グラフにおいて，BR に一致する 高品質なクリークを算出しており，その成功率 Scs は， brock800 1 の 1 例題に対して 97 ％（100 試行中 97 回 BR 値を算出）であったものの，（C2000.9 と brock800 1 を除く）他の 41 グラフの全てで 100 ％を達成してい る．C2000.9 に対して，従来 IKLS は提案 IKLS-SFI と 同じ Best 値 79 のクリークを算出した．PLS において は，100 試行中 100 回で 78 のクリークサイズが Best 値として報告されている一方で，BLS は，唯一 BR 値 に一致するサイズ 80 のクリークを 100 試行中で 1 回 算出したことが報告されている．DIMACS グラフ群に おいて最も困難な大規模グラフの一つとして知られて 5dmclique, http://archive.dimacs.rutgers.edu/pub/dsj/clique/
いる MANN a81（や MANN a45）に対して，BLS と PLS は，BR 値に一致するクリークの算出は困難であった が，提案・従来 IKLS の両アルゴリズムは，成功率 100 ％を比較的短時間に達成しており，BLS と PLS の探 索性能を大きく上回っていることを確認できる．他の 大規模かつ困難グラフである keller6 に対して，PLS の成功率は 36 ％であったが，各 IKLS は比較的短い平 均時間のもとで成功率 100 ％を達成した．高次数頂点 を逐次選択する従来 IKLS について，brock800 グラフ の 4 例題に対する成功率 Scs は，BLS と同様に低め， 若しくは比較的計算時間を要することがわかる．一方， 提案法は，上述の通り brock800 1 で成功率が 97 ％で あったのものの，残り 3 つの brock800 グラフに対し ては PLS と同様に 100 ％を達成した．このように，探 索頻度情報 SFI にもとづく提案 IKLS-SFI は，他の中 小規模の brock グラフに対しても比較的短時間に成功 率 100 ％を達成していることから，騙し構造を有する brock グラフ全般及び上述の MANN グラフを含めたより 広範な問題例に対しても有効に機能することを示した． 以上より，提案法 IKLS-SFI は，多くの問題例で他 の高性能メタ戦略アルゴリズムに匹敵する，若しくは， 問題例によっては同等以上の探索性能を有することを 明らかにした．
6
おわりに
本論文では，最大クリーク問題に対して，探索頻度情 報 SFI にもとづく反復 k-opt 局所探索法（IKLS-SFI） を提案した．評価実験の結果から，提案法 IKLS-SFI は，多くの問題例で他の高性能メタ戦略の探索性能に 匹敵する，若しくは，問題例によっては同等以上の性 能を有することを明らかにし，その有効性を示した． 今後の課題として，他のベンチマークグラフへ適用 した際の探索性能を明らかにすることや，高品質なク リークをより効率的に算出する改良法の検討などがあ げられる．参考文献
[1] R. Battiti and M. Protasi. Reactive local search for the maximum clique problem. Algorithmica, Vol. 29, No. 4, pp. 610–637, 2001.
[2] U. Benlic and J.-K. Hao. Breakout local search for maximum clique problems. Computers and
Operations Research, Vol. 40, No. 1, pp. 192–206,
2013.
[3] M.R. Garey and D.S. Johnson. Computers and
Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, 1979.
表 1: DIMACS グラフに対する提案法，従来法の実験結果及び高性能メタ戦略 BLS，RLS の報告結果
instance 提案 IKLS-SFI 従来 IKLS BLS [2] PLS [11] name BR n ρ Scs Best Avg t(s) Scs Best Avg t(s) Scs Best Avg t(s) Scs Best Avg t(s) C125.9 34 125 0.898 100 34 34.00 0.000 100 34 34.00 0.000 100 34 34.00 0.000 100 34 34.00 0.000 C250.9 44 250 0.899 100 44 44.00 0.004 100 44 44.00 0.001 100 44 44.00 0.000 100 44 44.00 0.000 C500.9 57 500 0.900 100 57 57.00 0.873 100 57 57.00 0.233 100 57 57.00 0.000 100 57 57.00 0.039 C1000.9 68 1000 0.901 100 68 68.00 32.588 100 68 68.00 9.051 100 68 68.00 19.996 100 68 68.00 0.394 C2000.9 80 2000 0.900 ( 2) 79 76.99 621.889 ( 2) 79 76.96 717.726 1 80 78.60 2694.800 ( 100) 78 78.00 23.613 DSJC500 5 13 500 0.502 100 13 13.00 0.009 100 13 13.00 0.016 — — — — 100 13 13.00 0.002 DSJC1000 5 15 1000 0.500 100 15 15.00 0.514 100 15 15.00 1.048 — — — — 100 15 15.00 0.098 C2000.5 16 2000 0.500 100 16 16.00 1.080 100 16 16.00 3.145 100 16 16.00 1.624 100 16 16.00 0.152 C4000.5 18 4000 0.500 100 18 18.00 279.168 100 18 18.00 951.684 100 18 18.00 366.650 100 18 18.00 31.323 MANN a27 126 378 0.990 100 126 126.00 0.004 100 126 126.00 0.001 100 126 126.00 19.716 100 126 126.00 0.007 MANN a45 345 1035 0.996 100 345 345.00 34.664 100 345 345.00 28.662 ( — ) 342 340.82 — ( 100) 344 344.00 6.020 MANN a81 1100 3321 0.999 100 1100 1100.00 24.028 100 1100 1100.00 5.796 ( — )1094 1092.17 — ( 100)1098 1098.00 56.441 brock200 1 21 200 0.745 100 21 21.00 0.004 100 21 21.00 0.003 100 21 21.00 0.006 100 21 21.00 0.001 brock200 2 12 200 0.496 100 12 12.00 0.007 100 12 12.00 0.025 100 12 12.00 0.101 100 12 12.00 0.006 brock200 3 15 200 0.605 100 15 15.00 0.002 100 15 15.00 0.040 100 15 15.00 0.319 100 15 15.00 0.006 brock200 4 17 200 0.658 100 17 17.00 0.052 100 17 17.00 0.028 100 17 17.00 0.241 100 17 17.00 0.016 brock400 1 27 400 0.748 100 27 27.00 2.753 100 27 27.00 5.608 100 27 27.00 67.998 100 27 27.00 0.225 brock400 2 29 400 0.749 100 29 29.00 0.360 100 29 29.00 2.129 100 29 29.00 9.746 100 29 29.00 0.079 brock400 3 31 400 0.748 100 31 31.00 0.112 100 31 31.00 0.458 100 31 31.00 2.845 100 31 31.00 0.038 brock400 4 33 400 0.749 100 33 33.00 0.048 100 33 33.00 0.261 100 33 33.00 1.776 100 33 33.00 0.022 brock800 1 23 800 0.649 97 23 22.94 26.880 19 23 21.38 59.652 70 23 22.40 878.392 100 23 23.00 6.298 brock800 2 24 800 0.651 100 24 24.00 10.292 32 24 21.96 66.716 68 24 23.04 603.875 100 24 24.00 5.108 brock800 3 25 800 0.649 100 25 25.00 13.921 52 25 23.56 57.035 84 25 24.52 571.377 100 25 25.00 3.156 brock800 4 26 800 0.650 100 26 26.00 4.574 88 26 25.40 47.868 100 26 26.00 337.042 100 26 26.00 1.369 gen200 p0.9 44 44 200 0.900 100 44 44.00 0.002 100 44 44.00 0.001 100 44 44.00 0.000 100 44 44.00 0.000 gen200 p0.9 55 55 200 0.900 100 55 55.00 0.001 100 55 55.00 0.000 100 55 55.00 0.000 100 55 55.00 0.000 gen400 p0.9 55 55 400 0.900 100 55 55.00 0.333 100 55 55.00 0.270 100 55 55.00 1.238 100 55 55.00 0.052 gen400 p0.9 65 65 400 0.900 100 65 65.00 0.006 100 65 65.00 0.001 100 65 65.00 0.000 100 65 65.00 0.000 gen400 p0.9 75 75 400 0.900 100 75 75.00 0.002 100 75 75.00 0.001 100 75 75.00 0.000 100 75 75.00 0.000 hamming8-4 16 256 0.639 100 16 16.00 0.000 100 16 16.00 0.000 100 16 16.00 0.000 100 16 16.00 0.000 hamming10-4 40 1024 0.829 100 40 40.00 0.002 100 40 40.00 0.002 100 40 40.00 0.011 100 40 40.00 0.001 keller4 11 171 0.649 100 11 11.00 0.000 100 11 11.00 0.000 100 11 11.00 0.000 100 11 11.00 0.000 keller5 27 776 0.752 100 27 27.00 0.015 100 27 27.00 0.006 100 27 27.00 0.000 100 27 27.00 0.011 keller6 59 3361 0.818 100 59 59.00 6.153 100 59 59.00 1.230 100 59 59.00 13.891 36 59 57.75 115.314 p hat300-1 8 300 0.244 100 8 8.00 0.001 100 8 8.00 0.001 100 8 8.00 0.000 100 8 8.00 0.000 p hat300-2 25 300 0.489 100 25 25.00 0.000 100 25 25.00 0.000 100 25 25.00 0.000 100 25 25.00 0.000 p hat300-3 36 300 0.744 100 36 36.00 0.001 100 36 36.00 0.001 100 36 36.00 0.000 100 36 36.00 0.000 p hat700-1 11 700 0.249 100 11 11.00 0.020 100 11 11.00 0.021 100 11 11.00 0.011 100 11 11.00 0.003 p hat700-2 44 700 0.498 100 44 44.00 0.001 100 44 44.00 0.001 100 44 44.00 0.000 100 44 44.00 0.002 p hat700-3 62 700 0.748 100 62 62.00 0.001 100 62 62.00 0.001 100 62 62.00 0.000 100 62 62.00 0.001 p hat1500-1 12 1500 0.253 100 12 12.00 2.077 100 12 12.00 3.321 100 12 12.00 2.308 100 12 12.00 0.686 p hat1500-2 65 1500 0.506 100 65 65.00 0.004 100 65 65.00 0.007 100 65 65.00 0.017 100 65 65.00 0.002 p hat1500-3 94 1500 0.754 100 94 94.00 0.016 100 94 94.00 0.016 100 94 94.00 0.017 100 94 94.00 0.007 [4] 金原一歩, 片山謙吾, 岡野傑士, 尾崎亮, 西原典孝, 舩曵信生. 最大クリーク問題に対する k-opt 局所 探索法の改良. 電子情報通信学会論文誌 (A), Vol. J101-A, No. 10, pp. 260–264, 2018.
[5] K. Katayama, A. Hamamoto, and H. Narihisa. An effective local search for the maximum clique problem. Information Processing Letters, Vol. 95, No. 5, pp. 503–511, 2005.
[6] K. Katayama, M. Sadamatsu, and H. Narihisa. Iterated k-opt local search for the maximum clique problem. In Evolutionary Computation
in Combinatorial Optimization, LNCS 4446, pp.
84–95. Springer, 2007.
[7] B.W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. Bell System
Technical Journal, Vol. 49, pp. 291–307, 1970.
[8] S. Lin and B.W. Kernighan. An effective heuris-tic algorithm for the traveling salesman problem.
Operations Research, Vol. 21, pp. 498–516, 1973.
[9] 松崎空良, 富田悦次, 長尾篤樹, 伊藤大雄, 若月光夫, 西野哲朗. 最大クリーク抽出アルゴリズム MCT の高速化. 情報処理学会研究報告 数理モデル化と 問題解決（MPS）2018-MPS-120, 2018. [10] 松崎空良, 富田悦次, 長尾篤樹, 伊藤大雄, 若月光 夫, 西野哲朗, 片山謙吾, 金原一歩. 最大クリーク 抽出アルゴリズム MCT の高速化（2）. 2018 年 度冬の LA シンポジウム, 2019.
[11] W. Pullan. Phased local search for the maximum clique problem. Journal of Combinatorial
Opti-mization, Vol. 12, No. 3, pp. 303–323, 2006.
[12] W. Pullan and H.H. Hoos. Dynamic local search for the maximum clique problem. Journal of
Ar-tificial Intelligence Research, Vol. 25, pp. 159–
185, 2006.
[13] E. Tomita. Efficient algorithms for finding maxi-mum and maximal cliques and their applications. In WALCOM 2017, LNCS 10167, pp. 3–15, 2017. [14] E. Tomita, K. Yoshida, T. Hatta, A. Nagao, H. Ito, and M. Wakatsuki. A much faster branch-and-bound algorithm for finding a maximum clique. In FAW 2016, LNCS 9711, pp. 215–226, 2016.
[15] Q. Wu and J.-K. Hao. A review on algorithms for maximum clique problems. European Journal of
Operational Research, Vol. 242, No. 3, pp. 693–
709, 2015.
[16] 柳浦睦憲, 茨木俊秀. 組合せ最適化—メタ戦略を 中心として—. 朝倉書店, 2001.
