貞松政史・片山謙吾＊・南原英生＊・成久洋之＊

(1)

岡山理科大学紀要第42号Ａｐｐ８５－９３(2006）

最大クリーク問題に対するlO-opt局所探索法の解析

貞松政史・片山謙吾＊・南原英生＊・成久洋之＊

岡山理科大学大学院工学研究科情報工学専攻

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

（2006年１０月２日受付、2006年11月６日受理）

1．まえがき

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

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

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

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

中で，次の目的（評価）関数

九｡P(Ｋ）＝｜Ｋ’

を最大にするクリークを求める問題である．

ＭＣＰは，通信ネットワーク，符号理論，並列計算，パターン認識等の分野にあらわれる実用上重要な組合せ最適化問題として知られており1)，Ｎｐ_困難2)である．従って，多項式時間で厳密解を算出するアルゴリズムは存在しないであろうと考えられている．またずＭＣＰの良質な近似解を得ることすらNP-完全のクラスに準じるほど困難であることが知られており3)，その他にもＭＣｐの難しさを示す否定的な報告がなさ

れている4)5)．

最近我々は，ＭＣＰに対して，可変深度探索(VariableDepthSearch，VDS)6)7)に基づくA-opt局所探索法(A-optLocalSemch，KLS)8)を提案した．KLSは，各反復において，現在のクリーク(解)を対象に複数個の頂点を連鎖的に追加もしくは削除する操作(それぞれをAdd移動，Drop移動と呼ぶ)により構成され，

現在の解からそれらの操作によって生成可能な解の集合を改めて近傍と捉えることで，局所探索を行うアルゴリズムである．その特長は，比較的大きな近傍を効率よく探索する巧妙な近傍探索処理を施しているにも関わらず，パラメータ値の設定を必要としないシンプルさである．ＫＬＳの性能を検証するために，第２回 DIMACSImplementationChallengeWbrkshop9)で利用されたベンチマークグラフに適用した結果，多くのグラフにおいて，そのワークショップで報告されていた最適解と同等以上の良質な解の算出に成功した．

更に我々は，ＭＣＰに対する高性能なメタ戦略アルゴリズムとして知られている，Marchioriによる遺伝的局所探索法と反復局所探索法'o)，タブー探索法にもとづくBattitiらのReactiveLocalSearch11）との比較を通して，それらと同等もしくは平均的により高品質の近似解を比較的短時間で算出できることを示した．

上述のように，ＫＬＳは，他の近似解法との比較においてその性能を検証しているが，探索の動作特性など，内部的な解析については，未だ十分になされていない．本論文では，ＭＣＰに対するＫＬＳの解析の一端として，ＫＬＳにおける近傍探索処理を打切る操作の検討，および与えられたグラフ中でのＫＬＳの探索範

囲について調査する．

2．ＭＣＰに対するh-opt局所探索法

本節では，我々が既に提案しているＭＣＰに対するh-opt局所探索法（KLS）の概要などに関して述べ

る．なお，ＫＬＳの詳細については文献8)を参照されたい

(2)

貞松政史・片山謙吾・南原英生・成久洋之

8６ h-opt-Local-Search(ＣＯ,PAPMdegc(pA)）

ｂｅｇｉｎｒｅｐｅａｔ

ＯＣｐ…＝ＣＯ,Ｄ:=CCp…,Ｐ:＝{1,…,冗},ｇ:=0,9,…:=O；

ｒｅｐｅａｔ

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

findavertexUwithmqzひE{pAnp}{degc(pAnp)(u)}；

ｉｆｍｕｌｔｉｐｌｅｖｅｒｔｉｃｅｓｗｉｔｈｔｈｅｓａｍｅｍaximumdegreearefbund thenselectonevertexuamongthemrandomly；

ＣＯ:＝ｏｏｕ{u},ｇ:＝ｇ＋1,Ｐ:＝Ｐ({u｝

ｉｆｇ＞９ｍ…ｔｈｅｎｇｍａｎＧ：＝９，OObest8＝ＣＯ；

ｅｌｓｅ

／/DropPhase(if{PＡｎＰ}＝0）

findavertexuE{ＯＯｎＰ}suchthattheresultinglPAnPlismaximized；

ifmultipleverticeswiththesamesizeoftheresultinglPAnPlarefbｕｎｄ

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

ＣＯ:＝ＯＣＷ）},ｇ:＝9-1,Ｐ:＝ハ{u}；

ifuiscontainedinOCpreuthenD:＝ＤＷ}；

endif

updatePA,○Ｍ,anddegc(pA)(i),ＶｉＥＰＡｎＰ；

untilＤ＝０；

ifgm…＞ＯｔｈｅｎＯＣ:＝ＣＯb…ｅｌｓｅＣＯ:＝OCbreU；

ｕｎｔｉｌｇｍＱ⑩≦Ｏ；

ｒｅｔｕｒｎｏＯ；

ｅｎｄ；

１２３４５６７８９０１

１１

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

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

２１ＫＬＳの基本アルゴリズム

ＫＬＳは，可変深度探索（VDS）のアイデアにもとづいている．ＶＤＳとは，与えられた解に対して比較的小さな近傍操作を連鎖的に適用することで到達可能な解の集合を改めて大きな近傍と捉える近傍探索のアイデアである．KLSは，各反復において，現在のクリーク(解)から複数個の頂点を連鎖的に追加および削除する操作(それぞれAdd移動，Drop移動と呼ぶ)により構成され，現在の解からそれらの操作によって生成可能な解の集合を改めて近傍と捉えることで，局所探索を行うアルゴリズムである．

ＫＬＳの擬似コードを図１に示す．ＫＬＳは外ループ（Linel-18）と内ループ（Line3-16）の処理を有する．

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

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

ＰＡ(J)＝{ｕ:ｕＥ(VIOO(1)),(u,j)ＥＥ,ＶＥＯＣ(')｝

である．０Ｍ(J)はＰＡ(')の定義を若干緩和した１辺不足集合と呼ぶ辺集合

○Ｍ(1)＝{(u,j)：ｕＥＷｅｏｃ(u),(u,j)翅,(ｕＤＥＥ,yjEcc('),ｊ≠i｝

である．なお，○Ｍ(')はＣＯ(U)に含まれる頂点群の中のいずれか一つの頂点ｉＥＣＣ(')だけに辺が存在し

ない頂点の集合と捉えることもできる（なお，ＣＯ二○Ｍ）（図２参照）．de9c(pA('))はＰＡ(u)により誘導

される部分グラフＧ(ＰＡ(J))内の各頂点ＵｅＰＡ(`)の次数である．

次いで，ＫＬＳの各反復における基本アルゴリズム（lD-opt局所探索処理）について簡潔に説明する．まず，

与えられた初期クリーク（初期解）ＣＯ(o)を対象として，複数個の頂点を連鎖的に追加する操作（Add移動

操作）および削除する操作（Ｄｒｏｐ移動操作）により到達可能な近傍解の集合ｃｃ('),…,ＣＯ(ん),...,ＣＯ(「）

を得る．（その生成途中では，移動候補頂点集合Ｐ（Line2）を利用することで，追加または削除された頂点

(3)

最大クリーク問題に対するルーOpt局所探索法の解析 8７

●

PＡｃｃ

●

０Ｍ

●

図２００，ＰＡおよび○Ｍの集合の一例

は再び追加・削除されることはない）．その近傍解の集合から最良解ＣＯ(ん)(１≦ん≦γ）を選び（Line8），

次反復の初期クリークＣＯ(o):＝ＣＯ(ん）とする（Linel7)．ＫＬＳは常に実行可能領域を探索空間としており，

各反復の初期クリークに応じて，h-opt近傍のサイズ（上記のｒに対応）が適応的に変動する．

上記のAo-opt近傍探索処理は，Ａｄｄ移動操作を施す「Ａｄｄフェーズ」（Line5-8）とＤｒｏｐ移動操作を施す「Ｄｒｏｐフェーズ」（LinelO-13）の二つのフェーズで構成される．以下では，それぞれのフェーズにおいて核となる頂点選択方式(Line5-6およびLinelO-11)について記述する．

２１．１Ａｄｄ移動頂点選択方式

ＰＡ(』)ｎＰの中で次数degc(pA(1)(u))が最大の頂点ｕを選択する．但し，同じ最大次数の頂点が複数個存

在する場合は，それらの頂点群からランダムに－つの頂点を選択する．

2.1.2Ｄｒｏｐ移動頂点選択方式

ＣＯ(1)の中で，ｌ＋１の時点で得られるlPA(!+')|が最大となる頂点ｕを選択する．但し，｜PA('+')|を最

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

3．ＫＬＳの解析に関する検討事項

本節では，本論文の目的である，ＫＬＳの解析における２つの検討事項について記述する．まず，ＫＬＳにおける近傍探索処理の打切り操作について３．１節で記述し，次いでＫＬＳの探索範囲について３．２節で記述

する．

3.1近傍探索処理の打切り操作

ＫＬＳの処理における内ループの終了条件はＤ＝０である(図１Linel6)．Ｄは外ループの各反復における初期クリーク，すなわち前回の反復によって得られた最良解(Cq,…)で初期化されている(Line2)．前

回の反復によって得られた最良解のクリークサイズが大きくなるほど，Ｄのサイズが大きくなるため，内ループの繰り返しの回数も比例して増加する可能性が高いしかし，繰り返しの回数が増加しても，ＫＬＳでは移動候補頂点集合Ｐ(Line2)を利用しているため，一度移動操作を行った頂点は，その反復内で再び移動操作を行うことはできない．そのため，後半の繰り返しでは移動可能な頂点群が大幅に減少しており，改善解が発見される可能性は低いと考えられ，この部分はＫＬＳの探索において効率的でない．そこで，探索の効率化を図るために，繰り返しをある程度の回数で打切る操作を考える．本論文では，、，ＣＣＩ,ｒｅＵのサ

イズを基準に以下の２パターンの打切り操作を提案する．

・打切り1：｜D|が|CCI,…|のもになったとき，内ﾙｰﾌﾟを終了する．

●打切り2：lDlがlOCbrcUlの；になったとき，内ループを終了する．

(4)

貞松政史・片山謙吾・南原英生・成久洋之

8８ 3.1.1実験Ｉの詳細

上述２パターンの打切り操作の効果を検証するために実験を行う．打切り操作を行わない従来のＫＬＳと 2パターンの打切り操作(打切り１と打切り２)をそれぞれ有する２タイプのＫＬＳの計３タイプのＫＬＳを比較検討する．対象とするグラフは，ＭＣＰの標準的なベンチマーク問題としてよく知られるＤＩＭACSベンチマークグラフ(最大頂点数4000,最大辺数5506380)から大規模もしくは厳密解の算出が困難な37グ

ラフを対象とする．

本実験では，以下のマルチスタート法を採用する．与えられるグラフＧに含まれる１頂点をクリークと見なす時，｜ｖｌ(＝、)個の異なる初期クリークが生成可能であることから，ｎ個の異なる（質の悪いクリーク）解をそれぞれ初期解とする．従ってマルチスタート法の１試行あたり，ｎ回のＫＬＳが実行され，ｎ個の局所最適解が得られる．ＫＬＳに与える初期クリークは，各頂点の次数にもとづき予めソートし，次数の高い頂点から非増加順に与える．ＫＬＳの純粋な性能を検証するためには，マルチスタート中，既に得られたクリークの情報を後のＫＬＳの実行の際に利用するべきではないため，ＫＬＳの各実行はそれぞれ独立させ，

得られるクリーク群から最良解を選び出力する．なお，同じクリーク重みの最良解が複数個得られる場合は，最初に得られる最良解を出力する．３タイプのＫＬＳをそれぞれ有するマルチスタート法を各１０回試行

する．

全てのＫＬＳはＣ言語によってコード化し，使用コンパイラは，最適化オプション－０２を付加したｇｃｃ (Ver､4.1.1）である．全ての実験は，Hewlett-Packard社の計算機HPxw4300WbrkstationCPU:Pentium４

3.4ＧＨｚ，４ＧＢＲＡＭ，ＯＳ:ＦＭｏｒａＣｏｒｅ５上で行う．

3.1.2実験Ｉの結果

結果を表１に示す．DIMACSbenchmarksの欄には，問題例名(Instance)を示した．打切りなしの欄には，打切り操作を施さない従来のＫＬＳを有するマルチスタート法の各試行によって得られた最良解値の平均値(Avg)，最良解を得るまでの平均計算時間(Time(s))，平均移動操作回数(step)，平均ＬＳ回数(ls-n）

を示した．打切り１，打切り２の欄には，打切り１，打切り２をそれぞれ施したＫＬＳを有するマルチスター

ト法の結果を打切りなしの欄と同様の形式で示した．

表１のAvgに注目すると，全体的に見て，打切り１，打切り２共に，打切りなしと同程度の解を算出できていることがわかる．しかし，部分的に見ると，打切り操作を施したＫＬＳの方が悪質な解，良質な解を算出している問題例があることがわかる．２パターンの打切り操作は，繰り返し回数をある程度の回数で打切

表１ＤＩＭACSベンチマークグラフに対する３タイプのＫＬＳによる実験結果

ＤｎＵＨＡＣ己

ｂｅｎｃｈｍａｒｋＢ

■､￣￣Ｌ八,￣､ツー￣■－－－￣￣■￣

丁」ヅリツタ訳し丁j百ｕリ」『｣ヅlソ=

Ⅱ回巳tａｎｃｅＡｖｐＴｍｎｅ【ＢＤＢｚｅＰⅡ写一ｍＡＶ圧Ⅱ､iＸｎｅ（Ｓ】ＳＥｅｐロ＆＝、Ａｖａ,エ､ｍｅ【ｓ】Ｂｚｅｐ旦已＝皿

C１２５．９

C250.9 C500.9 Ｃ1000.9 Ｃ2000.9

､SJC500.5

、SJC1000.5 C2000.5 C4000.5

Ⅲ△､UⅢnzT 1n△mU-n4B HAHpLa81 brock2002 brock200-A brocMOOユ brock400」

broch8002 broch800A

ge巫OO-pO､９弓44 8⑥n200子0.9-55 9⑥n400-pO､9-55 80魂００_P０．９△5 80,400_p０．９．５

ｈａ四,1屯8-4 ha■minglO-4

kOﾕﾕ⑥ｒ４上⑨ﾕﾕ③r5 kO11⑧z６ＰＬａｔ３００＝１

P上at300-2 PLat300-3 P上at700-1 P上aWOO-2

Ｐ上２t700-3

ｐ△唾1500-1 Ｐ上atl500-2 p上atl500-3

３４

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

一可Ｌ【ｍ】八『ＥＵＦＬＴＬｊｎ『Ｅ』■■■己旧凸５ミゲロミ刊ＪＱＩＱ■ｑ●６■１６０曰ｑｄｄｄｄ０ｄＩ０Ｊ

１１２２２２４５５６７１４１２５２３１４６１６９００００００００００００００００００００００００００００ｏ００００００００ＩｌｌＬｉｌＪｊＬｊ３ｌＪｊ９３７５００５００００００５０００００００００ ^７

^１

^２ｎＵ（ＵｎＵａＬ民）ｎＵｎＵ■Ｌロ）（ｕ▲■（Ｕ【Ｕ、】【Ｕｍｕ〔四一ｍ】ｍＬＦＬＴＬｒＬＴＬＴＬＴＬＴＬＪＬＦｄＦＬＴ＆ｌ■Ｉｑｌｑ８８勺。１００１ ^{1０１Ｚ４ＺL}

^{)２８５７１４３２}９６５３９３７１１５９

)７６７５２６１２４５ )１５１１３０４０３０９ )１８７３７１９２６４４９６６１１７ [2１６６９６１４３３８７３３７９６６５５ )３０４２８３１１

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

〕０１６７６１２

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

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

０２０9５１

６４２１２７１４７

００１１１３

０００１０２

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

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

６３

^１４^７

^９２０３５１９２２２０３５

３４

４４５６６６７５１３１５１６１７１２６３４３ 1０９８１１１６２４２５ zＣ zＣ４４５５５２６［

７［

１〔

４（

１］

２１１

５【

〔

２【

３（

１：

４」

６１１１６１

９４０００００００００００００００００００００００００００００００００００００１１．ＩｌｊｌｊＪｊ３ｊＪｊ５ｊ７３ｊ０１００００００６０００００００００

^１

^１ ^３００００９００１４０３４０００００ｃＣ０ＣｔＩｔＩＩＩｆ〃■、卓■■・ａ■■『〃■由二口■ｑ■■■■『『■■■｜■■可・■■■『 ^{1００１４９１}

^{１１３３４６１３１}．０７１３８５３８８

１２４４８３７２２４９１１９１４４６０３６３２ )１９７８４３２ L１２５６３８z１２ｌ３５７２８７２４６２８８１６５６６５０７ )１１１８９８７３１４２３８９９７３４８１８３２４０６３１１０９

〕０２３３７１７

〕０３６６０２１

〕５８５５０２１００

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

〕１８５５９７５２ｺ０４１４４４１２０６１9８７６６６０６０１００８７６３０２４４３６４２５０００２７１１７７４５９１５７０００２６１０１９６２５１１８８５１３２８３５１０７９００１9２６

０００７５1

００６１１３１１３

０５９１１８６７１

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

３４

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

二可Ｌｎｍ】几訂■■Ｆしぶ■》●Ａ『田ＬＢ凸伍巴倶Ｌ－ＳＬｆ■●１Ｊロー■ｑ■■■０ｑ０ｑｑＱｊｄ０ｄｄｑｌ０４

１１２２２２４５５６７１４１２５２３１４６１６９０００００００００００００００００００００００００００００００００００００１１１１１、Ｊ７‐、ＪＪｊＨ尹、〃ぬＪＴＪ３ｍＪｑ】房□〔Ｊ【ＵｎＵ０ｎｕ（Ｕ０（ＵｎＵＰＤ（ＵｎｘＵｎ）（ＵｎＸＵ０ｎＵ ^１

^１

^３０００１３０００４０３８０００００００ＣＣＣにｔｆｆｆ８グロ■■｜〃■■早■■『の■■『｜〃■■△■■『■■４■■凸■■『 ^{)００１４１Ｚ}

^{)１４３１５１３５})９９１１４０２91

226５５０６８３６４

〕６５４７５７３２６７

〕１４４８７２３２７０３２３９１４１ )０３３１４０１２２

１１４１４２４０５１４

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

〕０１２７８１６

〕０３４９０１７

〕６５５５２２１２３

〕０７49911 192４４４２１２７４４３１０３６１２９６０２４６９７８８３００６２１３８２２０９２１３４１７１１２０７３１０９５８ｇＯＯ６ｇｌＯ５２３８２

０００２３１

０８８２０８４３０

０００２６1

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

０００８０１

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

(5)

最大クリーク問題に対するルーopt局所探索法の解析 ^8９

ろうとする単純な操作なので，問題例によっては良質な解を発見する前に繰り返しが打切られ，悪質な解を算出してしまうと考えられる．良質な解を算出している問題例については，ＫＬＳにおける探索の動作自体が打切り操作を施すことによって変化していると推測される．次にtime(s)に注目すると，全体的に見て，

打切り１，打切り２共に，打切りなしの探索時間に対して改善が見られない．そこでstep，ｌｓ－ｎに注目すると，Ｓｔｅｐは打切り操作を施すことによって全体的に減少しているが，問題例によっては，ｌＳ－ｎが打切り操作を施すことによって増加している．このことからも，打切り操作を施すことによって探索の動作自体が変化していることが推測され，また，それによって，打切り操作が効率的に働いていないと考えられる．以上の結果より，ＫＬＳの効率化のためには，単純な繰り返し回数による打切り操作ではなく，より巧妙なルール

による打切り操作の設計が必要であると考えられる．

ａ２ＫＬＳの探索範囲

従来のＫＬＳでは，実験Ｉで用いたマルチスタート法を採用しており，ｎ回のＫＬＳを繰り返し適用する．

このマルチスタート法によるＫＬＳの各試行はそれぞれ独立であり，ＫＬＳによって得られたクリークの情報を全く利用していない．そのため，純粋なＫＬＳの探索性能が重要であり，その動作特性を調査することは有益な検討事項であると考えられる．本節では，ＫＬＳの動作特性を調査する一端として，与えられたグラ

フ中でのＫＬＳの探索範囲について調査する．

３２．１実験Ⅱの詳細

実験Ⅱでは，３．１節で検討した打切り操作がＫＬＳの探索に与える影響も付加的に調査するために，上述の３タイプのＫＬＳを対象とし，与えられたグラフ中での各ＫＬＳの探索範囲について調査する．対象グラフは実験Ｉと同様に，ＤＩＭACSのベンチマークグラフから３７グラフを対象とする．各タイプのＫＬＳは，実験Ｉと同様のマルチスタート法を採用し，各１回試行する．実験環境は実験Ｉと同様である．

探索範囲を表す指標を，対象グラフの頂点数に対する，各ＫＬＳにおける移動操作(Add移動操作，Ｄｒｏｐ

移動操作)の対象となった頂点数の割合，すなわち以下のように定義する．

移動操作の対象となった頂点数

探索範囲＝

_{対象グラフの頂点数} ×１０o[%］

3２２実験Ⅱの結果

結果を表２に示す．DIMACSbenchmarksの欄には，問題例名(Instance)，各問題例の頂点数(Nodes)，

辺密度(Density)を示した．打切りなしの欄には，打切り操作を施さない従来のKLSを有するマルチスター

ト法の試行における，KLSの各試行による探索範囲の最大値(Max)，平均値(Avg)とその標準偏差(sdev)，

最小値(Ｍin)を示した．なお，単位は全て％である．打切り１，打切り２の欄には，打切り１，打切り２をそれぞれ施したＫＬＳを有するマルチスタート法の結果を打切りなしの欄と同様の形式で示した．

表２の結果を見ると，ＫＬＳの探索範囲は，全体的に，対象とするグラフの頂点数，辺密度に関連する傾向が観測できる．辺密度が同程度のグラフでは，頂点数が多いグラフの方が探索の割合は小さい．すなわち，探索の対象となる頂点の数が同程度のため，グラフの頂点数に対する探索範囲の割合が低くなっていると考えられる．頂点数が同程度のグラフでは，辺密度が高いグラフの方が探索範囲の割合が大きい．つまり，探索の対象となる頂点数は，辺密度に比例して増加する傾向にあると考えられる．頂点数，辺密度共に同程度であるにもかかわらず，探索範囲に差が見られるグラフに関しては，各頂点の次数に偏りがあるなど，グラフの構造の違いが影響していると考えられる．また，打切りなしと打切り１，打切り２の結果を比較すると，全体的に見て，打切りのタイミングが早い打切り操作を施すほど，探索の割合が小さくなっていることがわかる．このことから，３．１２節で述べている推測と同様に，打切り操作を施すことで探索の動作

自体が変化していると推測される．

与えられたグラフ中でのＫＬＳの探索範囲について，さらに調査するために，打切りなしのＫＬＳを有する

マルチスタート法をＤＩＭACSベンチマークグラフから選出した最適解の算出が困難な４グラフ(C2000.9,

MANN-a81，keller6，p-hatl500-1)に各１回適用し，対象グラフにおける，各頂点毎の移動操作回数を調

(6)

9０

表２ＤＩＭＡＣＳベンチマークグラフに対する３タイプのＫＬＳによる探索範囲

査した．

その結果を図３に示す．横軸を対象グラフにおける各頂点の番号，縦軸を各頂点毎の移動操作回数および次数とする．なお，このグラフは，各頂点の番号と，それに対応する移動操作回数および次数を移動操作回数で降順にソートしてプロットしたものである．

図３の結果から，次数の高い頂点は移動操作回数が多くなっていることが観測できる．特にMANN-a81 とkeller6のグラフでは，次数が落ち込んでいる部分に対応して，移動操作回数も同様に落ち込んでおり，

ＫＬＳによって重点的に探索をする範囲が各頂点の次数に強く依存していることがわかる．従って，ＫＬＳの探索は，各頂点の次数の影響を強く受けており，次数が多い頂点の周りを重点的に探索する傾向にあると考

えられる．

4．むすび

本論文では，ＭＣＰに対するA-opt局所探索法(KLS)を解析する一端として，KLSにおける近傍探索処理を打切る操作の検討と探索範囲の調査を行った．ＫＬＳにおける近傍探索処理を打切る操作の検討では，内ループの繰り返しをある程度の回数で打切る操作を２パターン提案し，打切りなしのＫＬＳとの比較実験を行った．その結果，単純な回数制限による打切り操作では，全体的な探索時間の効率化を実現することができないことを示した．ＫＬＳの探索範囲の調査では，対象グラフの頂点数に対する，ＫＬＳによる移動操作の対象となった頂点数の割合を調べる実験を行った．その結果，ＫＬＳの探索では，全体的に見て，対象グラフの頂点数と辺密度によって，探索範囲が増減する傾向があることを示した．また，上述の打切り操作によって，探索範囲が小さくなる傾向を示した．さらに，対象グラフにおける，各頂点毎の移動操作回数と次数を調査した結果，ＫＬＳが重点的に探索する範囲は，対象グラフにおける各頂点の次数が強く影響する傾向を示した．以下では，今後の課題・検討事項について記述する．

(1)本論文で提案した打切り操作では，全体的な探索時間の効率化は実現できなかったが，今後，単純に

繰り返しの回数を制限するルールではなく，ＫＬＳの探索途中に得られる情報を利用した巧妙なルールの設

計について検討の余地がある．

(2)本論文で示したＫＬＳにおける探索範囲の傾向を利用して，さらに良質な解を算出するために，対象

グラフに依存している探索範囲をうまく拡大するアイデアの検討も興味深い．

ＤＩＭＡＣＳｂｅｎｃｈｍａｒｋｓ

施一ｏｐＬＬｏｃａｌごｅａｒｃｎ

ｒｊＦｕリ懇し『j則リユ fI15UリＺ

IｎＢｔａｎｃｅＮｏｄｅｓ

Ｄｅｎｓｉｔｙ

Ｍ且五ＡＶＥ（ｓ・ｄｅｖ）ＭｍＭａｘＡｖｇ（s・ｄｅｖ）Ｍ１、ＭａｘＡｖｇ（s・ｄｅｖ）Ｍｎ、

Ｃ125.9 Ｃ250.9 Ｃ500.9 Ｃ1000.9 Ｃ2000.9

､SJC500.5，

、SJC1000.5 Ｃ2000.5 Ｃ4000.5

1IAMLa27

1IADUDU里4B

lIADmJ-角Ｒｎ

br､dE200-2

brock200且

brock400-2 brock400-4 brock800-2

brockBOOA

gon200 gBn200 gep400 gep400 gen400

^{図鼬浬翅阿ｂ』} 》》》》》》》

^{と⑨１，⑨で４}^{ｋ曰１１⑨ｒ５}

》》》》》鋼叫４５５５５

と⑨l】□で６Ｐ上at300-1 P上at300-2 P上at300-3 P△at700-1 P上at700-2 p上at700-3 P上atl500-1 P上atl500-2

P上at1500-3

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

１５０００００００００００００００００００００００００ｃｃＣＣＣ６ｔｆにｔｆｔＬＩｇｇ０ｏｏＯ０００ｇｇｇｇ５４４５４ｏ００００３２４５１４８４４ｇ４５０５３３９９９５５５５９９９４６７７６６９９９９９６８６７８２４７２４７２５７８９０１０１００００６８６７９８１ｇ０００００９８９１８３８４９７８３６３ ^{７５４２１} ^{８８８１２２２} ９８３７８８５２１２３３６５２１

（】》（溝〕刊△（印〕Ｒ］▲■【図］ｎご【己同凸〔団Ｒｕ【どん『■』■』

６７４５５１１２

２３

｛次』ｊ月ゲコ■デヨ』尹虫』１２１１ ^{岸○の⑪⑦□●几} （⑥（ｃ負）ＳＬＱＬ●Ｌ１△４句】△缶貝）△４（■ｌｎＵ』□Ｒ）〈。Ｒ）□》１－ｄＬｐ４ｐ４Ｑ》、“７ｏ）【Ｕ●几【ｌ１Ｒ】ｎ名■『Ｒｕ〔■【■命■内１つｊＣ』因山

の⑪▲匙ウロ⑤。②】●上。上

口上⑦『っＬＱＬ

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

１

２３４３７００８５００５５５０５０８５５７７０５１８５０００６７７８６４４６５４２１０００ｏ２３３１２２２００６７４５６０１１０００２３Ｃ１２ｆ１１司岳ブ向ｊｎう【ゾ４４，Ｊや１１房。〔団□〕９△４△４（□（◎〆、ロ］ｑ）（Ｕ（Ｕ（己⑤□、）７７５（己》、ロ】（□２２（Ｕｎ》２２０５００８７５ｇｇｇｏ５３４８１１２５３３４８２７ｇ１５４６ｏ１８０５くｌくくくくｌくｌくくくくくＩＩくくくくｌくくくくくＩくくくくｌｌｌくｌく ^{□Ｊ冗色勺上} ^{宜凹宜凹昼）■Ｌ} 【二、二つ上ａＬａＬロユ、する缶Ｒ）（ごＲＵＱＪａＬ■ＬｎＵ②）幻缶巨Ｕ貧）ｎＵｐ】ｐＱｐ】ｑＵｎＵｎｕｐＱｐｕ【ごｎＵＲＵ■』ロ】〔出口」ＦＬ便』■ｊ■ＬＦｄＴＬＦＬ■巴

１１

ｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊ１

９３２０９４３４３４２２６６５０９５５４３０８３２４２０２０８６６５４８２４３２３７７４２１６８７４４１１８８５７９５２８９４９４８４４４５０２０４ｏ００００００５７５３３００００７７０００５５５６８９２３３６７８８６３６２３Ｊ７５２８０５７７４５５５０３３５５０７２１７１９０３３６５２２８１８ ^{５４２１１} ^{６６５１１１}

^１

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

^４

（明〕■『】■〕がし引庁】ぬ『し

２２

一展』■四利Ⅱ■沮伍』１２１１２３３３６Ｊ９６９０２９５０５０８００５７７７８９０７３０３６２２２６２１４３２１０００００００００１１１００３５２３４０００００Ｃ１２ＣＪ１ｔｆ１００００５００５５５８５００００７０００５５５１１３０９０３６８８８００３ ^４２１１ ^４４４１ ^{３３２２２} ^１１１１ ^１１６８１６３１００９ｇｇ６０８８３３０３１１２７５８４２３３２１Ｌ４Ｅ７に７４０２６１９９４５９１３６３１３２３３３５０６９９２５７６７４２２９３９７９００４２７９５５４５４３６６４４９７３６２３３６２００１２６２４８４７ｌくｌくくくくくくくくくくくくくくくくＩくくくくくｌくＩくくくくくくくくく４４４５９３２１０３９６７３１１△４４』Ｑ》２９ｌｂ（Ｕ４一口員己３。Ｌ△４（己３２１．４１７（Ｕ００００００００２７８６０００５２５００５００４９４０１０６３４０５６３０３３２３３６４８４６８２００５７６７００２０５６３８６８０６３１０８６１６１８７５５５１１６７８６３１５５３３８２１２４１４９１５５４６４４１１９２ｌｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊＪｊｊｊｊｊｊｊｊｊｊ ^{口Ｊ、二口▲} ^４八毛４ ^{句己へ二勺上司▲□上}

^１^１

２０３７４２１００８８９５８６６２２４４５５５６４５８１２７２１７ｔに：７ ^５３２１ ^{５５５１１１} ^{４４２３３１１}

^１

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

^{■【」【『し}

飼己二次』｜可四Ｆ迫宅』

■ＬⅥ二

。、△

２４３３３８９６８５７２５５０５１２０５７０７０１００００６０１７４６６８３２１１０００００００００１００００３４２２２０００００Ｄ１１０１１ＣＣＣ００００００００７８８１００００２５００５０５３５３５３０６０４１２０００ ^{（。⑦臼１－} ^{△４４百迅} ^{冗二句）１（１一勺し}

^１１

^１７△４』、ｑ）』⑥句ｏ１ｎ）（Ｕｐ４△４△４（ＣＱ）旬Ｉ旬１口］ロ】７０（Ｕロ】Ｒ］Ｑ》【、△ｑ【巳ｊｑｎ■ｑ】［盃［Ｕ屯１℃〕ロ』Ｆ几焦』こ』 ^９０ ^７ ^５８ ^７２２６０４０９２６０２３２５３５６５３１２２２７１４４４３１７６１０５５０７９５３１０２７８８１１５２６７１８８６１０１０４６３０８７７ｌくくくくｌくくくくくくｌくくくくくｌくくくくくくくくくＩくｌくくくくくく７５１２７１８９５５６７１６９０４４００５９８９７４９３４２２１０９１８６７３３１３３１００５６５７０８９３３１５１５９１６８２１４６９２０１１６８０００００００５２８７４００５５００００５５０４０４２３０３３４４１６６０４２２３１４４７４３６８０５２２５５５０７７０６１８２６０３３１１７６４２ｊｊＪｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊｊＪｊｊｊｊｊｊｊ ^３１１ ^４４４ ^{２２１１１}

^１

０９２７４２１００３３３５７６６２２２３３３４６４５３１ｚ７２１６ｇＣ４７

(7)

最大クリーク問題に対するルーopt局所探索法の解析 9１

4000 7000

numberofmove-- degree-

■・

●■■｡～◆q一・一c■･－．－－．－b---b～－■－．b･――ロー◆－－F■q･■･--..,--.Ｆ､---,.－◆．.．□－．Ｇ.|

…－－…－－……－－.～…~－－－…－－→－．－~.…￣…~－－－－一一一一~…￣………￣……8..

コ亘ヨヶの「。『ョ○くの（Ｑの四、のの）

６５４３２１００００００００００００００００００

［Ⅱ「コこヨワの「。『ョ○くの（○の、「の①）

３３２２

１

５０５０５

加伽的伽

００ ０Ｏ２００４００６００８００１０００１２００１４００１６００１８００２０００ 1000 ｎｏｄｅｎｕｍｂｅｒ

（a)Ｃ2000.9

----←---‐‐-ユーー､一一一一一一一一一Ⅱ---二▲---－－-二----ﾛｰｰｰｰﾆｰｰｰｰｰｰｰｰｰｰＬ一一ニーーー－－■__＿

０５００１０００１５００２０００２５００３０００

ｎｏｄｅｎｕｍｂｅｒ

(b)MANN-a81

3000 700

numberofmove…‐

degree-

mＢｌＬｎＩＩ

００００００００００６５４３２

コ亘ヨヮの「。『ョ○くの（□の、「

００００００００００５０５０５２２

１１コこヨワの「。｛ョ○くの（□の、「の①）

numberofmove-- degree-

８１００１

ｓｃｄや■ －－！

￣■■￣ご■■■■■

Ｐ￣～●￣●'■P1■■Ｐ－Ｓ◆守一ら｡いの■●■■■●,■■_■ _{~~●や￣●}

￣び■●--■■￣の￣Ｐ●+

ＯＬ－－－－－－－』－－－－－＝ニェーーニュー－－…－－－－－－

￣■￣●▲●｡－－－■●

００５００

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

ｎｏｄｅｎｕｍｂｅｒｎｏｄｅｎｕｍｂｅｒ

（c)keller6 （d)p-hatl500-1 図３対象グラフにおける各頂点の移動操作回数および次数

参考文献

1）IBomze,Ｍ・Budinich,PPardalos,ａｎｄＭ､Pelillo,``Themaximumcliqueproblem,，，inHandbookofCom- binatorialOptimization(suppLVOLA),，.-ＺＤｕ,Ｐ､Ｍ．Ｐ虹dalos(Eds.),ｐｐ,1-74,K1uwer,1999.

2）Ｍ・Garey）ａｎｄＤ､Johnson,“Computersandlntractability:AGuidetotheTheoryofNP-Completeness,，，

Freeman，ＮｅｗＹｏｒｋ，1979.

3）Ｕ､Pbige,Ｓ､Goldwasser,Ｌ・Lovdsz,SSafra,andM・Szegedy)"Approximatingcliqueisalmostnp-complete,，，

Proc，the32ndAnnualSymposiumonFbundationsofComputerScience，SanJuan，PuertoRico，ｐｐ２-12,

1991.

4）Ｓ・Arora,Ｃ・Lund,Ｒ・Motwani,Ｍ・Sudan,ａｎｄＭ・Szegedyi``Proofverificationandtheh麺dnessofapproxi- mationproblems,，，Proc､the33rdAnnualSymposiumonFbundationsofComputerScience,Pittsburgh,ＰＡ，

ｐｐ､14-23,1992.

5）』､HAstad,`Cliqueishardtoapproximatewithin〃'一ｅ,，，ActaMathematica,voL182,ｐｐ､105-142,1999.

6）BKernighanandSLin,``AnefTicientheuristicprocedurefbrpartitioninggraphs,，，BellSystemTbchnical

Journal,vol､49,ｐｐ291-307,1970.

7）SLinandBKernighan,``AneflbctiveheuristicalgorithmfbrthetraN'elingsalesmanproblem,，，Operations

ResearCh,voL21，pp498-516,1973.

numberofmove‐

degree-

､ﾛも

￣￣

￣ＳＦ■￣､●｡←･￣.￣L■■●￣Tひじ￣●￣－－●■■■●￣●－－｡■･▲･少■-▽￣-.p可●￣o－～￣－℃￣りご-

Ｆ

(8)

9２ ８）Ｋ・Kataiyama,Ａ・Hamamoto,andHNarihisa,``AnefIectivelocalsearchfbrthemaximumcliqueproblem,，，

InfbrmationProcessingLetters,voL95,ｎｏ､５，ｐｐ､503-511,2005.

9）DJohnsonandM､Trick,`Cliques,coloring,andsatisfiabilityi，，SecondDIMACSImplementationChallenge，

ＤＩＭＡＣＳＳｅｒｉｅｓinDiscreteMathematicsandTheoreticalComputerScience,AmericanMathematicalSociety，

1996.

10）EMarchiori,``Genetic,iteratedandmultistartlocalsearchfbrthemaximumcliqueproblem,，'Applications ofEvolutionaryComputing,ＬＮＣＳ２２７９,ppll2-l21，Springer,2002.

11）RBattitiandM.Protasi,“ReactivelocalseaJrchfbrthemaximumcliqueproblem,，，Algorithmica,voL29，

no､4,ｐｐ６１卜637,20OＬ

(9)

最大クリーク問題に対するk-opt局所探索法の解析

^9３

Ａｎａｌｙｓｅｓｏｆん-optLocalSearchfbrMaximumC1iqueProblem

ＭａｓａＳｈｉＳＡＤＡＭＡＴＳＵ，ＫｅｎｇｏＫＡＴＡＹＡＭＡ*，ＨｉｄｅｏＭＩＮＡＭＩＨＡＲＡ＊

andHiroyukiNARIHISA＊

GmdMeSchoolqfEn9i"eerjn9，

＊mpqrtmentqfIn/brmqtjo〃qMCOmputerEn9ineerd"９，

FhcultZ/ｑ/En9伽eerjn9,OAqMLmaUniue噸tZ/qfScjence・

Z-ZRjdqj-cho，ＯＡｑＷｍｕ初0-0005,Ｊ〃α､．

（ReceivedOctober2,2006;acceptedNovembeｒ6,2006）

Wehavealreadyproposedaneffectivelocalsearchbasedonvariabledepthsearch，calledA-optlocal search(KLS),forsolvingthemaximumcliqueproblem､KLSefIicientlyexplorestheAc-optneighborhood definedasthesetofneighborsthatcanbeobtainedbyasequenceofseveraladdanddropmovesthat areadaptvelychangedinthefeasiblesearchspaceAlthoughrecentresultsshowedthatKLSiscapable offindinghigh-qualitycliquesfbrDIMACSbenchmarkgraphs，ｔｈｅａｎａｌｙｓｅｓｏｆＫＬＳａｒｅｎｏｔｅｎｏｕｇｈｌｎ thispaper,weanalyzethestoppingconditionsａｎｄｔｈｅｓｅａｒｃｈｓｐａｃｅｏｆＫＬＳ．

貞松政史・片山謙吾＊・南原英生＊・成久洋之＊

岡山理科大学紀要第42号Ａｐｐ８５－９３(2006）

最大クリーク問題に対するlO-opt局所探索法の解析

貞松政史・片山謙吾＊・南原英生＊・成久洋之＊

岡山理科大学大学院工学研究科情報工学専攻

（2006年１０月２日受付、2006年11月６日受理）

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

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

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

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

中で，次の目的（評価）関数

九｡P(Ｋ）＝｜Ｋ’

を最大にするクリークを求める問題である．

れている4)5)．

2．ＭＣＰに対するh-opt局所探索法

本節では，我々が既に提案しているＭＣＰに対するh-opt局所探索法（KLS）の概要などに関して述べ

る．なお，ＫＬＳの詳細については文献8)を参照されたい

8６

h-opt-Local-Search(ＣＯ,PAPMdegc(pA)）

ｂｅｇｉｎ ｒｅｐｅａｔ

ｒｅｐｅａｔ

findavertexUwithmqzひE{pAnp}{degc(pAnp)(u)}；

ｉｆｍｕｌｔｉｐｌｅｖｅｒｔｉｃｅｓｗｉｔｈｔｈｅｓａｍｅｍaximumdegreearefbund thenselectonevertexuamongthemrandomly；

ｅｌｓｅ

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

endif

updatePA,○Ｍ,anddegc(pA)(i),ＶｉＥＰＡｎＰ；

ｕｎｔｉｌｇｍＱ⑩≦Ｏ；

ｒｅｔｕｒｎｏＯ；

ｅｎｄ；

１２３４５６ ７８９０１

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

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

ＫＬＳの擬似コードを図１に示す．ＫＬＳは外ループ（Linel-18）と内ループ（Line3-16）の処理を有する．

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

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

ＰＡ(J)＝{ｕ:ｕＥ(VIOO(1)),(u,j)ＥＥ,ＶＥＯＣ(')｝

である．０Ｍ(J)はＰＡ(')の定義を若干緩和した１辺不足集合と呼ぶ辺集合

○Ｍ(1)＝{(u,j)：ｕＥＷｅｏｃ(u),(u,j)翅,(ｕＤＥＥ,yjEcc('),ｊ≠i｝

である．なお，○Ｍ(')はＣＯ(U)に含まれる頂点群の中のいずれか一つの頂点ｉＥＣＣ(')だけに辺が存在し

ない頂点の集合と捉えることもできる（なお，ＣＯ二○Ｍ）（図２参照）．de9c(pA('))はＰＡ(u)により誘導

される部分グラフＧ(ＰＡ(J))内の各頂点ＵｅＰＡ(`)の次数である．

次いで，ＫＬＳの各反復における基本アルゴリズム（lD-opt局所探索処理）について簡潔に説明する．まず，

与えられた初期クリーク（初期解）ＣＯ(o)を対象として，複数個の頂点を連鎖的に追加する操作（Add移動

操作）および削除する操作（Ｄｒｏｐ移動操作）により到達可能な近傍解の集合ｃｃ('),…,ＣＯ(ん),...,ＣＯ(「）

を得る．（その生成途中では，移動候補頂点集合Ｐ（Line2）を利用することで，追加または削除された頂点

最大クリーク問題に対するルーOpt局所探索法の解析 8７

PＡ ｃｃ

０Ｍ

は再び追加・削除されることはない）．その近傍解の集合から最良解ＣＯ(ん)(１≦ん≦γ）を選び（Line8），

次反復の初期クリークＣＯ(o):＝ＣＯ(ん）とする（Linel7)．ＫＬＳは常に実行可能領域を探索空間としており，

各反復の初期クリークに応じて，h-opt近傍のサイズ（上記のｒに対応）が適応的に変動する．

ＰＡ(』)ｎＰの中で次数degc(pA(1)(u))が最大の頂点ｕを選択する．但し，同じ最大次数の頂点が複数個存

在する場合は，それらの頂点群からランダムに－つの頂点を選択する．

2.1.2Ｄｒｏｐ移動頂点選択方式

ＣＯ(1)の中で，ｌ＋１の時点で得られるlPA(!+')|が最大となる頂点ｕを選択する．但し，｜PA('+')|を最

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

3．ＫＬＳの解析に関する検討事項

本節では，本論文の目的である，ＫＬＳの解析における２つの検討事項について記述する．まず，ＫＬＳに おける近傍探索処理の打切り操作について３．１節で記述し，次いでＫＬＳの探索範囲について３．２節で記述

3.1近傍探索処理の打切り操作

ＫＬＳの処理における内ループの終了条件はＤ＝０である(図１Linel6)．Ｄは外ループの各反復におけ る初期クリーク，すなわち前回の反復によって得られた最良解(Cq,…)で初期化されている(Line2)．前

イズを基準に以下の２パターンの打切り操作を提案する．

・打切り1：｜D|が|CCI,…|のもになったとき，内ﾙｰﾌﾟを終了する．

●打切り2：lDlがlOCbrcUlの；になったとき，内ループを終了する．

貞松政史・片山謙吾・南原英生・成久洋之

8８

3.1.1実験Ｉの詳細

ラフを対象とする．

得られるクリーク群から最良解を選び出力する．なお，同じクリーク重みの最良解が複数個得られる場合 は，最初に得られる最良解を出力する．３タイプのＫＬＳをそれぞれ有するマルチスタート法を各１０回試行

全てのＫＬＳはＣ言語によってコード化し，使用コンパイラは，最適化オプション－０２を付加したｇｃｃ (Ver､4.1.1）である．全ての実験は，Hewlett-Packard社の計算機HPxw4300WbrkstationCPU:Pentium４

3.4ＧＨｚ，４ＧＢＲＡＭ，ＯＳ:ＦＭｏｒａＣｏｒｅ５上で行う．

3.1.2実験Ｉの結果

を示した．打切り１，打切り２の欄には，打切り１，打切り２をそれぞれ施したＫＬＳを有するマルチスター

ト法の結果を打切りなしの欄と同様の形式で示した．

表１ＤＩＭACSベンチマークグラフに対する３タイプのＫＬＳによる実験結果

ｂｅｎｃｈｍａｒｋＢ

C250.9 C500.9 Ｃ1000.9 Ｃ2000.9

､SJC500.5

、SJC1000.5 C2000.5 C4000.5

Ⅲ△､UⅢnzT 1n△mU-n4B HAHpLa81 brock2002 brock200-A brocMOOユ brock400」

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

ｂｅｇｉｎｒｅｐｅａｔ

１２３４５６７８９０１

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

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

PＡｃｃ

本節では，本論文の目的である，ＫＬＳの解析における２つの検討事項について記述する．まず，ＫＬＳにおける近傍探索処理の打切り操作について３．１節で記述し，次いでＫＬＳの探索範囲について３．２節で記述

ＫＬＳの処理における内ループの終了条件はＤ＝０である(図１Linel6)．Ｄは外ループの各反復における初期クリーク，すなわち前回の反復によって得られた最良解(Cq,…)で初期化されている(Line2)．前

得られるクリーク群から最良解を選び出力する．なお，同じクリーク重みの最良解が複数個得られる場合は，最初に得られる最良解を出力する．３タイプのＫＬＳをそれぞれ有するマルチスタート法を各１０回試行

kOﾕﾕ⑥ｒ４上⑨ﾕﾕ③r5 kO11⑧z６ＰＬａｔ３００＝１

Ｐ上２t700-3

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

^２ｎＵ（ＵｎＵａＬ民）ｎＵｎＵ■Ｌロ）（ｕ▲■（Ｕ【Ｕ、】【Ｕｍｕ〔四一ｍ】ｍＬＦＬＴＬｒＬＴＬＴＬＴＬＴＬＪＬＦｄＦＬＴ＆ｌ■Ｉｑｌｑ８８勺。１００１ ^{1０１Ｚ４ＺL}

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

^９２０３５１９２２２０３５

４４５６６６７５１３１５１６１７１２６３４３ 1０９８１１１６２４２５ zＣ zＣ４４５５５２６［

６１１１６１

９４０００００００００００００００００００００００００００００００００００００１１．ＩｌｊｌｊＪｊ３ｊＪｊ５ｊ７３ｊ０１００００００６０００００００００

^１ ^３００００９００１４０３４０００００ｃＣ０ＣｔＩｔＩＩＩｆ〃■、卓■■・ａ■■『〃■由二口■ｑ■■■■『『■■■｜■■可・■■■『 ^{1００１４９１}

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

^３０００１３０００４０３８０００００００ＣＣＣにｔｆｆｆ８グロ■■｜〃■■早■■『の■■『｜〃■■△■■『■■４■■凸■■『 ^{)００１４１Ｚ}

最大クリーク問題に対するルーopt局所探索法の解析 ^8９

_{対象グラフの頂点数} ×１０o[%］

最小値(Ｍin)を示した．なお，単位は全て％である．打切り１，打切り２の欄には，打切り１，打切り２をそれぞれ施したＫＬＳを有するマルチスタート法の結果を打切りなしの欄と同様の形式で示した．

ＫＬＳによって重点的に探索をする範囲が各頂点の次数に強く依存していることがわかる．従って，ＫＬＳの探索は，各頂点の次数の影響を強く受けており，次数が多い頂点の周りを重点的に探索する傾向にあると考