最大クリーク問題に対する局所探索法と頂点選択方式

(1)

岡山理科大学紀要第41号Appll3-120(2005）

濱本明宏・片山謙吾＊・南原英生＊・成久洋之＊

岡山理科大学大学院工学研究科システム科学専攻

＊岡山理科大学工学部情報工学科

（2005年９月30日受付、2005年11月７日受理）

1．まえがき

頂点(vertex)の集合Ｖ＝｛1,…,､｝とそれらの頂点の対を両端とする無向辺(undirectededge)の集合

ＥｃＶ×Ｖが与えられた時，Ｇ＝(ⅨＥ)を無向グラフという．特に，全ての２頂点間に１つの辺が存在す

る無向グラフを完全グラフという．ｖの部分集合ｖｔｖによる誘導部分グラフＧ(v')＝(v',Ｅｎｖ'×ｖ'）

が完全グラフの時，すなわち，Ｗ,ｊＥＶ',ｊ≠ｊに対して(j,ｊ)ＥＥである時，Ｖ'をクリークと呼ぶ．最大クリーク問題(MaximumCliqueProblem,MCP)3)とは，与えられたグラフＧに含まれるクリークの中

で，頂点数最大のクリークを求める問題である．

ＭＣＰは実用上重要な問題であり，通信ネットワーク，符号理論，並列計算，パターン認識等の分野の基本問題として頻繁にあらわれる3)．ＭＣｐは組合せ最適化問題の一つであり，Ｎｐ-困難4)である．従って，多項式時間で厳密解を求めるアルゴリズムは存在しないであろうと考えられている．さらに，ＭＣＰの(近似

度の良い)近似解を得ることすらＮＰ完全のクラスに準じるほど困難であることが知られており，その他に

もＭＣＰの難しさを示すネガティブな報告がなされている．

組合せ最適化問題に対する高性能な近似解法の多くは，メタ戦略'8)にもとづくアルゴリズムであり，その基本構成は大域的および局所的な探索処理をバランス良く備えたものである．特に，局所的な探索処理を担う代表例は局所探索法(LocalSearch,Locallmprovement)であり，多くの組合せ最適化問題に対して優れた局所探索法が提案されてきた．局所探索法は近傍探索法とも呼ばれ，現在の解の近傍の中から良好

な近傍解への移動を繰り返すものである．

代表的な組合せ最適化問題である巡回セールスマン問題(TravelingSalesmanProblem,TSP)5)に対する優れた局所探索法として，ＬｉｎとKernighanによる局所探索法'4)が良く知られている．彼らの局所探索法は，可変深度探索(VariableDepthSearch,VDS)のアイデアにもとづいており，ＴＳＰに対する他の古典的解法（2-opt局所探索法や3-opt局所探索法等）の探索性能を上回る高性能な局所探索法である．ＴＳＰに対する近年のメタ戦略アルゴリズムの多くは，彼らの局所探索法を主力的な探索法として導入しており7)，現在では非常に大規模な問題例へも適用されるに至っている')．ＬｉｎとKernighanによるＶＤＳのアイデアは彼らによって同時期に適用されたグラフ分割問題'3)をはじめ，最近では他の研究者により，一般化割当問題19)，バイナリー２次計画問題8,16)や最大多様性問題9,12)等へも波及しつつある．これらの局所探索法はそれぞれの最適化問題において代表的な近似解法として知られているだけでなく，ＴＳＰの場合と同様に，

メタ戦略アルゴリズムを構成するための主力的な探索法9,12,17)である．

最近我々は,ＭＣＰに対する局所探索法として,ＶＤＳのアイデア13''4)にもとづくハーopt局所探索法(k-opt

LocalSearch,KLS)'1)を提案し，良好な結果を得た．ＫＬＳは，各反復において，現在のクリーク（解）から複数個の頂点を連鎖的に追加・削除する操作（それぞれＡｄｄ移動，Ｄｒｏｐ移動と呼ぶ）により構成され，

現在の解からそれらの操作によって生成可能な解の集合を改めて近傍と捉えることで，局所探索を行うアルゴリズムである．その特長は，比較的大きな近傍を効率良く探索する巧妙な近傍探索処理を施している

にも関わらず，パラメータ値の設定を必要としないシンプルさである．

ＫＬＳの性能を検証するために，第２回DIMACSImplementationChallengeWOrkshop6)で利用されたベンチマークグラフに適用した結果，そのワークショップで報告されていた最良解と多くのグラフにおいて同等以上の良質の解の算出に成功した．更に我々は，ＭＣＰに対する高性能なメタ戦略アルゴリズムとして広く知られている，Marchioriによる遺伝的局所探索法および反復局所探索法'5)，Battitiらによるタブー

(2)

MCP-k-opt-Local-Search(００，ＰＡ,ＯＭｄｅ９Ｃ(pA)）

ｂｅｇｉｎ

ｒｅｐｅａｔ

ＣＣｐ…:＝ＣＯ,Ｄ＝CCp…,Ｐ:＝｛1,…,､}’９:＝0,9,…:＝０；

ｒｅｐｅａｔ

ｉｆｌＰＡｎＰ|＞Ｏthen ／／AddPhase

findavertexuwithmaxびE{pAnp｝｛de9G(pA)(ひ)｝；

ifmultipleverticeswiththesamemaximumdegreearefbund thenselectonevertexuamongthemrandomly；

ＣＯ:＝ＣＣＵ{U}’９:＝９＋1,Ｐ＝ハ{U}；

ｉｆ９＞９ｍ・垂ｔｈｅｎｇｍａａｃ:＝９，Ｃｑｅｓｔ:＝ＣＯ；

ｅｌｓｅ

／／DropPhase(if{ＰＡｎＰ｝＝Ｏ）

findavertexuE｛ＣＯｎＰ}suchthattheresultinglPAlismaximized；

ifmultipleverticeswiththesamesizeoftheresultinglPAlarefOunｄｔｈｅｎｓｅｌｅｃｔｏｎｅｖｅｒｔｅｘｕａｍｏｎｇｔｈｅｍrandomly；

ＣＯ:＝ＣＯＷ）},ｇ:＝９－１，Ｐ:＝ハ{U}；

ifuiscontainedinOCp…ｔｈｅｎＤ;＝ＤＷ}；

ｅｎｄｉｆ

ｕｐｄａｔｅＰＡ,○Ｍ,andde9G(pA)(i),ＶｊＥＰＡ；

untilＤ＝０；

if9ma錘＞OthenCO:＝OC6estelseCC:＝CCb…；

ｕｎｔｉｌ９ｍａご≦Ｏ；

ｒｅｔｕｒｎＯＣ；

ｅｎｄ；

１２３４５６７８９０１１１

２３４５６７８９

１１１１１１１１

図１ＭＣＰに対するﾙｰopt局所探索法の擬似コード''）

探索法にもとづくReactiveLocalSearch2)との比較を通して，それらのメタ戦略と同等もしくは平均的により高品質の近似解を比較的短時間に算出可能であることを示した．

ＫＬＳはシンプルで高性能な局所探索法であるが，局所探索過程における頂点の追加・削除の手続き(頂点選択方式）に関しては改良の余地が残されていた．そこで本論文では，新しい頂点選択方式を採用した KLS(改良法)を示し，従来のKLS(従来法)との比較を通じて，改良法の探索性能を調査する．

2．ＭＣＰに対するh-opt局所探索法と頂点選択方式

本章では，我々が既に提案しているＭＣＰに対するh-opt局所探索法(KLS)について記述する．KLS11）

は，可変深度探索(VDS)13,14)のアイデアにもとづいている．ＶＤＳとは，与えられた解に対して比較的小さな近傍操作を連鎖的に適用することで到達可能な解の集合を改めて大きな近傍と捉える近傍探索のアイデアである．

ＫＬＳは，各反復において，現在のクリーク（解）から複数個の頂点を連鎖的に追加・削除する操作（それぞれAdd移動，Ｄｒｏｐ移動と呼ぶ）により構成され，現在の解からそれらの操作によって生成可能な解の

集合を改めて近傍と捉えることで，局所探索を行うアルゴリズムである．

ＫＬＳの疑似コードを図１に示す．ＫＬＳは外ループ(Linel-18)と内ループ(Line３－１６)の処理を有す

る．以降，外ループに対しては「反復」，内ループについては「繰り返し」と呼び区別する．

まず，本論文で頻出する，図１中の重要な記号および用語を説明する．ｃｃ(')は内ループの繰り返しｌの時点における解(クリーク)である．ＰＡ(')はＣＯ(1)の全頂点に隣接するＣＯ(')に追加可能な頂点集合

PA(')＝{ｕ:ｕｅ(VICC(1)),(u,j)ｅＥ,VjECC(1)｝

である．

(3)

115

● ● PＡｃｃ

● ０Ｍ

図２ＣＯＰＡおよび０Ｍの集合の一例

○Ｍ(')は，ＰＡ(1)を若干緩和した１辺不足集合と呼ぶ辺集合

ＣＭ(1)＝{(u,j)：ｕＥｖ）ｊＥｏｃ(!)ん,j)巳Ｅ,(０，j)ＥＥ,VjEcc(1),ｊ≠j｝

である．なお，０Ｍ(')はＣＯ(【)に含まれる１つの頂点ｉＥＣＣ(')だけに辺が存在しない頂点の集合と捉える

ことができる(なお，ＣＯ二○Ｍ)(図2.参照)．de9G(pA(1))はＰＡ(1)により誘導される部分グラフＧ(PA(1)

内の各頂点ＵＥＰＡ(1)の次数である．

2.1ﾙｰopt近傍探索処理

以下では，ＫＬＳの各反復における基本アルゴリズム(h-opt近傍探索処理)について簡潔に説明する．まず，与えられた初期クリーク(初期解)ｃｃ(o)を対象に，Add移動操作およびDrop移動操作を連鎖的に適用することで到達可能な近傍解の集合ＣＯ(o),…,ＣＯ(胸),…,CCC)を得る(その生成途中では，移動候補頂点集合Ｐ(Line2)を利用することで，追加または削除された頂点は再び追加．削除されることはない)・その近傍解の集合から最良解ＣＯ(ん)(１≦A≦r)を選び(Line8)，次の反復の初期クリークＣＯ(0ルーＣＯ(ん)とする(Linel7)．KLSは，常に実行可能領域を探索空間としており，各反復の初期クリークに応じて，h-opt 近傍のサイズ(上述のｒに対応)が適応的に変動する．

上述のA-opt近傍探索処理は，Add移動操作を施す「Addフェーズ」（Line5-8)とＤｒｏｐフェーズを施す「Dropフェーズ」（LinelO-13)の二つのフェーズで構成される．以下では，ＡｄｄフェーズおよびＤｍｐ

フェーズのそれぞれの頂点選択方式について記述する．

2.2従来法のＡｄｄ移動頂点選択方式

反復ｔにおいて，初期クリークＣＯ(o)および対応するｐＡ(o)が与えられ，それぞれ|ＣＯ(o)|＞Ｏおよび pA(o)≠０であったと仮定する（繰り返しカウンタをノー０とする）．ＣＯ(o)からＣＯ(1)を得るための頂

点の移動は，誘導部分グラフＧ(Ｍ(o))内の各頂点の次数de9G(Ⅲ｡))を考慮し，最大次数の頂点ｕを選ぶ．

最大次数の頂点が複数個ある場合には，それらの頂点群からランダムに－つの頂点を選択する．選ばれた頂

点ｕをAdd移動操作によりＣＯ(1)＝ＣＯ((o))Ｕ{u}を得る．その後，ＰＡ(o)等の情報をＰＡ(1)等に更新する．なお，A-opt近傍探索処理中では，一つの頂点が移動する度に（つまり，Ａｄｄ移動または後に説明する

Ｄｒｏｐ移動操作が施される度に），関連するＰＡ等の情報（その他，degG(pA)および後に説明する○Ｍ）を

更新する．更新の方法は文献2)に示された方法と同様の更新法を採用する．詳細は文献2)を参照されたい．

Ａｄｄ移動操作を続けると，ＣＯはある繰り返し時点ｌでＡｄｄ移動操作が不可能なクリークＣＯ(!)まで拡大される．Ａｄｄ移動操作が不可能なクリークになると，Ａｄｄフェーズを終了し，Ｄｒｏｐフェーズに処理が移行する．内ループのh-opt近傍探索処理では，拡大不可能なクリークＣＯ(')から－つまたは複数の頂点をＤｒｏｐフェーズにて削除することで，より良好な（大きな）クリークの探索を試みる．

2.3従来法のDrop移動頂点選択方式

Ａｄｄフェーズが実施された後の内ループのある繰り返し時点ノで，拡大不可能なクリークＣＯ('）に到達したと仮定する．この時点で，Ｄｒｏｐ移動操作により，一つの頂点ｕをＣＯ(')から削除する．一つの頂点ｕ

(4)

MCP-k-opt-Local-Search(ＣＯ,ＰＡ,０Ｍ,de9G(pA)）

ｂｅｇｉｎ

ｒｅｐｅａｔ

ｃＣｐ…:＝ｃｃ,、＝ＣＣＰ…,Ｐ:＝｛1,…,〃}’９:＝０，９，…:＝ｏ；

ｒｅｐｅａｔ

ｉｆｌＰＡｎＰｌ＞Ｏthen ／／AddPhase

findavertexuwithmax⑪E{pAnp}{de9G(pAnp池)｝;

ifmultipleverticeswiththesamemaximumdegreearefbund thenselectonevertexuamongthemrandomly；

ＣＯ:＝ＣＣＵ{Ｕ}’９:＝９＋1,Ｐ:＝ＰＷ）}；

ｉｆ９＞９ｍ｡錘ｔｈｅｎ９ｍＱ工:＝９，Ｃｑｅ３ｔ:＝ＣＯ；

ｅｌｓｅ

／／DropPhase(if{ＰＡｎＰ}＝Ｏ）

findavertexuE｛ＣＣｎＰ)suchthattheresultinglPAnPlismaximized；

ifmultipleverticeswiththesamesizeoftheresultinglPAnPlarefbｕｎｄｔｈｅｎｓｅｌｅｃｔｏｎｅｖｅｒｔｅｘｕａｍｏｎｇｔｈemrandomly；

ＣＯ:＝ＣCMU}’９:＝９－１，Ｐ:＝ハ{U}；

ifuiscontainedinOCp…ｔｈｅｎＤ:＝ＤＷ}；

endif

updatePA,０Ｍ,andde9c(pAnp)(j),ＶｊＥＰＡｎＰ；

untilＤ＝Ｏ；

ｉｆ9m…＞OthenCC:＝ＣＱ…ｅｌｓｅＣＣ＝ＣＣＰ…；

ｕｎｔｉｌ９ｍＱｍ≦Ｏ；

ｒｅｔｕｒｎＣＣ；

ｅｎｄ；

１２３４５６

７８９０１

１１２３４５６７８９１１１１１１１１

図３新しい頂点選択方式の導入したＭＣＰに対するAD-opt局所探索法の擬似コード

をＣＯ(1)から削除する際，ＣＯ(')から任意に削除するよりも，追加可能集合のサイズ|Ｍ(!+')|をできるだけ大きくする頂点を削除するのが望ましいことは明白である．この観点から，Ｄｒｏｐフェーズでは，ＣＯ(1) から削除する－つの頂点Ｕを選ぶ際，ＰＡ('+')のサイズを最大にする頂点りを選ぶ．ＰＡ(J+')のサイズが同

じになる頂点が複数個存在する場合には，それらの頂点群からランダムに－つの頂点を選択する．

2.4新たな頂点選択方式を採用したＫＬＳ

ＫＬＳを改良するために，ＫＬＳのアルゴリズム内部に導入可能な頂点選択方式について検討する．従来法で

は,Add移動操作を適用する際，前述のように，ＰＡ(')からなる誘導部分グラフＧ(PA('))内の各頂点の中で

最大次数をもつ頂点をＣＯ(1)に追加する．局所探索の各反復では，２度以上同じ頂点が移動されることはな

いため，A-opt近傍処理後半では，Ｇ(PA('))に移動することが不可能な頂点が多く含まれる．ＰＡ(Ｉ)に含まれる移動可能な頂点(Ｕ:ＵＥＰＡ(1),ＵＥＰ)がＧ(PA(！))内で多くの移動不可能な頂点(Ｕ:ＵｅＰＡ(1),Ｕ伝Ｐ）

と隣接していると，後に拡大されるであろうクリークサイズに悪影響を与えると推測される．この問題を解決するために，改善法では，Ａｄｄ移動操作を適用する際，移動可能集合Ｐを考慮して，ＰＡ(ＯｎＰからなる誘導部分グラフＧ(PA(1)ｎＰ)内の各頂点の中で最大次数をもつ頂点をＣＯ(1)に追加する．

現在のクリークＣＯ(1)から一つの頂点Ｕを削除し，－つサイズの小さいクリークを得る際には，ＣＯ(U)に

－つの頂点を追加する場合と同様にＰを考慮して，ＰＡ(!+')ｎＰの個数が最大となる頂点をｃｃから削除

する．

以上を踏まえ，新しい頂点選択方式の導入したＫＬＳの疑似コードを図３に示す．

(5)

117

３．ＫＬＳの性能評価実験３．１実験方法

頂点選択方式の相違によるＫＬＳの探索性能を調査するために実験を行う．本論文ではＭＣＰの標準的なベンチマーク問題としてよく知られるＤＩＭACSベンチマークグラフ(最大頂点数4000,最大辺数5506380）

から大規模もしくは厳密解の算出が困難な３７問を対象とする．

一般に局所探索法は，一つの初期解が与えられた時，一つの局所最適解を算出する．従って－回だけの局所探索法の実行では良好な局所最適解を算出できない場合が多いため，通常，異なる初期解を与え，それぞれの初期解からスタートする局所探索法を複数回実行し，得られた最良解を出力する方法が一般に採用される．このような局所探索法の利用方法は，マルチスタート法と呼ばれ，局所探索法利用における最も単純かつ古典的な方法の一つである'8)．本実験でも同様に，マルチスタート法を採用する．本実験で実施するマルチスタート法の詳細は以下の通りである．与えられたグラフＧ(ⅨＥ)の含まれる１頂点をクリークと見なすと，｜ｖｌ(=､)個の異なる初期クリークが生成可能であることから，ｎ個の異なる(質の悪いクリーク)解をそれぞれ初期解としてＫＬＳを実行するマルチスタート法を採用する．従って，マルチスタート法の１試行あたり，ｎ回のＫＬＳが実行され，ｎ個の局所最適解が得られる．ＫＬＳの純粋な性能を検証するためには，マルチスタート法中，既に得られたクリークの情報を後のＫＬＳの実行の際に利用すべきではないため，ＫＬＳの各実行はそれぞれ独立させ，得られるｎ個のクリーク群から最良解を出力する．なお，同じクリークサイズの最良解が複数得られる場合は，最初に得られる最良解を出力する．マルチスタート法の

試行回数は１００回である．

アルゴリズムはＣによりコード化し，最適化オプション－０２を使用したｇｃｃコンパイラでコンパイルした．全ての実験は、ＨＰワークステーションxw6000(Xeon28GHz)上で実行した．

3.2実験結果

結果を表２に示す．表２のGraphの欄には問題名(Name)と第２回DIMACSImplementationChallenge WOrkshopの参加者の最良の結果6)(BR)(*がついたＢＲは最適解値であることが証明されている)を示した．

改良法の欄には改良法を組み込んだマルチスタート法の各試行によって得られた最良解値の最大値(Best)，

最良解値の平均値(Avg)，最良解の平均値の標準偏差(sdev.)を示した．以降，最良解を得るまでの平均計算時間(Time(8)，単位は秒)，平均計算時間の標準偏差(sdev.)を示した．

従来法の欄には文献'o)に示された従来法によるマルチスタート法の結果を引用した．ただし，従来法の

平均計算時間は本実験環境に合わせて校正したものである．

従来法の結果と比較すると，改善法はBestの値で３７問題例中３６問に対して，同等もしくはより良い結果を示した．その内の３問題例に対しては,従来法よりも大きいクリークを算出することができた(brock20M はサイズが１大きい17,brock400-2はサイズが８大きい33,gen400PO,9-55はサイズが２大きい55)．

Bestの値で改善法が従来法よりも悪い結果を示したのはMANN-a81の１問だけであり，改善法が算出したク

リークサイズと従来法が算出したクリークサイズの差は１である

従来法のＡｖｇの値と改善法のＡｖｇの値を比較すると，改善法は３７問題例中３４問に対して，同等もしくはより良い結果を示した(同じ結果を示したのが23問，より良い結果を示したのが１１問)．Ｃ1000.9,

MANN-a81，gen200-pO､09-44の３問に対しては，従来法の結果の方がより結果であったが，改善法との差

はわずかである．

次に，計算時間に関してふれる．改善法にもとづくマルチスタート法によって最良解を得るまで平均計算時間は，従来法よりも若干増加する傾向にあるようである．これは改善法が従来法に比べて平均的により良質な解を算出していることが原因であると推測される．従来法のＡｖｇの値と改善法のＡｖｇの値が同値であった問題例は２３問であり，その２３問に対する両解法の平均計算時間に着目すると，改善法は従来法よりも２３問題中１５問に対して良い結果を示した．その他の８問に対しては，従来法の平均計算時間の方が

良い結果を示したが，改善法との差はわずかである．

(6)

表１ＤＩＭACSマシンベンチマーク問題に対するUsertime(ＨＰワークステーションxw6000Xeon28GHz）

r100.5ｒ２００５ｒ３００５ｒ４００､５ｒ500.5

＜0.0010.0600.5203.19010.990

表２ＤＩＭＡＣＳベンチマークグラフに対するＫＬＳの結果

ＮａｍｅＢＲ

ＤＳＪＣ５００５l３ＤＳＪＣ１ＯＯＯ５１５Ｃ2０００５l６Ｃ４０００５１８ＭＡＮＮ－ａ２７

ＨＡＮＮ２４５ＭＡＤＵＤＩ且8１

ｈａｍｍｉｎｇ８－４l６ｈａｍｍｉｎｇｌＯ－４４０

ｋｅ１１ｅｒ４ｋｅｌ１ｅｒ５ｋＢ１１Ｂｒ６

4．むすび

我々が既に提案した最大クリーク問題(MCp)に対するﾙｰopt局所探索法(KLS)は可変深度探索法(VDS）

にもとづいており，ＭＣＰに対する他の近似解法と同等以上の探索性能を有する強力な局所探索法である.

KLSの特徴は，比較的大きな近傍を効率良く探索する巧妙な近傍探索処理を施しているにも関わらず，パラメータ値の設定を必要としないシンプルさである．

本論文では，この特徴を維持しながら，ＫＬＳの内部に新しい頂点選択方式の導入し，頂点選択方式の相違によるＫＬＳの探索性能を調査した．ＤＩＭACSベンチマークグラフを対象に新しい頂点選択方式の導入

したKLS(改善法)を評価した結果，改善法はより高品質な解を比較的短時間に算出可能であることを示し,

その有効性を確認した．

参考文献

１）Applegate,，.,Cook,ＷａｎｄＲｏｈｅ,Ａ､：ChainedLin-KernighanfbrLargeTravelingSalesmanProblems,ＪＩＶＦＯＲＭＳＪｏｕｒＭｏ〃Oomp秘ti〃9,Ｖ01.15,No.１，ｐｐ､８２－９２(2003)．

２）Battiti,Ｒ､andProtasi,Ｍ：ReactiveLocalSearchfbrtheMaximumCliqueProblem,AI9or肋伽ＣＧ,ＶＯＬ29,No.４，

pP610-637(2001)．

３）Bomze,Ｌ,Budinich,Ｍ､,Pardalos,Ｐ・andPelillo,Ｍ､：ＴｈｅＭａｚｉｍｕｍａｊ９ｕｅＰｒｏ脈、,ＩｎＤ－ＺＤｕ,Ｐ.Ｍ・Pardalos

（Eds.),HandbookofCombinatorialOptimization(suppLVOLA),Kluwer,ｐｐ､１－７４(1999)．

４）Garey,Ｍ,ａｎｄJohnson,，.：OomputersCMI汎tmctQMjtZﾉ：ＡＧｕＭｅｔｏｔｈｅＴﾉZeorZﾉｑﾉﾉVP-OompJete汎ess,FYeeman，

ＮｅｗＹｏｒｋ(1979)．

改艮1去征釆法

ＮａｍｅＢＲＢｅｓｔＡｖｇ（s､〔 ev）Ｔｉｍｅ(s） S､dev） BestＡｖｇ（s､dev）Ｔｉｍｅ(s） S､dev）

Ｃ１２５．９Ｃ２５０．９Ｃ500.9 C１０００．９ C2000.9

＊＊４４３４７５

７６６７０００１８

１１

００８２，

Ｍｍｍ麹町

く００１１

１

０３０１１１９７

⑩の４５５

０００

１

００８２７００１２０

●●●●●４４６６５

３４５６７

４４７８７３４５６７

１１１

２１４８７０１５３２００１０８１１⑭ ３３０３８

ｍｍ加、９●●●●《叩巫】

０００１１

１１１１１ｍ哩麺籾皿

ｍｏｏＬｍ

１１７５５

１１５４４００３６６

〃□ⅡⅡ、。〃日日■、●●●

０００

１１

００５８０００１３９

●●●●●

４４６６４３４５６７

４４７８７３４５６７

､SJC500.5

、SJC1000.5

＊＊３５１１

1３１３１５１４

０００．０３２（O）（０

９８１．４１７（0.140）（１ 026）

023）

1３１３１５１４

０００．０２３（O）（0.012）

9３０．５８９（0.255）（0.487）

Ｃ2000.5 Ｃ4000.5

６８１１

1６１６

１８１７ 0０3.326（2.783）（O）

０６（0.237）２１２１７（29.395） ^1６１６ ^１８１７ 0０2.541（2.162） ^（o）

0２（0.140）20.879（15.752）

MANN-a27 MANN-a45 MANN-a81

1２６３４５

＊

1０９８

1２６１２６．０００．００９（O）（0009）

3４５３４３．８９

1０９９１０９８．０５ 0.343）2.545（2.345）

0.260）２７２２５（54.418）

1２６１２６．００．０１６（O）（0.013）

345343.88（0.354）5.440 （4.848）

11001098.07（0.292）34.634 （73.109）

brock200-2 brock200-4 brock400-2 brock400A brock800-2 brock800-4

＊＊＊＊

２７９３

１１２３１１２２１１

０６９８４９１０８５５７００００６６

●●●●●●

００００００

１１１１

０５８２２４１０１６３９００１０８６

●●●●●●

００００００

ｊ０ｌｊｊｊｊｊ

９５６０３９２９０５０３７３４

●●●●●

０００００

１１

０１８８０１００８０９７

●●●●●●

１６４５００

１１２２２２

１７５３１１

１１２３２２１１

４６８１３０００９１９３００００２８

●●●●●●

００００００

ｌｌくくｌＩ

３６７５８７００１１３６００１０４００００００１

１１

０Ｏ

ＩＩ１１７７０６３ｊ０ｌ

４７３４

０００Ｉくく

００２０６７００４０８６

●●①●●●

１６４５００

１１２２２２

１６５５１１１１２２２２

gen200-PO､９－４４ gen200PO､９J55 gen400-PO､９J55 gen400pO､９－６５ gen400-PO､９Ｊ５

＊＊４５４５５５５

５６７

３５２５５

４５５６７４５５５５

４５５６７

０００００

^Ｊ１９５

“⑥“

^Ｉ１００Ｉ

００

ｌｌ

９０４００９０２００

０１９００２

０．０１７０．００４１００（0.087 032（0.0345）

０１５（0.013）

４５２５５４５５６７

４５３５５４５５６７０００００

^１１１

０００００

１１１

００１００００２０００００００

１１

８６３６７２０８０３００１００

蕊

hamming8-4 hamminglO-4

1６

^＊

4０ 1６１６

４０４０ 0０＜0.001（Ｏ（o）

ＯＯＯ１１５（O）（０

98;｝

^４０４０ ^１６１６ ÔＯ ^ＯＯ Ô） Ô） ^{＜０．００１} ^{０．１９４} ^（0.1753） ^（0002）

ｋ⑨l１ｅｒ４ｋｅｌｌｅｒ５ｋｅｌｌｅｒ６

１１

^平

2７５９

１１１１２７２７５７５５

００（Ｃ

ＯＯ（ｏ ^{＜０．００１} ^{０．０１１}

{::89}）

５９（0.633）51.025（36.126）

１１１１２７２７５７５５

0０＜0.001（0001）（o）

０００．０３５（O）（0.029）

５９（0.708）４５９３３（54.800）

p-hat300-1 p」nat300-2 p」lat300-3 p上at700-1 p」lat700-2 p上at700-3 p上atl500-1 p上atl500-2 p-hatl500-3

牢８＊＊＊＊

５６１４２３１４

２６＊２１５４６９１１１１１１

４４８３７３１６５０００６０１５４５００００００８０４

●ＣＯ●●●●●ロ

００００００１００

１１１１１

２２８７７３０９１０００６０１１５１００００００２０４００００００３００

１１１１１

０００００００００

１１１１

叩ｍｍｍｍｍｍｍｍ８２３１４６１６９．５６１４２２５４

８頭邦ｕ“⑪、髄“

１１１

４３７６４４８８００００５０１０３５００００００００３

●●●ｃ●。●●●

０００００００００

ｌｌｌくく！－Ｉく

１２０９７４５５６００１００１８５７０００１００２０３

●●●●●●●●●

ＯＯＯ０００２００

１１１１１

００００００００ｏ

ｌＩｌＩｌｌＩＩｌ

叩皿ｍｍｍｍ皿“皿、５６１４２２５４８２３１４６１６９

８頭妬ｕ“⑰、髄叫

(7)

119

５）Johnson,Ｄ・andMcGeoch,Ｌ､：ＴｈｅＺＭｅｌｍ９ＳＧｌｅｓｍｑ〃Ｐｍｂｌｅｍ：ＡＯＱｓｅＳＭｙ,LocalSearchinCombinatorial Optimization,JohnWiley8ZSons,ｐｐ､215-310(1997)．

６）Johnson,Ｄ・andTYick,Ｍ､：ai9ues,OoIorm9,`ＭＳａｔｉａ/tLMitU,SecondDIMACSImplementationChallenge,DIMACS SeriesinDiscreteMathematicsandTheoreticalComputerScience,ＶＯＬ26,AmericanMathematicalSociety(1996)．

７）片山謙吾,成久洋之:遺伝的反復局所探索法とその最適化性能,電子情報通信学会論文誌(A),VOLJ83-A,No.２，ppl79-187

（2000)．

８）片山謙吾,成久洋之:バイナリー２次計画問題に対する変形h-opt局所探索法,電子情報通信学会論文誌(A),VOLJ84-A,No.３，

pp430-435(2001）

９）片山謙吾,成久洋之:大規模な最大多様性問題に対する遺伝的局所探索,情報処理学会論文誌：数理モデル化と応用,ＶＯＬ４５，

Ｎ。､ＳＩＧ２(TOM10),ｐｐ､99-109(2004)．

10）Katayama,Ｋ,Hamamoto,Ａ､andNarihisa,Ｈ､:AnMectiveLocalSearchfbrtheMaximumCliqueProblem,1,/Ｄｒ‐

ｍａｔ伽Processm9Letters,ＶＯＬ95,No.５，ｐｐ､503-511(2005)．

11）Katayama,Ｋ,Hamamoto,AandNarihisa,Ｈ：SolvingtheMaximumCliqueProblembyA-optLocalSearch,Ｐ、‐

cee伽gsqfthe20“AOMSympos2四monAppJjedOompu伽9,ＶＯＬ２，pplO21-1025(2004)．

12）Katayama,KandNarihisa,Ｈ:Ａ汎ＥｕｏＭ伽qrUApProach/b7theMaqD加泌mDjUersjtyPmoblem,RecentAdvancesin MemeticAlgorithms,ＷＥＨａｒｔ,NKrasnogor,ａｎｄＪＥ・Ｓｍｉｔｈ(Eds.),Springer,ｐｐ３１－４７(2004)．

13）Kernighan,ＢａｎｄＬｉｎ,Ｓ:AnMicientHeuristicProcedurefbrPartitioningGraphs,BelISvstemT1ec伽calJourM，

ＶＯＬ49,pP291-307(1970)．

14）Ｌin,Ｓ・andKernighan,Ｂ:AnEfTbctiveHeuristicAlgorithmfbrthenavelingSalesmanProblem,Ope伽o"sReseGmc凡ＶＯＬ21,ｐｐ､498-516(1973）

15）Marchiori,Ｅ､：Genetic,Itemted`ＭﾉWltistarMocalSea伽/ｂｒ仇ｅＭａｚｍ四mOli9uePmblem,ApplicationsofEvo- lutionaryComputing,LNCS2279,Springer,ppll2-121(2002)．

16）Merz,RandFYeisleben,Ｂ:GreedyandLocalSearchHeuristicsfbrUnconstrainedBinalyQuadraticProgramming，

Ｊｏ皿r"qlq/HeMstics,ＶＯＬ８，No.２，ppl97-213(2002)．

17）Merz,Ｐ・andKatayama,Ｋ:MemeticAlgorithmsfbrtheUnconstrainedBinaryQuadraticProgramming,BdoSystems，

ＶＯＬ78,No.1-3,ｐｐ９９－１１８(2004)．

18）柳浦睦憲,茨木俊秀:組合せ最適化一メタ戦略を中心として－,朝倉書店(2001)．

19）Yagiura,Ｍ､,Yamaguchi,Ｔ､andlbaraki,Ｔ､：ＡＶｍｑｂｌｅＤｅｐ仇SeGmcﾉMI9orithm/ｂＭｔｅＧｅ〃emlize(MSS伽,､e”t PmobIem，Meta戸Heuristics：AdvancesandTYendsinLocalSearchParadigmsfOrOptimization，Ｓ、VOss，SMartello，

ＬＨＯｓｍａｎａｎｄＣ・Roucairol(Eds.),Kluwer,ｐｐ､459-471（1999)．

(8)

VertexSelectionRulesofLocalSearch fbrtheMaximuCliqueProbleln

ＡｋｉｈｉｒｏＨＡＭＡＭｏＴｑＫｅｎｇｏＫＡＴＡＹＡＭＡ*，

ＨｉｄｅｏＭＩＮＡＭＩＨＡＲＡ＊andHiroyukiNARIHIsA＊

GMMeSchoolqfEn9meerin9,OAqUqmqU『zjueMtyqfScie〃Ｃｅ．

*DePqrfme〃tqfIn/brmqtio〃〔MComPuterE"9meerjn9,FtBcu1tZ/がBn9ineerm9，

OlMBW7MzUnjuers伽qfScience・

L1Rjdqi-cho，OAqyqmq，700-0005,JQpq〃

（ReceivedSeptember30,2005;acceptedNovember7,2005）

Wehavealreadyproposedavariabledepthsearchbasedalgorithm,calledA-optlocalsearch(KLS)，

fbrthemaximumcliqueproblemandshownthatKLSoutperfOrmedrecentmetalleuristicalgorithms、

KLSeHicientlyexplorestheA-optneighborhooddefinedasthesetofneighborsthatcanbeobtainedby asequenceofseveralqddanddrOpmovesthatareadptivelychangedinthefeasiblesearchspacelnthｉｓ paper，weuseeflicientKLSalgorithmwhichexploresk-optneightborhoodinthesearchspacedeleted fromalreadymovedverticesComputationalresultsshowthatKLSiscapableoffindinghigh-quality cliqueswithreasonablerunningtimefbrDIMACSbenchmarkgraphs．

最大クリーク問題に対する局所探索法と頂点選択方式

ｒｅｐｅａｔ

ｒｅｐｅａｔ

ｅｌｓｅ

ｅｎｄｉｆ

ｒｅｔｕｒｎＯＣ；

ｅｎｄ；

２３４５６７８９

115

●

● PＡ ｃｃ

● ０Ｍ

ｒｅｐｅａｔ

ｒｅｐｅａｔ

ｅｌｓｅ

endif

ｒｅｔｕｒｎＣＣ；

ｅｎｄ；

７８９０１

117

r100.5ｒ２００５ｒ３００５ｒ４００､５ｒ500.5

Ｎａｍｅ ＢＲ

ＤＳＪＣ５００５l３ ＤＳＪＣ１ＯＯＯ５１５ Ｃ2０００５l６ Ｃ４０００５１８ ＭＡＮＮ－ａ２７

ＨＡＮＮ２４５ ＭＡＤＵＤＩ且8１

ｈａｍｍｉｎｇ８－４l６ ｈａｍｍｉｎｇｌＯ－４４０

ｋｅ１１ｅｒ４ ｋｅｌ１ｅｒ５ ｋＢ１１Ｂｒ６

改艮1去 征釆法

Ｎａｍｅ ＢＲ Ｂｅｓｔ Ａｖｇ （s､〔 ev）Ｔｉｍｅ(s） S､dev） BestＡｖｇ（s､dev）Ｔｉｍｅ(s） S､dev）

Ｃ１２５．９ Ｃ２５０．９ Ｃ500.9 C１０００．９ C2000.9

７６ ６７ ０００１８

００８２，

く００１１

０３０ １１１９７

０００

００８２７ ００１２０

３４５６７

４４７８７ ３４５６７

２１４８７ ０１５３２ ００１０８ １１⑭ ３３０３８

０００１１

ｍｏｏＬｍ

１１５４４ ００３６６

０００

００５８０ ００１３９

４４６６４ ３４５６７

４４７８７ ３４５６７

､SJC500.5

、SJC1000.5

1３１３ １５１４

０００．０３２ （O）（０

９８１．４１７ （0.140）（１ 026）

023）

1３１３ １５１４

０００．０２３ （O）（0.012）

9３０．５８９ （0.255）（0.487）

Ｃ2000.5 Ｃ4000.5

1６１６

１８１７ 0０3.326（2.783） （O）

０６ （0.237）２１２１７（29.395） 1６１６ １８１７ 0０2.541（2.162） （o）

0２（0.140）20.879（15.752）

MANN-a27 MANN-a45 MANN-a81

1２６ ３４５

1０９８

1２６１２６．０００．００９ （O）（0009）

3４５３４３．８９

1０９９１０９８．０５ 0.343）2.545（2.345）

0.260）２７２２５（54.418）

1２６１２６．００．０１６ （O）（0.013）

345343.88（0.354）5.440 （4.848）

11001098.07（0.292）34.634 （73.109）

brock200-2 brock200-4 brock400-2 brock400A brock800-2 brock800-4

２７９３

０６９８４９ １０８５５７ ００００６６

００００００

０５８２２４ １０１６３９ ００１０８６

００００００

９５６０３ ９２９０５ ０３７３４

０００００

０１８８０１ ００８０９７

１６４５００

１７５３１１

● PＡｃｃ

ＮａｍｅＢＲ

ＤＳＪＣ５００５l３ＤＳＪＣ１ＯＯＯ５１５Ｃ2０００５l６Ｃ４０００５１８ＭＡＮＮ－ａ２７

ＨＡＮＮ２４５ＭＡＤＵＤＩ且8１

ｈａｍｍｉｎｇ８－４l６ｈａｍｍｉｎｇｌＯ－４４０

ｋｅ１１ｅｒ４ｋｅｌ１ｅｒ５ｋＢ１１Ｂｒ６

改艮1去征釆法

ＮａｍｅＢＲＢｅｓｔＡｖｇ（s､〔 ev）Ｔｉｍｅ(s） S､dev） BestＡｖｇ（s､dev）Ｔｉｍｅ(s） S､dev）

Ｃ１２５．９Ｃ２５０．９Ｃ500.9 C１０００．９ C2000.9

７６６７０００１８

０３０１１１９７

００８２７００１２０

４４７８７３４５６７

２１４８７０１５３２００１０８１１⑭ ３３０３８

１１５４４００３６６

００５８０００１３９

４４６６４３４５６７

４４７８７３４５６７

1３１３１５１４

０００．０３２（O）（０

９８１．４１７（0.140）（１ 026）

1３１３１５１４

０００．０２３（O）（0.012）

9３０．５８９（0.255）（0.487）

１８１７ 0０3.326（2.783）（O）

０６（0.237）２１２１７（29.395） ^1６１６ ^１８１７ 0０2.541（2.162） ^（o）

1２６３４５

1２６１２６．０００．００９（O）（0009）

1２６１２６．００．０１６（O）（0.013）

０６９８４９１０８５５７００００６６

０５８２２４１０１６３９００１０８６

９５６０３９２９０５０３７３４

０１８８０１００８０９７

４６８１３０００９１９３００００２８

３６７５８７００１１３６００１０４００００００１

４７３４

００２０６７００４０８６

４５５６７４５５５５

９０４００９０２００

０１９００２

０．０１７０．００４１００（0.087 032（0.0345）

０１５（0.013）

４５２５５４５５６７

４５３５５４５５６７０００００

００１００００２０００００００

８６３６７２０８０３００１００

４０４０ 0０＜0.001（Ｏ（o）

ＯＯＯ１１５（O）（０

^４０４０ ^１６１６ ÔＯ ^ＯＯ Ô） Ô） ^{＜０．００１} ^{０．１９４} ^（0.1753） ^（0002）

ｋ⑨l１ｅｒ４ｋｅｌｌｅｒ５ｋｅｌｌｅｒ６

2７５９

１１１１２７２７５７５５

００（Ｃ

ＯＯ（ｏ ^{＜０．００１} ^{０．０１１}

５９（0.633）51.025（36.126）

１１１１２７２７５７５５

0０＜0.001（0001）（o）

０００．０３５（O）（0.029）

５９（0.708）４５９３３（54.800）

５６１４２３１４

４４８３７３１６５０００６０１５４５００００００８０４

２２８７７３０９１０００６０１１５１００００００２０４００００００３００

叩ｍｍｍｍｍｍｍｍ８２３１４６１６９．５６１４２２５４

４３７６４４８８００００５０１０３５００００００００３

１２０９７４５５６００１００１８５７０００１００２０３

叩皿ｍｍｍｍ皿“皿、５６１４２２５４８２３１４６１６９