焼きなまし法と粒子群最適化法の探索挙動を可視化してみた

目次

0. はじめに

 以前書いたブログ(超個体型データセンターにおける群知能クラスタリングの利用構想 - クマガリウムぶろぐ)の構想実現を進めるために、最適化アルゴリズムの基本的なところを理解するため、山登り法をはじめ、焼きなまし法や粒子群最適化法の探索挙動を可視化した結果を簡単にまとめてみます。

※このあたりお詳しい人がいたらコメント、補足など大歓迎

1. 最適化アルゴリズム

1.1 山登り法

 山登り法は、現在の解より近傍の解のほうが良い場合(今回は、値が小さい場合)に、現在の解と近傍の解を入れ替えて極値を探索する探索アルゴリズムです[1]。探索手法の中では最も単純かつ代表的な手法ですが、大域的極値以外の局所的極値に陥った場合に抜け出すことが出来ない欠点を持っています。

f:id:kumagallium:20190724111408p:plain:h200

1.2 焼きなまし法

 焼きなまし法(あるいは、シミュレーテッドアニーリング(SA))は、材料工学における焼きなまし(アニーリング)という物理プロセスに着想を得た最適化手法です[2]。アニーリングとは、物質を融解状態になるまで加熱し,徐々に冷却する操作のことであり、このアニーリングにより,分子がエネルギーが最も少ない状態に配列し,結晶構造を形成させることができます。この概念を最適化計算に利用しています。新しい点はランダムに生成され、その新しい点が現在の点より改善される場合は受け入れ、改悪される場合も一定の確率で受け入れます。その確率は、温度が高いほど、また変化量(新しい点と現在の差)が小さいほど受け入れる確率が高くなる関数となっています。それにより、高温では大域的な解の探索、低温では局所的な解の探索(極低温では山登り法と同義)が行えるため、局所的極値に陥ることを避けることができます。 本手法においては、近傍をどのように定義するか、温度スケジュールをどのように定義するかが非常に重要となる。

改悪される場合にも受け入れる確率は、以下のMetropolis法を用いることが多いようです。 { \displaystyle \Delta E}は、現在の解と新しい解との差を表します。

 { \displaystyle
p = \exp \left( - \frac{\Delta E}{T} \right)
}

f:id:kumagallium:20190724111039p:plain

f:id:kumagallium:20190723152702g:plain:w600

シミュレーテッドアニーリング(SA) 画像出典元:Wikipedia

1.3 粒子群最適化(Particle Swarm Optimazation: PSO

 粒子群最適化についての説明は、他のブログ(粒子群最適化(Particle Swarm Optimization: PSO)をGoで実装してみた - Fire Engine)でわかりやすく説明されていますが、一応ここでもしておきます。

  粒子群最適化は、餌を探す鳥の群れなどの行動に着想を得た最適化手法です。以下の図のように、各鳥が今までに得た最良な場所(パーソナルベスト { \displaystyle \vec{p_i} (t)})、他の鳥が得た最良の場所(グローバルベスト { \displaystyle \vec{g_i} (t)})、現在の慣性因子を考慮して次に向かうべき場所を決定します。この条件で移動を繰り返すことによって、最適な位置に鳥たちが集まり、その点が最適解となります。 移動ルールにおいて重要な移動速度の式は、以下のとおりです。 { \displaystyle I}は、慣性係数と呼ばれる定数で、1より小さい値を指定します。 { \displaystyle A_g}および { \displaystyle A_p}は加速度係数と呼ばれる値で、1に近い値を指定します[3]。

 { \displaystyle
\vec{v_i} (t+1) =I \vec{v_i} (t) + A_g \left( \vec{g}(t) - \vec{x_i} (t) \right) \times rand[0,1] + A_p \left( \vec{p_i} (t) - \vec{x_i} (t) \right) \times rand[0,1]
}


f:id:kumagallium:20190507121109p:plain:w400

2 ベンチマークを用いた探索挙動の可視化

 最適化アルゴリズムベンチマークとしては、ここ(python: ベンチマーク関数お試しコード - Qiita[4])が参考になりました。

2.1 Sphere function

 Sphere functionは、以下の式に示すように基本的な関数です。

 { \displaystyle
f(x_1 \cdots x_n) = \sum_{i=1}^{n} x_i^{2}
}

山登り法 大域的極値以外に局所的極値が存在しないため、図のように山登り法でも大域的極値を得ることができました。 f:id:kumagallium:20190723150335g:plain

焼きなまし法 焼きなまし法も、もちろん山登り法と同様に最適解を得ることができました。

f:id:kumagallium:20190724103810g:plain

粒子群最適化 粒子群最適化は、グローバルベストとして最適解を共有することができるため、上記手法よりも比較的少ない探索時間で最適解を得ることができました。 f:id:kumagallium:20190719152059g:plain

2.2 Ackley function

Ackley functionは多峰性関数で、大域的極値の周辺に多数の局所的極値を有しています。

 { \displaystyle
f(x_1 \cdots x_n) = 20 - 20 \exp \left(-0.2 \sqrt{\frac{1}{n} \sum_{i=1}^{n} x_i^{2} } \right) + e - \exp \left( \frac{1}{n} \sum_{i=1}^{n} \cos(2 \pi x_i)  \right)
}

山登り法 近傍の最適解を探索する山登り法では、多峰性のある関数における大域的極値を得ることができませんでした。初期値に近いところにある局所的極値に収束してしまいました。

f:id:kumagallium:20190724095053g:plain

焼きなまし法  焼きなまし法は、改悪される解を許容することで大域的探索できるようにしているため、図に示すように局所的極値に留まることなく、大域的極値に向かって収束できていることが確認できました。 f:id:kumagallium:20190724103501g:plain

粒子群最適化  Ackley関数における大域的極値は、その周辺と比べて極端に小さい値であるため、グローバルベストと各点の値の差が大きくなりやすく、すべての点が急激に大域的極値に収束すしていることが確認できました。

f:id:kumagallium:20190724095204g:plain

2.3 Rastrigin function

 Rastrigin functionは多峰性関数で、非常に多くの局所解を有しています。また、図に示すようにAckley関数と比較すると、大域的に比較的緩やかなお椀状をしていることが確認できます。

 { \displaystyle
f(x_1 \cdots x_n) = 20 - 20 \exp \left(-0.2 \sqrt{\frac{1}{n} \sum_{i=1}^{n} x_i^{2} } \right) + e - \exp \left( \frac{1}{n} \sum_{i=1}^{n} \cos(2 \pi x_i)  \right)
}

山登り法  Ackley関数の場合と同様に、多峰性関数であるため局所的極値に陥る結果となりました。

f:id:kumagallium:20190724095541g:plain

焼きなまし法  非常に緩やに温度を下げる必要があるものの、局所的極値に陥りつつも留まることはなく、大域的極値に収束していることが確認できました。焼きなまし法は、十分に高い温度から十分に緩やかな徐冷をおこなうことで多くの問題を解くことができることがわかりました。ただし、緩やかな徐冷が必要であるため、今回の粒子群最適化などと比べると探索時間が長時間必要でした。

f:id:kumagallium:20190724103608g:plain

粒子群最適化  粒子群最適化は、探索空間上に十分な粒子がある場合においては、多峰性かそうでないかのは比較的関係なく、大域的極値の周辺に短い探索時間で収束することがわかりました。ただし、Rastrigin関数はAckley関数よりも大域的に緩やかなお椀状であるため、大域的極値周辺の局所的極値も十分に小さな値であり、グローベルベストとの差という駆動力が小さくなるため、慣性力による移動が支配的になり大域的極値周辺で解が揺らぐことも確認できました。

f:id:kumagallium:20190719152433g:plain

2.3 Himmelblau's function

 図に示すように、Himmelblau's functionは多峰性関数で、4つの極値を有しています。

 { \displaystyle
f(x, y) = (x^2 + y - 11)^2 + (x + y^2 - 7)^2
}

山登り法 Himmelblau関数は、多峰性関数であるもののその全てが同じ値となる大域的極値と考えることができるため、図に示すようにほぼ問題なく4点に収束していることが確認できました。

f:id:kumagallium:20190724104234g:plain

焼きなまし法  焼きなまし法も、山登り法と同様に4点に収束していることが確認できます。

f:id:kumagallium:20190724104321g:plain

粒子群最適化  一方で、粒子群最適化では、基本的にグローバルベストに向かって移動する手法なので、大域的極値が複数存在する場合、初期値に依存して収束する点が決まることが確認できました。また、点によっては自分が知っているローカルベストが最適であると知って、揺らいでいる様子も図から確認できます。

f:id:kumagallium:20190724104409g:plain

3. おわりに

 最適化アルゴリズムの基本となる山登り法をはじめ、大域的極値が探索できる焼きなまし法や粒子群最適化の基本的な概要と実装、可視化によるそれぞれの挙動の違いを簡単に確認しました。また、それぞれの手法に得意不得意があることも確認できました。例えば焼きなまし法は、多くの関数に適用可能である一方で、パラメータ設定が重要で且つ探索時間が長くかかりました。ただしこの課題についても、現在までに多くの研究が行われていますのでそのあたりも抑えておく必要がありそうです[5]。また、粒子群最適化における、大域的極値と局所的極値との差が小さい場合に収束しない課題についても、多くの研究がされています。さらには、焼き鈍し法と粒子群最適化とを組み合わせた手法[6,7]なども存在するので、そのあたりの調査もまとめたいところですね。

4. 参考

  1. 山登り法 - Wikipedia
  2. Simulated annealing - Wikipedia
  3. 進化計算アルゴリズム入門 生物の行動科学から導く最適解
  4. python: ベンチマーク関数お試しコード - Qiita
  5. [Adaptive simulated annealing - Wikipedia
  6. A New Hybrid Algorithm of Particle Swarm Optimization | SpringerLink
  7. Hybrid PSO-SA Type Algorithms for Multimodal Function Optimization and Reducing Energy Consumption in Embedded Systems