この投稿は進化的計算と最適化 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）は多数提案されています。さらにその改良版も多数提案されており、下記に記載した以上のアルゴリズムが存在します。
微分を使用して最適化をする手法
- Steepest Descent Method (勾配法)
- Newton Method(ニュートン法)
微分を使わず最適化をする手法
- Hill-Climbing algorithm(山登り法)
- Pattern Search
- Nelder-Mead
- Bayesian Optimiztaion
自然界にヒントを得た最適化手法（一部組み合わせ最適化手法も混ざっています。。。）
特に有名なアルゴリズムは太文字斜体にしています。
- Anarchic society optimization
- Ant colony optimization
- Artifical Fish Swarm Optimization
- Artificial bee colony
- Artificial cooperative search
- Atmosphere clouds model
- Backtracking optimization search
- Bacterial Foraging Optimization Algorithm
- Bat algorithm
- Bee colony optimization
- Bee system
- BeeHive
- Bees algorithms
- Bees swarm optimization
- Big bang-big Crunch
- Biogeography-based optimization
- Black hole
- Brain Storm Optimization
- Bumblebees
- Cat Swarm Optimization
- Central force optimization
- Charged system search
- Consultant-guided search
- Cuckoo search search
- Cultural Algorithms
- Dendritic Cell Algorithm
- Differential evolution
- Differential search algorithm
- Dolphin echolocation
- Eagle strategy
- Eco-inspired evolutionary algorithm
- Egyptian Vulture
- Electro-magnetism optimization
- Estimation of Distribution Algorithm
- Evolutionary Strategy
- Fast bacterial swarming algorithm
- Firefly algorithm
- Fish-school Search
- Flower pollination algorithm
- Galaxy-based search algorithm
- Gene expression (Programing)
- Genetic algorithm
- Genetic Programing
- Glowworm swarm optimization
- Good lattice swarm optimization
- Grammatical evolution
- Gravitational search
- Great salmon run
- Group search optimizer
- Harmony search
- Heat transfer search
- Hierarchical swarm model
- Honey Bee Algorithm
- Human-Inspired Algorithm
- Imperialist competitive algorithm
- Intelligent water drop
- Invasive weed optimization
- Japanese tree frogs calling
- Krill Herd
- League championship algorithm
- Marriage in honey bees
- Memetic algorithm
- Monkey search
- OptBees
- Paddy Field Algorithm
- Particle swarm optimization
- Queen-bee evolution
- River formation dynamics
- Roach infestation algorithm
- Self-propelled particles
- Shuffled frog leaping algorithm
- Simulated annealing
- Social emotional optimization
- Spiral optimization
- Stochastic difusion search
- Termite colony optimization
- Virtual ant algorithm
- Virtual bees
- Virus Colony Search
- Water cycle algorithm
- Weightless Swarm Algorithm
- Wolf search
ルール
##評価方法
評価はいたってシンプル、後述する最適化アルゴリズムに各種ベンチマーク関数を解かせ、アルゴリズムが探索した最適解を得る。1度だけではまぐれの可能性もあるので複数回実行し評価指標を得る。
- 評価指標
- 指定した反復回数毎の解
- 最適解とアルゴリズムが計算した解の距離（最適解の近さ）
- 最善・最悪の最適解、平均とその分散
- 最適解の平均とその分散
- アルゴリズム固有のパラメータ
それぞれの最適化アルゴリズムが保有するパラメータの設定値（集団数、特殊なパラメータ）は別途記述する。
- 各アルゴリズム共通のパラメータ
反復回数は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 | - | × | 初期値を離す |
結果
後で追記
まとめ
後で追記
参考文献
- 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.
- Fister Jr, Iztok, et al. "A brief review of nature-inspired algorithms for optimization." arXiv preprint arXiv:1307.4186 (2013).
- Bhuvaneswari, M., et al. "Nature Inspired Algorithms: A Review." International Journal of Emerging Technology in Computer Science and Electronics 12.1 (2014): 21-28.