ヒ ュ ー リス テ ィ ック手 法 にお け る解 析 と評 価

ヒ ュ ー リス テ ィ ック手 法 にお け る解 析 と評 価

加 地 太 一

1は じ め に

何 ヶ所 か の都 市 とそ の 都 市 間 の 距 離 が 与 え られ た と き,す べ て の都 市 を巡 り, 元 に戻 る最 短 の 道 順 を 求 め た い 。 この 問題 を計 算 機 科 学 の 世 界 で は 巡 回 セ ー ル ス マ ン 問 題(travelingsalesmanproblem,TSP)と 呼 ぶ が,す べ て の 可 能 な 道 順 を列 挙 して そ の 中 で 最 良 な 巡 回 路 を見 つ けれ ば解 け る わ け で あ るか ら,あ ま りに も単 純 で ナ ン セ ンス な 問題 と思 わ れ る だ ろ う。 と こ ろが,こ の ナ ンセ ン ス な 問 題 が 計 算 機 で も解 け な い 難物 中 の 難物 なの で あ る。 もち ろ ん,4都 市 な ら高 々6通 りの 道 順 しか な い の で,そ の 中 で 最 短 な巡 回 路 が 答 え で あ り,誰 で も簡 単 に解 け る 問 題 で あ る。 しか し,そ の都 市 数 が 増 えて い く と道 順 の数 が ど う な る か が,こ の 問 題 の ネ ック と な る の で あ る。 都 市 数 を π とす れ ば,出 発 点 か ら次 の都 市 へ の 行 き方 は(n‑1)通 りで あ り,さ ら に,そ の都 市 か ら次 の 都 市 へ の 行 き方 は(n‑2)通 り と考 え て い け ば,全 巡 回 路 の 数 は(n‑1)1 通 りと な る 。 こ れ は ス ター リ ン グ の公 式(n1・ ・〜雁(n/e)")に よ りほ ぼ 〆 通

り と表 す こ とが で き,都 市 数 の増 加 に よ り指 数 関 数 的 に す べ て の 可 能 な道 順 の 数 が 増 加 す る こ とが わ か り,こ れ を組 合 せ 的 爆 発 と呼 ぶ 。 た とえ ば,30都 市 の 一 つ の 巡 回 路 の コス トを 一秒 間 に1012(1兆)回 計 算 で き るス ーパ ー コ ン ピ ュ ー タ が 仮 に あ っ た 場 合,30都 市 の 全 部 の 巡 回路 の 数 は291=約8.8×1030個 で あ る の で,30都 市 のす べ て の 巡 回 路 を計 算 す る に は8.8×1018秒 か か る 。一 年 は3.15

×107秒 で あ る の で,30都 市 の 巡 回 セ ー ル ス マ ン問 題 の答 え を求 め る に は約2800 億 年(2.8×1011)年 もか か る こ と に な る。 す な わ ち,た か だ か,30都 市 を 計

〔91〕

92

算 す る の に 数 千 億 年,あ る い は 数 兆 億 年 とい う天 文 学 的 計 算 時 間 を要 して し ま う。

こ の よ うな 巡 回 セ ー ル ス マ ン問 題 な ど を は じめ とす る組 合 せ 最 適 化 問題 は 多 くの場 面 で 利 用 可 能 な 応 用 範 囲 の 広 い 問 題 で あ る 。 しか し,こ れ ら の 問 題 は NP困 難 な ク ラ ス に属 し,そ の 問 題 の大 き さ が 増 大 す る と必 要 とす る 計 算 時 問 は 指 数 関 数 的 に増 大 し,も は や 実 用 時 間 内 で計 算 が 困 難 な 問 題 と な っ て し ま う。

これ ら の 問 題 に対 して,二 つ の対 応 が 考 え られ る で あ ろ う。 一 つ は,探 索 領 域 を限 定 し計 算 時 間 の増 大 をお さ え る とい う考 え方 で あ る。 す な わ ち,洗 練 した 厳 密 解 法 の 開 発 で あ り,分 枝 限 定 法,動 的 計 画 法 な ど を基 盤 と した ア ル ゴ リズ ム が 提 案 さ れ て きた 。 しか し,こ の場 合,NP困 難 な組 合 せ 最 適 化 問 題 に対 し て は 実 用 時 間 内 で 解 け る問 題 の大 き さが 限 られ て くる の は避 け られ な い事 実 で あ る 。 そ こ で,も う一 つ の 考 え 方 と して,実 用 時 間 内 で そ れ な りの 解,す な わ ち 実 用 上 十 分 で あ る近 似 解 を も とめ 代 替 す る と い うア プ ロー チ に よ る近 似 解 法 が 重 要 な手 法 と な っ て くる。 特 に,近 年,メ タ ヒ ュ ー リス テ ィ ッ クス を 中 心 と した ヒ ュ ー リス テ ィ ッ ク手 法(heuristics,発 見 的 手 法)が 注 目を浴 び て お り, 多 くの パ ラ ダ イ ム,ま た は,そ れ ら を改 良,あ る い は ハ イ ブ リ ッ ド化 した種 々 の提 案 が な され て い る 。 逆 に,あ ま りに も多 くの手 法 が 提 案 さ れ るあ ま り,利 用 者 に と っ て は ど の手 法 が 有 効 で あ り,適 切 で あ る か 判 断 しに く くな っ て い る の も事 実 で あ ろ う。 また,評 価 手 法 は 当然,研 究 者 に と って も対 象 とす る 手 法 の 良 し悪 しに 対 す る科 学 的 な判 断 手 法 と して,あ る い は,ア ル ゴ リズ ム の特 性 分 析 な ど に お い て も欠 か す こ との で き な い 問 題 で あ ろ う。 そ の た め に も,扱 う 事 例 に対 す る 有 効 な手 法,及 び特 性 な どを客 観 的 に判 断 す る た め の ヒ ュ ー リス テ ィ ッ ク手 法 の 評 価 法 は 必 要 不 可 欠 な 問題 で あ る。 で は,そ の た め の 評 価 に お け る観 点 とは何 で あ ろ うか?た と え ば,前 述 の 厳 密 解 法 にお け る 評価 の観 点 は 主 に,ど の くらい の 問 題 が 解 け る か 。 か つ,ど の く らい 時 間が 必 要 か 。 とい う 点 が 上 げ られ よ う。 そ れ に対 して,ヒ ュ ー リス テ ィ ッ ク手 法 を含 め た 近 似 解 法 で の 評 価 の観 点 は大 まか に示 す と,

● 求 ま る 解 の 質(近 似 度)

ヒ ュ ー リ ス テ ィ ッ ク 手 法 に お け る 解 析 と評 価 93

● 計 算 に要 す る時 間

で あ る 。 ま た,厳 密 解 法 と ヒ ュ ー リス テ ィ ック 手 法 に言 え る こ と と して,頑 健 性,利 便 性 な ど もあ げ られ る で あ ろ う。

こ こで は,主 に 上 記 の解 の 質 と計 算 時 間 に着 目 し て分 析 評 価 の 論 議 を 進 め て い く。 ヒ ュー リス テ ィ ック 手 法 に お け る この2つ の 観 点 を 明 らか にす る た め の 解 析 方 法 と し て,理 論 的 解 析 と実 験 的解 析 の2通 りの 方 法 が取 ら れ る 。さ ら に, 理 論 的 解 析 で は大 き く分 け て 最 悪 値 解 析 と確 率 的解 析 が あ る 。 この3つ の 実 験 的 解 析,最 悪 値 解 析,確 率 的 解 析 の 問 に は違 い が あ る わ け で あ り,長 短 を もち, 万 能 な ツ ー ル で は な い 。 理 論 的 解 析 は 計 算 機 科 学 と と も に発 展 し,ア ル ゴ リズ ム,デ ー タ構 造 の研 究,開 発 に大 き く貢 献 した。 しか し,ヒ ュ ー リ ス テ ィ ッ ク 手 法 の 場 合,漸 近 的 に 最 悪 な ケ ー ス の振 舞 い を 明 らか にす る 最 悪 値 解 析 で は, 通 常 求 ま る 値 が 最 悪 値 よ りは るか に よい 場 合 が 報 告 され て い る 。 ま た,確 率 的 解 析 の 場 合,解 空 間 の モ デ ル を立 て,そ の 上 で の振 る舞 い を検 討 す る こ と に な る 。 この と きの モ デ ル は単 純 化 され た場 合 が 多 く,現 実 の 問題,特 定 さ れ た 問 題 な ど の検 討 に不 向 きで あ る場 合 が 多 い 。 そ れ らに対 して,実 験 的 な解 析 は 計 算 機 上 に ア ル ゴ リ ズ ム を実 現 し,そ れ を 実 際 に動 か す こ と に よっ て 得 た デ ー タ を 分 析 しア ル ゴ リズ ム の 性 能,特 性 を 明 らか にす る もの で あ る 。そ れ に よっ て, 現 実 に求 まる 値 に近 い 結 果 を得 る こ とが 可 能 と な る 。 しか し,方 法 論 の基 準 が 明確 で な い な ど の 問 題 に よ り信 頼 性 に乏 しい な どの不 評 もあ る 。 本 論 文 で は, 特 に 実 験 的解 析 の 問題 点 とそ れ に対 す る対 応 と な る指 針,お よび 理 論 的解 析 で あ る 確 率 的解 析 の可 能 性 を一 例 を も っ て示 す こ と とす る。

2ヒ ュ ー リ ス テ ィ ッ ク 手 法 と実 験 的 解 析

現 在 の ヒュ ー リス テ ィ ック手 法 は計 算 機 の 進 化 と と も に,大 規 模 で あ り,か つ,複 雑 な 問 題 を解 くこ と を可 能 と した 。 そ の ヒ ュ ー リス テ ィ ック 手 法 に対 す る 解 析 法 と して,実 験 的 な解 析 が 主 流 とな り広 が り を見 せ て い る 。 そ の理 由 と して,理 論 的 解 析 に よ る結 果 が 実 世 界 の ア ル ゴ リズ ム の 能 力 に つ い て 完 全 に示

94

す こ とが で き な い 点 が あ げ られ よ う。 そ れ に対 して,実 験 的解 析 は現 実 世 界 の 情 報 を リア ル に表 現 し,現 実 に 近 い 性 能 分析 を可 能 とす る こ と に よ り,実 質 上 の ア ル ゴ リズ ム の性 能 評 価 に お い て 欠 かせ ない もの と な っ た わ け で あ る 。 しか し,そ の分 析 にお い て は数 学 的 な 厳 密 性 が な い な ど理 論 家 に は好 まれ ず,ま た, そ の 解 析 の 基 準 が 整 っ て お らず信 頼 性 の お け な い結 論 につ なが っ て い る もの も あ る。 そ こ で,本 論 文 で はBarr[2],Johnson[6コ,[7コ,久 保[10]等

を参 考 に,実 験 的 解 析 が 科 学 的,か つ 客 観 的 な解 析 ・分 析 方 法 と し て十 分 取 り 扱 わ れ る た め の 検 討 を加 え て い きた い 。

2.1実 験 的 解 析 に お け る手 順

実 験 の 大 ま か な流 れ を以 下 の よ う な3つ の プ ロ セ ス と し て示 す 。 特 に,こ こ で は ヒ ュ ー リス テ ィ ッ ク手 法 の解 析 で の主 要 な 観 点 で あ る解 の 質 と計 算 時 間 に 着 目 して 考 察 して い る 。 た だ し,ヒ ュー リス テ ィ ック 手 法 の 研 究 にお い て 寄 与 す る 問 題,す な わ ち価 値 と認 め られ る着 目点 は解 の 質 と計 算 時 間 の2つ 以 外 に も,問 題 の特 性 な どに依 存 し な い頑 健 性,ア ル ゴ リズ ム を実 装 しや す い な どの 実 装 の 容 易 さ,広 い 問題 に対 して対 応 可 能 な 一 般 可 能 性,さ らに,斬 新 な ア イ デ ィア で あ る な どの ニ ュ ー ス 性 な どの 着 目す る点 は多 様 で あ り,逆 に こ の よ う な寄 与 す る見 方 の 多 様 さ も標 準 的 な 形 式 が 存 在 し な い 一 因 と な っ て い る。

(1)実 験 の 目的 を明 確 に す る 。

ま ず,実 験 で何 を 明 らか にす る か とい う問題 を定 め な け れ ば な ら ない 。 実験 とは特 定 の 目的 の た め コ ン トロ ー ル され た条 件 の 下 で の テ ス ト事 項 の 集 ま りで あ る 。 そ れ に よ り,あ るパ フ ォ ー マ ンス の評 価,特 性 の 論 証,仮 説 の 正 当性 の 検 討 な ど を行 う もの で あ る 。 そ こ で,実 験 で何 を明 らか に す るか を 設 定 す る こ とが 実 験 の プ ロ セ ス の 第 一段 階 とな る 。 今 回 の 着 目す る観 点 に対 して の 主 要 な 目的 は 主 に以 下 と な る。

● 異 な る ア ル ゴ リズ ム の 性 能 比 較

● ア ル ゴ リズ ム の挙 動

ヒ ュ ー リ ス テ ィ ッ ク 手 法 に お け る 解 析 と評 価 95

● パ ラ メ ー タ に対 す る分 析

異 な る ア ル ゴ リズ ム の 性 能比 較 は主 に,解 の質 と計 算 時 間 の2点 に お い て の 優 位 性 の比 較 と な る 。ア ル ゴ リ ズ ム の 挙 動 は そ の 問 題 事 例 の 大 き さ に対 す る変 化, 問 題 事 例 の ク ラ ス に対 して の 挙 動 の 変 化 を通 して,ア ル ゴ リズ ム の 特 性 を把 握 す る。 また,ヒ ュ ー リス テ ィ ッ ク手 法 で はパ ラ メ ー タ の設 定 に よ っ て大 き くそ の 性 能 は 変 化 す る 。 そ こ で,パ ラ メ ー タ に対 す る 分 析 に よ り最 善 な設 定 値 を導 出 す る。 あ る い は頑 健 性 を 明 らか にす る こ と とな る。

(2)実 験 の デ ザ イ ン と実 行

次 に,実 験 方 法 をデ ザ イ ン し実 行 に 移 す わ け で あ る。 そ の 実 験 方 法 と して は 大 き く2つ に分 け られ る。 一 つ は競 争 的 実 験 で あ り,も う一 つ は 分 析 的 実 験 で あ る。 競 争 的 実 験 は ア ル ゴ リズ ム の優 位 性 を検 証 す る も の で あ り,同 じ問 題 の ク ラス に対 し て,異 な る ア ル ゴ リズ ム の パ フ ォー マ ンス を比 べ る こ とを責 務 と す る。 こ こで は,ア ル ゴ リズ ム お よ び プ ロ グ ラ ム,対 象 とす る問 題 を特 定 し準 備 しな け れ ば な らな い 。 そ して,ア ル ゴ リズ ム の挙 動,影 響 す る フ ァク ター, パ ラ メ ー タの 分 析 な どの 特 性 を明 らか に す るの が 分 析 的 実 験 に 当 た る。 た と え ば,解 の 質,計 算 時 間,あ る い は ロバ ス ト性 な どの ト レー ドオ フの 関係 を明 ら か にす る 。 ア ル ゴ リズ ム の性 能 に寄 与 す る 複 数 の フ ァ ク タ ー の 組 合 せ を認 識 す る 。 さ ら に,問 題 の 大 きさ に対 して の ア ル ゴ リズ ム の 性 能 の 変 化 な どを 明 らか に す る こ と は重 要 で あ ろ う。ま た,ヒ ュ ー リス テ ィ ッ ク手 法 で は 複 数 の パ ラメ ー タ に よ っ て ア ル ゴ リズ ム を制 御 す る た め,適 正 なパ ラ メ ー タ値 の 導 出,各 パ ラ メ ー タ の組 合 せ に よ る影 響 な ど を明 らか に す る こ とが 主 眼 とな る 。

(3)デ ー タ分 析 と結 果 の レポ ー ト

実 験 的解 析 に お け る最 後 の ス テ ップ で は 最 終 的 に 集 め られ た デ ー タ を客 観 的 に分 析 し,詳 細 な結 果 の 報 告 を し な け れ ば な らな い 。 こ こ で は,実 験 で集 め ら れ た デ ー タ を,分 析 の 目的,提 示 さ れ た 質 問 に対 して の 意 味 あ る 情 報 に変 えね ば な らな い 。 そ の た め に,統 計 的 な評 価,あ る い は 説 得 力 を生 む グ ラ フ ィ カル

96

な 表 示 は欠 か せ な い で あ ろ う。 さ ら に,次 の レポ ー テ ィ ン グ に お い て は,そ の 実 験 に科 学 的根 拠 を持 た せ る 内容 と し て表 現 し な け れ ば な ら な い。 そ の た め に は,ま ず 何 を お い て も,結 果 の再 現 性 を可 能 とす る ドキ ュ メ ン トに心 が け な け れ ば な らな い で あ ろ う。

2。2評 価 測 度

実 験 にお け る 重 要 な もの の 一 つ と して,実 験 の 目的 に対 して の性 能 を分 析 で き うる 評 価 測 度 の 問 題 が あ る。 今 回 前 述 した 目的 に対 す る科 学 的,か つ,客 観 的評 価 の た め に,ア ル ゴ リズ ム のパ フ ォ ー マ ンス を計 る測 度 を定 義 しな けれ ば な らな い 。 こ の パ フ ォ ー マ ンス に対 す る測 度 は,解 の質,計 算 時 間 に 対 して考 え ね ば な らな い の で,こ の2点 に 関 す る評 価 測 度 の 基 礎 的 な 知 識,定 義 な どを 示 した い 。ま た,今 回 は そ の 他 の評 価 項 目 は取 り上 げ な い 方 針 で 進 め て い るが, 頑 健 性 に 関 して は 問 題 の ク ラス な ど多 様 な 問題 を実 験 す る 過 程 で 評 価 項 目 と し て 避 け られ な い事 項 で あ る の で,頑 健 性 につ い て は簡 単 に 記 し て お く。

2.2.1解 の 質

ヒ ュ ー リス テ ィ ッ ク手 法 で は如 何 に 最 適 解 に 近 い 近 似 解 を求 め る か が 一 つ の 課 題 とな る。 求 ま る解 の 良 し悪 し,す な わ ち,最 適 解 へ の 近 さ を,解 の 質 と一 般 的 に 言 い,最 適 解 に近 け れ ば 解 の 質 は よい,そ う で な け れ ば,解 の 質 は悪 い,

と慣 習 的 に い う。解 の質 の 善 し悪 し を数 値 的 に 表 す 方 法 と して,絶 対 誤 差 と相 対 誤 差 が あ る。 そ れ ぞ れ,以 下 の よ う に定 義 さ れ る。

絶 対 誤 差:!(κ)一 ノ(κ') 相 対 誤 差:(八 κ)一∫(κり)が(κノ)

こ こで は κ は 求 ま っ た 近 似 解 で あ り,κ'は 最 適 解 で あ る 。 また,∫ は解 κの コ ス トを表 す 目的 関 数 で あ る 。この 相 対 誤 差 を利 用 す れ ば,き わ め て,数 値 的, 客 観 的 に 分 析 で き る わ け で あ るが,測 度 を計 算 す るた め に必 要 な最 適 解 が,対 象 と して い るNP困 難 な 問 題 で は 知 られ て い な い場 合 が 多 く,実 際 上 利 用 で き

な い ケ ー ス が 多 い わ け で あ る 。 ま た,最 適 解 が 知 られ て い な くて も,巡 回 セ ー

ヒ ュ ー リ ス テ ィ ック 手 法 に お け る 解 析 と 評 価 97

2.2.2計 算 時 間

実 験 的解 析 の 場 合,実 際 の 測 定 さ れ た 計 算 に か か る時 間 を も っ て測 度 と して い る。計 算 時 間 は計 算 環 境 とそ の 実 装 の仕 方 に大 き く依 存 す る値 で あ り,か つ, 計 算 過 程 に お け る さ ま ざ ま な 要 因 を集 約 した 結 果 生 じた 値 で あ る。 ち な み に, 計 算 環 境 で はCPUの ス ピー ド,メ モ リー サ イ ズ,コ ンパ イ ラ ー な ど,ま た, 実 装 の 仕 方 で は デ ー タ構 造,ア ル ゴ リズ ム,パ ラ メ ー タ,コ ー デ ィ ン グ の技 量 な ど多 くの フ ァク ター が 影 響 す る。 した が っ て,計 算 の 時 間 は ア ル ゴ リズ ム の 振 る舞 い に対 す る解 析 に は 向 か な い 値 で あ る こ とは 事 実 で あ る 。 ま た,ヒ ュ ー リス テ ィ ッ ク 手 法 は多 くの フ ェ ー ズ か ら な る 。 た と え ば,初 期 解 を見 つ け る フ ェー ズ,計 算 の入 力 の フ ェ ー ズ,デ ー タの 前 処 理 な どの フ ェ ー ズ か らな り, 実 質 ヒ ュ ー リス テ ィ ッ クス を動 か す 場 合,こ れ らの処 理 に多 くの負 担 を要 す る 場 合 が あ り,決 して解 を導 出 す る に 当 た り無 視 す べ き時 間 で は な い と考 え る 。 そ こで,ア ル ゴ リズ ム の 正 当 な 評 価 と して,計 算 時 間 で は入 力 処 理 お よ び前 処 理 な ど の時 間 を含 め終 了 ル ー ル に よ る ア ル ゴ リズ ム の 終 了 ま で の 時 間 を もっ て 比 較 す る こ とが も っ と も望 ま しい で あ ろ う。 現 実 の リア ル な値 を重 視 す る 実験 的解 析 に お い て は,実 際 に そ の 手 法 を もっ て ど の く らい の 時 間が か か る の で あ る か とい う 点 で 比 較 す る こ とが 他 の ア ル ゴ リズ ム との優 劣 を示 す と き に お い て は フ ェ ァ ー で あ る とい う考 え で あ る。 た だ し,お の お の の フ ェ ー ズ の 時 間 に 着

98

目す る場 合 は そ れ らの フ ェ ー ズ の 内 容 を 明記 す べ きこ と も忘 れ て は な ら な い 。

2.2.3頑 健 性

頑 健 性 は広 い 範 囲 の 問 題 に対 して の 適 用 可 能性 を意 味 す る。 す な わ ち,問 題 事 例 の 特 性 に よ っ て,計 算 時 間 と解 の 質 が 大 き く変 わ らず,安 定 した 結 果 を導 き出 す こ とを 言 う。 ま た,パ ラ メ ー タの 変 動 に対 して,安 定 した結 果 を導 き出 す こ と を も頑 健 性 を表 す もの の一 つ で あ る。 これ らは,多 様 な事 例 に対 して上 記 の値 な ど測 度 の 変 化 を も って 比 較 検 討 す る こ と と な る 。

2.3評 価 測 度 に 対 す る 影 響 要 因

ヒュ ー リ ス テ ィ ッ ク手 法 で の 実 験 的 解 析 で は 多 くの 自由 度(裁 量)を もつ 。 た とえ ば,問 題 事 例 の 選 択,ア ル ゴ リズ ム の実 装,計 算 機 環 境 評 価 測 度 の選 択,ア ル ゴ リズ ム の オ プ シ ョン,結 果 の 記 述 な どで あ る 。 これ らの選 択 は実 験 結 果 に 大 き く影 響 を与 え,実 験 の構 成 上,考 慮 し な け れ ば な ら な い重 要 な部 分 で あ る 。 ち な み に,主 要 な 評 価 項 目で あ る解 の 質 と計 算 時 問 に影 響 す る主 な要 因 は以 下 の3つ の 事 項 につ い て 存 在 す るで あ ろ う。

● 問 題 事 例

● アル ゴ リズ ム

● 計 算 機 環 境

そ れ ぞ れ の 要 因 を細 分 化 す る と,問 題 事 例 で は,問 題 サ イ ズ,次 元,構 造,ウ ェ イ トお よ びエ ッジ コス トな どの 分 布 な どが あ げ られ る で あ ろ う。さ ら に,ヒ ュ ー リス テ ィ ッ ク手 法 の ア ル ゴ リズ ム の構 成 を考 え る と,そ れ は種 々の フェ ー ズ か ら構 成 され 多 様 な 選 択 モ ジ ュー ル を 要 して い る 。 た と え ば,初 期 解 の 生 成 部, 近 傍解 の 生 成 部 な ど多 くの 部 品 か ら成 り立 っ て い る わ け で あ る。 そ こ で,各 フ ェ ー ズ で 扱 うア ル ゴ リズ ム,ヒ ュ ー リス テ ィ ッ クス の選 択 に よ りそ の性 能 は 異 な っ て くる。 また,プ ロ グ ラマ ー の 技 量,プ ロ グ ラ ム コー ドの 違 い な どか ら も計 算 時 間 な どは 大 き く影 響 し て くる 。 さ らに,ヒ ュ ー リス テ ィ ック手 法 は多 くのパ ラ メ ー タ に よ っ て制 御 さ れ,そ れ らのパ ラメ ー タ値,そ れ らの組 合 せ に

ヒ ュ ー リス テ ィ ッ ク 手 法 に お け る解 析 と評 価 99

この よ うな 多 くの 自由 度 が 実験 的 解 析 に お け る基 準 を作 りづ ら く して い る 大 き な原 因 で もあ ろ う。 実 験 者 は これ らの要 因 を分 類 し,そ の 中 で,問 題 の サ イ ズ,手 法 な どの 調 査 に 関 係 す る 要 因,問 題 の ク ラ ス,終 了 基 準,計 算 環 境 な ど の 固 定 す る 要 因,そ して,実 際 に 影 響 しな い 無 視 で き う る要 因 を区 分 し実 験 の 体 系 性 を整 え る こ とが 必 要 とさ れ る。

2.4問 題 点 と対 策

ヒュ ー リス テ ィ ック手 法 を評 価 す る と き,科 学 的,か つ 客 観 的 に解 析 を進 め て い か な け れ ば な らな い 。 しか し,現 状 で は 必 ず し もそ うで な い論 文 も散 見 さ れ る。 そ の主 要 な 原 因 は 前 述 で示 した よ うに,ヒ ュ ー リス テ ィ ック 手 法 の評 価

にお い て は,多 くの 自由 度 が あ る とい う と ころ に起 因 す る 。 た とえ ば,問 題 事 例 の選 択,ア ル ゴ リズ ム の 実 装,計 算 環 境,評 価 測 度 の 選 択,ア ル ゴ リズ ム の オ プ シ ョ ン(パ ラ メ ー タ な ど),そ して,レ ポ ー トの 記 述 な ど多 くの 部 分 で 実 験 者 の 裁 量 に まか せ られ て い る わ け で あ る。これ らは 実 験 に重 要 な 影 響 を与 え, これ らの 扱 い方 に よ り結 果 を大 き く左 右 す る わ け で あ る 。 そ こ で,実 験 的 解 析 を行 うに あ た り,次 の5つ の 事 項 か らそ の 問題 点 を探 り,そ れ に対 す る対 応 の 考 察 を加 え て い きた い 。

●●●●●

評 価 測 度 取 り扱 う問 題 ア ル ゴ リズ ム 計 算 機 環 境 分 析 と レポ ー ト

まず,評 価 測 度 は 多 数 の要 因 を原 因 と して 起 こ る 帰 結 で あ り,そ の 帰 結 で あ る 評 価 測 度 が か か え る 問 題 と対 策 を示 す 。 次 に,評 価 測 度 に 影響 を及 ぼ し,多 く の 自 由度 を有 す る 側 で あ る取 り扱 う 問 題,ア ル ゴ リズ ム,計 算 機 環 境 につ い て

ヱ00

検 討 す る。 最 後 に,最 終 的 に得 られ た 結 果 を い か に取 り扱 うか で そ の結 論 の と らえ 方 も変 わ っ て くる。 そ こ に も多 くの 自 由度 が存 在 し,科 学 的 な結 論 か ら逸 脱 す る 原 因 を秘 め て い る分 析 と レ ポ ー トの 検 討 を加 え て お く こ と とす る 。 た だ し,こ れ ら の各 項 目で 述 べ られ る こ とは 互 い に相 容 れ,体 系 づ け に くい 部 分 で も あ り,一 般 的 な 結 論 と して 示 しづ らい こ とは避 け ら れ な い と考 え て い る。

2.4.1評 価 測 度

解 の質 と計 算 の負 担 で 必 要 とす る求 め た 解 の値 と計 算 時 間 の 実 測 値 は あ ま り に も多 くの 要 因 に 支 配 され た結 果 で あ る 。 求 め た解 の 値 は 問題 事 例 や ア ル ゴ リ ズ ム の多 くの フ ァク ター に影 響 さ れ,計 算 時 間 は さ ら に計 算 環 境 の フ ァ ク タ ー に も影 響 され る で あ ろ う。 解 の 質 と計 算 時 間 の 両 者 に言 え る こ と と して,そ の 要 因 の 多 さは 客 観 的 評価 を 困 難 と させ る 原 因 で もあ り,ま た,固 定 化 した い 要 因 で あ る計 算 環 境 に 大 き く依 存 す る計 算 時 間 は ア ル ゴ リズ ム の 特 性 を推 定 す る に は 不 向 きな 値 で あ る 。 さ らに,解 の 質 と計 算 時 間 は トレ ー ドオ フの 関係 にあ り,こ れ らの 調 整 に 関 す る枠 組 み の 前 提 な しで は議 論 で き な い 問 題 で もあ る。

詳 細 は各 項 目で 後 述 す る とす る が,ま ず,そ の よ うな 数 値 に客 観 性 を持 た せ る に は,実 験 の 目 的 に合 わ せ て影 響 を与 え る 要 因 を体 系 化 した統 一 環 境 が 必 要 と な る。 しか し,影 響 す る要 因 の 多 さ は統 一 環 境 を前 提 とす る こ と事 態 を難 し く して い る の も事 実 で あ る。 す べ て の 要 因 に わ た り統 一化 す る こ とは 不 可 能 で あ り,か つ,必 要 も な い で あ ろ うが,再 現 性 を確 保 し,再 度 の実 験 で の 検 証 で も 同 様 な結 果 が 得 られ る よ う な環 境 を作 り上 げ る こ とに 心 が け るべ きで あ ろ う。

両 者 に い え る も う 一 つ の 問 題 は,解 の値,計 算 時 聞 の 実 験 値 の み で は全 体 と して の 相 対 的 な 情 報 は 薄 れ ざ る を得 な い の は 致 し方 な く,本 来,実 験 値 そ の も の 自体 で は比 較 検 討 に 向 く値 で は ない 。 解 の 質 で は,ベ ンチ マ ー ク 用 の 問題 な どで す で に最 適 解 が 知 られ て い る場 合 は,相 対 誤 差 を利 用 し よ り客 観 的 比 較 が 行 え,よ り科 学 的 な比 較 分 析 な どが 行 え る 。 しか し,そ れ 以 外 の場 合,よ り客 観 性 を維 持 す る ドキ ュ メ ン トの必 要 が 求 め られ るで あ ろ う。 計 算 時 間 で は個 人 的 な レベ ル で 実 験 比 較 す る場 合 は,実 験 者 が用 意 す る統 一 され た計 算 環 境 内 で

ヒ ュ ー リス テ ィ ッ ク 手 法 に お け る解 析 と評 価

行 え ば,い くつ か の フ ァ ク ター に影 響 され る誤 差 を含 み なが ら も限 られ た 範 囲 で の 客 観 性 が 得 られ るで あ ろ う。 しか し,多 くの参 加 者 な どを要 し,全 体 を見 渡 す こ とが 可 能 な大 規 模 な実 験 とい う の が 今 後 の ヒュ ー リ ス テ ィ ッ ク手 法 の 実 験 的 解 析 に は 欠 か せ な い 。 こ の 場 合,計 算 機 環 境 の 統 一 性 を取 る こ と 自体 が 困 難 な事 項 で あ る。 そ こで,あ る 計 算 機 を基 準 と し,そ の 計 算 機 の 計 算 時 間 に 換 算 し標 準 化 した 時 間 を代 用 す る 方 法 が 有 効 で あ る。 さ ら に,計 算 時 間 そ の もの を使 用 す る の で は な く,探 索 数,デ ー タ構 造 へ の更 新 数 な ど,時 間,負 担 に 相 関 す る指 標 を 用 い る こ と も あ る 。 これ らは プ ロ グ ラ ム ス キ ル,計 算 環 境 な どの 要 因 に は影 響 せ ず,漸 近 的 な特 徴 を得 る に は 有 効 で あ ろ う。

2.4.2取 り扱 う問 題

テ ス トす る た め の 問題 事 例 は,実 問 題 か らの 選 ば れ た 問 題 事 例,あ る い は事 例 を生 成 す る プ ロ グ ラ ム に よ る 問 題 事 例 な ど に よ っ て用 意 さ れ る 。 実 世 界 の 問 題 は ヒ ュー リス テ ィ ック 手 法 の最 終 的 目的 で あ り,そ の 効 果 を示 す こ と は究 極 の 目的 で あ ろ う。 ま た,特 定 な特 性,性 質 を分 析 す る た め に,そ れ を調 査 す る た め の 問 題 を作 り出 す こ と も重 要 で あ ろ う。しか し,現 実 的 な問 題 とか け離 れ, 極 端 に 難 し い 問 題 は避 け るべ き で あ る。 ま た,問 題 の サ イ ズ にお い て は,小 さ

な 問題 の 場 合,ア ル ゴ リズ ム の特 性 が 表 に 出 て こ な い もの で あ り,可 能 な 限 り 大 きな 問 題 を扱 う こ とに よ っ て,ア ル ゴ リズ ム の 振 舞 い,特 性 が 明 らか に な る も の で あ る。 そ こで,ど の よ う な 問 題 事 例 を扱 うか 。 とい うの が ひ とつ の 課 題 と な る わ け で あ る 。 実 験 者 は 当 然,い い 結 果 を 出 そ う と して,期 待 す る結 果 と 特 性 を 導 出 で き う る こ とを 望 む わ け で あ る。 こ こで,そ れ らの 結 果 を 強 調 した い た め に特 定 の 問 題 事 例 に偏 る実 験 を 行 い が ち と な る。 当 然,限 られ た 問 題 か ら普 遍 性 の あ る 結 論 は導 か れ に くい し,一 般 性 につ い て は 結 論 を下 せ な い で あ ろ う。

普 遍 性 の あ る 結 論 を導 くた め に,で き う る 限 り広 範 囲 な デ ー タ を取 り扱 い, 全 体 に わ た る 問 題 の 難 し さ を調 査 す る こ とが 重 要 な観 点 とな る。 す な わ ち,問 題 の ク ラス と 問 題 の サ イ ズ に対 して多 様 な観 点 で 望 ん で ほ しい 。 ま た,テ ス ト

ヱ02

問 題 を広 く調 査 す れ ば,ス トレス の あ る問 題,限 界 な ど興 味 の あ る もの が 得 ら れ,さ ら な る研 究 へ の 進 展 と な る。 もち ろ ん,そ の た め に は 幅 広 い 問 題 に対 す

るベ ンチ マ ー ク 問 題 の 整 備 は不 可 欠 で あ る。 そ の様 な もの が 充 実 す る こ と に よ り,よ り普 遍 性 の あ る結 論 と相 対 的 な 関 係 な どが 導 き 出 され る も の と考 え る。

た だ し,新 しい 問 題,あ る い は 新 しい 手 法 な どの レベ ル で は標 準 的 な 問 題 を対 象 とす る こ と に よ り,今 後 の展 開 の 土 台 を築 き,ま た,特 定 な ケ ー ス を 対 象 と す る と きは 全 体 の 中 の 位 置 づ け を示 して い た だ きた い もの で あ る。

2.4.3ア ル ゴ リズ ム

ヒ ュ ー リス テ ィ ッ ク手 法 は多 くの モ ジ ュー ル か ら構 成 さ れ て い る こ とは す で に 述 べ た 。す な わ ち,各 段 階 で 使 用 す る ヒ ュ ー リス テ ィ ッ クス,近 傍 構 造,デ ー タ構 造 な ど多 くの 選 択 の 余 地 が あ り,ヒ ュ ー リ ス テ ィ ッ ク手 法 は 多 くの 戦 略, パ ラ メ ー タ を含 む た め,各 種 各 様 の 選 択 が 迫 られ,そ の 採 用 の 違 い に よっ て 異 な る タ イ プ と な る。 した が っ て,同 一 名 の ヒ ュ ー リス テ ィ ック 手 法 で も,極 端 に 言 え ば そ の 性 質 は異 な っ て くる 場 合 が生 じ,あ る 意 味 で は無 限 に近 い 手 法 が 実 現 可 能 とな る。 そ の よ う な組 合 せ の多 さ は,一 般 的 な結 論 を 導 き に く くす る 原 因 の 一 つ で あ ろ う。 また,ア ル ゴ リ ズ ム の 細 部 に わ た る点 で の 不 明 確 さ は, 客 観 的 な位 置 づ け の結 論 を 出 し に くい現 状 を生 む で あ ろ う。 さ ら に,ア ル ゴ リ ズ ム の 実 現 に 対 して,コ ー デ ィ ン グ,プ ロ グ ラマ ー の技 量 な どが 大 き く影 響 す る 。 ま た,パ ラ メ ー タの チ ュ ー ニ ン グ に よっ て も結 果 は 変 化 す る 。 特 に,解 の 質 と計 算 時 間 は トレー ドオ フ の 関 係 に あ り,パ ラ メ ー タの 調 整 次 第 で 実 験 結 果

と して 好 ま しい 値 を導 くこ と も可 能 で あ ろ う。

こ こで 述 べ る こ とは多 分 に レポ ー トに 関 す る こ と とあ い 重 な る が,細 部 に わ た る事 項 に 関 し て 明確 化 し再 現 性 を与 え る こ と は複 数 の 要 因 か ら起 因す る 評 価 測 度 の 結 果 に 関 す る情 報 を 明確 化 し,よ り客 観 的 な判 断 へ と導 く もの で あ る の で,こ こ で 記 して お く。 さ て,ま ず これ らの 問 題 に対 して,ア ル ゴ リズ ム を構 成 す る モ ジ ュ ー ル な ど につ い て の 詳 細 な報 告 が 望 ま れ る 。 そ れ に よ り,そ の ア ル ゴ リ ズ ム の 位 置 づ け が 明 確 に な るで あ ろ う。 ま た,対 比 ア ル ゴ リズ ム に お い

ヒ ュ ー リ ス テ ィ ッ ク 手 法 に お け る 解 析 と評 価

て も,プ ロ グ ラム を洗 練 し,パ ラ メ ー タ の チ ュ ー ニ ング は 欠 か せ な い 。 そ の 結 果,初 め て客 観 的 な結 論 が 見 出 さ れ る も の で あ る 。 ま た,今 後 の 研 究へ の 寄 与 に お い て も,最 終 結 果 を 示 す だ け で な く,各 種 の 戦 略 の結 果 に対 す る 寄 与,お よ び そ の 原 因 の検 討 に 関 して レ ポ ー トす る こ とは 重 要 で あ ろ う。 読 者 は む し ろ そ ち ら に 関心 が あ り,戦 略 の 寄 与,そ れ らの ア ル ゴ リズ ム 上 の 計 算 負 荷 な ど は ア イ デ ィ ア を触 発 し,さ ら な る研 究 の 一 助 とな る に違 い な い 。 さ らに,各 種 ア ル ゴ リズ ム の体 系 的 な分 類 に も とつ い た 比 較 検 討 は よ り客 観 的 な デ ー タ を提 示

して くれ る で あ ろ う。

さ らに,パ ラ メー タ の 問 題 を考 え ね ば な らな い 。 ヒ ュ ー リス テ ィ ック ス 手 法 は 多 くの パ ラ メ ー タ に よ っ て 制 御 さ れ る わ け で あ る が,そ の パ ラ メ ー タ の チ ュ ー ニ ング に は多 くの 時 間 が 費 や され る もの で あ る。 そ の パ ラ メ ー タの 推 奨 値 に い た る過 程 とそ の選 択 の 理 由 な ど も読 者 は 興 味 が あ る もの で あ り,レ ポ ー トす べ き事 項 で あ ろ う。 チ ュー ニ ング にお い て,も う一 つ 言 え る こ とは 解 の質 と計 算 時 間 の トレー ドオ フ を ど う捉 え るか で あ ろ う。 どの 点 で 折 り合 い をつ け た か に つ い て は 論 じて い た だ け れ ば あ りが た い 。

ア ル ゴ リ ズ ム の 実 験 的解 析 に お い て,パ ラ メ ー タ の推 奨 値 を 固定 させ た 上 で 行 う,あ る い は,パ ラ メ ー タ 自動 設 定 モ ジ ュ ー ル を組 み 込 む 形 式 で,パ ラ メ ー タ の チ ュー ニ ン グ な しで 実 験 に移 れ る方 法 が大 規 模 な ヒュ ー リス テ ィ ッ ク手 法 の競 争 的 実 験 で 使 用 され て い る[6]。 パ ラ メ ー タ の 固 定 化,あ る い は 自動 計 算 化 で,チ ュ ー ニ ン グ な どの 重 い処 理 は省 か れ,事 例 に対 す る扱 い 方 は 統 一 化 さ れ,テ ス ト環 境 と して 公 平 化 さ れ る。 ま た,実 用 的 観 点 か ら,パ ラ メ ー タ の チ ュ ー ニ ン グ とい う経 験 的 要 素 が 強 い 処 理 は極 力 利 用 者 に負 わ せ るべ きで な い こ とは 事 実 で あ る。 た だ し,問 題 事 例 に対 して,異 な っ た パ ラ メ ー タ を使 用 す る と き は,そ の 点 につ い て 記 す 事 を忘 れ て は な ら な い。

2.4.4計 算 機 環 境

計 算 環 境 に お い て は 以 下 の 多 くの 要 因が 評 価 測 度 で あ る計 算 時 間 に 主 と して 影 響 す る。

104

●

●

●

商 学 討 究 第57巻 第1号

まず,実 験 に あ た り,

らな い 。 そ の上 で,実 験 の 目的 と照 ら し合 わ せ て,強 く影 響 す る 要 因 の 固定 化 が 望 まれ る。限 られ た範 囲 内 で,こ れ らの 要 因 の 固 定 化 は 可 能 な こ とで あ るが,

レ ポ ー トにお い て そ の実 験 環 境 の不 明確 さが 多 数 見 られ る場 合 が あ る 。 そ れ に よ り,計 算 機 時 間 に お け る 客 観 的判 断 の 困難 さ を生 む で あ ろ う し,実 験 の再 現 性 自体 も難 し くな る で あ ろ う。 ま た,再 現 性 の 情 報 を 明確 化 す る こ とで,計 算 環 境 の 正 当 な統 一化 が な さ れ て い る か を判 断す る 手 立 て とな る。

こ こで,よ く知 ら れ て い ない 計 算 機 な どを使 用 して い る場 合,よ く知 られ て い る計 算 機 能 力 との ラ フ な 比 較 な ど を示 す と,評 価 測 度 を判 断 す る基 準 の 助 け と な る で あ ろ う。 ま た,複 数 の 環 境 下 で 競 争 的 実 験 を行 う場 合,当 然 計 算 環 境 の 統 一化 は不 可 能 と言 わ ざ る と言 え な い わ け で あ る。 そ れ に対 して は,ベ ンチ マ ー ク に よ りそ れ ぞ れ の計 算 機 の 能 力 を計 測 し,任 意 の マ シ ン と の計 算 時 問 に お け る比 率 に よ り,そ の マ シ ンで 計 算 され た場 合 の ラ フ な値 を標 準 時 間 と して 求 め,そ の 値 を も って 計 算 時 間 の 比 較 をす る。 これ に よ っ て,固 定 化 で き な い 要 因 を ラ フ な意 味 で の 統 一 した 枠 組 み の 中 に ま とめ あ げ,評 価 す る手 立 て とす

る こ とが 可 能 で あ ろ う。

ハ ー ド ウ ェ ア(ブ ラ ン ド,モ デ ル,メ モ リ ー サ イ ズ,CPUス ピ ー ド, プ ロ セ ッ サ ー 数,プ ロ セ ッ サ ー コ ミ ュ ニ ケ ー シ ョ ン ス キ ー ム)

ソ フ ト ウ ェ ア(オ ペ レ ー テ イ ン グ シ ス テ ム,言 語,コ ンパ イ ラ ー,コ ン パ イ ラ ー セ ッ テ イ ン グ)

シ ス テ ム(ジ ョ ブ ミ ッ ク ス)

こ れ ら の 要 因 の ど れ が 強 く影 響 す る か 判 定 し な け れ ば な

2.4.5分 析 と レ ポ ー ト

最 後 に,実 験 で得 ら れ た デ ー タ を分 析 し情 報 に 変 え る作 業 が 重 要 とな っ て く る。 分 析 者 は分 析 の 目 的,仮 説,質 問 に 対 して科 学 的 な根 拠 を与 え て い か ね ば な ら な い 。 特 に次 の よ う な 点 が 分 析 の焦 点 と な る で あ ろ う。

● ア ル ゴ リズ ム の 優 位 性

● 手 法 にお け る 長 所 と短 所

●●●

ヒ ュ ー リ ス テ ィ ック 手 法 に お け る 解 析 と 評 価

寄 与 す る 要 因 と トレー ドオ フ

問 題 の サ イ ズ を大 き く した と きの 振 舞 い

ヱ05

な どに つ い て取 り出 した デ ー タ を統 計 的,あ る い は非 統 計 的 に評 価 し,そ の分 析 の結 果 の ドキ ュ メ ン トを作 成 す る こ と とな る 。 こ の段 階 で も,結 果 に影 響 を 与 え る 多 くの 自由 度 が 存 在 す る。 これ ら の 自由 度 は,あ る意 味 で,分 析 者 の 良 心 に もか か わ る 問 題 に左 右 され る が,や は り,そ の 自 由 度 の 多 さが 影 響 を拡 大 し科 学 的 な レポ ー トか ら遠 ざ け る原 因 と な る 。 また,評 価 に対 す る観 点 が 多 様 で あ り,す な わ ち,こ こ で 述 べ た評 価 測 度 の他,問 題 の特 性 な ど に依 存 し な い 頑 健 性,ア ル ゴ リズ ム の 実 装 の 容 易 さ,広 い 問 題 に対 して 対 応 可 能 な 一 般 可 能 性 な ど,着 目す る 点 が 様 々 で あ る こ とか ら分 析 を含 め て レポ ー トの形 式 にお い て も標 準 的 な基 準 は存 在 し に くい 点 もあ げ られ よ う。 重 要 な こ とは,す で に述 べ た よ うな 問 題 の取 り扱 い に よ っ て肯 定 的 な結 果 に 限定 した 形 式 で持 っ て い く こ とは 分 析 者 の裁 量 で 可 能 で あ る とい う こ とで あ る。また,標 準 的 な基 準 が 整 っ て い な い が た め に,科 学 的根 拠 を持 た せ る た め の 基 本 的事 項 で あ る再 現 性 の条 件 が 整 っ て い な い ケ ー ス も存 在 す る 。

こ の よ う に,分 析 を科 学 的 と して位 置 づ け る た め に は広 範 囲 な テ ス トと統 一 環 境 を用 意 しな け れ ば な らな い で あ ろ う。 さ らに,そ れ を保 障 す る た め の 環 境 の 明 示 と,再 現 性 が 科 学 的 根 拠 を 持 た せ る もの と して 必 要 不 可 欠 な 事 項 とな る 。 結 果 の再 現 性 を可 能 とす る ドキ ュ メ ン トで は,主 に次 の よ う な も の が 上 げ ら れ る で あ ろ う。

● 影 響 す る要 因 の 詳 細 化

● 評 価 測 度 の 取 り扱 い

● パ ラ メ ー タ設 定

こ れ らの 詳 細 な レポ ー トが な い な らば,再 現 性 を失 う と同 時 に,客 観 的 な 判 断 も不 可 能 と な る 。 逆 に,こ れ らの情 報 が 整 う努 力 を行 う こ と に よ り,前 述 し た 多 くの 自 由度 に対 し て,科 学 的 な判 断 が くだせ る 立 場 へ と向 か わせ る 一 つ の 強 い フ ァ ク タ ー とな るで あ ろ う。

ヱ06 商 学 討 究 第57巻 第1号

ま た,レ ポ ー トに お い て グ ラ フ ィ カ ル な 表 示 は説 得 力 の あ る洞 察 を助 け る も の で あ り,そ の利 用 を心 が け るべ きで あ る 。 しか し,場 合 に よ っ て は 逆 に曖 昧 な 結 果 表 示 と な る場 合 もあ る の で,ケ ー ス に お い て有 効 な使 用 を心 が け るべ き で あ る。

最 後 に,本 分 野 に お け る よ り科 学 的 な要 素 を取 り入 れ る ア プ ロ ー チ と して統 計 的 な 分 析 を 取 り入 れ た 実 験 の 設 計 が 考 え られ る で あ ろ う[1]。 多 様 な 要 因 が 変 化 す る と き,統 計 的 な方 法 論 が 分 析 の 唯 一 の ア プ ロ ー チ と な り,テ ス トの 負 担 量 を最 小 化 し,科 学 的 な分 析 の 結 果 を最 大 化 す る もの で あ ろ う。た と え ば,

実験 計 画 法 な ど は物 理,農 学,医 学 で は一 般 的 に使 用 され 科 学 的分 析 の 根 拠 と な っ て い る。 本 分 野 に お い て も期 待 され る ア プ ロー チ で もあ ろ う。

2.5実 験 的解 析 の ま とめ

現 在 の ヒュ ー リ ス テ ィ ッ ク手 法 は,計 算 機 の 能 力 の拡 大 と と もに 大 規 模,複 雑 な 問 題 に対 して の果 敢 な挑 戦 を 可 能 と し,発 展 しつ つ あ る分 野 で あ る。 しか

し,ヒ ュ ー リス テ ィ ック 手 法 の主 要 な分 析 法 で あ る実 験 的解 析 に お い て は,そ の基 準 が 不 明 瞭 な部 分 が 現 在 も残 され て い る 。 また,と に か く実 験 して み た ら ば う ま くい っ た とい う レベ ル で 終 わ り,一 般 的 な,普 遍 的 な 結 論 に到 達 して い な い 範 疇 で あ る こ と は否 め ない 。 そ こで,主 要 な 観 点 で あ る解 の質 と計 算 時 間 に 影 響 を及 ぼ す 要 因 を 中 心 に ヒ ュ ー リス テ ィ ッ ク手 法 の 実験 に対 す る 考 え を大 ま か に述 べ させ て い た だ い た 。 体 系 しづ らい分 野 で あ り,書 き足 りな い 部 分 が 多 々 あ っ た の も事 実 で あ る 。 さ らに,こ れ らの 分 野 に 関 して の 詳 細 な ガ イ ドラ イ ン と し てBarr[2],Johnson[7],久 保[10]な どが あ る の で,是 非 参 考 に して い た だ き た い。

Barr[2]に も記 さ れ て い るが,大 雑 把 に 言 え ば,実 験 的 解 析 に お け る 到 達 点 は

● 広 範 囲 な テス ト

● 実 験 環 境 の 明 示

● 実 験 結 果 の 再 現 性

ヒ ュ ー リ ス テ ィ ッ ク 手 法 に お け る解 析 と評 価 107

そ れ に よ り,科 学 的,客 観 的 な実 験 解 析 が 多 く行 わ れ る こ と に よ り,今 まで, 狭 い 意 味 の 点 で しか な く,一 般 性,相 対 的優 劣 な どの 結 論 が 導 きが た か っ た 状

況 か ら,さ らに そ れ ら を結 ぶ 線 へ と,そ し て面 に な り,普 遍 性 の あ る結 論 へ と 進 み ヒ ュ ー リス テ ィ ッ ク手 法 の 今 後 の発 展 につ な が る もの と考 え る。

3理 論 的 解 析 の ア プ ロー チ

上 記 で ヒュ ー リス テ ィ ック 手 法 に お け る実 験 的解 析 の 問題 点 と対 処 に 関 して の 考 察 を示 した 。こ の実 験 的 解 析 が 主 流 とな り ヒ ュ ー リス テ ィ ック 手 法 の解 析, 分 析 が 進 め られ て い る 。 そ れ に は,よ り リ ア ル な情 報 を 用 い た解 析 を通 して ヒ ュー リ ス テ ィ ッ ク手 法 の性 能 を明 らか に し て い くこ との現 実 的 な方 向性 が 読 み取 れ る 。確 か に,ヒ ュ ー リス テ ィ ック 手 法 で 求 ま る値 が 最 悪 値 解 析 で 算 出 さ れ る値 よ りは るか に 良 い 場 合 が 多 い 。 また,確 率 的 解 析 で立 て た モ デ ル は 限 定 した も の で あ り,現 実 的 な 問 題 にそ ぐわ ない な どの 問 題 が ヒ ュー リ ス テ ィ ッ ク 手 法 に対 す る 理 論 的解 析 に は多 々 見 られ る。 しか し,上 記 で述 べ た よ うな 問 題 を含 ん だ 実 験 的 解 析 で は ヒ ュ ー リス テ ィ ッ ク ス手 法 の 特 性 の 一 般 的,普 遍 的 結 論 は 導 か れ な い で あ ろ う。 ま た,そ の 問 題 を ク リア した 実 験 的解 析 の み で も,

ヒ ュー リス テ ィ ック ス の 特 性 が 深 め られ る と も思 わ ない 。 多 方 面 か らの 見 方 に よ りは じめ て 普 遍 的 な研 究 へ とつ なが る もの と考 え る。 そ こで,次 に,理 論 的 解 析 の 一 つ で あ る確 率 的 解 析 の 分 析 例 を示 して,そ の可 能 性 を考 え て い きた い 。

こ こ で はEikelder等[3]が 行 っ た 巡 回 セ ー ル ス マ ン問 題 に対 して のLocal Searchの 確 率 的 解 析 を示 す 。 近 傍 構 造 は2‑OPT近 傍 を 限 定 した バ ー ジ ョ ン を 用 い て お り,次 の改 善 解 へ 移 動 す る方 法 は近 傍 集 合 の 最 小 値 を選 択 す る こ と と して い る 。 ま た,解 空 間 の解 の コス トの 分 布 を正 規 分 布 と仮 定 し分 析 を 進 め て い る。 こ の よ う な仮 定 は確 率 的 解 析 で の 共 通 した ア プ ロ ー チ で あ る。 そ の 上 で 求 ま る局 所 解 の 値 と局 所 解 を得 る の に必 要 な ス テ ッ プ 数 の確 率 を算 出 して い る 。 そ の 結 果 は 実 際 にLocalSearchで 求 め た 結 果 と比 較 して 密 に 近 似 し,そ

ヱ08

の 優 秀 性 が 示 さ れ た 。 しか し,確 率 的解 析 の欠 点 と言 わ れ た よ う に,い くつ か の点 で モ デ ル を 限 定 して い る わ け で あ り,一 般 性 に薄 く他 の 問 題 へ の 適用 が 難 し い わ け で あ る。 こ こで の 一 つ の 問 題 は 近 傍 構 造 が2‑OPTに 限定 され,か つ, 2‑OPTの 限 定 した バ ー ジ ョン で あ る こ とで あ る。 す な わ ち,通 常 の2‑OPTで

は適 用 で きず,そ の 他 の近 傍,あ る い は そ の 他 の 問 題 へ の適 用 が 難 しい こ とで あ る。 そ こで,様 々 な近 傍 や,問 題 へ の 適 用 が 可 能 と な る よ う,著 者 が 試 み た 手 法 を述 べ,ヒ ュ ー リス テ ィ ッ ク手 法 の 理 論 的解 析 へ の 期 待 とつ な げ て い き た

い 。

3.1Eikelderに よ る確 率 的 解 析

こ こ で,対 象 とす る問 題 は そ の 他 の 問 題 へ の適 用 が 可 能 で あ る こ とを 示 す た め,グ ラ フ 分 割 問 題 に 対 して,交 換 近 傍 を用 い たLocalSearchで の 同 様 な 結 果 を考 え て い きた い 。 グ ラ フ分 割 問題 は カ ッ トエ ッ ジ の コス トを最 小 化 す る よ

う頂 点 を2つ の集 合 に分 割 す る問 題 で あ り,互 い の 集 合 の任 意 の 一 つ の 頂 点 同 士 を交 換 す る交 換 近 傍 に よ り近 傍 構 造 を定 義 す る 。 最 初 の ス テ ップ と して,ま ず,あ る確 率 分 布 に従 っ た 問 題 の解 空 間 を設 定 す る。 す な わ ち,解 κの コス ト

を確 率 変 数f(x)と し考 え,f(x)は 平 均 〃z,分 散 σ2の正 規 分 布yV(m,σ2)と な る 確 率 空 間 の 上 でLocalSearchの ア ベ レー ジ ケ ー ス の 分 析 を行 う。 この 解 空 間 モ デ ル の 設 定 は確 率 的 解 析 に お け る共 通 した ア プ ロー チ で もあ る。 ま た,任 意 の 解xの 近 傍 を κ1,̲,Xbと す る と,そ の 大 きさ はb=[N(κ)【 と な る 。 次 に, Eikelderの モ デ ル は こ こ で の フ レー ム ワ ー ク と な る の で そ の モ デ リ ン グ の 概 要 を説 明 す る。 まず,重 要 な確 率 と して 以 下 の ス テ ップ確 率 が あ る。 この 確 率

に よ っ て 我 々 が 求 め た い統 計 量 が す べ て 求 ま る こ と とな る 。

9(C・,C)=Pr{∀i∈{、,...,blf(Xi)〉 ・if(X・)=C・} (1)

こ れ は解Xoが コス トCoを 持 つ と き,そ の 近 傍 の す べ て が コ ス トcよ り大 で あ る確 率 を示 す 。 さ ら に,こ の ス テ ッ プ確 率 を用 い て,コ ス トCoの 解 か ら コ ス

トcの 解 へ 移 動 す る確 率 密 度 が 以 下 の 式 で導 出 され る。

ヒ ュ ー リス テ ィ ッ ク手 法 に お け る解 析 と評 価

∂

「 死9￠ αc)

(2)P(Co,c)=1

‑9(Co ,Co)

さ ら に,高 々 κ+1回 の ス テ ッ プ で コ ス トcの 局 所 解 に 達 す る 密 度 関 数 ρκ+1(c) と,κ ス テ ッ プ ま で 局 所 解 に 達 せ ず,κ+1ス テ ッ プ で コ ス トcと な る 密 度 関 数 ηκ+1(c)は 以 下 の 再 帰 式 で 求 ま る で あ ろ う 。

ρ κ+1(C)=ρ κ(C)+9(C,C)η κ(C)

nrc・・(・)一 ∫ 男・￠ ・)(1‑9(・ ・…))P￠ ・・c)d・ ・

(3) (4)

こ れ ら よ り,最 終 解 の 局所 解 密 度 が

Pfin=limρ κ(5)

κ→oo

で 計 算 さ れ る 。 た だ し,limη κ==0で あ り上 式 は 収 束 さ れ 一 定 の 値 に 近 づ く。

だ レ 

最 後 に,局 所 解 に達 す る ス テ ップ数 を確 率 変IX:stePsと 捉 え れ ば,

P・1・t・P・ 一 ・}一 ∫ 二9(c,・)rp、 、一・(c)d・ , (6)

と な る 。

3.2AR(1)プ ロ セ ス に よ る解 空 間 の 解 析

問題 は ス テ ップ確 率(1)式 を導 出す る こ と に帰 着 さ れ る 。 この 値 が 求 ま る こ と に よ り,得 られ る解 の値,お よ び要 求 さ れ る 反復 数 の確 率 分 布 が 求 ま る こ と と な る 。 この ス テ ッ プ確 率 導 出 の キ ー ポ イ ン トと して,2つ の 相 関 関 数 を知 る こ と が 重 要 な課 題 と な る 。 一 つ は解Xoと そ の 近 傍 解 との 相 関 関 数 で あ り,も う 一 つ は解Xoの 近 傍 内 の 解 同士 の 相 関 関 数 で あ る。Eikelder等 は この 値 を求 め る た め に,2‑OPT近 傍 の 限 定 版 モ デ ル を 設 定 し,そ の モ デ ル の 上 で 上 記 の2 つ の 値 を 導 出 した 。 しか し,通 常 の2‑OPT近 傍,お よ び他 の 組 合 せ 最 適 化 問 題 で の 利 用 は 不 可 能 で あ る 。 そ こ で,我 々 はAR(1)プ ロ セ ス(afirstorder

ヱヱ0商 学 討 究 第57巻 第1号

autoregressiveprocess)の 考 え 方 を 利 用 し,相 関 関 数 値 を 導 出 し ス テ ッ プ 確 率 を も と め る 方 法 に つ い て 検 討 し た 。AR(1)と い う の は確 率 過 程 に お け る 時 系 列 上 で 以 下 の 式 に 従 う プ ロ セ ス の こ と を い う 。

Xt=9LXt‑1+Nt (7)

そ して,任 意 の解 κに 対 して そ の 評 価 値(コ ス ト)を!(κ)と す る と,組 合 せ 最 適 化 問 題 の ラ ン ドス ケ ー プ は 写 像 ∫:κ け!ω に よ っ て 定 義 さ れ る 。 こ の ラ

ン ドス ケ ー プ 上 の ラ ン ダム ウ ォー ク{煽 に よ る評 価 値 の 確 率 的 な時 系 列 は

!(κ κ)ニ ρ(1)[(f(κ κ̲1)一 〃z]+m+△ (8)

で 表 され,AR(1)プ ロ セ ス に従 う もの と考 え られ る。 この 性 質 が 多 くの 組 合 せ 最 適 化 問 題 の解 空 間 に見 られ,統 計 的 な性 質 を導 き出 す こ と を可 能 とす る[9]。

こ こ で,△ は あ る 平 均 と分 散 を 持 っ たWhiteNoiseで あ り,ρ(r)は 自己 相 関 関数 で あ る。AR(1)プ ロ セ ス の特 徴 と して

ρ(・)一 ρ(1)1・1,r‑O,±1,±2,… (9)

の式 の よ うに 自己 相 関 関 数 は ス テ ッ プ数rの 増 加 に よ っ て0へ の 指 数 関 数 的 な 減 衰 を 示 す 。 この 性 質 が確 認 さ れ た な ら ば,解 空 間 の評 価 値 ラ ン ドス ケ ー プ が AR(1)プ ロ セ ス に従 っ て い る と判 断 で き うる 。 ま た,時 系 列 がAR(1)プ ロ セ ス で あ り,か つ ρ<1な ら ば,そ の プ ロ セ ス は 定 常 過 程 とな る こ とが 知 られ て い る 。 定 常 過 程 にお い て 自己 共 分 散 は

R(・)一 講 幽 一町 ㈲])(Zf(x…)‑E[zf(・ …)])⑳

で見 積 も り可 能 とな る[8]。 した が っ て,1ス テ ッ プ の 自己 相 関 関 数 は ρ(1)

=R(1)/R(0)で あ り,こ の 値 はXoと そ の 近 傍 と の 相 関 関 数 ρ と同 値 で あ る 。 ま た,Xoの 任 意 の2つ の 近 傍 問 の 相 関 関 数 レ は,近 傍 解 同 士 の 共 通 す る 属 性 の 比 率 が 高 い こ とか ら,近 似 的 に ρ に 近 い 定 数 と仮 定 す る。 こ の よ う に, AR(1)プ ロ セ ス の 考 え に基 づ き求 め た 相 関 関 数 を 用 い て,!(Xo)=Coが 与 え ら

1

0.8

0.6

0.4

0.2

0

一〇.2 0

ヒ ュ ー リス テ ィ ッ ク手 法 に お け る解 析 と評 価

empirical theoretical‑一 一+一 一一

20406080

図1自 己相 関関 数 の振 る舞 い

100

刀 ヱ

6.00E‑03 5.00E‑03 4.00E‑03 3.00E‑03 2。00E‑03 1.00E‑03 0.00E+00

0 0 0 0 0 0 0 0 8 7 6 5 4 3 2 1 0

O◎っ

OQっl

oo O T

O ◎o T

NめNl

寸Noっー

㊤Oeっl

o◎O寸l

O寸ゆI

N 6 1

寸◎oO‑

Oゆトー

ooNool

OOOI

… 一理論値 一 実測値

図2:最 終解 の確 率 密度関 数 と実測 値