遺伝的交叉を用いた
並列シ ミュレ ーテッド アニーリング
Parallel Simulated Annealing using Genetic Crossover
同志社 大学工学部 廣安 知之，三木 光範，○ 小掠 真貴
Tomoyuki Hiroyasu, Mitsunori Miki and Maki Ogura
Department of Knowledge Engineering and Computer Science , Doshisha University Abstract In this paper, we propose Parallel Simulated Annealing using Genetic Crossover.
In the proposed algorithm, there are plural processes and the sequential SA is operated in each process. After some steps, the genetic crossover is used to exchange the information between the solutions. This operation reduces the computational cost while SA needs large cost especially in the continuous problems. The proposed algorithm is applied to the continuous test problems.
Through the numerical examples, it is found that our algorithm can search the solution effectively, compare to distributed genetic algorithms and sequential SAs.
1
はじ め にシ ミュレ ーテッド ア ニ ー リング
(Simulated Annealing : SA)
は 最適化問題を 解く近似解法の 一つで あり，多くの 組 合せ 最 適 化 問題に 対し て 有 効な 手 法で あ る1)．SAの 探 索は 最 適 解 へ 収 束 す る と い う 保 証 を 持 つが ，解を 得 る まで の 計 算 量が 非 常に 多 いと い う 短 所を 持 つ ．連 続 最 適 化 問 題を 対 象とし た 場 合は ，特に 最 適 解 を 得 る ま で に 多 く の 計 算 量が 必 要 と な り 実 用 的で は な い ．そ の ため 逐次処理で あ るSA
を 並列化し 高速化を 図る研究が され て い る 2)．本 研 究では ，並 列
SA
の 適 用範 囲を 広げ るため ，連 続 最適化問題を 対象とする場合で も ，比較的少ない計算量 で 良好な 解を 得るこ とので き る新たな 並列SA
アルゴ リ ズ ムを 提案する ．提案する手法は ，並列に 複数実行し て い るSA
の 解 の 伝 達 時に ，遺 伝 的ア ルゴ リズ ム(Genetic Algorithm : GA)
の オ ペレ ー タで あ る 遺 伝 的 交 叉を 用 い た もので あ る ．局所 的な 探 索が 得 意なSA
に ，大 局 的な 探 索が 得 意で か つ 部 分 解の 組 み 合 わ せで 最 適 解が 得ら れ るGA
オペレ ータを 取り入れ ることで ，適用可能な 対 象 問 題の 範 囲 を 拡 張 す る こ とが 可 能で あ る ．本 研 究で は ，提 案 す る ア ルゴ リズ ムを い く つか の テ スト 関 数に 適 用し ，その 有 効 性を 検 討す る ．2
遺 伝 的 交 叉を 用い た 並 列シ ミュレ ー テッド ア ニ ーリ ン グ本 手 法で 提 案 す る ア ルゴ リズ ムは ，複 数のプ ロセ ス 上で それぞ れ
SA
の 操作が 並 列に 行われ る ．一定 間隔の ア ニ ー リング が 繰 り 返 され た 後 ，次に 示 す よ うな 遺 伝 的 操 作に より 解の 伝 達を 行 う．本研 究で はSA
の 探 索点 の 総 数を 個 体 数 ，アニ ー リング ステップ(計 算 繰り 返し
回 数)を 世 代 数と 呼ぶ こ と と す る ．並列に 実行し て い る
SA
から ランダ ムに 親とし て2
個 体を 選択し ，設計変数間交叉を 行 う．もとの 親と 生成し た 子と の4
個 体 間 の うち 評 価 値 の 高 い2
個 体 を 選 択し て ，この2
個体から 次の 探索を 続け る ．この 操作は すべ て の 個 体に 対し て 行 われ る ．あ る 設 計 変 数の 最 適 値が求 まって いる 場合 ，遺 伝的交 叉に よって その 設 計変 数の 最 適値を 他の
SA
探 索に 伝 達す ることが で きるた め ，ア ニ ー リング の 収 束を 早め ることが で きると 考え られ る ． 図1
に その 概 念 図を 示 す．n : crossover interval
SA SA SA SA
...
n n
hightemperature low
temperature n
end
randomselection crossover randomselection crossover
図
1:
遺伝 的 交 叉を 用 いた 並 列SA
の 概 念 図3
数 値 実 験3.1 GA
オペレ ー タを 用い た3
種の 並 列SA
と の 比 較 提 案 す る モデ ル で はGA
オ ペレ ー タで あ る 遺 伝 的 交 叉を 用いている ．この有 効性を 検証するため ，解の伝 達 方法とし て 遺 伝的 交叉以 外のGA
オペレ ータを 用いた3
つの 並列SA
と ，解 探索 能 力を 比較し た ．これ ら は 一 定 間 隔ご と に 以 下の よ うな 方 法で 解の 伝 達を 行 うもの で あ る ．•
エ リート 選 択を 用い た 並 列SA(elitePSA):
複 数 個 体の 中で の エ リ ート 個 体を 他の すべ て の 個 体の 新た な 探 索 点と す る
•
ル ーレット 選 択を 用いた 並 列SA(roulettePSA):
各個体の 評価値を 基にし たル ーレット 選択に よりす べ て の 個 体の 新た な 探 索 点を 決 定 す る
•
エ リ ート 保 存 を 含 むル ーレット 選 択 を 用 い た 並 列SA(e-roulettePSA):
エ リート 保存を 用いたル ーレット 選択に よりすべて の 個 体の 新た な 探 索 点を 決 定す る
対 象 問 題 と し て ，2 設 計 変 数 の
Rastrigin
関 数 とGriewank
関 数 の2
つ の 連 続 関 数 最 小 化 問 題 を 用 い た ． 個 体 数は20，200
とし た ．それぞれ の並列
SA
の個体数を20
とし てRastrigin
関数 を解いた結果を図2に 示し ，個体数を 200
とし てGriewank
関数を 解いた 結果を 図3
に 示し た ．横軸は 初 期温度 ，縦 軸は1
個 体の 持 つエ ネルギ ー ，すな わ ち 解の 値で あ り，結 果は
10
試 行の 平 均 値で あ る ．Energy
crossoverPSA elitePSA roulettePSA e-roulettePSA
1.0E-08 1.0E-06 1.0E-04 1.0E-02 1.0E+00
5 10 20 30
Initial temperature
図
2: Rastrigin
関 数の 結 果(20
個 体)Energy
crossoverPSA elitePSA roulettePSA e-roulettePSA
1.0E-08 1.0E-06 1.0E-04 1.0E-02 1.0E+00
5 10 20 30
Initial temperature
図
3: Griewank
関 数の 結 果(200
個 体)図
2
か ら は 提 案 手 法と 他の 手 法の 結 果に 大 きな 違 い が あ るこ とが わか る ．遺 伝 的交 叉を 用いた 並列SA
は 初 期温度に よらずに 常に 良好な 解を 求められ ているが ，他 の3
つ の 手 法で はど の よ うな 初 期 温 度で も 精 度の 良 い 解を 求め るこ とが で きな かった ．各 並 列
SA
の 個 体 数を10
倍 の200
とし てRastrigin
関 数を 解いた 場合には ，4つの 手 法すべ てで 常に 良好な 解 が 求めら れ た ．個 体 数 を 増 加 させ て も 各 個 体 の 繰 り 返 し 計算回数が あまり変わらなかったために 全体の計 算回 数が 増え ，すべ て の 手 法で 解が 求 まった と 考え られ る ．Griewank
関 数を20
個 体で 解いた 際に は ，ど の 手 法で も 良好な 解が 求められ ず 有意な 差は なかったが ，個体数 を200
とし た と きには 図3
に 示すよ うに 大きな 差が あっ た ．ル ーレット 選 択を 用いた 並 列SA
と エ リート 保 存を 含 むル ーレット 選 択を 用いた 並列SA
で はど の 初 期 温 度 で も 常に 得ら れ る 解 の 精 度は 良 く な いが ，エ リ ート 選 択を 用いた 並列SA
で は 初 期温 度に よって 良 好な 解が 求 め ら れ る 場 合が あ る こ と が わ か る ．遺 伝 的 交 叉を 用 い た 並列SA
では 初期温度に よら ず 常に 良好な 解が 求めら れ た ．これ ら の 結 果か ら ，適 用 させ た テ スト 関 数に 対し て は ，遺 伝的 交叉を 用いた 並 列
SA
の 解 探索 能力が 最も 優 れ て いると いえ る ．また エ リート 選 択を 用いた 並 列SA
も 比 較 的 優れ た 解 探 索 能 力を 示し て い るが ，最 適 解 を 求 め ら れ る 確 率は 遺 伝 的 交 叉 を 用 い た 並 列SA
よ り 低 い ．こ のた め エ リート 選 択を 用いた 並 列SA
は ，遺 伝的 交叉を 用いた 並列SA
と 比較すると 解探索能力は 低いと いえ る ．3.2
遺 伝 的 交 叉を 用い た 並 列SA
の 解 探 索 能 力3.1
節の 数値実験に より，遺伝的交叉を 用いた 並列SA
の 解探索能力が 優れ て いることが 明らかとなった ．本節 で は ，分 散GA
と 逐 次SA
と の 探 索 能 力の 比 較を 行 う．対象問題は
10
設計変数，30
設計変数のRastrigin
関数，Griewank
関数，Rosenbrock
関数で ある ．各手法の評 価計 算 回 数 を 等し くし ，終 了 条 件を 満たし た と きに 探 索を 終 了し た ．遺 伝 的 交 叉を 用いた 並 列SA
の 個 体 数は400
とし ，8000世 代の 探 索 を 行った ．逐 次SA
は3200000
世 代(8000
世 代×400
個 体に 相 当)の 計 算を 行 うもの(表 中
で はSSA-long
と す る)，8000世 代の 計 算を 独 立に400
回 実 行す る も の(表中で は SSA-short
と す る)の2
種 類とし て ，並 列SA
と 性能を 比較し た ．また 分 散GA
は20
個 体×
20
島の400
個体とし ，8000世代まで 探索を 行った ，並 列SA
と2
つの 逐 次SA
の 初 期 温 度は10
に 統 一し た ．各 手 法に ついて 試 行は それぞ れ10
回ず つ 行 い ，10試 行 中 で 最適解が 得られ た 回数を 表1
に 示し た ．ここでの 最適 解とは 評 価 値が1 . 0 × 10 e
−6以 下の こ と を 示す．表
1:
逐 次SA，分 散 GA
と の 比 較Rastrigin
Griewank
Rosenbrock 10dimensions 10dimensions 10dimensions
30dimensions
30dimensions 30dimensions
SA SSA-long SSA-short GA
10 0 0 10
0
0 0
0 0
0 0
0 0
0 0 1
1 0
0
7 9
10 10 10
まず，提 案手 法と 逐 次
SA
と の 結 果を 比 較す ると ，逐 次SA
と 遺 伝 的 交 叉を 用い た 並 列SA
の 評 価 計 算 回 数は 等し いこ とから ，単にSA
のア ニ ー リング 時間や 回 数を 増 加し ただ け で は 結 果が 向 上し な い こ と が わ か る ．ま た 分 散GA
と の 結 果を 比 較す ると ，GAで の 探 索が 困 難 な 設 計 変 数 間に 依 存 関 係 の あ る 問 題に 関し て は ，特に 遺伝的交叉を 用いた 並列SA
の 探 索が 有効で あ ることが わ か る ．設 計 変 数 間に 依 存 関 係 の な い 関 数 を 対 象 とし た と きも ，GAに 劣ら な い探 索が 行われ て い る ．これ ら の 結果から ，提 案す る 遺 伝的交 叉を 用いた 並 列SA
の 探 索 能 力は 有 効で あ ると いえ る ．4
結 論本研究で は ，組合せ 最適化問題を 得意と する
SA
が 連 続 最 適 化 問 題を 対 象とし た と きに も ，実 用 的に 解 を 得 る た め の 並 列ア ルゴ リズ ムとし て ，遺 伝 的 交 叉を 用 い た 並列SA
を 提案し た ．また 提 案手 法を い く つか の 連続 最適化問題に 適用し ，その 探索能力を 逐次SA，分散 GA
と 比 較し た ．その 結 果 ，遺 伝 的 交 叉を 用いた 並 列SA
は アニー リング の 収束が 早く，得られ る解の 品質も良いこ とが 示され た ．参 考 文 献
1) Bruce E. Rosen,
中 野 良 平.シ ミュレ ーテッド ア ニ ー リ ング-基礎と 最新 技術-.
人工知 能学会誌, Vol. 9, No. 3,1994.
2) E. H. L. Aarts, J. H. M. Korst. Simulated annealing and
Boltzmann machines. John Wiley
＆Sons, 1989.
出 典： 第
