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

この投稿は進化的計算と最適化 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翻訳をもとに意訳すると、
１は、新しいアルゴリズムが既存のアルゴリズムと比較されていない
２は、著者は自然界をアイディアにした新しいアルゴリズムを作るべきではないと本で述べているのに、著者は多数作っている。
と書かれているようです

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

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

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

最適化アルゴリズムは、最適化したい関数の情報を使うものと使わない２つに分類されます。特に、関数の情報を使わないアルゴリズムで、自然界にヒントを得た最適化アルゴリズム（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 )

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

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

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.