河本敬子・片山謙吾＊・成久洋之＊

(1)

岡山理科大学紀要第３７号Appl27-135(2001）

探索傾向に基づいた知識の導入によるlD-opt局所探索法の研究

河本敬子・片山謙吾＊・成久洋之＊

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

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

（2001年11月１日受理）

１序論

近年，最適化問題に対する効率的な解法として，遺伝的アルゴリズム(GeneticA1gorithm,ＧＡ)，アニーリング法，タブー探索法やそれらの変形版などのアルゴリズムであるメタ戦略が提案されてきた．メタ戦略は，基本解法である局所探索法（LocalSeaJ｢ch,ＬＳ）などと自然界に存在するアイデアを結合させることによって，比較的短時間に高品質な近似解を算出可能である．この一例として，ＧＡにＬＳを組み込んだ遺伝的局所探索法(GeneticLocalSeaJFch,GLS)などが挙げられるが，ＧＬＳで費やされる探索時間の多くはＬＳが占めている場合が多い．このことから，メタ戦略で多く用いられるＬＳの性能を維持しつつ，探索時間の大幅な効率化を可能にする方法の提案が期待されている．

本論文では，バイナリー２次計画問題（BinaryQuadraticProgrammingProblem,BQP）を取り上げ，

ＢＱＰに対して知られているＬＳの中でも，最も有効なk-Opt局所探索法（A-Opt法）に焦点をあてる．このk-Opt法は，1960年代後期から７０年代前期において，巡回セールスマン(travelingsalesmanproblem）

およびグラフ分割問題(graphpartitioningproblem)に対してＬｉｎとKemighanにより提案された局所探索法[13,16]のアイデア（可変深度探索,vaJFiabledepthsearch）に基づき，近年ＢＱＰに対してMerzと Freislebenによって提案された[181ＢＱＰに対する作叩t法では，良好な近傍解を探索し，その近傍解への移動を繰り返すことで最終的に良質な近似解を算出する．しかしながら，近傍解探索のプロセスは必ずしも効率的ではないため，近傍解探索を打切るためのパラメータが準備されている．このパラメータ設定によってルー叩t法自体の探索時間をある程度短縮できることが知られているが，十分な知識の導入による検

討はなされていない

本論文の目的は，k-opt法の近傍解の探索傾向に基づいた知識の導入による大幅な探索時間の効率化手法の提案である．本論文では，２でバイナリー２次計画問題，３．１でＢＱＰに対するA-Opt局所探索法について記述する．次に，３．３でんOpt法における既存のパラメータ設定による近傍解の探索傾向を分析し，その観測結果を用いてMerzらが示したパラメータ設定[18]をベースにした新たな方法を４に提示する．その結果，既存のパラメータ設定との比較において，同等の探索性能を維持しつつ，探索時間を大幅に短縮可能であることを示す．

２バイナリー２次計画問題

バイナリー２次計画問題（BQP）とは，、×、の対称行列Ｑ＝(qが)が与えられたとき，次の目的関数

泥冗

巾）＝⑳ロ⑳＝ＺＺ９`j剛，，

ｉ＝１ｊ＝１

ｚｄＥ{0,1}V‘＝1,…,、（１）

を最大化する解勿を求める問題である[５１ＢＱＰは，NP-困難であり，数多くの応用例を有している．例として，ＣＡＤ問題[15]，マシンスケジューリング問題[１１capitalbudgetingandfinancialanalysis問題[17]，

trailicmessagemanagement問題[6]，分子構造問題[21]などがある．更に，ＢＱＰは様々な組合せ最適化問題と同等であることが知られている．そのような問題として，最大カット問題，最大クリーク問題，最大

頂点パッキング問題，最小頂点被覆問題，最大独立集合問題などがある[3,5,8,19,201

(2)

河本敬子・片山謙吾・成久洋之 1２８

３ＢＱＰに対するルーopt局所探索法 3.1k-Opt局所探索法

最初に，局所探索法で利用される解の表現について記述する．ＢＱＰにおける解勿は，長さ、で構成される各ビットユワォ(i＝1,…,､)にＯもしくは１を持つ，Ｏ~１ビット表現である．また’0と１のどのような組合せであっても実行可能解となるため，ＢＱＰの解空間Ｘのサイズは２河となる．最も簡単な近傍は，解ｚに対して，ｊ番目のビットを反転することによるLOpt近傍である．このとき，一度に生成可能なLOpt近傍解の数は、に等しく，Lopt近傍を有する局所探索法はL0pt局所探索法（】~叩t法）と呼ばれる.】~Opt法は,各繰り返しにおいて，現在解の目的関数加)と冗個からなるI-0pt近傍解の地')とのゲイン9(＝ｆ(Z')￣/(z)）

が最大となる近傍解を生成しながら探索を進め，その最大となるゲインがＯもしくは負となるときを終了

条件とするものである．また，ルーOpt近傍jVk-opt(z)＝{z'eXldH(`Ｍ')三A｝(｡〃は二つの解のハミン

グ距離を指す)は，一つのビットからk個のビットを－度に反転することにより到達可能な解の集合と定義

され，１sの数に応じて指数的（|jVk-optl＝〃ん）となる.

ＢＱＰに対するルーOpt近傍は，連続的なLOpt近傍操作によって到達可能な解集合とされる.具体的には，

各ビットに対して１回のみ行うことを保証したビットの反転を連続的に行うこれは，最大のゲインを持つピットを連続的に反転することによりｎ個の解集合を生成し，そのｎ個の解集合の中の最良解をｋ~Opt近傍解とするものである．よって，ＢＱＰに対するルーOpt近傍は，各繰返しにおいて’～ん個の可変的なピットの反転によって構成され，一般的にｈの数を常に固定した完全ルーOjDt近傍よりも効率的な探索を可能にする．

現在解ｚにおけるｊ番目のピット(ZjE{0,1})を反転し得られる近傍解評価のためのゲイン値gjは,次式で求められ，Ｏ(､)時間を要する．なお，巧＝１－mjである．

几

９，＝qjj(珂一錘，)＋２Ｅ帆(司一⑳j）（２）

ゴー1,学』

式(2)を用いてｎ個のLOpt近傍解のゲイン値を計算するには，Ｏ(､2)時間を要する．Merzらは，ｎ個の LOpt近傍解のすべてのゲイン値を線形時間で可能とするゲイン更新法を採用しており[18]，我々のA-Opt

法でもこの更新法を取り入れた．

ここで，図１に示すＢＱＰに対するk-Opt法の擬似コードをもとにアルゴリズムを説明する．このアルゴリズムは，外ループと内ループの二つの繰返し処理から構成される．各変数は，探索中に算出された最良解ｍ６…を保持するためのｚｐ…最良解伽｡tのゲイン値０m…現在解ｚのゲイン値０，近傍解へ移動するために現在解に対して反転操作を実施し得るピット番号を保持するＣである．内ループ中の処理は，Ｃのすべてのピットを反転させることにより，生成された７０個の解の中から最大のゲインＧｍｃ懇を有するz6e8t をA-opt近傍解とする．次に，外ループでは，このような探索操作を良好な近傍解が生成できなくなるまで繰返す．このルー叩t法は，deterministicであるため，与えられた初期解に依存した局所最適解を算出する．

片山らはメタ戦略に局所探索法の導入を前提として，そのルーopt法にランダム性を与えた，ランダムルーOpt 法を提案している[10,111文献[9,12]では，GLSなどのメタ戦略には，ランダムルーOpt法を導入する方

が良好な解を算出しやすいことが示唆されている．

３２k-０Pt局所探索法のパラメータ、について

ＢＱＰに対するdeterministick-0pt局所探索法の基本アルゴリズムは，内ループにおいてｎ個の解の生成を巧妙に行い，その解集合の中から最良の解を選ぶ．しかしながら，探索時間の効率化を考えると，常にｎ個の解を調べる必要はなく，実際的にはそれよりも比較的少ない個数の解を調べることで，（保証は無いが）

最良解を選び出すことが可能になる．Ｍｅｒｚらは，内ループの終了条件（Ｏ＝Ｏになるまで）を内ループで保持されるｚ…が見つかった時点から数えて、回の内ループの繰返しにおいても最良解が更新されなければ，内ループを強制的に終了する方法に修正し，探索時間の短縮を試みた．これにより，パラメータｍを

(3)

探索傾向に基づいた知識の導入によるルーqPz局所探索法の研究 ¹²⁹

ｍ＜、のように設定する場合は，基本アルゴリズムよりも探索時間の効率化が可能であることを述べている[l81Merzらは，このｍを100とすることを推奨した一方，片山らのランダムルーOpt法でも同様のパラメータが存在し，ｍを５０と推奨している[101舟Opt法は，ｍの設定値によって，最終的に得られる解や探索に要する探索時間に影響を及し，無駄な探索時間を省くことができると考えられる．

procedurek-Opt-Local-Search(z’９）

ｒｅｐｅａｔ

Ｚｊ,…:＝Ｚ,Ｇm・麺:＝0,0:＝0,Ｃ:＝｛1,…,､}；

ｒｅｐｅａｔ

ｆｉｎｄｊｗｉｔｈｇｊ＝maxiEo9i；

Ｇ:＝Ｇ＋ｇｊ；

ｉｆＧ＞０ｍα霧ｔｈｅｎＧｍａ錘：＝０，z6est:＝ｚ；

ｚｊ:＝l-zj,ｃ:＝ｃＷ}；

updategains9ifbrallj；

untilＯ＝０；

ｉｆＧｍｃ麺＞Ｏｔｈｅｎｚ：＝ｚ６ｅｓｔｅｌｓｅｚ:＝ｚｐ…；

untilGmQ垂≦Ｏ；

ｒｅｔｕｒｎｚ；ｅｎｄ；

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

図１ルーopt局所探索法

3.3ルーOpt法における探索傾向の分析

本論文では，greedyに生成された初期解による解からスタートするA-OPt法に関する探索傾向を分析する．それは，将来的にメタ戦略へk-opt法を導入する場合の影響について検討するためであり，より実際的な効果を観測できるものと期待できる[14]、これは，多くの場合に局所探索法はメタ戦略の主力探索法になり得ることに起因している．例えば，メタ戦略の一つと知られるＧＬＳでは，突然変異や交叉操作によって生成された解は，ランダム解よりも比較的良好な解となり，greedyな初期解と類似するものと考えることができるからである．なお，greedy解法[18]は，ランダム性を有しており，計算機上で与えるランダムの種などに応じて異なる近似解を生成可能である．greedｙ解法により平均的に得られる解質は，以下に記述する問題例に対して，多くの場合に，既知の最良解から約１％～5％程度と比較的良い．

表１は，greedyな初期解に対する基本アルゴリズムの各外ループにおいてＧｍａ麺を得たときの内ループの繰返し回数を示す．ここで，内ループの繰返し回数をIteInLoopと表記する．この結果は，１００回の実行による平均である．本実験では，ＢＱＰの良く知られたテスト問題[4]から500～2500変数までの大規模な45個の問題例を扱うこれらの問題例は，Ｇ１overらによる500変数の５個の問題例(glov500)[7]，Kochenberger らによる1000変数の10個の問題例(kb-g)[２１Beasleyによる500,1000,2500変数の問題例(beas500，

beaslOOO,beas2500)[5]で，それぞれは10個の問題例を含む．全問題例は，ORLIB[4]より取得可能であり，これらは，問題サイズ，各問題例の行列Ｑのdensity（de7L8(Ｑ):行列ＱにおいてＯ以外の数値が含

まれる割合）などの違いがある．

Ｍｅｒｚらのパラメータｍを１００とした方法での各外ループにおけるIteInLoopは，Ｇｍａｍが得られてから最大100回を必要とする．しかしながら，表ｌによると，毎回Ｇ､｡露が得られてから１００回も内ループを行う必要はないと考えられる．例えば，glov500-1において０m…が得られたときのIteInLoopは，１回目の外ループでは２６，２回目の外ループでは１２となっており，外ループの回数が増すごとにＧｍｑ麺を得るときのIteInLoopは，徐々に減少することが観測できる．また，他の問題例においても同様の傾向がみられる．

(4)

河本敬子・片山謙吾・成久洋之 1３０

これらの観測から，各外ループにおいてＧnｍｍが得られたときのItelnLoop付近で内ループを打切れぱ，解質をできるだけ落とさずに計算時間を大幅に短縮できると考えられる．

表１を更に分析すると，９１｡v-500の各問題例に対する１回目の外ループにおいてＧ…錘を得たときの IteInLoopの平均値は，２６～３０となっており，いずれも，問題サイズ〃の約1/20である．また，２回目以降の各外ループにおいてＧｍａ露を得たときのIteInLoopの平均値は，前回の外ループにおけるIteInLoopの約1/2であることが観測できる．更に，他の各問題例群においても同様の探索傾向がみられたこのように，外ループの回数が増すにしたがって，Ｇｍａ露が得られたときのIteInLoopは問題例の特徴の違いに関係なく，平均的に減少する傾向が確認された．

４探索傾向に基づいた知識の導入によるAMpt局所探索法

本論文での探索傾向に基づく知識を導入したk-opt法について記述する．提案する方法は．探索時間を大幅に短縮させるために，近傍解探索の分析結果に基づき基本となる内ループの繰返し回数を決定する．そして，探索状況から更に内ループを追加することによって，近傍解生成の打切りを効率的に行う．我々の提案する新たな方法は，表１によるk-opt法の探索傾向の分析から得られた知識を導入することによって，内ループの繰返し回数を効率的に変動させることを可能としている．

以下に，探索傾向に基づく知識を導入したルー叩t法のアルゴリズムを説明する．この方法は，図１の基本アルゴリズムで示した１－１０行目を図２のように書き換えたものである．ここで，図２に示す擬似コードをもとにアルゴリズムを説明する．各変数は，現在の内ループの繰返し回数を示すＬＧｍａ露が得られたときの内ループの回数Lgm…前回の内ループでのゲイン値ｃｐ…，内ループの基本繰返し回数!，ある区間におけるＧの増減を調べるためのｐである．Ｊの値は，表１の各外ループにおいてGmo塗を得たときの IteInLoopに基づいて決定する．１回目の外ループでのｌは問題サイズ、の1/２０，２回目以降の外ループのＩは前回の外ループで０m･麺が得られたときのIteInLoopの1/２とした．

Ｌ:＝０，ＬｇｍＱｚ：＝０，Ｇｐ…：＝0,1,ｐ；

updateム repeat

L＋＋；

ｆｉｎｄｊｗｉｔｈｇｊ＝maxdEo9d；

Ｇ:＝Ｇ＋ｇｊ；

ｉｆＧ＞ＧｍｏｚｔｈｅｎＧｍａ露：＝Ｇ,z6eat:＝ｚ,Ｌｇｍａ錘:＝Ｌ；

ｚｊ:＝l-zj,ｏ:＝ｏＷ}；

updategains9ifbrallj；

ｉｆ((Ｌ三J)ａｎｄ(G，…≦Ｇ)ａｎｄ(Ｌ三p))thenbreak；

Ｇｐ７ｅＵ＝G untilC＝０；

if(Lgm…＞Ｌ－ｐ)thenp:＝Ｌ＋P,goto2；

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

図２探索傾向に基づいた知識の導入によるA-opt局所探索法

このアルゴリズムでは，まず内ループの基本繰返し回数としてＩ回の内ループを繰返した後，更に１０行

目の現在のＧと前回の内ループで得られたＧｐ…の比較においてＧの増大がみられなくなるまで内ループを繰返す．１３行目では，区間[Ｌ－ｐ,L]における広範囲なＧの増減を調べ，その区間内においてＧｍ･麺が得られていれば，今後，Ｇｍｃｪが更新される可能性があると考え，現時点から更にｐ回の内ループを繰返す．

ここでは，区間を決定するための変数ｐの初期値を２０とした

(5)

探索傾向に基づいた知識の導入によるA-cｿM局所探索法の研究 ^1３１

次に，図３を用いてその様子を詳細に示す．我々の提案する方法では，内ループの基本繰返し回数【によって，内ループの繰返し回数が１回または１回からＧの増大がみられなくなった時点で内ループを打切り，無駄な繰返しを大きく省くことができる．しかしながら，この時点から何回かの内ループを繰返すことによってＧm･垂が更新されるかもしれない．そこで，現時点までの内ループにおけるＧの増減によって，

今後，内ループにおいてＧｍａ麺が更新される可能性を考慮した予測を行う．これによって，我々は現時点と現時点からｐ回前の区間[Ｌ－ｐ,L]の内ループにおいてＧ…が得られていれば，現時点から更にｐ回の内

ループを繰返す方法を提案した．

了剰^／

ロロ圏印

ニーニーニーーや

：

現時点 innerloopL

図３Ｇm･垂が更新される可能性を考慮した予測

５数値実験

上で提案した探索傾向に基づく知識を導入したルー叩t法の有効性を検討するために，ベンチマーク問題を用いて，ｍを１００に固定したＭｅｒｚらのk-OPt法との比較を行う．実験は，表１で扱った問題例を使用する．

すべての実験は，NECPC98-NXMate(PentiumⅢ,650ＭHz)上で実行され，プログラム言語はＣ言語で

ある．

表２は，greedyな初期解に対するk-0pt法の実験結果である．各欄は，既知の最良解値(best-known)，ｍの値を従来通り100に固定，新しい方法に対して，1000回の試行で得られた最良解(best)と既知の最良解からのその解質(%)，平均値(avg)とその解質(%)，全計算時間ｔ（秒）を示す．更に，新しい方法の有効性を検討するために，従来法に対する平均の解質差(loss)，全計算時間の短縮率(r-t)を示す．

例えば，glov500-3の問題例における従来の方法によるａｖｇの解質は0.251％，計算時間は３７秒であるのに対し，新たな方法では，ａ凡７９の解質が0.287％，計算時間は３秒となっており，0.036％の解質の低下で計算時間を91.9％短縮できている．また，全問題例におけるａｖｇの解質の低下具合の差は従来の方法に対

して，平均0064％の低下で，計算時間は平均65.3％の短縮が可能である．

これらの結果から，我々の提示した方法は，最終的に得られる解質をできるだけ維持しつつ，探索時間を大幅に短縮可能であることを示した．よって，実用的な観点からメタ戦略に導入する場合にも，非常に有効であると考えられる．

(6)

河本敬子・片山謙吾・成久洋之 1３２

６結論

本論文では，ルー叩t法の探索傾向の分析から得られた知識の導入による近傍解生成の打切りを行うことによって，大幅な探索時間の効率化手法を提案した．我々の提案する方法は，既存の効率化手法に比べ，平均的な解質をできるだけ維持しながら，探索時間を大幅に短縮できることを示した．

表１各外ループにおいてGmo錘を得たときのItelnLoopの平均

outer-1oop

~I~｢ﾛｰｒ５Ｔｚ~｢5~｢5~｢７－｢§~｢5~｢IＵ

配１２８咄５８，０００００１２３４５６７８９０００００００００００００００００００００５５５５５５５５５５ＮＭＮＭⅡＨＭＭⅡⅢⅡⅡⅡⅡⅡⅡⅡⅡⅡⅡⅡⅡⅡⅡⅡⅡⅡⅡⅡⅡ ０１２３４５６７８９１１２３４５６７８９１００》”州ｗｗ椒剛卿卿卿卿剛卿ＭＭＭ鰄蠅醐鰄鰄鰄鰄鰄Ⅷ鰄脚剛刎細剛刎刎剛刎刎剛剛鯏帆細細細細鯏刎ｇｇｇｇｇｋｋｋｋｋｋｋｋｋｋｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂ

壕

^{０００００００００１} ^{●●■●●●●●●●}^{１２３４５６７８９０} ^{２２３２２．} ^{４６５５４６６５６６} ^{１０４７７３５３５２}^{６６０６８’} ^■^|ｌｉＪ^’｜^jｉｉｌ^{２２３２２３３２３３} ^{０９２８６４４７６２}

LｌLｉ

^{１１２１１２２１１２} ^{３５３８５４２９８０} ^６_９ ^１「し ^{１１１１２}

’

１５１１７１３

１２９９１１

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

１１

１１１１１１

１１

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

１

１１１１１

１１

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

１

１１

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

１

１１１１１１１１１１１

(7)

探索傾向に基づいた知識の導入によるルーclPz局所探索法の研究 ^1３３

表２greedyな初期解に対する実験結果

＝

ujLIjl^００ ^{０２０７１} ^{１５５５０} best 1001610.000^611940000 1380350.000 1727710.000 1905０７００００

61036.0390.258 99931.3910.229 137638.6560.287 171936.2190.483 189910.8590.313

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

６１０５９．０６６０．２２１ 999632030.197 137688.4840.251 172016.0310.437 190017.6250.257 61194

100161 138035 172771 190507

611940.000 1001610.000 1380350.000 1727710.000 1905070000

130618.3980.637 171621.2500.675 189248.1561.722 213056.6251.216 240647.0310.710 240016.1251.347 249400.5311.652 261805.2810.932 258957.4221.409 270615.3751.370

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

1314410.011 1727880.000 1925650.000 2150190.306 2423670.000 2430180.113 2526180.383 2640770.072 2626240.013 2740460.120 130696.5230.57821

171795.2340.57559 189560.8131.56073 213336.8911.086108 240838.2340.63197 240444.3131.171145 249826.6251.484129 262086.2810.826150 259387.0311.245182 271032.4381.218215 1314410.011

1727880.000 1925340.016 2153740.141 2423670.000 2431320.066 2535610.011 2640770.072 2626240013 2740300.126 131456

172788 192565 215679 242367 243293 253590 264268 262658 274375

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

1165860000 1283390.000 1308120.000 1300770.015 1254870.000 1217720.000 1222010.000 1235300.023 1207980.000 1306190.000

115813.3670.663 127934.0390.316 130504.5940.235 129619.1170.367 124858.5700.501 121092.6560.558 121281.2580.753 122853.8910.571 120089.1090.587 130197.3050.323

１３３４２５５４４３

115890.3910.597 127963.6800.292 130538.9610.209 129672.2270.327 124946.6250.431 121175.9920.489 121376.3360.675 122926.3360.512 120173.6170.517 130259.3050.275

２９０００５００１４１１１１１１１１１

1165860.000 1283390.000 1308120.000 1300770.015 1254870.000 1217720.000 1222010.000 1235300.023 1207980000 130619０．０ 116586

128339 130812 130097 125487 121772 122201 123559 120798 130619

１１１１１１１１１１●●●●●●●●●●００００００００００

370635.9060.216 353341.5310.448 369465.8750.477 369565.3130.299 351434.2810.376 358301.9690.369 369642.0310.418 350555.5310.409 347679.5000.474 350002.4690.402 3714380.000

3549300.001 3712360.000 3706050.019 3527300.009 3594520.049 3710470.039 3517850.059 3493370.000 3512260.054

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

370718.6880.194 353504.2500.402 369663.2810.424 369705.8440.261 351584.0000.333 358467.3750.323 369812.7810.372 350711.6560.364 347868.6560.420 350170.1250.354

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

3714380.000 3546310.085 3712360.000 3706750.000 3527300009 3596290.000 3711930.000 3518940.028 3493370.000 3514150000 371438

354932 371236 370675 352760 359629 371193 351994 349337 351415

１１１１１１１１１１●●●Ｇ●●●●●●００００００００００

15152110.0481509448.1250.429 14703860.0681467242.8750.282 141353000471409957.2500.299 15077010.0001504263.5000.228 149177000031487737.2500.273 14682930.0591464696.6250.304 14776570.0941473176.8750.396 148419900001481283.6250.196 14816570.0511478685.7500.251 14824620.06014788330000.305

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

７００７３７３１４３２１２０１１２９２１１１１１１１１１１

15150980.0561510182.6250.380 14703860.0681467646.0000.255 14136130.0411410490.0000.262 15077010.0001504721.3750.198 149179600011488286.2500.237 146831900571465333.8750.261 14781260.0621473872.6250.349 14841990.0001481679.2500.170 148205100241479224.3750.215 14825440.0551479378.3750.268

１１１１１１１１１１●●●●●●●●●●００００００００００

1515944 1471392 1414192 1507701 1491816 1469162 1479040 1484199 1482413 1483355

(8)

河本敬子・片山謙吾・成久洋之

134

参考文献

［1］Ｂ・A1idaee,０A・Kochenberger,Ａ・Ahmadian,``O-1quadraticprogrammingappro江hfbeoptimalsolutionoftwo schedulingapproachfbrtheoptimalsolutionoftwoschedulingproblem8,，，InternationalJournalofSystem8Science，

voL25，ｎｏ､２，ｐｐ､401-408,1994．

［2］Ｍ､Ｍ・AminiandBAlidaee,ａｎｄＧＡ・Kochenberger,``Ascattersearchappro錘htounconstrainedquadraticbinaxy programs,，'NewldeasinOptimization(eds,Ｄ・Corne,Ｍ・DorigoandFGlover),McGraw-Hill,ｐｐ､317-329,1999．

［3］FBarahona,Ｍ・Jiinger,Ｇ・Reinelt，“Experiment8inquadraticO-1programming,，，MathematicalProgramming，vol､44,ｐｐ､127-137,1989．

［4］Ｊ・EBeasley)``OR-Library:di8tributingte8tproblemsbyelectronicmail,，，JoumaloftheOperationalResearchSociety，

vol､41,ｎｏ､11,ｐｐ,1069-1072,1990．

［5］JEBeasley,``Heuri8ticalgorithmsfbrtheunconstrainedbinaryquadraticprogrammingproblem,，，TbchnicalReport，

ManagementSchool,ImperialCollege，ＵＫ，1998．

［6］GGallo,PLHammer,Ｂ・Simeone,``Quadraticknapsackprograms,'，MathematicalProgrammingvoL12,pp､132-149,_1980．

［7］Ｆ・Ｇ１over,Ｇ､A・Kochenberger,ａｎｄＢ・Alidaee，‘`Adaptivememorytabu8earchfbrbinaryquadraticprogramB,'，

ManagementScience,voL44，ｎｏ､３，ｐｐ､336-345,1998．

［8］ＰＬ・Mnescu,``SomenetworMowproblemssolvedwithpseudo-Booleanprogramming,，，OperationsResearch,voL13，

ｐｐ､388-399,1965.

[9］KKatayama,Ｍ・TEni,andHNarihi8a，``Acompari8onofgeneticlocalsearchalgorithm8fbrbinaryquadratic programming,，，nchnicalReportofIEICE(COMP),COMP2000-12,voL100,ｎｏ､52,ｐｐ､49-56,Ｍａｙ2000．

[10］片山謙吾,成久洋之，``バイナリー２次計画問題に対する変形ん-Opt局所探索法,，，信学誌(A),voLJ84-A,ｎ0.3,ｐｐ､430435,

Mar，2001．

[11］Ｋ､Katayama,Ｍ・nni,ａｎｄＨ・Narihi8a,``SolvinglargebinaryquadraticprogrammingproblemBbyeflbctivegenetic localsearchalgorithm,,,Proc・ofthe2000GeneticandEvolutionaryComputationConference，JuL8-12，LasVega8，

ＵＳＡ，ｐｐ､643-650,2000.

[12］KKatayamaandHNarihisa,``Onfilndamentaldesignofparthenogeneticalgorithmfbrthebinaryquadraticpro‐grammingproblem,,,

[13］Ｂ､Ｗ・KernighanandS.Ｌin,``AnefIicientheuristicprocedurefbrpartitioninggraph8,，，BellSystemTbchnicalJournal，

voL49，ｐｐ､291-307,1970．

[14］Ｋ,Ｋohmoto,Ｋ・Katayama,andHNarihisa,``EmpiricalKnowledgeofaParameterSettinginルーOptLocalSearch fbrtheBinalyQuadraticProggrammingProblem,，，Proc・ofthe2001SeventeenthlntemationalJointConferenceon ArtificalIntelligence(IJCAI-O1),Aug4-10,Seattle,USA,2001．

[15］Ｊ・Krarup,Ｐ.Ｍ・Pruzan,``Computeraidedlayoutdesign,'，MathematicalProgrammingStudyWo1.9,ｐｐ､75-94,1978．

[16］ＳＬｉｎａｎｄＢ.Ｗ・Kernighan,``AnefTectiveheuristicalgorithmfbrthetravelingsale8manproblem,，，OperationsRe‐

search，vol､21,ｐｐ､498-516,1973．

[17］Ｒ、､McBride,Ｊ､S､YOrmark,``Animplicitenumerationalgorithmfbrquadraticintegerprogramming,''Management

Science，vol,26,ｎｏ､３，ｐｐ､282-296,1980．

[18］Ｐ､MerzandBHei81eben,``Greedyandlocalsearchheuristicsfbrunconstrainedbinaryquadraticprogramming,'’

１bchnicalReportNo､99-01,Infbrmtik-Berichte,1999.(toappearinJourMQfHemstic8）

[19］ＰＭ､Pardalos,Ｇ・P､Rodgem,``Abranchandboundalgorithmfbrthemaximumcliqueproblem,'，Compute頭and

OperationsResearch,vol､１９，ｎｏ､５，ｐｐ､363-375,1992．

[20］Ｐ,MPardalos,Ｊ・Xue,``Themaximumcliqueproblem,，，JournalofG1obalOptimization,vol,4,ｐｐ､301-328,1994．

[21］AmPhillips,JBRosen,``Ａｑｕａdraticassignmentfbrmulationofthemolecularconfbrmationproblem,，，Journalof

GlobalOptimization,voL4，ｐｐ､229-241,1994.

(9)

探索傾向に蕊づいた知識の導入によるＡ-(Ｗ局所探索法の研究 ^1３５

AD-OptLocalSearchbyIntroductionofKnowledgebasedonSearchTendeｎｃｙ

ＫｅｉｋｏＫＯＨＭＯＴＯ，ＫｅｎｇｏＫＡＴＡＹＡＭＡ＊＆HiroyukiNARIHISA＊

ＧＭｗＬｔｅＳｃｈｏｏｌｑｆ肋9mee伽９

切epmme汎tqfIｳq/b7wMLtioM/Comp伽erEn9i凡eerm9 FtBcu胸ｑ/En9mee7m9

okQgqmQUniue78伽qfScle〃ce RjdqichoLZ，○んｑｙＧｍＧ７ＤＯ-0005,Ｊ〃α78

（ReceivedNovemberl,2001）

Inrecentye麺s,themetaheuristicswhicharealgorithm,suchasGeneticA1gorithm(GA),Simulated Annealing,nbuSearch,ａｎｄｓｏｏｎ,hasbeenproposedasaneflicientmethodfbroptimizationproblem・

Themetaheuristicscancalculatenear-optimalsolutionsofhigh-qualityinashortsearchtimerelatively bycombiningLocalSeaJ｢ｃｈ(LS)withisthebasicmethod,andtheideawhichexi8tsinthenatural worldAsthisexample，althoughGLSwhichincludedLSinGAismentioned，LSaccountsfbrmany ofsearchtimeexpendedbyGLSinmanycases・Therefbre,maintainingtheperfbrmanceofLSusedby themetaheuristics，theproposalofthemethodtoenabletheefliciencyenhancementofsearcｈｔimeis expected

lnthispaper，ｗｅｆｂｃｕｓｏｎｔｈｅｍｏｓｔｐｏｗｅｒｆＵｌｔｈｅＡ‐叩tlocalsearchheuristicinLSknownfbrthe binaryquadraticprogrammingproblem・Thek-Optlocalsearchheuristiｃｉｓｋｎｏｗｎｔｈａｔｉｔｃａｎｒｅｄｕｃｅｓｅａｒｃｈｔｉｍｅｔｏｓｏｍｅｅｘｔｅｎｔ，However,theintroductionofsuHicientknowledgefbrtheA-0ptlocalsearch heuristicisnotstudied，WeproposetheefliciencyenhancementtechniquetoreduceaUthemoresearch timebyintroducingtheknowledgebasedonthesearchtendencybyanalysisoftheneaJFsolutionsearch ofthek-optlocalsearchheuristic、IncomparisonwiththeexistenttheeHiciencyenhancementtechnique，

ourproposalmethodshowsthatsearｃｈｔｉｍｅｃａｎｂｅｍｏｒｅｒｅｄｕｃｅｄ，maintajninganequivalentsearch perfbrmance．