📂最適化理論

遺伝的アルゴリズムにおけるカオス演算とは何ですか?

用語 ¹

遺伝的アルゴリズムにおける カオス演算^{chaos operation} とは、突然変異を起こすときにカオス写像を用いて解の多様性を高める手法を指す。

説明

カオス演算は遺伝的アルゴリズムで突然変異操作を行うとき、変異を起こす次元のドメインが閉区間 $[a, b]$ のように表されるとき、正規化を行った後、次のようなロジスティック写像などを用いて新しい解を生成する。 $$ x_{n+1} = r x_{n} \left( 1 - x_{n} \right) $$ ロジスティック写像で $r = 4$ の場合、$x_{n+1}$ は完全に決定論的^{deterministic}でありながら、特定のいくつかの初期条件を除いては初期条件に敏感なので、解空間全体を広く探索できる。

理論的根拠?

ロジスティック写像の固定点^{fixed point}を除けばカオス演算が解空間を大きく探索できることは分かるが、単純に一様分布からサンプリングするのと何が異なるのか？

いくつかの文献でカオス演算が良好な性能を示すと報告されているが、その理由は正確には分からない。個人的にはロジスティック写像の自然不変測度を考えると、解が閉区間の両端に近い位置にある場合に十分有利になり得るのではないかと考えている。

ロジスティック写像の $\rho$ はまるでベータ分布に似た確率密度関数のように見えるが、実装そのものを含めてランダムサンプリングより有利な点があるように思える。