i‰»“IƒVƒ~ƒ…ƒŒ[ƒeƒbƒhƒeƒ“ƒpƒŠƒ“ƒO

第38回 月例発表会（2001年04月） 知的システムデザイン研究室

進化的シミュレーテッドテンパリング

Evolutionary Simulated Tempering

吉田 武史

Takeshi YOSHIDA

Abstract: This paper proposes a new heuristic search method for discrete optimization problems. The simulated annealing is one of effective optimization methods, but a huge amount of computation is required to obtain good solutions. This is due to the excessive high starting temperature, but it is very difficult to determine it. The proposed method firstly uses a very high temperature and rapidly the temperature is cooled down to a very low temperature, and the temperature is increased to a certain value, which is called simulated tempering. The effective tempering temperatures are sought by using multiple search processes and genetic algorithms. From the experiments on traveling salesman problems, the method is found to be very effective and useful.

1 はじめに

シ ミュレ ー テッド ア ニ ー リ ン グ (Simulated Annealing:SA)1) は ，広 範 囲 の 組 み 合 わ せ 最 適 化 問題に有効な汎用近似解法である．しかしながら「温 度」と呼ばれる制御パラメータの推移が解の精度に依 存し，任意の問題に対する一般的な温度スケジュール は明らかになっていない． 一方，これまでの研究において，特定範囲の温度で のアニーリングが SA の性能に大きく影響することがわ かっている2)．我々はすでに解の精度に対する温度の影 響を調べるため，巡回セールスマン問題 (TSP) に関し て，解交換を行わない温度並列 SA(TPSA)3)を適用し， 重要な温度の存在を確認した．しかし，この温度は問題 に依存し，一般的な決定方法は明らかになっていない． そこでアニーリングの効率を示す評価値をもとに GA 操作を行い，自動的に重要温度を求める進化的シミュ レーテッドテンパリング (Simulated Tempering:ST) を 提案する．そののち，提案した手法を TSP に適用し，有 効性を検証する．

2 重要温度の確認

重要温度と他の温度における解摂動の比較を行う．Fig. 1 に，解交換を行わない TPSA を対象問題 eil51 に適用 した結果を示す．この図では，横軸に各プロセスの温度， 縦軸に解の経路長を示す． Fig. 1 では TPSA 終了時に各プロセスが得た最も良 い解の経路長と解探索中に生じるすべての解の平均経 路長を示す．この図より，重要温度ではアニーリング中 に多少の改悪を受理して摂動し，その探索途中で良好な 解を得ることがわかる．そこで，解の動きを示す評価値 を用いて，重要温度を自動的に求める進化的シミュレー テッドテンパリングを提案する． 10-2 ₁₀-1 ₁₀0 ₁₀1 ₁₀2 ₁₀3 ₁₀4 ₁₀5 ₁₀6 400 500 600 700 800 900 1000 1100 Distance Temperature Best Average

Fig. 1 Best and Average of TPSA

3 進化的シミュレーテッドテンパリング

Fig. 1 より局所解が最適解と非常に近い値であるこ とがわかる．また必要以上に高い温度でのアニーリング では解の精度が悪い．そこで一度急激に温度を下げて， 局所解に収束させてから温度を少し上げる方が効率的で あると考えた．このようにして生まれたのがシミュレー テッドテンパリング (ST) である． 3.1 シ ミュレ ー テッド テ ン パ リ ン グ (Simulated Tempering:ST) ST は焼き戻し (Tempering) を模倣した新しいヒュー リスティックサーチである．基本アルゴリズムは SA と ほぼ同じであるが，処理の前半に極低温でのアニーリン グで局所解に収束させ，評価値に基に重要温度を求める のが大きな特徴である． 3.2 並列遺伝的シミュレーテッドテンパリング (Par-allel Genetic ST:PGST) 本発表では，ST を並列化し，GA 操作によって重要 温度を求める並列遺伝的 ST(PGST) を提案する．Fig. 2 に PGST の概念図，Fig. 3 に PGST のアルゴリズム 1

を示す． proc1 proc2 proc3 procN proc4 GA OperationGA Operation 評価値の高い 温度を残す GA OperationGA Operation Fig. 2 PGST 初 期 設 定 極 低 温 で の 探 索 生 成 ・ 受 理 判 定 評 価 値 に よ る 選 択 交 叉 ・ 突 然 変 異 終 了 判 定 Yes 評価周期 No Fig. 3 Algorithm of PGST PGST では各プロセスが一定期間アニーリングを行う (評価周期)．その後，各プロセスの評価値を元に GA の 選択・交叉・突然変異処理を施し，次の評価周期におけ る温度を決定する． 3.3 評価値 評価値の決定方法を Fig. 4 に示す．評価値は (1) 各プ ロセスで 1 周期の解の平均を計算する，(2) (1) による 値の全プロセス平均を次の周期における評価基準に設定 する，(3) 評価基準を下回る受理に対して，解と基準の 差分を加算する，(4) 評価周期ごとに同じ操作を繰り返 す，以上の操作によって決定する． T1 Tn T2 評価周期 ①各プロセスの前周期の解平均 ②全プロセスの平均を 次の周期の基準に 全プロセス平均 評価値 = Σ(解 - 基準) ③評価値を計算

Fig. 4 Evaluation Value

この決定方法によって，頻繁に評価基準を下回る重要 温度付近の評価値は高くなる．そのため GA 操作によっ て全てのプロセスの温度が重要温度付近に集中すると考 えられる．

4 実験結果

Fig. 5 に逐次 SA と PGST の解探索能力の比較を行っ た結果を示す．本実験では最適解が既知の 5 つの対象問 題に逐次 SA と PGST を適用し，最適解から誤差 1%以 内の解を発見したときのアニーリングステップ数を比較 した．Fig. 5 の横軸は問題名，縦軸はアニーリングス テップ数を示す．なお実験結果は 20 回試行した平均値 を示す．

eil51 bier127 kroA100 pr152 pr76 0 50 100 150 200 250 Annealing Steps(×10 3) Problem name SA PGST Fig. 5 PGST Result Fig. 5 より，どの対象問題においても逐次 SA に比べ て PGST の解探索能力が優れていることがわかる．ま た Fig. 6 に eil51 に PGST を適用したときの各プロセ スの温度推移を示す． 0 1000 2000 3000 4000 5000 10-5 10-3 10-1 101 103 105 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 A B C D E F G H I J K L M N O P Q R S T a b c d e f g h i j k l m n o p q r s t Temperature Annealing Steps Fig. 6 Temperature of PGST eil51 における重要温度は 2 付近である．Fig. 6 より PGST では各プロセスの温度が重要温度に集中すること がわかる．

5 結論

ST は評価値を用いて重要温度を自動的に求めるアル ゴリズムである．この ST に GA 処理を組み込み並列化 することによって，重要温度を自動的に求める PGST を提案した．また PGST と SA を比較した結果，PGST が優れた精度を示すことがわかった．

参考文献

1) Kirkpatrick, S., Gelett Jr. C. D., and Vecchi, M. P.:

Op-timization by Simulated Annealing, Science, Vol. 220, No. 4598, pp. 671-680 (1983).

2) David T.Connolly. An improved annealing scheme for the QAP. European Journal of Operational Research, 1990. 3) 小西健三，瀧和男，木村宏一：温度並列シミュレーテッドアニーリン

グ法とその評価，情報処理学会論文誌，Vol.36，No.4，pp.797-807 （1995）