組合せ最適化問題に対する近傍集合の解析
加 地 太 一
1は じ め に
プ リ ン ト回 路 基 盤 に お い て,ド リ ル で複 数 の 穴 を あ け る加 工 工 程 が あ る 。 こ の と き,基 盤 の ドリル の 穴 あ け に要 す る 時 間 を で き る だ け短 くな る よ うに 機械 を 自動 化 した い 。 そ の た め に,ド リ ル穴 の 位 置 を機 械 が 次 々 と移 動 して い くの に 要 す る 時 間 を最 小 化 し た工 程 シス テ ム を構 築 す る 。 そ れ に よっ て,運 用 に お け る効 率 的 な生 産 計 画 が 可 能 と な る。 実 際,こ れ に よ っ て あ る メ ー カ ー で は 年 間 一 億 円程 度 の 費 用 削 減 に成 功 した との 話 もあ る。 さて,こ の よ う な 問題 は 本 論 文 で 対 象 とす る組 合 せ 最 適 化 問 題 を用 い て 解 く こ とが き る うる 。 そ して,こ の 組 合 せ 最 適 化 問題 は 適 切 な計 画,設 計,方 策 な ど解 くた め の 応 用 範 囲 の 広 い 問 題 で もあ る。 た とえ ば,上 記 の 回路 基 盤 穿 孔 の 問 題 で は,組 合 せ 最 適 化 問 題 の 一 つ で あ る巡 回 セ ー ル ス マ ン問 題(travelingsalesmanproblem,TSP)を
解 く事 に よ って 解 を 求 め る こ とが で き うる 。
TSPと は"何 ケ所 か の 都 市 とそ の都 市 間 の 距 離 が 与 え られ た と き,す べ て の都 市 を巡 り元 に戻 る 最 短 の道 順 を求 め る 問 題"で あ る。 こ の 問 題 はす べ て の 可 能 な道 順 を列 挙 して そ の 中 で 最 短 な 巡 回 路 を見 つ け れ ば解 け るわ け で あ るか ら,あ ま り に も単 純 で ナ ンセ ンス な 問題 と思 わ れ る だ ろ う。 と こ ろが,こ の ナ ンセ ンス な 問 題 が 計 算 機 で も解 け な い難 物 中 の 難 物 な の で あ る 。 も ち ろ ん,5 都 市 な ら高 々24通 りの 道 順 しか な い の で,そ の 中 で 最 短 な巡 回 路 が 答 え で あ り 誰 で も簡 単 に解 け る 問 題 で あ る。 と こ ろ が,そ の都 市 数 が 増 え て い く と道 順 の 数 が ど う な る か が こ の 問 題 の ネ ッ ク と な る の で あ る 。 都 市 数 を π とす れ ば,
〔41〕
出 発 点 か ら次 の 都 市 へ の 行 き方 は(n‑1)通 りで あ り,さ ら に,そ の都 市 か ら次 の都 市 へ の 行 き方 は(n‑2)通 り と考 え て い け ば,全 巡 回路 の 数 は(n‑1)1 通 りと な る。 こ れ は ス ター リ ン グ の公 式(刎 得飯 万(〃/のつ に よ りほ ぼ 〃η通
り と表 す こ とが で き,都 市 数 の増 加 に よ り指 数 関 数 的 に す べ て の可 能 な道 順 の 数 が 莫 大 に増 加 す る。 これ を組 合 せ 的 爆 発 と呼 ぶ 。 た と え ば,30都 市 の 一 つ の 巡 回 路 の コ ス トを 一秒 間 に1012(1兆)回 計 算 で きる ス ーパ ー コ ン ピュ ー タが 仮 に あ っ た場 合,30都 市 の 全 部 の 巡 回路 の 数 は291二 約8.8×1030個 で あ る の で, 30都 市 のす べ て の 巡 回路 を計 算 す る に は8.8×1018秒 か か る 。 一 年 は3.15×107 秒 で あ る の で,30都 市 の 巡 回 セ ー ル ス マ ン 問 題 の 答 え を 求 め る に は 約2800億 年
(2.8×1011)年 もか か る こ と に な る。 す な わ ち,た か だ か,30都 市 を計 算 す る の に 数 千 億 年,あ る い は 数 兆 億 年 とい う天 文 学 的 計 算 時 間 を要 して し ま う。
ま た,こ れ らの 問 題 は い か に計 算 機 の ス ピ ー ドが 高 速 に な ろ うが,そ の 計 算 時 間 は雀 の 涙 ほ ど しか 改 善 され な い。 とい う か必 要 とす る計 算 時 間 は残 念 なが ら 天 文 学 的 な値 の ま まで あ る 。 い わ ゆ る,計 算 機 が 如 何 に速 くて もそ の 計 算 時 間 は 問題 の サ イ ズ(都 市 数)に 対 して指 数 関数 的 に 増 加 す る傾 向 を示 し,現 実 的 な時 間 内 で 実 行 不 可 能 な 難 しい 問 題 の 部 類 に入 れ られ る。
こ の よ う に,組 合 せ 最 適 化 問 題 の多 くは本 質 的 に複 雑 度 が 高 く,厳 密 な最 適 解 を効 率 よ く求 め る の は 困 難 で あ る 。 だ が,最 適 値 に近 い値 を もつ 可 能 解 で よ
け れ ば効 率 よ く求 め 得 る可 能 性 が あ り,実 用 上 大 き な意 味 が あ る。 近 似 最 適 解 を う ま く求 め る に は,問 題 の 解 や 構 造 に関 す る 知 識 を い か に 利 用 す る か が ポ イ ン トに な る の で ヒ ュ ー リ ス テ ィ ッ ク解 法 と呼 ば れ る。 さ ら に,近 年 で は そ の ヒ ュ ー リス テ ィ ッ ク な知 識 を組 み 合 わせ て よ り高 度 な ア ル ゴ リズ ム を構 成 す る た め の メ タ ヒ ュ ー リ ス テ ィ ッ ク ス の研 究 が 盛 ん に 行 わ れ て い る 。 そ の 中 に は LocalSearch法,SimulatedAnnealing法,遺 伝 ア ル ゴ リ ズ ム,TabuSearch 法 な ど,最 近 話 題 の ア プ ロ ー チ も含 まれ て い る 。 この メ タ ヒ ュー リス テ ィ ック ス に お い て,解 の 近 傍 が よ りよい ア ル ゴ リズ ム を作 る う え で の 重 要 な概 念 の 一 つ で あ る 。 近 傍 とは 任 意 の解 に対 して,何 らか の操 作 を加 え る こ とに よ り移 動 した解 の 集 合 で あ る。 メ タ ヒ ュー リス テ ィ ック ス で は こ の近 傍 に も とつ い て 解
組 合 せ最 適化 問題 に対 す る近傍 集合 の解析
43
空 間 を探 索 し,よ り良 い解 へ 到 達 させ る も の で あ る。 した が って,こ の 近 傍 の 良 し悪 しが ア ル ゴ リズ ム の優 劣 へ とつ なが っ て く る。そ こ で,本 論 分 で は こ の 近 傍 の 構 造 を確 率 的 に 解 析 して,近 傍 の 特 性 を明 ら か にす る もの で あ る。 こ こ か ら得 られ る情 報 を近 傍 生 成,近 傍 の 移 動 を よ り効 率 的 に 実 現 す る手 立 て へ とつ な げ て い くこ と,ま た,メ タ ヒュ ー リス テ ィ ッ ク ス の性 能 の 解 析 へ とつ な げ て い きた い 。 本 論 分 で は まず,解 空 問 の 特 性 を あ ら わ す 基 礎 統 計 量 をAR(1)モ デ ル を構 成 す る こ とに よ っ て,汎 用 的 に 導 出 す る こ と を 可 能 と し た。 さ らに,情 報 量 基 準 の 考 え を も と に,AR(1)モ デ ル の 正 当 性 を補 強 して お く。 こ のAR(1)モ デ ル か ら得 られ た基 礎 統 計 量 を も と に,近 傍 の 構 造 を あ らわ す 確 率 モ デ ル を構 成 す る。
2AR(1)プ ロ セ ス に よ る 解 空 間 の 解 析
解 の 近 傍 の 分 布,あ る い は,求 ま る局 所 解 の分 布 な ど を推 定 す る確 率 的解 析 を行 う た め,解 空 間 の構造 を統 計 的 に 明 らか に した い 。 そ の た め に,解 空 間 の 特 性 を表 す 各 種 の統 計 量 を考 察 して い く こ とが 必 要 と な っ て くる 。 そ こ で,本 論 文 で は解 空 問 がAR(1)プ ロセ ス と呼 ば れ る 特 徴 的 な性 質 を有 す る とい う仮 定
を検 証 し,そ こか ら必 要 な統 計 量 を導 き出 して い く。 そ し て,後 述 す る節 で そ の 導 出 さ れ た 統 計 量 の 有 効 性 を 検 討 す る 。確 率 的 な解 析 で は通 常,モ デ ル を構 築 しや す い よ う に,特 定 の 問題,お よ び特 定 の 近 傍 な ど を設 定 して,こ の よ う
な 統 計 量 を導 出 す る。 しか し,こ こ で提 唱 す るAR(1)プ ロ セ ス を用 い る こ と に よ り,多 くの 組 合 せ 最 適 化 問題 あ る い は 各種 の近 傍 な ど に対 応 す る汎 用 的 な 解 析 が 可 能 と な る こ とが 期 待 され る。 以 下 に,解 空 間 の 性 質,AR(1)プ ロ セ ス に よ るモ デ ル 化,そ して,そ こ か ら導 出 さ れ る 基 礎 統 計 量 につ い て 考 え て い く。
組 合 せ 最 適 化 問 題 の す べ て の 可 能 な 解xの 集 合 をXと し よ う。 そ し て,与 え られ た解 か ら あ る基 本 操 作 で 別 の 解 を導 出 す る こ と を移 動 と呼 び,そ の移 動 の 集 合 に よっ て,任 意 の 解 に対 して 近 傍 集 合 が 定 義 で き る。 また,解 κに対 し て の 評 価 値(コ ス ト)をf(x)で 表 す こ と とす る。 そ の 写 像f:XHRを 組 合 せ
最 適 化 問 題 の 評 価 値 ラ ン ドス ケ ー プ(fitnesslandscape)と 呼 ぶ こ と とす る。
評 価 値 ラ ン ドス ケ ー プ とい う言 葉 は理 論 生 物 学 お よ び理 論 物 理 学 に端 を発 し, 組 合 せ 的 対 象 か ら 実 数 値 へ の 写 像 に 関 す る 問 題 に 広 が りつ つ あ る。 最 近, Weiberger[5]は 不 偏 的 ラ ン ダ ム ウ ォー ク の概 念 が 評 価 値 ラ ン ドス ケ ー プ構 造 を調 査 す る た め の 適 切 な手 法 で あ る こ と を示 した 。 こ こ で,"評 価 値 ラ ン ド ス ケ ー プ は統 計 的 にisotropicで あ る"と い う重 要 な付 加 的 条 件 を課 す る こ と が 必 要 で あ る。
この 評 価 値 ラ ン ドス ケ ー プ の 特 性 を解 析 す る た め に,ま ず,ラ ン ダ ム に 選 ん だ 点(解)を 出発 点 と して ラ ン ダ ム に選 ば れ た近 傍 点(近 傍解)に 移 動 し,こ の 点(解)か ら再 び ラ ン ダ ム に 選 ば れ た 近 傍 点(近 傍 解)に 移 動 す る こ と を繰
り返 す こ と に よ っ て 得 られ た 評 価 値(fitness)の 系 列 を考 え る 。 こ の評 価 値 の 系 列 の 統 計 が,選 ば れ た 出発 点 に か か わ らず 同 じで あ る と き,考 え て い る 評 価 値 ラ ン ドス ケ ー プ は 統 計 的 に等 方 的 な ラ ン ドス ケ ー プ(statisticallyisotropic landscape)で あ る と い う。 多 くの 組 合 せ 最 適 化 問 題 で は こ の性 質 が み た され て い る と考 え ら れ る の で,こ の モ デ ル の特 性 を利 用 し,評 価 値 ラ ン ドス ケ ー プ の構 造 を分 析 す る こ とが 可 能 で あ る。
この 評 価 値 ラ ン ドス ケ ー プ に着 目 し,組 合 せ 最 適 化 問 題 の ラ ン ダ ム な探 索 過 程 の ス テ ッ プ κに お け る評 価 値 ∫(κκ)がつ くる 時 系 列 は,あ る ラ ン ダ ム ウ ォー ク の 結 果 で あ る と考 え る こ とが で き る。 こ の系 列 が 時系 列 モ デ ル の 一 つ の タイ プ で あ るAR(1)プ ロ セ ス(autoregressiveprocessoforderone)[5コ と して モ デ ル 化 す る こ とが 可 能 で あ り,そ の 考 え 方 を利 用 して 解 析 を試 み る も の で あ る 。
AR(1)プ ロセ ス は 次 の 方 程 式 をみ たす 過 程 で あ る 。
Xt=ZLXt̲1+Wt
(1)た だ し,Wtは 無 相 関確 率 変 数 の 定 常 系 列 で あ る。Weinbergerは"AR(1)プ ロ セ ス が,N‑K問 題 や 組 合 せ 最 適 化 問 題 を含 め て,ラ ン ドス ケ ー プ の 広 い ク ラ ス の 上 で ラ ン ダム ウ ォー クの 統 計 を う ま く捕 ら え る で あ ら う と考 え る こ とに は
組合 せ 最適 化 問題 に対す る近 傍集 合 の解析45 十 分 納 得 の い く理 由 が あ る"と 述 べ て い る 。
組 合 せ 最 適 化 問 題 の 評 価 値 ラ ン ドス ケ ー プ 上 の ラ ン ダ ム ウ ォー ク{Xl,κ2,
̲,κN}は,AR(1)プ ロ セ ス と して,次 の 再 帰 方 程 式 で 支 配 さ れ た モ デ ル化 が 可 能 と考 え られ る。
!(κκ)ニ μ+ρ(1)[f(κ κ̲1)一 μ]+△(2)
こ こ で,∫(κ κ)は 解 κκの コ ス ト を 確 率 変 数 と し考 え た も の で あ る 。 ま た,κ は 時 系 列 の ス テ ッ プ を 表 す 。 こ の 再 帰 的 な 性 質 が 多 く の 組 合 せ 最 適 化 問 題 の 解 空 間 に 見 ら れ,統 計 的 な 性 質 を 導 き 出 す こ と を 可 能 と す る[2][5]。 た だ し,
△ は 平 均0,分 散d2を も つ 白 色 雑 音 で あ り,ρ(r)はrス テ ッ プ の 自 己 相 関 関 数 で あ る 。 便 宜 上,ρ(1)を ρ で 表 す も の と す る 。
AR(1)プ ロ セ ス の 特 徴 と し て
ρ(r)==ρ(1)1・1,r‑O,±1,±2,…(3)
の式 の よ う に 自己 相 関 関 数 は ス テ ッ プ数7の 増 加 に よ っ て0へ の 指 数 関 数 的 な 減 衰 性 を示 す 。 こ の性 質 が 確 認 され た な らば,解 空 間 の 評 価 値 ラ ン ドス ケ ー プ がAR(1)プ ロ セ ス に従 っ て い る と判 断 で き う る。 ま た,時 系 列 がAR(1)プ ロ セ ス で あ り,か つ ρ(1)<1な らば,そ の プ ロ セ ス は 定 常 過 程 とな る こ とが 知 ら れ て い る[3]。 定 常 過 程 の 定 義 か ら,!(x。)は 定 数 の 平 均 値 μ と分 散 σ2を持 つ 。 す な わ ち,
E[f(κ κ)]=μforallk(4) E[(f(xκ)一 μ)2]ニ σ2forallk(5)
が 成 立 す る 。 ま た 定 常 性 に よ り,COV(f(ti),ご(ち))は ス テ ッ プ 差li一 ブ1に の み 依 存 す る 。 共 分 散 関 数(covariancefunction)を
五〜(h)ニCov(f(Xh),f(Xo))==E[(f(Xh)一 μ)(f(Xo)一 μ)]
に よ り 定 義 す る と,
(6)
Cov(ご(Xi),!㊥)=1〜(li一 ブ1)
で あ り,ま た 勿 論
R(0)ニVar(f(κ κ))=σ2
で あ る。 こ こで,定 常 過 程 にお い て 自己 共 分 散 は
Rω 一 寿 罫 細 一E[f(x・)])・(fx…)‑E[f(x…)])
で見 積 も り可 能 と な る[3]。 した が っ て,1ス テ ッ プの 自己相 関 関数 は
ρ 二 去〜(1)/R(0)
(7)
(8)
(9)
(1①
で あ り,こ の 値 はXoと そ の 近 傍 との 相 関 係 数 と同 値 で あ る 。 ま た,Xoの 任 意 の2つ の 近 傍 聞 の 相 関 係 数 りは,近 傍 解 同 士 の 共 通 す る属 性 の 比 率 が 高 い こ とか ら,近 似 的 に ρに 近 い 定 数 と仮 定 す る。 こ の よ う に,AR(1)プ ロ セ ス の 考 え に 基 づ き解 空 間 の特 徴 的 な統 計 量 が 推 定 可 能 と な る り,以 後 で述 べ る推 定 値 の基 礎 統 計 量 と し て活 用 で き う る もの と考 え る 。
評 価 値 ラ ン ドス ケ ー プ 上 の 時 系 列 がAR(1)モ デ ル で あ れ ば,い くつ か の特 性 が得 られ る わ け で あ る が,問 題 は 実 際 にAR(1)プ ロ セ ス で あ る か とい う こ とに 帰 着 さ れ る。AR(1)プ ロ セ ス の特 徴 的 な 性 質 と し て 指 数 的 な 減 衰 性 を示 す(3)式 とな る顕 著 な特 性 が あ る 。 こ の指 数 的 減 衰 性 を確 認 して,解 空 間 がAR(ユ)プ ロ セ ス に従 っ て い る か を確 か め て み る。 た だ し,解 空 間 を ∫(κ)は平 均 吻,分 散 δ2の正 規 分 布eiV(m,a2)に 従 う確 率 空 間 と考 え る 。 こ の解 空 間 モ デ ル の 設 定 は 確 率 的 解 析 に お け る 共 通 し た ア プ ロー チ で もあ り,以 後 の 分 析 に お い て も同 様 な解 空 間 を対 象 とす る 。 特 に,本 研 究 に お け る手 始 め の段 階 で もあ る の で,解 析 の 検 証 実 験 の 事 例 と して,組 合 せ 最 適 化 問題 の 代 表 的 な 問 題 で あ るTSPを 使 用 し,扱 い や す い 問 題 の 大 き さか ら解 析 して い くこ と とす る。 グ ラ フ の構 造 は ラ ン ダ ム な コス トを付 与 した 完 全 グ ラ フ で あ り,頂 点 数100と500を 対 象 とす る 。 そ の解 空 間 は コ ス トの 平 均 が0,分 散 は頂 点 数100の 場 合 は10で あ り,頂
組合 せ 最適化 問題 に対 す る近傍 集合 の解 析47
点 数500の 場 合 は50と す る。 た だ し,こ の 場 合,ユ ー ク リ ッ ド平 面 的 な性 質 は 有 さ ない 。
図1は 頂 点 数100の 場 合 の 結 果 で あ り,破 線 が 理 論 的 に 導 出 した 自 己相 関 関 数 の振 る舞 い を 示 し,実 線 が 対 象 の解 空 間上 の サ ン プ ル か ら実 際 に 自己 共 分 散 の見 積 も り を求 め る(9)式か ら 自 己 相 関 関 数 の 値 を導 出 しそ の 振 る 舞 い を示 し た。 また,図2は 頂 点 数500の 場 合 の 同様 な 結 果 で あ る。
結 果 と して,解 空 間 の サ ン プ ル か ら求 め た 自己 相 関 関 数 値 は理 論 的 に導 出 し た 自己相 関 関 数値 と 同様 な 振 る舞 い を示 し,指 数 関数 的 な減 衰 性 が 認 め られ る。
した が っ て,そ の 空 間 はAR(1)プ ロ セ ス に 従 っ て い る と い っ て よい で あ ろ う。
rl
0.8
0.6
4 α
⊆O凋邸一Φ﹂﹂OOO↑⊃邸
0.2
0
一〇.2 0
sample‑
theoretic‑一 一一
50100150200250
step
図1:頂 点 数100の 自 己 相 関 関 数 の 振 る舞 い
300
1
0.9
0.8
0.7
§o・6 遷
§o'5
濤o .4
0.3
0.2
0.1
0
01002003004005006007008009001000
step
図2:頂 点数500の 自己相関 関数 の振 る舞 い
3情 報 量 基 準 に よ るAR(1)モ デル の検 証
前 節 で は,自 己相 関 関数 が 指 数 的 減 衰 性 を示 すAR(1)プ ロ セ ス の特 徴 的 な性 質 が 認 め られ る こ と を示 した 。 た だ し,AR(1)プ ロ セ ス で あ る な ら ば指 数 的 減 衰 性 と な り う る が,指 数 的 減 衰 性 の 性 質 が あ れ ばAR(1)で あ る と は 必 ず し もい え な い 。 そ こで,情 報 量 基 準 な どの 考 え方 を 用 い て,異 な る観 点 よ り検 討 を加 え そ の 正 当性 を補 強 して お き た い 。 まず,確 率 過 程 に お け る予 測 の 理 論 か ら, 時 聞 κ に お け る 時 系 列 の 値 戸 は そ れ 以 前 の 各 時 点 の 結 合 分 布 が 多 変 量 正 規 分 布 と し て表 され る の な らば,
F・a・F。 一、+a2F。‑2+…+apE。‑P㈲
が 最 適 な 予 測 子 で あ る と言 わ れ て い る[5]。 た だ し,各 係 数 はYule‑Walker 方 程 式 に従 う。 した が っ て,最 良 な 自 己 回帰 式 モ デ ル を推 定 す る こ と に よ り,
組合 せ最 適化 問題 に対 す る近傍 集合 の解析49
組 合 せ 最 適 化 問 題 の解 の ラ ン ダ ム移 動 の プ ロ セ ス を決 定 す る こ とが で き る。 具 体 的 に は,ま ず,自 己 回 帰 モ デ ル と して い くつ か の モ デ ル の 次 数 に対 し て の 自 己 回 帰 係 数,白 色 雑 音 の標 準 偏 差 な ど を最 尤 法 を用 い て推 定 す る。 次 に,い く つ か の 次 数 に対 して推 定 され た 自己 回帰 モ デ ル に対 して どの モ デ ル が 最 善 で あ る か を,客 観 的 な 基 準 と してAIC(赤 池 の 情 報 量 基 準)[3]を 用 い て 決 定 し, 自 己 相 関 関数 の 振 る舞 い の モ デ ル とす る。
こ こで 利 用 す る最 尤 法 は,得 られ た デ ー タに よ っ て,任 意 の 母 数 が 取 る尤 も ら し さ を表 す 関 数 で あ る 尤 度 関 数 を用 い て 母 数 の 値 な ど を推 定 す る 方 法 で あ る。 そ して,最 適 な予 測 子 で あ る 自己 回帰 モ デ ル の 一 般 式 は
X(t)=α1X(t‑1)+α2X(t‑2)+…+αMX(t一 乃の+ア7(の
働で あ る の で,任 意 の 次 数Mに 対 し て お の お の の 自 己 回 帰 係 数 αiの値 と17V(t) の 分 散 σの 値 を こ の 最 尤 法 で 推 定 す る こ と と な る。 こ こで,時 間 と と も に 変 化 す る時 系 列 デ ー タ を{κ1,x2,̲,κN}と す る と,こ の モ デ ル に対 して の 尤 度 関 数 の対 数 を とっ た 対 数 尤 度 関 数 は
L(cri,a・,…,・・M,σ)一 一t
,,ゑ 磯 げ ツ2‑‑llin2πr(i3)
と な る 。 こ の 対 数 尤 度 関 数 の 値 が 最 大 で あ る と こ ろ のbl1,α2,...,aM,δ が 最 も 尤 も ら し い モ デ ル を 構i成 す る こ と と な る 。 そ のa1,a2,̲,aMの 値 は,
ω〃=Σ η 一μ,一ブ ㈲
t=1
と い う量 を導 入 す る こ とに よ っ て,
ω11ω12"。 ω11匠
ω21ω22● ●'ω2M
ω ルnω ル∫2'● ● ω 」 励
・偽・殉⁝^吻
を 解 く こ と に よ っ て 決 定 す る 。 ま た,δ は,
ω10
ω20
ωMO
(15)
δ一鎗 毎一
、亀蜘2㈹
か ら求 ま る 。
さ ら に,実 際 の デ ー タ を分 析 す る 際 の 有 効 な モ デ ル選 択 基 準 と して 情 報 量 基 準AICが あ る。 そ の 計 算 は
AIC=‑2(最 大 対 数 尤 度)+2(モ デ ル の パ ラ メ ー タ の 数)
(17)で 与 え られ る 。 こ のAICの 値 が 小 さ い ほ うが,よ り真 の モ デ ル に近 い こ と を 意 味 す る値 で あ り,こ の 値 の 比 較 に よ っ て モ デ ル の 正 当性 を表 す 指 標 とな る わ
け で あ る。 自 己 回 帰 モ デ ル の 場 合,最 大 対 数 尤 度 は
L(a、,a,,…,aM,δ)一 一 穿 一 誓ln2π ♂ ⑯
とな る の で,こ れ を㈲ 式 に 入 れ て本 質 的 な項 を 取 り出す と,
AIC(a1,a2,...,aM,δ)=ノVln∂2+2(M+1)
⑲と な る 。
以 上 よ り,解 空 間 か ら 得 ら れ た 時 系 列 デ ー タ に 対 し て,㈲ 式 か らa1, a2,...,aMと ㈹ 式 か ら δ を 求 め る 。 ⑲ 式 を 計 算 しAICが 最 小 と な る よ う に,M, a1,δ12,̲,δ肱,∂ を 定 め れ ば よ い 。
そ こ で,表1,2に 頂 点 数 が100と500に 対 す るMが0か ら4の 場 合 の 自 己 回 帰 係 数 の 推 定 値 と 情 報 量 基 準 の 値 を 記 し て お く。 た だ し,時 系 列 上 か ら取 る デ ー タ に よ っ て 多 少 の 値 の 変 化 は 見 ら れ る が,多 く の ケ ー ス の 場 合,α2以 降 は0に 近 い 値 と な り,実 質 上 は0に 近 似 で き る も の と考 え て も 問 題 は な い で あ ろ う 。 そ こ で,表1,2で は α2以 降 の 値 が 他 よ り モ デ ル に 影 響 を 与 え る で あ ろ う ケ ー ス を 記 し て お く 。 こ の 結 果 に よ る と,頂 点 数 が100,及 び500の2つ の 場 合 に お い て,共 にM=1,す な わ ちAR(1)モ デ ル の ケ ー ス の 情 報 量 基 準 が 最 小 と な り,よ り,真 の モ デ ル に 近 い こ と を 意 味 す る 。 ま た,自 己 相 関 関 数 も㈲
式 と 一 致 し て お りモ デ ル の 正 当 性 が 示 さ れ る 。
組合 せ最 適化 問題 に対 す る近傍 集合 の解 析 表1:自 己回 帰係数 の 推定 と情報 量 基準(頂 点 数100)
5ヱ
必
α1 α2 α3 α4 AIC
0■⊥9臼り04
0.979 0.986 0.980 0.968
一 〇.009
‑0 .02
0.012
0.018
0.01 一 〇 .010
22582.0
‑9236 .9
‑8997 .4
‑8760 .6
‑8991 .9
表2自 己回帰 係数 の推 定 と情報 量 基準(頂 点 数500)
M α1 α2 α3 α4 AIC
0■⊥9臼3バ4
0.9959 1.0032 0.9962 0.9834
一 〇 .0073
0.0131‑0.0127
0.02670.0034
39268.3
‑9443 .7
‑9047 .4
‑9146 .9
‑0 .0173‑8866.7
4近 傍 集合 の分 布 に対 す る解 析
評 価 値 ラ ン ドス ケ ー プ 上 の ラ ン ダム ウ ォ ー クか ら得 られ る統 計 的 性 質 の知 識 と して解 空 間 の 基 本 的諸 量 が 導 出 され た。 こ こで 導 か れ た 統 計 的性 質 の 知 識 を 用 い て他 の性 質 を推 定 で き う る。 そ こ か らモ デ ル の仮 定 よ り評 価 値 ラ ン ドス ケ ー プ 上 の 重 要 な 局 所 的 な 特 徴 を推 論 して い く こ と とな る。Weinbergerは 評 価 値 ラ ン ドス ケ ー プ上 で,状 態 κの 評価 値 が 与 え られ た も とで の 次 の 状 態 ッ の 評 価 値 の 分 布 に 関 す る期 待 値,分 散 の 推 定 を示 して い る 。 これ は 時系 列 上 の2 点 間 に 着 目 し,次 の移 動 す る状 態 が 振 舞 う予 測 の モ デ ル に よ り導 か れ た 値 で あ る。
しか し,組 合 せ 最 適 化 問 題 で は 多 数 の近 傍 点 を有 して お り,近 傍 集 合 全 体 を 捉 え た 分 布 の モ デ ル と して 表 現 は され て い な い 。 ま た,本 節 で導 出 され る各 種
の 統 計 量 を 求 め る に は 不 十 分 な モ デ ル で も あ る 。 そ こ で,複 雑 な 近 傍 の 構 造 を 表 す モ デ ル で 再 検 討 し,単 純 な 近 傍 点 で な く 近 傍 構 造 を確 率 的 に 表 現 し て い く 。
特 徴 と し て,AR(1)か ら 求 め ら れ た 統 計 的 性 質 が こ の モ デ ル の 上 で も よ い 近 似 と し て 働 き,特 定 の 問 題,あ る い は 特 定 の 近 傍 の み に 限 定 す る こ と な く,多
く の 知 識 が 推 定 で き る こ と と な る 。 ま た,AR(1)か ら 求 め ら れ た 統 計 的 性 質 と 組 み 合 わ せ て,こ こ で 示 し た 近 傍 構 造 の モ デ ル に よ り,さ ら な る 性 質 を 導 く可 能 性 を 広 げ て い く も の で あ る 。
モ デ ル を 考 察 す る た め に,ま ず,任 意 の 解 をXoと し て,解Xoに 対 す る 近 傍 解 の 集 合 を{κ1,κ2,...,κb}と 考 え る 。bは 近 傍 解 の 個 数 で あ る 。f(XO)を 解XOの コ ス トの 確 率 変 数 と す る と,そ の 近 傍 解 の 確 率 変 数 は!(x1),̲,f(κb)で あ り,そ れ ぞ れ が と る 値 はCO,Cl,...Cbで 表 す 。 こ こ で,任 意 の 解XOが コ ス トCOを 持 つ
と き の 解XOの 近 傍 構 造 を 確 率 的 に 考 察 す る 。 す な わ ち,f(XO)ニCOが 与 え ら れ た 条 件 の も と で,げ(κ1),̲,f(Xb))の 条 件 付 多 変 量 分 布 の 確 率 密 度 関 数 h(Cl,̲,CblCo)を 導 出 す る こ と に よ りそ の 近 傍 構 造 を 明 ら か に し た い 。 こ の と
き,X=(f(x1),...,f(Xb),ノ=●(Xo))の 結 合 確 率 分 布 が 多 変 量 正 規 分 布 を 示 す(X〜
Nb+1(m,Σ))と 仮 定 し た な ら ば,h(Cl,̲,CblCO)は 多 変 量 正 規 分 布Nb(m',Σ') と な る こ と が 言 わ れ て い る[4]。 こ の 平 均 ベ グ ト ルM'と 共 分 散 行 列 Σ'を 導 き,分 布 の 特 徴 を 特 定 す る 。 そ の た め に,結 合 確 率 分 布X〜Nb+1(m,Σ)の
モ デ ル を 詳 細 に し て お く必 要 が あ る 。 こ こ で 対 象 と な るX,m,Σ の 要 素 は
12 22 Σ Σ
11 21 Σ Σ ー
= Σ
エユ ワ ロ m m ー
一㎜
m弘
ユ ワ ロ X X ー
=
X た ま
むるれさ表で割分の
Xl=げ(x1),̲,f(κb))t,X2ニ(f(Xo))
㈲
⑳
で あ り,対 応 す る平 均 ベ ク トル の各 要 素 は
m、 ニ(〃Z、,̲"Mb)t,m2=(m。)
㈲と な る 。 ま た,Σ11はf(Xi),i=1̲bと!(吻),ブ=1̲bに 対 す る 共 分 散 行 列 で あ
組合 せ最 適化 問題 に対 す る近傍 集合 の解析
53 り,そ の 各 要 素 を 笏,i,ブ=1̲bと 記 す 。 Σ22=(roo)はf(Xo)の 分 散 と な る 。 そ し て,Σ12と Σ21ニ(riO)は!(Xo)とf(Ci);iニ1,。..,bと の 共 分 散 行 列 を 表 す も の で あ る 。
さ て,こ こ で 必 要 と さ れ る 各 要 素 の 値 は,AR(1)の 特 性 か ら導 き 出 し た 基 礎 的 な 統 計 量 を 用 い て 決 定 す る こ と が 可 能 で あ る 。 こ れ ら の 値 を 用 い て 有 効 な 推 定 が 可 能 で あ る か を 検 証 し た い 。 前 述 し た よ う に 組 合 せ 最 適 化 問 題 の 評 価 値 ラ ン ドス ケ ー プ がAR(1)で あ る と こ ろ か ら,導 き 出 さ れ た(4)式 か ら ⑳ 式 の 性 質, お よ び,近 傍 解 と の 相 関 関 数 値 な ど よ り,
〃Zi=μ,i=0,1,...,b
η ゴ=σ2,i=o,1,̲,b
riO,rOiニ ρ,i=1,...,1う
笏=り,i≠ ブ,i,ブ=1,…,b
(23)
②の (25) (26)
と し て,X〜Nb+1(m,Σ)の モ デ ル を 完 成 す る こ と が で き う る 。
そ こ で,h(C1,̲,CbICO)の 分 布 を 導 出 し 近 傍 の 確 率 分 布 を 特 定 し た い 。 前 述 し たX〜Nb+1(m,Σ)の 仮 定 の も と,X2の 要 素 がf(Xo)=Coと し て 与 え ら れ れ たX1の 条 件 付 分 布Nb(m「,Σ')のm'と Σ!は
m・=m1+Σ12Σ 記(CO‑m2)=(㎡), Σ ノ=Σ11一 Σ12ΣsiΣ2i=(「ij)
②の
②⑳
と な る こ とが 知 ら れ て い る[4]。 す で にAR(1)か ら 得 ら れ た 基 礎 統 計 量 に よ り, 上 式 の 各 要 素 の 値 は 導 く こ とが 可 能 で あ る 。 近 傍 の 多 変 量 正 規 分 布 の 各 々 の 確 率 変 数 の 期 待 値 は 〃zー ゴ=〃z'=μ+ρ(Co一 μ);iニ1,...,bと な り,各 々 の 分 散 は 〆ii=σ2(1一 ρ2);i=1,̲,bと し て 必 要 な モ ー メ ン トが 導 出 可 能 と な る 。
次 に,近 傍 の 構 成 を 示 す 値 と し て,解 κ0の コ ス ト をCOと し た 場 合,解 κ0
近 傍 の 最 小 値 をAR(1)の 情 報 に 基 づ き 推 定 し た い 。 こ の 値 を 求 め る た め に 重 要
な 確 率 と し て 以 下 の ス テ ッ プ 確 率 が あ る[1]。
9(C。,C)=Pr{。i∈{、,̲,b}撫)>Clf(X・)=・ ・}
㈲こ れ は 解Xoが コス トCoを 持 つ と き,そ の 近 傍 の す べ て が コス トcよ り大 で あ る 確 率 を示 す 。 さ ら に,こ の ス テ ップ 確 率 を 用 い て,コ ス トCoの 解 か ら コス
トcの 解 へ 移 動 す る確 率 密 度 が
∂
P(c・・c)‑i響 留 ㈹
の 式 で 導 出 され る[1]。
今 回,こ の ㊨①式 を 用 い て,
」二=二c1・)(c()tc)dc
⑳を解XOの コス トCOが 与 え ら れ た もの と し て の 解XOの 近 傍 の 最 小 値 の 推 定 値 とす る。
問 題 は ス テ ッ プ確 率 ㈲ 式 を 導 出 す る こ と に帰 着 さ れ る。 こ の値 を求 め る こ と に よ り,㈹,⑳ 式 が 求 ま る こ と と な る 。 そ の ス デ ッ プ確 率 は先 に求 め たAR(1) モ デ ル か らの 基 礎 統 計 量 を用 い て 導 出 した 近 傍 の 確 率 密 度 関{Sth(Ci,̲,CblCO) に 対 して
9(C…)‑f
c..… ∫ ○.h(・…'・…IC・)dc・ …dCb
㈱の よ う に 求 め る こ と が で き る 。 こ れ に よ っ て 特 定 の 問 題,特 定 の 近 傍 に 限 定 す る こ と な く ス テ ッ プ 確 率 が 計 算 さ れ る 。h(C1,̲,CblCO)は 多 変 量 正 規 分 布 砺(㎡,Σ')に 対 応 す る 。 し か し,働 式 の 多 重 積 分 の 計 算 は 数 値 的 に も 計 算 は 容 易 で な い 。 そ こ で,多 次 元 変 数 を 単 一 化 し て 一 重 積 分 に 簡 単 化 し た ス テ ッ プ 確 率 の 導 出 を 示 し て お く。 ま ず,Tongの 定 理(Theorem3.3.3)[4]を 用 い る こ と に よ り,近 傍 集 合 を 表 すb変 量 確 率 ベ ク トルX1ニ げ(x1),̲,f(Xb))〜
Nb(m',Σ')を 独 立 し たb+1変 量 標 準 正 規 分 布 の 確 率 ベ ク トルY=(yo,Y1,...Yb)
組 合 せ 最 適 化 問 題 に対 す る 近 傍 集 合 の 解 析55
〜Nb+1(0 ,Ib+1)で 構 成 で き る 。 す な わ ち,X1=CY+m'で 変i換 で き る 。 た だ し,Cはb×(b+1)の 行 列
Cニ α β10
β01
(33)
で あ り,こ こ で,
α=σVI="Tv(34)
β=(レ ー ρ2)/(1一 り)(35>
で あ る も の と す る 。 こ のX1=CY+mノ とYの 独 立 し た 標 準 正 規 分 布 性 か ら ス テ ッ プ 確 率 圃 式 を
9(Co,c) ニPr{。i∈[、
,̲,b]f(Xi)>C}=Pr{∀i∈[、,̲,b]yi>一 の 。+(C‑m')/α}
一 か{・i∈[1
,...,b]yi〉‑By・+(C‑m')/ψ ・一 ・ 蹄 ・‑S}ds
1。 。s2
=m
..exp‑‑ll"lp・1・i∈[・ ・ … ・ ・]・Yi>一 β・+￠‑m')/α}ds
一 毒=一 妥 滋 ∫ 二
.(,.m,)/a一 号
一献 鶉 罐 〔一差・+
α諺
と 導 出 す る こ と が で き る 。 ま た,(30)式 は
恥 ・)一⑳ 一添 。。))∫二・書
・σ毒 摩 〕う∴ 一囁
ー ー ー
8 ε 〜 r ⊥ 〜 Prトしーー ー ー
呵 〕小
￠‑m・)〕〕bds
/
(36)
(37)
と計 算 さ れ る 。 た だ し,
u‑‑sv一 ρ2+1 ￠ 一 ρCo+(ρ 一1)μ) σ画2‑2レ
で あ る 。 以 上 よ り,⑳ 式 が 数 値 計 算 的 に 計 算 可 能 と な る 。
㈹
5お わ り に
計 算 困 難 な組 合 せ 最 適 化 問 題 の近 似 解 を求 め るた め の 手 法 と して メ タ ヒ ュ ー リス テ ィ ック ス の研 究,開 発 が な さ れ て い る。 この 手 法 の ベ ー ス とな る近 傍 構 造 を解 析 す る こ と は,近 傍 生 成 な どに お け る知 識獲 得 を 可 能 と し,メ タ ヒ ュ ー リ ス テ ィ ック ス の 改 良へ とつ な げ る 知 見 とな り う る。 ま た,ア ル ゴ リズ ム の 良
し悪 し を解 析 す る た め の確 率 的 解 析 の 基 本 的情 報 を も提 供 す る もの で あ る。
そ こ で本 論 分 で は,近 傍 の 分 布 の特 性 を確 率 的 に解 析 す るた め に,解 空 間 の構 造 を統 計 的 に明 らか に した。解 空 間の 特 性 を示 す各 種 の統 計 量 を導 出 す るた め に, 解 空 間がAR(1)プ ロ セ ス と呼 ば れ る特 徴 的 な性 質 を有 す る とい う仮 定 を検 証 し, そ こ か ら必 要 な 統 計 量 を導 き出 した 。 さ ら に,AR(1)モ デ ル か ら導 き出 した統 計 量 を用 い て 近 傍構 造 を確 率 的 に モ デ ル化 し,近 傍 の特 性 の解 析 に成 功 した。
確 率 的 な解 析 で は通 常,モ デ ル を構 築 しや す い よ う に,特 定 の 問 題,お よび 特 定 の 近 傍 な ど を設 定 して,こ の よ う な統 計 量 を導 出 す る 。 しか し,こ こ で提 唱 す るAR(1)プ ロ セ ス を用 い る こ とに よ り,多 くの組 合 せ 最 適 化 問 題,あ る い は 各 種 の 近 傍 な ど に 対 応 す る 汎 用 的 な 解 析 が 可 能 とな っ た と こ ろ に 特 徴 が あ り,汎 用 性 に 富 ん だ有 効 な解 析 方 法 が 示 さ れ た もの で あ る 。 今 後 は さ ら に ア ル ゴ リズ ム の特 性 を示 す 解 析 モ デ ル の構 築,お よび,本 論 分 で 得 られ た 近 傍 構 造 の情 報 を も と に有 効 な 手 法 の 開発 を試 み た い 。
組合 せ最 適化 問題 に対 す る近傍 集合 の解析
57
参 考 文 献 [1]
[2]
[3]
[4]
[5]
Eikelder,H.M.M.,Verhoeven,M.G.A.,Vossen,T.W.M.andAarts,E.H.L.,"A ProbabilisticAnalysisofLocalSearch",inMeta‑Heuristics:Theory&Appli‑
cations,ed.Osman,LO.andKelly,J.P.,KluwerAcademicPublishers, pp.605618,1996.
Kaji,T.,"ProbabilisticAnalysisofLocalSearchusingAR(1)Modelinthe GraphPartitioningProblem",Proc.oftheFifthMetaheuristicsInternational Conference,PaperID38(2003).
Priestley,M.B.,"SpectralAnalysisandTimeSeries",AcademicPress,1981.
Tong,Y.L.,"TheMultivariateNormalDistribution",Springer‑Verlag,1990.
Weinberger,E,"CorrelatedandUncorrelatedFitnessLandscapesandHow toTelltheDifference",BiologicalCybernetics,Vol.63,pp.325‑336,1990.
