タイブレーク時の頂点選択方式の検討

(1)

岡山理科大学紀要第46号Ａｐｐ３９－４８(2010）

最大クリーク問題に対する反復舟opt局所探索法のＫｉｃｋ法におけるタイブレーク時の頂点選択方式の検討

幸村明典・片山謙吾＊・南原英生＊

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

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

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

1．まえがき

組合せ最適化問題は，その多くがＮｐ-困難1)であるため，現実的な時間で良質の解を求める近似解法の研究が盛んである．近年，計算機性能の急速な向上により，多少時間はかかっても，より精度の高い解を求める解法の要求が高まっている．この目的を実現するための一般的枠組みを提供しようとするのがメタ戦略である．メタ戦略の代表的なものに反復局所探索法がある．反復局所探索法は与えられた解を改善し，

より良い解にする操作である局所探索と，局所解から脱出する操作である突然変異を繰り返し適応する手

法である．

実用上重要な組合せ最適化問題の一つに最大クリーク問題(MaximumCliqueProblemMCP)2)がある．

ここでＭＣＰの定義を示す．頂点(vertex)の集合Ｖ＝{1,…,､｝とそれらの頂点の対を両端とする無向辺 (undirectededge)の集合ＥＣＶ×Ｖが与えられた時，Ｇ＝(ⅨＥ）を無向グラフという・特に，全ての２頂点間に１つの辺が存在する無向グラフを完全グラフという．Ｖの部分集合ＶにＶによる誘導部分グラフＧ(V')＝(V',ＥｎＶ'×Ｖ')が完全グラフの時，すなわち，Ｗ,ＪＥＶ',ｊ≠ｊに対して(j,j)ＥＥである時，Ｖ'をクリークと呼ぶ．ＭＣＰとは，与えられたグラフＧに含まれるクリークの中で，頂点数最大のクリークを求める問題である．ＭＣＰは，通信ネットワーク，符号理論，並列計算，パターン認識等の分野にあらわれる実用上重要な組合せ最適化問題として知られており2)，Ｎｐ‐困難である．従って，多項式時間で

厳密解を算出するアルゴリズムは存在しないであろうと考えられている．

最近我々は，ＭＣｐに対する反復局所探索法として，反復除opt局所探索法(IteratedAmptLocalSearch，

IKLS)を提案した8)．ＩＫＬＳの局所探索法には，可変深度探索(VariableDepthSearch,VDS)6)7)のアイデ

アにもとづく舟opt局所探索法(舟optLocalSearch,KLS)'０)を使用している．また，IKLSの突然変異にはLEC-Kickを使用しており，ＤＩＭＡＣＳベンチマークグラフに対して良い結果を示している．LEC-Kick は局所探索によって得られる局所解ＣＯと接続している他の頂点ＵＥＶｌＣＣの中から，ＣＯと接続する次数が最も少ないＵをランダムに１頂点選択する．そして，選択されたＵと接続しているｃｃの頂点との間で局所解を脱出する解を生成する．前述したりＥＶＩＣＣの中からランダムに１頂点を選択する方式以外にも，このようなタイブレーク時の頂点選択方式には複数の方式が存在する．しかし，どのような頂点選択方式が有効かどうかの十分な検証はまだ行われていない．そこで，本論文では以下の項目について検討する．

（１）局所探索によって得られた局所解の累積解情報を利用したタイブレーク時の頂点選択方式(詳細は３．章を参照)を検討する．

（２）(1)で示した頂点選択方式とRestartの組み合わせにより探索がどのように変化するかを検証する.

（３）累積解情報の初期化を行うことで探索にどのような影響があるかを検討する．

（４）従来のIKLSと比較を行うことで本研究の頂点選択方式の有効性を検証する．

(2)

幸村明典・片山謙吾・南原英生 4０

procedurelKLS input:ｇｒａｐｈＧ＝(VlE)；

output：bestcliqueqestinG；

begin

generateC；ｃｏｍｐｕｔｅＰＡ，○Ｍ,anddegc(ｐＡ)；

Ｃ:＝LocalSearch(C,ＰＡ,○Ｍ,degc(pA));C6est:＝Ｃ；

ｒｅｐｅａｔ

Ｃ:＝Kick(ＧＰＡ,○Ｍ,degc(pA))；

Ｃ:＝LocalSearch(ＱＰＡ,○Ｍ,de9c(pA))；

iflCl＞|“stlthenqest:＝Ｃ;endif

ifrestart＝truethen

generaｔｅＣｉｃｏｍｐｕｔｅＰＡ,○Ｍ,andde9G(ｐＡ)；

Ｃ:＝LocalSearch(０，ＰＡ,OMdegc(pA))；

iflCl＞|C…|thenqest:＝Ｃ;endif

endif

untilterminate＝true；

returnCbest；

ｅｎｄ；

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

図１ＭＣＰに対する反復舟opt局所探索法

2．ＭＣＰに対する反復k-opt局所探索法(IKLS）

本節では，ＭＣＰに対するIterated〃optLocalSearch(IKLS)8)について記述する．ＩＫＬＳは反復局所探索法を基にしたアルゴリズムである．反復局所探索法は過去の探索で得られたよい解にランダムな変形を

加えたものを初期解として，局所探索法を反復する方法である．

2.1ＩＫＬＳの基本アルゴリズム

ＭＣＰに対する反復作opt局所探索法(Iterated〃optLocalSearch,IKLS)の流れを図１に示す．IKLSの主要な構成要素は，LocalSearch(Line2,Line5)，Kick(Line4)，Restart(Line7～11)であり，これらの反復により探索を行う．まず，初期プロセスとして，グラフＧの頂点からランダムに選択した１頂点を初期

クリークＣとし，ＰＡ,○Ｍ,de9G(pA)を更新する(詳細は2.2節を参照)(Lineｌ)．そして，Line2で初期

クリークＣに対してＫＬＳを適用することでＩＫＬＳの初期プロセスを完了する．その後，Ｌｉｎｅ３～１２のメインループによって探索を行う．Ｌｉｎｅ４では，ＫＬＳを適用して得られた解に対してＫｉｃｋを適用し，新たな初期解を生成する．Line5では，Ｋｉｃｋによって得られた解に対してＫＬＳを適用することによりさらにクリークの拡大を図ろ．Line７～１１では，探索の多様’性を持たせるための処理として，ＩＫＬＳに対してRestart処理を施す．その条件は，KLSの探索途中における最良解値(lCbestl）と同じ回数ＫＬＳを適用しても最良解の更新が無い場合である．Rest麺tにおける初期クリークとして，グラフＧの中からVlCbestである１頂点をランダムに選択する．ＩＫＬＳの終了条件(Linel2)はIKLSの処理中におけるＫＬＳの適用回数が、×１００回に到達した時，もしくは，最適解，既知の最良解と同じサイズのクリークが得られた時とする．以下で，

ＩＫＬＳの主要な構成要素であるLocalSearch，Ｋｉｃｋについて示す．

２．２LocalSearch

lKLS内部で使用するLocalSearchとして，我々が既に提案しているＭＣＰに対する舟opt局所探索法 (KLS)１０)を用いる．ＫＬＳの概要について以下に示す．

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

ＫＬＳは，ＶＤＳのアイデアにもとづいている．ＶＤＳとは，与えられた解に対して比較的小さな近傍操作を

連鎖的に適用することで到達可能な解の集合を改めて大きな近傍と捉える近傍探索のアイデアである．ＫＬＳ

は，各反復において，現在のクリーク(解)から複数個の頂点を連鎖的に追加および削除する操作(それぞれ

(3)

最大クリーク問題に対する反復A-opt局所探索法のＫｉｃｋ法におけるタイブレーク時の頂点選択方式の検討４１

procedureKLS(ＣＯ,ＰＡＰＭｄｅｇＧ(pA)）

ｂｅｇｉｎｒｅｐｅａｔ

ＣＣｐｒｅｕ:＝ＣＯ,Ｄ:＝CCP…,Ｐ:＝{1,…,〃),ｇ:＝0,97…:＝O；

ｒｅｐｅａｔ

ｉｆｌＰＡｎＰ|＞Ｏｔｈｅｎ／／AddPhase

findavertexuwithmam⑩E{pAnp}{degG(pAnp)(u)}；

ifmultipleverticeswiththesamemaximumdegreearefOund thenselectonevertexuamongthemrandomly；

ｃｃ＝ｃｃｕ{u},ｇ:＝ｇ＋1,Ｐ:＝Ｐ({u｝

ｉｆｇ＞ｇｎｚｏｍｔｈｅｎｇｍｃｚｍ：＝９，ＣＣｂｅｓｔ：＝ｃｃ；

ｅｌｓｅ／/DropPhase(if{ＰＡｎＰ}＝Ｏ）

ｆｉｎｄａｖｅｒｔｅｘｕｅ｛ｃＣｎＰ}suchthattheresultinglPAnPlismaximized；

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

ＣＣ:＝ＣＯ({U},ｇ:＝９－１，Ｐ:＝Ｐ({U}；

ifuiscontainedinOCp…ｔｈｅｎＤ＝Ｄ({u}；

ｅｎｄｉｆ

ｕｐｄａｔｅＰＡ,○Ｍ,anddegc(pA)(Z),ＶｊｅＰＡｎＰ；

untilＤ＝Ｏ；

ifgmo⑰＞ＯｔｈｅｎＣＣ:＝OObestelseCC:＝CCP…；

untilgm…≦Ｏ；

ｒｅｔｕｒｎＣＯ；

ｅｎｄ；

１２３４５６７８９０１

１１

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

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

●

● PＡｃｃ

●

０Ｍ

図３ＣＯ,ＰＡおよび○Ｍの集合の一例

Add移動，Drop移動と呼ぶ)により構成され，現在の解からそれらの操作によって生成可能な解の集合を改めて近傍と捉えることで，局所探索を行うアルゴリズムである．

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

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

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

ＰＡ(')＝{ｕ:ｕＥ(ＶICC(')),(u,j)ｅＥ,ViECC(')｝

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

○Ｍ(')＝{(u,j)：ｕｅＷｅＣＣ('),(Ｕ勾匿E,(u,j)ｅＥ,VJECC(1),ｊ≠j｝

(4)

幸村明典・片山謙吾・南原英生 4２

procedureLEC-Kick(ＣＯ,ＰＡ,ＯＭｄｅｇＧ(pA)）

begin

ifallieOOaredisconnectedtｏａｌｌｊｅＶ(CCthen

selectavertexuEVlCCrandomly;computePA,ＯＭａｎｄｄｅｇＧ(pA)；

ｃｃ:＝Ｏ;ＣＯ:＝ＣＣＵ{U};returnnewcliqueCO；

ｅｎｄif

findavertexueVlCCwiththelowestedgenumbertoverticesofCC・

ifmultipleverticeswiththesamｅｌｏｗｅｓｔｅｄｇｅｎｕｍｂｅｒａｒｅｆｂｕｎｄｔｈｅｎｓelectonevertexuamongthemrandomly；

ｄｒｏｐｖｅｒｔｉｃｅｓｆｒｏｍＣＣｔｈａｔａｒｅｎｏｔｃｏnnectedtou；

／／thedroppedverticesareremovedfrｏｍＰｉｎＦｉｇ２(line３)。nlyfbrlstiterationofthenextKLS ｕｐｄａｔｅＰＡ,○Ｍ,ａｎｄｄｅｇｃ(ｐＡ)；

ｒｅｔｕｒｎｎｅｗｃｌｉｑｕｅＣＣ；

ｅｎｄ；

１２３４５６

７

８９ 図４ＬＥＣ－Ｋｉｃｋの擬似コード

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

ない頂点の集合と捉えることもできる（なお，ＣＯＣＯＭ）（図３参照）．de9G(pA(1)）はＰＡ(')により誘導される部分グラフＧ(PA(1))内の各頂点ＵＥＰＡ(')の次数である．

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

与えられた初期クリーク（初期解）ＣＯ(o)を対象として，複数個の頂点を連鎖的に追加する操作（Add移動操作）および削除する操作（Ｄｒｏｐ移動操作）により到達可能な近傍解の集合ＣＯ(1),…,ＣＯ(ん),…,ＣＯ（７）

を得る．（その生成途中では，移動候補頂点集合Ｐ（Line2）を利用することで，追加または削除された頂点は再び追加・削除されることはない）．その近傍解の集合から最良解ＣＯ(AC)(１≦ん≦ｒ）を選び（Line8），

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

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

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

2.2.2Ａｄｄ移動頂点選択方式

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

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

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

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

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

2.3Ｋｉｃｋ

ＩＫＬＳで使用する突然変異(Kick)として，Lowest-Edges-Connectivity-basedKick(LEC-Kick)を使用する．LEC-Kickの擬似コードを図４に示す．まずLEC-Kickの例外処理(Lineｌ～4)について説明する．与えられたクリークｃｃに対して，グラフＧにおけるｃｃ以外の頂点群ＶｌＣＣが全く隣接していない場合，

LEOKickを適用することができない．この場合，例外処理として，ＶｌＣＣから１頂点をランダムに選択し，その１頂点を新たなクリークとみなし，探索を継続する．以下，LEC-Kickの具体的な操作について示

す．ｃｃが与えられた時，ＶＩＣＣで，ＣＯの頂点群と最低１頂点以上隣接している頂点集合から，隣接して

いる数が最も少ない頂点Ｕを選択する(Line５）選択する頂点の候補が複数個存在する場合は，それらの頂

(5)

最大クリーク問題に対する反復A-opt局所探索法のＫｉｃｋ法におけるタイブレーク時の頂点選択方式の検討４３点群からランダムに１頂点を選択する(Line６）そして，頂点ｕと頂点ｕに隣接するＣＯの頂点群とで新たなクリークを構成する(Line７～8)．なお，KickによってＣＯから削除された頂点群は，次回のＫＬＳの探索における１回目の反復で集合Ｐ(図２，Line２)から除外する．

図５はｃｃが与えられたときに，隣接している頂点の中からどの頂点が選ばれるかを示したものである．

ＣＯには頂点ｕ,～ｕ４が接続している．これらの頂点は図４のline5で選択される頂点である．LEC-Kick ではＣＯと最小次数で接続しているｕ４が選ばれる．

〃１

図５ＬＥＣ－Ｋｉｃｋの頂点選択

3．タイブレーク時の頂点選択方式 3.1累積解情報に基づく頂点選択方式

前述の2.2.2節や2.2.3節及びＫｉｃｋの擬似コード図４のＬｉｎｅ６で行われる，タイブレーク時の頂点選択方式は複数の候補頂点の中から，ランダムに１つの頂点を選択するものであった．本節ではＫｉｃｋにおけるタイブレーク時の頂点選択方式としてランダムに選択する方式を含め，３種類の頂点選択方式を示す．ＩＫＬＳではＫｉｃｋによって得られた候補頂点群の中から，より適切な頂点を選択する基準として，ＩＫＬＳの探索の途中で発見されるクリークの情報を利用する．現世代ｔの探索によって得られた局所解をＣＯ(t）とする．ｔ世代までの探索において発見されたＣＯ(1)，…，ＣＯ(t-')の情報を蓄積したものを累積解情報とよぶ．累積解情報は任意の頂点がクリークを構成するための頂点として，何回算出されたかをカウントしたものである．図６は累積解情報と与えられたグラフにおける，頂点の関係を表したものであり，円で囲まれているｃｃ(t)は探索により発見されたクリークを示している．図は説明を簡単化するためにクリーク以外の頂点にのみ番号を付けている．累積解情報の各添字は，グラフの頂点の番号に対応している．累積解情報の添字１には，グラフの番号ｌの頂点が算出されたクリークに何回含まれていたかのカウント数を格納している．この図では番号１の頂点は３回クリークを構成するための頂点であったことを示している．この累積解情報を使用し，候補頂点の中から１頂点を選択する．頂点の選択方式は以下の３種類とする．

（１）すべての候補頂点からランダムに選択する(累積解情報は使用しない）

（２）累積解情報の値が最も小さい頂点を選択する．

（３）累積解情報の値が最も大きい頂点を選択する．

3.2累積解情報の初期化

ここでは前節で示した累積解情報の初期化について述べる．累積解情報を用いた探索では，局所探索により発見される解がそれ以後の局所探索に影響を与える．累積解情報は局所解を脱出する解を生成する時に，

Ｋｉｃｋにおいて選択可能な頂点の中から１頂点を選択する際に使用する．頂点の選択方法に工夫を施すこと

で探索全体の多様化，集中化を調節する．もし，累積解情報に蓄積される局所解の情報が望ましいものでは

ない場合，累積解情報に基づいて生成される局所解を脱出する解は，次期局所探索に好ましくない影響を

与える．そして，局所探索によって得られる解に対して適用されるＫｉｃｋは結果的に，劣悪な局所解を脱出

(6)

幸村明典・片山謙吾・南原英生 4４

累積解情報

llllUlillll1iil

図６累積解情報と各頂点の関係

する解を生成する可能性が高いと考えられる．そこで，累積解情報を初期化する(累積解情報のカウントを 0にする）ことを考える．累積解情報の初期化の方法は以下の３つである．

（１）累積解情報を初期化しない．

（２）Restart時に累積解情報を初期化をする．

（３）RestartをIKLSに組み込まない場合は，探索中に発見された既知の最良解のサイズを超えた解を発

見したときに累積解情報を初期化する．

4．ＩＫＬＳの性能評価実験

本節では，３．節で示したタイブレーク時の頂点選択方式の相違によるＩＫＬＳの探索`性能について検討を行う．

4.1実験の詳細

タイブレーク時の頂点選択方式の相違によるＩＫＬＳの探索性能を評価するために，３種類の頂点選択法にRestart，累積解情報の初期化の有無を組み合わせた１０タイプのＩＫＬＳを比較検討する．対象とするグラフは，ＭＣＰの標準的なベンチマーク問題としてよく知られるＤＩＭACSベンチマークグラフ(最大頂点数4000,最大辺数5506380)'1)から大規模もしくは厳密解の算出が困難な３５グラフとする．ＩＫＬＳの終了条件は，ＬＳ回数､ｘ100回時もしくは既知の最良解の値(BR)に一致した解を算出時とし，試行回数は各問題例に対して２５回とする．全てのＩＫＬＳはＣ言語によってコード化し，使用コンパイラは，最適化オプション－０２を付加したｇcｃ（Ver､4.1.2）である．全ての実験は，Hewlett-Packam社の計算機HPxw4300 WbrkstationCPU:Pentium４３．４ＧＨｚ，４ＧＢＲＡＭ，ＯＳ:ＵｂｕｎｔｕｌＯＯ４上で行う．

4.2実験結果

結果を表１，２に示す．DIMACSbenchmarksの欄には，問題例名(Instance)と既知の最良解(BR)（＊

がついたＢＲは最適解値であることが証明されている）を示したＩＫＬＳの欄には，異なるタイプの頂点選択方式を有する１０種類のＩＫＬＳの結果を示しており，各ＩＫＬＳの２５回試行中に得られた最良解値の最大値(Best)，平均値(Avg)，最良解を得るまでに掛かった秒数の平均(Time)をそれぞれ示している．また，

表の下にある総合計(Tbtal)はBest，Avg，Timeの値をそれぞれ合計したものである．ＩＫＬＳの欄にある random，min，ｍａｘは３種類の頂点選択方式を示している．randomは選択可能な頂点群の中からランダムに１頂点を選択する．ｍｉｎは選択可能な頂点群の中から累積解情報が最小の頂点を選択し，ｍａｘは累積解情報が最大の頂点を選択する．また，ＲはRestartを使用しており，ＮＲはRestartを使用していないことを示している．Ｆは累積解情報の初期化を示しており，ＮＦは初期化を行わないＦ(R)はRestart時に累積解情報を初期化し，Ｆ(B)はIKLSの探索において今までに発見された最良解を超える解を発見したとき

に累積解情報を初期化する．

表１，及び表２から，１０種類のＩＫＬＳの中で最もIbtalのＡｖｇが良かったのは、in＋Ｒ+ＮＦであった．

ｍin＋Ｒ+ＮＦは多くの問題例で他の手法と同等かそれ以上の結果を算出している．また，brock800-4の問

題例に対しては最も良好な結果を示した．次に，各方式の問題例毎の有効`性を検証する．ｍin＋Ｒ＋ＦＲは

(7)

最大クリーク問題に対する反復A-opt局所探索法のＫｉｃｋ法におけるタイブレーク時の頂点選択方式の検討４５

ＭＡＮＮ－ａ４５，Ｃ2000.9の問題例で良い結果を示している．ｍin＋Ｒ＋ＮＦではbrock800-4の問題例に対して他の手法と比べ良好な結果である．max＋Ｒ＋ＦＮはＣ1000.9の問題例でより効率的な探索を行っている．

ｍin＋ＮＲ+ＦＢはbrock400-2やbrock800-2の問題例に対して良い結果を示している．max+ＮＲ+ＮＦは C2000.5やkeller6で他の手法と比べて同等かそれ以上の結果を示している．

ｍｉｎの方式に注目する．ｍｉｎの方式は他のrandomやｍａｘの方式と比べ良い結果である．ｍｉｎの方式は探索中で局所解として算出された回数が最も少ない頂点を選択することから，他の方式であるrandomやｍａｘと比べ，より多様性のある探索を行うことができる．また，max＋ＮＲ+ＮＦのIbtalのＡｖｇは実験した全ての方式の中で最も悪いものであった．max＋ＮＲ+ＮＦは検証する方式の中で探索の多様性が最も小さいものである．これらの結果から，ＭＣＰに対してはより多様性のある探索が有効であると考えられる．

我々が行ったＭＣＰに対する地形解析の結果はそのほとんどの問題例で大谷構造が観測できないというものであった9)．これは言い換えると，ＭＣｐに対してはより多様`性のある探索が必要ということである．従っ

て，本実験の結果は地形解析の結果に支持されるものであった．

前述のことを踏まえ、in+Ｒ，min+ＮＲの結果に注目すると，ｍin+ＮＲ+ＦＢと、in+ＮＲ+ＮＦはRestaｪｔを使用する、in＋Ｒ+ＦＲやrandom＋Ｒと比べIbtalのＡｖｇが良い結果を示している．このことから，ｍｉｎはRestartを使用しなくても探索の多様`性を＋分に保持できるのではないかと推測される．また，max+Ｒ，

max+ＮＲを比較するとmax+Ｒの結果がＮＦ，ＦＢＦＲに関係無く良いものである．しかしながら，ｍａｘは探索の多様性を十分に保持していると考えることは難しい．ｍａｘの方式はより多く算出される頂点を選択する方式であり，Ｋｉｃｋの中で探索の集中化を行っていると考えられる．そのため，Restartを行うことで探索に多様`性を持たせる方式が，Restartを行わない方式よりも良い結果を算出したと推測される．

以上より，１０タイプのＩＫＬＳを検討した結果，総合的に見て、in＋Ｒ＋ＮＦを組み込んだIKLSによって算出された結果が最も良い結果であることを確認した．

5．むすび

本論文では，ＭＣＰに対するＩＫＬＳを示し，その内部に導入可能な複数の頂点選択方式の相違による探索性能を調査した．異なる３種類のＫｉｃｋにおけるタイブレーク時の頂点選択方式にRestart，累積解情報の初期化を組み合わせた計１０種類のＩＫＬＳの比較実験において，ｍin＋Ｒ＋ＮＦを有するＩＫＬＳが全体的に良好な結果を示した．実験の結果からＭＣＰにおいてはより多様`性のある探索が必要であると考えられる．しかし，各問題例毎の詳細な結果を見ると，各手法は有効に働く問題例に違いがあった．

次に今後の課題を２つ示す．(1)本論文で検討した累積解情報に基づく頂点選択方式はKLSのAdd移動頂点選択方式(2.22節)やDrop移動頂点選択方式(223節)へも導入が可能であり，どのような結果を示すのか大変興味深い．(2)有効性の異なる複数の頂点選択方式を適応的に使い分けることにより，アルゴリ

ズムの性能を向上させることである．

参考文献

1）MGarey,andDJohnson,``Computersandlntractability：AGuidetotheTheoryofNP-Completeness,”

FYeeman，ＮｅｗＹｏｒｋ，１９７９．

２）IBomze,MBudinich,Ｐ､Pardalos,ａｎｄＭ､Pelillo,“Themaximumcliqueproblem,，'inHandbookofCom- bina力orialOptimiz帥ion(suppLVOLA),Ｄ－ＺＤｕ,PMPardalos(Eds.),ｐｐ､1-74,Kluwer,1999.

3）Ｕ・Rige,Ｓ・Goldwasser,Ｌ,Lovdsz,SSafra,ａｎｄＭ・Szegedy,``Approximatingcliqueisalmostnp-complete,'，

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

1991.

4）Ｓ､Arora,ＯＬund,Ｒ・Motwani,Ｍ・Sudan,ａｎｄＭ､Szegedy,“Proofverificationandthehardnessofapproxi- mationproblems,，，Proc・the33rdAnnualSymposiumonPbundationsofComputerScience,Pittsburgh,ＰＡ１

ｐｐｌ４-23,1992

5）JHAstad,“Cliqueishardtoapproximatewithinn1-c,，，ActaMathematica,voL182,ｐｐ､105-142,1999.

6）SLinandBKernighan,“AneflectiveheuristicalgorithmfOrthetravelingsalesmanproblem,''０perations

Research，voL21，pp498-516,1973.

(8)

幸村明典・片山謙吾・南原英生 4６

表１累積解情報を使用するＫｉｃｋとRestartを使用するＩＫＬＳの結果

ＤＳＪＣ５ｕＵ．

、ＳＪＣ１０００．５Ｃ2０００．５

ｈ日mmngB-4１６

，画ﾕﾕ8１０－４４０

ｋｎＩ１□ｚ４ｒｎｌｌＢｒ５ｋ

中本＊＊＊＊臣ＪＲ）勺上幻缶、三つ一氏）▲缶》Ｒ》、奎勺Ｊ■Ｌ沿紐Ｒ〉■▲Ｒ）（ソ

ＤＳＪＣ５ＤＳＪＣ１００

Ｃ２＠ｍ

ｌＷＵＲＵｎｚ７１２６１Ｗ、１４５３４５

ｈＢｍｍｎｇＢ－４ｈＢ四ｍｇｌｏ－４４０

ユｋ２Ｉ１■丁

１日

７）BKernighanandS.Ｌin,“AnefTicientheuristicprocedurefbrpartitioninggraphs,，'BellSystemHchnical

Journal,voL49,pp291-307,1970.

8）KKatayama,Ｍ､Sadama九su,andHNarihisa,``Iteratedk-optLocalSearchfOrtheMaximumCliqueProb‐

ｌｅｍ,，，Proc､ofSeventhEuropeanConferenceonEvolutionaryComputationinCombinaLorialOptimisation

（EvoCOP-2007),LNCS4446,Springer-Verlag,pp84-95,Valencia,Spain,Aprilll-13,2007.

9）上野伸郎，濱本明宏，片山謙吾，成久洋之，“最大クリーク問題に対する地形解析，，，平成１６年度電気・情報関連

学会中国支部第５５回連合大会講演論文集，ｐ、３７６，０ct」6,2004.

10）KKatayama,Ａ､Hamamoto,andHNarihisa,“AnefTectivelocalsearchfOrthemaximumcliqueproblem,'’

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

11）DJohnsonandMITick,“Cliques,coloring,andsatisfiability,''SecondDIMACSImplementationChallenge，

lkLLj己

Ｉｎｓｔａｎｃ〔

ｒａｎｄｏｍ＋皿ｍｉｎ＋Ｒ＋ＦＲｍｉｎ＋Ｒ＋ＮＦ

ｎａｒｎｅ

ＢＲ

ＢｅｓｔＡｖｇｒｌｍｅ

^Ｂｅｓｔ

Ａｖｇ

^Ｔｉｍｅ ^Ｂｅｓｔ

Ａｖｇ

^Ｔｉｍｅ

０１２５．９Ｃ250.9 Ｃ500.9 Ｃ1000.9 Ｃ2000.9

＊＊４４７８８３４５６７、嘔嘔ｗＯ０９５

ｏｏＬ記

９

５７

●５２２

０００８４０００８０

●●●●●

４４７７６３４５６７

ｊｊｊｊ

５５５５２２２２

ノノノノ

５５５２ｚ２２２

ｌＩくく

４４７８３４５６

１５２

ノ

２Ｉ７

７４４７７６３４５６７

１１１１

５５５５２２２２

ノノノノ

５５５２２２２２

くＩｌく

４４７８３４５６

ｊ５２

ノ６

く７

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

４４７７５３４５６７

ｊｊｊｊ

５５５５２２２２

ノノノノ

５５５２２２２２

くＩｌＩ

４４７８３４５６

１５２ノ２Ｉ７７

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

、SJC500.5

､ＳＪＣ1000.5 Ｃ2000.5

＊＊３５６

１１１

1３（２５／２５）１３１５（２５／２５）１５１６（２５／２５）１６

０００．０５９００１．３６４００５．６４６

1３（２５／２５）１３１５（２５／２５）１５１６（２５／２５）１６

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

1３（２５／２５）１３１５（２５／２５）１５１６（２５／２５）１６

０００．０５７００１．５０８００４．４０８

臘蓋： ^３４５ ^１２６

^車^中 126（２５／２５）126.000.034

345（２３／２５）３４４．９２７６１．９５６ 126（２５／２５）１２６．０００．０２７

345（２３／２５）344.92706.207 126（２５／２５）１２６．０００．０３３ 345（２１／２５）344.84638.367

broEk?､n2

brcek?､n-4 brock4002 brock400畠 brock8002 brock800-4

＊＊中中（ニヴ０（ソロＪ幻坐Ｒ）１つ・上か二句）句ニワ』

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

●●●●●●

００３１３５

００８０２０００８０１８

■ＤＣＣ●●

２７７３１１

１１２３２２

１１１Ｊ５５５５２２２２

ノノノノ５５８５ｚ２１２

ｌｌｌｌ

２７９３

１１２３ｊｊ

５５２２

ノノ

１４

く！

４６２２

２１

７８３１２３

１２

ｊｊｊｊｊ５５５５５２２２２２

ノノノノノ

５５０５５

２２２２２

くくくｌく

２７９３１

１１２３２２２ｊ５２

ノ６

^Ｉ６２

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

ｊｊｊｊ

５５５５２２２２ノノノノ５５４５２２２２

！ｌｌＩ

２７９３

１１２３１Ｊ

５５２２

ノノ

１９

^ｌＩ

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

gen200-pO､９－“

gen200-pO・g-55 gen400平０．９－５５ g0n400-pO･g-65 ge□400-p０．９－７５

中本４５５５５４５５６７４５５５５４５５６７

^{ｊｌｊｊｊ}

５５５５５２２２２２

ノノノノノ

５５５５５２２２２２

ｌくくくく

４５５５５４５５６７００２００００００００００００４５７４５１０５２１００６００４５５５５４５５６７

^{ｊｊｊｊｊ}

５５５５５２２２２２

ノノノノノ

５５５５５ｚ２２２２

ｌｌくくＩ

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

ｊｊｊｊｊ

５５５５５２２２２２

ノノノノノ

５５５５５ｚ２２２２

ｌＩｌｌｌ

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

hamming8-4

磑画、鞆SUB毎１，－ａ

１６４０

中 1６（２５／２５）１６４０（２５／２５）４０

ＯＯＯＯＯＯ

０００

０２３

1６（２５／２５）１６

４０（２５／２５）４０

^ＯＯＯＯＯＯ０００

０２２

1６（２５／２５）１６４０（２５／２５）４０

^００００００

００００２１ k⑧Ｉ１ｅｒ４

ｋ⑧ｌｌｅｒ５ｒ⑬1】⑨T６

１１２７５９

甲 1１（２５／２５）１１２７（２５／２５）２７５９（２５／２５）５９

００００００００８

ＯＯＯＯ２７５５４

1１（２５／２５）１１２７（２５／２５）２７５９（２５／２５）５９

ＯＯＯＯＯＯＯＯ５

００００３２８７０

1１（２５／２５）１１２７（２５／２５）２７５９（２５／２５）５９

ＯＯＯＯＯＯＯＯｇ

００００２８４１６

p-hat300-1

p上at300-2 p上at300-3 p｣1a七700-1 Ｐ上at700-2 p-hat700-3 Ｐ上atl500-1 p上atl500-2 p上atl500-3

中本中中＊中臣ＪＲ）勺上幻缶、三（色区）扣乏ＣＯ、奎勺Ｊ■Ｌ沿紐Ｒ〉■▲Ｒ）、ワ

３２６７５０，０４ｍｍ叩叫ｍｍ３叫四０ｏｏｏ０ｏｍ０ｏ叩皿叩ｍｍｍｍｍｍ８２３１４６１６９，５６１４２２５４

^１^５^２^ノ^５^２^く^８

ｊｊｊｊｊｊｊｊ

５５５５５５５５２２２２２２２２

ノノノノノノノノ

５５５５５５５５２２２２２２２２

くＩＩくくくくＩ

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

^１^５^２

^ノ

^５^２^Ｉ^８

５５５５５５５５２２２２２２２２

５５５５５５５５２２２２２２２ｚ

ｌｌくくｌｌくＩ

５６１４２２５４２３１４６１６９３１５７４７７４４０００４０１２３９００００００２００Ｏ００Ｏ００７００叩Ⅲ、叩四ｍｍⅢ、８２３１４６１６９．５６１４２２５４

^ｊ^５^２^ノ^５^２^く^８

５５５５５５５５２２２２２２２２

ＩくＩｌくｌｌＩ

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

ｒｂｔａｌ１７４０１７３０．６４ｌＵ９Ｕ・ｂＢＵ１７３７１７３１．４４１０１０．７２３１７４０１７３２．４４８８３．４７２

ｌｋＬＬ弓

Iｎ３ｔａｎｃｅ

ｍａｘ＋Ｒ＋ＦＲｍａｘ＋Ｒ＋ＮＦ

ｎａｌｎｅ

ＢＲ

ＢｅｓｔＡｖｇＴｎｍｅ

^Ｂｅｓｔ

Ａｖｇ

^Ｔｉｍｅ

０１２５．９Ｃ250.9 Ｃ500.9 Ｃ1000.9 C2000.9

＊＊４４７８８３４５６７

０５９嘔叩、唖６●●●戸〃。

００１５

１

０

５

●０３２

０００８４０００８２

Ｓ■ｃ●●

４４７７６３４５６７

１１１Ｊ

５５５５２２２２

ノノノノ

５５５２２２２２

１ＩくＩ

４４７８３４５６

１５２ノ６Ｉ

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

ｊｊｊｊ

５５５５２２２２

ノノノノ

５５５４２２２２

^ｌくくく

４４７８３４５６

１５２ノ

６

Ｉ７

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

、SJC500.5

､SJC1000.5 C2000.5

＊＊３５６

１１１

1３（２５／２５）１３１５（２５／２５）１５１６（２５／２５）１６

０００．０４１００１．８０７００５．２５４

1３（２５／２５）１３１５（２５／２５）１５１６（２５／２５）１６

0０００４９００１．２２８００５．０５３ HADmU=n27

MANN-a45 1２６３４５

＊

＊ 126（２５／２５）１２６．００００２８

345（２１／２５）344.84７１０．５７３ 126（２５／２５）１２６０００．０２７ 345（１７／２５）３４４．６８607.706

brock200-2

broCと?0D-4 brock400-2 brock400-4 brock8002 brock800-4

中中中中

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

●●ｅ●①□

００４１２４

００６０２０００３０１０

ｓ●●●ａ●

２７８３１２

１１２３２２

ｊｊｊｊ５５５５２２２２

ノノノノ５５１５２２２ｚ

ｌｌｌｌ

２７９３

１１２３１Ｊ

５５２２

ノノ

１５

ｌく

４６２２

２

１７７３１１１２３２２

１１１Ｊ５５５５２２２２

ノノノノ

５５７５

２２１２

くくＩく

２７９３

１１２３Ｊ１

５５２２

ノノ

２４

^くく

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

gen200pO､９－“

gen200-pO･g-55 gen400-pO･g-55 gen400-pO･g-65 gen400-p０．９－７５

＊＊４５５５５４５５６７４５５５５４５５６７

ｊｊｊｊｊ

５５５５５２２２２２

ノノノノノ

５５５５５２２２２２

くＩくＩく

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

ｊｊｊｊｊ

５５５５５２２２２２

ノノノノノ

５５５５５２２２２２

^{ＩくｌＩＩ}

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

hamming8-4 hamminglO-4

１６４０

中 1６（２５／２５）１６

４０（２５／２５）４０

^０００ ^０００ ^０００ ^０２３

1６（２５／２５）１６４０（２５／２５）４０

^ＯＯＯ ^ＯＯＯ

００００２０ k⑨l1Gr4

k⑨１１⑨r5 k■1Ｔ⑥r６

１１２７５９

中 1１（２５／２５）１１２７（２５／２５）２７５９（２５／２５）５９

ＯＯＯＯＯＯＯＯ８

００００３４５８６

1１（２５／２５）１１２７（２５／２５）２７５９（２５／２５）５９

００００００００４

ＯＯＯＯ２８７１３

Ｐ上at300-1

p上at300-2 p上at300-3 p-hat700-1 P上at700-2 p上at700-3 P上atl500-1 p-hatl500-2 p上atl500-3

＊＊中中＊字戻り公Ｕ勺上幻缶へ二へ奎臣）幻缶。。〈二口）勺Ｌ幻仏侯Ｕ可ＬＲＵｎコ

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

^１５２ノ５２Ｉ

８ ５５５５５５５５２２２２２２２２

５５５５５５５５ｚ２２２２２２２

ｌＩくｌくくｌＩ

５６１４２２５４２３１４６１６９２１５６５９７４４０００５０１５３９００００００３００唖皿血応哩唾呼哩唖ｏｏｏｏｏｏｍｏｏ叩皿皿ｍｍｍｍｍｍ８２３１４６１６９．５６１４２２５４

^１^５^２

^ノ

^５^２^Ｉ^８

５５５５５５５５２２２２２２２２

ノノノノノノノノ５５５５５５５５２２２２２２２２

くＩくくくｌｌＩ

５６１４２２５４２３１４６１６９

Ｔｂｔａｌ１７４０１７３１．４４１０３８．４８０１７４０１７３０．６０９８５．８９１

(9)

最大クリーク問題に対する反復k-opt局所探索法のＫｉｃｋ法におけるタイブレーク時の頂点選択方式の検討４７表２累積解情報を使用するＫｉｃｋとRestartを使用しないＩＫＬＳの結果

、９８－４ユユｇ１ｏ－４

Ｂｍｒ４

５ユ且zＥ

う0７３４－４用

、ＳＪＣ５００．５ＤＳＪＣｍＯＯ

Ｃ２０００，５

ｈ日四四ｍｇ８－４ｈＢｍｍｎｇＯ－４

Bｍｚ４５ユ囚ｒＧ

ＤＩＭＡCSSeriesinDiscreteMathematicsandTheoreticalComputerScience,AmericanMathematicalSociety’

1996.

１１ＬＬ軍

Iｎｓｔａｎｃｅｒａｎｄｏｍ＋ＮＬＬｍｍ＋ＮＲ＋ＦＢ

ｍｉｎ＋ＮＲ＋ＮＦ

ｎａＪｎｅ

ＢＲ

ＢｅｓｔＡｖｇ

^Ｔｉｍｅ巳ｅＢｔＡｖｇｌ､iｍｅ巳ｅｓｔＡｖＲＴｉｍｅ

０１２５．９Ｃ250.9 Ｃ500.9 C1000.9 C2000.9

＊＊４４７８８３４５６７４４７７６３４５６７

^ｊｊｊｊ

５５５５２２２２

ノノノノ

５５５４２２２２

くくｌく

４４７８３４５６

１５２

ノ

５く７７

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

４４７７６３４５６７

１１１Ｊ５５５５句

２２２２２

ノノノノ

５５５９２２２１

Ｉくｌく

４４７８３４５６ノ

７く

７７ ０００．００００００．０１４００２．１０２ 7６４８．４５８２０２５１．８５６

皿匹遜廻》００２６エ

０００８００００８２

●●●●、

４４７７６３４５６７

Ｊｊｊｊ５５５５

２２２２

ノノノノ

５５５２２２２２

ｌｌｌｌ

４４７８３４５６

１５２

ノ

１Ｉ

８

７

､SJC500.5

、SJC1000.5 C2000.5

＊＊３５６

１１１

1３（２５／２５）１３１５（２５／２５）１５１６（２５／２５）1６

0００．０６１００１．６３９００３．３００

1３（２５／２５）１３１５（２５／２５）１５１６（２５／２５）１６

０００．０６３００１．８８９００６．７３０

1３（２５／２５）１３１５（２５／２５）１５１６（２５／２５）１６

０００．０３８００１．９５８００４．３９０

繍二翼 ^１２６ ^３４５

^＊^＊ 126（２５／２５）126.000.037

345（８／２５）344.32345.492 1２６（２５／２５）126.00０．０２９

345（７／２５）３４４．２８276.040 1２６（２５／２５）126.000.029 345（６／２５）344.24３６９００１

brock200-2

brock2OO-4 brock4002 brock400-4 brockBOO2 brock800-4

＊＊中本

２７９３４６

１１２３２２

２７７３１１

１１２３２２ｌｊｊｌ５５５５２２２２ノノノノ

５５８５

２２１２くくくく

２７９３１１２３

ｊｊ

５５２２ノノ１２

^ｌく

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

００８０１４

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

’２７８３１２ ’１１２３２２

ｊｊｊｊ５５５５２２２２

ノノノノ

５５４５

２２２２

くｌくく

２．７９３

１１２３ｊｊ

５５２２

ノノ

４６

^ｌく

４６２２

４８３２１５

５０８５０５０２９９６０

●●●●白●

００３０５５

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

０ｑ●●●●

００４１４９

００２０６０

００５０３４

⑥。●の●０

２７８３１２

１１２３２２

ｊｊｊｊ５５５５２２２２

ノノノノ

５５２５

ｚ２２２

ｌｌｌｌ

２７９３

１１２３Ｊ１

５５２２ノノ３７

くく

４６２２

gen200-pO gen20o-Po gen400-pO gen40qpO gen400-pO

“鍾星鎚妬９９９９９

＊＊

ん缶且）区Ｊ貝）Ｅｕ幻幾頁Ｊ貝）Ｒｕ守‐

４５５５５４５５６７

^{ｊｊｊｊｊ}

５５５５５２２２２２

ノノノノノ

５５５５５２２２２２

くくくくＩ

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

^{ｊｊｊｊｊ}

５５５５５２２２２２

ノノノノノ

５５５５５ｚ２２２２

ｌｌｌくＩ

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

ｊｊｊｊＪ

５５５５５２２２２２

ノノノノノ

５５５５５２２２２２

くくくくく

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

ｈ、耐、

ｈ肉、、

１６４０

＊ 1６（２５／２５）１６

４０（２５／２５）４０

^０００ ^０００ ^００００２３

1６（２５／２５）１６

４０（２５／２５）４０

^ＯＯＯＯＯＯ０００

０１８

1６（２５／２５）１６

４０（２５／２５）４０

^ＯＯＯＯＯＯＯＯＯｋｅ１１ｅｒ４Ｏ１ｇ

ｋ⑨11⑧ｒ５ｋ③l１ｅｒ６

１１２７５９

＊ 1１（２５／２５）１１２７（２５／２５）２７５９（２５／２５）５９

００００００００６

００００３５７６７

1１（２５／２５）１１２７（２５／２５）２７５９（２５／２５）５９

ＯＯＯＯＯＯＯＯ５

００００２８７３３

1１（２５／２５）１１２７（２５／２５）２７５９（２５／２５）５９

OＯＯＯＯＯＯＯ５

００００２８５７７

Ｐ上at300-1

p-hat300-2 p-hat300-3 p-hat700-1 p-hat700-2 p-hat700-3 P上atl500-1 P-hat1500-2 p-hatl500-3

中本中中＊

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

●■■●●０

００００００

０

●

８

１５２

ノ

５２

く

８７４

７

１

５４３９００００

００００００００

巳●巳●□●●●

５６１４２２５４２３１４６１６９

ｊｊｊｊｊｊｊｊ５５５５５５５５２２２２２２２２

５５５５５５５５

２２２２２Ｚ２２

ｌｌくｌｌくくＩ

５６１４２２５４２３１４６１６９

４１６５４５両０８ｍｍ叩叱ｍｍ６ｍ叩ｏｏｏｏｏｏｍｏｏ ^０ ^０ ^８

^ｊ^５^２

^ノ

^５^２^く

^８

００００００００００００００００

●●●●●●●●

５６１４２２５４２３１４６１６９

ｊｊｊｊｊｊｊｊ５５５５５５５５２２２２２２２２

ノノノノノノノノ５５５５５５５５

２２２２２２２２

くくくくくｌくく

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

ｍｍ叩印加、、、肥

ｏｏｏｏ００ｍｏ０

叩皿皿皿皿皿皿、、

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

^１^５^２

^ノ

^５^２^Ｉ

８

ｊｊｊｊｊｊｊｌ５５５５５５５５２２２２２２２２ノノノノノノノノ５５５５５５５５

２２２２２２２２

^{くｌくくＩくｌく}５６１４２２５４

２３１４６１６９

'Iｂｔａｌｌ７４Ｕl７２９．８０６４９．３４４」ｒ４Ｕｌ７Ｕ１．７ｂ６２２．０２８ 1７４１１７３１．６０７３４．４６５

L｣几Ｌ＝

IｎＢｔａｎｃｅｍａｘ＋1,1“＋ｒ､己ｍａＸ十ＮＲ＋ＮＦ

ｎａＸｎｅ

ＢＲ巳ｅｓｔＡｖｇＴｉｍｅ巳ｅＢｔＡｖｇＴｉｍｅ

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

中中４４７８８３４５６７４４７７６３４５６７

ｊＪｊｊ

５５５５２２２２

ノノノノ

５５５３

２２２２ＩＩＩ１

４４７８３４５６

ｊ５２

ノ

５く

７

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

皿唖巫錘》．．。８３００１４２

０００８８０００８０

■●●●●

４４７７６３４５６７

ｊｊｊｊ５５５５

２２２２

ノノノノ

５５５２２２２２

くくくく

４４７８３４５６

ｊ５２

ノ６

く７

７ ､SJC500.5 ＤSJC1000.5 C2000.5

＊＊３５６

１１１

1３（２５／２５）１３１５（２５／２５）１５１６（２５／２５）１６

０００．０５４００２．２０７００４９４０

1３（２５／２５）１３１５（２５／２５）１５１６（２５／２５）１６

００００４６００１．２３９００３．２２４ XABlDl127

XAMU-24E １２６３４５

＊

＊ 126（２５／２５）126.00０．０２３

345（７／２５）344.28430.920 1２６（２５／２５）１２６．０００．０２８ 345（２／２５）３４４．０８９１．９７８

brock?｡｡_Q

brock200-4 bzock400-Q brock400-4 brock8002 brock800A

＊＊中中

２７９３４６

１１２３２２

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

●■■■■□

００３２１２

００４０２０

００２０１４

●Ｂ●●●●

２７７３１１

１１２３２２

ｊｊｊｊ５５５５２２２２

ノノノノ５５４５２２１２

くくくく

２７９３

１１２３ｊｊ

５５２２

ノノ

１２

Ｉく

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

２１５３２８◆■のｑ■ｃ

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

●●●●●●

２７７３１１

１１２３２２

ｊｊｊｊｊ５５５５５２２２２２

ノノノノノ

５５６５５

ｚ２１２２

ｌＩくＩ！

２７９３１

１１２３２１５

２

ノｚｌ６２

gen200-PO gen200-PO gen400-PO gen400Po gen400-Po

g-4j4 9-55 9-55 9-65 9-75

＊＊４５５５５４５５６７４５５５５４５５６７

^{ｊｊｊｊｊ}

５５５５５２２２２２

ノノノノノ

５５５５５２２２２２

くくくくく

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

^{１１１１Ｊ}

５５５５５２２２２２

ノノノノノ

５５５５５２２２２２

^{ＩくＩ～く}

４５５５５４５５６７００２００ｏＯｏＯＯ０００００２６４９２１００１１００２００

ｈａ回ming8-4 hamminglO-4

１６４０

中 1６（２５／２５）１６

４０（２５／２５）４０

^０００ ^０００ ^０００ ^０２０

1６（２５／２５）１６４０（２５／２５）４０

^ＯＯＯＯＯＯ

0０１０１７ kn11er4

ke11er5 knller6

１１２７５９

中 1１（２５／２５）１１２７（２５／２５）２７５９（２５／２５）５９

００００００００５

００００４０５４８

1１（２５／２５）１１２７（２５／２５）２７５９（２５／２５）５９

ＯＯＯＯＯＯＯＯ４

００００３２１６０

p-hat300-1

p-hat300-2 p-hat300-3 p-hat700-1 p上at700-2 p上at700-3 p上atl500-1 p上atl500-2 p上atl500-3

＊＊＊＊＊＊貝）ＲｕでＬＡ邑冗色へ缶臣Ｊ幻缶ＣＯヘニロ）勺上幻缶ＲＵ１▲Ｒ）（リ

嘔皿唖唾哩吋豚唖唖ｏｏｏｏｏｏｍｏｏ６９

●

７

１５２

ノ４２

く

８００００００００００００００００

０■ｅ●●■■●

５６１４２２５４２３１４６１６９

ｊｊｊｊｊｊｊｊ５５５５５５５５２２２２２２２２

ノノノノノノノノ５５５５５５５５２２２２２２２２

！ｌｌくくｌくく

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

●●①●●●

ｏＯ０ＯｏＯ

２

９

●７

ｊ５２

ノ

３２

く

８

１９

８０３０９３８００

●巾

００ ０００００６０００００００９００

●●●●●Ｓ⑤●

５６１４２１５４２３１４６１６９

ｊＪｊｊｊｊｊｊ

５５５５５５５５２２２２２２２２

５５５５５４５５２２２２２２２２

くくｌくｌくくく

５６１４２２５４２３１４６１６９

Ｔｂｔａｌ 1７４０１７２９．００７８８．４８９ 1７３７１７２８．８８４２６．８２６

(10)

幸村明典・片山謙吾・南原英生

4８ VCrtexSelectionbasedTie-BreakiｎｇＭｅｔｈｏｄｓｉｎＫｉｃｋ五℃chniqueoflterated冷一ｏｐｔＬｏｃａｌＳｅａｒｃｈｆｂｒｔｈｅＭａｘｉｍｕｍ

ＣｌｉｑｕｅＰｒｏｂｌｅｍ

ＡｋｉｎｏｒｉＫＯＭＵＲＡ，ＫｅｎｇｏＫＡＴＡＹＡＭＡ*，ＨｉｄｅｏＭＩＮＡＭＩＨＡＲＡ＊

ＧｍｄｕｑｔｅＳｃ/Zoolq/Engmeerm9，

＊DepqrtnLentqfIiq/brmQtjonandCOmPUterEn9mee伽９，

FhcmltZ/qfEn9Zneerm9,ＯｈＱＷ７ＤｑＵｎｊｕｅ畑tZﾉqfScjence・

Ｉ－ＺＲｊｄｑｊ－ｃ/DC，Kjta-Au，OAqZ/qmq700-0005，Ｊｑｐｑ〃

（ReceivedSeptember30，2010;acceptedNovember9，２０10）

Manymetaheuristicshavebeenproposedfbrcombinatorialoptimizationproblems・Oneofthetypecal metaheuristicsiswellknowntobeiteratedlocalsearch(ILS)Inmanycases,ILShasbeenshowntobe capableoffinding(near-)optimumsolutionsfbrdifIicultcombinatorialoptimizationproblems

lnthispaper,weinvestigatethreetypesofvertexselectionbasedtie-breakingmethodsinwhichcan beusedinlLSfbrthemaximumcliqueproblem(MCP）ILSalgorithmswitheachofthemethodsare evaluatedonDIMACSbenchmarkgraphs・TheresultsshowthattheperfOrmanceoflLSalgorithmswith

タイブレーク時の頂点選択方式の検討

岡山理科大学紀要第46号Ａｐｐ３９－４８(2010）

最大クリーク問題に対する反復舟opt局所探索法のＫｉｃｋ法における タイブレーク時の頂点選択方式の検討

幸村明典・片山謙吾＊・南原英生＊

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

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

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

1．まえがき

より良い解にする操作である局所探索と，局所解から脱出する操作である突然変異を繰り返し適応する手

法である．

実用上重要な組合せ最適化問題の一つに最大クリーク問題(MaximumCliqueProblemMCP)2)がある．

厳密解を算出するアルゴリズムは存在しないであろうと考えられている．

最近我々は，ＭＣｐに対する反復局所探索法として，反復除opt局所探索法(IteratedAmptLocalSearch，

IKLS)を提案した8)．ＩＫＬＳの局所探索法には，可変深度探索(VariableDepthSearch,VDS)6)7)のアイデ

（１）局所探索によって得られた局所解の累積解情報を利用したタイブレーク時の頂点選択方式(詳細は ３．章を参照)を検討する．

（２）(1)で示した頂点選択方式とRestartの組み合わせにより探索がどのように変化するかを検証する.

（３）累積解情報の初期化を行うことで探索にどのような影響があるかを検討する．

（４）従来のIKLSと比較を行うことで本研究の頂点選択方式の有効性を検証する．

幸村明典・片山謙吾・南原英生 4０

procedurelKLS input:ｇｒａｐｈＧ＝(VlE)；

output：bestcliqueqestinG；

begin

generateC；ｃｏｍｐｕｔｅＰＡ，○Ｍ,anddegc(ｐＡ)；

Ｃ:＝LocalSearch(C,ＰＡ,○Ｍ,degc(pA));C6est:＝Ｃ；

ｒｅｐｅａｔ

Ｃ:＝Kick(ＧＰＡ,○Ｍ,degc(pA))；

Ｃ:＝LocalSearch(ＱＰＡ,○Ｍ,de9c(pA))；

iflCl＞|“stlthenqest:＝Ｃ;endif

ifrestart＝truethen

generaｔｅＣｉｃｏｍｐｕｔｅＰＡ,○Ｍ,andde9G(ｐＡ)；

Ｃ:＝LocalSearch(０，ＰＡ,OMdegc(pA))；

iflCl＞|C…|thenqest:＝Ｃ;endif

endif

untilterminate＝true；

returnCbest；

ｅｎｄ；

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

図１ＭＣＰに対する反復舟opt局所探索法

2．ＭＣＰに対する反復k-opt局所探索法(IKLS）

本節では，ＭＣＰに対するIterated〃optLocalSearch(IKLS)8)について記述する．ＩＫＬＳは反復局所探 索法を基にしたアルゴリズムである．反復局所探索法は過去の探索で得られたよい解にランダムな変形を

加えたものを初期解として，局所探索法を反復する方法である．

2.1ＩＫＬＳの基本アルゴリズム

クリークＣとし，ＰＡ,○Ｍ,de9G(pA)を更新する(詳細は2.2節を参照)(Lineｌ)．そして，Line2で初期

ＩＫＬＳの主要な構成要素であるLocalSearch，Ｋｉｃｋについて示す．

２．２LocalSearch

lKLS内部で使用するLocalSearchとして，我々が既に提案しているＭＣＰに対する舟opt局所探索法 (KLS)１０)を用いる．ＫＬＳの概要について以下に示す．

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

ＫＬＳは，ＶＤＳのアイデアにもとづいている．ＶＤＳとは，与えられた解に対して比較的小さな近傍操作を

連鎖的に適用することで到達可能な解の集合を改めて大きな近傍と捉える近傍探索のアイデアである．ＫＬＳ

は，各反復において，現在のクリーク(解)から複数個の頂点を連鎖的に追加および削除する操作(それぞれ

最大クリーク問題に対する反復A-opt局所探索法のＫｉｃｋ法におけるタイブレーク時の頂点選択方式の検討４１

procedureKLS(ＣＯ,ＰＡＰＭｄｅｇＧ(pA)）

ｂｅｇｉｎ ｒｅｐｅａｔ

ＣＣｐｒｅｕ:＝ＣＯ,Ｄ:＝CCP…,Ｐ:＝{1,…,〃),ｇ:＝0,97…:＝O；

ｒｅｐｅａｔ

ｉｆｌＰＡｎＰ|＞Ｏｔｈｅｎ／／AddPhase

findavertexuwithmam⑩E{pAnp}{degG(pAnp)(u)}；

ifmultipleverticeswiththesamemaximumdegreearefOund thenselectonevertexuamongthemrandomly；

ｃｃ＝ｃｃｕ{u},ｇ:＝ｇ＋1,Ｐ:＝Ｐ({u｝

ｉｆｇ＞ｇｎｚｏｍｔｈｅｎｇｍｃｚｍ：＝９，ＣＣｂｅｓｔ：＝ｃｃ；

ｅｌｓｅ ／/DropPhase(if{ＰＡｎＰ}＝Ｏ）

ｆｉｎｄａｖｅｒｔｅｘｕｅ｛ｃＣｎＰ}suchthattheresultinglPAnPlismaximized；

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

ＣＣ:＝ＣＯ({U},ｇ:＝９－１，Ｐ:＝Ｐ({U}；

ifuiscontainedinOCp…ｔｈｅｎＤ＝Ｄ({u}；

ｅｎｄｉｆ

ｕｐｄａｔｅＰＡ,○Ｍ,anddegc(pA)(Z),ＶｊｅＰＡｎＰ；

untilＤ＝Ｏ；

ifgmo⑰＞ＯｔｈｅｎＣＣ:＝OObestelseCC:＝CCP…；

untilgm…≦Ｏ；

ｒｅｔｕｒｎＣＯ；

ｅｎｄ；

１２３４５６ ７８９０１

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

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

● PＡ ｃｃ

０Ｍ

図３ＣＯ,ＰＡおよび○Ｍの集合の一例

Add移動，Drop移動と呼ぶ)により構成され，現在の解からそれらの操作によって生成可能な解の集合を 改めて近傍と捉えることで，局所探索を行うアルゴリズムである．

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

最大クリーク問題に対する反復舟opt局所探索法のＫｉｃｋ法におけるタイブレーク時の頂点選択方式の検討

（１）局所探索によって得られた局所解の累積解情報を利用したタイブレーク時の頂点選択方式(詳細は３．章を参照)を検討する．

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

本節では，ＭＣＰに対するIterated〃optLocalSearch(IKLS)8)について記述する．ＩＫＬＳは反復局所探索法を基にしたアルゴリズムである．反復局所探索法は過去の探索で得られたよい解にランダムな変形を

ｂｅｇｉｎｒｅｐｅａｔ

ｅｌｓｅ／/DropPhase(if{ＰＡｎＰ}＝Ｏ）

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

１２３４５６７８９０１

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

● PＡｃｃ

Add移動，Drop移動と呼ぶ)により構成され，現在の解からそれらの操作によって生成可能な解の集合を改めて近傍と捉えることで，局所探索を行うアルゴリズムである．

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

ifmultipleverticeswiththesamｅｌｏｗｅｓｔｅｄｇｅｎｕｍｂｅｒａｒｅｆｂｕｎｄｔｈｅｎｓelectonevertexuamongthemrandomly；

ない頂点の集合と捉えることもできる（なお，ＣＯＣＯＭ）（図３参照）．de9G(pA(1)）はＰＡ(')により誘導される部分グラフＧ(PA(1))内の各頂点ＵＥＰＡ(')の次数である．

与えられた初期クリーク（初期解）ＣＯ(o)を対象として，複数個の頂点を連鎖的に追加する操作（Add移動操作）および削除する操作（Ｄｒｏｐ移動操作）により到達可能な近傍解の集合ＣＯ(1),…,ＣＯ(ん),…,ＣＯ（７）

を得る．（その生成途中では，移動候補頂点集合Ｐ（Line2）を利用することで，追加または削除された頂点は再び追加・削除されることはない）．その近傍解の集合から最良解ＣＯ(AC)(１≦ん≦ｒ）を選び（Line8），

LEOKickを適用することができない．この場合，例外処理として，ＶｌＣＣから１頂点をランダムに選択し，その１頂点を新たなクリークとみなし，探索を継続する．以下，LEC-Kickの具体的な操作について示

ここでは前節で示した累積解情報の初期化について述べる．累積解情報を用いた探索では，局所探索により発見される解がそれ以後の局所探索に影響を与える．累積解情報は局所解を脱出する解を生成する時に，