2 温度調節の必要性
前節の実験結果より，探索初期ではローカルサーチを用いたPSA/GAcは効果的な探索を行うが，探索中盤から終盤にかけて収束が遅くなり，最適解にはローカルサーチを用いないPSA/GAcとほご同時に到達することが分かった．この原因として，ローカルサーチを行った後の温度が高いため，大きな改悪が受理されやすく，ローカルサーチによって得られた低いエネルギー値がその後の探索に影響を及ぼさないということが考えられる．
この問題に対処する方法として，ローカルサーチ後のエネルギー値の減少の度合いに応じて温度を下げることを考える．エネルギー値の減少とともに温度を下げることによって，大幅な改悪を防ぎ，その結果解への収束を早めることができると期待される．
3 温度調節メカニズムの概要
ローカルサーチを効率的に行うために考案した温度スケジューリングでは，ローカルサーチを行うまでのエネルギー遷移の度合いから，ローカルサーチを適用してエネルギー値が減少した後の温度を決定する．
そのためにPSA/GAcによる探索中に，各個体ごとに一定間隔のMCsweepごとにその時のエネルギー値を保存する．また，ここではローカルサーチ間のMCsweep数をローカルサーチ周期と呼ぶこととする．
ローカルサーチ周期になると，保存したエネルギー値を用いてエネルギー値の履歴を近似する曲線を生成し，この曲線を用いてローカルサーチ後のエネルギー値に対応するMCsweep数を決定する．ローカルサーチを用いたPSA/GAcでは，温度はMCsweepごとに冷却される．したがって，MCsweep数が決定されれば，それに対応する温度を決定することができる．そこで，近似曲線からローカルサーチ後のエネルギー値に対応するMCsweep数を決定し，式(3.1)を用いてローカルサーチ後にとるべき温度を決定する．
本アルゴリズムのイメージ図をFig.1に示す．Fig.1において，あるローカルサーチアルゴリズム間隔(Local
Search Interval)内においてエネルギー値を保存(P1,P2,P3,P4,P5)し，それらの値から近似曲線を生成する．ローカルサーチ後，近似曲線からローカルサーチ後のエネルギー値に相当するMCsweep数を求め，新しい温度を決定する．
Fig.1 温度調節メカニズムの概要
4 数値実験
4.1 テスト関数への適用
本実験では，レポートNo.20020508014で作成したタンパク質のエネルギー関数を模擬したテスト関数を対象問題とする．
4.2 パラメータ
本実験で用いたパラメータをTable.1に示す．本手法では，ローカルサーチ間隔までの関数値の減少の度合いを用いてローカルサーチ後の温度を決定する．したがって，ローカルサーチ間隔が短すぎると，関数値に大きな変化が現れないために本手法の効果が十分に現れない可能性がある．したがって，ローカルサーチ間隔にはある程度大きな値を用いる必要がある．
Table.1 パラメータ
パラメータ |
値 |
個体数 |
8 |
総MCsweep |
10000 |
初期温度 |
10.0 |
クーリング率 |
0.999 |
交叉周期 |
20 |
ローカルサーチ間隔 |
300 |
4.3 実験結果
Table.1に示したパラメータを用いて，ローカルサーチ後に温度を下げる場合と，下げない場合それぞれのPSA/GAcについて実験を行った．レポートNo.20020508014で作成したテスト関数の最適解は-205.0であるが，局所最適解は全て-200.0以上の値となっている．したがって，ここでは-204.0以下の値を最適解として扱うこととする．
Fig.2 実験結果
Fig.2は，最適解が得られた5試行について，エネルギー値の履歴の平均を示したものである．Fig.2において，横軸がMCsweep数を，縦軸がエネルギー値を表す．Fig.2（左）は探索初期から終了条件までの関数値の履歴を，Fig.2（右）は最適解付近の関数値の履歴を示している．Fig.2（左）より，ローカルサーチ後に温度調節を行う場合では，温度調節を行わない場合よりも全体的に早く関数値が減少している様子が見られる．また，Fig.2（右）を見ると，温度調節を行う場合では，温度調節を行わない場合よりも約3000MCsweep早く最適解に収束している．
Fig.3 温度履歴
Fig.3は，それぞれの手法における温度の推移を示したものである．横軸はMCsweep数を，縦軸は温度を表す．今回の実験では，ローカルサーチを行う間隔を300MCsweepとしたため，300MCsweepごとに温度が大きく下がっている．
4.4 考察
ローカルサーチを用いたPSA/GAcでは，ローカルサーチ後にエネルギー値が減少する．従来のPSA/GAcでは，ローカルサーチを行うと，エネルギー値のみが減少し温度はローカルサーチ前の値が維持される．その状態ではエネルギー値に比べて温度が高いため，受理率が高くなり，その後の探索で大幅な改悪が高い確率で受理される．その結果，ローカルサーチの効果が薄れてしまう．
それに対し，温度調節を行うPSA/GAcでは，ローカルサーチ後にエネルギー値の減少の度合いに応じて温度を下げる．この操作により，ローカルサーチ後に大幅な改悪が受理される確率が小さくなる．その結果，Fig.2に示したように最適解への収束が従来の温度スケジューリングを持つPSA/GAcよりも大幅に高速化されたと考えられる．
5 結論
本レポートでは，ローカルサーチアルゴリズムの効果を向上させるための，温度調節メカニズムを考案した．この温度調節を行うローカルサーチを用いたPSA/GAcを，No.20020508014で作成したテスト関数に適用したところ，ローカルサーチ後に温度を下げることにより従来のPSA/GAcよりも少ない計算量で最適解を求めることが分かった．
このテスト関数は，タンパク質のエネルギー関数を模擬していることから，温度調節を行うローカルサーチを用いたPSA/GAcはαへリックス構造を持つタンパク質の立体構造予測に対しても有効であることが期待される．
