Neighborhood Parallel Simulated Annealing

Transactions of JSCES, Paper No.20060026

近傍並列シミュレーテッドアニーリング

^∗

Neighborhood Parallel Simulated Annealing

安藤 景子

¹

，三木 光範

²

，廣安 知之

²

，及川雅隆

³

Keiko ANDO, Mitsunori MIKI, Tomoyuki HIROYASU, Masataka OIKAWA

1

同 志 社 大 学 大 学 院

(〒610-0394

京 田 辺 市 多 田 羅 都 谷

1-3)

2

同 志 社 大 学 工 学 部

(〒610-0394

京 田 辺 市 多 田 羅 都 谷

1-3)

3

奈 良 先 端 科 学 技 術 大 学 院 大 学

(〒630-0192

奈 良 県 生 駒 市 高 山 町

8916-5 )

When applying SA to continuous optimization problems, the appropriate adjustment of the neighborhood ranges becomes necessary to obtain the good performance. In this paper, we propose a Neighborhood Parallel Simulated Annealing (NPSA) for continuous optimization problems, which provides global search using the periodic exchange of different neighborhood ranges with parallel computers. The proposed approach, NPSA, automatically determines the appropriate neighborhood range, and shows a good perforamance in solving typical test problems.

Key Words : Parallel Simulated Annealing, Continuous Optimization Problem, Neighborhood Range

1.

はじめに

近 年 ，社 会 を 構 成 す る シ ス テ ム は 大 規 模 ，複 雑 化 が 進 み ，そ れ に 伴 い シ ス テ ム の 最 適 化 が 重 要 と なって い る ．最 適 化 問 題 と は ，与 え ら れ た 制 約 条 件 の も と で そ の 評 価 関 数 を 最 大 ま た は 最 小 に す る 最 適 解 を 求 め る 問 題 の こ と を い い ，実 世 界 の 多 く の 場 面 で 見 ら れ る ．最 適 化 問 題 は ，設 計 変 数 が 連 続 で あ る 連 続 最 適 化 問 題 と 設 計 変 数 が 離 散 的 で あ る 組 合 せ 最 適 化 問 題 に 分 類 で き る ．前 者 の 問 題 は ，主 に 目 的 関 数 の 勾 配 情 報 を も と に 連続的な探索を行い最適解を求めることが多い．一方，

後 者 の 問 題 で は 汎 用 的 な 確 率 的 ア ル ゴ リ ズ ム に よ り 準 最 適 解 を 求 め る こ と が 多 く，発 見 的 手 法

(

ヒュー リ ス ティック 法

)

で あ る 遺 伝 的 ア ル ゴ リ ズ ム

(GA)

や シ ミュ レ ー テッド ア ニ ー リ ン グ

(SA)

な ど が 用 い ら れ る

⁽¹⁾

．

SA

は

Metropolis

ら が

1953

年 に 発 表 し た 焼 き な ま し と 呼 ば れ る 加 熱 炉 内 の 固 体 の 冷 却 過 程 を シ ミュレ ー ト す る ア ル ゴ リ ズ ム に 端 を 発 し ，最 適 化 問 題 ，特 に 組 み

合わせ最適化問題に有効なアルゴリズムである．

SA

で

は ，最 小 化 す べ き 目 的 関 数 は エ ネ ル ギ ー と 呼 ば れ ，任 意 の 非 線 形 性 を 持った 目 的 関 数 を ほ と ん ど 処 理 で き る と い う 大 き な 利 点 が あ る

^{(2, 3, 4)}

．

∗ 原 稿 受 付

2006

年

6

月

16

日, 改 訂 年 月 日

2006

年

8

月

29

日,発 行 年 月 日

2006

年

9

月

8

日, c

2006

年 日 本 計 算 工 学 会 ．

Manuscript received, June 16, 2006; final revision, August 29, 2006; published, September 8, 2006. Copyright c 2006 by the Japan Society for Computational Engineering and Science.

SA

は

GA

等 と 同 じ く 非 線 形 性 を 持 つ 種々の 目 的 関 数 を 処 理 で き る と い う 大 き な 利 点 が あ る が ，

2

つ の 欠 点 が 存 在 す る ．

1

つ は ，解 探 索 の 振 る 舞 い を 決 め る パ ラ メ ー タ の 決 定 が 困 難 で あ る と い う こ と で あ り，も う

1

つ は 解 を 得 る ま で の 計 算 時 間 が 長 い と い う こ と で あ る

(5)

．

SA

で 重 要 と な る パ ラ メ ー タ は ，近 傍 と 温 度 で あ る ． 組 み 合 わ せ 最 適 化 問 題 の 場 合 で は ，隣 接 す る

2

つ の 要 素 を 入 れ 替 え る な ど し て 近 傍 を 生 成 す る ．こ の た め ， 近 傍 の 構 造 を 適 当 に 決 め る と ，温 度 ス ケ ジュー ル の 調 節 が 最 も 重 要 と な る ．

一 方 ，連 続 最 適 化 問 題 に

SA

を 適 用 す る 場 合 ，近 傍 は ユ ー ク リッド 空 間 内 で の 距 離 に 関 係 し ，自 由 に 決 め る こ と が 可 能 で あ る ．一 般 的 に ，近 傍 が 小 さ い 場 合 に は エ ネ ル ギ ー の 変 化 が 小 さ く，近 傍 が 大 き い 場 合 に は エ ネ ル ギ ー の 変 化 が 大 き い ．ま た そ の 変 化 は 目 的 関 数 の ラ ン ド ス ケ ー プ に 大 き く 依 存 す る ．そ の た め ，連 続 最 適 化 問 題 に

SA

を 適 用 す る 場 合 ，近 傍 の 調 節 が 非 常 に重要になるが，それを一意に定義することは難しい．

こ れ に 対 し ，目 的 関 数 の ラ ン ド ス ケ ー プ に 応 じ た 近 傍 を 適 応 的 に 調 節 す る 研 究 が 行わ れて いる ．

Corana

は 解摂動に用いる近傍を受理率が

0.5

となるように，ラン ド ス ケ ー プ に 応 じ た 近 傍 調 節 を 自 動 化 し た

⁽⁶⁾

．ま た 、 著 者 ら は 任 意 の 受 理 率 を 与 え る こ と の で き る 新 し い 近 傍 設 計 を 考 え ，最 適 な 受 理 確 率 を 目 標 と す る 適 応 的 近 傍 を 持 つ シュミ レ ー テッド ア ニ ー リ ン グ

(SA/AAN)

を 提 案 し た

^{(7, 8)}

．こ れ ら の 手 法 は ，近 傍 の 自 動 調 節 を 行 う た め ，問 題 ご と の チュー ニ ン グ は 必 要 な い が ，近 傍

の 自 動 調 節 の た め の パ ラ メ ー タ が 必 要 と な る ． そ こ で 本 研 究 で は ，近 傍 の 調 節 を 自 動 化 し ，か つ 近 傍 調 節 の た め の パ ラ メ ー タ を 必 要 と し な い 手 法 ，近 傍 並 列

SA

（

Neighborhood Parallel Simulated Annealing

：

NPSA

）を 提 案 す る ．

NPSA

で は 並 列 処 理 を 行 い ，各 プ ロ セ ス に 異 な る 近 傍 を 与 え る ．そ の 近 傍 を プ ロ セ ス 間 で 交 換 す る こ と に よ り，近 傍 の 自 動 調 節 を 行 う．

本論文では，まず解探索が良好に行える近傍について 検証を行う．次に，提案手法である近傍並列

SA(NPSA)

に つ い て 述 べ る ．最 後 に ，代 表 的 な 数 学 関 数 最 小 化 問 題 に 本 手 法 を 適 用 し ，解 探 索 能 力 と 近 傍 履 歴 に つ い て 検 証 す る ．

2.

最適な近傍

SA

では，次状態は現在の状態に摂動を加えることで

生 成 さ れ る ．摂 動 に よ り 生 成 さ れ る 次 状 態 の 範 囲 の こ と を 近 傍 と 呼 び ，連 続 最 適 化 問 題 の 場 合 ，近 傍 は ユ ー ク リッド 空 間 の 距 離 と し て 与 え ら れ る ．ま た 本 論 文 で は ，そ の 距 離 の 最 大 値 を 近 傍 幅 と 呼 ぶ ．

SA

では，一般に現在の解を中心とし，解摂動のため

の 移 動 距 離 に 関 す る 確 率 分 布 を 与 え る こ と に よ り 近 傍 を 定 義 す る 方 法 が 一 般 的 で あ る

⁽⁹⁾

．こ の 場 合 ，解 摂 動 の た め の 近 傍 幅 を 考 え る こ と が 重 要 に な り，近 傍 幅 を 一 定 と し 探 索 を 行 う ア ル ゴ リ ズ ム

⁽¹⁰⁾

，温 度 を 用 い て 近 傍 幅 を 決 定 す る ア ル ゴ リ ズ ム

⁽¹¹⁾

，目 的 関 数 の ラ ン ド ス ケ ー プ に 従 い 適 応 的 に 近 傍 幅 を 決 定 す る ア ル ゴ リ ズ ム

^{(6, 7, 8)}

な ど が あ る ．

近傍幅が大きすぎる場合は得られる解の精度が悪く，

小 さ す ぎ る 場 合 は 探 索 の 進 行 が 遅 く な る た め ，近 傍 幅 の 定 義 が 難 し い ．そ こ で ，最 適 な 近 傍 幅 を 求 め る た め ， 種々の 近 傍 幅 に 対 し て 数 値 実 験 を 行った ．後 に 説 明 す る 連 続 最 適 化 問 題 に お け る 標 準 的 な テ ス ト 関 数 で あ る

Rastrigin

関 数 お よ び

Griewank

関 数 に 対 し て ，探 索 開 始 時 か ら 終 了 時 ま で 一 定 の 近 傍 幅

(

固 定 近 傍 幅

)

と し ， 近 傍 幅 は 最 大 で 設 計 空 間 の 幅 ，最 小 の 近 傍 幅 と し て そ の

10

⁻³と し ，こ の 間 を 指 数 的 に

100

分 割 し ，

100

種 類 の 近 傍 に つ い て 実 験 を 行った ．ま た 数 値 実 験 で は ，近 傍 構 造 に 用 い る 確 率 分 布 と し て 一 様 分 布 を 用 い た ．結 果 を 図

1

お よ び 図

2

に 示 す．こ れ ら の 図 の 横 軸 が 近 傍 ， 縦 軸 が エ ネ ル ギ ー 値 を 表 し ，

2

，

3

次 元 の 結 果 を 示 し て い る ，こ れ ら の 結 果 に は

30

試 行 の 中 央 値 を 用 い る ．

図

1

お よ び 図

2

よ り，

Rastrigin

関 数 で は 近 傍 が

1

，

Griewank

関 数 で は

2

次 元 の 場 合

6

，

3

次 元 の 場 合

8

で あ る 場 合 ，最 も 効 率 の 良 い 探 索 が 行 え て お り，問 題 毎 に 最 適 な 近 傍 幅 が 存 在 す る と 言 え る ．

こ れ ら の 結 果 か ら ，対 象 問 題 ご と 次 元 ご と に 最 適 な 近 傍 幅 を 特 定 す る こ と が で き れ ば ，そ の 近 傍 幅 で 集 中 的 に 探 索 を 行 う こ と で 良 好 な 結 果 を 得 る こ と が で き る と 考 え ら れ る ．し か し ，最 適 な 近 傍 幅 を 求 め る た め に は ，多 く の 予 備 実 験 が 必 要 と な る ．ま た ，最 適 な 近 傍 幅 は 問 題 ご と に 異 な る た め ，最 適 な 近 傍 幅 を 一 意 に 定 義 す る こ と は 難 し い ．

10 10 10

1E-2 1E-1 1E+0 1E-1

1E+2 &KOGPUKQP

&KOGPUKQP

Energy

Neighborhood range

-2 -1 0

Fig.1 Appropriate Neighborhood range (Rastrigin)

1E-6 1E-4 1E-2 1E+0 1E+2

Energy

Neighborhood range

&KOGPUKQP

&KOGPUKQP

10⁰ 10¹ 10²

Fig.2 Appropriate Neighborhood range (Griewank)

こ れ に 対 し ，温 度 を 用 い て 近 傍 幅 を 決 定 す る ア ル ゴ リ ズ ム は ，温 度 の 高 低 に よ り 近 傍 幅 を 決 定 す る も の で あ り，そ れ ら は 正 規 分 布 の 近 傍 構 造 を 持 ち ，標 準 偏 差 に 温 度 を 用 い る

Boltzman

ア ニ ー リ ン グ，コ ー シ ー 分 布 の 高 速 ア ニ ー リ ン グ な ど が あ る ．こ れ ら の ア ル ゴ リ ズ ム で は ，温 度 が 高 い 場 合 は 近 傍 幅 が 大 き く，温 度 が 低 い場合は近傍幅が小さくなるため，高温では大域探索，

低 温 で は 局 所 探 索 を 行 え る ．し か し こ の 方 法 で は ，近 傍 幅 と 温 度 が 密 接 に 関 係 し て い る た め ，適 切 な 温 度 ス ケ ジュー ル の 設 定 が 難 し く，ま た 目 的 関 数 の ラ ン ド ス ケ ー プ を 考 慮 す る こ と が 出 来 な い と い う 問 題 が あ る ．

一 方 ，近 傍 幅 を 問 題 に 応 じ て 適 応 的 に 決 め る 方 法 は 前 述 し た 様 に い く つ か 存 在 す る ．こ れ ら の 方 法 で は ， 適 応 的 な 近 傍 幅 調 節 に 用 い る パ ラ メ ー タ を 与 え れ ば ， 問 題 と 探 索 状 況 に 応 じ て 適 切 な 近 傍 を 自 動 的 に 求 め る こ と が で き る ．

SA

では現状態から次状態を生成する際，現状態から

近 傍 の 範 囲 内 に 次 状 態 を 生 成 し ，そ の エ ネ ル ギ ー 値 を 求 め る ．次 状 態 の エ ネ ル ギ ー 値 が 現 状 態 の エ ネ ル ギ ー 値 よ り 低 い 場 合 は 現 状 態 は 次 状 態 に 推 移 し ，現 状 態 の エ ネ ル ギ ー 値 よ り 高 かった 場 合 は

Metropolis

基 準 を 用 い 確 率 的 に 次 状 態 に 推 移 す る ．

Corana

は ，現 状 態 か ら 次 状 態 に 推 移 す る 確 率

(

受 理 率

)

が

0.5

と な る よ う に 近 傍 を 適 応 的 に 変 化 させ 探 索を

行う手法を提案した．しかし，受理率を

0.5

とする妥当 性 が 明 ら か と なって い な かった た め ，著 者 ら は 任 意 の 受 理 率 に な る よ う な 近 傍 調 節 が 可 能 と な る 手 法 ，最 適 な 受 理 確 率 を 目 標 と す る 適 応 的 近 傍 を も つ シ ミュレ ー テッド ア ニ ー リ ン グ

(SA/AAN)

を 提 案 し た ．

Corana

の手法，

SA/AAN

は問題ごとに最適近傍を求

め る 必 要 が な い 優 れ た 手 法 で あ る が ，あ る 周 期 ご と に 周 期 内 で の 受 理 率 を 基 に 近 傍 幅 を 拡 大 ，縮 小 し 近 傍 を 適応的に調節するため，基準となる受理率

(Corana:0.5

，

SA/AAN

：任意の値

)

と近傍幅を拡大，縮小するパラメー

タ が 必 要 と な る ．

近 傍 の 定 義 方 法 は 前 述 し た 様 に 種々存 在 す る が ，適 応 的 な 手 法 を 用 い た 場 合 で も ，近 傍 調 節 の た め の 最 低 限 の パ ラ メ ー タ が 必 要 に な る こ と か ら 分 か る よ う に ， 最 適 な 近 傍 を 対 象 問 題 に 依 存 す る こ と な く 自 動 的 に 求 め る こ と は ，非 常 に 難 し い と 言 え る ．

3.

近傍並列

SA

（

NPSA

）

3.1

近 傍 並 列

SA

（

NPSA

）の コ ン セ プ ト

本 論 文 で は ，近 傍 の 適 応 的 調 節 を 行 い ，か つ 調 節 の

ためのパラメータ

(

基準となる受理率，近傍の拡大，縮

小 の た め の パ ラ メ ー タ

)

が 不 要 と な る 新 し い 近 傍 調 節 メ カ ニ ズ ム を 持 つ 手 法

(NPSA)

を 提 案 す る ．

NPSA

で

は，異なった近傍を持つ複数の

SA

を同時並列的に動作

さ せ ，一 定 の ア ニ ー リ ン グ 周 期 ご と に プ ロ セ ス 間 で 通 信 を 行 う．全 プ ロ セ ス の エ ネ ル ギ ー 値 か ら 各 プ ロ セ ス の エ ネ ル ギ ー 値 の 相 対 評 価 を 行 い ，そ の 評 価 に 従 い エ ネ ル ギ ー 値 の 高 い プ ロ セ ス に は 大 き な 近 傍 を 与 え 大 域 探 索 を ，エ ネ ル ギ ー 値 の 小 さ い プ ロ セ ス に は 小 さ な 近 傍 を 与 え 局 所 探 索 が 行 え る よ う に 近 傍 を 交 換 す る ．こ の よ う に 操 作 を 繰 り 返 す こ と で ，探 索 に 応 じ た 適 切 な 近 傍 が 与 え ら れ る と 考 え ら れ る ．

Each processor has

a different neighborhood. Neighborhood are adjusted at each cooling step Gather energy

Assign neighborhood in order of energy

Sort Adjust Neighborhood

Adjust Neighborhood

New neighborhood are assigned for all SA processes.

Adjust Neighborhood

SA

SA

SA

SA SA

SA

SA

SA

SA

SA

SA

SA SA

SA

SA

SA

Fig.3 Algorithm of NPSA

3.2

近 傍 並 列

SA

（

NPSA

）の ア ル ゴ リ ズ ム

NPSA

は 並 列 プ ロ セ ス に 対 し て そ れ ぞ れ 異 な る 近 傍 幅 を 与 え ，各 プ ロ セ ス は そ の 近 傍 幅 で 探 索 を 行 う．ま た ，周 期 的 に 全 プ ロ セ ス の 同 期 を と り プ ロ セ ス 間 で 情 報 交 換 を 行 う．探 索 状 況 に 応 じ た 近 傍 幅 調 節 を 行 う た め ，探 索 状 況 が 安 定 し た 後 に 近 傍 幅 調 節 行 う 必 要 が あ る ．そ の た め ，近 傍 幅 調 節 は ク ー リ ン グ 周 期 と 同 時 に 行 う．同 期 時 に は ，各 プ ロ セ ス が 持 つ エ ネ ル ギ ー 値 を

1

つ の プ ロ セ ス に 集 め ，エ ネ ル ギ ー 値 を ソ ー ト し ，エ

ネ ル ギ ー 値 が 低 い 良 好 な 解 探 索 を 行 なって い る プ ロ セ ス か ら 順 に 小 さ な 近 傍 幅 が 設 定 さ れ る よ う 近 傍 幅 を 割 り 当 て る ．

こ う す る こ と に よ り，エ ネ ル ギ ー 値 の 小 さ い 良 好 な 解 探 索 を 行 なって い る プ ロ セ ス は 小 さ い 近 傍 幅 が 割 り 当 て ら れ る た め ，そ の 解 付 近 の 局 所 探 索 を さ ら に 進 め る こ と が で き る ．ま た ，エ ネ ル ギ ー 値 が 悪 い 局 所 解 に 陥って い る プ ロ セ ス に は 大 き な 近 傍 幅 が 割 り 当 て ら れ る た め ，大 域 探 索 を 行 う こ と に な り 局 所 解 か ら 抜 け 出 す こ と が 可 能 と な る ．こ の よ う に ，各 プ ロ セ ス は 他 の プ ロ セ ス と 協 調 し ，探 索 に 応 じ て 適 応 的 に 近 傍 幅 を 調 節 す る ．

NPSA

に お け る プ ロ セ ス 間 で の 近 傍 幅 交 換 の 概 念 図 を 図

3

に ，

NPSA

の ア ル ゴ リ ズ ム を 図

4

に 示 す．

Acceptance criterion

Terminal condition?

Cooling cycle?

Yes

Adjust Neighborhood

Yes No

No

No Yes

Set initial parameters

Transition

Synchronize

Sort energy

Assign neighborhood

End Generate next state Set

qφ Initial State:X^q Initial Temperature:T^q

X'=X +ӠX^{q q}

Probability=exp

(-

^ӠET^q

)

ӠE<0 or

Compute energy

ӠE=E(X')-E(E )^q

X φX'^q+1

Cooling

T φǩT (0<ǩ<1)^{q+1 q}

Fig.4 NPSA

の ア ル ゴ リ ズ ム

図 中 の

T

は 温 度 を

X

は 解 集 合 を 示 し ，

X

^qは 現 在 の 解 を

X’

は 次 状 態 の 候 補 解 を 示 す．ま た

E

は エ ネ ル ギ ー 値

(

評 価 値

)

を ，

∆E

は 現 在 の 解 と 次 状 態 候 補 の 解 と の エ ネ ル ギ ー 差 を 示 し ，

α

は 冷 却 率 を 示 す．

初 期 設 定

(Set initial parameters):

 

初 期 設 定 で は

NPSA

で 用 い る 近 傍 幅 の 種 類 を 設 定 す る た め ，最 大 近 傍 幅 ，最 小 近 傍 幅 お よ び プ ロ セ ス 数 を 設 定 す る ．

NPSA

で 用 い る 近 傍 幅 は ，最 大 近 傍 幅 を 設 計 空 間 の 幅 ，最 小 近 傍 幅 を そ の

10

⁻⁵と し ，そ の 中 間 の 近 傍 幅 は 等 比 的 に 割 り 振 り プ ロ セ ス 数 分 生 成 す る ．

本 手 法 で は 最 小 近 傍 幅 を 設 計 空 間 の

10

⁻⁵と す る が ， 要 求 さ れ る 解 精 度 に 合 わ せ て 設 定 す る こ と が 可 能 で あ る ．

Rastrigin

関 数 お よ び

Griewank

関 数 に 対 す る 最 小 近 傍 幅 と 精 度 の 関 係 を 図

5

に 示 す．図

5

の 横 軸 が 最 小 近 傍 幅 ，縦 軸 が エ ネ ル ギ ー 値 を 示 す．こ の 結 果 よ り 最 小 近 傍 幅 は 大 き す ぎ る と 精 度 に 影 響 す る が ，あ る 程 度 小 さ く す れ ば 良 い と い う こ と が 分 かった ．探 索 空 間 の

10

⁻⁵程 度 に 設 定 す る の が 妥 当 と 考 え ら れ る た め ，本 実 験 で は 探 索 空 間 の

10

⁻⁵と し た ．

NPSA

で は プ ロ セ ス 数 は 自 由 に 選 択 す る こ と が で き る た め ，用 い る こ と の で き る プ ロ セ ス の 数 に 合 わ し て 設 定 す る こ と が 可 能 で あ る ．た だ し ，プ ロ セ ス 数 は 隣 り 合 う プ ロ セ ス 同 士 の 近 傍 幅 の 比 率 と 関 係 す る ．探 索 領 域 の 連 続 性 の 観 点 か ら ，比 率 が

0.5

以 上 必 要 で あ る と 考 え ら れ る が ，プ ロ セ ス 数 が 多 い 場 合 に は 隣 り 合 う プ ロ セ ス と の 近 傍 幅 の 比 率 は 高 く な り，プ ロ セ ス 数 が 少 な い 場 合 に は 比 率 は 低 く な る ．比 率 が 小 さ す ぎ る 場 合 は 近 傍 幅 の 変 化 が 大 き す ぎ ，大 き す ぎ る 場 合 は 変 化 が 小 さ す ぎ 無 駄 に プ ロ セ ス 数 が 増 加 す る ．そ こ で ，問 題 の 特 徴 の 異 な る

2

つ の 関 数 を 用 い て プ ロ セ ス 数 と 性 能 に つ い て 調 べ る ．

Rastrigin

関 数 は 大 き な 局 所 解 を 無 数 に 持 つ 関 数 で あ り，

Griewank

関 数 は 大 域 的 に は 単 峰 で あ り 局 所 的 に は 局 所 解 が 無 数 に 存 在 す る と い う 特 徴 を 持 つ ．ま た ，プ ロ セ ス 数

16

の 場 合 は 隣 り 合 う プ ロ セ ス と の 近 傍 幅 の 比 率 が

0.5

で あ り，

32

の 場 合 は 比 率 が

0.7

程 度 と な る ．図

6

に 結 果 を 示 す．図

6

の 横 軸 が プ ロ セス数，縦軸がエネルギー値を示す．この結果より，最 適 な プ ロ セ ス 数

(

比 率

)

は 問 題 の 特 徴 に よ り 異 な る の で は な く，比 率 が

0.5

で あ る

16

プ ロ セ ス 以 上 は 必 要 で あ る と 言 え る ．ま た ，プ ロ セ ス 数 を 増 や し す ぎ て も 大 き く 精 度 の 影 響 し な い こ と よ り

32

プ ロ セ ス 程 度 で 十 分 で あ る と 考 え ら れ る ．

10 10 10 10

1E-7 1E-5 1E-3 1E-1

Energy

Minimum neighborhood range

Rastrigin (2 Dimension Rastrigin (3 Dimension) Griewank (2 Dimension) Griewank (3 Dimension) W: maximum neighborhood range

(width of design space)

-1 -3 -5 -7

˜W

Fig.5 Minimum Neighborhood range

解 の 生 成 ，受 理 判 定 ，状 態 遷 移 ，ク ー リ ン グ

(Gener-

8 16 32 64

1E-7 1E-5 1E-3 1E-1 1E+1

Energy

Number of processors

Rastrigin (2 Dimension) Rastrigin (3 Dimension) Greiwank (2 Dimension) Greiwank (3 Dimension)

Fig.6 Number of Processors using NPSA

ate next state, Acceptance criterion, Transition

，

Cooling) :

 

解の生成

(Generate next state)

では，現状態から近傍の 範 囲 内 に 次 状 態 を 生 成 す る 処 理 を 行 う．受 理 判 定

(Ac- ceptance criterion)

で は ，現 状 態 か ら 次 状 態 へ 推 移 す る か を

Metropolis

基 準 に 基 づ い て 判 断 を 行 う．受 理 さ れ た 場 合 は ，次 状 態 へ の 遷 移

(Transition)

を 行 う．こ れ ら の 処 理 を ク ー リ ン グ

(

温 度 の 冷 却

)

期 間 ま で 繰 り 返 し ， ク ー リ ン グ

(Cooling)

を 行 う．こ れ ら の 処 理 は 通 常 の

SA

と 同 じ で あ る ．

同 期

(Synchronize) :

 

適応的に近傍を調節するため，プロセス間で同期

(Syn- chronize)

を と り，各 プ ロ セ ス が も つ エ ネ ル ギ ー 値 を

1

つ の プ ロ セ ス に 集 め る ．

エ ネ ル ギ ー 値 の ソ ー ト

(Sort energy) :

 

1

つ の プ ロ セ ス に 集 め ら れ た エ ネ ル ギ ー 値 を 降 順（ ま た は 昇 順 ）に ソ ー ト す る ．

近 傍 幅 の 再 定 義

(Assign neighborhood) :

 

降 順（ ま た は 昇 順 ）に ソ ー ト さ れ た エ ネ ル ギ ー 順 に ， 初 期 設 定 で 定 め た 近 傍 幅 の 種 類 か ら 大 き な（ ま た は 小 さ な ）近 傍 幅 が 割 り 当 て ら れ る よ う，近 傍 幅 と エ ネ ル ギ ー 値 を 対 応 付 け る ．エ ネ ル ギ ー 値 に 対 応 す る 近 傍 幅 を 元 の プ ロ セ ス に 反 映 さ せ る た め ，エ ネ ル ギ ー 値 を 集 め た プ ロ セ ス か ら 各 プ ロ セ ス に 近 傍 幅 の 通 信 を 行 い ， 各 プ ロ セ ス の 近 傍 幅 の 再 定 義

(Assign neighborhood)

を 行 う．

4.

提案手法の有効性の検証

提 案 手 法 に お け る

SA

の 性 能 お よ び 有 効 性 を 検 証 す る た め に ，提 案 手 法 で あ る

NPSA

，並 列

SA(Prallel SA:PSA)

，

Corana

の 手 法

(Corana)

，

SA/AAN

，一 般 的 な 逐 次

SA(SA)

，ラ ン ダ ム に 探 索 空 間 を 全 探 索 す る 手 法

(Random)

を 異 な る 特 徴 を 持 つ

3

つ の 標 準 テ ス ト 関 数 に 適 用 し 解 探 索 能 力 ，解 探 索 の 履 歴 お よ び 探 索 に 伴 う 近 傍 幅 履 歴 に つ い て 比 較 を 行 う．ま た ，提 案 手 法 は 次 元 ご と の 探 索 を 行 う メ カ ニ ズ ム を 組 み 込 ん で い な い た め ，対 象 と す る 次 元 数 は

2

，

3

お よ び

5

次 元 と す る ．

4.1

対象問題 対象問題として式

(1)

に示す

Ras-

trigin

関 数

⁽⁹⁾

，式

(2)

に 示 す

Griewangk

関 数

⁽¹²⁾

お よ び 式

(3)

に 示 す

EggHolder

関 数

⁽¹³⁾

の

3

つ の 標 準 テ ス ト 関 数 を 用 い る ．

Rastrigin

関数，

Griewank

関数の最適解は原点に存在 し ，そ の 時 の 関 数 値 は

0

で あ る ．

Rastrigin

関 数 は 局 所 解 が 格 子 状 に 存 在 す る 多 峰 性 の 関 数 で あ り，

2

次 元 の 場 合 ，

100

個 の 局 所 解 を 持 つ 設 計 変 数 間 に 依 存 関 係 の な い 多 峰 性 の 関 数 で あ る ．

Griewank

関 数 は 設 計 変 数 間 に 中 程 度 の 依 存 関 係 を 持 ち ，大 域 的 に は 単 峰 的 な 関 数 の よ う で あ る が ，局 所 的 に 無 数 の 局 所 解 を 持 つ 関 数 で あ る ．一 方 ，

EggHolder

関 数 は 多 峰 性 で 極 め て 複 雑 な ラ ン ド ス ケ ー プ 持って い る 関 数 で あ り，最 適 解

,

そ の 時 の 関 数 値 は 設 計 空 間 の 次 元 に 依 存 し ，そ の 値 は 既 知 で な い が ，こ こ で は 最 小 値 を 求 め る 未 知 の 問 題 と し て 考 え ，提 案 手 法 の 有 効 性 の 検 証 に 用 い る ．

f

_R

(x) = (N × 10) +

_N

i=1

x

²_i

− 10 cos(2πx

_i

) (1)

定 義 域

: − 5.12 < x

i

≤ 5.12,

最 適 解

: (x

1

, x

2

) = (0, 0),

最 適 値

: f = 0

f

G

(x) = 1 +

N i=1

x

²_i

4000

−

N i=1

cos

√ x

i

i

(2)

定 義 域

: − 600 < x

_i

≤ 600,

最 適 解

: (x

₁

, x

₂

) = (0, 0),

最 適 値

: f = 0

f

_E

(x) =

ⁿ⁻¹

i=1

−x

_i

sin |x

_i

− P|

   

(3)

−P sin |P + x

_i

/2 |

     

P = x

_i+1

+ 47,

      定 義 域

: −512 < x

_i

≤ 512

4.2

温度パラメータ

SA

で は ，温 度 パ ラ メ ー タ と し て 最 高 温 度 と 最 低 温 度 を あ ら か じ め 決 定 し な け れ ば な ら な い ．こ こ で は ，

2

次 元 の テ ス ト 関 数 に お い て 温 度 の 調 節 を 行った ．そ の 決 定 方 法 に つ い て 述 べ る ． 近 傍 幅 の 範 囲 内 に 次 状 態 を 生 成 さ れ る 分 布 と し て ， 式

(4)

の よ う な 正 規 分 布 を 用 い る 場 合 は ，最 高 温 度 の 決 定 方 法 と し て ，各 変 数 の 標 準 偏 差 を 基 に 最 高 温 度 を 決 め る 方 法 が あ る ．こ の 方 法 で は ，標 準 偏 差 を 変 数 の 設 計 空 間 の

1/4

と 設 定 す る ．こ れ に よ り 最 高 温 度 で 設 計 空 間 内 を 十 分 に 探 索 可 能 と 考 え ら れ る

⁽⁸⁾

．

し か し ，今 回 は 分 布 と し て 一 様 分 布 を 用 い て い る た め ，標 準 偏 差 を 用 い た 決 定 方 法 を 用 い る こ と が で き な い ．そ こ で 近 傍 を プ ロ セ ス に 割 り 当 て る 最 大 の 近 傍 と し ，最 高 温 度 に お け る ア ニ ー リ ン グ 時 の 解 探 索 領 域 と 問 題 空 間 の 定 義 域 と の 差 が 最 小 に な る よ う に ，予 備 実 験 を 行 い 最 高 温 度 を 決 め る ．最 高 温 度 が 高 す ぎ る 場 合 は ，大 域 的 探 索 に 支 障 は な い が ，解 摂 動 が 定 義 域 を は み 出 す 確 率 が 高 く な り，計 算 効 率 が 下 が る ．と こ ろ が ，

最 高 温 度 が 低 す ぎ る 場 合 は ，定 義 域 に 探 索 さ れ な い 領 域 が 生 じ る た め で あ る ．

一 方 ，最 低 温 度 で は 解 の 精 度 を 向 上 さ せ る た め の 探 索が行われなければならない．そこで，予備実験によっ て ，求 め る 精 度 と 同 じ オ ー ダ ー の 解 を 得 ら れ る 温 度 を 最 低 温 度 と す る ．

g

_k

( x ) = 1

(2πT

_k

)

^D/2

exp

−|x|

²

2T

_k

(4)

4.3

各 パ ラ メ ー タ 設 定

問 題 に 適 応 す る 近 傍 幅 を 持 つ

SA

の 性 能 を 評 価 す る た め に ，式

(1)

，

(2)

お よ び

(3)

に 示 す

3

つ の テ ス ト 関 数 について表

1

および

2

に用いたパラメータを示す．クー リ ン グ 回 数 は

32

と し ，

PSA

と

NPSA

の 並 列 プ ロ セ ス 数 も 同 じ く

32

と し た ．一 方 ，

NPSA

に お け る 各 プ ロ セ ス の 近 傍 幅 は 最 大 近 傍 幅 を 設 計 空 間 の 幅 ，最 小 近 傍 幅 を そ の

10

⁻⁵と し ，そ の 間 の 近 傍 幅 は 指 数 的 に 割 り 振っ た ．ま た ，同 期 を とって

NPSA

の 近 傍 調 節 を 行 な う 周 期 は

PSA

の ク ー リ ン グ 周 期 に 合 わ せ た ．ま た ，並 列 手 法 と 逐 次 手 法 の 探 索 回 数 は 等 し く し た ．

並 列 プ ロ セ ス 数 と ク ー リ ン グ 回 数 と を 等 し く す る 理 由 は 特 に な く，近 傍 幅 が 大 き く 変 化 し な い と い う 条 件 の も と で 任 意 の 数 に 設 定 で き る ．そ の 他 の パ ラ メ ー タ に 関 し て は ，表

1

お よ び

2

に 示 す．

な お ，乱 数 は

rand48

を 用 い た ．こ の 乱 数 は ，

Martin

Birgmeier

らによって作成された

48

ビットの線形擬似乱

数 生 成 関 数 で 発 生 さ せ る ．こ の 乱 数 の 詳 細 は 文 献

⁽¹⁴⁾

を 参 照 さ れ た い ．

Table 1 Parameters

（NPSA，PSA）

Function Rastrigin Griewank EggHolder

最 高 温 度

10 20 10

最 低 温 度

0.01 0.001 0.01

ク ー リ ン グ 周 期

320 960 960

ク ー リ ン グ 率

0.8 0.726 0.8

プ ロ セ ス 数

32

最 小 近 傍 幅 設 計 空 間 の 幅 ×

10

⁻⁵

Table2 Parameters(Corana,SA/AAN,SA,Random)

Function Rastrigin Griewank EggHolder

最 高 温 度

10 20 10

最 低 温 度

0.01 0.001 0.01

ク ー リ ン グ 周 期

320*32 960*32 960*32

ク ー リ ン グ 率

0.8 0.726 0.8

プ ロ セ ス 数

1

最 小 近 傍 幅 設 計 空 間 の 幅 ×

10

⁻⁵

5.

実験結果および考察

5.1

解 探 索 能 力 解 探 索 能 力 に 関 す る 実 験 結 果 を 図

7

，

8

，

9

お よ び 表

3

に 示 す．

Rastrigin

関 数 に 適 用 し た 場 合 に 得 ら れ た 結 果 を 図

7

に ，

Griewank

関 数 に 適 用 し た 場 合 の 結 果 を 図

8

に ，

EggHoder

関 数 に 適 用 し た 場 合 の 結 果 を 図

9

に 示 す．表

3

に

Rastrigin

関 数 と

Griewank

関 数 の 最 適 解 取 得 率 を 示 す．最 適 解 取 得 率 は

NPSA

と

NPSA

の次に良い性能を示した

SA/AAN

の結 果を示す．図

7

，

8

，

9

の結果には問題の難しさを示すた めに，ランダムに探索空間を全探索する手法

(Random)

の 結 果 も 示 し て い る ．こ れ に よ り，こ れ ら の 問 題 は ラ ン ダ ム に 探 索 空 間 を 全 探 索 す る し ら み つ ぶ し 的 な 探 索 で は 求 め る 精 度 が 得 ら れ な い と い う こ と が 分 か る ．

図 の 横 軸 は 次 元 数 ，縦 軸 は エ ネ ル ギ ー 値

(

評 価 値

)

を 示 し ，エ ネ ル ギ ー 値 は 値 が 小 さ い 程 ，良 好 な 結 果 を 示 す．こ れ ら の 結 果 は ，

30

回 試 行 の 中 央 値 を 用 い て いる ． 中 央 値 を 用 い た 理 由 は ，複 数 の 局 所 解 が 存 在 し ，そ れ ら の 関 数 値 に 大 き な 差 が あ る 場 合 に は 平 均 値 で な く 中 央 値 で 比 較 す る 方 が 位 置 母 数 の 推 定 量 と し て 頑 健 で あ る か ら で あ る ．

一 般 的 な

SA

の 手 法 と

SA

の 改 良 手 法 で あ る

Corana

の 手 法

(Corana)

お よ び

SA/AAN

と

NPSA

を 比 較 す る と図

7

，

8

および

9

より，

Rastrigin

関数，

Griewank

関数，

EggHolder

関 数 と も に

NPSA

は 良 好 な 結 果 を 示 し て い る こ と が 分 か る ．並 列 手 法 で あ る

PSA

と

NPSA

を 比 較 す る と ，

NPSA

は

PSA

よ り 明 ら か に 良 好 な 結 果 を 示 し て い る こ と が 分 か る ．

Corana

の 手 法 と

SA

を 比 較 す る と，

SA

の改良手法である

Corana

の手法が

SA

より劣っ て い る 結 果 が あ る が ，

SA

は 最 適 な 近 傍 幅 を 予 備 実 験 に よ り 求 め て い る た め で あ る ．

Energy

Dimension

1E-6

1E-5 1E-4 1E-3 1E-2 1E-1 1E+0

2 3 5

NPSA PSA Corana SA/AAN SA Random

Fig.7 Performance of the methods(Rastrigin)

EnergyE n e rg y

Dimension Dimension

1E-6

1E-6 1E-5 1E-5 1E-4 1E-4 1E-3 1E-3 1E-2 1E-2 1E-1 1E-1 1E+0 1E+0

2 3 5

NPSA NPSA PSA PSA Corana Corana SA/AAN SA/AAN SA SA Random Random

Fig.8 Performance of the methods(Griewank)

Table 3 Success ratio on NPSA and SA/AAN

Dimension Rastrigin Griewank

NPSA SA/AAN NPSA SA/AAN

2 0.33 0 1 0.2

3 0.17 0 0.53 0

5 0 0 0 0

Energy

Dimension

5 -4000 -3500 -3000 -2500 -2000 -1500 -1000

3 -2000 -1800 -1600 -1400 -1200 -1000 -800

2 -1200 -1000 -800 -600 -400 -200

NPSA PSA Corana SA/AAN SA Random

Fig.9 Performance of the methods(EggHolder)

5.2

解 探 索 の 履 歴 お よ び 近 傍 幅 履 歴

NPSA

と

最も標準的で性能の高い

PSA

の近傍履歴とエネルギー

履 歴 を 比 較 し ，

NPSA

の 有 効 性 を 考 察 す る ．対 象 問 題 に は

2

次 元 の

Rastrigin

関 数 を 用 い た ．図

10

に

NPSA

の エ ネ ル ギ ー 履 歴 ，図

11

に

PSA

の エ ネ ル ギ ー 履 歴 を 示 す．図

11

の 横 軸 が ア ニ ー リ ン グ ス テップ 数

(

評 価 回 数

)

，縦 軸 が エ ネ ル ギ ー 値 を 示 し ，

Current Energy

は 探 索 点 の エ ネ ル ギ ー 値 を ，

Best Energy

は

Current Energy

の 履 歴 か ら 求 め た 最 良 の エ ネ ル ギ ー 値 を 示 す．

図

10

お よ び

11

よ り

NPSA

が

PSA

よ り よ い 解 が 得 ら れ て い る こ と が 分 か る ．ま た ，

NPSA

は

PSA

よ り 早 く 局 所 解 か ら 抜 け 出 し て お り，こ れ に よ り 最 適 解 領 域 で の 探 索 が

PSA

よ り 十 分 に 出 来 て い る と い え る ．

そ の 理 由 は 図

12

に 示 す 近 傍 履 歴 か ら 明 ら か で あ る ． 図

12

は

32

プ ロ セ ス 中 最 終 的 に 最 も 良 い エ ネ ル ギ ー 値 を 得 た プ ロ セ ス の 履 歴 を 示 し ，横 軸 に ア ニ ー リ ン グ ス テップ 数 ，縦 軸 に 近 傍 を 示 し て い る ．

PSA

は 近 傍 の 交 換 を 行 わ な い 手 法 で あ り，予 備 実 験 よ り 求 め た 最 適 な 近 傍 幅 で あ る

1

を 近 傍 幅 と し て 用 い る ．

PSA

は 予 備 実 験 に よ り 求 め た 最 適 な 近 傍 で 探 索 を 行って い る が ，最 適 解 領 域 に

NPSA

と 比 べ 速 く 収 束 し て い な い ．ま た ，

NPSA

と 比 べ エ ネ ル ギ ー 値 が 悪 く な る 方 向 に 推 移 し や す く なって い る こ と か ら ，最 適 解 領 域 に 探 索 点 が 入っ て も す ぐ に 抜 け 出 し て し て い る こ と が 分 か る ．そ の た め ，探 索 終 盤 に な り 温 度 が 下 がって も ，最 適 解 領 域 で の 局 所 探 索 が 十 分 出 来 て い な い と 考 え ら れ る ．

一 方 ，

NPSA

は 近 傍 交 換 時 に 各 プ ロ セ ス の 探 索 点 の 解 を ソ ー ト し ，エ ネ ル ギ ー 値 が 大 き い 解 に は 大 き い 近 傍 を 与 え ，エ ネ ル ギ ー 値 が 小 さ い 解 に は 小 さ い 近 傍 を 与 え る と い う，近 傍 を 適 応 的 に 変 化 さ せ る メ カ ニ ズ ム を 持 つ た め ，最 適 解 領 域 に 入って い る 解 で は 局 所 探 索

0.0 0.2 0.4 0.6 0.8 1.0 1E-7

1E-6 1E-5 1E-4 1E-3 1E-2 1E-1 1E+0 1E+1 1E+2

Annealing steps

Energy

Best Energy Current Energy

˜10⁴

Fig.10 History of energy(NPSA)

Best Energy Current Energy

Energy

Annealing steps

0.0 0.2 0.4 0.6 0.8 1.0

1E-4 1E-3 1E-2 1E-1 1E+0 1E+1 1E+2

˜10⁴

Fig.11 History of energy(PSA)

0.0 0.2 0.4 0.6 0.8 1.0

1E-5 1E-4 1E-3 1E-2 1E-1 1E+0 1E+1

Neighborhood range

Annealing steps

NPSA PSA

˜10⁴

Fig.12 History of neighborhood range

を ，局 所 解 領 域 に 入って い る 解 で は 大 域 的 探 索 が 行 え る ．図

12

の 結 果 か ら ，探 索 前 半 で は 局 所 解 領 域 で 探 索 を行っているため，局所解から脱け出すために，徐々に 近 傍 が 大 き く なって い る こ と が 分 か る ．局 所 解 か ら 脱 け 出 し 最 適 領 域 に 入った 探 索 中 盤 で は ，局 所 探 索 の た め に 近 傍 幅 が 徐々に 小 さ く な り，探 索 終 盤 で は 小 さ な 近 傍 幅 で 局 所 探 索 を 十 分 行って い る こ と が 分 か る ．

6.

まとめ

シミュレーテッドアニーリングを連続最適化問題に適 用 す る 場 合 ，近 傍 の 調 整 が 必 要 不 可 欠 と な る ．本 研 究

で は ，従 来 の 適 応 的 近 傍 メ カ ニ ズ ム で 必 要 と さ れ る 多 くの近傍調節のためのパラメータを減らし，かつ，並列 処 理 を 用 い る こ と で 処 理 時 間 の 短 縮 が 期 待 で き る 新 し い 適 応 的 近 傍 並 列 ア ル ゴ リ ズ ム

(NPSA:Neighborhood Parallel Simulated Annealing)

を 提 案 し た ．そ し て 実 験 結 果 よ り 提 案 手 法 が シ ミュレ ー テッド ア ニ ー リ ン グ の 拡 張 ア ル ゴ リ ズ ム と し て 有 効 で あ る こ と を 確 認 し た ．

参考文献

(1) Reeves, C.R.(

編

)

，横 山 ，奈 良 ら

(

訳

):

モ ダ ン ヒュー リ ス ティック ス ，日 刊 工 業 新 聞 社

(1997).

(2)

喜 多 一

.

シ ミュレ ー テッド ア ニ ー リ ン グ

.

日 本 ファ ジィ学 会 誌

, (1997).

(3) Aarts, E. and Korst, J.:

 

Simulated Annealing and Boltzmann Machines, john Wiley & Sons, (1989).

(4) Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A. and Teller, E.: Equation of State Calcula- tion by Fast Computing Machines, Journ. of Chem- ical Physics, Vol. 21, pp. 1087-1092 (1953).

(5) Ingber, L.:

 

Simulated Annealing: Practice versus theory, Journal of Mathl. Comput.and Modelling.

Vol.18, No.11, pp29-57 (1993).

(6) Corana, A., Marchesi, M., Martini, C. and Ridella, S.: Minimizing Multimodal Functions of Continu- ous Variables with the ”Simulated Annealing” Algo- rithm, ACM Trans. on Mathematical Software, Vol.

13, No. 3, pp. 262-280 (1987).

(7)

三木光範

,

廣安知之

,

小野景子：最適な受理確率を目標 とするを適応的近傍を持つシミュレーテッドアニー リ ン グ，情 報 処 理 学 会 誌

Vol.44,No.1,pp1-6(2003).

(8)

三 木 光 範

,

廣 安 知 之

,

笠 井 誠 之

,

小 野 景 子：適 応 的 近 傍 を 持 つ 温 度 並 列 シ ミュレ ー テッド ア ニ ー リ ン グ，

情 報 処 理 学 会 誌

Vol.42

，

No.4

，

pp745-753 (2003) (9) Bruce E. Rosen,

中野 良平：シミュレーテッドアニーリ

ング

,

人工知能学会誌

Vol.9,NO.3,pp.365-371

（

1994).

(10) Szu, H. and Hartley, R.: Fast Simulated Annealing, Physics Letters A,Vol.122,No.3,4,pp.157-162 (1987).

(11) Rosen, B.: Functional Optimization based on Ad- vance Simulated Annealing, IEEE Workshop on Physics and Computation, PhysComp 92 (Dallas, Texas), pp. 289-293 (1992).

(12) Whitley, D., Mathias, K., Rana, S. and Dzubera, J.:

Evaluating Evolutionary Algorithms, Artificial Intel- ligence, Vol. 85, pp. 245-276 (1996).

(13) http://www.ft.utb.cz/people/zelinka/soma /func.html

(14) http://www.ics.uci.edu/eppstein/projects/pairs