Edited at

最適化アルゴリズムの異種格闘技戦(比較)

More than 1 year has passed since last update.

この投稿は進化的計算と最適化 Advent Calendar 2017 24日目になります。

すみません!当日までに結果が間に合いませんでした。。。後日更新します。。。

2年前に書いた最適化アルゴリズムを評価するベンチマーク関数まとめがちょこちょこ見られているので、ベンチマーク関数を使った最適化アルゴリズムの比較(異種格闘技戦)を行ってみました。といってもそんなに出場選手はいません。この記事を書くにあたり論文をサーベイしたところこんなにあるのか、、、と少しびっくりしています。


TL;DR


  • 様々な最適化アルゴリズムとベンチマーク関数を組み合わせどれが性能(最適解への距離、反復回数)が良いかを調査した。

後で追記


はじめに

最適化には実数を扱わない組み合わせ最適化、最適解が複数存在する多目的最適化がありますが、今回触れる最適化は実数であり、解が一意に存在する最適化を扱います。


きっかけ

数多くの最適化アルゴリズムを提唱しているXin-She Yangさんが書かれたNature-Inspired Optimization Algorithmsという本のアマゾンレビューにこんなレビューが書かれていました。


The book does not provide a comprehensive comparison to highlight each algorithm performance.

1- The book presents some new algorithms, such as Bat, Cuckoo, and Flower algorithms. However, the author always shows a comparison with other algorithms like GA and PSO but there is no comparison provided between Bat, Cuckoo, and Flower algorithms.

2- The author wrote in the Preface "We do not encourage readers to develop new algorithms such as grass, tree, etc.", at the same time, he proposes several algorithms which is a contradiction.

3- I gave 3 stars because the book is written nicely and contains some useful information.


Google翻訳をもとに意訳すると、

1は、新しいアルゴリズムが既存のアルゴリズムと比較されていない

2は、著者は自然界をアイディアにした新しいアルゴリズムを作るべきではないと本で述べているのに、著者は多数作っている。

と書かれているようです

2はブーメラン的な記述に対する指摘ですが、1の内容はこの本に限らず、新しい最適化アルゴリズムを研究開発している方にも当てはまることではないでしょうか。昔の同技法と比べ少しでも改善ができれば良いのではなく、幅広く比較し検証すべきと思います。

と偉そうに書きましたが、素人に言われなくても重々承知なことだと思うので、私個人の趣味として各種最適化アルゴリズムとベンチマーク関数を用いて比較検討を行ってみました。


こんなにあるよ最適化アルゴリズム

最適化アルゴリズムは、最適化したい関数の情報を使うものと使わない2つに分類されます。特に、関数の情報を使わないアルゴリズムで、自然界にヒントを得た最適化アルゴリズム(Nature Inspired Algorithm)は多数提案されています。さらにその改良版も多数提案されており、下記に記載した以上のアルゴリズムが存在します。

微分を使用して最適化をする手法


  1. Steepest Descent Method (勾配法)

  2. Newton Method(ニュートン法)

微分を使わず最適化をする手法


  1. Hill-Climbing algorithm(山登り法)

  2. Pattern Search

  3. Nelder-Mead

  4. Bayesian Optimiztaion

自然界にヒントを得た最適化手法(一部組み合わせ最適化手法も混ざっています。。。)

特に有名なアルゴリズムは太文字斜体にしています。


  1. Anarchic society optimization

  2. Ant colony optimization

  3. Artifical Fish Swarm Optimization

  4. Artificial bee colony

  5. Artificial cooperative search

  6. Atmosphere clouds model

  7. Backtracking optimization search

  8. Bacterial Foraging Optimization Algorithm

  9. Bat algorithm

  10. Bee colony optimization

  11. Bee system

  12. BeeHive

  13. Bees algorithms

  14. Bees swarm optimization

  15. Big bang-big Crunch

  16. Biogeography-based optimization

  17. Black hole

  18. Brain Storm Optimization

  19. Bumblebees

  20. Cat Swarm Optimization

  21. Central force optimization

  22. Charged system search

  23. Consultant-guided search

  24. Cuckoo search search

  25. Cultural Algorithms

  26. Dendritic Cell Algorithm

  27. Differential evolution

  28. Differential search algorithm

  29. Dolphin echolocation

  30. Eagle strategy

  31. Eco-inspired evolutionary algorithm

  32. Egyptian Vulture

  33. Electro-magnetism optimization

  34. Estimation of Distribution Algorithm

  35. Evolutionary Strategy

  36. Fast bacterial swarming algorithm

  37. Firefly algorithm

  38. Fish-school Search

  39. Flower pollination algorithm

  40. Galaxy-based search algorithm

  41. Gene expression (Programing)

  42. Genetic algorithm

  43. Genetic Programing

  44. Glowworm swarm optimization

  45. Good lattice swarm optimization

  46. Grammatical evolution

  47. Gravitational search

  48. Great salmon run

  49. Group search optimizer

  50. Harmony search

  51. Heat transfer search

  52. Hierarchical swarm model

  53. Honey Bee Algorithm

  54. Human-Inspired Algorithm

  55. Imperialist competitive algorithm

  56. Intelligent water drop

  57. Invasive weed optimization

  58. Japanese tree frogs calling

  59. Krill Herd

  60. League championship algorithm

  61. Marriage in honey bees

  62. Memetic algorithm

  63. Monkey search

  64. OptBees

  65. Paddy Field Algorithm

  66. Particle swarm optimization

  67. Queen-bee evolution

  68. River formation dynamics

  69. Roach infestation algorithm

  70. Self-propelled particles

  71. Shuffled frog leaping algorithm

  72. Simulated annealing

  73. Social emotional optimization

  74. Spiral optimization

  75. Stochastic difusion search

  76. Termite colony optimization

  77. Virtual ant algorithm

  78. Virtual bees

  79. Virus Colony Search

  80. Water cycle algorithm

  81. Weightless Swarm Algorithm

  82. Wolf search


ルール


評価方法

評価はいたってシンプル、後述する最適化アルゴリズムに各種ベンチマーク関数を解かせ、アルゴリズムが探索した最適解を得る。1度だけではまぐれの可能性もあるので複数回実行し評価指標を得る。


  • 評価指標


  1. 指定した反復回数毎の解

  2. 最適解とアルゴリズムが計算した解の距離(最適解の近さ)

  3. 最善・最悪の最適解、平均とその分散

  4. 最適解の平均とその分散


  • アルゴリズム固有のパラメータ

それぞれの最適化アルゴリズムが保有するパラメータの設定値(集団数、特殊なパラメータ)は別途記述する。


  • 各アルゴリズム共通のパラメータ

反復回数は10,000とする


最適化アルゴリズム

自作のLibOptimizationに実装されているアルゴリズムを対象としました。

昔から知られるNelder-Mead Method, Pattern Search, Simulated Annealing、自然界にヒントを得たアルゴリズムであるGeneic Algorithm, Particle Swarm Optimzation, Differential Evolution, Cuckoo Search, FireFly, Evolution Strategyとその改良アルゴリズムを評価対象としています。


  • Nelder Mead Method

  • Pattern Search

  • Simulated Annealing

  • BLX-alpha and JGG(Just Generation Gap)

  • UNDX(Unimodal Normal Distribution Crossover) and JGG

  • SPX(Simplex Crossover) and JGG

  • REX(Real-coded Ensemble Crossover) and JGG

  • PCX(Parent Centric Recombination) and G3(Generalize Generation Gap)

  • PSO(Standard)

  • PSO using Linear Decrease Inertia Weight

  • PSO using Chaotic inertia weight(CDIW-PSO)

  • PSO using Chaotic inertia weight(CRIW-PSO)

  • PSO using Adaptive inertia weight

  • DE/rand/1/bin

  • DE/rand/2/bin

  • DE/best/1/bin

  • DE/best/2/bin

  • JADE(self adaptation DE)

  • Standrad Cuckoo Search

  • FireFly algorithm

  • Evolution Strategy (1+1)-ES )


使用するベンチマーク関数

ベンチマーク関数は多数存在します(これ参照)。全て確認するというの一つの方法ですが性質を整理して選んで評価するのも一つの方法と思います。個人の見解ですが、最適化問題で解く評価関数は下記のような性質を1つまたは2つ以上持っていると考えています。下記性質を組み合わせて持り比較ができるようなベンチマーク関数を選びました。

No.
評価関数の性質
説明

1
変数依存性の有無
他の変数が少し変化すると評価値が大きく変化する性質の有無

2
関数の形状(単峰/多峰)
大域的最適解の探索能力確認(局所解にとどまらないかどうか)

3
関数の形状(急峻な大域的・局所解)
大域的最適解の探索能力確認(局所解にとどまらないかどうか)

4
関数の形状(平坦の有無)
大域的最適解の探索能力確認(平坦が続くと探索が打ち切られる可能性)

5
高次元
高次元関数における大域的最適解の探索能力確認

6
ノイズの有無
実世界の最適化問題ではノイズが存在(例:正規分布に従うホワイトノイズ)

7
不連続の有無(微分の可否)
微分を用いたアルゴリズムは使用不可

選択したベンチマーク関数は以下の通りです。性質のうち微分不可、ノイズは除外しました。

関数名
変数依存性の有無
関数の形状(単峰/多峰)
関数の形状(急峻な大域的・局所解)
関数の形状(平坦の有無)
高次元
ノイズの有無
不連続の有無(微分の可否)
備考

Sphere function
×

×
×
2,10,50
-
×

Rosenbrock function


×

2,10,50
-
×

De Jong’s function F5
-



2
-
×
初期値を離す

Rastrigin function
-

×
×
2,10,50
-
×
初期値を離す


結果

後で追記


まとめ

後で追記


参考文献


  1. Valdez, Fevrier, Patricia Melin, and Oscar Castillo. "A survey on nature-inspired optimization algorithms with fuzzy logic for dynamic parameter adaptation." Expert systems with applications 41.14 (2014): 6459-6466.

  2. Fister Jr, Iztok, et al. "A brief review of nature-inspired algorithms for optimization." arXiv preprint arXiv:1307.4186 (2013).

  3. Bhuvaneswari, M., et al. "Nature Inspired Algorithms: A Review." International Journal of Emerging Technology in Computer Science and Electronics 12.1 (2014): 21-28.