TabuSearch _を用いた無閉路有向グラフ系列分割問題の近似解法

TabuSearc h ̲ を用 いた

無 閉路有 向グラフ系列分割問題の近似解法

加 地 太 一

1 .はじめに

先行順位のある要素をその先行順位を保持 したまま,い くつかのステ‑ショ ンに配置する問題を考え る｡ このとき,配置に対するある制約条件の もとで, この配置にともなって決定 される最良な評価値を求めるものとす る｡ この種の 問題 としては,先行順位の制限を無視せずに,要素作業を作業ステーションの 数が最小になるように作業ステーションに割 り当てるライ ン ･バ ランシンダの 問題などがある 1) ,6) ｡さらに,制約条件, コス ト関数を変え ることによって, 各種の問題 に適応できる｡

今回は特に次のような問題を取 り上 げい くつかの検討を試みる ｡ プロセスと考 え られる要素がある資源量を要求 し, 1 つのステーションにおいて使用できる 資源量が定まっている場合,ステーション問のプロセスの移動において,ある コス ト量がかかるものとす る｡ただ し,同一のステーション間での移動 におい てはコス トが無視できるもの とする｡ このとき,各プロセスをステーションに コス トの総和が最小になるよう先行順位の制限を無視せずに配置す る｡ この問 題はライン ･バランシンダ問題のコス ト関数を変えた問題で もある｡また,応 用例 としては前後関係のある一般化 したデータのパイプライ ンの問題 などが考 え られる｡たとえば,メモ リと 2 次記憶間のプロセスの移動 コス トを辺 コス ト とし,ディスク時間を最小化す る問題,およびパー トにおける年次計画などで の利用が計 られる｡

これ らの問題 は基本的に無閉路有向グラフの頂点を先行順位の関係を無視せ

〔 1 2 5 〕

126 _{商 学 討 究 第} 4 6 巻 第 1 号

ずに分割す る問題 として表す ことが可能であり, この無閉路有向グラフの系列 分割問題 に置 き換え,本問題 を考察す る｡前回 8 ),無閉路有向グラフの系列 分割問題 に対 しては探索空間を宿約 し動的計画法を用いた算法 により, m 並 列に近 い構造を持っ頂点数 nのグラフに対 して計算量 0( n m) で求め られるこ とを示 した｡ しか し, この算法ではランダムなグラフに対 しては指数的オー ダーの計算時間を必要 とし,実質的な時間内では計算が不可能である｡ した が って,我 々は本問題に対 し効果的な時間内で計算可能な近似解法の適用を試 みる｡その近似解法 として昨今,種々の問題で優れた成果を示 している Tabu Searc h 3) ,4) I5) I l o ⁾ ･ ^{1 1 ) ･ 1 2 )} を採用す ることとす る ｡TabuSear c h は Fre dGl ov e r によって提案 された局所探索法の変形である｡その大まかな戦略は探索過程で 以前に探索 した解に再び戻 る解のサイクリングをタブー リス トを設けることに よって禁止する処置をとることである｡

本稿ではまず,無閉路有向グラフの系列分割問題についての諸定義を定め, TabuSe arc h の戦略について述べる ｡ さらに本間題を TabuSe arc h へ適用 す る場合の近傍等の基本的考えを示す｡次に具体的な算法の実現 と工夫点につ いて論ず る｡最後に特性評価および挙動解析を行 うための数値実験の結果 とそ の考察 について明 らかにす る ^｡

2. 諸定義

単一の入 口と出口を持つ無閉路有向グラフ D( V, E) が与え られたとき, D

の有向辺が定めるⅤ上の順序関係の反射的かっ推移的な閉包をとって得 られる 順序関係を̲ <とす る｡関係ゴはDが無閉路であることか ら反対称性をみた し, 半順序関係 となる｡ このよ うに して, D か ら導かれ る半順序集合を ( V , ±) で表す｡

定義 1. 空でない部分集合 A⊂V か ら誘導 された D の部分 グラフを △( A) で 表す｡ △( A) の任意の 2 点を結ぶ D 内の有向路がすべて △( A) の有向路 とな

るとき, A( A) は系列を保持するDの部分 グラフであるという ^｡

Tabu search を用 いた無閉路有 向 グラフ系列分割問題 の近似解法 127 定義 2. V の部分集合 A が, AcxA か ら選んだ 2 元対 ( x, y) に関 して ,x

と y が当において比較可能な らば常に x く 抄が成立するとき , ( Ac , A) をAによっ て定まる V の辺堕 とい う ^｡ そ して, A をこの切断の土壁, A c を王堕 とい ^{う ｡}

2 つの切断 ( Ac , A) , ( Bc , B) に対 して A⊇B が成立す るとき, ( Ac , A) は ( Bc , B) の前 にあるといい, ( Ac , A)i‑( Bc , B) で表す｡ また真 に前 にあ ることを記号 ( Ac , A) ‑ < ≠( B c , B) で示す｡

定義 3. V の互いに素な部分集合 X と Y がそれぞれ V のある切断の下組 と上組 に含 まれ るな らば, X とYは切断によ り生壁 されるといい,X F Y で表す. X

と Y についてXI Y またはYI Xが成 り立っ とき,X と Y は分離可能であるとい

う ｡

X I Yは定性的には " Xが Yよ り前にある' 'ことを,またX とYを結ぶ辺が存 在するときには " それ らの辺はすべて同 じ向きを もつ" ことを表 している｡

ここで,無閉路有向グラフの系列分割を次の様に定義す る｡

定義 4. D( V, E) の頂点集合 V の分割が ^Y l l V ² 1 ･･ ･l V ^k を満たすよ うに 順序づけられるとき, この分割を D( V, E) の系列分割 という ^.

このとき,各分割成分 Vi は系列保存の性質を もっ ^｡ 図 1 は無閉路有向グラフ の系列分割の∵例である｡

本問題で考えるネ ッ トワークは,多重辺を もたない単一の入 口と出口を持っ n個の頂点か らなる無閉路有向 グラフ D( V, E) と して与え られてお り, D

( V, E) のすべての頂点 U∈V には重み ^{W (U)} が,各有向辺 ( a ,U) ∈E に

はコス ト C( a ,U) が付与 されている｡ これ らの値 はすべての u, U∈V につ

いて,条件 0< W (U) ≦B ,C( a ,U) ≧ 0を満たす整数であり, B はブロック

サイズと呼ばれる問題に固有な正の整数である｡ このとき無閉路有向グラフの

系列分割 において,I Vi l ‑ L r ∑ E T 7 . W (V) ≦B の もとで,切断され る辺のコス トの

総和を最小にす る分割を求める｡

図 1 無閉路有向グラフの系列分割

3.TabuSear ch の基本的構造

TabuSearc h は人間の記憶の構造を利用 した解への探索方法であり,解の サイクリングを避けるためにタブー リス トという記憶域を設け,一部の探索を 禁止す る処置をとる｡ すなわち , TabuSearc h は最近の ^S 個の探索解をタブー リス トに記憶 しておき,それ らを候補か ら除 く,あるいは最近の ^S 個の探索解 で生 じた変数 x i の変化方向をタブー リス トに記憶 し, これ らの変数の逆方向 への変化を禁止す る処置を とる｡ ここで,タブー リス トを aとすると, Tabu Sear c h では現在の解 x n o wの近傍集合 N( K no w) か ら α を除 き,その中か ら最 小 コス トとなる解 x next を選択す る.また近傍集合か らaを除いた新たな集合 を N( a ,x no w) とす る｡すなわち, N( α ,x no w) ‑ ( N( x no w) ‑α) となる｡そ の移動を行 う関数を以下に示す｡

( x d ̲ nex t . . t ;

m ove( x no w )‑ i f cos t( x next) ≦cos t( x)for al l x∈N( α ,x no w ) し ￠ ,i f N( a ,x no w )‑ ￠

また α の長 さを 1 e ngt h とし,以下の算法構成で基本的な TabuSe ar c h を記

述す る 1 0 ) I l l ) ,1 2 ) ｡

Ta bus e ar c h を用いた無閉路有向 グラフ系列分割問題の近似解法 129

1: t : ‑0;

2: ∬o:‑ i ni t i als ol ut i on;

3 : α : ‑ ￠ ;

4: l e ngt h: ‑apos i t i v ei nt eger;

5: whi l es t oppl ng‑C r i t e r i on <>ye sdobe gl n 6: x t .1 : ‑move ( x t );

7 : a.:‑ α Ux ,‑ x t̲Zcngth

8･ . t:‑ i +i;

9: e nd;

TabuSe ar c h は非常に柔軟性の高い枠組みであ り,上の算法にさ らにい くっ かの戦略を付加 して構成す る｡

4. 近傍 とタブーの基本的考え

TabuSe ar c h の算法を構成す るにあたって重要な要素はその問題 における 解の近傍 とタブーの要素の構成である｡以下にその基本的な考えを述べる｡

無閉路有向グラフ D( V , E) の系列分割を ( Vl ,V ² , ･･･ , V ^k) とす る｡

Vi によって誘導 された D( V, E) の部分 グラフを △( V ′)とす る ^｡ この とき, A(Ⅴ′) の有向辺が定める Ⅴ ′の関係 において,極大元および極小元 となる頂 点 U∈V ′は系列分割の性質を変えることな く,他のあるブロック V J に移動で きる ｡ Uが極大元のときは D( V , E) での U か らの流出辺が V t ･ .1, ‑ ･, V ^卜 1 内の頂点に流入す ることがなければ , Uは V ^j S こ移動可能である｡同様 に,

U が極小元のときは流入辺が V ^,̲i, ･･･, ^{V t̲1} 内の頂点か ら流出 しなけれ ば V ^j に移動可能 となるO この U の Vi か ら V ^j への移動を e ( U ; i , j) で表わすO また, ^Ⅴ ブ の直前あるいは直後 に新 しい空 ブロックを作 り,前記 と同様な条件 が満たされれば,そこに U を移動 して系列を拡大するができる｡ この U の空ブ

ロックへの移動を a( U; i , j) で表す｡ さ らに, e ( U; i , j) , a( U; i , j) によ る頂点の移動 によって Vi が空 にな った ときには, この Vi を取 り除いて系列

/ / ー＼

1 30 _{商 学 討 究 第 46 巻 第 1号} を縮小することもできる｡

与え られた系列分割 く V l, V 2 , ･･ ･, V ^h) に移動 e( U 昌 , j ) または, a( U; i , j) を行 うことによって, 新 しい系列分割が得 られ る｡このように して, 得 られた系列分割の集合が系列分割 く V ^l, V ² , ‑ ･, V ^h) の近傍である｡

この移動 による系列分割の生成にあたって,移動によって空 となったブロック は系列か ら取 り外す約束 に してお く｡

次に,タブーの要素 としては解その ものとはせず,通常,解の移動に関係す る頂点および辺などを属性 として,これをタブーの要素 とす る｡ 本問題の場合, 頂点の移動 による近傍が構成 されるので,その移動 した頂点を属性 と考える｡

ここで , Vi i V メ である V t ･ の任意の頂点が V , に移動 したとき,その頂点をタブー リス ト t abu‑ t o‑ 1 e f tに格納す る ｡t abu‑ t o‑ 1 e f tに格納 されている属性である 頂点は V ^j か らVi への移動が禁止 されることとなる｡同様な形式で,Vj の任意 の頂点が V z ･ ‑移動 した とき,その頂点をタブー リス ト t abu‑ t o‑ r i ght に保存

し, V ‑ か ら V ^j の移動を禁断する ｡

5.TabuSe ar c h への実現

本問題において無閉路有向グラフそのものをあっか う場合,分割の表現など に複雑なデータ構造を必要 とす る｡また基本構成に述べるような解の近傍構造 を実現す るためには複雑な処理が要求 される｡それゆえに,算法の構成,計算 の負担に著 しい影響を及ぼす｡ これに対 して我々は無閉路有向グラフを一列化 したグラフに変換 し,その上で分割を考え,さらに基本構成の近傍を効果的な 処理方法で実現す る｡

5. 1 無閉路有向グラフと一列化 グラフ

無閉路有向グラフはいっで も一列化 (トポロジカル ソー ト) が可能であるが,

結果 は一意でな く複数の一列化が可能である＼ ｡本問題 はこの一列化 グラフとの

関係 において以下の特徴的な性質がある ^｡

Tabus ear c h を用いた無閉路有向 グラフ系列分割問題の近似解法 131 定理. 無閉路有向グラフDの任意の系列分割はDのある一列化 グラフの順序 を保持 した分割 ( 一列化 グラフの系列分割)を指定す ることによって定まる ^｡

証明 : Dの系列分割は正規表現の もとでVI J V 2 1･‑ 1 V h をみたす｡各 Vi によって誘導 される V の部分 グラフを一列化 グラフ D i に書 き直 し, D i を添字 の順に左か ら右 に一列に並べ,それ らをカッ トセ ッ トに属す る辺で結びつける

と, D の一列化 グラフが得 られる. ここで, この一列化による頂点の番号付け と,各 D 7 の最左端の頂点番号か らな る単調増加部分列か ら一列化の系列分割 を作れば, これは与え られた無閉路有向グラフの系列分割 と一致す る｡

以上か ら本問題においては無閉路有向グラフを一列化 グラフに変換す るOそ の一列化 グラフ上での分割を考えることによって,データの処理を容易に行 う ことが可能 となる｡ここで, 一列化 されたある頂点列を f ul, U2, ･‑ , Uni

とす る｡この とき, 任意の頂点 ^U ♪ ^{, i )q ;} ( p < q) をブ レイク ･ポイ ン ト ²⁾ b i,

b jとす ることによって部分集合 Vi‑[ b ^t, b , ) ‑ ( U ♪ , U ♪ .1, ･･･ , U q ̲1)

を決定でき,ブ レイク ･ポイン トの集合 i bl , b 2 , ･･･,b hi によって一 意的に系列分割 く Vl , V 2 , ‑ ･, V hi が表現で きる｡ したが って,無閉 路有向グラフの先行順位を無視 しない頂点列 とブ レイク ･ポイ ン トの集合 の データを管理す ることによって容易に解の表現が可能 となり, これを利用 して 効果的な TabuSearc hを構成す る｡

5.2 近傍移動の実現

本問題では部分集合の個数,任意の部分集合の要素数 は不定である｡ これが 近傍の構造を複癖にしている｡ これに対 して一列化 グラフの頂点列 とブレイク

･ポイ ン トの集合 によるデータ表現の観点か ら,効果的な近傍移動を実現す る｡ このとき, 4 章の基本的考えで述べた近傍に若干の制限を加える｡

基本構成の近傍e( U; i , j ) , a( U: i , j)を実現す るためには,部分集合間の頂

点の移動,あるいはブレイク ･ポイ ン トの移動,およびブレイク ･ポイ ン トの

1 32 _{商 学 討 究 第 46 巻 第 1 号}

付加,削除などによって構成 され る｡本問題を構成するにあたっては上記の頂 点の移動 とブ レイク ･ポイ ン トの処理の 2 つの操作を分 け,複合す ることに

よって次の解ぺの移動を決定す る｡

まず,頂点の移動は基本的には 2 つの部分集合間の左,右移動 によって構成 す る｡ただ し,最適解の近似を強めるために複数の部分集合間での移動を実現 す る｡直接前後す る 2 つの分割集合 V z ･ ‑ ^{[ b m} , b m. 1 ) , V , ･ ‑ ^{[ b m .} 1 ,b m .2)

に対 してVi の移動可能な頂点の うちコス ト変化量が最小 となる頂点をV ^j へ移 動する｡ このときタブー リス ト上に含まれている頂点は移動を禁止する｡ この

>

処理を関数 N ( V,V･ ,t abu‑ to ‑ r i ght) とす る｡ただ し移動可能な頂点がなけ れば,V" V ^j はそのままとす る｡また,V ^j の移動可能な頂点をVi へ移動す

B =

る同様な処理を関数 N ( V,V ,t abu‑ t o‑ l e ft ) とする｡

‑ ･ +

近似を強め るために, N( V,V ,t abz L ‑ t O‑ r i ght )の処理をすべての部分集合 に順次適合 した以下の処理

→ 一 ‑ ‑ >

N( V l ,V 2 , t abu‑ t o‑ r i ght ),N ( V 2 ,V 3 , t abu‑ t o‑ r i ght) ,

‑ ‑ ‑ ‑ ‑ ‑ チ

‑,N ( V k ̲ 1 , V k ,t abu‑ t o‑ r i ght ) を多次元 1 e f ト ー O‑r i ght 移動 と呼び,

‑ ‑ ‑ ‑ ‑ 〜

関数 mu l t i N( V l ,V 2 , ･ ･ ･ , V k ,t a b u ‑ t o‑ r i ght )で表す ^. 同様な

【 ≒ =

N ( V,V it abu‑ t o‑ l e ft ) の順次適合 した以下の処理

≡ = ⊂ ≡ ≡ =

N( V k ,Vk ‑ 1 ,t abu‑ t o‑ l e ft ) , N ( Vk ‑ 1 , Vh ‑ 2 ,t abu‑ t o‑ l e ft ) , ー

‑,N ( V2 , Vl ,t abL L ‑ t O‑ l e ft ) を多次元 r i ght ‑ t o‑ 1 e f t移動 と呼び,関数

< ‑

T nu l t i N(V l ,V 2 ,･ ･ ･ , Vk ,t abu‑ t o‑ l e f t )で表す｡

/また,多次元 l e f t ‑ t o‑ r i ght 移動,多次元 r i ght ‑ t o‑ 1 e f t 移動だけでは部分集 合の個数,大 きさの大 きな変化は望めない｡ したが ってさらに近似を強めるた めにブレイク ･ポイ ン トの移動を試みる｡ある一列化 グラフに対 してブレイク

･ポイ ン トの単調増加列 i b l , b 2 ,‑ , b k) を決定す ることによって部分集合

( vl ,V 2 ,･ ･ ･ ,V ^k) である解 x が示 ざれ る. この とき,ブ レイク ･ポイ ン ト

を移動および付加,削除などによって得 られる ( b' 1 , b ' 2 ,‑ , b ' h ′ )で決定 され

Tabus e ar c h を用 いた無閉路有 向 グラフ系列分割 問題 の近似解法 1 33

る部分集合 V ' 1 ,V ' 2 ,‑ ,V ' h ′ である近傍解の集合を Aと定義 し, これによって 部分集合の大 きさ,個数が変化する｡またその変化にともなって頂点の部分集 合問の移動 も行われる｡ただ し ,x∈ Aで もあるとす る｡ この とき, Aの中で

‑ ･ ･ ･ > ･ ‑ ‑ づ ゝ

最 も低いコス トを示す解∬′‑の移行を 人と定義す る｡ここで , A を求めること は Ke r ni g h an の一列化 グラフの最適系列分割問題 を解 く算法 2) ･9) と等 しく 0 ( a) で構築できる.

以上,頂点列の並び,およびブレイク ･ポイン トの位置に観点をおき, 3 つ の近傍移動 の処理 に分割 し構成 した｡ この処理を‑反復過程 中において,

‑ ‑ → t ･ ･ ･ ･ ･ ･ ‑ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ‑

T nul t i N( Vl ,V2 , ･ ･ ･ , Vh ,t abu‑ t o‑ r i ght ) ,T nul t i N( Vl ,V2 ,‑ , V k ,t abu‑ t o‑ l e ft) と順次行い,再び合成す ることによって,容易な処理で効果的な近似効果を持 つ近傍移動を作成する ^｡

5.3 タブー リス トの実現

解移動 (x ,x′ ) に対 しての逆向きの移動の禁止の属性 として , (x ,x' ) の とき移動す る頂点をあてることとし,多次元的 l e f t ‑ t o‑ r i ght 移動 と多次元的 r i ght 一 七 0‑ 1 e f t 移動 の 2 つの移動形式 に対 して 2 つの タブー リス ト Tabu‑ t o‑

1 e f tと Tabu‑ t o‑ r i g h t を設 けたO タブー リス トは待 ち行列構造 によって構成

されるが,プログラム上では頂点集合に対応す る一次元配列を用意 し,配列の

添え字 は頂点に対応するもの とす る｡ このとき,初期化の段階で配列のすべて

の要素を 0 に しておき,移動対象 となる頂点の要素にある正の数を入れ,反復

毎に 1 以上の要素の値に対 して 1 減ずることによって, 1 以上の頂点を禁断対

象 とす る｡ある正の数 としては Vi か ら Vi .1 ( Vi .1 か ら Vl )へ,頂点 V を移

動 したときのコス トの変化量が負および正の 2 つの場合に対 して異なる値を用

意す る｡すなわち,変化量が改善 されたな らば TabuLe ngt h lの値,そ うで

ないのな らば TabuLengt h2 の値を与え る｡ これ らの値の適正値 は事前の数

値実験により判定する｡

1 34 _{商 学 討 究 第} 4 6 巻 第 1 号

5. 4 コス ト計算 )

N O7 1 ･ , V 十1 ,t abu‑ t oli ght ) の処理 の過程で計算す る頂点 U ∈Vi の Vi か ら

→

V H l への移動 に伴 うコス ト変化量 6( U ,Vi ,Vi .1 ), および

⊂ ≡ 王 =

N (Vi,V 7 ‑ 1 ,t abu‑ t o‑ l e ft) における頂点 U ∈V 昌こ関す る同様なコス トの変 ー

化量 6( U ,V i ,V ^{. ･} ̲1 ) は以下の計算式を用いることによって高速に計算するこ とが可能である ^｡

‑ ･ ･ ･ 事

6( U ,Vi ,V 2 .1 ) ‑ _S∈T ^{∑ C(} _{r ,} ^{S, U)‑} _t∈V. ^∑ _{. 1} ^{C( U ,i )}

⊂ ≡ =

6( U ,Vi ,Vi ̲1 )‑ ∑ C( t ∈V . U, i ) ‑ S ∑ C ∈ V H ( S, U)

5. ‑5 終了判定基準

終了判定基準 としては,ある反復回数を繰 り返す方法,または局所解が更新 された段階か ら, この値が更新 されな くなってか らの経過時間がパラメーター St op を越えたときに,算法が終了す る方法などが考え られる｡今回のタブー

リス トでは後者を採用 しパラメータは2000か ら3000 反復前後 とする｡

5. 6 近似度の改善

現在の段階で求 まった近似解に対 して,本問題の特徴 により,以下の方法を 用いさらに近似度を改善す ることが可能である ^｡

5. 6. 1 局所最適解か らの再出発

本問題で得 られる局所最適解の頂点列 と最適解の頂点列の構造は部分的な配

置が異なるのみで,解の構造 としては近い関係にある｡すなわち,分割された

部分集合の部分的一致が見 られる｡ この性質より,以前に探索 した良好な解の

情報を積極的に使 うことによ り, さ らに良好な解を探索す る戦略が考え られ

る｡ この考えを取 り入れ,現在得 られた局所最適解を初期解 とおき,タブー リ

ス トをすべて空 として再び探索を進めることは有効な結果を もた らす可能性が

強い｡

Tabus e a r c h を用いた無 閉路有 向 グラフ系列分割 問題 の近似解法 135 5 . 6. 2 2 頂点交換法

解 x を表す一列化 グラフ上の任意の隣接す る 2 頂点 ui, U , に対 して , u lと ^{U , .} の間の切断を考慮 したとき得 られるコス トを C とす るO この とき,頂点 ui と ^{U ,} が交換可能であり, しかも交換 された場合のコス ト C ′ が C ′ < Cとなる場合 , V. ･

とuj の交換を行 う ^｡ この操作をすべての交換可能な 2 頂点に対 して行 うことに よって,コス トが改善 される可能性を含む新たな一列化 グラフが生成 される ^｡ この一列化 グラフに対 して,前記の一列化 グラフの最適系列分割門題の解法に より最適なブ レイク ･ポイ ン トの位置を求め,解x′を生成す る｡ このx′のコ ス トが改善 されているな らば,￡′を近似解 ∬とし,以上の処理を改善 され る 問繰 り返す｡ この方法を 2 頂点交換法 と呼ぶ｡

6. 数値実験

本章では上記で構成 した TabuSe ar c h の算法に対 しての特性評価および挙 動解析を行 う｡まず ,TabuSearc h を効果的に動作 させ るために,最 も重要 なパラメータは禁止 リス トの長 さである｡ このパラメータの値 は事前の数値実 験か ら考察す ることとな る｡本問題 において は ･ 2つの禁止 リス ト Tabu‑ t ol 1 e f tおよび Tabu‑ t o‑ r i ght を設 けているが禁止 リス トの長 さのパ ラメータは 両禁止 リス トとも共通 とする｡ただ し,任意の頂点の移動に関与するコス ト変 化量が改善 された場合 TabuLe ngt h1 ,そうでない場合 TabuLe ngt h2 と 2 つのパ ラメータを準備する｡最初に Tabul J e ngt h lの適正値 について考える｡

TabuLengt h2 の値を 0 に固定 し,値の変化 に対 しての コス トの値の変化を 数値実験で確かめ考察す る｡図 2 , 3 , 4 は頂点数5 00 のラ ンダムグラフに対 しての数値実験の一例であり,それぞれブロックサイズが1 0 ,30 ,50 の場合を 扱 う｡ この実験より,ブロックサイズ1 0 の場合, 2 前後が適正であり,ブロッ

クサイズ30 の場合, 7 か ら 1 4 であり,ブロックサイズ50 の場合,1 4 前後 となっ

た｡ TabuLe ngt h lの適正値 はこの結果 よ りブロックサイズの大 きさに影響

されると考え られる｡すなわち,ブロックサイズの 1/ 5 か ら 1/ 3 の大 きさ

1 3 6 卦 亜 叫 ヰ 鍾 湖 4 6曲 事 ) 亜

7 1□ ty P ヰ If 沌 ‑ Lo

T a b u L e n g th 2 ‑ 0

コス ト

= : : : : 叢 :: = : : : ; : : : : : :: : : : : . } ; : : : : . 譲 妻 … ▲ ◆ ー ■ ● ‑

‑‑ 一 . ‑ .‑義:

: : ; 謙 ; 育

謙 … 三 三 ;

◆

…鮭 き= . i

鰭

fi

朋 剛 勇

T a b u L e n g t h ‑

図 2 淋 1t rJ R T a ) 御 伽 rL C か u R T a ) 滑 蒜

7 t□ ty 9 4 4 沌 = 30

T a b u L e n g t h 2 ‑ 0

コス ト

I . . . , . 〜

: : ̲ : . #

● ■ 一 ● ● ■ 一

L . I . L l 4 . ‑ ▼ ■ ● ▼ ■ ■ ● ー . 捷● ' ^蒸 ● ノ ー ^{‑ . . √ . . ‑ . . . ■ ● . . , / P ● .}

: : . .; : : . = : 鷲

# . : . : , : . : ‑ : . : . : . : ‑ : ‑ : . :: . : : : : : . : . : ‑ : . . ' . : . : . :

: . ‑ ‑ ‑. . . こ 暮. : . : . : . : . : . : . : 一. : 一 : . : ‑ : ‑ : . : ‑ : I . ‑ : . : .

H X 和 讃 T a b u L e n gt h l

図 3 淑 iL rJ R T a) 御 伽 F C cE か u R T 8 神 話

Tabus e ar c h を用いた無閉路有向 グラフ系列分割問題の近似解法 1 37

ブロックサイズ ‑50 TabuLe ngt h2‑0

0 0 0 0 2 0 5 5 1 1 エY E=

● ● ■ ■ ● ● ■ ■ ■ ● ● ◆ ● 一 ●

■ ■ ■ ● ● ◆ ● ■ ■ ■ ● ■ ■ ● ● ■ ●

: I l : t 4 : l ' . : I 4 . + ' : I 4 J ‑ . : L I . ･ ■ ' : ■ : ; 一 l ; 柿; : ● : : ● l : ■ + : ■ ; : ● : : ● l : ● : : ■ I ち ● . : : ● . ; ● : ; 一 I ; l ● ■ J ● ● ‑ + I ● : ● ■ ■ .: ● : ● ● ● 一 l ■ I ● ● ● ● L ● ←一 ■ 一 一 : ◆ ヽ ● . ● 一 ㌧ :● ● ● ● ● ● 一 一 ● r : 一 ● 一 一 一 ● ■ ■ ′ ● ● ■ ■ ● ● ■ L l ■ 一 ㌧ 4 ■ ● ■ 一 ‑ ' ■ ● ■ I 1 ■ l J I J t ‑ +

書 桔 : : : :f ● ▼ I 一 ■ r ● t ● l ◆ ■ ー ■ ■: : ● ■■ : : : I ■ ■ : ‑ , ● ● ■ : . ■ ●■ ㌔ : ● : ● ● : ● ● ● ■ ■ ■ ■ ● ■ ､ ● ◆ ● ● ● + I J + . l + l ‑ t f 4 : f J . , J I I :

I r ‑ I . f J r L ■ : . モ >■ ･ ● : ● ● ● ■ I 一 一 ■ . ▼ ● 一 ● ■ > : ■ ● ● : ● . ■ : ● 一 : : : ' ● : ● ● 一 ● ■ : ● ■ ■ ■ ●: ● i ● : ● / 一 ■ . + r #: I : : .

● ■

● ■ ● ●

■ ■ ■ ■ J ● ● ■ 一 ■ ■ L ● ◆ ● ■ ■ I ● I ■ ● 一 至 … ; … 圭 : : : : . . : . : I : : r t J ● I ● ● r I ■ J : I : ･ I ' . : : : . : . : ' 〜 ; : :i : : :; : :: : : . :･ : . : . : . ■ 葺 ● き ■ 壬 : ● ● : I ■ ‑ : ‑ ● i I 一 I : t 一 : I I ■

● ■ : ● ● : ● . ●

■ 一 ◆ ･ : ■ : I : ･ : : . * : . ● t ● . : . : . ン ● ■ ● ■ ● ● ◆■ ● ●: ● 1 ‑ : . I◆ ー: . . . ● . ● . ● : ● : ' :● ● ● : , ■ ◆ ‑ I l . P . . . ̲ ‑ , . ‑ .

■ ● ■ ▼ ■ ■ ● ●

● 一 ■ 一 ●

● ◆ ● 一 ● ● ● 一

B I t l ● ヽ ■ ヽ ● ^{継: . : : . : i . .■ 一 t : ■ . t : 一 ● 一 : ､ ● ● ; ; ､至 : 澗 . : : : . : : . . :■ : ■ ー ; ● ■ ■ ■ : ● ; ● + A ● I ● L ‑ ● ‑ ● l + ヽ ■ d . ■ l ● . l t ● l l ● ■ ▼ J ヽ l 1 : ◆ ; ･ ‑ : : ′ ; . ; : 日 ■ ; . : : ; . ; . ▲ : I ■ . I . 一 : I. . : ■ : ; ● ヽ : : ● : ; 一 t : ; 一 ■' J ■ I ● I ■ L ■ l ̀ . ● l ･ ● t . : ､ ､ . . : : ● ■ . . 一 ■● ●■ l ' : r J : . J ● : : + ● : . I ● : . I ● ■ . : : . . : ‑ ■ ; : ● ● . : 一 : ● ● . : ● I ‑ ‑ ● .}

0 20 4 0 60 80 10 0 TabuLe ng t h1

図 4 禁止 リス トの長 さによるコス トの変化

を TabuLe ngt h lの適正値 とす ることが望ま しい｡

次に TabuLe ngt h2 の適正値を考察す る｡図 5 , 6 , 7 , 8 は図 4 で使用 したグラフで,同様 にブロックサイズ 50 に対す る TabuLe ngt h lとコス トの 変化を表す数値実験であ り,それぞれ, TabuLe ngt h2 の値が 4 , 6 , 8 , 10 である｡図 4 に比べ ると明 らかに TabuLe ngt h2 によって大 きなコス トの 改善の効果を得 ることがわかる ^｡ また図 5, 6, 7, 8を比較す ることによっ て, この場合, TabuLengt h2 は 8 前後が適正であ り,その他の実験 も含め て考察す ると TabuLe ngt h lのやや低めの値を適正値 とす ることが望ま しい｡

最後 に 2 並列 グラフに対 して は厳密解 を求 め ることが可能 であ るので,

TabuSe are h との比較を試み,局所解 の近似度 につ いて論 じる｡表 1 はブ

ロックサイズ,エ ッジコス ト,中間エ ッジを変化 させた場合の頂点数 200 の 2

並列 グラフのコス トの比較である｡表 1 よりエ ッジコス トがすべて 1 の場合,

TabuSear c h ー の結果 は最適解 にほとんど近い値か最適解その もの となる｡ し

か し,エ ッジコス トの値が幅広 く変化する場合,近似度 は前記に比べて悪 くな

1 38

エ Y n エY n

1 5400 1 5 200 15000 1 4800 1 4600 1 4400 1 4200 1 4000 1 3800 1 3600

1 5 400 1 5200 1 5000 1 4800 1 4600 1 4400 1 4200 1 4000 1 3800 1 3600

商 学 討 究 第 46 巻 第 1 号

Ta buLe ngt h2‑4 , p ‑50

■ ◆ ■ 一 一 ● ■ ▼ ● ● ● ● ● : 難: , ‑ : , : , : L . ; : ≡ i : . 好 手 ; : ; I ; I ; ; : : ン ン :‑ / J I . . ■ ､ ◆

■ 一 ■ ■ ● ● ■ ･ . 一 :▲ ● ■ ● 一 ● ● ● ■ 一 ● i : : : . : : : : : i : 一 ■ ■ ■ 一 ■ ● 一

● ● ● ■

◆ ● ■ ∴ ■ ● 一 ■

■ ■ ■ ● ■ ● 1 ● ■ 4 ‑ ■ ^l ■ ^{4 . ● ㌔ ● ● ● + ‑ ● ◆ L} 1 ^{ヽ ■ ● ̀ ● ●} ‑ : ^{● ▼} . ^■ : ‑ ^■ l l ^{' ■} l ^{■ 4 ● ‑ ● .} + ^ノ + ^● ‑〜 r . I + . I ‑ ･ I . . + . I + . . 1 . : : . . : : : : . . : : : : : : : ; ; ; : : : ; 言 : : 辞 : : : : : ; ^{: : ; : : : : ; : … : .} A : . _. . _̀ ' _● . i _ー l ■ ■ ◆

■ ●. ‑ I ‑ ‑ I : : : : : : : ‑ ㌧ + , ● I ● 1 ■ ● ● ■

● ▼ 一 . 4 . 1 1 4

. . : . : . . : : 4 : . . f J l J . l 一 ● I ◆ ■ ■ 一 ▼ 一 ● ▼ 一 ■ ● 一 一 一 ● ‑ . ̀ . ● . ● : ◆ : ̀ : ̀ : ■ : ∫ : : : : : : : : : : : : . : ∫ : ● : ‑

0 20 40 60 80 1 00

Ta buLe ngt h1

図 5 禁止 リス トの長 さによるコス トの変化

TabuLe ngt h2‑6 , p‑ 50

.J.I‑ 1 l ^{I J}

●●● 一

°◆■●●. ● ● '■●●●●● ･ ....: ●■一

● ● : ■ ■ ▼ . ■ ● ◆ ●● ●●一

'

● ^●■● ‑ ■ ■ ● ● ^{▼■●●● ■} '.:. ●●◆● ^●■● ■ ■ I+ . . . I . . J . . : I . I J : : 1 . ' L ' : : l ' 1 ' I : ■ . . . : ■ ; , : 一 : ■ t ^{. ■ r . . + ■ I . 一 ● l ■ ■ 掴S ' g E 瑚 ● ● ■ ■ : .}

l Jr

一 ● ● ■ 一 ㌧‑ ■

● 一 ㌧

‑ ■ ● ■ ●一 一 ^{●■●● ●} ● ^{● ● ◆ ● ● ■ ● ● ･ T J .} ･ . . ヽ ● . ● . 一 : . : : : : : : : : : : : I : ^. : ^.:IllI :.:::.:::::::::::: : . : : :... .: : : : : : : .

. ● ● 一 ● ● ●■一

■ ▼ ●■ ● ● ●●■ 一 ■ ● ● ● ■ ●■■ ■ ■ 一 ● + + 小 : 一 ● ● f

I ^{IIAf I} : : : ^{: :} ; ^: : ^: : : : ^{: : ::::::.:. : ::::::::: : :::::;:::} : : : : : : : : I : I

● I I ^{■ ●} I ^● I ● I ^● t r ^一 l ^■ + ^一■ J

; ; 棋4 4 ■ ‑ ■ t ● r ● J ◆ ● I ● t ; : i : : ! 弓 i i : ; ● ; ● ^:;: : ヽ ; ^{港 . ● + ■ ■} : ; T ; ; ; ; T : ^{:r : . 小 . : 1 . ‑ : : :.:1 ●■■ ･:.: I+f ● + : ■ . 4 ■ I 1 . ;:; 弓 辞 ;::港 : : : : : : ;i:. : : : i : . ' :}

一●■●●●■ ◆ ･ : . : : . : : ; : : i ^: ; ^{: :} ｡ ^:I ■ ^{. ● . ■ : ● ● ■●■ 一 ● : : ; i} : , : ^{: 如 き ; 焉 瑚 結 き ;} : : ^{:;:::;I ;:::沖 ::;}

^{; : ; 令}

i :串 ^{ー IBJIIII+I} 一 ^● ､ 一 ^{■ ‑ ● ● ■ ■ ■ ●● ●● ; ; ;} ● .I ^.JfJ + ^{1 4 ; : ; ; ; : ● ､ ● I l ′ ■一一 r lL r ' I ■ A ● Ill + ● ■ 4 ■ 1 ● ●●■ IJI ●■ 一 ▲ L ▼ ● I :; : ; ::相} 川: 〜 : ; ; ; ; : : I : : :

● ■ ^{; 草 : : : : ' : : 7 T. : *.} . . 7 T ^{' ; I . I ■▼●● ::.: I;一: 一●● : ■■●▲● :} I ^{:;: . :; : ; ..:.:.●●● ●一● ･ } . . メ : . ● . ●● 1 ●■ I: 一 一 4 .}

^{4 一●●● : : ー ‑}

^{4+ ■ lld ●‑ ■ l r}

0 20 40 60 80 1 00

Ta buLe ngt h1

図 6 禁止 リス トの長 さによるコス トの変化

Tabu s earc h を用 いた無閉路有 向 グラフ系列分割 問題 の近似解法 1 39

Tabul J engt h2‑ 8 , p‑5 0

エY n エ Y L;

1 5 4 00 1 5 20 0 1 5 0 00 1 48 00 1 46 0 0 1 44 0 0 1 4 20 0 1 40 0 0 1 3 8 0 0 1 36 0 0

1 5 40 0 1 5 20 0

1 5 0 0 0 1 4 80 0 1 4 6 0 0 1 4 4 0 0 1 4 20 0 1 40 0 0

1 3 8 00 1 3 6 0 0

: こ ' :

一 一 ■ 一 : ● ■ I ; ･ I ヽヽ : : . . : : . ● ; ● : : ● : : 一 ● ■ ● ● l 1 ‑ + I a: 一 ㌧ 一 ､ ■ ● , 一 . 拙 : . : ' :

: : ; : : I . : : : : : : : :: : : i . 1 : I . : I . : ■ ■ ‑ . : I . : ‑ . : . . : : . : . ' . ■ ■ ▲ ･ : ^{. ●}

I : : : ; i . i : 蔓 享 ; ･ ■ ● : ● . : 一 ▼ I 一 : ● ● ; 寺 ● ● ■ ● ^: : ^{. ' , . : , . . : ･ . T . .}

; . ' i

: 諺 ■ ● ● ^{● ､} : ^{● . ,} ● ● t ^■ 一 . ● ^: ● 一 I 一 ● ● ● ● ■ ■ ^■ ● ^{一 ■} : ^{; ▲ ; ･ : : : : : : . : : . : : ･ . ‑ : ; . : : : . : :}

: 雲 i + . ‑I ‑ 漕 輔 ≡ ‑ ■ ■ ■ ● ● : 耕 . ･ l ● : : I 一 . I l ● ' . : I 一 . ; ● : L

■ ゝ 一 一 ■ ■ 一 ▼ ‑ ● ● ● ● 一 I : . : ･ : ● : . : ･ :. :. . l ‑ I ‑ . ‑

● 一 ■ 一 一 ● . I . I

▼ ■ ● ● I I + J I l ● ■ 一 ■ ●■● ■ 一一

: ? : ?; ー ン: , : . :

l l 一 〜 ､ ‑ + . I ‑ I 蔓 ; ■ ● ▲ ■ 一 I . I: ! ' . ◆ 一 ■ ● ■ ^{一 I . ; : ; : : : ! . , : . . : . , :: : ; ?, ; : : : :: : : : : : ' . ; : ; : : : : : . I : :}

0 ^{20 4 0 6 0 8 0 1 0 0}

T ^a b uL e n g t ^{h 1}

図 7 禁止 リス トの長 さによる コス トの変化

Tat ) uLengt h2‑1 0 , p = 5 0

. I ‑ ‑

… 至 … ● I ◆ : ■ . 昔 : : I . : ; I ● ● ■ ■ ■ + ● ● リ ‑ ■ ■ . . I 一 ● l : : ● ● :: . : 一 : , ■ : ; : ● ● : ● ● I : ● ' : ● ; : ●

≡ : ≡ : ; :

I l . ･ ■ : : 一 : 一 一 ■ 妻 l 妾 ■ J . ● ● I … V. きき董 : 1, : ● ‑ ● ‑ . ' 一 I . 一 , ‑ : ● : . . 拷 : . : : : 一■ ノー ● ･ : ､ 拷: ' : '' . ' . ; : . 焉 . : I ; ' : . ; : ､ : : . : .

a .

I t f ● ニ : ■ ■ ■ : 一 ● I 一 ; ■ :: : ● . 一 ; 辛 : : : : 童 . : ;: ' : : : . : : : i : ; : i : ; : ^: . ^宅 : . ⁱ : ⁱ

I

: : : : 三 . 令 : : : : . :. . 〜. .. . . . : ■ .. ′ I . ● . ^{: I , : ' ' : こ . . :: I . : : : : : : : : : : : :: I . : : : : : I . . . : I . : l . ; : ; : . : . ; I . ‑ I .}

i ● l l i ▲ ■ ●i ● ■ ●

; :i : ; : : ; : ; i : ;; ; : :: ' : ^{4 : : ; : ' /: i : : : ; : : : :}

^{: : 張 : ; : : : : : : : : : ; : ; : : : : . :. : . ;: : : : : : : : : : ' ; ' :}

･ ; : ; ; + ; ^{≧ ■ . : . ; : : : ! . . ; : : :: : : : : ' : i : : I : . : : . : : : . A : : : : : : : : L : ; . I : I : : ' : . : : : . : : : . : : . : : 浩}

^{: ' : : ; . 料 : ; ; : I : : I : : ; : 〜 : : : :}

i : ' ! ･ : 酔 : : ●: ■ ● ■ ■ 1 ■ : : T : : : : : : : : ! : . : , : . : . : . > : . : . : . : . ; . : . . ' . ‑ . . : : : : : I . ‑ : : : . :

: ; : ^: . ' . . : : : : ' :

l Hf I I I ⁴ ●■ ･ : . 寺 : ､ : 一 ● 妻 . ● ● ● : ■ 一 骨 ■ 一 ■ 圭 ■ ･ : ー l I ● , .I ‑ : 一 . . :: . : : A . ･ ■ : : ' : i : : : . : :

: ■ ヾ ● ● ● ≡ + : ◆ ● : e : 一 ■ ; . J : ■ ● : l : I 一 ● : . t : ◆ 日 :

: ≡ I : ● J

一 A

. I I ■■●; J l +J l . I I r ‑ 柿 ー 宜 ● . ■■ ■ 一 一 . ● I

0 ^{20 40 60 80 1 0 0}

TabuLe ngt h1

図 8 禁止 リス トの長 さによる コス トの変化

1 40 商 学 討 究 第 4 6 巻 第 1 号

表 1 2 並列グラフに対する厳密解 と TabuSe ar ch によるコス ト グ ラ フ a b p C d e f g h

エ ッジコス十 1 1 から 1 0

ブロックサイズ 1 0 1 0 4 0 4 0 I O 1 0 4 0 4 0 中間エ ッジ 0 ^{2 0 0 2 0 0 2 0 0 2 0}

･ 厳寧解 . 2 0 4 0 5 1 9 5 1 1 4 6 6 8 7

る傾向がある｡ これはカ ッ トされ る辺の コス ト値が大 きな範囲を持つため, カ ッ トの選びかたにより,解の値 に大 きな影響を及ぼす結果 となるためであ る｡ しか し,ブロックサイズが大であると,そのカッ トの選びかたに多様性が あるので最良な値を選びやす く,上記の影響 は現れない｡また,中間エ ッジが 入 ることによるグラフの複雑性には本解法は影響を受けない｡

本算法の計算時間は頂点数200 のグラフに対 しては‑反復 6 .2m s とな り;

20 00 か ら 30 0 0 の反復で計算が一般 に終了す るので,約1 2 か ら 1 8 秒の計算時間 を要す ることとなる｡ これは近似解を求めるのに十分に効果的な時間内での処 理が行えることを意味す る｡

7 .おわ りに

本稿 で は,無 閉路有 向 グラ フの系列分 割 問題 に対 す る効果 的 な Tabu se ar c h の適用を試みた｡無閉路有向グラフの複雑なデータ構造を一列化 グラ

フによる単純なデータ構造へ変換す ることによって高速処理および記憶容量の 削減を実現 した｡また,効果的な近傍構造を構成す ることによって,解の移動 の多様性を広げるとともにより近似度の高い解を探索す ることを可能 とした｡

さらに,禁断 リス トにより解のサイクリングを避けるとともに探索空間の効果

的な削減を行 うことによって高速な処理を実現 した｡次に数値実験により算法

Tabu s earc h を用 いた無閉路有 向 グラフ系列分割 問題 の近似解法 141 の特性および挙動の分析を行い,パラメーターの適正化に対す る傾向を明 らか にした｡また,全般的に TabuSearch は無閉路有向グラフの系列分割問題 に 対 して近似度の高い結果を得 ることが示 され,最良解の探索に効果がある算法

と結論できうる｡

最後 に,以上 の数値実験 は小樽商科大学情報処理セ ンターの Argoss5270 ( SUN) および DEC3000 上で行 った｡

参 考 文 献

1)Be t t s , j. and Mahmoud, k. i. : A Met hodf orAss embl y Li neBal anc i ng , Engi nee ri ngCos t sandPr oduc t i onEc onomi cs,Vol . 1 8 , pp5 5‑64( 1 989) . 2)Ke rni ghan, B. W∴ Opt i malSequent i alPart i t i onsofGraphs , ∫. ACM ,

Vol . 1 8,No.1,pp. 34‑40( 1 97 1) .

3)Gl ov e r,F. :TabuSe arc hI,ORSA J. C., Vol .1,No3,pp1 90‑20 6( 1 989 ) . 4)Gl ove r,F∴TabuSearc h Ⅱ ,ORSA ∫. C., Vol .2,No l ,pp4‑3 2( 1 99 0) . 5)Ree ves, C. R :Mondarn Heuri st i cTec hni qusf orCombi nat ori alProb‑

l ems,Bl ac kWe l l ( 1 99 3) .

6)Sal veson, M. E. : TheAss embl y Li neBal anci ng Probl em,TheJour nal oH ndus t r i alEngi nee r i ng,May‑June,pp. 18‑25( 1 9 55).

7) 茨木俊秀 : 組合わせ最適化 一分枝限定法を中心 として‑,産業図書 ( 1 983).

8) 加地 :半順序の最適系列分割問題の構造 と算法構成,商学討究, Vol . 45 ,No.2 , pp1 85‑204( 1 99 4) .

9 )加地,大内 :最適系列分別問題 に対する効率的分枝限定法の構築 と諸特性解析,情 報処理学会論文誌, Vol . 35 , N) ･3,pp. 3 64‑372( 1 99 4) .

1 0 ) 久保 :巡回セールスマ ン問題への招待, 日本 OR , Vo1 3 9,No3,pp156‑1 6 2 ( 1 9 94) .

ll ) 日本 OR 学会第 30 回 シンポジウム :モダンヒュ‑ リステイクの新展開 ‑Gnet i cA1 ‑ gor i t hm,Si mul at edAnneal i ng,TabuSearch,NeuralNet 法 は本当に有効 か‑, ( 1 99 4).

1 2 ) 藤沢,久保,森戸 : TabuSearc bのグラフ分割問題‑の適用 と実験的解析,電学

論 C , Vol . 11 4,No4,pp4 30‑437( 1 99 4) .