共分散行列適応による非確率的進化戦略（CMA-ES）の時間計算量の削減

本論文は、共分散行列適応（CMA-ES）を用いた非確率的進化戦略に基づく新しい進化的最適化戦略を提案する。この新しいアプローチは、最適解への収束に必要な世代数を削減することを目的としている。世代数、すなわちアルゴリズムの時間計算量を削減することは、大規模な集団サイズを望む場合に重要である: (1) ノイズの影響を減少させるため; (2) グローバル探索特性を向上させるため; (3) アルゴリズムを（高度に）並列のマシン上で実装するため。私たちの方法は、大規模なプロセッサ数に対して好ましくスケールする高い並列アルゴリズムを実現する。これは、大規模集団からの利用可能な情報を効率的に組み込むことによって達成され、共分散行列を適応させるのに必要な世代数を大幅に削減する。元のCMA-ESバージョンは、小規模な集団で共分散行列を信頼性高く適応させるように設計されているが、大規模な集団を効率的に活用することはできない。私たちの修正により、効率が最大10nの集団サイズにスケールアップされる。ここでnは問題の次元である。この方法は多くのテスト問題に適用されており、多くのケースでCMA-ESが二次的な時間計算量から線形の時間計算量に進展できることを示している。