シミュレーテッド・アニーリング(SA法)の概要と実験結果

ツイート

プロダクト開発第二部の岡野です。

今回はシミュレーテッド・アニーリング(SA法)の概要と実験結果をお伝えいたします。

近年、マルウェア研究では機械学習などを用いた検知手法が模索されています。機械学習の多くは学習過程において最適化問題を解決する必要が出てきます。最適化では、本来は最適な値ではないが近傍では最適値となるような局所解にはまり、脱出できないケースが問題とされます。例えば山登り法では、改悪方向に遷移しないため谷のある解空間では局所解にはまります（図1）。一方でSA法は、一定の確率で改悪方向にも遷移させることによって局所解からの脱出を可能としています。

図1

SA法の概要

SA法は金属工学から転用された技術です。金属を高温の液状にし、徐々に温度を下げることで、最小エネルギー状態を保持した秩序ある構造の状態を作り出す「焼きなまし」をコンピュータ上で再現した技術です。アルゴリズムは下記のとおりです。

1. 温度の初期値を決定

2. 解の候補を取得（改善する場合は受理、改悪の場合も一定の確率で受理）

3. 一定回数2.を試行したら温度を下げる

4. 温度が下がりきるまで2-3を繰り返す

2.で挙げた一定の確率には下記のMetropolis法が用いられるケースが多いです。

※T = 温度、ΔE = 今の解と新しい解候補との差

つまり、温度が高いほど、また改悪度合いが小さいほど受理されやすくなります。

実験結果

下記のような評価関数から、最適解となるx=-1.2を探すという実験を行います。初期値はx=2とします。

山登り法の場合、谷があるためx=1.6の局所解から抜け出せません。SA法の場合、パラメータを下記のように設定することで、局所解を乗り越えてx=-1.19という最適解に近い値を安定的に見つけ出すことができました。

・冷却率：0.995

・反復回数：1000

・近傍探索範囲：0.01

まとめ

SA法は簡素な実装で安定して局所解からの脱出が可能であり、有用なアルゴリズムですが、下記のような問題が残っています。

１．計算量が多い

極度に計算量が多いアルゴリズムとなっており、実行時間に制限のある環境下では解空間の探索が不十分となり、最適解を見つけ出せない可能性があります。

２．パラメータに性能が依存

探索結果がパラメータ（特に冷却率）に大きく依存し、説くべき問題ごとにパラメータの試行錯誤による調整が不可欠となります。

今後は、局所解からの脱出が可能という特性を活かし、機械学習手法への応用を目指します。これによって学習精度を上げ、検知率を向上させたいと考えています。

関連記事

緊急レポート：韓国サイバー攻撃マルウェア詳細解析結果

SpyEye解析レポート

.NET製マルウェアの検出手法に関して