進化計算アルゴリズムの効率性に関する新しい研究成果が発表されました。本研究は、(μ+1)進化戦略(EA)がBinary Value関数(BinVal)の最適化問題を解く際の計算量を大幅に改善したものです。 従来の研究では、(μ+1)EAがBinValの最適解を見つけるために必要な関数評価回数は、Krejca、Neumann、Wittによる上界O(μ^5 n log(n/μ^4))とされていました。これに対して、本研究ではμ = o(n/log n)の条件下で、最大でもO(μ log μ · n log n)回の関数評価があれば最適解に到達可能であることを証明しました。この改善により、計算量は多項式時間内で大幅に削減されています。 特に注目すべき点は、この成果が標準的なビット変異を含む複数の変異演算子に対して成立することです。これにより、進化戦略の実装の柔軟性が確保されながらも、理論的な性能保証を得ることができます。さらに、本研究の結果から、(μ+1)EAがBinValで動作する速度はOneMax関数と比較して最大でもO(log μ · log n)倍の遅延に留まることが示唆されました。これは、異なる最適化問題間での相対的な計算効率を理論的に評価する上で重要な知見となります。