メタ戦 略の評価分析 と

メタ戦 略の評価分析 と

並 列TabuSearchア ル ゴ リ ズ ム の 提 案

小樽商科大 学大学 院平 成12年3月 修 了 現㈱ ア ジェ ンダ 丸 田 寛 之

小樽 商科大学 加 地 太 一

1は じ め に

対 象 が 組 合 せ 的,離 散 的 な条 件 の 下 で の 最 適 化 を組 合 せ 最 適 化 問題 と呼 び, 配 送 計 画 問題,生 産 ス ケ ジ ュー ル 問題 お よ び工 場 施 設 配 置 問 題 な ど多 くの 意 思 決 定 の 問 題 で利 用 され て い る。 しか し,こ の 問題 の 特 徴 と して 問 題 の サ イ ズ に した が っ て組 合 せ 的 爆 発 をお こ し,計 算 機 で も数 兆 年 の時 間 を要 す る計 算 困 難 な 問題 と な る。 そ こで,近 似 解 を求 め代 替 す る戦 略 と して,近 年 メ タ戦 略 の 有 効 性 が示 さ れ て い る。 こ れ まで 様 々 な メ タ戦 略 の改 良 ア ル ゴ リズ ム が 提 案 され て きた 。 しか しな が ら,実 際 的 な利 用 に 際 して は そ れ ら の改 良 ア ル ゴ リズ ム よ り も基 本 的 な構 成 の ア ル ゴ リズ ム を用 い る こ とが 一 般 的 で あ る が,こ れ らの基 本 的 な構 成 の ア ル ゴ リズ ム の優 劣 は 明確 で は な く,各 応 用 分 野 に お け る利 用 に 際 して 総 合 的 な 評価 を行 い特 質 を明 らか に す る こ とが 求 め られ る 。 こ こ で は 組 合 せ 最 適 化 問 題 の代 表 的 な 問題 で あ る グ ラ フ分 割 問題 を対 象 と して,基 本 的 な 構 成 に よ る各 種 メ タ戦 略 を複 雑 度 の 高 い複 数 分 割 問題 に適 用 し,評 価 実 験 を行 い 各 ア ル ゴ リ ズ ム の 基 本 性 能 を比 較 評 価 す る もの で あ る。

ま た,こ れ らの メ タ戦 略 は 計 算 機 の進 化 と と もに 飛 躍 的 な発 展 を遂 げ て きた 。 しか しな が ら最 近 は従 来 の 計 算 機 ア ー キ テ クチ ャ で は す で に計 算 能 力 が 頭 打 ち の 状 況 で あ り,新 しい パ ラ ダ イ ム と し て並 列 計 算 機 が 注 目 され て い る。 こ れ は 従 来 の 逐 次 的 な ア ル ゴ リズ ム と は 異 な る ア プ ロ ー チ が 要 求 さ れ る もの で あ る

〔91〕

が,並 列 計 算 機 は複 数 の プ ロ セ ッサ で 処 理 を 複 数 同時 に行 う こ とで 計 算 性 能 を 大 き く向 上 させ る もの で あ り,そ の メ リ ッ トは 非 常 に大 きい 。 そ こ で,探 索 時 問 を要 す るTabuSearchを 並 列 化 し探 索 時 間 及 び解 の 質 の 改 善 を 試 み た。

TabuSearchは 探 索 す る近 傍 空 間 の サ イ ズ が 大 き くな る と多 大 な 計 算 時 間 を 要 す る。 そ こで 近 傍 探 索 を分 割 す る こ と で複 数 の プ ロ セ ッサ で 分 散 して 探 索 す る こ とに よ る計 算 時 間 の 短 縮 を試 み た 。 さ らに,各 プ ロ セ ッサ 上 で 部 分 解 を 同 時 に複 数 生 成 し,TabuSearchに よ る 局 所 的 な探 索 を複 数 同 時 に行 う こ と で 解 の 質 の 向 上 を試 み た 。 これ は 問 題 を独 立 した 部 分 問 題 に 分 割 し,各 プ ロセ ッ サ 上 で 部 分 問 題 に対 して探 索 を行 い 収 束 させ,部 分 解 を生 成 す る。 各 プ ロセ ッ サ で 生 成 さ れ た 部 分 解 は 通信 に よ っ て 完 全 解 へ 合 成 す る。 これ を繰 り返 す こ と で収 束 性 に優 れ,探 索 時 間 も短 い ア ル ゴ リズ ム を提 案 した。 この ア ル ゴ リズ ム を構 成 す る上 で,TokenPassingと い う手 法 を用 い た 。 こ の手 法 で は計 算 環境 に と らわ れ ず に比 較 的 自由 な 実 装 を可 能 と レ 効 果 的 に各 プ ロ セ ッサ に ス ケ ジ ュ ー リ ン グ を行 う こ とが で き る。 各 プ ロ セ ッサ に は 完 全 に独 立 した 部 分 問 題 が 割 り当 て ら れ,独 立 した 探 索 を行 う こ とが 可 能 な こ とか ら,各 プ ロセ ッサ は 他 の プ ロ ゼ ッサ と異 な る ア プ ロ ー チ で 解 を 収 束 させ,同 時 に他 の プ ロセ ッサ の 状 態 に依 存 せ ず に非 同 期 に探 索 を行 う こ と も実 現 で きる もの で あ る 。

2グ ラ フ分 割問 題

グ ラ フ分 割 問 題 は,NP一 困 難 な組 合 せ 最 適 化 問題 の 一 種 で あ り,VLSIの 回 路 設 計 等 のCADや 配 置 ・配 送 問 題,プ ロ グ ラ ム分 割 問 題 な ど に応 用 され る も の で あ る。 こ の 問 題 は ウ ェ イ トを もつ 〃 ノ ー ド(頂 点)と コ ス トを もつ エ ッ ジ(辺)か ら な る グ ラ フ を各 部 分 集 合 に分 割 し,そ の異 な る部 分 集 合 聞 の エ ッ ジ コ ス ト総 和 が 最 小 に す る 問 題 で あ る 。 ノ ー ド数 πが 十 分 に小 さ い 場 合,厳 密 解 法 に よっ て 解 く こ とが で きる が,あ る程 度 を超 え る と組 合 せ 的爆 発 に よ り 厳 密 解 を得 るの は難 し くな る。 また 本 問 題 は 多 分 割 の た め,従 来 研 究 され て い る2分 割 に比 べ て汎 用 的 で あ る が複 雑 度 が 高 くな る。

メ タ戦 略 の 評 価 分 析 と並 列TabuSearchア ル ゴ リズ ム の 提 案 93 今 回 対 象 とす る 問 題 は,頂 点 集 合Vと 無 向 辺 集 合Eか らな る グ ラ フZ)(V, E)に お い て,そ の カ ッ トエ ッ ジの コス トが 最 小 と な る よ うな 多 分 割 を 求 め る

問題 で あ り,制 約 条 件 と して 分 割 した各 部 分 集 合 に お け る頂 点 の ウ ェ イ ト総 和 が あ る 値 乃 を こ え な い もの とす る。 こ の 問 題 は以 下 の よ う に 定式 化 され る。

minΣei」

i∈Vi,ゴ ∈ 巧 ・ゴ≠ゴ

subjecttoΣw(の ≦Pi,i=1,̲,ん 刀∈ レ}

こ こで,〃 ω)は 頂 点"の ウ ェ イ トとす る 。 ま た,ブ ロ ッ クサ イ ズ 乃 と分 割 数 たは 与 え られ た 数 で あ る 。

3メ タ戦 略

組 合 せ 最 適 化 問 題 はNP一 困 難 な 問 題 と さ れ,厳 密 な 完 全 解 を 求 め る こ とは 計 算 量 の 問 題 か ら非 常 に 困 難 で あ る。 そ こで 何 らか の 近 似 解 法 に よ っ て 問 題 を 解 き,近 似 解 を求 め る こ とに な る。

近 年 で は組 合 せ 最 適 化 問 題 を解 くた め に ヒ ュ ー リス テ ィ ック な 知 識 を有 機 的 に組 合 わ せ て,よ り高 度 な ア ル ゴ リズ ム を構 成 した メ タ戦 略 の研 究 が 盛 ん に 行 わ れ て お り,従 来 の 近 似 解 法 を超 え たパ ラ ダ イ ム と して 注 目 され て い る。 メ タ 戦 略 は ヒ ュ ー リス テ ィ ック に パ ラ メ ー タ を追 加 し,そ の 自 由度 を用 い て 問 題 を 解 くテ クニ ック で あ る た め,パ ラ メ ー タ を適 正 値 に 設 定 す る作 業 が 不 可 欠 とな る[1]。 これ らの メ タ戦 略 は これ ま で改 善 アル ゴ リズ ム も多 く提 示 され て い る 。

しか し,問 題 解 決 の た め の 実 際 的 な利 用 で は,通 常 は 標 準 的 な構 成 で 利 用 され る の が 常 で あ る 。 しか しな が ら,各 種 メ タ戦 略 の標 準 的 な構 成 の 能 力 は あ ま り 知 られ て い な い た め,実 際 的 な評 価 を行 い そ の特 質 を明 らか に す る。 こ こ で は ま ず メ タ戦 略 の基 本 的 な 考 え方 と グ ラ フ 分 割 問 題 へ の 適 用 に お け る構 成 を 示 す 。

3.1近 傍 の 構 成

メ タ戦 略 にお い て は,そ の ほ とん どが 近 傍 を基 礎 と して構 築 さ れ て お り,近 傍 構 成 の 設 計 が 重 要 と な る。 近 傍 の構 成 は 問 題 依 存 で あ り,各 問題 に 適 用 す る に は 問題 の 特 性 に合 わ せ て 設 計 す る必 要 が あ る 。

近 傍Nは 実 行 可 能 解 の集 合Xを 与 え た と き,以 下 の 写 像 と して 定 義 され る。

!V:X→2x

す な わ ち,実 行 可 能 解 の 集 合 か ら,そ の べ き 集 合(部 分 集 合 の 集 合)へ の 写 像 が 近 傍 で あ る 。実 行 可 能 解x∈Xで,f(x)≦ ノ●(y),∀.y∈N(x)を 満 た す も の を, 近 傍Nに 対 す る 局 所 的 最 適 解(10caloptimalsolution)と 呼 ぶ 。[1]

こ こ で 用 い る グ ラ フ 分 割 問 題 の 近 傍 は 通 常 用 い られ る ブ ロ ッ ク 問 の 頂 点 の 交 換 に 基 く も の を 使 用 す る 。 こ の と き,解 κ を

x=(Sl,S2,̲,Sn)

と し,&は 分 割 さ れ た頂 点 の 部 分 集 合 を 表 す もの と し て,こ の 解 κ に対 して 近 傍 構 造 万(の を以 下 の よ う に定 義 す る。

2V(x)ニ{x'=(Sl,S2,̲,S'v,̲,S/w,̲,Sn):S/v=(Sv＼li})∪{ブ},

S'w=(Sw＼{ブ})U{i},fori≠ ブ,∀i,∀ ブ}

3.2LocalSearch

LocalSearchは メ タ 戦 略 の 基 本 と な る ア ル ゴ リ ズ ム で あ り,今 回 対 象 と す る ア ル ゴ リ ズ ム もGeneticAlgorithmを 除 い て は こ のLocalSearchを 基 本 的 な 構 造 と し て い る 。 今 回 実 験 を 行 っ たLocalSearchは 最 も 基 本 的 な も の で あ る 。 探 索 は ま ず 現 在 の 解 の 近 傍 の 中 か ら,最 も解 を 改 善 す る も の を 選 択 す る 。 こ れ を 次 の 解 と し て 採 用 し,近 傍 の 中 に こ れ 以 上 改 善 す る 解 が な く な っ た 時 点 で 探 索 を 終 了 す る 。 こ のLocalSearchの 短 所 は 局 所 最 適 解 に 陥 りや す い こ と で あ り,一 旦 局 所 最 適 解 に 陥 る と,脱 出 手 段 を 持 た な いLocalSearchで は そ こ で 探 索 を 終 了 し て し ま う 。 こ の た め,他 の ア ル ゴ リ ズ ム と比 較 し て 解 の 質 は

メ タ戦略 の評 価分析 と並列TabuSearchア ル ゴ リズムの提 案95 そ れ ほ ど良 くな い 。LocalSearchの 近 傍 生 成 は 標 準 的 な も の と して,解xの 近 傍N(x)の 中 か ら最 良 な解 を選 択 し,次 の 解 に移 動 す る も の とす る 。 こ の解 生 成 を 関数 勿 ρ ω と表 現 し,以 下 の よ うに 定 義 す る。

imP(x)一{乙;ifminlcost(x')}<礁 廊 送綴

3、3TabuSearch

TabuSearchはLocalSearchの 変 形 で,一 度 交 換 し た 頂 点 をTabuListTL に 一 定 期 間 記 憶 し,同 じ解 の 探 索 を 禁 止 す る こ と で 解 の サ イ ク リ ン グ を 防 ぐ も の で あ る 。 近 傍 生 成 は 標 準 的 な も の と し て,解 κ の 近 傍 万(κ)の 中 か ら π に 含 ま れ る も の を 除 い た な か で 最 良 な 解 を 選 択 し,次 の 解 に 移 動 す る も の と す る 。

こ れ を 関tWimPTL(x,TL)と 表 現 し,以 下 の よ う に 定 義 さ れ る 。

i〃ipT,乙(x,TL)=〆if!(〆)≦!(ン)forallツ ∈(N(x)＼TL)

通 常,TabuListは 解 そ の もの を保 持 す る の で は な く,解 の移 動 に 関 連 す る何 ら か の 属 性 をTabuの 要 素 とす る。 今 回 は 移 動 し た 頂 点 を属 性 と してTabu Listに 記 憶 し,一 度 移 動 した頂 点 は一 定期 間 の 移 動 を禁 止 し た。

今 回 は これ に長 期 メ モ リ(Long‑termmemory)を 付 加 した も の を採 用 した 。 一 般 的 なTabuListはTabuLengthと して 与 え られ た 期 間 の サ イ ク リ ン グ を 防 ぐも の で あ るが,長 期 メモ リ は 長期 的 なサ イ ク リ ン グ を 防 ぐ もの で あ り,探 索 が 終 了 す る まで 保 持 され る 。 長 期 メ モ リ は 配 列LT(n)に 頂 点 の移 動 回 数 を 記 憶 す る もの と した 。 この と き,頂 点 ゼと頂 点 ブを 交 換 した と き の コス トを 以

下 の 式 で評 価 す る。

f(Si7・)+(卿)×B阻s去 珊)×BIAS)

こ れ は,頂 点 ♂と ブを 交 換 し た と きの コ ス トノ(8毎・)に頂 点 ゴと ブの 移 動 回 数 に 応 じた コ ス トを評 価 時 に 加 え る こ とで,頻 繁 に移 動 を繰 り返 す 頂 点 を移 動 し に

く くす る もの で あ る。

3.4SimulatedAnnealing

SimulatedAnnealingは,局 所 探 索 を ラ ン ダ ム に行 い,解 が 改 悪 さ れ た 場 合 で も新 しい解 に あ る確 率 で 移 る こ とで,局 所 最 適 解 に 補 足 さ れ る こ と を 防 ぐア ル ゴ リズ ム で あ る 。

この ア ル ゴ リズ ム は,「 温 度 」 を ゆ っ く り と低 下 させ る こ と で 結 晶 構 造 を安 定 させ る焼 き鈍 しの ア ナ ロ ジー を用 い て い る。SimulatedAnnealingで は,近 傍 か ら新 しい解 を確 率 的 に選 択 す る。 選 択 され た解 は,現 在 の 解 よ りも改 善 さ

れ る もの で あ れ ば 無 条 件 に受 理(Accept)さ れ る 。改 悪 す る もの で あ っ た 場 合, 次 式 の よ う に温 度 を用 い て確 率 的 に受 理 す るか ど う か を 決 定 す る。

1ー

・xp(c^{∫(κ)一∫(め}

iff(xノ)≦ 二!(x)

)iff(x')〉!ω

cは 温 度 で あ り,f(x)は 現 在 の解 の コス ト,!(xノ)は 新 しい解 の コ ス トで あ る。

こ れ は つ ま り,解 が改 悪 され る場 合 はe『△/Cの 確 率 で 受 理 す る こ と を意 味 す る 。 こ の温 度cは 一 定 の 係 数 に よっ て 減 少 して い く。 温 度 が 高 い と きは 改 悪 さ れ る 解 は 受 理 さ れ や す い が,温 度 が低 くな る に つ れ 改 悪 さ れ る 解 は受 理 され に く く

な る 。

3.5GeneticAlgorithm

GeneticAlgorithmは 自 然 淘 汰 や 突 然 変 異 と い っ た,生 物 の 進 化 論 を モ デ ル と し た ア ル ゴ リ ズ ム で あ る 。GeneticAlgorithmで は,Reproduction,Cross‑

over,Mutationの3つ の オ ペ レ ー タ に よ っ て 遺 伝 子 を 進 化 さ せ る も の で あ る 。 こ の ア ル ゴ リ ズ ム は,集 団 と し て 多 数 の 解 を 個 体 と し て 保 持 す る 。Reproduc‑

tionで は,こ れ ら の 集 団 か ら 目 的 関 数 値 の 高 い 個 体 を 高 い 確 率 で 複 製 す る 。 次 に,Crossoverに よ っ て 個 体 同 士 を 交 叉 し,そ れ ぞ れ の よ り良 い 部 分 を 合 成 し て 新 し い 個 体 を 生 成 す る 。 ま た,Mutationで は 複 製 の 際 に あ る 確 率 で 突 然 変 異 を 発 生 さ せ る 。 こ れ に よ っ て 個 体 群 に 多 様 性 を も た せ る も の で あ る 。

メ タ 戦 略 の 評 価 分 析 と 並 列TabuSearchア ル ゴ リ ズ ム の 提 案 97 GeneticAlgorithmに お け る遺 伝 子 の 要 素 は 記 号 列 で あ り,対 象 とす る 問 題 を 記 号 列 と して 表 現 し な け れ ば な らな い 。 今 回GeneticAlgorithmで 採 用 した 近 傍 構 造 は,す で に実 績 が あ り一 定 の 結 果 を 示 して い る もの を採 用 した[9]。

各 ブ ロ ッ ク毎 に 頂 点 を線 形 に 配 置 し,各 頂 点 を遺 伝 子 と して扱 う もの と した 。 こ こで 用 い る 交 叉 は,親 遺 伝 子 か ら優 位 な 部 分 集 合 を確 率 的 に 選 択 し,対 応 す る遺 伝 子 部 分 を保 持 す る。 そ れ 以 外 の遺 伝 子 部 分 を他 の 親 遺 伝 子 か ら コ ピ ー す る もの と し た。

Parent‑A

Parent‑B

Block1 Block2 Block3

○φ(}Q◎ 670

ノ

/

8(⊃ 〈わ 54(誕)、

↓

80 ³⁴⁵ 621 BlocklBlock2Block3

図1:GeneticAlgorithmCrossover

図1は 交 叉 の 一 例 で あ る 。ま ず,8ノ ー ド3ブ ロ ッ ク か ら な る グ ラ フ に お い て, 各 頂 点 を 線 形 に 配 置 す る 。Parent‑Bか らParent‑Aへ 交 叉 し 次 世 代 の 解 を 生 成 す る 場 合,優 位 な ブ ロ ッ ク をBlock2と す る と,Parent‑AのBlock2を ま ず 保 存 し,そ れ 以 外 の ノ ー ド をBlock‑Bの も の と 置 き 換 え る 。 つ ま り, Parent‑Bに お け るBlock1の ノ ・一一・ド8と7をParent‑AのBlock1ヘ コ ピ ー す

る 。 こ れ でParent‑AのBlock1は 埋 ま っ た の で 次 はBlock2で あ る が,Block2

は 優 位 な ブ ロ ッ ク で あ る た め,そ の ま ま 保 存 す る 。 次 にParent‑Aの 優 位 な ブ ロ ッ ク に 含 ま れ る ノ ー ド を 除 い て,Parent‑AのBlock3へParent‑Bか ら ノ ー ド を 同 様 に コ ピ ー す る 。 結 果,Parent‑Aの 優 位 な ブ ロ ッ ク を 保 存 し た ま ま, Parent‑Bの 情 報 と 交 叉 で き る こ と に な る 。

ま た 今 回 採 用 し た 親 遺 伝 子 の 選 択 は,個 体 の コ ス ト値 に 応 じ て 優 秀 な も の か ら 確 率 的 に 選 択 す る,適 応 度 比 例 方 式(ル ー レ ッ ト選 択)と し た 。 こ の と き 使 用 し た 適 応 度 関 数 は 次 式 で あ る 。

ness=cost 1Fit

つ ま り,コ ス トが 小 さ い ほ ど適 応 度 が 高 い もの と した 。 ま た 交 叉 点 の選 択 は, 選 択 した 親 が 保 持 す る解 の なか で 最 も優 秀 な ブ ロ ッ ク を保 存 す る も の と した 。

こ の と き,各 ブ ロ ッ ク の 内 部 コス トが 大 きい も の は 外 部 コス ト(カ ッ トエ ッ ジ コ ス ト)が 小 さい 傾 向 で あ る こ とか ら,内 部 コ ス トが も っ と も大 きい ブ ロ ッ ク を保 存 す る もの と した 。 ま た,突 然 変 異 は 指 定 した確 率 で ラ ン ダム に選 択 され た 頂 点 をブ ロ ック 間 で 強 制 的 に 交 換 す る もの と し,こ れ を全 て の 親 遺 伝 子 に対

して行 っ た 。

4メ タ戦 略 の 数 値 実 験 に よ る評 価 分 析

今 回 の 各 メ タ戦 略 の 基 本 的 な構 成 に よ る 実 験 で は,100〜500ノ ー ドの ラ ンダ ム グ ラ フ を対 象 と した 。ラ ンダ ム グ ラ フ の 生 成 は,ノ ー ドxか らx+1へ の エ ッ ジ を全 ノ ー ドに対 して 生 成 す る こ とで,closedな グ ラ フで あ る こ と を保 証 し, さ ら に各 ノ ー ドか らノ ー ド数 の10%つ つ ラ ン ダ ム にエ ッ ジ を発 生 させ た 。 よ っ て,nノ ー ドグ ラ フ の エ ッ ジの 総 数 はn×{(〃/10)+IIで あ る。 ま た,各 エ ッ ジの ウ ェ イ トは1〜10の 範 囲 で ラ ン ダム に設 定 し,各 グ ラ フ にお け る各 ノ ー ド の ウ ェ イ トは 固 定 と した 。

メ タ戦 略 の 重 要 な要 素 と してパ ラメ ー タ の 設 定 が あ り,こ れ に よ っ て解 の 質 が 大 き く左 右 され る。 通 常,こ れ らの 値 は事 前 の 数 値 実 験 に よ っ て設 定 を行 う

メ タ戦 略 の 評 価 分 析 と並 列TabuSearchア ル ゴ リ ズ ム の 提 案 99 も の で あ る 。TabuSearchで は,TabuLengthの 設 定 が 必 要 で あ る 。Tabu Lengthは 事 前 に500ノ ー ドの グ ラ フ で い くつ か の パ ラ メ ー タ で 実 験 を 行 っ た 。

こ の 予 備 実 験 は 異 な る10種 類 の グ ラ フ,グ ラ フ1〜 グ ラ フ10に 対 し て 行 い,そ の 平 均 か ら20が 最 良 で あ っ た た めTabuLengthと し て 採 用 し た 。 ま た, LongtermmemoryのBIAS値 も 同 様 に 実 験 を 行 っ た と こ ろ,0.20が 最 良 で あ っ た た め,0.20に 設 定 し た 。SimulatedAnnealingに 関 し て は 初 期 温 度,温 度 減 少 係 数,終 了 基 準 温 度,内 側 ル ー プ の 回 数,そ の 増 加 係 数 の 設 定 が 必 要 で あ る 。 初 期 温 度 は 高 い ほ ど 良 い コ ス トが 得 ら れ る が,高 す ぎ る と 無 駄 な 探 索 が 増 え,計 算 時 間 が 増 加 す る 。 初 期 温 度 と 終 了 基 準 はAcceptanceRatioと 同 時 に 計 測 し,AcceptanceRatioが0.7〜0,0003と な る よ う に 初 期 温 度 を15,終 了 基 準 を0.01に 設 定 し た 。 つ ぎ に 温 度 の 減 少 係 数 は1に 近 い ほ ど ゆ っ く り と 冷 却 さ れ る こ と に な る た め,1に 近 い ほ ど コ ス トが 改 善 さ れ る が,こ れ も 同 様 に 大 き す ぎ る と 計 算 時 間 が 劇 的 に 増 加 す る 。 こ れ も 同 様 に い くつ か の 係 数 に 対 し て コ ス ト と 計 算 時 間 を 計 測 し た と こ ろ,0.97ま で は コ ス ト の 改 善 が 見 ら れ る が,そ れ 以 上 は コ ス ト は 改 善 さ れ ず 計 算 時 問 だ け が 増 加 す る た め,0.97を 採 用 し た 。 ま た,内 部 ル ー プ の 回 数 は100と し,増 加 係 数 は 計 算 時 間 と の ト レ ー一・ド オ フ で 1.03と し た 。GeneticAlgorithmで はPopulation数 と 突 然 変 異 発 生 率 を 設 定 す る 必 要 が あ る 。Population数 は 個 体 群 に 含 ま れ る 個 体 の 総 数 で あ り,多 い 程 良 い コ ス トが 得 ら れ る 傾 向 に あ る が,多 い 程 計 算 時 聞 が 増 加 す る 。 こ れ も い く つ か のPopulationで 実 験 を 行 っ た 。Populationを 増 加 さ せ る ほ ど コ ス トが 低 下 す る が,計 算 時 間 も 劇 的 に 増 加 す る 。 実 験 の 結 果,300ま で は 減 少 傾 向 を 示 し た が,そ れ 以 上 は 停 滞 傾 向 で あ っ た た め300を 採 用 し た 。 ま た,突 然 変 異 発 生 率 も 同 様 に 実 験 を 行 い,最 良 で あ っ た0.04を 採 用 し た 。 こ れ は1イ テ レ ー シ ョ ン に お け る 各 個 体 に 対 す る 確 率 で あ る 。

今 回 実 験 に 用 い た 環 境 はlnte1CeleronProcessor/400MHzを 搭 載 し た PC/AT互 換 機 のLinux上 で 実 験 を行 っ た 。 表1に8ブ ロ ッ ク の 分 割 問 題 に お け る 実 験 結 果 を 示 し た 。SimulatedAnnealing,GeneticAlgorithmに 関 し て は ア ル ゴ リ ズ ム 中 に確 率 要 素 が あ る た め,そ れ ぞ れ10回 実 験 を 行 い,そ の 平 均

表1:ComputationalResultobtainedusingLS,TS,SAandGA

Algorithm 100 200 300 400 500

LocalSearch 3838.0 16526.0 38252.0 69282.0 108484.0 TabuSearch 3812.0 16335.0 37710.0 68843.0 108055.0 Simulated

Annealing

AVG 3704.8 16269.6 37794.0 68968.8 108425.6 MIN 3687.0 16238.0 37744.0 68770.0 108302.0 MAX 3734.0 16342.0 37879.0 69104.0 108526.0

GeneticAlgorithm

AVG 4491.4 18559.4 42671.0 75423.0 118619.4 MIN 4346.0 18438.0 42580.0 75204.0 118457.0 MAX 4558.0 18647.0 42765.0 75822.0 118936.0

表2ComputationalTimeobtainedusingLS,TS,SAandGA(sec)

Algorithm 100 200 300 400 500

LocalSearch 1.40 24.58 137.78 756.56 1391.83

TabuSearch 7.25 93.66 423.36 1357.88 2210.26

SimulatedAnnealing 29.49 75.41 147.51 230.50 307.12 GeneticAlgorithm 1ユ0.8ユ 500.45 974.5ユ 1814.66 1886.03

をAVGに,最 小 値 をMINに,最 大 値 をMAXに 示 し た 。 ま た,表2は そ の 計 算 時 間 を示 した 。

LocalSearchは,TabuSearchやSimulatedAnnealing等 と 比 較 して そ れ ほ ど良 い コ ス トは 得 られ な か った 。 こ の ア ル ゴ リズ ム は局 所 最 適 解 に 陥 る と脱 出手 段 を もた な い た め,こ れ 以 上 の改 善 を行 う こ とが で き な くな る。 最 初 に 局 所 最 適 解 に陥 っ た 時 点 で 探 索 を終 了 して し ま う こ とか ら,他 の 局所 最 適 解 か ら の脱 出 手 段 を もつ アル ゴ リズ ム と比 較 して 解 の 質 が劣 る こ とは 明 らか で あ る 。

TabuSearchは 比 較 的 良 い 結 果 を 出 し て い る が,今 回 採 用 し たTabu Searchの 近 傍 は全 近 傍 を探 索 す る必 要 が あ る た め,計 算 時 間 が 大 き く,ノ ー

ド数 の 増 加 と と も に 計 算 時 間 が 増 加 す る 。 こ の た め,TabuSearchは 比 較 的 少 な い ノー ド数 の グ ラ フ に お い て は効 果 的 で あ るが,ノ ー ド数 が 多 い グ ラ フ に 対 して は 現 実 的 で は な い。

SimulatedAnnealingに 関 し て はTabuSearchと 同 レ ベ ル の コス トが 得 ら れ た 。 少 な い ノ ー ド数 の グ ラ フ にお い て は 計 算 時 間 が他 の ア ル ゴ リズ ム よ り も

メ タ戦 略 の 評 価 分 析 と並 列TabuSearchア ル ゴ リ ズ ム の 提 案 101 長 い が,比 較 的大 規 模 な グ ラ フ に対 して は 他 の ア ル ゴ リズ ム よ り も圧 倒 的 に短 い 計 算 時 間 で 探 索 を完 了 す る 。

SimulatedAnnealingの 近 傍 生 成 は,確 率 的 に ノー ドを 選 択 す る もの で あ る た め,他 のLocalSearchやTabuSearchの よ うに 全 近 傍 を探 索 す る もの に比 較 す る ど圧 倒 的 に 短 い 時 間 で1イ テ レ ー シ ョ ンを 完 了 す る 。 さ ら に,ノ ー ド数 や ブ ロ ッ ク数 の 影 響 も受 け に くい 。 実 験 結 果 で 示 さ れ る,ノ ー ド数 に 対 す る計 算 時 間 の 増 加 の ほ とん どはSimulatedAnnealingの ア ル ゴ リズ ム そ の もの で は な く,ノ ー ドの交 換 処 理 な どの グ ラ フ操 作 に 関 す る部 分 が 大 部 分 を 占 め る の が 原 因 で あ る。

ま た,GeneticAlgorithmは 今 回 の標 準 的 な構 成 の ア ル ゴ リズ ム に お い て は LocalSearchに も及 ば なか っ た 。GeneticAlgorithmに 関 して は近 傍 構 造 の 改 善 等 で 若 干 改 善 が 得 られ る可 能 性 もあ る が,本 質 的 に本 問 題 の よ うな 組 合 せ 最 適 化 問 題 に は 適 用 し に くい ア ル ゴ リズ ム で あ り,LocalSearchな ど の 局 所 性 の あ る ア ル ゴ リ ズ ム との ハ イ ブ リ ッ ドが 有 効 で あ ろ う。

5並 列 処 理 とMPl

これ ま で の ア ル ゴ リズ ム は逐 次 的 に実 行 を行 う,い わ ゆ る フ ォ ンノ イ マ ンマ シ ン と呼 ば れ る逐 次 計 算 モ デ ル に 基 い た コ ン ピ ュ ー タ で計 算 され る も の で あ る。 こ の モ デ ル は シ ン プ ル で あ る反 面,単 一 の プ ロ セ ッサ で 全 て の 処 理 を行 う た め 処 理 能 力 は そ の プ ロセ ッサ の 能 力 に依 存 す る。 これ まで 組 合 せ 最 適 化 問題

を解 くた め の ア ル ゴ リズ ム は コ ン ピ ュ ー タの 進 化 と と も に発 展 して きた 。 しか し なが ら単 一 の プ ロ セ ッサ の性 能 はす で に 限 界 に達 して お り,ベ ク トル 計 算 機 等 の ス ーパ ー コ ン ピュ ー タ もす で に頭 打 ち の状 態 で,並 列 化 に よ っ て性 能 を確 保 して い る の が 現 状 で あ る[2]。 並 列 処 理 は 複 数 の プ ロ セ ッサ を協 調 さ せ て利 用 す る こ とで 計 算 時 間 を短 縮 させ る新 しい パ ラ ダ イ ム で あ り,組 合 せ 最 適 化 問 題 に対 す る新 た な 近 似 解 法 を展 開 す る もの で あ ろ う。

今 回 の 実 験 で は,並 列 処 理 を 実 現 す る 手 段 と し てMPI(MessagePassing

Interface)ラ イ ブ ラ リ を 採 用 し た 。MPIは メ ッ セ ー ジ 通 信 を 行 う た め の ラ イ ブ ラ リ 標 準 で あ る が,そ の 利 点 は ポ ー タ ビ リ テ ィ と 使 い や す さ に あ る 。MPI は 分 散 メ モ リ の マ ル チ プ ロ セ ッ サ,ワ ー ク ス テ ー シ ョ ン の ネ ッ ト ワ ー ク,ま た こ れ ら の 組 み 合 わ せ の 環 境 で も 動 作 す る よ う に 設 計 さ れ,さ ら に 共 有 メ モ リ で も実 現 可 能 で あ る[3]。

今 回 並 列 ア ル ゴ リ ズ ム の 実 験 を 行 っ た 環 境 は,い くつ か の 独 立 し た コ ン ピ ュ ー タ を ネ ッ トワ ー ク に 接 続 し,そ れ を プ ロ セ ッ サ 間 の 通 信 路 と し て 利 用 す る も の で,ワ ー ク ス テ ー シ ョ ン ク ラ ス タ の 一 形 態 で あ る 。 そ の ネ ッ ト ワ ー ク 構 成 は,100BASE‑TXEthernetを 用 い,各 コ ン ピ ュ ー タ をFastEthernetSwitch‑

ingHUBへ 接 続 し た 。 コ ン ピ ュ ー タ はIntelCeleronProcessor/400MHzを 搭 載 し た 同 性 能 の コ ン ピ ュ ー タ を4台 使 用 し,OperatingSystemに はLinuxを 採 用 し た 。

こ の 環 境 に お い てMPIの 通 信 パ フ オ ー マ ン ス テ ス ト を 行 っ た と こ ろ,1024 バ イ ト ブ ロ ッ ク の 実 効 転 送 速 度 は1.3Mbps程 度 で あ っ た 。 ま た,ブ ロ ッ ク サ

イ ズ を 大 き く し た ピ ー ク 性 能 で も23Mbps程 度 で あ っ た 。 こ の 通 信 路 の バ ン ド 幅 の 狭 さ は 弱 結 合 で あ る ワ ー ク ス テ ー シ ョ ン ク ラ ス タ の 欠 点 で あ り,専 用 の 並 列 計 算 機 等 と比 べ て 大 き く劣 る 点 と な っ て い る こ と か ら,ア ル ゴ リ ズ ム を 構 成 す る 際 に 通 信 量 を で き る だ け 抑 え る こ と が 求 め ら れ る 。

6近 傍 分 割 並 列TabuSearch

TabuSearchは 全 近 傍 を探 索 す る性 質 上,多 大 な 計 算 時 間 を必 要 と し一 定 の ノー ドを超 え る と現 実 的 な 計 算 時 間 で は解 を得 る こ とが で きな くな る。 そ こ で,近 傍 分 割 並 列TabuSearchはTabuSearchの 近 傍 探 索 プ ロセ ス を並 列 化 す る こ と で探 索 時 間 を短 縮 す る もの で あ る。

この ア ル ゴ リズ ム で は,プ ロ セ ス 数p個 に お い て 探 索 す る近 傍 空 間N(x)を Nl(x),N2(x),...,!曽(x)に 分 割 し各 プ ロセ ス に割 り当 て る こ とで1プ ロ セ ス あ

た りの 探 索 す る 領 域 を制 限 す る こ とで,探 索 時 間 を 短 縮 す る。 これ は探 索 す る

メ タ戦 略 の 評 価 分 析 と並 列TabuSearchア ル ゴ リズ ム の 提 案 103 ブ ロ ック の ペ ア を各 プ ロ セ ス に 割 り当 て る こ と に よ っ て行 った 。

こ の ア ル ゴ リ ズ ム は 通 常 のTabuSearchと 同 様 に 全 組 合 せ に 対 して 探 索 を 行 うが,プ ロセ ス あ た りの 探 索 範 囲 が 限 定 さ れ る た め 探 索 量 を大 幅 に 削 減 す る こ とが で き る。 と くにTabuSearchで は交 換 対 象 ノー ドの 探 索 が 計 算 時 間 の も っ と も大 き な ウ ェ イ トを 占 め て お り,こ の部 分 の 改 善 は大 幅 な計 算 時 間 短 縮 を期 待 す る こ とが で き る。

7TokenPassing並 列TabuSearch

近 傍 分 割 並 列TabuSearchで はTabuSearchに お け る 近 傍 探 索 を並 列 化 し,計 算 時 間 の 短 縮 を試 み た もの で あ るが,確 か に 計 算 時 間 は 効 率 的 に縮 約 で き る が 解 の 質 は従 来 の 逐 次 的 なTabuSearchと 同 一 で あ る。 こ こ で提 案 す る ア ル ゴ リズ ム はTabuSearchを 基 礎 と し て高 度 に並 列 化 す る こ とで,探 索 時 間 の 短 縮,及 び さ らな る解 の 質 の改 善 を狙 う もの で あ る。

こ の ア ル ゴ リズ ム は 図2に 示 され る よ うに 割 り当 て を 管 理 す るTokenを 用 い て 問 題 を複 数 の 部 分 問題 に分 割 し,そ れ を各 プ ロセ ッサ に割 り当 て局 所 的 に TabuSearchに よ る探 索 を行 う もの で あ る。 さ ら にSuperMoveに よ っ て 集 合 的 な移 動 を行 い,生 成 され た 部 分 解 を各 プ ロ セ ッサ 間 で 互 い に 交 換 す る こ とで 完 全 解 を生 成 し整 合 を得 る 。 こ の種 の 問 題 を並 列 化 す る際 に 問 題 と な る の は, 分 割 方 法 と 同期 で あ る 。 近 傍 分 割 並 列TabuSearchで は近 傍 を分 割 し て探 索

を 分 散 させ る こ とで 計 算 時 間 は短 縮 す るが 解 の 質 は 逐 次 ア ル ゴ リズ ム と同 等 で あ る 。 並 列 環 境 にお い て解 の 質 を改 善 す るた め に は 複 数 の 探 索 を同 時 に行 う こ とで探 索 数 を 増 や す こ とが 求 め られ る 。 しか し,複 数 の 探 索 を行 う と複 数 の 解 が 生 成 さ れ,そ れ を 同期 させ 整 合 性 を 保 た な け れ ば な らな い。

以 上 の 問題 を解 決 す る た め に,こ の ア ル ゴ リズ ム で は,問 題 そ の も の を分 割 して 各 プ ロ セ ス に割 り当 て る も の と し,探 索 す る ブ ロ ック のペ ア を割 り当 て る が,こ の と きに プ ロ セ ス 間 で の 独 立 性 を高 め不 整 合 を防 ぐた め に 同 じ ブ ロ ッ ク が 複 数 の プ ロ セ ス に割 り当 て られ る重 複 を防 ぐ よ うに 割 り当 て る 必 要 が あ る 。

国

翫胤.↓ 圃

TabuSearch I.ocal

LoOP SuperMove

↓^{SubProblemAssign} 匝]

TabuSearch Local

LoOP SuperMove

×

図2:TokenPassingParallelTabuSearch

こ れ を 実 現 す る た め に,TokenPassingを 採 用 し た 。TokenPassingは Tokenと 呼 ば れ る配 列 を各 プ ロ セ ス 問 で 巡 回 させ る もの で あ る 。Tokenは ブ ロ ッ ク の 割 り当 て 情 報 を記 録 し,Tokenを 持 っ て い る プ ロセ ス だ け が ブ ロ ッ ク 割 り当 て を行 う権 利 を有 す る 。Tokenを 持 つ プ ロ セ ス はTokenに 記 録 され て い る割 り当 て 情 報 を参 照 し,割 り当 て られ て い な い空 きブ ロ ック を 予 約 す る。

こ の と き,Tokenに 割 り当 て 済 み の マ ー ク を し て か ら次 の プ ロ セ ス へ 送 信 す る 。 この 仕 組 み に よ り,各 プ ロセ ス 問 の ブ ロ ック割 り当 て の調 停 時 に重 複 を防

ぐ もの と した 。

各 プ ロ セ ス 間 の 解 の整 合 性 に関 して は,一 定 期 間 の探 索 を終 え た ら結 果 を 各 プ ロ セ ス に送 信 す る こ と で 整 合 性 を得 る も の と した 。 各 プ ロ セ ス はTokenか

ら得 た ブ ロ ッ クの ペ ア を 一 定 期 間探 索 し,そ の 間 移 動 した 頂 点 を記 憶 して お く。

探 索 終 了 時 に移 動 した頂 点 の 情 報 を各 プ ロセ ス に送 信 し,他 の プ ロセ ス は任 意 の 時 点 で 受 信 した 移 動 を 強 制 的 に行 う。 この と き,各 プ ロ セ ス に 割 り当 て られ

メ タ戦 略 の 評 価 分 析 と並 列TabuSearchア ル ゴ リ ズ ム の 提 案 105 て い る ブ ロ ック は独 立 した もの で あ り,重 複 は有 り得 な い た め,他 の プ ロ セ ス の 探 索 に は 全 く影 響 し な い。 この よ う に各 プ ロ セ ス が 非 同 期 で探 索 を行 う こ と で,同 期 タ イ ミ ン グ に と らわ れ な い 自由 度 の 高 い探 索 を行 う こ とが 可 能 と な る。

以 上 の よ う に 各 プ ロ セ ス は,Tokenの 取 得,ブ ロ ッ ク の 割 り当 て,探 索, 解 の 同 期,Tokenの 開 放 を 繰 り返 す こ とで 解 を収 束 させ て い く。 探 索 を他 の

プ ロ セ ス よ り先 に 終 え た 場 合 にお い て も,Tokenさ え 取 得 で きれ ば新 し い探 索 を他 の プ ロセ ス と非 同 期 に行 え る こ とが この ア ル ゴ リズ ムの 特 徴 で あ る。 こ の 方 法 で は,グ ラ フの ブ ロ ック 数 や 並 列 環 境 の プ ロ セ ス 数,ま た 各 プ ロ セ ス の 計 算 速 度 な ど に影 響 され ず に,か つ リソ ー ス をで きる だ け 有 効 に利 用 す る こ と が 可 能 とな る。 ま た,こ の 方 法 に よ っ て プ ロセ ス 間 で ブ ロ ック割 り当 て の調 停 を行 っ た場 合,各 プ ロセ ス は そ れ ぞ れ 完 全 に独 立 した 部 分 問 題 を持 つ た め,各 プ ロ セ ス上 で 異 な る戦 略 を取 る こ と もで きる 。 ま た,ブ ロ ック割 り当 て時 に 各 プ ロ セ ス が 持 つ 戦 略 に 最 も適 した ブ ロ ック ペ ア を各 プ ロセ ス の ポ リ シ ー に よ り 選 択 す る こ と も可 能 と な る。

今 回採 用 した 戦 略 は,い くつ か の 実 験 を行 っ た結 果 ラ ン ダ ム に ブ ロ ック を 割 り当 て 多 様 性 を 持 たせ,TabuSearchに よ っ て 短 時 間 で 収 束 させ る こ とが 最 も良 い 結 果 で あ っ た た め こ れ を採 用 し た 。 こ の 戦 略 の 特 徴 は,Tokenが 一 周 す る だ け の 割 り当 て しか 行 わ な い こ と で あ る 。 例 え ば,8ブ ロ ッ クの グ ラ フ で あ っ た場 合,そ の ブ ロ ッ ク のペ ア の 組 み 合 わ せ は28通 りあ るが,こ れ を4プ ロ セ ス で 探 索 した 場 合,4ペ ア の組 み 合 わせ しか 探 索 を行 わ ない こ と を示 す 。 探 索 範 囲 の 限 定 は解 の 質 を低 下 させ る原 因 と もな りう る が,こ の ア ル ゴ リズ ム で は 各 プ ロ セ ッサ で 局 所 的 に探 索 を 強 化 し,部 分 解 の生 成 を行 う こ とで解 の質 を 向 上 させ た 。

さ らに,各 プ ロ セ ス に お い て割 り当 て られ た ブ ロ ック の 探 索 を終 え,同 期 を 取 る ま え にSuperMoveを 行 っ た。SuperMoveは ブ ロ ッ ク 内 の あ る ノー ド

集合 を ま とめ て 交 換 す る もの で あ る 。 図3は そ の 一 例 で あ る。 まず2つ の ブ ロ ッ ク 内 か ら ノー ドを い くつ か 選 択 す る。 そ れ らの 各 ノ ー ドに接 続 され て い る エ ッ ジ の な か で 最 もエ ッ ジ コス トが 大 きい もの を1つ 選 択 し,'そ の先 に あ る ノ ー

Assignedblock1 Assignedblock2 図3:SupreMove

ドを選 択 す る 。 図 の例 だ と ノ ー ドaに 接 続 され て い るエ ッ ジで 最 もエ ッ ジ コ ス トが 大 きい エ ッ ジAを 選 択 し,そ の先 に あ る ノ ー ドbを 選 択 す る 。 こ の2つ の ノー ドと1つ の エ ッ ジ を1セ ッ トと し,ブ ロ ッ クか ら選 択 され た い くつ か の ノ ー ドに対 して この セ ッ トを生 成 す る 。 こ れ を2つ の ブ ロ ッ ク に対 して 行 っ た 後,生 成 さ れ た セ ッ トの 交換 で発 生 す る コス ト差 を計 算 す る 。 そ の 中 で 最 も コ ス トを改 善 す る セ ッ トの ペ ア を交 換 す る。

この 戦 略 は,例 え ば ノ ー ドaの み を 移 動 した 場 合,エ ッ ジAが 新 た に外 部 コ ス トと な るが,こ の コ ス トが 大 きい 場 合,ノ ー ドa及 び ノ ー ドb単 体 で は 移 動 しに くい こ と に な る。 そ こ で,ノ ー ドaとb及 び エ ッジAを ま と め て 他 の ブ ロ ッ クへ 移 動 させ る こ と に よ りエ ッ ジAを 外 部 コ ス トに す る こ と な く ノ ー ドを移 動 させ る こ とが 可 能 とな る 。 また,こ れ らの ノ ー ドを効 果 的 に選 択 す る た め に,ブ ロ ッ クか ら ノー ドを選 択 す る と きに 最 も移 動 回 数 の 少 な い ノー ドを 選 択 す る とい うTabu効 果 と は逆 の移 動 を促 進 す るた め の 選 択 を行 う戦 略 を 採 用 し た。 こ れ はLongtermMemoryを 用 い る こ とで 移 動 回 数 の 少 な い 頂 点 を 選 択 す る こ と に よ っ て 実 現 した。

図4に そ の ア ル ゴ リ ズ ム を 示 す 。4:=CatchToken(xt);は,Tokenを 取 得 し 解xtか ら 部 分 問 題 を 割 り 当 て る 関 数 で あ る 。 ま た,SendSubSolution(イ, q;q・1,2,...n,p≠q);は,プ ロ セ ッ サp上 で 生 成 し た 部 分 解4を 他 の プ ロ セ ッ サqへ 送 信 す る 関 数 で あ り,ReceiveSubSolution(x9,q=1,2,...,n,p≠q);は,

メ タ戦 略 の 評 価 分 析 と並 列TabuSearchア ル ゴ リ ズ ム の 提 案

t:=0;

xo:=InitialSolution;

repeat

x努:=CatchToken(Xt);

repeat

曜+1:=impTL(xg,TL);

TL:=TLU{xg}＼{ω 卜TL}

t:=t十1;

untilIocal‑100P SuperMove(xg);

SendSubSolution(xg,(1;q=1,2,...n,P≠9・);

x9=ReceiveSubSolution(ω2;q=1,2,̲n,p≠q);

xt:=SynchronizeSolution(xg;P=1,2,̲n);

untilstoP‑criterion

図4:TokenPassingParallelTabuSearch

ヱ07

プ ロ セ ッ サq上 で 生 成 さ れ た 部 分 解 κ7を 受 信 す る 関 数 を 意 味 す る 。Xt:=

SynchronizeSolution(イ;p=1,2,̲n);は 各 プ ロ セ ッ サpで 生 成 さ れ た 部 分 解 を整 合 し完 全 解 κ,を生 成 す る もの で あ る。

8並 列 実 験 結 果

実 験 に用 い た グ ラ フ は逐 次 ア ル ゴ リズ ム に用 い た もの と同 様 な グ ラ フ構 造 で あ る 。ま た,こ の 実 験 は近 傍 分 割 並 列TabuSearchで は2か ら4プ ロ セ ッサ の, TokenPassing並 列TabuSearchで は4プ ロ セ ッサ に よ る比 較 を行 っ た 。

並 列TabuSearchに お い て も,逐 次 ア ル ゴ リズ ム と 同様 に パ ラ メ ー タ を 適 切 に 設 定 しな け れ ば な らな い 。 こ れ も同 様 に事 前 の 数 値 実 験 に よ っ て設 定 を行 う。

近 傍 分 割 型TabuSearchはTabuSearchの 近 傍 探 索 部 分 の み を そ の ま ま 並 列 化 し た も の で あ る た め,必 要 な パ ラ メ ー タ は 通 常 のTabuSearchと 同 様 に TabuLengthの 設 定 が 必 要 で あ る 。 こ の 値 は 対 象 と す る 問 題 に 対 し て 適 切 に 設 定 し な け れ ば な ら な い 。 今 回 はSequencialと 同 様 に 予 備 実 験 に よ り20を 採 用 し た 。

TokenPassingに よ る 並 列TabuSearchに お い て は,通 常 のTabuLength な ど の パ ラ メ ー タ に 加 え て,ロ ー カ ル ル ー プ の 回 数 を 設 定 す る 必 要 が あ る 。 各 プ ロ セ ッ サ は ま ず ロ ー カ ル ル ー プ で 指 定 さ れ た イ テ レ ー シ ョ ン の 問,割 り 当 て ら れ た ブ ロ ッ ク に 関 し て,ロ ー カ ル でTabuSearchに よ る 探 索 を 行 う。 探 索 を 終 え た の ち に 通 信 を 行 い 部 分 解 を 合 成 す る 。 こ の ロ ー カ ル ル ー プ 数 は 短 す ぎ る と 部 分 解 の 合 成 の た め の 通 信 が 頻 繁 に 発 生 し,粒 度 が 細 か く な り全 体 の パ フ ォ ー マ ン ス が 低 下 す る 。 し か し な が ら,長 す ぎ る と 解 の 質 が 低 下 す る 傾 向 に あ る 。500ノ ー ド16ブ ロ ッ ク と1000ノ ー ド8ブ ロ ッ ク で 実 験 を 行 っ た 結 果,5が 最 良 で あ っ た た め5回 を 採 用 し た 。 ま たTabuLengthは 通 常 のTabuと 異 な

り,部 分 問 題 に 対 す る 長 さ で あ る た め,こ れ も 同 様 に 計 測 を 行 っ た 。 こ の 結 果, 2が 最 良 で あ っ た た め2を 採 用 し た 。

8。1近 傍 分 割 型 並 列TabuSearch

実 験 結 果 を 図5に 示 した 。SeqTSは 通 常 のTabuSearchで あ り,PTS‑2p は2プ ロ セ ッサ の,PTS‑4pは4プ ロ セ ッサ の 近 傍 分 割 型 並 列TabuSearch で あ る。 こ の ア ル ゴ リ ズ ム はTabuSearchの 近 傍 探 索 部 分 を並 列 化 した も の で あ り,解 の 質 はTabuSearchと 同一 で あ る た め,探 索 時 間 の み を示 した 。

この ア ル ゴ リズ ム で は近 傍 探 索 範 囲 を各 プ ロ セ ッサ に分 散 させ る こ とで 計 算 時 間 の 短 縮 を狙 う もの で あ るが,こ の 近 傍 探 索 範 囲 の 分 割 は ブ ロ ック の ペ ア単 位 で 行 われ る。2つ の ブ ロ ッ ク の組 み 合 わ せ 数 が 実 行 環 境 の プ ロセ ッサ 数 で 割 り切 れ る値 で あ れ ば,計 算 時 間 の 理 論 値 は1∠Processorで あ る。 今 回 は4プ ロ セ ッサ で 実 験 を 行 っ たが,計 算 時 間 は2プ ロ セ ッサ で 平 均1/1.63に,4フ.ロ セ ッサ で 平 均1/2.98に 改 善 され て い る 。 これ は並 列 処 理 特 有 の プ ロセ ッサ 問 通 信

メ タ戦 略 の 評 価 分 析 と並 列TabuSearchア ル ゴ リ ズ ム の 提 案 109

1200000

tOOOO.OO

800000

奮,。 。署 。。。

400000

200000

000

TabuSearchCalcTime

/「

/i

//ノ//…

/////

■ 「 ・5

1002003004005006007008009001000

Nodes 十SeqTS+PTS‑2p十PTS‑4p

図5:近 傍 分 割 並 列TabuSearchTime(sec)

等 の処 理 が 入 る た め,線 形 に 減 少 は しな い もの の比 較 的 に効 率 的 に 並 列 化 され て い る こ とが 確 認 で き る。TabuSearchの 近 傍 探 索 は 非 常 に 計 算 時 間 を要 す る処 理 で あ り,交 換 す る デ ー タ も非 常 に 少 ない こ とか ら,粒 度 が粗 く通 信 量 の 少 な い ア ル ゴ リズ ム で あ る とい え る。

8.2TokenPassing並 列TabuSearch

実 、験 結 果 を 表3に は100か ら500ノ ー ドの コ ス トを,表4に は600か ら1000ノ ー ド の コ ス ト を,ま た 表5に は100か ら500ノ ー ドの 計 算 時 間 を,表6に は600か ら1000ノ ー ド の 計 算 時 間 を 示 し た 。TSは 通 常 のTabuSearchで あ り,SA はSimulatedAnnealing,TP.TSはTokenPassing並 列TabuSearchで あ る 。

TokenPassing並 列TabuSearchに お い て は,SequencialTabuSearchと

比 較 し て,計 算 時 間,解 の 質 の 両 方 に お い て 改 善 が 認 め ら れ た 。 こ の ア ル ゴ リ ズ ム で は,近 傍 探 索 に お い て ブ ロ ッ ク の 組 合 せ を プ ロ セ ッ サ 数 に 限 定 す る 。 従 来 のTabuSearchの 全 探 索 で は8分 割 に 対 し て28通 り の ブ ロ ッ ク の 組 合 せ に

表3:ComputationakResultobtainedusingTS,SAandTP.TS(100‑500node)

Algorithm 100 200 300 ⁴⁰⁰ 500

TS

1

3812.0 16335.0 37710.0 68843.0 108055.0 SA AVG 3704.8 16269.6 37794.0 68968.8 108425.6 SA MIN 3687.0 16238.0 37744.0 68770.0 108302.0

SA

.

MAX 3734.0 16342.0 37879.0 69104.0 108526.0 TP,TS AVG 3787.2 16270.0 37645.0 68653.6 107607.6 TP.TS

I

MIN 3774.0 16219.0 37583.0 68520.0 107427.0 TP.TS

I

MAX 3801.0 16334.0 37706.0 68761.0 107761.0

表4:ComputationalResultobtainedusingTS,SAandTP.TS(600‑1000node》

Algorithm 600 700 800 900 1000

TS 157788.0 216037.0 284427.0 362989.0 448997.0

SA AVG

.

157643.2 216348.2 284325.4 362909.4 447511.0

SA MIN

.

157549.0 216155.0 284153.0 362369.0 447367.0

SA MAX 157880.0 216730.0 284828.0 363012.0 447840.0

TP。TS AVG 156887.2 215295.8 283407.8 361363.8 446172.0

TP.TS MIN 156746.0 215183.0 283134.0 361204.0 445922.0 TP.TS

I

MAX

1

156988.0 215356.0 283778.0 361571.0 446351.0

表5:ComputationalTimeobtainedusingTS,SAIandTP.TS(100‑500nodeXsec)

Algorithm 100 200 300 400 500

TS 7.25 93.66 423.36 1357.88 2210.26

SA 29.49 75.41 147.51 230.50 307.12

TP.TS 3.50 24.51 90.8 254.34 573.07

表6:Computational丁imeobtainedusingTS,SAandTP.TS(600‑1000nodeXsec)

Algorithm 600 700 800 900 1000

TS

1

4456.19 5797.71 7385.28 9205.00 10832.89

SA 385.80 464.98 548.88 628.17 700.38

TP.TS 1068.53 ^1100.84 2059.99 2659.27 3543.63

メ タ 戦 略 の 評 価 分 析 と並 列TabuSearchア ル ゴ リ ズ ム の 提 案 111 対 して 探 索 を行 うが,今 回 実 験 を行 っ た4プ ロ セ ッサ 上 で は4通 り組 合 せ に対 す る探 索 しか 行 わ な い もの で あ り,こ れ に よ っ て計 算 時 間 の 大 幅 な短 縮 を実 現 す る と と も に,有 効 な解 を 導 出 して い る の が 特 徴 で あ る 。 ま た,こ の探 索 は各 プ ロ セ ッサ 上 の ロー カ ル ル ー プ で 局 所 的 な探 索 が 複 数行 わ れ る こ とで 表3,4 よ り解 の 質 の改 善 が 確 認 さ れ,ノ ー ド数 が 少 な い もの を 除 い て,最 悪 値(MAX) で さ えSimulatedAnnealingを 凌 ぐ解 が 得 ら れ た 。 計 算 時 間 もSimulated Annealingに は 至 ら な い もの の,従 来 の 逐 次 的 なTabuSearchよ り大 幅 に 時 間 が 短 縮 さ れ 実 用 的 な 時 間 内 で 探 索 可 能 な 効 率 的 な並 列 ア ル ゴ リ ズ ム と 言 え る。

9お わ り に

グ ラ フ分 割 問題 に対 して基 本 的 な構 成 か ら な る各 種 メ タ戦 略 ア ル ゴ リズ ム を 構 成 し 数 値 実 験 に よ っ て 実 際 的 な 評 価 を 行 っ た。 そ の 結 果,GeneticAlg()‑

rithmは 本 問 題 の よ うな 組 合 せ 最 適 化 問 題 に対 して は良 い結 果 が 得 られ な か っ た。 一 方,SimulatedAnnealing,TabuSearchは 優 れ た 結 果 を 示 し,と く にSimulatedAnnealingに お い て は 解 の 質,計 算 時 間 と もに 他 の ア ル ゴ リズ ム を凌 ぐ結 果 を示 し,問 題 の サ イ ズ が 大 きい もの に対 して は 計 算 時 間 の 観 点 か ら SimulatedAnnealingが 最 も効 果 的 で あ る とい え る。 以 上 の実 際 的 な分 析 は応 用 分 野 に お け る利 用 に際 して の 有 効 な知 識 と な る で あ ろ う。

ま た,TabuSearchに お い て は そ の 性 質 上,多 大 な 計 算 時 間 を 要 した 。 そ こ で 新 た な 並 列 と い うパ ラ ダ イ ム を 組 み 込 ん だ 近 傍 分 割 型 の 並 列Tabu Searchを 提 案 し,TabuSearchに お い て 最 も計 算 時 間 を要 す る 近 傍 探 索 部 分 を各 プ ロセ ッサ に 分 散 させ る こ とで 効 率 的 な並 列 化 を 行 う こ と で計 算 時 間 を大 幅 に縮 約 す る こ とが で き た。 この 手 法 は 問 題 サ イ ズ に あ わ せ て プ ロ セ ッサ 数 を 増 加 させ る こ とで,計 算 時 間 を さ らに短 縮 す る こ と も可 能 で あ り,よ り大 きな 問 題 で も現 実 的 な 時 間 で 解 を 得 る こ と が で き る で あ ろ う。 さ ら に,Token Passingを 用 い た 問 題 分 割 型 の 並 列TabuSearchを 提 案 し,こ の ア ル ゴ リズ ム

に よ っ て 計 算 時 間 の 大 幅 な短 縮 を可 能 と し通 常 のSimulatedAnnealingを 凌 ぐ 解 を得 る こ とが で きた 。 この 手 法 で はTokenに よ っ て 並 列 計 算 環 境 に依 存 せ

ず に部 分 問 題 を割 り当 て る こ とを 可 能 と した 資 源 管 理 を考 案 し,プ ロ セ ッサ 数 や プ ロ セ ッサ 性 能 が 異 な る も の が混 在 す る シ ス テ ム にお い て もで きる だ け 効 率 的 に解 を得 る こ とを可 能 と した。 また,各 プ ロ セ ッサ に は完 全 に独 立 した 部 分 問 題 が 割 り当 て られ る た め,プ ロ セ ッサ 独 自 の戦 略 で 部 分 問題 を解 くこ と もで き,一 つ の 問 題 に対 して 様 々 な戦 略 を 複 数 同時 に 適 用 す る こ と も実 現 で き る。

同 時 に各 プ ロ セ ッサ に お い て 他 の プ ロ セ ッサ の状 態 に依 存 せ ず に非 同期 に 探 索 を 行 う こ と もで き る で あ ろ う。 こ の よ う に シス テ ム に 対 して柔 軟 な対 応 を 実 現 した こ と で,ワ ー ク ス テ ー シ ョ ンク ラ ス タ特 有 の ス ケ ー ラ ビ リテ ィ を生 か した ア ル ゴ リ ズ ム で あ る とい え る。

メ タ 戦 略 の 評 価 分 析 と並 列TabuSearchア ル ゴ リ ズ ム の提 案 113

参 考 文 献

[1]室 田 一 雄:離 散 構 造 と ア ル ゴ リ ズ ムIV,近 代 科 学 社,1995。

[2]斎 藤,三 十 尾,志 澤,丸 川,秋 山,野 口,鬼 塚:分 子 動 力 学 法 プ ロ グ ラ ム

AMBERとBarnes‑Huttreecodeの 並 列 化 に よ る 高 速 化,情 報 処 理 学 会 論 文 誌{

Vol。40,No.5,pp2142‑2151,1999.

[3]MPI:メ ッ セ ー ジ 通 信 イ ン タ ー フ ェ イ ス 標 準(日 本 語 訳 ド ラ フ ト), http://www.ppc.nec.co.jppi‑jndex.html,1996.

[4]藤 沢 克 樹,久 保 幹 雄,森 戸 晋:TabuSearchの グ ラ フ 分 割 問 題 へ の 適 用 と 実

験 的 解 析,T.IEEEJAPAN,Vol.114‑C,No.4,pp.430‑437,1994.

[5]RobertoBattiti,GiampietroTecchiolli:Parallelbiasedsearchforcombinato‑

rialoptimization:geneticalgorithmsandTABU,MicroprocessorsandMicrosy‑

stemsVol.16No.7,pp.351‑367,1992.

[6]SAULA.KRAVITS,ROBA.RUTENBAR:PlacementbySimulatedAnneal‑

ingonaMultiprocessor,IEEETRANSACTIONSONCOMPUTER‑AIDEDDE‑

SIGN,VOL.CAD‑6,NO.4,pp.534‑549,1987.

[7]C.‑NFiechter:Aparalleltabusearchalgorithmforlargetravelingsalesman problem,DiscreteAppliedMathematics51,pp243‑267,1994.

[8]MichelToulouse,TeodorG.Crainic,MichelGendreau:CommunicationIssues inDesigningCooperativeMulti‑ThreadParallelSearches,Meta‑heuristics:

theoryandapplications,KluwerAcademicPublishers,1996.

[9]荒 木,加 地,山 本,鈴 木,大 内:遣 伝 的 ア ル ゴ リ ズ ム に よ る 最 適 系 列 分 割 問

題 の 解 法,電 気 学 会 論 文 誌C分 冊,Vol.120‑C,No.2,pp.215‑221,2000.

[10]EmileAarts,JanKorst:SimulatedAnnealingandBoltzmannMachines, JOHNWILEY&SONS,1989.