知的システムデザイン研究室 学籍番号：36-98-0710 笠井 誠之 修士論文公聴会 [2000/02/02] 温度並列SAの 連続最適化問題への拡張 知的システムデザイン研究室 学籍番号：36-98-0710 笠井 誠之 ただいまより，修士論文「温度並列SAの連続最適化問題への拡張」の発表を行います．知的システムデザイン研究室の笠井です． よろしくおねがいします． 同志社大学大学院 工学研究科 知識工学専攻

研究背景 並列処理の応用 ヒューリスティック探索手法の並列化 これまで これから 数値解析 最適化 シミュレーテッドアニーリング(SA)，遺伝的アルゴリズム(GA)，セルオートマトン(CA)，ニューラルネット(NN)，etc 高い計算負荷で並列化は必須 原理的に自然な並列化が可能 これまで これから 数値解析 最適化 並列処理の応用は，これまで数値解析を中心に行われてきました． しかし近年，最適化の並列処理が注目を浴びてきています． そして，この並列最適化のなかでも特に注目されているのがここに挙げます．ヒューリスティック探索手法と呼ばれる手法の並列化です． これらに共通しているのは，高い計算負荷で並列化は必須であるということです． 本研究では，シミュレーテッドアニーリング(SA)の並列アルゴリズムについて考えます．

Simulated Annealing （SA） 物理現象のモデル化 金属の焼きなまし(ｱﾆｰﾘﾝｸﾞ)を計算機上でシミュレート 温度 高 温度 低 ゆっくり冷やす シミュレーテッドアニーリング（SA）とは，物理現象をモデル化したものです． 高温状態であり，エネルギーが高い状態にある金属をゆっくり冷やすとエネルギーの低いきれいな金属の結晶を得ることができます．このことを焼きなまし（アニーリング）と呼びます． 焼きなましによってエネルギーの低い状態が得られるわけですから，この現象をモデル化すると，目的関数の最小状態を求める最適化に利用することができます．SAはそのように考え出されました． エネルギー 高 エネルギー 低 最適化に利用

シミュレーテッドアニーリング (SA) 温度 E高 E低 金属の焼きなまし(annealing)を模擬した最適化法 アルゴリズム 1.解の摂動 2.受理判定 Metropolis基準 エネルギーEが 3.クーリング 減少 増加 確率1.0で摂動を受理 3.クーリング 3.クーリング －(Ｅnext－Ｅcurrent) Ｔ exp 確率 で摂動を受理 3.クーリング 3.クーリング 3.クーリング 3.クーリング 3.クーリング 温度 3.クーリング 3.クーリング 3.クーリング E高 最適解 局所解 長所 複雑な問題が解ける SAのアルゴリズムをこのような目的関数の最小を求める場合で説明します．SAでは，目的関数の高さをエネルギーと呼び，エネルギーのもっとも低い状態が最適解です． SAには3つの重要な処理があります． まず初めに，現在の解を異なる解に移動(摂動)させます．その摂動によってエネルギーとが減少すれば，つまり解が改善されれば確率1.0でその摂動を受理します．エネルギーが増加していれば，この式のような確率でそれを受理します．摂動が却下された場合は，解は変化しません．この式をメトロポリス基準と呼びます． この改悪確率は，ここにある温度と呼ぶパラメータが大きいほど，大きくなり，温度が低いほど改悪確率は低くなります． そこで温度の高い状態から低い状態へのクーリングというものを行うことによって，このアルゴリズムは，処理の前半には，局所解の谷をこえ，温度が下がってくる後半には，改善方向の摂動が多くなり，最終的には最適解に到達することを期待します． SAの長所は，複雑な多峰性問題を解くことができるということです． また，短所は，高い計算コストとクーリングスケジュールの設定が極めて困難であるということです． 短所 計算時間が長い． クーリングスケジュール決定困難 E低

SAの並列化 目的 従来手法 新しい手法 計算の高速化 ＳＡ 温度並列シミュレーテッドアニーリング（TPSA） 同期 独立型並列SA さて，近年新しいSAの並列化アルゴリズムが提案されました．それは温度並列SA「TPSA」と呼ばれるものであり，これまで組み合わせ最適化問題に適用されてきました． TPSAは，これまでの並列SAにない特徴を持っています． 新しい手法 温度並列シミュレーテッドアニーリング（TPSA）

温度並列SA (TPSA) アルゴリズム 並列処理との親和性 温度スケジュールの自動化 確率的に良質な解が低温PEに移動 解交換 解交換 最高温 高温 低温 最低温 解摂動 受理判定 解摂動 受理判定 解摂動 受理判定 解摂動 受理判定 温度並列SAのアルゴリズムを， 4プロセッサの並列計算機を使用する場合で説明します． まず，それぞれのプロセッサに異なる温度とそれぞれの初期解を与えます．そして，それぞれのプロセッサは独自に温度一定のままに，通常のSAと同じように摂動と受理判定の繰り返しを行います． そして，ある程度の探索を行うと，隣り合うプロセッサで解を交換します．解交換のルールは，お互いの解の優劣から，良好なものが確率的に低温側に推移するようなものを用います．そうすることで，このアルゴリズムの終了時には最低温プロセッサから最適解を得ます． TPSAにおいて最も注目すべきことは，温度スケジュールを自動化できることです．逐次SAでは，初期温度を与え，これどどのように下げていくのがアルゴリズムの性能に大きな影響を与え，大変難しい問題です． 一方，TPSAの場合は並列に走っている各解が，お互いのエネルギーを見比べて，自分自身に適切な温度を渡り歩いていくことになります．そこで，どれだけ温度を下げるかということについて考えなくてもすむのです． Temperature Time Parallelize in Temperature

本研究の目的 SA over SA continuous spaces SA TPSA over continuous spaces Extensions SA SA TPSA Parallelizations TPSA over continuous spaces TPSA/AN SAは，従来組合せ最適化に適用されてきました． このSAを連続最適化問題に適用するための研究が数多く行われています． 一方，SAの並列化の研究もあり，その中にTPSAがあります． そこで，本研究ではこれまでに行われていないそのTPSAを連続空間に応用することを目的としました．そして，新しいアルゴリズムTPSA/ANを提案します．

連続最適化問題のためのSA 摂動近傍 定義可能 定義困難 TSP 組合せ最適化問題の場合 連続最適化問題の場合 解を変化させる最小の操作 一般的に解の摂動は，その問題において解を変化させる最小の操作を用いて行います．たとえば，全ての町を巡る最短経路を求める組合せ最適化問題である巡回セールスマン問題では，ある2本の経路を抜き取り，新たな経路を結ぶことで解を操作します．1本では経路交換ができないため，2本の経路交換はまさに最小の操作でり，厳密にそれを定義することができます． 一方，連続最適化問題の場合は，この2次元空間における探索のように，最小の近傍をどのように定義するかを考えなければなりません．解が連続値であるため無限のバリエーションが考えられ，その近傍の定義は難しいといえます． そのため，これまで多くの摂動方式が研究され提案されています． 定義困難 2 dimensional problem space Solution

従来の連続最適化問題のためのSA ランダム性を重視 ルールを使用 （関数のランドスケープを考慮） TPSAによる並列化 一様分布の近傍のSA Boltzmannアニーリング Fast SA その他 ルールを使用 （関数のランドスケープを考慮） CoranaのSA VFSR Dekkers & AartsのSA Press & TeukolskyのSA その他 TPSAによる並列化 これまで研究されてきた連続空間での多くの解摂動方式を簡単に分類すると，摂動にランダム性を重視するものと，あるルールを使用し，問題空間のﾗﾝﾄﾞｽｹｰﾌﾟを考慮したものに分けることができます．本研究では，この中のCoranaのSAをTPSAによって並列化することにしました．

適応的近傍 (Adaptive Neighborhood) 提案手法 TPSA/AN TPSA Corana’s method ＋ 各温度で関数のランドスケープを考慮 受理と却下の割合が1：1に保たれるように，解摂動のための近傍の大きさを調節する． ここで提案するアルゴリズムの特徴はこのようになります． まず，連続的な問題空間で探索を行うためにCoranaの手法を用いています． そこで，本手法は目的関数のランドスケープの情報を利用し，受理と却下の割合を一定に保ちながら適応的に近傍レンジを調節します． 適応的近傍 (Adaptive Neighborhood)

受理率に関する近傍の調節 －Coranaの手法－ 却下過多 受理過多 近傍レンジ 近傍を 小さくする 近傍を 大きくする 無駄 受理と却下の割合を１：１に保つように 近傍を調節する Solution x1 2 dimensional problem space x2 目的関数の勾配が急な地点を探索する場合，「大きすぎる」近傍レンジによる摂動は，Metropolis基準により却下されてしまうので，探索効率を考えてレンジを小さくしなければなりません． さらに，勾配が平坦な地点では，「小さすぎる」レンジは解の向上の度合いが小さくなってしまうので，レンジを大きくしなければなりません． そこで，このようなメカニズムを実現するために，受理と却下の割合が１：１に保たれるような，近傍レンジの調節プロセスを用いることになります． 無駄

温度に対する近傍の調節 －Coranaの手法－ x1 x2 2 dimensional problem space 高温時には，近傍が大きくなる． 低温時には，近傍が小さくなる． 高温 Solution ただいま，説明しましたこのメカニズムを用いると，受理率が高くなりがちな高温状態では，近傍レンジは大きく調整され，大域的な探索が実現されます． 一方，受理率が低くなりがちな，低温状態では，近傍レンジは小さく調節され，局所的な探索が実現されます． 低温

近傍調節の定式化 m, m’: 近傍レンジ. g(p) : 近傍レンジ調節のため p : 摂動の受理率. p = n / N 0.4 0.6 1/(c+1) c+1 1 m, m’: 近傍レンジ. g(p) : 近傍レンジ調節のため の係数. p : 摂動の受理率. p = n / N ここで述べた近傍レンジの調節を数式で表現するとことのようになります． この式で使用する受理率pは近傍レンジの調節間隔中に，受理された摂動の回数から計算されます． この受理率が0.6以上になると，近傍レンジを大きくし，0.4以下になると，近傍レンジを大きくします． 本研究では，経験的に c=2，N = 8. n : 受理された摂動回数． N : 近傍レンジ調節間隔．

対象問題 Rastrigin関数 設計変数の数：2 局所解の数： Griewank関数 fR：121 fG：約50000 fS：5 Shekel関数 Rastrigin Griewank Local view Shekel Global view

実験に使用したパラメータ この実験では，このようなパラメータを用います．(スライドを指しつつ) TPSAのためのプロセス数は32プロセスとします． SAとTPSAのための最大温度・最低温度はともに同じです． 総計算回数はSAとTPSAで等しくなっています． 逐次SAにおけるマルコフ連鎖の長さ(温度を一段下げるまでの計算回数)は10240です． 逐次SAのクーリング率は，0.8とします． TPSAのための解交換間隔は32ステップとします．

並列計算機への実装 PC-cluster 実装方法 CPU： Pentium II 233MHz× 8 Memory： 128MB×8 OS： Linux Parallel library： PVM Network： 100Base-T (Fast Ethernet) 我々は，Pentium IIプロセッサを用いた8台のPCによるPCクラスタを使用しました． それぞれのPCのOSは，Linuxです． 通信ライブラリとしてPVMを用いました． 相互接続ネットワークは100Base-T“Fast Ethernet”です． 実装は，それぞれの温度をそれぞれのプロセスに1つずつ割り当てました． 実装方法 1つの温度を１つのプロセスに割り当てる．

実験 TPSA/AN： 適応的近傍レンジ SA/AN： 適応的近傍レンジ SA/FN： 固定近傍レンジ 要 設定 TPSA/FN： 固定近傍レンジ

実験結果 [Rastrigin] 実験は，Coranaの手法を使用するTPSA/ANとSA/AN，また使用しないSA/FNとTPSA/FNの4つアルゴリズムを比較することで行いました． Coranaの手法を使用しない場合，近傍のレンジはある値に固定します． この図は，横軸に固定近傍レンジの各設定を列挙しています．そして，十回の試行を行った際の得られた解のエネルギーの中央値で評価します．縦軸はエネルギーです． まず，赤線が固定近傍レンジSA/FN，青線が固定近傍レンジTPSA/FNを示しています． このグラフを見ると，それぞれの手法において，最良の解を得ることができるレンジの設定があることに気づきます．逐次SAでは1であり，TPSAでは0.5となっています．また，多くの設定においてTPSAは逐次SAより性能が低いということが注目すべき事実です． 一方，本研究で提案するTPSA/ANは，この中のすべての設定において，最も良好な解を得ることが出来ています．

実験結果 [Griewank] 同様です．

実験結果 [Shekel] 同様です．

温度と近傍レンジの履歴 (Max. T) (Min. T) こちらは提案手法において，結果としてglobal minimumに到達したある解の通過してきた温度の履歴を示しています．また，それとともに近傍レンジの変化の履歴も示しています．青線が温度の履歴であり，ピンク線が近傍レンジの履歴です．横軸はステップ数を表しています． 提案手法では，このように温度スケジュールが自動化され，また，近傍のレンジもそれにあわせて変化しています． (Min. T)

最終的に最低温度に到達した解の エネルギー履歴 [Rastrigin] 0.1 0.5 1 5 次に，TPSAにおいて最終的に最低温度に到達した解がたどったエネルギーの履歴を示します．Rastrigin関数の場合で見ていきます． 横軸がステップ数で，青線がTPSA/ANの履歴を表しています．そのほかの線は，それぞれ近傍レンジを固定した場合のエネルギーの履歴です．たとえば，近傍のレンジ大きい5の設定では，高速に良好な解を得ていますが，ある程度のところで解の精度を向上させることができないでいます．また，レンジの小さい0.1の設定は，大域的な探索を行うことができないため，探索の初期の段階から，解の向上が得られないままとなっています． しかし，TPSA/ANでは，各温度で近傍のレンジが変化していますので，大域探索と局所探索の両方が行えることによって，最終的には最も良好な解をえることが出来ています． AN

解探索の履歴 Global optimum Initial solution なお，先ほどのTPSA/ANのエネルギー履歴を持つ解の2次元空間上での探索の様子は，この図のようになります．それぞれの局所解領域で局所探索を行い，また別の解を探索するためにそこから脱出している様子を見ることができます． Initial solution

適応的近傍の効果 要 各温度における効率の良い摂動 TPSA SAの探索回数：L回 TPSAにおける ある一つの解の探索回数： 回 L n ・・・ Parallelization in temperature TPSA SAの探索回数：L回 TPSAにおける ある一つの解の探索回数： 回 L n 適応的近傍の効果をまとめます． ここにL回の摂動を行う逐次SAがあったとします． そして，それを温度並列SAのアルゴリズムにしたがって，nプロセッサで並列化します．そうすると，ある一つの解について見れば，その解はL/n回の摂動しか行えないことになります．つまり，少ない摂動回数で逐次SAと同様，あるいはそれ以上の精度の解を得るためには，それぞれの解が適切なレンジで摂動し，効率のよい探索が行われなくてはなりません． そして，TPSA/ANが良好な結果をもたらすという事実は，このことが実現できているということを示しています． 要 各温度における効率の良い摂動 ・・・ 適応的近傍により実現

TPSA/AN(case1) ＜ TPSA/AN(case2) 並列処理による速度向上 エネルギー計算の負荷 100倍 TPSA/AN(case1) ＜ TPSA/AN(case2) 最後に，本手法は並列アルゴリズムですので，並列処理による速度向上について触れておきます． これは縦軸に，逐次SAの計算速度を１としたときのTPSAの速度向上率を表しています．こちらのcase1は，先ほどのRastrigin関数を解いたときの結果です．この問題は，非常に計算負荷が小さかったので，8台の計算機で約1.8倍の速度向上しか得られなかったのですが，この問題の計算負荷を100倍にすると8台で約6倍の結果が得られました． まずまずの結果ですが，線形速度向上に近いものを得ようとするなら，実装方法を変更を検討しなければならないと思います．これは，今後の課題です．

まとめ 温度並列SAの応用範囲の拡張 連続最適化問題への応用 適応的近傍を持つ温度並列SA(ＴＰＳＡ/ＡＮ)の提案 まとめは，このようになっています．

まとめと今後の課題 ＜ 一様分布 Boltzmann SA Fast SA Corana SA VFSR Dekkers & Aarts Press & Teukoslky ランダム摂動 ﾗﾝﾄﾞｽｹｰﾌﾟ依存 ランダム摂動 ﾗﾝﾄﾞｽｹｰﾌﾟ依存 一様分布 = SA/FN TPSA/FN Corana SA = SA/AN TPSA/AN ＜ TPSA化すべき手法 連続最適化問題のためのより実用的な温度並列SAの提案と検証 より局所探索の効率が良い摂動(傾斜法，シンプレックス法)の導入 並列計算機への実装の工夫 より複雑な現実世界の実際の最適化問題への応用

研究発表リスト 論文 1. 三木光範，笠井誠之：PVMによる仮想並列計算機の構築とオブジェクト指向型計算モデルにおける性能評価，同志社大学理工学研究報告，Vol. 40，No. 1，pp. 1-10 (1999) 2. (投稿中，採録決定) 三木光範，廣安知之，笠井誠之：連続最適化問題への温度並列シミュレーテッドアニーリングの応用，情報処理学会論文誌 並列処理特集 (2000) 講演 1. 三木光範，廣安知之，笠井誠之，谷村勇輔，池内智悟，中野 猛：PCクラスタによるいくつかの計算事例，第13回計算力学講演会，同志社大学，1998/9/11 2. 三木光範，笠井誠之：PVMを用いたPCクラスタによる並列計算，フロンティア事業研究発表会 ，京都リサーチパーク，1998/11/14 3. 三木光範，笠井誠之：温度並列シミュレーテッドアニーリングのトラス構造物最適化への応用，日本機械学会第11回計算力学講演会，関西大学100周年記念会館，1998/11/18 4. 三木光範，廣安知之，笠井誠之：連続変数を持つ最適化問題への温度並列シミュレーテッドアニーリングの応用，第14回 超並列計算研究会，北陸先端科学技術大学院大学，1998/11/27 5. 三木光範，廣安知之，笠井誠之：連続最適化問題への温度並列シミュレーテッドアニーリングの応用，情報処理学会 並列処理シンポジウム99，pp.135-142 ，1999/6/20 6. 笠井誠之，三木光範，廣安知之：適応的温度並列シミュレーテッドアニーリング，日本機械学会1999年度年次大会，慶應義塾大学 三田キャンパス，1999/7/29 7. Mitsunori MIKI, Tomoyuki HIROYASU, Masayuki KASAI and Motonori IKEUCHI: Temperature Parallel Simulated Annealing with Adaptive Neighborhood for Continuous Optimization Problem, IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS’99) , MIT, Cambridge, Massachusetts, U.S.A., 1999/11/4 8. 笠井誠之，三木光範，廣安知之：問題に適応する摂動近傍を持つ温度並列シミュレーテッドアニーリング，第27回数理モデル化と問題解決研究会，奈良女子大学，1999/11/25 9. (投稿中，査読結果待ち) 三木光範，廣安知之，笠井誠之：適応的近傍を持つ温度並列シミュレーテッドアニーリング，2000年記念並列処理シンポジウム JSPP2000 (2000)

Appendix

目次 １．研究背景 ２．シミュレーテッドアニーリング (SA) ３．従来の並列SA ４．温度並列SA (TPSA) ５．研究目的 ７．拡張アルゴリズムTPSA/ANの提案 ８．実験結果 ９．まとめ 10．今後の課題

研究背景 ヒューリスティック探索手法 長所 短所 複雑な問題を解くことができる． 高い計算負荷 シミュレーテッドアニーリング (SA), 遺伝的アルゴリズム (GA), セルオートマトン (CA), ニューラルネット (NN) 長所 複雑な問題を解くことができる． 短所 高い計算負荷 パラメータ設定が困難 (e.g. SAではクーリングスケジュールの決定が困難) Several heuristics search methods have been proposed for optimization problems which contain a lot of local optima. For example, simulated annealing, genetic algorithms, cellar automata, neural network is favored by many researchers. One of the most attractive advantages of these methods is that it can process cost functions possessing quite arbitrary degrees of nonlinearities. But these methods also have disadvantages. They need high computational costs. And it is difficult to determine parameters peculiar to each methods. (In the case of SA, you have to determine the parameters called “cooling schedule”, but it is difficult.)

Simulated Annealing (SA) GA 生物の進化をモデル化 最適化に応用 SA 物理現象をモデル化 初期解 最適解 弱い 微生物 強い 人間 進化 本研究で扱うSAを，前の3人の発表にあったGAと比べて簡単にイメージをつかんでいただきます． GAは，微生物が長い進化の果てに人間になったように，生物の進化をモデル化した最適化手法であり， 初期解 最適解 高ｴﾈﾙｷﾞｰ 非結晶 低ｴﾈﾙｷﾞｰ 結晶 焼きなまし （アニーリング）

Feature of SA 長所 短所 複雑な問題を解くことができる． 実装・コード化が容易である． 真の最適解が統計的に得られる保証がある． 短所 最適解を得るまでの計算時間が長い． クーリングスケジュールを決定するのが困難 The advantages of SA are these ones. SA can process cost functions possessing quite arbitrary degrees of nonlinearities. It can be implemented quite easily. It can statistically guarantee finding an optimal solution. The disadvantages are these ones. SA needs a lot of computation time to find the optimum solution. And it is difficult to determine the proper cooling schedule which defines the behavior of the algorithm.

温度並列シミュレーテッドアニーリング (TPSA) 確率的に良質な解が低温PEに移動 解交換 解交換 解交換 最高温 高温 低温 最低温 温度並列SAのアルゴリズムの概念図は，この図のようになります． この図は，4つの温度用に4つのプロセッサを用いる例です． まず，4つの初期解を生成しそれぞれのプロセッサに1つずつ与えます． そして，それぞれのプロセッサに異なる温度を担当させます． それぞれのプロセッサは，それらの温度を一定に保ち，解摂動と受理判定による通常の逐次SAを行っていきます． そして，ある回数の反復計算を行うと，それぞれがお互いの解を交換します．解を交換するルールは，良い解が高温プロセッサに存在した場合には必ず交換し，そうでない場合でもある確率にしたがって交換することにします． これらの動作により，結果として良質な解が低温プロセッサの方に集まり， 最終的に最低温度プロセッサから解を得ます． 解摂動 受理判定 解摂動 受理判定 解摂動 受理判定 解摂動 受理判定

連続最適化問題のためのSA Coranaの手法 : 適応的な近傍 Dekkers & Aartsの手法 : 傾斜法を解摂処理に組み込む Very Fast Simulated Re-annealing : 感度を用いる (Adaptive Simulated Annealing) Fast Annealing : コーシー分布を用いる Boltzmann Annealing : 正規分布を用いる miscellaneous これらの連続空間のためのSAの特徴は解摂動時に 以下の手法を取り入れることである． エネルギー関数のランドスケープの情報を利用する． 処理の進行とともに近傍レンジを小さくしていく． There are several sequential SA algorithms for continuous optimization problems. The features of these methods are using structural information of objective functions and adjusting neighborhood range in the phase of generating a next state. For example, Corana’s method uses adaptive neighborhood system. Dekkers & Aarts’s method uses quasi-Newton.

連続最適化問題の解摂動 CoranaのSA 一様分布近傍のSA VFSR Boltzmann SA Fast SA x1 x2 一様分布近傍のSA Boltzmann SA Fast SA CoranaのSA VFSR 2 dimensional problem space これまでに連続最適化問題をSAで解こうとした研究で使用されてきた摂動をいくつか紹介しておきます．まず，もっとも単純なものは，現在の解の周りに確率分布を考え，その確率に基づきランダムに次の解を生成するものです．ただし，ランダムすぎると効率が悪いので，探索の履歴から目的関数の形，ランドスケープを考慮して，あるルールに従い，近傍の確率分布を調節するアルゴリズムがあります． ランダムに生成 Solution

連続最適化問題の解摂動 Dekkers ＆ AartsのSA 近傍は単純な確率分布ではない 関数の傾斜を評価する ランダム x1 2 dimensional problem space ランダム 傾斜法 また，目的関数のﾗﾝﾄﾞｽｹｰﾌﾟを考慮する方法として，DekkersらのSAでは，傾斜法を利用し，ランダムな摂動と組み合わせて解摂動を実現しています．

連続最適化問題の解摂動 Press & TeukolskyのSA 優 劣 Simplex（単体）として 解を表現 x1 2 dimensional problem space Press & TeukolskyのSA Simplex（単体）として 解を表現 優 劣 また，少々特殊な方法としてPressらのSAでは，一般的に問題空間上の1点として表現してする解を，Simplexとして表現します．そして，Simplex上の各頂点のｴﾈﾙｷﾞｰを見比べて，もっとも悪い解を消滅させるようなSimplexの変形を解の摂動としています．

本研究の目的 従来のTPSAの応用 ＝ 組合せ最適化問題 TPSAの応用範囲の拡張 連続最適化問題のためのTPSAの新しいアプローチの提案 適応的近傍を持つ温度並列SA (TPSA/AN： Temperature Parallel Simulated Annealing with Adaptive Neighborhood) TPSAは，これまで組み合わせ最適化問題に適用されてきました． それはベースになっているSAがもともとそのためのアルゴリズムだからです． そのTPSAの応用範囲の拡張を考えます． 本研究では，連続最適化問題のためのTPSAの新しいアプローチを提案します． 我々が提案するのは，連続最適化問題のためのTemperature Parallel Simulated Annealing with Adaptive Neighborhoodです．

温度に対する近傍レンジの調節 －Coranaの手法－ 高温時の近傍レンジ 連続空間では，近傍レンジ(探索領域)の設定が解の精度に影響を与える． 高温時には，大域探索が行われるように，近傍レンジが大きくなくてはならない． 低温時には，局所的な探索により精度が向上するように，近傍レンジが小さくなくてはならない． x2 ここでは，TPSAに組み込む近傍レンジ調節のメカニズムを説明します． 連続空間の探索において，大域的な探索は大きな近傍レンジである方が効率的な探索ができると考えることが出来ます．一方，解の精度を向上させるための局所的な探索は，小さな近傍レンジを用いなければなりません． そこで，高温時には大きな近傍レンジ，低温時には小さな近傍レンジを用いることにします． 低温時の近傍レンジ x1

受理率に関する近傍レンジの調節 －Coranaの手法－ x2 x1 大きすぎる近傍 小さすぎる近傍 各温度での摂動の受理率と却下率を元に近傍レンジを調節する． 却下が多ければ 受理が多ければ 近傍レンジを 小さくする 近傍レンジを 大きくする また一方で，目的関数の勾配が急な地点を探索する場合，「大きすぎる」近傍レンジによる摂動は，Metropolis基準により却下されてしまうので，探索効率を考えてレンジを小さくしなければなりません． さらに，勾配が平坦な地点では，「小さすぎる」レンジは解の向上の度合いが小さくなってしまうので，レンジを大きくしなければなりません． そこで，このようなメカニズムを実現するために，受理と却下の割合が１：１に保たれるような，近傍レンジの調節プロセスを用いることになります． 受理率を５０%に保つ

大域探索能力の指標 －最大温度決定時における－ B x2 問題空間領域の各境界線に最も接近した解と境界線との距離の平均値 e.g. 2次元では， (A+B+C+D) / 4 C A x1 Problem space D シミュレーテッドアニーリングにおいては，“温度”と呼ばれる重要なパラメータを決定しなければなりませんが，本研究のアルゴリズムでは独自の方法でそれらを決定することができます． 最高温度は，計算時間と探索能力のトレードオフから決定します． 具体的には，候補となるいくつかの温度を用意し，それらの一定温度のもとにSAを実行させ，その時の計算時間と，その時に問題空間の境界線に近づいた解，例えば2次元では右上の図のように4つの境界に最も近づいた4つの解のことであり，それらの解と境界線の距離の平均，つまりA,B,C,Dの距離の平均を記録するという予備実験を行います． 計算時間は右の図のように温度が上がれば増加していきます． またA,B,C,Dの平均は

制御パラメータの決定 －最大温度ー 最大温度は計算時間と大域探索能力のトレードオフから決定する． 予備実験 1. 最大温度の候補となる温度で一定温度の逐次SAを実行． 2. 探索されない領域の大きさと計算時間を計測． 3. 大域探索能力と計算時間のトレードオフを考える． . シミュレーテッドアニーリングにおいては，“温度”と呼ばれる重要なパラメータを決定しなければなりませんが，本研究のアルゴリズムでは独自の方法でそれらを決定することができます． 最高温度は，計算時間と探索能力のトレードオフから決定します． 具体的には，候補となるいくつかの温度を用意し，それらの一定温度のもとにSAを実行させ，その時の計算時間と，その時に問題空間の境界線に近づいた解，例えば2次元では右上の図のように4つの境界に最も近づいた4つの解のことであり，それらの解と境界線の距離の平均，つまりA,B,C,Dの距離の平均を記録するという予備実験を行います． 計算時間は右の図のように温度が上がれば増加していきます． またA,B,C,Dの平均は .

制御パラメータの決定 －最小温度ー 最小温度は，近傍レンジの大きさが求めようとする解の精度と等しくなるような温度に決定する． 予備実験 1．最小温度の候補となる温度で一定温度の逐次SAを実行． 2．それぞれの温度のときの，近傍レンジの平均値を計測． 3．解の精度を考える． Required accuracy .

実験に使用したパラメータ In this experiment, we use these parameters. The number of processes for TPSA is 32 processes. Maximum temperatures and Minimum temperature for both SA and TPSA are same. The number of iterations of SA is 32 times as many as TPSA. Therefor total computational resources for both SA and TPSA are same. The Markov Length for SA is 10240 steps. The Cooling rate for SA is 0.8. The exchange interval for TPSA is 32 steps.

実験結果 10 trials SA/AN TPSA/AN 実験結果はこのようになります． まず，青線が逐次SA，赤線がTPSAを示しています．また，横軸が設定したレンジ，縦軸に得られた解のエネルギーを示しており．下に行くほど良い解が得られたことを示しています． このグラフを見ると，それぞれの手法において，最良の解を得ることができるレンジの設定があることに気づきます．逐次SAでは1であり，TPSAでは0.5となっています．また，多くの設定においてTPSAは逐次SAより性能が低いということが注目すべき事実です． 一方，本研究で提案するTPSA/ANは，この中のすべての設定において，最も良好な解を得ることが出来ています． TPSA/AN

T0におけるエネルギー履歴

Griewangk関数における結果 SA/AN TPSA/AN

TPSA/ANの効果 Markov chain of sequential SA ・・・ 逐次SAで1つの解がL回の摂動を行う． Parallelization in temperature 逐次SAで1つの解がL回の摂動を行う． nプロセッサでTPSAによる並列化 → ある1つの解は，L/n回の摂動を行う． TPSAでは，解1つあたりの摂動回数が短い． →各温度において効率の良い摂動 が要求される． TPSA/ANの良好な結果は，各温度における効率の良い摂動が実現できていることを示している． TPSA/ANの効果を要約します． ここにL回の摂動を行う逐次SAがあったとします． そして，それを温度並列SAのアルゴリズムにしたがって，nプロセッサで並列化します．そうすると，ある一つの解について見れば，その解はL/n回の摂動しか行えないことになります．つまり，少ない摂動回数で逐次SAと同様，あるいはそれ以上の精度の解を得るためには，それぞれの解が適切なレンジで摂動し，効率のよい探索が行われなくてはなりません． そして，TPSA/ANが良好な結果をもたらすという事実は，このことが実現できているということを示しています．

最適化の実行前にどれだけの計算量が必要かは，わからない 総計算量と解の精度の関係 Rastrigin 常にTPSAが 良好 最適化の実行前にどれだけの計算量が必要かは，わからない Griewank 計算量が多い時に TPSAが良好

まとめと今後の課題 ランダム摂動 Boltzmann SA Fast SA ﾗﾝﾄﾞｽｹｰﾌﾟ依存 VFSR Dekkers & Aarts Press & Teukoslky 一様分布 Corana’s SA ランダム摂動 連続最適化問題のためのより実用的な温度並列SAの提案と検証 より局所探索の効率が良い摂動(傾斜法，シンプレックス法)の導入 並列計算機への実装の工夫 より複雑な現実世界の実際の最適化問題への応用